1
$\begingroup$

I have been exploring clustering algorithms (K-Means, K-Medoids, Ward Agglomerative, Gaussian Mixture Modeling, BIRCH, DBSCAN, OPTICS, Common Nearest-Neighbour Clustering) with multidimensional data. I believe that the clusters in my data occur across different subsets of the features rather than occurring across all features, and I believe that this impacts the performance of the clustering algorithms.

To illustrate, below is Python code for a simulated dataset:

## Simulate a dataset.

import numpy as np, matplotlib.pyplot as plt
from sklearn.cluster import KMeans

np.random.seed(20220509)

# Simulate three clusters along 1 dimension.

X_1_1 = np.random.normal(size = (1000, 1)) * 0.10 + 1
X_1_2 = np.random.normal(size = (2000, 1)) * 0.10 + 2
X_1_3 = np.random.normal(size = (3000, 1)) * 0.10 + 3

# Simulate three clusters along 2 dimensions.

X_2_1 = np.random.normal(size = (1000, 2)) * 0.10 + [4, 5]
X_2_2 = np.random.normal(size = (2000, 2)) * 0.10 + [6, 7]
X_2_3 = np.random.normal(size = (3000, 2)) * 0.10 + [8, 9]

# Combine into a single dataset.

X_1 = np.concatenate((X_1_1, X_1_2, X_1_3), axis = 0)
X_2 = np.concatenate((X_2_1, X_2_2, X_2_3), axis = 0)

X = np.concatenate((X_1, X_2), axis = 1)

print(X.shape)

Visualize the clusters along dimension 1:

plt.scatter(X[:, 0], X[:, 0])

enter image description here

Visualize the clusters along dimensions 2 and 3:

plt.scatter(X[:, 1], X[:, 2])

enter image description here

K-Means with all 3 Dimensions

K = KMeans(n_clusters = 6, algorithm = 'full', random_state = 20220509).fit_predict(X) + 1

Visualize the K-Means clusters along dimension 1:

plt.scatter(X[:, 0], X[:, 0], c = K)

enter image description here

Visualize the K-Means clusters along dimensions 2 and 3:

plt.scatter(X[:, 1], X[:, 2], c = K)

enter image description here

The K-Means clusters developed with all 3 dimensions are incorrect.

K-Means with Dimension 1 Alone

K_1 = KMeans(n_clusters = 3, algorithm = 'full', random_state = 20220509).fit_predict(X[:, 0].reshape(-1, 1)) + 1

Visualize the K-Means clusters along dimension 1:

plt.scatter(X[:, 0], X[:, 0], c = K_1)

enter image description here

The K-Means clusters developed with dimension 1 alone are correct.

K-Means with Dimensions 2 and 3 Alone

K_2 = KMeans(n_clusters = 3, algorithm = 'full', random_state = 20220509).fit_predict(X[:, [1, 2]]) + 1

Visualize the K-Means clusters along dimensions 2 and 3:

plt.scatter(X[:, 1], X[:, 2], c = K_2)

enter image description here

The K-Means clusters developed with dimensions 2 and 3 alone are correct.

Clustering Between Dimensions

Although I did not intend for dimension 1 to form clusters with dimensions 2 or 3, it appears that clusters between dimensions emerge. Perhaps this might be part of why the K-Means algorithm struggles when developed with all 3 dimensions.

Visualize the clusters between dimension 1 and 2:

plt.scatter(X[:, 0], X[:, 1])

enter image description here

Visualize the clusters between dimension 1 and 3:

plt.scatter(X[:, 0], X[:, 2])

enter image description here

Questions

  1. Am I making a conceptual error somewhere? If so, please describe or point me to a resource. If not:

  2. If I did not intend for dimension 1 to form clusters with dimensions 2 or 3, why do clusters between those dimensions emerge? Will this occur with higher-dimensional clusters? Is this why the K-Means algorithm struggles when developed with all 3 dimensions?

  3. How can I select the different subsets of the features where different clusters occur (3 clusters along dimension 1 alone, and 3 clusters along dimensions 2 and 3 alone, in the example above)? My hope is that developing clusters separately with the right subsets of features will be more robust than developing clusters with all features.

Thank you very much!

UPDATE:

Thank you for the very helpful answers for feature selection and cluster metrics. I have asked a more specific question: Why Do a Set of 3 Clusters Across 1 Dimension and a Set of 3 Clusters Across 2 Dimensions Form 9 Apparent Clusters in 3 Dimensions?

