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?

  • $\begingroup$ What did you already try? What literature did you read? $\endgroup$ – 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.

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).

| cite | improve this answer | |

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.