Matching Similar Items from a Set

Question

I'm trying to match items. Given a set of $n$ items I can rank on a scale from 0 to 100 of how similar they are to one another. For instance, if item $n_1$ is milk and item $n_2$ is also milk, then the similarity between $n_1$ and $n_2$ would be 100%. If $n_3$ is soda, then the similarity between $n_1$ and $n_3$ would be, perhaps, 80%, and so on.

I'm trying to figure out how to group the $n$ items into groups of similar items, but it's a challenging problem. I run into the following issue: A horse is similar to a cow, which is similar to a goat, which is similar in part to goat cheese, which is similar to cheese, which is correlated with crackers. However, I wouldn't expect a horse to be in the same group as crackers. Each item might be pair-wise correlated, but the beginning and end might not be.

Any ideas?

Answer 1

What you want to do here is partition N observations into K clusters who exhibit similar properties. This is called clustering and you can find more info here.

Since you already have a numerical similarity measure, this makes me think about using the K-Means algorithm, in which you operate in several steps:

• Initialize cluster centroids randomly
• Assign each observation to the cluster corresponding to the closest centroid.
• Update the centroids as the new mean of the elements in the cluster.

You can check for convergence when the centroids have stopped moving or within a certain threshold.

This would ensure that the items in each cluster are somewhat correlated, and you can have more fine-grained clusters by increasing the number of clusters in the algorithm (the "K"). Finding the number of clusters depends on each problem, and I advise you try a bunch of values for your problems, look at what comes out grouped together, and see what makes sense.

Hope that helps.

Answer 2

I think what you are looking for is called "cluster analysis" or "clustering". Many different algorithms exist. In your case, you would want some "connectivity clustering", i.e. group elements together based on a property that links each two.

Have a look at the clustering algorithms in scikits.learn (Python code) and the references mentioned there.