$\endgroup$

3 Answers 3

3
+50
$\begingroup$

The field of feature selection for clustering studies this topic.

A specific algorithm for feature selection for clustering is Spectral Feature Selection (SPEC) which estimates the feature relevance by estimating feature consistency within the spectrum matrix of the similarity matrix. The features consistent with the graph structure will have similar values to instances that are near to each other in the graph. These features should be more relevant since they behave similarly in each similar group of samples, aka clusters.

"Feature Selection for Clustering: A Review" by Alelyani et al. goes into greater detail. There is an also an Feature Selection for Clustering Python package.

$\endgroup$
2
  • $\begingroup$ Thanks! I am having trouble installing the python package you recommended. I have cloned the repository, and the installation instructions say to "Copy content of the folder fsfc to the source root of your project". I can find the fsfc folder in 'Home' but I don't know where the source root of my project is. I am using Anaconda Navigator on Ubuntu with an environment I called 'Cluster'. Do you know where I can find the source route of my project? $\endgroup$ May 15, 2022 at 21:10
  • $\begingroup$ I was able to use 'import sys' and 'print(sys.path[1])' to find the location of the 'Cluster' environment. Then, I pasted the 'fsfc' folder (from within the 'fsfc' clone) inside the location of the 'Cluster' environment. Note: github.com/danilkolikov/fsfc/issues/3 $\endgroup$ May 16, 2022 at 16:34
1
$\begingroup$
  1. Firstly, embrace the fact that clustering is unsupervised. Supervise learning algorithms can do feature selection because they know what they look for: features that are relevant to target. This is not the case for clustering - it just tries to make sense of everything you feed in.

    Say I have a dataset of 100 people with 3 attributes: age, weight, and wealth. In my mind, I may expect clusters of 30 "elder fat gentleman" and 70 "young healthy boy" (using only age and weight); but the clustering algorithm returns 1 "old filthy fat ass" versus 99 "other lowborn" (using all 3 features). Is the algorithm wrong? No! We are just looking at same thing from different aspects.

    Key message is there is no absolute right or wrong in unsupervised learning.

  2. If I did not intend for dimension 1 to form clusters with dimensions 2 or 3, why do clusters between those dimensions emerge?

    Things we do not intend for do not imply it cannot exist. Try drawing a 3D plot with all 3 dimensions together plus cluster colors; the clustering algorithm may be seeing structure in 3D that is invisible in 2D.

  3. There are some metrics that evaluate the "goodness" of clusters, e.g. Silhouette Score, Rank Index etc. So maybe we can formulate it as an optimization problem - try to optimize a metric w.r.t. feature selection. I am not very familiar with this, but sounds like framing into a supervised problem.

$\endgroup$
1
$\begingroup$

The essential thing you are doing wrong is the selected number of clusters.

You have chosen 6 when you defined in your dataset 3.

So by simply changing to this:

from this:

K = KMeans(n_clusters = 6, algorithm = 'full', random_state = 20220509).fit_predict(X) + 1

To:

K = KMeans(n_clusters = 3, algorithm = 'full', random_state = 20220509).fit_predict(X) + 1

You get:

plt.scatter(X[:, 1], X[:, 2], c = K)

enter image description here

and this:

plt.scatter(X[:, 0], X[:, 0], c = K)

enter image description here

How can I select the different subsets of the features where different clusters occur (3 clusters along dimension 1 alone, and 3 clusters along dimensions 2 and 3 alone, in the example above)? My hope is that developing clusters separately with the right subsets of features will be more robust than developing clusters with all features.

You can try kind of random feature removal by randomly shuffling a feature and fitting your clusters and then calculating a separateness measure like silhouette and see which one gives you the highest decrease (the higher, the more important a feature is to form the clusters) Repeat this step n times for every feature.

This would be equivalent to Permutation importance (check)

$\endgroup$
1
  • $\begingroup$ Thanks! "You have chosen 6 when you defined in your dataset 3" This is part of what I am struggling with. I created 3 clusters across a single dimension. Then, I created 3 more clusters along 2 other dimensions. I intended for there to be 6 clusters in total (3 clusters along dimension 1, and 3 clusters along dimensions 2 and 3) but I ended up with 3 apparent clusters in 3 dimensional space. $\endgroup$ May 17, 2022 at 16:44

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.