In Clustering we want to find optimal Clusters - data points that are close together (measure by a defined distance measure). Is there any "Anti-"Clustering? We have a set of data points and want to find "Anti-"Clusters - subsets with data points that are as far apart as possible (measure by a defined distance measure, for example euclidean distance).

In a concrete application I have a set of people and want to divide these people into n groups as diverse as possible measure with a few predefined criteria (diverse means: as less as possible of the same values of each criteria in each group).

The first time I thought about this it seemed pretty intuitive but I couldn't find any method to create these subsets, maybe I'm to focused on regular Clustering methods. Sorry, if this question is too trivial, but any help would be appreciated!

  • 4
    $\begingroup$ A naive but often serviceable starter definition of a cluster is that its points are like each other and unlike points in other groups. So, it's still clustering. $\endgroup$ – Nick Cox Mar 5 '18 at 14:27
  • $\begingroup$ Suppose you have 4 numbers: $x_i\in (1,2,8, 9)$. Your distance is the $d(i,j)=|x_i-x_j|$. How do you want your two anti-clusters look? (1,8) and (2,9)? $\endgroup$ – Aksakal Mar 5 '18 at 15:18
  • $\begingroup$ Here's an interesting paper on hipsters - the observations that want to maximize their differences with the population end up looking the same. arxiv.org/abs/1410.8001 $\endgroup$ – Aksakal Mar 5 '18 at 20:06
  • $\begingroup$ My post is admittedly rather imprecise. if we have the four numbers and the distance measure given by you, both {(1,8),(2,9)} and {(1,9),(2,8)} would have the same average distance within the clusters. However, {(1,8),(2,9)} would be the better split since there are no differences in the distances within the clusters. $\endgroup$ – Sven E. Mar 5 '18 at 22:10
  • $\begingroup$ Referring to the definition by @NickCox: The definition of clustering is: points are like each other and unlike points in other groups. And the definition of anti-clustering (which I only chose as a name since I don't know any better) should be, that points are unlike within a group and like points in other groups - which in terms expresses that the distances within the clusters should be rather similar to each other. I hope that makes sense. $\endgroup$ – Sven E. Mar 5 '18 at 22:10

It's still clustering that you want, because you're trying to split the data into subsets, which is clustering.

If you clustering algorithm is based on a distance measure, then simple negative of that measure or inverse should accomplish subsetting you request. Some algorithms rely on the distance measure being positive, in this case the inverse should work. You could soften the inverse with a fractional power function, of course.

  • 2
    $\begingroup$ The correctness and utility of this answer are doubtful, because the parallel with clustering is imperfect. In clustering, data are partitioned into subsets whose values are mutually close within each subset but otherwise values in different subsets are far apart. In the present case it appears to be necessary for values within subsets to be mutually far (so far, so good) but no criteria are applied to distances between points in different subsets. Furthermore, nonlinear transformations of distances ought to produce very different solutions and therefore require careful consideration. $\endgroup$ – whuber Mar 5 '18 at 15:03
  • $\begingroup$ You're right that negative difference would lead to observations within subset far from each other, but the subsets to be close to other. However, I think that it's inevitable. $\endgroup$ – Aksakal Mar 5 '18 at 20:07
  • $\begingroup$ Right: that's why this seems fundamentally to be a different kind of problem. $\endgroup$ – whuber Mar 5 '18 at 20:37

There are several related domains:

  1. Outlier detection: find unusual points, rather than typical representatives as in clustering.
  2. Stratified sampling. Choose a random sample such that the samples correspond to different classes. For larger sets, so that the class distribution matches.
  3. Archetypal analysis. Summarize data not by 'average' cluster representatives, but rather by extreme observations that "bound" the clusters.

But you'll certainly need to become more explicit about the formal requirements that you have, some vague intuition is not enough.

Maybe you still want clustering - kmeans tries to minimize the within-cluster variance, which implies that it maximizes the between cluster sum of squares. So in a good kmeans clustering, the typical squared deviation of two objects not in the same cluster is maximized; the clustering does divide the data into partitions that are "as dissimilar as possible".

  • $\begingroup$ Thanks for your answer. I thought about using k-means to help in my problem. My understand is, that k-means minimizes the distance within a cluster and maximizes the distance between the clusters. For my problem I would need to do the opposite. That is to maximize the distance within a cluster and minimize the distances between the clusters (so that the distances within the clusters are rather similar). That why I tried to describe it as "anti-clustering". But it sounds like stratified sampling could be another approach to the problem - I will have to look into this further. $\endgroup$ – Sven E. Mar 5 '18 at 22:18

We have been working on unclusters (and anti-clusters and noclusters) and we have a few definitions that we have been exploring.

  1. the holes between clusters that illustrate where points can not exist.
  2. the density of points on the periphery of a cluster.
  3. the density of clusters (as compared to the density of points in the clusters)
  4. the specificity of the centroid in any given cluster... how much can you move the centroid yet still keep the cluster reasonably intact.
  5. the potential overlap between clusters (coclusters) - we even thought there should be a complex cluster with a real and imaginary components to handle overlapping densities.

k-means is certainly a useful approach, but there seems to be some underlying meaning to these "unclusters"... and we have started to try to model these unclusters so that we can learn optimal numbers of clusters and start with 'better' centroid estimates.

It sounds like you are exploring the density aspect to help with cluster separation and overlap. Certainly a very interesting topic and one that warrants more thought.


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.