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 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 at 15:01
  • $\begingroup$ You cannot apply k-means to categorical data such as "country" $\endgroup$ – ttnphns Jan 13 at 18:29
  • $\begingroup$ Yes, only to the quantitative parameters, in my case height and weight $\endgroup$ – LJG Jan 14 at 9:41

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 at 15:43
  • $\begingroup$ @LJG I have added a link to a thread on stackoverflow that discusses your problem. $\endgroup$ – cdalitz Jan 13 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 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 at 10:24

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.