K-Modes For Categorical Data

Why Use a Categorical Clustering Method?

A customer record might describe a preferred contact channel, payment frequency, and coverage tier. These fields can reveal useful groups, but they do not have a natural numeric scale. Coding “online” as 1 and “phone” as 2 does not mean that phone is one unit greater than online. Applying Euclidean distance to such codes would impose a numerical meaning that the categories do not have.

K-modes is a partitioning method designed for categorical observations. It measures dissimilarity by counting mismatches and represents each cluster with a componentwise mode: the most frequent category in each feature. Like k-means, it alternates between assigning observations to clusters and updating cluster representatives. Its distance and representative, however, are suited to categories rather than numeric measurements.

Definition: Suppose there are \(n\) observations, each with \(p\) categorical features, and a chosen number \(k\) of clusters. Write \(x_{ij}\) for the category of observation \(i\) on feature \(j\), \(c_i\) for its cluster assignment, and \(m_{gj}\) for the prototype category of cluster \(g\) on feature \(j\). The matching dissimilarity between observation \(i\) and prototype \(g\) is \(d_H(x_i,m_g)=\sum_{j=1}^{p} I(x_{ij}\ne m_{gj})\), where \(I(\cdot)\) equals 1 when its condition is true and 0 otherwise. The k-modes objective is \(W=\sum_{i=1}^{n}\sum_{j=1}^{p} I(x_{ij}\ne m_{c_i j})\), the total number of feature-level mismatches between observations and their assigned prototypes.

In the basic method, each feature contributes one unit for a mismatch, regardless of which two categories differ. Matching categories contribute zero. Thus, observations that differ on three of five features have dissimilarity 3. The number is a mismatch count, not a probability or a distance in dollars, years, or any other measurement unit.

The basic setup treats features as equally important, assumes categorical values are available for the features used, and uses hard assignments: each observation belongs to one cluster. The analyst supplies \(k\); k-modes does not establish that a particular number of clusters is correct. Missing values must be handled before calculating these mismatch counts. If a feature has many levels, or if some features should matter more than others, equal one-unit contributions also need careful consideration.

Assignment and Prototype Updates

K-modes alternates two steps. Given current prototypes, it assigns each observation to a prototype with the smallest matching dissimilarity. Given those assignments, it updates each prototype feature by feature, selecting a most frequent category within each cluster. These steps do not require taking averages of category labels.

Initialize \(k\) prototypes.
Choose starting category profiles. Different initial choices can lead to different final partitions.

Assign observations.
For each observation, calculate its mismatch count to each prototype and assign it to a closest one. A tie requires a stated tie-handling rule.

Update the prototypes.
Within each cluster, choose a most frequent category for each feature. If multiple categories share the highest frequency, choose one by a defined rule or retain a tied choice consistently.

Check the objective and stopping condition.
Recalculate \(W\). Stop when assignments and prototypes are unchanged, or apply an explicit cycle-handling rule if equal-objective changes recur.

Why the Mode Is the Right Prototype

The prototype update follows directly from the mismatch objective. Consider one feature in one cluster, and suppose its possible categories are \(a_1,\ldots,a_L\). If the prototype chooses category \(a_r\), the number of mismatches on that feature is the number of observations not equal to \(a_r\). If \(N_r\) observations have category \(a_r\), and the cluster has \(N\) observations in total, that number is \(N-N_r\). Therefore, minimizing mismatches is equivalent to maximizing \(N_r\).

\text{mismatches from choosing }a_r=N-N_r \qquad\Longrightarrow\qquad \arg\min_{a_r}(N-N_r)=\arg\max_{a_r}N_r

The objective is a sum across features, so each feature can be minimized separately. Choosing a mode for every feature therefore minimizes the total mismatch count for fixed assignments. A cluster prototype need not be an actual observed row: its most frequent categories on different features can come from different observations.

Key result: For fixed assignments, a componentwise mode minimizes the k-modes mismatch objective. For fixed prototypes, assigning each observation to a closest prototype minimizes that objective over the assignments. Each step therefore cannot increase \(W\), although ties can leave \(W\) unchanged.

Worked Examples

Worked Example: One Assignment and Update Round

A hypothetical insurer represents six policyholders using contact channel, billing frequency, and coverage tier. The records are shown below. Starting prototypes are \(M_1=(\text{web},\text{annual},\text{low})\) and \(M_2=(\text{agent},\text{monthly},\text{high})\). Assign the records, update the prototypes, and calculate the objective. The method is matching dissimilarity followed by componentwise modes; it avoids treating category labels as numeric measurements.

Record	Channel	Billing	Tier
A	web	annual	low
B	web	monthly	low
C	agent	annual	high
D	agent	monthly	high
E	web	annual	high
F	agent	monthly	low

Step 1: Calculate distances to the starting prototypes. Record A has distances 0 to \(M_1\) and 3 to \(M_2\), so it joins cluster 1. B has distances 1 and 2, so it joins cluster 1. C has distances 2 and 1, so it joins cluster 2. D has distances 3 and 0, so it joins cluster 2. E has distances 1 and 2, so it joins cluster 1. F has distances 2 and 1, so it joins cluster 2.

The starting assignments are therefore cluster 1: A, B, E; and cluster 2: C, D, F. Their nearest-prototype distances sum to \(0+1+1+0+1+1=4\), so the objective for these assignments and prototypes is \(W=4\).

Step 2: Update cluster 1. Its channel values are web, web, web, so the mode is web. Its billing values are annual, monthly, annual, so the mode is annual. Its tier values are low, low, high, so the mode is low. The updated prototype is \(M_1=(\text{web},\text{annual},\text{low})\). B and E each differ from it on one feature; A matches it on all three. Cluster 1 contributes \(0+1+1=2\) mismatches.

Step 3: Update cluster 2. Its channel values are all agent, so the mode is agent. Its billing values are annual, monthly, monthly, so the mode is monthly. Its tier values are high, high, low, so the mode is high. The updated prototype is \(M_2=(\text{agent},\text{monthly},\text{high})\). C and F each differ from it on one feature; D matches it on all three. Cluster 2 contributes \(1+0+1=2\) mismatches.

The updated total is \(W=2+2=4\). Reassignment to these prototypes leaves every record in its current cluster, with the same distances listed above. The result is unchanged by another assignment and update round, so it is stable under these steps. The check is that the post-update objective remains 4, not greater than its pre-update value of 4. A common mistake is to select a different “average” category for each feature; the mode, not a numerical average, minimizes mismatches.

Worked Example: Finding a Prototype When a Feature Has a Tie

A hypothetical service team summarizes five policyholder profiles using channel, billing, and coverage. Their values are (web, monthly, standard), (web, annual, standard), (phone, annual, standard), (phone, annual, premium), and (branch, monthly, premium). Treat them as one cluster. Find a modal prototype and its mismatch cost. This calculation illustrates that ties in a feature’s mode can produce multiple equally good prototypes.

Channel. Web occurs twice, phone occurs twice, and branch occurs once. Choosing web produces \(5-2=3\) mismatches; choosing phone also produces \(5-2=3\). Either is a mode.

Billing. Annual occurs three times and monthly occurs twice. Choosing annual produces \(5-3=2\) mismatches.

Coverage. Standard occurs three times and premium occurs twice. Choosing standard produces \(5-3=2\) mismatches.

Choose web to resolve the channel tie. The prototype is (web, annual, standard), and its total cost is \(3+2+2=7\). Checking record by record gives costs \(1,0,1,2,3\), which also sum to 7. Choosing phone instead yields the same total because its channel mismatch cost is also 3. The common mistake is to assume that a tied mode makes the objective undefined: it gives alternative prototypes with equal cost, so the tie rule should be explicit and reproducible.

Worked Example: Why Numeric Codes Can Mislead

A hypothetical portfolio has four records for one categorical feature, contact preference: A, A, B, and C. Compare the k-modes result with a one-cluster k-means calculation after two possible numeric codings. This example avoids the trap of assuming that digits assigned to categories have a meaningful scale.

K-modes. A occurs twice; B and C each occur once. The mode is A. The two records coded A match the prototype, while B and C each mismatch, so the objective is \(W=2\).

K-means with coding A=0, B=1, C=10. The numeric mean is \((0+0+1+10)/4=2.75\). The sum of squared deviations is \(2(0-2.75)^2+(1-2.75)^2+(10-2.75)^2\). The terms are \(15.125\), \(3.0625\), and \(52.5625\), giving \(70.75\).

K-means with coding A=0, B=1, C=2. The mean is \((0+0+1+2)/4=0.75\). The sum of squared deviations is \(2(0-0.75)^2+(1-0.75)^2+(2-0.75)^2=1.125+0.0625+1.5625=2.75\).

The categories and their frequencies did not change, but the k-means squared-error objective changed from 70.75 to 2.75 because the arbitrary code for C changed from 10 to 2. K-modes still gives two mismatches. The mean 2.75 in the first coding is not a contact preference. K-means is appropriate for numeric features with meaningful Euclidean differences; assigning integers to nominal categories does not create that meaning.

Comparison With K-Means and Practical Interpretation

Feature	K-modes	K-means
Input geometry	Categorical values; mismatch count	Numeric values; Euclidean distance
Cluster representative	Componentwise mode	Coordinatewise arithmetic mean
Within-cluster objective	Total feature mismatches	Total squared Euclidean deviations
Effect of arbitrary category codes	None, if category identity is preserved	Can change distances, means, and objective

Both methods seek a partition that performs well under their own objective, and an alternating procedure can settle at a solution that depends on initialization. Neither method proves that the resulting groups are genuine or useful. A low k-modes mismatch count means that observations match their assigned modal profiles on many features; it does not establish predictive value, causal differences, or business importance.

In practice, retain categorical variables as categories and ensure category levels are represented consistently. Do not convert nominal factor levels to integers and then pass them to a numeric clustering method as though the values were measurements. Inspect the feature-wise modes and mismatch counts as well as the assignments: a cluster profile is more informative than a cluster number alone. Features that duplicate one another can also effectively count the same distinction multiple times, so consider their meaning before fitting.

Stopping, Ties, and Common Exam Traps

For fixed assignments, the mode update cannot increase the objective. For fixed prototypes, nearest-prototype assignment cannot increase it either. Since \(W\) is a nonnegative integer, it cannot decrease indefinitely. But that fact alone does not prove that the assignments and prototypes must stop changing: the objective can remain constant while different equally good choices are made on ties.

A sound implementation checks whether the full state—both assignments and prototypes—has stopped changing. It should also handle ties reproducibly and protect against equal-objective cycles, for example by recording previously visited states and stopping if a state repeats, or by imposing a maximum-iteration safeguard. If a repeated state is encountered, report the best objective reached and the tie-handling rule. Do not claim that a deterministic tie rule alone rules out cycles unless that property has been established for the specific rule.

A stable result is a solution for which neither assignment nor prototype update changes the state under the specified rules. It is not necessarily the global minimum of \(W\). Multiple initializations can be used to explore alternative solutions, but the objective remains a measure of mismatch under the chosen features and equal-weight convention, not a general measure of cluster quality.

Using a mean of labels. Nominal categories have no arithmetic average. Use a modal category for each feature.
Forgetting feature-level counting. Each mismatched feature adds one, so two records can differ on several features and contribute several mismatches.
Ignoring tied modes or assignment distances. Ties can produce equal-cost alternatives; state how they are resolved.
Overstating convergence. A non-increasing integer objective eventually becomes constant, but equal-objective states may still change. Use a state-based stopping or cycle-handling rule.
Interpreting the result too broadly. K-modes describes similarity under the selected categorical features; it does not by itself demonstrate that the clusters are useful for a later decision.

Key takeaway: K-modes replaces k-means’ Euclidean distances and numeric means with feature mismatch counts and modal prototypes. Its update steps reduce or preserve the mismatch objective, while explicit tie and cycle handling is needed to ensure a reliable stopping rule.

Check Your Understanding

For each problem, use one mismatch per differing feature and show the key counts before checking the answer.

Two records have four categorical features and agree on the first, second, and fourth features. What is their matching dissimilarity? (Answer: 1)
In a cluster of eight records, a region feature has category counts A=4, B=3, C=1, and a delivery feature has counts express=5, standard=3. Give a modal prototype and its total mismatch cost. (Answer: (A, express), with \(4+3=7\) mismatches)
Two prototypes are \(M_1=(\text{app},\text{annual},\text{basic})\) and \(M_2=(\text{agent},\text{monthly},\text{plus})\). To which prototype is a record (agent, annual, plus) closer, and what is its distance? (Answer: \(M_2\), distance 1; its distance to \(M_1\) is 2)
A five-record cluster has one categorical feature with counts phone=2, web=2, branch=1. What are the modal choices and the minimum mismatch cost on this feature? (Answer: phone or web; the minimum cost is 3)

What You'll Learn