K-modes implementation in pyspark

Question

I'm looking for an implementation of k-modes in pyspark. I found this and this as implementations.

First, I tried implementing k-modes using the first link and faced issues. So I went ahead and tried the second implementation on github. This one worked (as in ran without errors), but I'm still unable to use it in the proper way because of no guide/usage techniques. According to the github page:

n_modes=36
partitions=10
max_iter=10
fraction = 50000 * partitions / (data.count() * 1.0)
data = data.rdd.sample(False,fraction).toDF()

method=IncrementalPartitionedKMetaModes(n_partitions = partitions, n_clusters = n_modes,max_dist_iter = max_iter,local_kmodes_iter = max_iter,
 similarity = "frequency", metamodessimilarity = "hamming")

cluster_metamodes = method.calculate_metamodes(data)

I'm not able to understand how to use this cluster_metamodes, or what it even means.

In short, k-modes will be performed for each partition in order to identify a set of modes (of clusters) for each partition. Next, k-modes will be repeated to identify modes of a set of all modes from all partitions. These modes of modes are called metamodes here.

Can someone explain the concept and tell how to use this method of clustering on a pyspark dataframe of categorical values?

Answer 1

Modes are just the analog of centroids in k-means. A distributed implementation assigns points to clusters in parallel on subsets of the data, then computes new centroids in parallel, and finally collects those results to perform a (weighted) average of those centroids to get the real centroids. Similarly here, after cluster assignment, modes are computed on subsets of the data in parallel, but then they need to be collected and combined into the real new modes. For whatever reason they're calling the 'real' modes 'metamodes'.

Answer 2

I'm happy to hear that it runs without errors. Since the time when the question was asked I have fixed some more issues there and also wrote a paper about it, which can be used as a documentation for clarity (the paper is referenced on github).

the cluster_metamodes is an array containing resulting "modes of modes" or metamodes. In other words, this is an list with centers of the clusters. How to use it further depends solely on you. For example, you can calculate a distance from each record to all metamodes, using any of the distance functions provided:

• hamming_dissim(record, cluster_metamodes)
• frequency_based_dissim(record, cluster_metamodes)

More detailed example is now provided on the github.

Besides this, there are now two more functions, namely get_modes and get_mode_indexes. The first one will return you the list of modes (not metamodes!), i.e. all centers of all clusters in all data subsets (that were clustered individually). The second one will return you a list with corresponding mode ID (which is globally unique) for each original record.

If you would have 100 records in your data and run pyspark-kmetamodes with 5 partitions, partition size 20 and n_modes = 2, it will result in:

• cluster_metamodes containing 2 elements (2 metamodes calculated from 10 modes)
• get_modes will return you a list with 10 elements (5 partitions x 2 modes per partition = 10 modes)
• get_mode_indexes will return you 100 elements, where each element will contain the corresponding mode ID (taking into account that there are 10 modes), get_mode_indexes()[9] should contain the mode ID for the 10th record from the analysed data set.