Logging similarities between vectors with R

Question

I'm trying to write a program that automatically groups similarities between vectors. The vectors are comprised of point coordinates.

For example (assuming X, Y, and Z are numbers):
Data Set 1: [1, 8, X1, X2, 6, X3, X4, 8, 5, 4, 9, 4, Y1, Y2, Y3, Y4, Y5, 1, 5, 7]
Data Set 2: [X1, X2, X3, X4, 6, 3, 5, 4, 3, 6, Y1, Y2, Y3, 7, Y4, Y5, 7, 3, 5, 7]
Data Set 3: [X3, 5, 6, 4, 3, 6, X1, Y3, 3, 5, 6, X4, 2, 6, 7, X2, Y2, 5, 6, X4, Y4]

X1, X2, X3, and X4, and Y1, Y2, Y3, Y4, and Y5 don't match perfectly with each other between Data Set 1 and 2, but they're within very close proximity, and in the same order, unlike the example in Data Set 3.

Is there an algorithm that can do this kind of grouping?

Answer 1

@Subtle Array, you're right that the question is vague, but I think it's legitimate to look for a starting point and refine your question through exploration. @Erik's question is one that you will definitely have to address along the way.

R is very good at handling both simultaneous and iterative operations across data sets. You could, for example, calculate the Mahalanobis distance for each of your 5-dimensional points, then calculate the differences between a pair of points, and tell you they are "matched" if the difference is below your threshold.

Or, you could have R do an element-wise difference between two points. This is, anyway, the default behaviour. Once you have a 5-dimensional array of differences, you could tell R to check if the median difference is below your threshold, or if most of the elements are below your threshold.

Reading back over it, my answer sounds vague too. In short, this is certainly a problem that R can solve in lots of ways. If this is the sort of problem you work with regularly, you will be well-rewarded for learning R now.

EDIT:
Given the updates to your question, I think two approaches might be viable. Mahalanobis distance, as I mentioned above, is implemented in the R function "mahalanobis()," which I believe is part of the "stats" library. The function takes a matrix and the corresponding covariance matrix to calculate a set of Mahalanobis scores. For your vector set, each vector will get a single number corresponding to its multidimensional dispersion.

But you could also try the following:

x1=1:10
x2=1:10; x2[c(3,5)]=c(43,3)
x3=1:10; x3[c(5,7)]=c(24,14)

this.list = list(x1,x2,x3)
lapply(this.list, function(x){
sum.differences = unlist((lapply(this.list, function(y){
    sum(abs(x-y))
})))
which.min(sum.differences[sum.differences != 0])
})

This toy code will find the minimum total distance between any two of your vectors. It's a quick-and-dirty approach, and I'm sure lots of people on this forum could write something much more clever, but I hope it might at least get you going.

Answer 2

Have a look at the field of subspace clustering. Also known as Biclustering.

In your example, the two points could be part of a subspace cluster in Dimensions 1,2,3+5, while dimension 4 would be considered irrelevant or "noise" for the cluster.

Subspace clusterings can live with clusters having different relevant dimensions. The main challenge is how to deal computationally with large numbers of attributes. If you have $d$ dimensions, you'd potentially have to check $O(2^d)$ subspaces for clusters. So you can't check all of them, but need clever methods of searching for interesting subspaces.

https://en.wikipedia.org/wiki/Clustering_high-dimensional_data#Subspace_Clustering

You might also want to look into the Curse of dimensionality (e.g. on Wikipedia)

https://en.wikipedia.org/wiki/Curse_of_dimensionality