Assignment 1: Clustering Techniques for Categorical

Data (K-Modes)
Implementation and Analysis

by Saumya Pancholi (M25CSA027)

October 2,2025

Abstract
This report presents the step-by-step manual implementation of the K-Modes
clustering algorithm to cluster a synthetic categorical dataset. The dataset con-
sists of 200 samples with 9 categorical features, designed with distinct category
distributions for clear cluster separation. The report covers the theoretical back-
ground, algorithm derivation, code details, as well as visual and quantitative results
analysis.

1 Introduction
Clustering is an unsupervised machine learning technique used to group data points into
clusters such that points in the same cluster are more similar to each other than to
those in other clusters. Traditional clustering algorithms such as K-Means use Euclidean
distance and mean computations, which are not suitable for categorical data.
K-Modes clustering adapts K-Means for categorical data by replacing means with
modes, and Euclidean distance with Hamming distance (count of feature mismatches).
This report implements K-Modes clustering manually from scratch, explains the under-
lying concepts, and demonstrates clustering a synthetic categorical dataset based on the
roll number features.

2 Dataset Creation
Based on the roll number M25CSA027, the number of features is the sum of the digits in
the last three characters: 0 + 2 + 7 = 9.
The synthetic dataset contains 200 samples, each with 9 categorical features. The cat-
egories for each feature are carefully chosen to encourage cluster separation by allocating
distinct subsets of categories to different clusters.
For feature fi , the categories Ci = {ci1 , ci2 , . . .} were selected such that cluster samples
draw mostly from different subsets of Ci , making clusters naturally separable.

1
3 K-Modes Clustering: Fundamentals and Algorithm
3.1 Distance Metric: Hamming Distance
For two categorical data points x = (x1 , x2 , . . . , xm ) and y = (y1 , y2 , . . . , ym ), the Ham-
ming distance is defined as
m
X
dH (x, y) = δ(xj , yj )
j=1

