sklearn KMedoids returns empty clusters

user_10933726 0
Viewed 3517

I am using KMedoids from sklearn_extra.cluster. I use it with a precalculated distance matrix (metric='precomputed') and it used to work. However, we found a bug in the way the distance matrix was calculated and therefore had to implement it ourselves. Since then the KMedoids algorithm doesn't work anymore. This is the stacktrace:

C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 1 is empty! self.labels_[self.medoid_indices_[1]] may not be labeled with its corresponding cluster (1).
  warnings.warn(enter code here
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 2 is empty! self.labels_[self.medoid_indices_[2]] may not be labeled with its corresponding cluster (2).
  warnings.warn(
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 3 is empty! self.labels_[self.medoid_indices_[3]] may not be labeled with its corresponding cluster (3).
  warnings.warn(
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 4 is empty! self.labels_[self.medoid_indices_[4]] may not be labeled with its corresponding cluster (4).
  warnings.warn(
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 5 is empty! self.labels_[self.medoid_indices_[5]] may not be labeled with its corresponding cluster (5).
  warnings.warn(
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 6 is empty! self.labels_[self.medoid_indices_[6]] may not be labeled with its corresponding cluster (6).
  warnings.warn(
C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\sklearn_extra\cluster\_k_medoids.py:231: UserWarning: Cluster 7 is empty! self.labels_[self.medoid_indices_[7]] may not be labeled with its corresponding cluster (7).
  warnings.warn(

I have checked the distance matrix, it is a two-dimensional nparray with dimensions of n_data x n_data where the values on the diagonal are zero, so that should not be the problem. All the values are between 0 and 1. We used to use this algorithm for the Gower distance, but that did not work when we only had categorical data for some reason. All our values are boolean values. The Gower distance returned the following:

File "C:\Users\...\AppData\Local\Programs\Python\Python38-32\lib\site-packages\gower\gower_dist.py", line 62, in gower_matrix
    Z_num = np.divide(Z_num ,num_max,out=np.zeros_like(Z_num), where=num_max!=0)
TypeError: ufunc 'true_divide' output (typecode 'd') could not be coerced to provided output parameter (typecode '?') according to the casting rule ''same_kind''

I also tried pyclustering KMedoids and that did work. However, you need to define the initial medoids yourself using pyclustering and the method I found for that did not work with categorical data. (see below)

initial_medoids = kmeans_plusplus_initializer(data, n_clus, kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize(return_index=True)

Stacktrace:

File "path_to_file", line 19, in <module>
    initial_medoids = kmeans_plusplus_initializer(data, n_clus, kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize(return_index=True)
  File "path\Python\Python38-32\lib\site-packages\pyclustering\cluster\center_initializer.py", line 357, in initialize
    index_point = self.__get_next_center(centers)
  File "path\Python\Python38-32\lib\site-packages\pyclustering\cluster\center_initializer.py", line 256, in __get_next_center
    distances = self.__calculate_shortest_distances(self.__data, centers)
  File "path\Python\Python38-32\lib\site-packages\pyclustering\cluster\center_initializer.py", line 236, in __calculate_shortest_distances      
    dataset_differences[index_center] = numpy.sum(numpy.square(data - center), axis=1).T
TypeError: numpy boolean subtract, the `-` operator, is not supported, use the bitwise_xor, the `^` operator, or the logical_xor function instead.

My problem can be fixed in three ways, so I hope that someone can help me:

  1. Someone knows why KMedoids by sk-learn doesn't work and can help me with that, so I can use it.
  2. Someone knows what I'm doing wrong with the Gower function from PyPI, so I can use either pyclustering or sklearn.
  3. Someone knows how I can easily find the initial medoids to use for pyclustering, so I can use pyclustering.

I have posted a simple version of the code below.

import pandas as pd
import gower_distance as dist
from sklearn_extra.cluster import KMedoids

data = pd.read_csv(path_to_data)
dist = calcDist(data) # Returns NxN array where N is the amount of data points
# I'm using 8 clusters, which is the default, so I haven't defined it
kmedoids = KMedoids(metric='precomputed').fit(dist)
labels = kmedoids.predict(dist)
scikit-learn cluster-analysis python
2 Answers

I also received that warning (however using the euclidean-distance). using another initialization of the cluster cores fixed it for me:

kmedoids = KMedoids(metric='precomputed', init='k-medoids++').fit(dist)
user_133973520

To get cluster labels from the trained model (i.e. train label),

data = pd.read_csv(path_to_data)
dist = calcDist(data)
kmedoids = KMedoids(metric='precomputed').fit(dist)
labels = kmedoids.labels_

To use kmedoids.predict with any predict data using the trained k-medoids model, you need to compute N x K distance matrix from N predict data to K medoids, properly indexed.

medoids = predictData[kmedoids.medoid_indices_, :]
distToMedoids = calcDistToMedoids(predictData, medoids) # with the same metric used in training
predict_labels = kmedoids.predict(distToMedoids)
predict_labels = np.argmin(distToMedoids, axis=1) # what .predict() does

You can check more from the source code.

user_51918080
Related