k-means clustering data with large number of meaningless values

Question

I am looking to perform k-means on my dataset which contains a large number of 0 values.

The last value you see is different to the others, that is simply the sum of transactions, not related to the categorical frequency count.

Example:

[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 189200.579626]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.06556796]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 5.46e-06]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 5.46e-06]

Each feature is a frequency count of how many times the associated id is seen within a category.

When I run k-means, I see that most of the data is clustered in one cluster.

+------------+--------+----------------------+
| cluster_id |  size  | sum_squared_distance |
+------------+--------+----------------------+
|     0      | 659187 |    0.999997057952    |
|     1      |   3    |    1.33333326876     |
|     2      |   1    |         0.0          |
|     3      |   3    |    0.666666716337    |
|     4      |   1    |         0.0          |
|     5      |   1    |         0.0          |
|     6      |   1    |         0.0          |
|     7      |   1    |         0.0          |
|     8      |   1    |         0.0          |
|     9      |   11   |    2.72727286816     |
+------------+--------+----------------------+

I am assuming that this is because the majority of the dataset has not been seen in a feature category and therefore has a value of 0.

What is the best way to overcome this, drop rows where a 0 is seen across each category? Are these rows meaningless to clustering?

Answer 1

One thing you could do is apply some dimensional reduction algorithm (such as PCA) so you can get the columns with high variance, then run k-means on that data set.

However, I suggest against using k-means in sparse matrices like yours. Anony-Mousse's answer here explains it well.

Answer 2

welcome to DataScienceSO!

So I guess from a logical standpoint a very sparse dataset (heaps of 0's or missing values) will likely create similar clusterings just simply due to the lack of information for a large amount of the observations. So you're right in your assumption.

Technically these rows are not useless as they represent a valid clustering, but in a business sense they essentially are as they communicate no information about potential groupings of observations going forward.

NB: K-means is influenced by differences in scale which may be causing some troubles. Whatever statistical package will definitely have a scaling function that forces the variable to have mean zero and sd of one.

This is a problem because k-means doesn't understand differences in units. For instance if variable A is measured in meters and variable B in km, A = 1000 would be seen as greater than B = 1 even though they are equal.

Also I'd take a second look at the number of clusters you have. It may be too many for the amount of real information you have. See this post for more information

Answer 3

I agree with Calpis: first reduce number of dimensions. But instead of PCA (which is designed for multivariate normal data) use matrix factorization. SVD or NMF.