I need help to find all possible clusterizations via the k-means method in Python. Let's assume for simplicity that I have the following table:

height | weight | country of origin (X/Y/Z) | flag (1/0)

So a n_people x 4 size table.

I inserted the data artificially to specifically give the possibility to choose between two different clusterizations.

Now using k-means method "I find" that all people taller than 180 cm are from country X.

This is the piece of code to find the first clustering (all people taller than 180 cm are from country X):

df = pd.read_csv('survey.csv')
x = df.iloc[:, :].values
kmeans2 = KMeans(n_clusters=2)
y_kmeans2 = kmeans2.fit_predict(x)

But I also know that all people shorter than 170 cm have the flag variable equal to 0.

Is there a way to find this clustering by "ignoring" the previous one? Does redefining x by excluding the third column (country of origin) make sense? If the k-means method were not the best one, what could be an alternative?

Thanks to anyone who will answer.

  • 2
    $\begingroup$ Can you please explain what your aim is? Do you use all four features for clustering, or only height and weight? As you apparently already have the cluster label (presumably either "country" or "flag"), it would be more natural to use a linear discriminant analysis (LDA) instead of ignoring the class labels. Note that weight and height are presumably highly correlated, but an LDA shoud figure this out on itself. $\endgroup$
    – cdalitz
    Jan 12, 2021 at 14:50
  • $\begingroup$ I use all four features for clustering. Beyond the example I have proposed, which may not be the best to explain my purpose, my question is: how do I, in general, identify all the possible clusterizations (that is, in how many "legitimate" ways I can group data)? Applying the k-means method, I only get one. $\endgroup$
    – LJG
    Jan 12, 2021 at 15:01
  • $\begingroup$ You cannot apply k-means to categorical data such as "country" $\endgroup$
    – ttnphns
    Jan 13, 2021 at 18:29
  • $\begingroup$ Yes, only to the quantitative parameters, in my case height and weight $\endgroup$
    – LJG
    Jan 14, 2021 at 9:41

1 Answer 1


From your clarification in the comments, you ask for the number of ways how a set of n elements can be partitioned into k clusters.

This number is given by the Stirling numbers of the second kind. Their definition and properties can be found in Abramowitz, Stegun: "Handbook of Mathematical Functions".

To actually list all partitions into k clusters, you can use one of the algorithms (most notably "Algorithm U" by Knuth) given in this thread:


  • $\begingroup$ It seems to me that your argument is purely theoretical. From a statistical point of view, even on a practical level (thus involving programming) how does one find all the valid ways to group data? $\endgroup$
    – LJG
    Jan 12, 2021 at 15:43
  • $\begingroup$ @LJG I have added a link to a thread on stackoverflow that discusses your problem. $\endgroup$
    – cdalitz
    Jan 13, 2021 at 17:39
  • $\begingroup$ I'm not sure how I can determine which cluster each row of the table will be assigned to? Should I try every single possibility with a loop and then calculate the error and see in which cases I find the smallest errors? $\endgroup$
    – LJG
    Jan 14, 2021 at 10:11
  • $\begingroup$ So you need all possible partitionings for optimizing some criterion? This is not a good idea, because this approach has exponential runtime (see the asymptotic formula for the Sterling numbers in Abramoitz, Stegun) and is thus not tractable. K-means or hierarchical clustering algorithms have polynomial runtime and are thus efficient ("tractable"), but might yield suboptimal solutions. If your number of items is very small, however, this might indeed be possible and you can compare the result with results returned by efficient algorithms. $\endgroup$
    – cdalitz
    Jan 14, 2021 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.