# 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