Unit 7: Unsupervised Learning

I. Foundations of Unsupervised Learning

Unsupervised learning discovers structure in data without predefined target labels. Clustering is its central grouping task: observations are partitioned so that members of the same cluster are relatively similar, while members of different clusters are relatively dissimilar.

• Input: A dataset contains observations (x_1,x_2,\ldots,x_n), described by numerical, categorical, or mixed features, but no known class variable.
• Objective: A clustering algorithm seeks a partition (C_1,C_2,\ldots,C_K), where each observation belongs to one or, in soft clustering, several groups.
• Similarity principle: The definition of “similar” depends on the data:
  • Euclidean distance commonly measures numerical similarity.
  • Manhattan distance measures coordinate-wise absolute differences.
  • Simple matching dissimilarity compares categorical values.
• Model dependence: Different algorithms assume different cluster structures; for example, K Means favors compact, approximately spherical numerical clusters.
• Preprocessing convention: Features should be cleaned and transformed appropriately because distance calculations are sensitive to missing values, scale, and representation.
• Validation challenge: Since true labels are generally unavailable, clustering quality is often assessed through cohesion, separation, stability, or domain usefulness.

II. Clustering Algorithms — Discovering Groups in Unlabelled Data

A. Introduction to clustering algorithms

Clustering algorithms organize observations into groups according to a specified similarity rule and optimization criterion.

• Partitioning methods: These divide (n) observations directly into (K) non-overlapping clusters; K Means, K Modes, and K Medians belong to this family.
• Hierarchical methods: These create a nested tree of clusters:
  • Agglomerative clustering begins with one observation per cluster and repeatedly merges clusters.
  • Divisive clustering begins with one cluster and repeatedly splits it.
• Density-based methods: Algorithms such as DBSCAN identify dense regions separated by sparse regions and can mark isolated observations as noise.
• Model-based methods: These assume observations arise from a mixture of probability distributions; Gaussian mixture models, for example, estimate probabilistic cluster membership.
• Hard versus soft assignment:
  1. Hard clustering: Each observation belongs to exactly one cluster, as in standard K Means.
  2. Soft clustering: Each observation receives membership probabilities or degrees, as in Gaussian mixtures or fuzzy clustering.
• Core design choices: A clustering task requires decisions about:
  • Feature representation and scaling.
  • Dissimilarity or similarity measure.
  • Number of clusters (K), where required.
  • Initialization and stopping conditions.
• Data preparation: Standardization prevents large-scale variables from dominating numerical distance:

z_ij = (x_ij - μ_j) / σ_j

Here, (x_{ij}) is feature (j) of observation (i), while (\mu_j) and (\sigma_j) are that feature’s mean and standard deviation.

• Interpretation requirement: A mathematically compact partition is useful only if its clusters are stable, distinguishable, and meaningful for the application.

B. Applications and limitations

Clustering supports exploratory analysis, segmentation, summarization, and anomaly discovery, but its results must not automatically be treated as natural classes.

• Applications: Customer segmentation, document grouping, image compression, biological taxonomy, community detection, and preliminary anomaly screening all use clustering.
• Exploratory value: Cluster profiles can reveal patterns, such as one customer segment having high purchase frequency but low average transaction value.
• Algorithm dependence: The same observations may receive different assignments under Euclidean, Manhattan, or categorical dissimilarity.
• No universal solution: Clustering is affected by feature selection, noise, outliers, initialization, and the assumed value of (K).
• Interpretive caution: A cluster label such as “Cluster 2” has no inherent meaning; meaning comes from examining its features and domain context.

III. K Means — Centroid-Based Numerical Clustering

A. K Means

K Means partitions numerical observations into (K) clusters by minimizing squared Euclidean distance from observations to cluster centroids.

• Objective function:

J = Σ(k=1 to K) Σ(x_i ∈ C_k) ||x_i - μ_k||²

Here, (J) is within-cluster sum of squares, (C_k) is cluster (k), (x_i) is an observation, and (\mu_k) is the arithmetic mean, or centroid, of that cluster.

• Algorithm:
  1. Select (K) initial centroids, often using K Means++.
  2. Assign every observation to its nearest centroid.
  3. Recalculate each centroid as the mean of assigned observations.
  4. Repeat assignment and update until assignments stop changing or the decrease in (J) becomes negligible.
• Centroid update:

μ_k = (1 / |C_k|) Σ(x_i ∈ C_k) x_i

Here, (|C_k|) is the number of observations in cluster (k).

• Worked example: For one-dimensional observations (2,3,10,11) with (K=2), the stable groups are ({2,3}) and ({10,11}); their centroids are (2.5) and (10.5).
• Initialization: Random starting centroids can produce different local minima; multiple runs are therefore compared, retaining the result with the smallest (J).
• Convergence: Each assignment or update step does not increase (J), so the method eventually converges, although not necessarily to the global optimum.

B. Applications and limitations

K Means is efficient for large numerical datasets when clusters are compact and reasonably well separated.

• Strengths: It is simple, fast, scalable, and produces centroids that summarize typical cluster profiles.
• Suitable cases: Numerical customer attributes, color vectors in image compression, and normalized sensor measurements commonly fit its representation.
• Scale sensitivity: A variable measured in thousands can dominate one measured between 0 and 1 unless standardization is applied.
• Outlier sensitivity: Because the mean and squared distance react strongly to extreme values, one distant point can shift a centroid substantially.
• Shape assumption: The method performs poorly for curved, elongated, overlapping, or unequal-density clusters.
• Data restriction: Arithmetic means are not meaningful for nominal categories, motivating K Modes.

IV. K Modes — Mode-Based Categorical Clustering

A. K mode

K Modes adapts partitioning to categorical data by replacing numerical centroids with modes and Euclidean distance with categorical dissimilarity.

