12
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Why does non-dimensionality make this problem special? $\endgroup$
    – Raphael
    Oct 22, 2010 at 7:15
  • 1
    $\begingroup$ Some algorithms I saw for clustering (really just k-means) require generation of random data points as seeds, which is not possible with dimensionless data. So, the special requirement is that the cluster centers must be represented by a set of existing data points (perhaps weighted). $\endgroup$
    – paintcan
    Oct 22, 2010 at 15:51

5 Answers 5

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Thank you for the quick & clear overview. It will take me at least a few days to determine if you have answered my question. It seems I have a lot to learn before I understand my problem sufficiently :) $\endgroup$
    – paintcan
    Oct 21, 2010 at 18:01
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes, that's another good example. And of course Warren is an expert on this ! I don't know if the OP's input was +/- though, or could be converted via thresholding. if so, this is definitely a viable option. $\endgroup$
    – Suresh Venkat
    Oct 21, 2010 at 19:24
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

Consider k-nearest neighbour algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Raphael, the k-NN algorithm is not really a clustering algorithm, is it ? unless you repeatedly pull out the k neighbors of a node ? $\endgroup$
    – Suresh Venkat
    Oct 21, 2010 at 21:56
  • $\begingroup$ We draw an edge between nodes that are in each other's sets of $k$ nearest nodes. In the resulting graph, cliques (almost-cliques) should be some kind of cluster. I figured that since we are building up the graph, identifying these cliques should not be too hard, but I did not think it through completely. $\endgroup$
    – Raphael
    Oct 22, 2010 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.