Extract clusters from a graph of absolute-distance edge

Question

I don't know if I have formulated this problem right:

I have tons of items and the distances between each pair of them. Feeding this data into some visualization tool, I am able to create a nice image of network with arbitrarily defined center of the coordinate. (Since I only have distances, which do not imply any coordinate) I can eye-ball some clusters in the graph.

Now I want to show with high confidence that there exists some valid classification of the items.

Let's not ask from where the number of clusters comes. The worst case is I have to search for it exhaustively within a reasonable interval.

I have the distances in a matrix form, where the (row, column) = (i, j) entry is the distance from point i to point j. Distances are normalized by the largest, therefore they range from 0 to 1.

Is there a good way to extract the clusters out of this?

Answer 1

You could start by using a simple k-means clustering algorithm. In this approach, you aim to pick a set of $k$ means $m_i$, and assign each point $x$ in your data to a certain set $S_i$; within each set, you want to minimize the average distance:

$\sum_{i=1}^k\sum_{x\in S_i}|x-m_i|^2 = $ minimum.

Given some guess for the set of means $\{m_i\}_{i=1}^k$, the data points closest to each mean can be found by computing the Voronoi diagram of the means. The means are then updated iteratively.

k-means may be good enough for your purposes, but if you try it and find it insufficient, there is a whole host of other algorithms for this problem. These will all be heuristics rather than give you exact solutions, since clustering is usually NP-complete for any realistic criterion (I think).