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.
 A: 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.
A: 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.
A: 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

