1

Are there any types of clustering algorithms that focus on forming specific sized clusters? This can be thought of us as a grouping algorithm more than a clustering algorithm.

Basically, given n data points, and fixed groups of a certain size k, find the optimal distribution of points to sets based upon certain classifiers, that will hopefully minimize the distance of classifiers for each point in a given group.

This problem seems to be pretty similar to a clustering problem, but the main difference is that we are concerned with a specific cluster size, but not concerned about the number of clusters.

jab
  • 5,673
  • 9
  • 53
  • 84
  • What I can think is to implement a "starvation" mechanism. If too much data point are assigned to a cluster, exceeding a critical value, then the cluster shall become "bloated" and split into two(K-means) or have shrinked size(reduce standard deviation in gaussian mixture). On the contrary, if a centroid become "starving", it shall be removed or have expanded size. The drawback is this cannot reach precisely the cluster size intended, and it also has a potential "global starvation" problem. – Kh40tiK May 11 '14 at 02:51
  • possible duplicate of [Group n points in k clusters of equal size](http://stackoverflow.com/questions/8796682/group-n-points-in-k-clusters-of-equal-size) – Has QUIT--Anony-Mousse May 11 '14 at 14:47

2 Answers2

2

There is a tutorial on how to implement such an algorithm in ELKI:

http://elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans

Also have a look at constraint clustering algorithms; although usually these algorithms only support "Must link" and "cannot link" constraints, not size constraints.

You should be able to do a similar modification where you first specify the group sizes, then assign points randomly, and swap cluster members as long as your objective function improves; similar to k-means / k-medoids. As you may get stuck in local minima, restart a number of times and only keep the best.

See also earlier questions, e.g. K-means algorithm variation with equal cluster size and Group n points in k clusters of equal size

Community
  • 1
  • 1
Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
0

The problem that you are posing is a combinatorial optimization problem. It is very important to know if you need an exact solution, or that can you settle for an approximate one?

If you need exact solutions, there is a body of work that focuses on clustering with different types of constraints. The constraint that you mentioned can be encoded in this framework. However, you should now that this approach scales up to a datasets with a certain size.

Behrouz Babaki
  • 81
  • 2