A mathematical and architectural study of knowledge discovery without ground-truth labels: Centroid, Hierarchical, and Density-based Clustering (K-Means, DBSCAN), Parametric and Non-parametric Density Estimation (GMM, KDE), Dimensionality Reduction (PCA), and Association Rule Learning (Apriori).
In Unsupervised Learning, an algorithm is provided exclusively with an input dataset of unlabeled observations D = {x_1, x_2, dots, x_N } subset of R^d without corresponding supervisory response targets y.
Without explicit target labels to compute prediction errors (y - y_predicted), the algorithm cannot minimize empirical risk in the traditional supervised sense. Instead, unsupervised learning formulates optimization objectives centered on intrinsic structural properties:
The objective corresponds to one of four fundamental geometric and probabilistic problems:
Partitioning observations into discrete latent groups such that intra-cluster similarity is maximized and inter-cluster similarity is minimized.
Modeling the continuous joint probability density function p(x) to identify anomaly outliers and generate synthetic samples.
Projecting high-dimensional feature spaces (d) into lower-dimensional manifolds (k ll d) while preserving maximal variance or pairwise distances.
Discovering frequent co-occurrence relationships and conditional dependencies across large transaction itemsets (X ⇒ Y).
In enterprise systems, unlabeled data is abundant and virtually free—collected continuously from server event logs, IoT sensors, clickstream trajectories, and raw audio/text. Supervised labeling requires expensive human domain experts, introduces annotator bias, and scales linearly with dataset size (O(N) cost). Unsupervised learning extracts latent representations that power anomaly detection, customer segmentation, recommendation engines, and foundational self-supervised pre-training.
K-Means partitions N observations into K non-overlapping clusters by minimizing the Within-Cluster Sum of Squares (WCSS / Inertia):
Lloyd's Alternating Optimization Algorithm:
x_i to its nearest centroid μ_k, forming Voronoi polygonal cells: C_k = {x_i : x_i - μ_k^2 ≤ x_i - μ_j^2, for all j }.μ_k as the mean of all points assigned to cluster C_k.μ_k(t+1) - μ_k(t) < ε (guaranteed local convergence).
Standard random initialization frequently falls into poor local minima. K-Means++ picks the first centroid uniformly at random, then selects each subsequent centroid μ_k with probability proportional to the squared distance to the nearest existing centroid: P(x) = (D(x)^2 / Sum D(x')^2). This forces initial seeds to be spread far apart across the data manifold, guaranteeing an O( log K) competitive bound against optimal clustering.
Density-Based Spatial Clustering of Applications with Noise (DBSCAN) locates regions of high point density separated by areas of low density. Unlike K-Means, it does not require specifying K and discovers arbitrary non-convex shapes:
MinPts points within radius ε: |N_ε(p)| ≥ MinPts. Forms cluster anchors.MinPts neighbors, but falls within ε-neighborhood of a Core Point. Lies on cluster perimeter.C = -1).
Without ground-truth labels, cluster quality is validated using the Silhouette Coefficient s(i) in [-1.0, +1.0]:
Where a(i) is the mean intra-cluster distance from point i to all other points in its own cluster, and b(i) is the mean nearest-cluster distance. s ≈ +1 indicates dense, well-separated clusters; s ≈ 0 indicates overlapping boundaries; s < 0 means instances were assigned to the wrong cluster.
Models probability density as a weighted convex combination of K multivariate Gaussian distributions:
p(x) = Sum k=1^K π_k N(x μ_k, Σ_k), quad Sum k=1^K π_k = 1γik = P(z_i = k x_i) = (π_k N(x_i μ_k, Σ_k) / Sum j=1^K π_j N(x_i μ_j, Σ_j))
Makes zero parametric assumptions about distribution shapes. Places a smooth kernel function K(·) centered at every single data observation:
f_predicted_h(x) = (1 / N h^d) Sum i=1^N K( (x - x_i / h) right)h > 0 controls smoothing: small h ⇒ spiky, high-variance density; large h ⇒ over-smoothed, high-bias density.
High-dimensional datasets suffer from the Curse of Dimensionality: geometric volume explodes exponentially, Euclidean distances concentrate into a narrow band (dist max ≈ dist min), and models require exponentially more data to generalize.
PCA identifies an orthogonal coordinate system where the first principal component aligns with the direction of maximal variance, and each successive component is mutually orthogonal:
Where X is mean-centered, Σ in Rd × d is the sample covariance matrix, v_k are the orthonormal eigenvectors (principal axes), and λ_k are the eigenvalues representing variance along each axis.
X - μ. High collinearity across original dimensions.k < d eigenvectors capturing >95 % cumulative variance: (Sum i=1^k λ_i / Sum j=1^d λ_j) ≥ 0.95.Z = XV_k. Orthogonal, zero cross-correlation, minimal L_2 reconstruction loss.Association rule mining discovers interesting statistical relationships, correlations, and co-occurrences between items in transaction databases (e.g., Market Basket Analysis: "If customers buy Diapers, they also buy Beer").
| Association Metric | Mathematical Equation | Probabilistic Meaning | Threshold Interpretation |
|---|---|---|---|
| Support | supp(X) = (freq(X) / N) |
P(X) |
Prevalence: Filters out rare item combinations. Must exceed min _support. |
| Confidence | conf(X ⇒ Y) = (supp(X Union Y) / supp(X)) |
P(Y | X) |
Certainty: Conditional probability that basket contains Y given X. |
| Lift | lift(X ⇒ Y) = (supp(X Union Y) / supp(X)supp(Y)) |
(P(Y|X) / P(Y)) |
Lift > 1: Positive association. Lift = 1: Independent. Lift < 1: Substitution/negative. |
"All non-empty subsets of a frequent itemset must also be frequent."
Contrapositive: If an itemset {A, B } is infrequent (supp < min _support), then any superset containing it (e.g., {A, B, C }, {A, B, D }) is guaranteed to be infrequent and can be pruned immediately from the search tree. This reduces search complexity from exponential O(2^M) to a tractable subset.
The following standalone script implements and validates K-Means with Silhouette evaluation, DBSCAN non-convex clustering, Gaussian Mixture Models, PCA dimensionality reduction, and an Association Rule metric calculator:
# =====================================================================
# DevAscent Academy: Verified Comprehensive Unsupervised Learning Suite
# Demonstrates: K-Means (Elbow & Silhouette), DBSCAN, Gaussian Mixture
# Models (GMM), PCA Decomposition, and Association Rules
# =====================================================================
import numpy as np
import pandas as pd
from sklearn.datasets import make_blobs, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, DBSCAN
from sklearn.mixture import GaussianMixture
from sklearn.decomposition import PCA
from sklearn.metrics import silhouette_score
def run_clustering_and_density_demo():
print("=== 1. CLUSTERING: K-MEANS & SILHOUETTE VALIDATION ===")
np.random.seed(42)
# Generate 3 isotropic Gaussian blobs
X_blobs, _ = make_blobs(n_samples=600, centers=3, n_features=4, cluster_std=1.2, random_state=42)
X_scaled = StandardScaler().fit_transform(X_blobs)
for k in [2, 3, 4, 5]:
km = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
cluster_labels = km.fit_predict(X_scaled)
sil = silhouette_score(X_scaled, cluster_labels)
print(f"K={k} | WCSS (Inertia): {km.inertia_:10.2f} | Silhouette Score: {sil:.4f}")
print("Takeaway: K=3 achieves the maximum silhouette score, matching the ground-truth structure.\n")
print("=== 2. NON-CONVEX CLUSTERING: DBSCAN ===")
# Generate non-convex concentric crescent moons
X_moons, _ = make_moons(n_samples=500, noise=0.08, random_state=42)
db = DBSCAN(eps=0.22, min_samples=6)
labels = db.fit_predict(X_moons)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"DBSCAN Detected Clusters: {n_clusters}")
print(f"Noise / Anomaly Outliers Isolated: {n_noise} ({n_noise/len(X_moons):.2%})\n")
print("=== 3. PROBABILISTIC SOFT CLUSTERING: GMM ===")
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42)
gmm.fit(X_scaled)
probs = gmm.predict_proba(X_scaled)
print(f"GMM Converged: {gmm.converged_} in {gmm.n_iter_} iterations")
print(f"Sample 0 Soft Responsibilities: {probs[0].round(4)}")
print(f"BIC Score: {gmm.bic(X_scaled):.2f}\n")
def run_pca_dimensionality_reduction():
print("=== 4. DIMENSIONALITY REDUCTION: PCA DECOMPOSITION ===")
np.random.seed(42)
# Generate correlated 8-dimensional dataset
X = np.random.randn(300, 8)
X[:, 2] = X[:, 0] * 1.8 + X[:, 1] * 0.5 # Injected multicollinearity
X[:, 5] = X[:, 3] * -2.2
scaler = StandardScaler()
X_std = scaler.fit_transform(X)
pca = PCA(n_components=4)
X_pca = pca.fit_transform(X_std)
var_ratio = pca.explained_variance_ratio_
cum_var = np.cumsum(var_ratio)
print(f"Original Dimension: {X.shape[1]} -> Reduced Dimension: {X_pca.shape[1]}")
for idx, (var, cum) in enumerate(zip(var_ratio, cum_var), start=1):
print(f"PC{idx} | Individual Variance: {var:6.2%} | Cumulative Explained Variance: {cum:6.2%}")
print(f"Top 4 Principal Components preserve {cum_var[-1]:.2%} of total information!\n")
def calculate_association_rules():
print("=== 5. ASSOCIATION RULE LEARNING METRICS ===")
# Transactions: List of shopping baskets
transactions = [
{'Bread', 'Milk'},
{'Bread', 'Diapers', 'Beer', 'Eggs'},
{'Milk', 'Diapers', 'Beer', 'Cola'},
{'Bread', 'Milk', 'Diapers', 'Beer'},
{'Bread', 'Milk', 'Diapers', 'Cola'}
]
N = len(transactions)
def support(itemset):
count = sum(1 for t in transactions if itemset.issubset(t))
return count / N
# Rule: {Diapers, Milk} => {Beer}
X = {'Diapers', 'Milk'}
Y = {'Beer'}
XY = X.union(Y)
supp_X = support(X)
supp_Y = support(Y)
supp_XY = support(XY)
conf = supp_XY / supp_X
lift = supp_XY / (supp_X * supp_Y)
print(f"Rule: {X} => {Y}")
print(f"Support(X): {supp_X:.2f} ({supp_X*N:.0f}/{N} transactions)")
print(f"Support(Y): {supp_Y:.2f} ({supp_Y*N:.0f}/{N} transactions)")
print(f"Support(X ∪ Y): {supp_XY:.2f}")
print(f"Confidence: {conf:.2%}")
print(f"Lift: {lift:.4f} (Lift > 1.0 indicates strong positive association!)")
if __name__ == "__main__":
run_clustering_and_density_demo()
run_pca_dimensionality_reduction()
calculate_association_rules()J = Sum x - μ_k^2. Geometrically, assigning points to their closest centroid partitions the vector space into convex polygonal Voronoi cells bounded by linear hyperplanes. Furthermore, using Euclidean distance from a central mean point inherently assumes that clusters are spherical (isotropic) and of comparable size. When clusters form non-convex crescents, concentric rings, or varying densities, the straight Voronoi boundaries cut directly through clusters. Density-based algorithms like DBSCAN resolve this by linking points through continuous density-connected chains.
ε and MinPts in DBSCAN and how they isolate anomalies.
ε specifies the maximum physical distance radius defining an observation's neighborhood (N_ε(p)), while MinPts defines the minimum density threshold of points required to form a cluster core. A point p is a Core Point if |N_ε(p)| ≥ MinPts. Points within ε of a core point but possessing fewer than MinPts neighbors are Border Points. Any point that is neither a core point nor reachable from a core point is classified as Noise / Anomaly. A rule of thumb is setting MinPts ≥ 2d (twice the feature dimensions) and selecting ε by plotting the k-nearest neighbor distance curve and locating the "knee" elbow inflection.
I(x in C_k) in {0, 1 }). GMM computes continuous posterior probabilities (responsibilities γik in [0, 1]) representing soft degree-of-membership under Bayes' theorem.Σ_k = σ^2 I). GMM parameterizes individual covariance matrices Σ_k, allowing clusters to form ellipsoids with arbitrary orientations and unequal scales. If all covariances in GMM are constrained to σ^2 I and variance σ^2 → 0, the EM update equations reduce mathematically to Lloyd's K-Means algorithm.X be a mean-centered design matrix. We seek a unit direction vector w (w₂² = w^Tw = 1) that maximizes the sample variance of the projected data z = Xw:
Var(z) = (1 / N-1) z^Tz = w^T ( (1 / N-1)X^TX right) w = w^T Σ ww^Tw = 1:
L(w, λ) = w^T Σ w - λ (w^Tw - 1)w to zero:
∇w L = 2Σw - 2λ w = 0 ⇒ Σw = λ ww^T: w^T Σw = λ w^Tw = λ. Thus, the projected variance directly equals the eigenvalue λ. To maximize variance, w must be the eigenvector corresponding to the maximum eigenvalue λ max.
M items, the power set of all possible itemsets is 2^M - 1. For M = 100, evaluating all combinations (≈ 1.26 × 1030) is computationally impossible. The Apriori Principle exploits the monotonic downward-closure property of Support:
If X subset ofeq Y ⇒ supp(X) ≥ supp(Y)X is infrequent (supp(X) < min _support), every superset Y supset X is guaranteed to be infrequent. The algorithm prunes the entire branch of candidate supersets without ever counting their database occurrences, dramatically reducing candidate evaluations.
conf(X ⇒ Y) = P(Y | X) = (P(X Intersection Y) / P(X)). Suppose 90 % of supermarket customers purchase Milk (P(Milk) = 0.90). If we evaluate the rule {Coffee } ⇒ {Milk }, we might discover a seemingly impressive Confidence of 85 %. However, this is actually lower than the unconditional base rate of purchasing Milk (90 %). Customers who buy Coffee are actually less likely to purchase Milk than random shoppers! Lift normalizes confidence by the target's base rate:
lift(X ⇒ Y) = (P(YX) / P(Y)) = (0.85 / 0.90) ≈ 0.944< 1.0, it exposes that Coffee and Milk have a negative association (substitutes), preventing costly marketing blunders.
K. Because WCSS strictly decreases monotonically as K increases (reaching 0 when K=N), engineers search for a sharp inflection point ("elbow") where diminishing returns set in. However, for real-world continuous data, the elbow is frequently smooth, ambiguous, and subjective. Silhouette Analysis evaluates both cohesion a(i) (compactness within cluster) and separation b(i) (distance to nearest neighbor cluster). The silhouette score peaks at an objective maximum value, providing an unambiguous metric that penalizes over-clustering and alerts engineers when clusters overlap (s ≤ 0).
f(x); new unseen test points cannot be projected into the learned embedding without re-running optimization on the entire dataset.