# Logging similarities between vectors with R

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?

-
The question is indeed vague, because you do not define what "similar" means, and that is a very important point. For example are [0.99,1.99] and [1,2] "similar"? Are [1,2,3,4,0] and [1,2,3,4,100000] "similar"? Are non-integer points even possible? –  Erik May 8 '12 at 6:58
The match has to be mostly exact. 1 needs to match with another 1, 2 with another 2, and so on, and only allow variation in maybe 1 of the 6 points. –  Subtle Array May 8 '12 at 11:55

@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.

-
Thank you for your reply. I have text files full of points, whole numbers without decimals. Example: [1, 90, 23, 42, 11, 20, 4, 40, ...], [8, 20, 70, 90, 54, 50, 5, ...] I would like to cluster the patterns between these datasets where there is only minor variation. Example: The program would acknowledge [1, 2, 3, 4, 5, 6] in the first set, and [1, 2, 3, 4, 0, 6] in the second as a pattern, and log both sets of numbers into a text file. I think if I just knew the name(s) of this type of clustering, I'd be able to look it up and research it, and learn how to apply it. –  Subtle Array May 8 '12 at 12:14
Are you looking for clustering, in which many points will aggregate together, or simply pairing, in which a point is testing against a single other point? I read your original question as a search for pairs, but perhaps what you're looking for is called "cluster analysis," or as @Anony-Mousse writes, "subspace clustering." –  Ash May 8 '12 at 13:32
Mahalanobis distance (gauging similarity of an unknown sample set to a known one) sounds close to what I'm looking for. Biclustering also sounds promising, but I'm still trying to make sense of the definition. I probably need to learn more linear algebra. In short: I'm looking for the name of the algorithm or technique used to automatically group similar patterns, where only 1 or maybe 2 of the elements are different, between 2 data sets. Element order is also a factor. [1, 2, 3, 4, 0, 6] and [1, 2, 3, 4, 5, 6] would be considered a match, but [3, 6, 5, 2, 1, 4] wouldn't. –  Subtle Array May 8 '12 at 15:35
I did some research, and updated and simplified my post so that it would be more clear. –  Subtle Array May 8 '12 at 16:23
Ash, you've been a great help. Thank you very much! –  Subtle Array May 8 '12 at 17:09

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

-
Looks very promising. I'll look it up now. Thank you for your reply. –  Subtle Array May 8 '12 at 12:18
I've been doing a lot of research into clustering algorithms, and I finally know enough now to fully appreciate this reply. Thank you again, Anony-Mousse. –  Subtle Array May 27 '12 at 2:02