where (
1 if xj ̸= yj
δ(xj , yj ) =
0 if xj = yj
This distance counts the number of mismatched categorical features.

3.2 Cluster Centroids as Modes

Unlike numeric means, for categorical features, we compute the mode of each feature
within a cluster:


zk = arg max fc,1 (k), arg max fc,2 (k), . . . , arg max fc,m (k)
c∈C1 c∈C2 c∈Cm

where fc,j (k) is the frequency of category c in feature j in cluster k.

3.3 Algorithm Steps

1. Initialization: Randomly select K points from the dataset as initial cluster modes
{z1 , z2 , . . . , zK }.

2. Assignment: For each data point xi , assign it to the cluster whose mode minimizes
the Hamming distance:

cluster(xi ) = arg min dH (xi , zk )

k=1,...,K

3. Update: For each cluster, recompute the mode for each feature based on assigned
points.

4. Repeat steps 2 and 3 until modes converge (no change) or max iterations reached.

4 Manual Implementation: Stepwise Details

Listing 1: Generating synthetic categorical data with spread clusters

// Step 1 : Data c r e a t i o n
np . random . s e e d ( 4 2 )
num samples = 200
num features = 9

categories = [

2
 [ ’ Quartz ’ , ’ G r a n i t e ’ , ’ B a s a l t ’ , ’ Marble ’ , ’ Limestone ’ ] ,
[ ’ Falcon ’ , ’Hawk ’ , ’ Eagle ’ , ’ Owl ’ ] ,
[ ’ Copper ’ , ’ I r o n ’ , ’ Aluminum ’ , ’ Zinc ’ ] ,
[ ’ Marathon ’ , ’ S p r i n t ’ , ’ Relay ’ , ’ H u r d l e s ’ ] ,
[ ’ Jazz ’ , ’ B l u e s ’ , ’ Reggae ’ , ’ C l a s s i c a l ’ , ’ Folk ’ ] ,
[ ’ Python ’ , ’ J a v a S c r i p t ’ , ’ Ruby ’ , ’Go ’ , ’ Rust ’ ] ,
[ ’ Tundra ’ , ’ Savanna ’ , ’ Taiga ’ , ’ Chaparral ’ ] ,
[ ’ Saturn ’ , ’ J u p i t e r ’ , ’ Neptune ’ , ’ Uranus ’ , ’ Pluto ’ ] ,
[ ’ Origami ’ , ’ C a l l i g r a p h y ’ , ’ Ikebana ’ , ’ Ceramics ’ ] ,
]

c l u s t e r s i z e s = [50 ,50 ,50 ,50]

data = [ ]

for c l u s t e r i d , s i z e in enumerate ( c l u s t e r s i z e s ) :
c l u s t e r s a m p l e = {}
for f e a t i d x in range ( n u m f e a t u r e s ) :
cat list = categories [ feat idx ]
s t a r t i d x = c l u s t e r i d % len ( c a t l i s t )
cat subset = c a t l i s t [ start idx : ] + c a t l i s t [ : start idx ]
c l u s t e r s a m p l e [ f ’ F e a t u r e { f e a t i d x +1} ’ ] = \
np . random . c h o i c e ( c a t s u b s e t [ : max( 2 ,
len ( c a t s u b s e t ) / / 2 ) ] , s i z e=s i z e ) ;
data . append ( pd . DataFrame ( c l u s t e r s a m p l e ) )

d f = pd . c o n c a t ( data ) . r e s e t i n d e x ( drop=True )
print ( d f . head ( ) )
Comments: Data is created per cluster by sampling shifted subsets of categories to
ensure feature diversity and natural cluster separations.
Listing 2: Initialization of cluster modes
// Step 2 : I n i t i a l i z e c l u s t e r modes from random d i s t i n c t p o i n t s
K = 4
np . random . s e e d ( 0 )
i n i t i n d i c e s = np . random . c h o i c e ( num samples , K, r e p l a c e=F a l s e )
modes = d f . i l o c [ i n i t i n d i c e s ] . v a l u e s . copy ( )
Comments: Modes are initial prototype categorical vectors for clusters.
Listing 3: Hamming distance function and iterative clustering
// Step 3 : D e f i n e Hamming d i s t a n c e
def hamming distance ( p o i n t , mode ) :
return np .sum( p o i n t != mode )

// I t e r a t i v e a s s i g n m e n t and update
a s s i g n m e n t s = np . z e r o s ( num samples , dtype=int )
for i t e r a t i o n in range ( 2 0 ) :
for i in range ( num samples ) :

3
 d i s t s = [ hamming distance ( d f . i l o c [ i ] . v a l u e s , modes [ j ] )
for j in range (K ) ] ;
a s s i g n m e n t s [ i ] = np . argmin ( d i s t s )

old modes = modes . copy ( )

for k in range (K) :
c l u s t e r p o i n t s = d f . i l o c [ a s s i g n m e n t s == k ]
i f not c l u s t e r p o i n t s . empty :
modes [ k ] = c l u s t e r p o i n t s . mode ( ) . i l o c [ 0 ] . v a l u e s

i f np . a r r a y e q u a l ( modes , old modes ) :

print ( f ” Converged a f t e r { i t e r a t i o n } i t e r a t i o n s . ” )
break

df [ ’ Cluster ’ ] = assignments
Comments: - Each point is assigned to nearest cluster mode by minimized mismatch
count. - Modes are updated by selecting most frequent alternative for each feature. -
Process repeats until convergence.

5 Visualization
Since data is categorical and multidimensional, we use t-Distributed Stochastic Neigh-
bor Embedding (t-SNE) for dimension reduction.

Input: numerically encoded features → 2D space preserving neighborhood distances

Plot: Cluster assignments shown by different colors in t-SNE embedding space reveal
cluster separation visually.

6 Results
The algorithm converged quickly (after few iterations). The cluster modes for each cluster
are listed below (displaying mode categorical feature for clarity):

Table 1: Cluster Mode Results

Cluster F1 F2 F3 F4 F5 F6 F7 F8 F9
0 Granite Hawk Iron Marathon Blues Java- Savanna JupiterCalli-
Script graphy
1 Marble Owl Zinc Hurdles Classical Go Chaparral Uranus Ceramics
2 Basalt Eagle AluminumRelay Reggae Ruby Taiga Neptune Ikebana
3 Granite Eagle AluminumRelay Reggae Java- Savanna Jupiter Calli-
Script graphy

The spread-out dataset and clustering process allowed clear cluster formation with
meaningful modal representatives.

4
Figure 1: t-SNE visualization showing cluster groupings of the 200 samples into 4 clusters
after K-Modes clustering.

7 Conclusion
This assignment demonstrated a manual implementation of the K-Modes clustering al-
gorithm tailored for categorical data. It emphasized:

• Understanding of Hamming distance and mode computation as core K-Modes con-

cepts.

• Synthetic categorical data generation with engineered cluster structures.

• Iterative point assignment and mode update until convergence.

• Visualization techniques such as t-SNE for high-dimensional categorical data clus-

ters.