How do you cluster a table of purely categorical attributes, where a mean is undefined?
answer
- the update step is what breaks
- no average of bachelors and PhD
- most frequent value per attribute
- count attributes that disagree
- same loop, different centre definition
basics
~20 sUse k-modes: each cluster centre is the most frequent value of every attribute, and two records are compared by counting the attributes on which they disagree. Averaging category codes is meaningless, so plain k-means does not apply.
solid answer
~50 sk-means cannot run here because its update step averages the members of a cluster, and there is no average of `bachelors` and `PhD`. k-modes replaces the two pieces that assume numbers. The centre becomes a **mode vector**: for each attribute, the value that occurs most often among the cluster's members. The comparison becomes a simple matching count: how many attributes two records disagree on. The loop is otherwise the same as k-means — assign every record to the closest centre, recompute the modes, repeat until assignments stop changing. On a table of job-applicant profiles (degree, region, seniority band) a k-modes centre reads as a describable archetype: `MSc / EMEA / mid`. The alternative route is to build a pairwise dissimilarity matrix over the records and run k-medoids on it, which also works when the table mixes categorical and numeric columns.
go deeper
Be ready to say out loud why the k-means update step fails on categories — there is no average of two labels — and to name a method whose centre is a mode or an actual record instead. That reasoning matters more than the algorithm's name.
Explain the two substitutions precisely: mode vector per attribute as the centre, count of disagreeing attributes as the comparison, with the assign-and-recompute loop unchanged. Mention that ties are common and make the result less stable than the numeric case.
Show judgment about the columns: band high-cardinality attributes, question equal weighting of attributes that the business does not weigh equally, and check whether rare levels are being swallowed by archetypes that do not describe them.
Frame it as a modelling decision, not a tool choice: the mismatch count encodes an implicit claim that all attribute disagreements are equally important. Decide with the business whether that is acceptable, or whether a weighted or mixed-type formulation is worth the extra cost and explanation.
## Why k-means simply cannot run k-means alternates two steps: assign each point to the nearest centre, then set each centre to the **mean** of the points assigned to it. That second step is arithmetic on the feature values. Given a column whose values are `bachelors`, `MSc`, `PhD`, there is no mean. Given `EMEA`, `APAC`, `AMER`, there is no mean. The algorithm has nothing to compute. The naive rescue — replace the categories with integer codes and average those — produces a number that means nothing. If `EMEA=0, APAC=1, AMER=2`, then a cluster split evenly between EMEA and AMER gets a centre of `1`, which reads as APAC: a region that nobody in the cluster is from. Worse, the *arbitrary* code order silently asserts that APAC sits between the other two, and every distance the algorithm computes inherits that fiction. ## What k-modes changes k-modes keeps the shape of the loop and swaps out the two number-dependent pieces. **The centre.** Instead of a mean vector, a cluster is summarised by a **mode vector**: for each attribute independently, the value that appears most often among the cluster's current members. For a cluster of applicant profiles, that might be `MSc / EMEA / mid`. Note this is a synthetic combination — no single applicant need match it on all three attributes — but every component is a real category, so the centre is readable. **The comparison.** Instead of squared numeric distance, two records are scored by a simple matching count: the number of attributes on which they hold different values. Two applicants sharing degree and seniority but differing on region score 1; identical profiles score 0. The objective the algorithm reduces is the total of these mismatch counts between records and their assigned mode vector. **The loop.** Pick k initial modes, assign each record to the mode it mismatches least, recompute each cluster's mode vector, and repeat until assignments stabilise. Like k-means, it converges to a local optimum, so different starts give different partitions, and `k` is still yours to choose. ## What to watch out for - **Ties everywhere.** With few attributes and few levels, many records tie for "closest centre", and modes tie for "most frequent value". Implementations break ties arbitrarily, which makes results less stable than the numeric case. - **High-cardinality columns.** An attribute with hundreds of levels — postcode, product SKU — contributes a mismatch almost always, so it adds noise rather than structure. Group it into meaningful bands before clustering. - **Every attribute weighs the same.** A mismatch on `region` counts exactly as much as a mismatch on `seniority band`, whether or not the business thinks they matter equally. Weighting attributes is a deliberate decision, not a default. - **Rare categories.** A level held by a handful of records will essentially never win a mode, so those records get absorbed into a cluster whose archetype does not describe them. ## Mixed tables Real tables are rarely purely categorical. Two standard routes: 1. **k-prototypes**, which clusters mixed data by combining a numeric distance on the numeric columns with the mismatch count on the categorical ones, weighted by a parameter that decides how much a category disagreement is worth relative to a numeric gap. Choosing that weight is the whole game, and it is a domain decision. 2. **Reduce to a dissimilarity matrix and run k-medoids.** Score every pair of records with a mixed-type dissimilarity, then cluster the matrix. This costs `n`-squared memory but sidesteps the question of what an average of anything is, and gives centres that are real records. ## What an interviewer is testing Mostly one thing: do you notice that the algorithm's *update step* is what breaks, rather than reaching for a preprocessing trick and hoping. A candidate who says "turn the categories into numbers and run k-means" has not thought about what the resulting centre means. A candidate who says "the mean is undefined, so I need a method whose centre is a mode or an actual record" has.
- What is wrong with mapping the categories to integers and running k-means anyway?The integer order is invented, so the distances are invented. With `EMEA=0, APAC=1, AMER=2`, a cluster split between EMEA and AMER gets a centre of 1 — reported as APAC, a region nobody in that cluster is from — and the coding also asserts that APAC lies between the other two. The algorithm runs and returns numbers; the numbers describe an ordering the data never had.
- Your table has both categorical and numeric columns. What now?Either k-prototypes, which adds a numeric distance on the numeric columns to the mismatch count on the categorical ones with a weight deciding how much one category disagreement is worth relative to a numeric gap; or reduce every record pair to a mixed-type dissimilarity and run k-medoids on that matrix. The first is cheaper, the second avoids defining any average at all.
- Why can a high-cardinality column such as postcode hurt k-modes?With hundreds of levels, almost every pair of records disagrees on that attribute, so it contributes a near-constant mismatch that carries no information while diluting the attributes that do. It also almost never produces a meaningful mode. Band it into regions or drop it before clustering.
saying these in an interview costs you the question
- Encodes categories as integers and averages them
- Claims k-means works on any data after encoding
- Says the k-modes centre must be an existing record
- Ignores that every attribute is weighted equally
- Thinks categorical clustering avoids picking k