• Prototype: The representative of cluster (C_k) is a mode vector (q_k), whose (j)-th component is the most frequent category for feature (j).
• Simple matching dissimilarity:

d(x_i, q_k) = Σ(j=1 to p) δ(x_ij, q_kj)
δ(a, b) = 0 if a = b; otherwise 1

Here, (p) is the number of categorical features, (x{ij}) is observation (i)’s value for feature (j), and (q{kj}) is cluster (k)’s modal value.

• Objective:

J_modes = Σ(k=1 to K) Σ(x_i ∈ C_k) d(x_i, q_k)

The algorithm minimizes the total number of feature mismatches between observations and their cluster modes.

• Procedure:
  1. Choose (K) initial mode vectors.
  2. Assign each observation to the mode with the fewest mismatches.
  3. Update each feature of each mode using the most frequent assigned category.
  4. Repeat until no assignment changes.
• Worked example: For records ((Red,Small)), ((Red,Large)), and ((Blue,Small)), the overall mode is ((Red,Small)), because each component is selected independently by frequency.
• Tie handling: If categories have equal maximum frequencies, a deterministic rule or the previous mode may be used to keep updates reproducible.

B. Applications and limitations

K Modes is useful for nominal attributes but depends on a meaningful treatment of categorical mismatches.

• Applications: Survey-response grouping, product-profile segmentation, and clustering records containing categories such as occupation, region, or device type.
• Advantage: It does not impose artificial arithmetic operations on labels; category codes 1, 2, and 3 are treated as names rather than quantities.
• Frequency blindness: Basic matching gives every mismatch cost 1, even when one category is rare and potentially more informative.
• Interpretive issue: A component-wise mode may combine common values into a prototype that does not occur as an actual record.
• Data restriction: Standard K Modes is not designed for continuous variables; mixed datasets require an approach such as K Prototypes or carefully designed dissimilarities.

V. K Medians — Robust Numerical Partitioning

A. K median

K Medians groups numerical observations by minimizing Manhattan distance and representing each cluster through component-wise medians.

• Objective function:

J_median = Σ(k=1 to K) Σ(x_i ∈ C_k) ||x_i - m_k||₁
||x_i - m_k||₁ = Σ(j=1 to p) |x_ij - m_kj|

Here, (m_k) is the median vector of cluster (k), (p) is the feature count, and (|\cdot|_1) denotes Manhattan distance.

• Update rule: Each coordinate (m_{kj}) is the median of feature (j) among observations assigned to (C_k).
• Procedure: Initialize (K) representatives, assign observations to the nearest representative by Manhattan distance, update coordinate-wise medians, and repeat until stable.
• Worked example: For values (1,2,100) in one cluster, the median is (2), while the mean is approximately (34.33); therefore, the median resists the extreme value.
• Distinction from K Medoids: A K Medians representative may be an artificial coordinate-wise vector, whereas a K Medoids representative must be an actual observation.
• Geometry: Manhattan distance produces axis-aligned, diamond-shaped neighborhoods rather than the circular or spherical neighborhoods associated with Euclidean distance.

B. Applications and limitations

K Medians is preferable to K Means when numerical data contain substantial outliers or absolute deviation is the appropriate loss.

• Robustness: Extreme observations influence medians less than means, reducing centroid displacement.
• Applications: Robust location grouping, logistics, and skewed numerical datasets can benefit from absolute-distance optimization.
• Limitations: The method still requires (K), remains sensitive to initialization, and may settle at a local optimum.
• Scaling: Features with larger numerical ranges can still dominate Manhattan distance, so robust scaling may be necessary.
• Ambiguity: For an even number of values, multiple medians may minimize absolute deviation; implementation rules determine the selected representative.

VI. Clustering Evaluation — Measuring Partition Quality

A. Performance measures of clustering

Clustering performance measures quantify compactness, separation, agreement with known labels, or consistency across repeated samples.

• Within-cluster sum of squares: Lower K Means inertia indicates greater cohesion, but it always decreases as (K) increases; the elbow method looks for a point beyond which improvement becomes modest.
• Silhouette coefficient:

s(i) = [b(i) - a(i)] / max{a(i), b(i)}

Here, (a(i)) is observation (i)’s average dissimilarity to its own cluster, and (b(i)) is its smallest average dissimilarity to another cluster. Values approach (1) for well-separated points, (0) near boundaries, and (-1) for potentially misplaced points.

• Davies–Bouldin index: This compares within-cluster scatter with between-centroid separation; smaller values indicate compact, separated clusters.
• Calinski–Harabasz index: This ratio compares between-cluster dispersion with within-cluster dispersion; larger values generally indicate clearer structure.
• External measures: When trusted reference labels exist, Adjusted Rand Index or normalized mutual information measures agreement while accounting for arbitrary cluster-label names.
• Purity: Each cluster is matched to its most frequent reference class, but purity can be misleading because it rises when many small clusters are created.
• Stability: A reliable solution should remain similar under repeated initialization, resampling, or small perturbations of the data.
• Comparability condition: Scores should be compared using the same preprocessing, feature set, distance definition, and dataset.

B. Interpretation and limitations

No single score proves that a clustering is correct, so numerical evaluation must be combined with stability and domain interpretation.

• Metric alignment: Evaluation should use a dissimilarity compatible with the algorithm—Euclidean for K Means, Manhattan for K Medians, and matching dissimilarity for K Modes.
• Structural bias: Internal indices often favor compact, well-separated clusters and may underrate valid irregular structures.
• Label limitation: External labels can evaluate recovery of known classes, but the clustering may reveal a different legitimate organization.
• Model selection: A suitable (K) balances metric quality, stability, interpretability, and practical usefulness rather than merely maximizing one score.