Is there a way to enforce that a set of points are assigned to the same class when clustering in sklearn or other clustering library?

user_5156760 0
Viewed 325

I would like to use one of sklearn's clustering algorithms but with the restriction that certain sets of points must belong to the same class. For instance, given the set of points below I would like to enforce that all red points belong to the same class and all blue points belong to the same class. I would also like it so that red and blue points can belong to the same class. If this is not possible in sklearn I am also open to using other libraries.

Clustering with some points prespecified

scikit-learn cluster-analysis python
3 Answers

One possible solution which should work for any library is to define a "superpoint" for the blue cluster and another for the red cluster.

So just define the blue superpoint to be the average / median of each blue point and similarly for the red. Then run the clustering on these two superpoints plus the remaining points

user_123953870

The name for this is "constrained clustering," which is a family of semi-supervised clustering approaches in which a user can also supply constraints as:

  1. Must Link - two nodes must belong to the same cluster
  2. Cannot Link - two nodes cannot belong to the same cluster

There's an implementation of the COP-KMeans algorithm, which provides an API like this:

import numpy
from copkmeans.cop_kmeans import cop_kmeans
input_matrix = numpy.random.rand(100, 500)
must_link = [(0, 10), (0, 20), (0, 30)]
cannot_link = [(1, 10), (2, 10), (3, 10)]
clusters, centers = cop_kmeans(dataset=input_matrix, k=5, ml=must_link,cl=cannot_link)
user_124391190

There's actually no need to use constrained clustering in your case. Let's say all the points are a set called P and you have a subset of points P' you want to be in the same cluster. The sum of square distances from any point x to the points of P' can be shown to equal:

|P'|(||x-Average(P')||^2+Var(P')).

Now since k-means tries to find the k points that would minimize the sum of square distances to all the points (including P') then replacing P' with n points all equals to Average(P') (or one point with a weight of |P'|) will enforce all those points to be in the same cluster and decrease the constrained loss function by exactly |P'|Var(P') (which is a constant of P' that does not depends on the k points and therefore does not affect the solution to the constrained k-means).

That means you can simply replace any point in P' with Average(P') and then solve regular k-means and this will be equivelent to the constrained k-means. You can do this with any of the sets of points you want to be in the same cluster.

Edit: I just saw in one of your comment you said this in regard to replacing the points with the mean "Perhaps this is a flaw in the image I used, but I don't necessarily know that the red and blue points are near each other. If they were dispersed across the space this could have weird implications I think. I like the idea though."

So unlike your comment suggests, no, replacing the points with the mean will not have weired implicitions regardless of how far they are from each other.

user_82711800
Related