14
votes
$\begingroup$

I want to cluster ~22000 points. Many clustering algorithms work better with higher quality initial guesses. What tools exist that can give me a good idea of the rough shape of the data?

I do want to be able to choose my own distance metric, so a program I can feed a list of pairwise distances to would be just fine. I would like to be able to do something like highlight a region or cluster on the display and get a list of which data points are in that area.

Free software preferred, but I do already have SAS and MATLAB.

$\endgroup$

9 Answers 9

Reset to default
11
votes
$\begingroup$

GGobi (http://www.ggobi.org/), along with the R package rggobi, is perfectly suited to this task.

See the related presentation for examples: http://www.ggobi.org/book/2007-infovis/05-clustering.pdf

$\endgroup$
3
  • $\begingroup$ Thanks for the suggestion, @Shane. ggobi looks promising, I am installing it right now and will give it a try :) $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:12
  • 1
    $\begingroup$ Works fine on other platforms, but gtk does not play nice with OSX. $\endgroup$
    – anonymous
    Aug 10, 2010 at 17:02
  • 3
    $\begingroup$ gtk is fine on OSX. $\endgroup$
    – hadley
    Jan 21, 2011 at 5:44
5
votes
$\begingroup$

Exploring clustering results in high dimensions can be done in R using the packages clusterfly and gcExplorer. Look for more here.

$\endgroup$
1
  • $\begingroup$ Thanks, but is there any benefit to using clusterfly rather than calling ggobi directly? The website only mentions clustering methods, which are interesting, but not my primary goal just yet. gcexplorer has less informative website, but looks like it is for visualizing data after it has already been split to clusters. I will give them a try once I get to that point, but not what I need right now. $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:12
4
votes
$\begingroup$

(Months later,) a nice way to picture k-clusters and to see the effect of various k is to build a Minimum Spanning Tree and look at the longest edges. For example,

alt text

Here there are 10 clusters, with 9 longest edges 855 899 942 954 1003 1005 1069 1134 1267.
For 9 clusters, collapse the cyan 855 edge; for 8, the purple 899; and so on.

The single-link k-clustering algorithm ... is precisely Kruskal's algorithm ... equivalent to finding an MST and deleting the k-1 most expensive edges.

— Wayne, Greedy Algorithms.

22000 points, 242M pairwise distances, take ~ 1 gigabyte (float32): might fit.

To view a high-dimensional tree or graph in 2d, see Multidimensional Scaling (also from Kruskal), and the huge literature on dimension reduction. However, in dim > 20 say, most distances will be near the median, so I believe dimension reduction cannot work there.

$\endgroup$
2
votes
$\begingroup$

I've had good experience with KNIME during one of my project. It 's an excellent solution for quick exploratory mining and graphing. On top of that it provides R and Weka modules seamless integration.

$\endgroup$
1
  • $\begingroup$ Looks like a useful program, but their webpage does not do a good job of convincing me it will solve this exact problem. It looks like it may be too broad, too many features I don't care about, making it hard to do the simple things. I will give it another look if the other choices don't work out. $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:19
2
votes
$\begingroup$

Also have a look at ELKI, an open-source data mining software. Wikimedia commons has a gallery with images produced with ELKI, many of which are related to cluster analysis.

$\endgroup$
0
1
vote
$\begingroup$

Take a look at Cluster 3.0. I'm not sure if it will do all you want, but it's pretty well documented and lets you choose from a few distance metrics. The visualization piece is through a separate program called Java TreeView (screenshot).

$\endgroup$
1
  • $\begingroup$ Thanks for the suggestion, but the ability to choose my own measure of distance is critical, so this won't work to me. Someone else may find it useful, though. $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:06
1
vote
$\begingroup$

GGobi does look interesting for this. Another approach could be to treat your similarity/inverse distance matrices as network adjacency matrices and feeding that into a network analysis routine (e.g., either igraph in R or perhaps Pajek). With this approach I would experiment with cutting the cutting the node distances into a binary tie at various cutpoints.

$\endgroup$
4
  • $\begingroup$ I thought of this but there doesn't seem to be a reasonable cut point, and domain experts can't justify one either. $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:15
  • $\begingroup$ I would think this could be fairly arbitrary for your stated purpose - honestly, you might not even need to actually cut into binary, just recode a tie value label on a scale of 1 to some manageable number, then progressively hide/show the ties at various levels (optionally also hiding/eliminating any pendants & orphans along the way). Not directly responding to your request as written, but why not take a more typical approach and use a hybrid clustering method that doesn't use initial centroids to identify preliminary clusters, then feed the centroids from that result into your new analysis? $\endgroup$
    – Shelby
    Aug 10, 2010 at 16:45
  • $\begingroup$ I am guessing you mean to try for many different cutoffs until I see some nice results? I wish to avoid that for standard multiple comparisons reasons. re: your second suggestion I guess I just trust myself better than those algorithms. I use the computer to process large amounts of data too tedious to do by hand, not to replace my thinking. $\endgroup$
    – anonymous
    Aug 10, 2010 at 17:06
  • 1
    $\begingroup$ You're using hypothesis testing language but yet talking about a very exploratory, know-it-when-you-see-it approach @ the same time - so it's not clear what your goal really is for this part of your analysis. If you have hypotheses you're testing later (e.g. predicting cluster membership or using clust membership as predictor) then you can choose not to do things that will tempt bias there. But "multiple comparison" issues don't really figure into the exploratory problem you're describing. The viz cutoffs are just to help you see what's there - but your trust may still be misplaced. $\endgroup$
    – Shelby
    Aug 11, 2010 at 11:48
1
vote
$\begingroup$

Weka is an open source program for data mining (wirtten and extensible in Java), Orange is an open source program and library for data mining and machine learning (written in Python). They both allow convenient and efficient visual exploration of multidimensional data

$\endgroup$
1
  • $\begingroup$ Orange's features page says 'under construction' and they don't list screenshots like what I am doing. weka has no features list at all. They may be able to do what I want, but if they don't promote the feature, how can I tell. I am more convinced by the other choices. $\endgroup$
    – anonymous
    Aug 10, 2010 at 15:24
0
votes
$\begingroup$

DataMelt free numeric software includes Java library called JMinHep. Please look at the manual under the section "Data clustering". It provides a GUI to visualize multidimensional data points in X-Y, and run a number of data clustering algorithms.

$\endgroup$