KModes is an extension of KMeans that supports categorical data. KModes models are fit similarly to KMeans models. The core algorithm is an expectation-maximization algorithm that finds a locally optimal solution.
The main steps to fitting the model are:
Select a set of K initial cluster centers. You can generate this set with the RandomSample function, which samples rows from an input table using the kmeans++ and kmeans|| algorithms. These initialization algorithms generate initial cluster centers that are more likely to lead to better local optima.
- E step
A mapper assigns each point in the input table to one of the K clusters, and stores the sums of the numerical attributes and counts of the categorical attributes.
- M step
A reducer aggregates the the statistics generated for each worker in the E step and generates new cluster centers. For numerical attributes, the new center is the mean of the value of the attribute for the points assigned to the cluster. For categorical attributes, the new center is the mode of the attribute value for the points assigned to the cluster.
The algorithm runs for either a set number of iterations or until the change in movement of the cluster centers drops below a user-specified threshold.
When assigning points to a cluster, a hybrid distance function that combines a numeric distance and a categorical distance is required. The default distance between two data points in a KModes model is the squared Euclidean distance:
where N denotes the indices of numerical attributes, C denotes the indices of categorical attributes, and wj denotes the weight to be assigned to a category.
The Manhattan distance can also be used: