# Extract clusters from a graph of absolute-distance edge

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?

• What did you already try? What literature did you read? – Wolfgang Bangerth Jul 13 '13 at 12:22

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.