1
$\begingroup$

I would like to run some kind of clustering algorithm on my data (which can be thought of as a collection of vectors). I do not want to start with using k-means because I do not know what k I should have or what k makes sense to have. Instead, I would rather have each cluster satisfy some kind of condition.

For example, how can I cluster a collection of $n$ vectors $\{v_1, \ldots, v_n | v_i \in \mathbb{R}^m\}$ into clusters $C = \{c_1, \ldots, c_D\}$ ($D \leq n$ and $D$ is not known a priori) such that $\forall d \in \{1, ..., D\}, f(c_d = \{v_1, \ldots\})\ \text{is true}$ where $f$ is some function that returns a boolean output (true if a condition is satisfied by a cluster $c_d$ and false otherwise).

To continue the example, $f(c)$ could be $$ f(c) = \left\{ \begin{array}{ll} true & \text{if } \max\limits_{i, j}(d(v_i, v_j)) \leq r \text{ for some $r$ known a priori}\\ false & \text{otherwise. }\\ \end{array} \right. $$

In the above example, putting each of the $n$ vectors into its own cluster satisfies my criteria, but I would also want to build as large clusters as possible.

My question is whether or not these types of clustering algorithms exist and what are they called? If not, what would be your approach to solving the above example?

$\endgroup$
  • $\begingroup$ I think there exist no "general form" solution for such constraining. Everything is dependent on the specific clustering algorithm. Some algorithms can easily accomodate such constraint, others might be modified to accomodate it, still others might not at all. $\endgroup$ – ttnphns Aug 20 '15 at 16:15
3
$\begingroup$

There exist literally hundreds of clustering algorithms.

It is not as of research had stopped when k-means was developed.

Are you sure there isn't some obscure clustering algorithm that does exactly that? Look for constrained clustering, for example.

For example, canopy clustering can trivially be abused to never produce clusters with a diameter larger than D. Just set T1=T2=0.5*D. It's not really canopy clustering anymore (but the obvious greedy first stab at an approximate solution), but it satisfies your requirements.

complete-linkage clustering

probably is exactly what you are looking for. If you cut the tree at height D, every cluster should have a diameter of at most D.

$\endgroup$
  • $\begingroup$ I am not at all saying that k-means is a pinnacle of clustering techniques, I am just having trouble researching what are the names of clustering techniques that would work in my situation. That's for mentioning canopy clustering. $\endgroup$ – bourbaki4481472 Aug 20 '15 at 20:30
  • $\begingroup$ Canopy is more of a data compression thing than a useful clustering algorithm. But also don't expect us to know all 100+ clustering algorithms... $\endgroup$ – Has QUIT--Anony-Mousse Aug 20 '15 at 20:35
2
$\begingroup$

I think you are over thinking it...

Let $r$ be the max distance between vectors in the same cluster, $d(.,.)$ a distance function, and $f(.,.)$ a function such that:

$$ f(v_i, v_j) = \left\{ \begin{array}{ll} 1 & \text{if } d(v_i, v_j) \leq r\\ 0 & \text{otherwise. }\\ \end{array} \right. $$

First, calculate a binary connectivity matrix $M$ such that element $m_{ij} = f(v_i, v_j) \ \ \epsilon \ \{0, 1\}$.

$M$ now represents a graph where $v_i$ is connected to $v_j$ if their distance is below your threshold. The strongly connected components of this graph are the clusters you are looking for.

If $n$ is large, some algorithms will allow you to find all strongly connected components without calculating $M$ beforehand. For example: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

$\endgroup$
  • 1
    $\begingroup$ Oh! Neat! This approach with making $M$ and then searching for strongly connected components will work with any $f(.,.)$ as long as $f(.,.)$ is symmetric. Moreover, this simplifies my problem because I don't need to give a criteria for a whole cluster, only a criteria for two members of a cluster. $\endgroup$ – bourbaki4481472 Aug 20 '15 at 22:36
  • $\begingroup$ However, do you think your solution gives a unique solution to the problem? $\endgroup$ – bourbaki4481472 Aug 20 '15 at 22:37
  • $\begingroup$ Actually, you're not right, the clusters are not the strongly connected components, but actually the complete subgraphs. You just reformulated the problem in terms of the maximal cliques problem (which is NP-complete). $\endgroup$ – bourbaki4481472 Aug 28 '15 at 21:50
1
$\begingroup$

One option is to use a genetic algorithm. The chromosome could specify which cluster each vector belongs to, and the fitness function could include all the constraints you want, including factors to minimise the number of clusters or maximise the number of vectors per cluster. Mutation could move one vector from one cluster to another, and crossover would move whole clusters from one solution (model) to another. In practice, you'd need to at least specify an upper-bound on the number of clusters.

$\endgroup$
  • $\begingroup$ You don't think there is a more deterministic approach than using a genetic algorithm? Now as I am thinking about it, I could put every vector into its own cluster and then merge clusters until a condition is not satisfied? $\endgroup$ – bourbaki4481472 Aug 20 '15 at 19:03
  • $\begingroup$ That sounds like a form of agglomerative hierarchical clustering, which is also worth trying. One risk of such deterministic algorithms is that they may converge to a locally optimal solution. Stochastic and/or population-based approaches may avoid those, but at greater computational cost. $\endgroup$ – dcorney Aug 21 '15 at 9:39
1
$\begingroup$

One clustering algorithm that might suit your needs well is DBSCAN. This algorithm tries to expand an $\epsilon$-ball around the observed data points, and those that are in each others' neighborhoods are merged into clusters. Points without sufficiently many neighbors in their $\epsilon$ neighborhoods are labeled as noise.

$\endgroup$

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.