1
$\begingroup$

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

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
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your reply. Can you please give me some more detailed reference about something to read about distance based clustering methods? $\endgroup$
    – mariosangiorgio
    Commented Sep 28, 2012 at 1:20
  • 1
    $\begingroup$ Wikipedia isn't bad for that, actually. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Sep 28, 2012 at 6:05
  • $\begingroup$ Wikipedia calls them density based clustering methods while I was looking for distance based. Thanks for the clarification. $\endgroup$
    – mariosangiorgio
    Commented Sep 28, 2012 at 6:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Sep 28, 2012 at 6:31
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. Do you recommend me any visualization tool? $\endgroup$
    – mariosangiorgio
    Commented Sep 27, 2012 at 13:07
  • $\begingroup$ 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? $\endgroup$
    – James LI
    Commented Sep 28, 2012 at 16:50
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you please explain me how I am supposed to map my feature into a graph? $\endgroup$
    – mariosangiorgio
    Commented Sep 27, 2012 at 13:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – micans
    Commented Sep 27, 2012 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.