Q19Machine Learning

Unsupervised Machine Learning relies on clustering algorithms to mathematically discover hidden structures in unlabeled datasets. The two absolute dominant architectural paradigms are K-Means (a partition-based algorithm) and Hierarchical Clustering (a tree-based algorithm). They execute fundamentally different mathematical mechanics.

K-Means is a highly aggressive, iterative algorithm that utilizes the Expectation-Maximization (EM) mathematical framework to violently partition the dataset into exactly $K$ distinct, non-overlapping clusters.

The Mathematical Algorithm

• Step 1 (Initialization): The engineer MUST manually define the integer hyperparameter $K$. The algorithm mathematically drops $K$ random points into the data space to act as initial Centroids (the mathematical center of mass).
• Step 2 (Expectation / Assignment): The algorithm calculates the absolute Euclidean distance between every single data point $x_i$ and every centroid ${\mu }_j$: $$D=||x_i-{\mu }_j|{|}^2$$ Each data point is violently assigned to the cluster of the centroid it is mathematically closest to.
• Step 3 (Maximization / Update): The algorithm completely recalculates the position of all $K$ centroids. The new centroid ${\mu }_j$ is moved to the exact mathematical Mean (average) of all the data points currently assigned to it: $${\mu }_j=\frac{1}{|S_j|}\sum _{x\in S_j}x$$
• Step 4 (Convergence): Steps 2 and 3 repeat endlessly. The centroids physically move across the space until they mathematically stop shifting (Convergence). The loss function (Within-Cluster Sum of Squares) is minimized.

Merits and Demerits

It executes blisteringly fast with a time complexity of $O(n\cdot K\cdot I)$. However, guessing the exact $K$ is often mathematically impossible upfront, and K-Means fails catastrophically if the physical clusters are not perfectly spherical.

Hierarchical Clustering completely abandons the concept of predefined $K$. It builds a massive mathematical taxonomy (a Dendrogram) representing the exact distance relationships of every point.

The Mathematical Algorithm (Agglomerative)

• Step 1: Initialize all $N$ data points as $N$ independent clusters.
• Step 2: Compute the massive $N\times N$ Distance Matrix. This defines the exact mathematical distance between every cluster.
• Step 3: Find the two clusters $A$ and $B$ that have the absolute minimum mathematical distance. Violently fuse them into a single cluster $(A\cup B)$.
• Step 4 (Linkage Update): Recalculate the distance from the new fused cluster to all other remaining clusters. The mathematical "Linkage" defines how this is calculated: - Single Linkage: Distance is the absolute minimum distance between any point in $A$ and any point in $B$: $\min (dist(x,y))$. - Ward's Method: Fuses clusters that mathematically minimize the total variance within the clusters.
• Step 5: Repeat until only exactly ONE massive root cluster remains. The engineer then mathematically "cuts" the resulting Dendrogram tree at a specific height to obtain the desired number of clusters.

Merits and Demerits

It is highly interpretable via the Dendrogram and requires zero guessing of $K$. However, its mathematical time complexity is a catastrophic $O(N^3)$, making it completely physically impossible to execute on massive datasets containing millions of rows.