# How to deal with variability in clustering. Multiple/Meta clustering?

I'm not sure what information is relevant here, so here is some background:

• I'm using Python 3 / sklearn, but I could probably use R if needed.
• I have a small sparse data-set (~1500 samples, ~1600 features).
• I've "normalized" the data using python's MaxAbsScaler and used PCA to reduce the number of features to about 800.

I have tried k-means on the data-set, but I end up with two problems:

• First, although the clusters mostly seem to "make sense", many clusters are "contaminated" with samples that clearly don't belong. These "contaminants" move around to different clusters depending on the starting seed.
• Second, the samples that clearly "do belong" together are frequently shuffled into different clusters depending on my starting seed.

I feel as though I need a way to perform multiple clusterings and then cluster based on the samples that are most frequently clustered together. Meta-clustering? Is this possible? If so, I'm not sure what tools are available.

Also, does the clustering variability indicate some underlying problem w/ the data? If so, any thoughts on how to examine the problem?

If what I wrote above isn't clear, here is a simple illustration of the problem:

Imagine I have three categories:

• cars
• books
• ice cream flavors

If I perform k-means with "seed x", I get these clusters

• cluster 1: The Bible, Catcher in The Rye, Toyota, Iliad, The Hobbit
• cluster 2: Ferrari, Great Expectations, BMW, Honda, Mercedes
• cluster 3: Vanilla, Chrysler, Chocolate, Rocky Road, Mint, Butterschotch

If I use a different seed, I get these clusters

• cluster 1: BMW, Mercedes, Honda, Vanilla, Chrysler
• cluster 3: Catcher in The Rye, Toyota, The Hobbit, Great Expectations, The Bible

You can see that the "contaminants" are moving around, but the other samples are moving around, too.

Edit below

@Anony-Mousse You asked if the data are "noisy". I'm not sure how to measure noisiness, so I can't answer that question.

You also wanted to see PC1 vs PC2 (see pic below). You don't see clustering, primarily because even the 1st principal component captures only a small percentage of the variance (see 2nd figure below).

• I have 1380 samples and 1637 features.
• PCA with about 780 principal components captures about 99% of the variance

Any suggestions are much appreciated.

• It looks as though your solution space has many local maxima. You need more data here I suspect as with 800 variables I would have liked a number of observations in the tens of thousands. – mdewey Mar 12 '17 at 9:51
• @mdewey Thank you for the comment. Unfortunately, I am stuck with my limited data-set. – user36476 Mar 12 '17 at 23:19
• What kind of features do you use? Is your data noisy? (Because k-means does not work well on noisy data). Can you plot the first two principal components? If you can't see very clear clusters in that plot, k-means will not work. – Anony-Mousse Mar 17 '17 at 7:03
• @Anony-Mousse See the additional information that I provided. I assume you will argue (from the figures) that K-means is not the way to go. If you have any additional suggestions, please let me know. Thank you. – user36476 Mar 19 '17 at 0:13