2
$\begingroup$

I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique.

In this brute force algorithm we test every possible clustering example and see what natural clusters occur.

The problem comes from the assignment of every possible clustering. If give each value a cluster sequentially the complexity is much higher than necessary and results in many overlaps.

Sequential Example: 5 objects into 3 clusters 11111, 11112, 11113, 11114, 11115, 11121, etc. . .

But 11112 and 11113 are effectively the same. The complexity above is O(k^n) where k is the number of clusters and n is the number of objects. This makes for a terrible time afterwards because duplicates will not be fun to work with and parse. Looking at natural clusters becomes easier with more points as well, and in a simple example, assigning 20 to 5 results in 3,200,000 mostly duplicate clusterings.

If we look at this using combinatorics then we can assign n objects to k groups in (n + k - 1) C (k - 1) ways. This results in 20 objects to 5 clusters having only 10626 different combinations.

Is there any way already made to exhaustively produce these arrangements in this way to eliminate the duplicates?

$\endgroup$
2
$\begingroup$

The objects you are interested in enumerating are counted by Stirling numbers of the second kind. In particular, $\genfrac{\{}{\}}{0pt}{}{n}{k}$ is the number of ways to partition a set of size $n$ into $k$ non-empty parts. The Stirling numbers satisfy the recurrence $$ \genfrac{\{}{\}}{0pt}{}{n+1}{k} = k\genfrac{\{}{\}}{0pt}{}{n}{k} + \genfrac{\{}{\}}{0pt}{}{n}{k-1}. $$ Indeed, either element $n+1$ is in a partition of its own, or it joins one of the other $k$ parts. The initial conditions are $\genfrac{\{}{\}}{0pt}{}{0}{0} = 1$ and $\genfrac{\{}{\}}{0pt}{}{0}{n} = \genfrac{\{}{\}}{0pt}{}{n}{0} = 0$ for $n > 0$. In other words, if $n = k = 0$ then there is a unique solution (the trivial solution), and if $n = 0$ or $k = 0$ otherwise then there are no solutions.

You can use this recurrence to recursively generate all partitions you are after.

$\endgroup$
2
  • $\begingroup$ Excuse me if I'm incorrect, but it doesn't seem to be what I'm looking for based upon the size of $S_{20}^{(5)}$ ~ 749 Billion (Wolfram's Calculation) which is much higher than just sequentially numbering the data points. Was my original calculation of ${{n + k - 1}\choose{k - 1}}$ incorrect for this or is my understanding of Stirling numbers incorrect? $\endgroup$ Apr 4 '16 at 21:36
  • $\begingroup$ Actually, I know why my calculation was incorrect, and I'm going to look into Stirling numbers more. Thanks for your time! $\endgroup$ Apr 4 '16 at 21:54

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.