<p>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.</p>

<p><a href="http://www.micans.org/mcl/">http://www.micans.org/mcl/</a></p>

<p>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</p>

CC BY-SA 2.5
2010-11-10T00:55:30.840Z
2010-11-10T00:55:30.840Z
Christina Boucher
<p>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:
<a href="http://www.psi.toronto.edu/index.php?q=affinity%20propagation" rel="nofollow">http://www.psi.toronto.edu/index.php?q=affinity%20propagation</a></p>

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

<p>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.</p>

CC BY-SA 2.5
2010-10-21T21:09:07.113Z
2010-10-21T22:33:20.097Z
2010-10-21T22:33:20.097Z
dan_x
<p>There's also <a href="http://geomblog.blogspot.com/2009/08/correlation-clustering-i-dont-like-you.html">correlation clustering</a>, which has as input information for each pair of items indicating whether they belong in either the same cluster or different clusters.</p>

CC BY-SA 2.5
2010-10-21T19:24:09.710Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-10-21T18:22:34.240Z
2010-10-21T18:22:34.240Z
Warren Schudy
<p>Consider <a href="http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm" rel="nofollow">k-nearest neighbour algorithm</a>.</p>

CC BY-SA 2.5
2010-10-21T21:56:21.587Z
Raphael, the k-NN algorithm is not really a clustering algorithm, is it ? unless you repeatedly pull out the k neighbors of a node ?
Suresh Venkat
CC BY-SA 2.5
2010-10-22T07:14:55.373Z
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.
Raphael
CC BY-SA 2.5
2010-10-21T21:41:09.130Z
2010-10-21T21:41:09.130Z
Raphael
<p>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).</p>

<p>For $k$-median clustering, there's been a ton of work, too much to review here. Michael Shindler at UCLA <a href="http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf">has a nice survey</a> of the main ideas. </p>

<p>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. </p>

<p>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. </p>

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

CC BY-SA 2.5
2010-10-21T18:01:05.700Z
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 :)
paintcan
CC BY-SA 2.5
2010-10-21T17:22:43.307Z
2010-10-21T17:22:43.307Z
Suresh Venkat
<p>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.</p>

<p>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.</p>

<p>thank you!</p>

CC BY-SA 2.5
2010-10-22T07:15:27.780Z
Why does non-dimensionality make this problem special?
Raphael
CC BY-SA 2.5
2010-10-22T15:51:11.440Z
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).
paintcan
<machine-learning><lg.learning><clustering>
clustering algorithm for non-dimensional data
paintcan
# clustering algorithm for non-dimensional data

(Asked by: username_0 on 2010-10-21)

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!

**Tags:** machine-learning, lg.learning, clustering
> **Comments:**
> **username_1**: Why does non-dimensionality make this problem special?  
> **username_0**: 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).  

---

## 5 answers

### Answer by username_5 on 2010-10-21. Score: 15 | Accepted answer

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](http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf) 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.

> **Comments:**
> **username_0**: 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 :)  

---

### Answer by username_2 on 2010-11-10. Score: 5

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 by username_3 on 2010-10-21. Score: 5

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 by username_4 on 2010-10-21. Score: 5

There's also [correlation clustering](http://geomblog.blogspot.com/2009/08/correlation-clustering-i-dont-like-you.html), which has as input information for each pair of items indicating whether they belong in either the same cluster or different clusters.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_1 on 2010-10-21. Score: 1

Consider [k-nearest neighbour algorithm](http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm).

> **Comments:**
> **username_5**: Raphael, the k-NN algorithm is not really a clustering algorithm, is it ? unless you repeatedly pull out the k neighbors of a node ?  
> **username_1**: 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.  

---

