# Clustering algorithm and distance function for sets

I am willing to run a clustering algorithm on data records consisting in sets each one representing the features enabled at a certain time.

Is there any clustering algorithm you would recommend me to try out? In my first tests I'm experimenting with K-means, but maybe there is something more suitable.

Is there any distance function that works well with sets? I guess that there is something better than the Euclidean distance but I don't have may clue on how the better metric could look like.

-

There are some problems associated with k-means here.

First of all, k-means is designed for Euclidean distance. Literally. It does not require triangle inequality, but it requires that the mean minimizes variance. Which might not hold for other distance functions.

Furthermore, the mean of a binary vector -- assuming you try to represent your sets as binary vectors -- will not be a binary vector. So it doesn't map back to a set. And that can cause artifacts. Essentially, all the means will be somewhere in the center of the data set, much closer to each other than to the actual instances. That is not really what k-means meant to do.

There are tons of distance functions for sets, and an even larger number of clustering algorithms that do not require means to minimize the variance. Try distance based clustering methods. A good starting point is Wikipedia. Hierarchical (but note that these are often implemented in $O(n^3)$, thus slow) and density based (where density is often computed by distance based estimations)

On the scientific side, try this survey:

• Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek (2011).
Density-based Clustering.
WIREs Data Mining and Knowledge Discovery 1 (3): 231–240. doi:10.1002/widm.30
-
Wikipedia isn't bad for that, actually. – Anony-Mousse Sep 28 '12 at 6:05
Wikipedia calls them density based clustering methods while I was looking for distance based. Thanks for the clarification. – mariosangiorgio Sep 28 '12 at 6:26
Some of the density based are grid-based. So these probably don't make a lot of sense for you. But those that use distances for density estimation should work. – Anony-Mousse Sep 28 '12 at 6:31

You can convert set information to binary vectors (0/1 for presence/absence of a feature), then use a binary metric (e.g. Jacard, Tanimoto, Russell-Rao, Skal-Sneath, Yule metric) to cluster your data. I would try to pick a good visualization tool to explore the results and decide which algorithm/metric is the best for the data/problem.

-
 Thanks for your answer. Do you recommend me any visualization tool? – mariosangiorgio Sep 27 '12 at 13:07 I would not easily discount Euclidean distance, it often works pretty well even for binary data compared to other binary metrics. Which tool is appropriate for you depends very much on your data and requirements. What kind of data sets are you dealing with? How many features and objects? Do you know how many clusters are in your data? – James LI Sep 28 '12 at 16:50

I would start with distances such as proposed by James Li. They are sometimes known as fingerprint distances. Then, in my experience, it can be a good idea to use graph clustering, although this may depend on the number of features that you have. If this is large and dimensionality is thus large, and if 'set intersection' models data proximity well, then graph clustering is in my opinion the best approach. If the number of features is limited, graph clustering can still work well, but one should also consider the option of comparing feature vectors directly and use an algorithm such as OPTICS - perhaps you have already done that.

-
Can you please explain me how I am supposed to map my feature into a graph? – mariosangiorgio Sep 27 '12 at 13:08
You have objects described by features. Suppose you use the tanimoto coefficient. You can then make a long list of triples 'A B w' where A and B are objects, and w is the tanimoto coefficient. Such a triple represents a single edge or arc, specifying the two nodes and the edge weight. Many graph clustering software packages (such as found in igraph, networkx, or mcl) will accept this format. Most graph clustering algorithms expect a similarity (e.g. tanimoto, Pearson correlation). For very dense data it may be necessary to specify a threshold value, only allowing w larger than the threshold. – micans Sep 27 '12 at 13:31
Thank you for your explanation. Now it is clear. – mariosangiorgio Sep 27 '12 at 13:39