2
$\begingroup$

I have a symmetric score matrix and I would like to cluster the values in two dimensions rather than through a tree. Is there any method / library that would take the input matrix and treat the scores as attractive/repelling forces? The final outcome would then be a two-dimensional visualization of clusters. (Something similar is available for proteins http://www.eb.tuebingen.mpg.de/research/departments/protein-evolution/software/clans.html , but I have other data)

$\endgroup$
1
$\begingroup$

The standard approach to do this is by using multidimensional scaling (MDS).

Depending on your data, you may be able to use metric MDS, or only non-metric MDS.

On the other hand, "attactive/repelling forces" is the motivation for force directed graphs. But these are sometimes hard to tune so that they neither explode nor shrink.

Anyway, try both of them.

$\endgroup$
1
$\begingroup$

I think you are muddling two things that should not be muddled. However, there are tools that will do the two things you want and visualise them concurrently. These are graph visualisation tools that can do both a force-directed lay-out and a clustering (from a choice of graph clustering algorithsm, although BioLayout only offers mcl). The clustering may be indicated for example by node color. The ones I am most familiar with (but there are others) are Cytoscape and BioLayout - the latter is able to handle much larger graphs.

By way of explanation of my opening statement, a force-directed lay-out cannot in general lead to a good clustering by just considering the coordinates in 2-dimensional or 3-dimensional Euclidean space, if the input data is high-dimensional to begin with. No wonder - as a lot of information has been discarded. It is very easy to construct examples exhibiting this behaviour and real-life data shows the same. One thought experiment is this: construct a six-dimensional hypercube and lay it out in 2 dimensions. Inevitably, some nodes that are 6 steps apart in the graph will be in close proximity in the projected space. But you do not have to take my word for it, just try the tools I mentioned.

$\endgroup$
  • $\begingroup$ I agree with you about the reduction problem and that one should choose methods carefully based on the data properties and what you eventually want to show. For my case, however, upscaling from the similarity matrix to n-d space is a legit application. $\endgroup$ – El Dude Jun 15 '15 at 16:46
1
$\begingroup$

A popular method that extends metric Multi-dimensional Scaling (MDS) is the ISOMAP algorithm. Per your comment, this is available in scikit learn as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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