# Clustering similar values in a matrix

I posted this on stackoverflow.com yesterday and its had very few views. I came across this stackexchange site and thought its got to be worth an ask:

I have an interesting problem and I'm sure there is an elegant algorithm with which to solve the solution but I'm having trouble describing is succinctly which would help finding such an algorithm.

I have a symmetric matrix of comparison values e.g:

-104.2732   -180.3972   -130.6969   -160.8333   -141.5499   -139.2758   -144.7697   -114.0545   -117.6409   -140.1391
-180.3972   -93.05421   -171.618    -162.0157   -156.8562   -156.3221   -159.9527   -163.2649   -170.127    -153.2709
-130.6969   -171.618    -101.1591   -154.4978   -143.6272   -116.3477   -137.2391   -125.5645   -128.9505   -131.6046
-160.8333   -162.0157   -154.4978   -96.96312   -122.7894   -141.5103   -127.7861   -149.6883   -153.0445   -130.2555
-141.5499   -156.8562   -143.6272   -122.7894   -101.7487   -141.451    -123.9087   -138.7041   -139.2517   -125.3494
-139.2758   -156.3221   -116.3477   -141.5103   -141.451    -99.99486   -134.6553   -132.7735   -138.7249   -134.1319
-144.7697   -159.9527   -137.2391   -127.7861   -123.9087   -134.6553   -100.0683   -141.3492   -138.0292   -120.5331
-114.0545   -163.2649   -125.5645   -149.6883   -138.7041   -132.7735   -141.3492   -106.8555   -115.58 -139.3355
-117.6409   -170.127    -128.9505   -153.0445   -139.2517   -138.7249   -138.0292   -115.58 -104.9484   -140.4741
-140.1391   -153.2709   -131.6046   -130.2555   -125.3494   -134.1319   -120.5331   -139.3355   -140.4741   -101.3919


The diagonal will always show the maximum score (as it is a self-to-self comparison). However I know that of these values some of them represent the same item. Taking a quick look at the matrix I can see (and have confirmed manually) that items 0, 7 & 8 as well as 2 & 5 and 3, 4, 6 & 9 all identify the same item.

Now what I'd like to do is find an elegant solution as to how I would cluster these together to produce me 4 clusters.

Does anyone know of such an algorithm? Any help would be much appreciated as I seem so close to a solution to my problem but am tripping at this one last stumbling block :(

Cheers!

• Which clustering algorithms have you tried so far?
– Ken
Commented Apr 26, 2012 at 16:08
• @Ken: I've not found any clustering algorithm that seemed applicable ... which doesn't help ... so I've been trying to work out a system from base principles ... I had some, seemingly, good results using a progressive refinement method based on a mean and standard deviation but I found cases where outliers messed up the mean and stddev so badly that nothing got clustered together ...
– Goz
Commented Apr 26, 2012 at 17:22
• Well, look at distance and density based clustering algorithms; as you have a similarity-matrix-like thing. Commented Apr 26, 2012 at 17:42
• @Anony-Mousse: I must admit I've been wondering whether I could apply k-means clustering to this problem. Though with that I'd need to know the number of clusters ... I guess I could perform a distance minimisation iteration (basically modify the number of clusters until I get the minimum distance on clustering). I'm just not sure how to choose a distance metric for such a plan ...
– Goz
Commented Apr 26, 2012 at 18:54
• k-means makes only sense for euclidean distance, as the mean only minimizes euclidean, not arbitrary distances. In other cases, k-means may file to converge and run into an infinite loop. K-means is heavily limited, it's not just the stupid k parameter. Commented Apr 27, 2012 at 6:34

Hierarchical clustering may be a good solution because it provides flexibility, a quantitative assessment of cluster similarity and grouping, and--by means of dendrograms--a natural graphical way to analyze the data.

Let's illustrate with some R commands. First, the data, for those who might wish to follow along:

x <- matrix(c(-104.2732, -180.3972, -130.6969, -160.8333, -141.5499, -139.2758, -144.7697, -114.0545, -117.6409, -140.1391,  -180.3972, -93.05421, -171.618, -162.0157, -156.8562, -156.3221, -159.9527, -163.2649, -170.127, -153.2709, -130.6969, -171.618, -101.1591, -154.4978, -143.6272, -116.3477, -137.2391, -125.5645, -128.9505, -131.6046, -160.8333, -162.0157, -154.4978, -96.96312, -122.7894, -141.5103, -127.7861, -149.6883, -153.0445, -130.2555, -141.5499, -156.8562, -143.6272, -122.7894, -101.7487, -141.451, -123.9087, -138.7041, -139.2517, -125.3494, -139.2758, -156.3221, -116.3477, -141.5103, -141.451, -99.99486, -134.6553, -132.7735, -138.7249, -134.1319, -144.7697, -159.9527, -137.2391, -127.7861, -123.9087, -134.6553, -100.0683, -141.3492, -138.0292, -120.5331, -114.0545, -163.2649, -125.5645, -149.6883, -138.7041, -132.7735, -141.3492, -106.8555, -115.58, -139.3355, -117.6409, -170.127, -128.9505, -153.0445, -139.2517, -138.7249, -138.0292, -115.58, -104.9484, -140.4741, -140.1391, -153.2709, -131.6046, -130.2555, -125.3494, -134.1319, -120.5331, -139.3355, -140.4741, -101.3919), nrow=10)


An "average" linkage method appears to get the results you have derived:

x.cluster <- hclust(dist(x), method="average")
plclust(x.cluster, labels=as.character(0:9))


In this plot (produced by the second R command), the "height" is the Euclidean distances between the columns of the matrix x (thought of as 10-vectors).

The clusters (1), (3(4(69))), (0(78)), and (25) are evident among the leaves near the bottom of this plot. What you consider to be a "cluster" depends on the cutoff height. E.g., cutting the tree at height 52 reproduces your four clusters:

> split(0:9, cutree(x.cluster, h=52))
$1 [1] 0 7 8$2
[1] 1

$3 [1] 2 5$4
[1] 3 4 6 9


whereas cutting it slightly lower (at 40) will split column 3 away from (4(69)).

For links to the documentation for hclust, plclust, and cutree, as well as links to alternative clustering solutions in R, please see the Cluster Analysis Task View.