# k modes: optimal k

I have categorical data and I'm trying to implement k-modes using the GitHub package available here. I am trying to create clusters in my (large) dataset of say, 5-7 records, each of most similar records.

However, as of now I have no means to select the optimal 'k' which would result in maximum silhouette score, ideally. This would be ideal as k-modes works on dissimilarity/similarity measure as a distance. So I would assume that silhouette distance would then measure how close/far the clusters are based on the distance metric defined by this dissimilarity and thus, establish the silhouette score. I'm not able to find an implementation of this.

Can I perhaps use the elbow method here? But then, I'm not able to understand how to programmatically determine this, without looking at a graph as I have to do this process repeatedly a large number of times. Currently, an idea is - find k where cost drops substantially. See if the next few values introduce a very less drop in cost or not. If yes, choose this as k, if no.. then what? I'm a little confused at this point.

I was looking online and also found this, which I'm not able to interpret in terms of k modes. I'm looking for any code/suggestions to start me off on the right path.

Instead of trying to find a place to download some source code, why don't you just implement, e.g., Silhouette yourself?

Plenty of the code you find online in blogs and repos is broken.

I've seen so many github repositories with bad code, and people like you wondering why it doesn't work. Relying on anonymous others to not have made mistakes is a bad idea. At some point you are better off writing the code yourself!

Of course it is okay to rely on large open-source projects like sklearn, R, ELKI, Weka. These have code-reviews, discuss pull requests, and dozens of people look at the code, use it, try to find and fix bugs (but even there are errors in the code).

• The idea to ask this question was to have someone verify my logic before I start implementing the code, which is why I posted some of the thoughts I had on the ways I could start off. Or say, if someone was already working on this problem, I could have discussed this with them. Please see -- 'So I would assume that silhouette distance (in k-modes) would then measure how close/far the clusters are based on the distance metric defined by this dissimilarity and thus, establish the silhouette score.' – user2816215 Mar 18 '19 at 13:51
• Yes, Silhouette "just" needs pairwise distances. That may be too expensive to compute, but on small data this will work. It took me like 30 seconds to verify that all of R, sklearn, ELKI will allow you to specify an arbitrary distance matrix... Why did you not check yourself? – Has QUIT--Anony-Mousse Mar 18 '19 at 17:21
• I didn't search for it yet, tbh. I was just trying to have someone confirm if what I was saying was right before getting down to the implementation part. I didn't search for the specifics. The thing is that my dataset is large. Pairwise distances will be expensive. – user2816215 Mar 18 '19 at 18:26
• Silhouette ist defined on paiwise distances. So then don't use Silhouette. Read the definitions and documentation, please! – Has QUIT--Anony-Mousse Mar 18 '19 at 18:51
• Say, I was using pairwise distances. I was looking into the calculation as defined here (scikit-learn.org/stable/modules/generated/…). How would we define 'nearest' here? What kind of distance metric would be a good choice? Equality in terms of the vector? Or something like hamming/jaccard distance for each of the values of the vector? By that, I mean - say a column has ['apple', 'cloudy] and ['mango', 'cloudy'], would a dissimilarity measure say the sum of dissimilar items work? Say, 1 in this case? Or jaccard giving sum of similarity of items? – user2816215 Mar 18 '19 at 19:03
def matching_disimilarity(a, b):
return np.sum(a != b, axis=1)

silhouette_dict = dict()
cluster_labels = [...]
distinct_cluster_label_predictions = unique cluster_labels

for i in m_array:
other_records_in_cluster = m_array_(with cluster_prediction == cluster_prediction of i) - i
other_records_outside_cluster = m_array_(with cluster_prediction != cluster_prediction of i)
other_records_outside_cluster_labels = cluster labels of record in other_records_outside_cluster

sum_a = 0
sum_b = 0
sum_cluster_dist = dict()
avg_cluster_dist = dict()

for c in distinct_cluster_label_predictions:
sum_cluster_dist[c] = 0

# finding a(i) - for each observation i, calculate the average dissimilarity ai between i and all other
# points of the cluster to which i belongs.
for j in other_records_in_cluster:
sum_a += matching_disimilarity(i, j)
a = sum_a/len(other_records_in_cluster)

dict_b = dict()

# find average of inter-cluster distance with nearest neighbour
for j in other_records_outside_cluster:
dist_i_to_j = matching_disimilarity(i,j)
dict_b[j] = dist_i_to_j
sum_till_now = sum_cluster_dist[other_records_outside_cluster_labels[j]]
sum_cluster_dist[other_records_outside_cluster_labels[j]] = sum_till_now+dist_i_to_j

for c in distinct_cluster_label_predictions:
avg_cluster_dist[c] = sum_cluster_dist[c]/(length of elements_belonging_to_c)

# nearest_neighbour is the with smallest average distance
# for more than one nearest neighbour? Break randomly?
nearest_cluster_label = key of minimum avg_cluster_dist value

neighbouring_cluster_records = records with cluster_prediction == nearest_cluster_label

for k in neighbouring_cluster_records:
sum_b += dict_b[k]
b = sum_b/len(neighbouring_cluster_records)

if (a<b):
sil = 1 - (a/b)
elif(a==b):
sil = 0
else:
sil = b/a - 1

silhouette_dict[i] = sil

average_silhouette_score = avg(all values in silhouette_dict)

• No, b is defined differently. – Has QUIT--Anony-Mousse Mar 18 '19 at 20:46
• Can you point out where I am wrong? Here (sthda.com/english/wiki/print.php?id=241#concept-and-algorithm) it says for calculating b - for all other clusters C, to which i does not belong, calculate the average dissimilarity d(i,C) of i to all observations of C. The smallest of these d(i,C) is defined as bi=min d(i,C). The value of bi can be seen as the dissimilarity between i and its “neighbour” cluster, i.e., the nearest one to which it does not belong. So, I took the average distance from i to all points in the neighbour cluster, which I found by the minimum of all avg distances – user2816215 Mar 19 '19 at 14:35
• Also, I made a few corrections to the code. – user2816215 Mar 19 '19 at 15:54
• The nearest other cluster is not the same as throwing all other clusters into one big set. You need the average distance to each cluster, ignoring the current point. Then find the nearest other to get b. – Has QUIT--Anony-Mousse Mar 19 '19 at 17:29
• avg_cluster_dist is a dictionary containing avg of distance to each of the distinct clusters c. It has been calculated for each distinct_cluster_label_predictions and then nearest_cluster_label is chosen as the key of minimum avg_cluster_dist value. Finally, this value is used. Is this what you meant? I don't understand what you mean by 'ignoring the current point'. – user2816215 Mar 19 '19 at 19:10

Typically you will choose the number of clusters associated with the highest silhouette value but this can be tricky because the difference in silhouette values between X and Y clusters can be very negligible. Have you tried generating silhouette plots? The silhouette plots will let you visualize the clustered data with respect to their assigned cluster proximity, on a -1 to 1 scale with the cluster numbers on the vertical axis

https://github.com/nicodv/kmodes/issues/46