Unit 4: UNSUPERVISED LEARNING: CLUSTERING AND PATTERN DETECTION

I. Orientation — Learning Structure Without Labels

Unsupervised learning discovers structure in data whose observations have no predefined target label. This unit focuses on clustering, which groups similar observations, and association analysis, which identifies items or events that frequently occur together.

• Input: A dataset contains features or transactions but no known output variable, such as customer attributes without customer segments.
• Central objective: The method seeks regularities such as compact groups, hierarchical relationships, frequent itemsets, or dependable co-occurrences.
• Similarity assumption: Meaningful structure can be represented through a distance, similarity, or co-occurrence measure.
• Exploratory character: Results suggest patterns rather than proving causal relationships; domain interpretation remains necessary.
• Feature dependence: Scaling, encoding, missing-value treatment, and irrelevant variables can substantially change discovered patterns.
• Evaluation: With no labels, quality is assessed using internal measures, stability, interpretability, and usefulness in the intended application.

II. K-Means Clustering — Partitioning Data Around Centroids

K-means partitions numerical observations into a chosen number of clusters by minimizing variation within each cluster. Every observation belongs to exactly one cluster, represented by its centroid.

A. K-Means Clustering

K-means repeatedly assigns observations to their nearest centroid and recomputes centroids until the assignments stabilize.

• Objective function: For observations divided into clusters (C_1,\ldots,C_K), K-means minimizes within-cluster sum of squares (WCSS):

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

• (K): specified number of clusters.
• (x_i): the (i)-th observation vector.
• (C_k): observations assigned to cluster (k).
• (\mu_k): mean vector, or centroid, of cluster (k).
• (||x_i-\mu_k||^2): squared Euclidean distance from an observation to its centroid.

• Algorithm: The alternating assignment and update operations never increase (J).

1. Choose K initial centroids.
2. Assign each observation to its nearest centroid.
3. Replace each centroid with the mean of its assigned observations.
4. Repeat steps 2–3 until assignments or centroid positions stop changing.

• Preprocessing: Features should usually be standardized, for example with (z=(x-\bar{x})/s), because a large-scale variable can dominate Euclidean distance.
• Convergence: The algorithm reaches a local minimum in finitely many assignment patterns, but not necessarily the global minimum.
• Conditions: K-means works best for compact, roughly spherical, similarly sized clusters and is sensitive to outliers because both means and squared distances are affected by extreme values.

B. K-means clustering intuition

The intuition is to place representative centers so that each observation lies near the center of its assigned group.

• Geometric view: Assignment divides the feature space into Voronoi regions; every point in a region is closer to its centroid than to any other centroid.
• Mean as representative: For squared Euclidean distance, the arithmetic mean is the point that minimizes total squared distance to observations in a cluster.
• Alternating improvement:
  1. Assignment step: Fixed centroids produce the lowest available distance by assigning each point to its nearest center.
  2. Update step: Fixed memberships produce the lowest squared error by moving each center to its cluster mean.
• Illustration: For one-dimensional points (1,2,8,9) with (K=2), stable clusters are ({1,2}) and ({8,9}), whose centroids are (1.5) and (8.5).
• Decision boundaries: Boundaries are linear hyperplanes midway between centroids, which helps explain why K-means struggles with curved or interlocking groups.

C. K-means random initialization trap

The random initialization trap occurs when poor starting centroids lead K-means to an inferior local minimum.

• Path dependence: Different initial centers can create different early assignments, final clusters, and WCSS values on the same dataset.
• Typical failure: Two initial centroids may fall in one natural group while another group initially has no representative, producing unbalanced or misleading partitions.
• Multiple restarts: Run K-means with several random seeds and retain the solution with the smallest final WCSS; n_init = 10 means ten independent initializations.
• K-means++: The first centroid is selected randomly; each later centroid is sampled with probability proportional to the squared distance from its nearest existing centroid.

P(x_i selected) = D(x_i)² / Σ_j D(x_j)²

• (D(x_i)): distance from (x_i) to its nearest selected centroid.
• This spreads initial centers and generally improves convergence and solution quality.

• Stability check: Similar assignments and WCSS values across seeds indicate a more dependable structure; large variation suggests overlap, outliers, or an unsuitable (K).

D. K-means selecting number of clusters

Selecting (K) balances compact clusters against unnecessary fragmentation.

• Elbow method: Plot WCSS against (K) and choose the bend after which additional clusters yield only small reductions. WCSS always decreases as (K) rises, reaching zero when each distinct point forms its own cluster.
• Silhouette coefficient: For observation (i), compare cohesion (a(i)) with the nearest-cluster separation (b(i)):

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

• (a(i)): average distance from (i) to its own cluster.
• (b(i)): smallest average distance from (i) to another cluster.
• (s(i)) approaches 1 for a well-placed point, 0 near a boundary, and a negative value for possible misassignment.

• Model comparison: Average silhouette can compare candidate values of (K), while gap statistics compare observed WCSS with reference data lacking cluster structure.
• Domain constraint: Operational usefulness matters; a retailer may choose five actionable customer segments even if a statistical measure weakly favors six.
• Validation: Inspect cluster sizes, centroid profiles, seed stability, and behavior on resampled data rather than relying on one metric.

