clustering algorithm for non-dimensional data

Question

i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this dataset. i imagine that because the data has no dimensions, a cluster center might consist of several data points and a tolerance, and membership within the cluster might be determined by the average of the distance of a data point to every data point in the cluster center.

please forgive me if this question has a well known solution, i know very little about this kind of problem! my (very limited) research has only turned up clustering algorithms for dimensional data, but i apologize in advance if i've missed something obvious.

thank you!

Answer 1

If the distance function is a metric, then you can employ either $k$-center clustering (where the maximum radius of a ball is minimized) or $k$-median clustering (which minimizes the sum of distances to cluster centers). $k$-center clustering is easy: merely pick the $k$-farthest points, and you're guaranteed to get a 2-approximation via triangle inequality (this is an old result due to Gonzalez).

For $k$-median clustering, there's been a ton of work, too much to review here. Michael Shindler at UCLA has a nice survey of the main ideas.

Both these problems are NP-hard in general, and are hard to approximate to within an arbitrary factor. Note that if you drop the condition of being a metric, things get a lot worse in terms of approximability.

Another, more heuristic approach which might be ok for your application is to use a technique like MDS (multidimensional scaling) to embed your distance matrix in a Euclidean space, and then use one of many different Euclidean clustering methods (or even $k$-means clustering). If you are sure that your distance function is a metric, then you can do a slightly more intelligent embedding into Euclidean space and get a provable (albeit weak) guarantee on the quality of your answer.

Ultimately, as with most clustering problems, your final choice depends on the application, your data size, and so on.

Answer 2

There's also correlation clustering, which has as input information for each pair of items indicating whether they belong in either the same cluster or different clusters.

Answer 3

If you're just looking for good empirical performance, the affinity propagation algorithm usually works better than k-medians. There is code available in several languages and publications describing the algorithm in more detail are here: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

The objective that it tries to maximize is: $$\sum_{i} s(i, c_i)$$

where $s$ is a similarity measure defined between pairs of points (e.g., negative distance), and $c_i \in \mathbf{c}$ gives the cluster that $i$ belongs to. There is one additional parameter given in $s(i, i)$ that controls whether you prefer large or small clusters.

Answer 4

Your question seems to imply that you are looking for an algorithm with decent computational time. Given the size of your vertices (or points) would be to create a weighted graph representation of your data and use Markov Cluster Algorithm (MCL) to cluster the graph.

http://www.micans.org/mcl/

MCL is based on random walks through weighted and unweighted graphs to find dense subgraphs. It is able to handle large graphs and has been used in many well-known, well-used bioinformatic programs (such as BLAST). -Boucher

Answer 5

Consider k-nearest neighbour algorithm.