III. Hierarchical Clustering — Building Nested Groups

Hierarchical clustering represents nested similarity relationships as a tree called a dendrogram. Agglomerative clustering begins with individual observations and successively merges the closest clusters.

A. Hierarchical Clustering (Agglomerative)

Agglomerative hierarchical clustering constructs a bottom-up hierarchy without requiring the final number of clusters in advance.

• Procedure:

1. Place each of n observations in its own cluster.
2. Compute distances between clusters using a chosen linkage.
3. Merge the two closest clusters.
4. Update inter-cluster distances.
5. Repeat until one cluster remains.

• Dendrogram: Leaves represent observations, branches represent merges, and branch height records the distance at which clusters joined.
• Cluster selection: Cutting the dendrogram at a fixed height creates a partition; a large vertical gap often indicates a defensible cut before dissimilar groups merge.
• Advantages: The method exposes structure at several resolutions and does not require an initial (K); the dendrogram also supports interpretation.
• Limitations: Standard agglomerative merging is irreversible, can be computationally expensive for large (n), and remains sensitive to scaling, outliers, the distance metric, and linkage.

B. Types of Linkages (Single, Complete, Average, Centroid)

A linkage defines how the distance between two multi-observation clusters is calculated and therefore controls the hierarchy’s shape.

• Single linkage: Uses the smallest pairwise distance:

d(A,B) = min d(a,b), where a ∈ A and b ∈ B

• It can detect elongated shapes but may create chaining, where groups join through a sequence of nearby bridge points.

• Complete linkage: Uses the largest pairwise distance, (d(A,B)=\max d(a,b)), encouraging compact clusters but making results sensitive to outliers.
• Average linkage: Uses the mean of all cross-cluster pairwise distances:

d(A,B) = [1 / (|A||B|)] Σ(a∈A) Σ(b∈B) d(a,b)

• It balances the nearest-pair emphasis of single linkage and farthest-pair emphasis of complete linkage.

• Centroid linkage: Uses the distance between cluster means, (d(A,B)=d(\mu_A,\mu_B)); after merging, the new centroid is weighted by cluster sizes.
• Comparison: Single linkage prioritizes connectivity, complete linkage controls cluster diameter, average linkage reflects overall separation, and centroid linkage compares central locations.

IV. Association Analysis — Detecting Co-Occurrence Patterns

Association analysis discovers implication-style relationships in transactional data. It first identifies itemsets occurring often enough and then evaluates rules such as (X\rightarrow Y), where (X) and (Y) are disjoint itemsets.

A. Association Rules

Association rules quantify how frequently items occur together and how strongly the presence of one item predicts another.

• Support: The proportion of (N) transactions containing an itemset (X):

support(X) = count(X) / N

• Confidence: The conditional frequency of (Y) among transactions containing (X):

confidence(X → Y) = support(X ∪ Y) / support(X)

• Lift: The rule’s confidence relative to the baseline frequency of (Y):

lift(X → Y) = confidence(X → Y) / support(Y)

• Lift (>1) indicates positive association, lift (=1) independence, and lift (<1) negative association.

• Example: In 100 baskets, 20 contain bread, 15 contain butter, and 10 contain both. For bread (\rightarrow) butter, support is (0.10), confidence is (10/20=0.50), and lift is (0.50/0.15=3.33).
• Caution: High confidence can merely reflect a common consequent, and association does not establish causation.

B. Finding Patterns

Finding useful patterns requires efficient candidate discovery followed by statistical and business filtering.

• Apriori principle: If an itemset is frequent, all its subsets must be frequent; equivalently, any superset of an infrequent itemset must also be infrequent.
• Apriori process:

1. Find frequent one-itemsets using minimum support.
2. Join frequent k-itemsets to form (k+1)-item candidates.
3. Prune candidates having an infrequent subset.
4. Count candidate support and retain frequent itemsets.
5. Generate rules meeting minimum confidence.

• FP-Growth: A frequent-pattern tree compresses transactions and mines frequent itemsets without explicitly generating every Apriori candidate, often improving performance on dense data.
• Threshold tradeoff: Excessively high support misses rare valuable patterns; excessively low support creates many candidates and spurious rules.
• Filtering: Rank surviving rules using support, confidence, lift, minimum item counts, rule length, novelty, and domain relevance; remove redundant rules conveying the same relationship.

C. Market Basket Analysis Using Association Rules

Market basket analysis applies association rules to purchase transactions to identify products commonly bought together.

• Representation: Each receipt is a transaction and each product is a binary item; quantity and purchase order are usually omitted in the basic formulation.
• Workflow: Clean product identifiers, define the transaction boundary, encode baskets, mine frequent itemsets, generate rules, filter them, and validate findings on later transactions.
• Business uses: Strong rules can guide shelf placement, cross-selling recommendations, bundled offers, coupon targeting, and inventory coordination.
• Interpretation: A rule such as {pasta, sauce} → {cheese} should be judged by cheese’s baseline support and rule lift, not confidence alone.
• Operational risks: Promotions, seasonality, store layout, household purchasing, and product availability can create temporary or confounded associations.
• Responsible deployment: Test recommendations through controlled experiments and monitor revenue, margin, customer response, and rule stability; a statistically strong bundle may still be unprofitable or inconvenient.