Clustering and Unsupervised Machine Learning

Introduction to Clustering

• Clustering is an unsupervised learning technique that partitions data instances into meaningful groups called clusters.

• A cluster contains data instances that are more similar to each other than they are to data instances in other clusters.

• Clustering differs from classification in several ways:

  • The goal of classification is to learn a model or function that can assign the correct class label to an unseen data instance. In classification, historical instances with known target values are used to learn patterns that separate classes.

  • In clustering, prior knowledge of class membership is not known but is rather discovered.

  • Like classification, clustering assigns discrete values to data instances.

• Clustering can be used as a stand-alone tool for data exploration or as a pre-processing step for other algorithms.

• Common applications of clustering include:

  • Customer segmentation: Identifying different customer groups for product targeting.

  • Text collection organization: Grouping documents into previously unknown topics.

  • Data aggregation: Representing multiple data instances with a single representative example.

  • Imputation: Replacing missing values by using representative instances.

• A practical example involves Diagnostic-Related Groupings (DRGs). Medical insurance companies use DRGs to determine standard treatment costs. Hospitals may assign incorrect DRGs to obtain higher reimbursements. Fraud detection is difficult because fraud cases are not clear outliers, some hospitals have naturally higher claims, and fraud behavior changes over time. Clustering groups similar hospitals so that outliers within those groups can be investigated.

Methodology: CRISP-DM for Clustering

• The CRoss Industry Standard Process for Data Mining (CRISP-DM) is applied to clustering through six phases:

  • Data Understanding and Data Preparation: An analytical base table is created. This table does not require a target feature. Clustering is sensitive to data quality, so issues must be fixed here.

  • Modelling: Identifying and applying the appropriate clustering algorithm.

  • Evaluation: Found clusters are evaluated and interpreted.

  • Deployment: The algorithm is deployed as a stand-alone or integrated process.

Modeling Phase: Clustering Approaches

• Different algorithms define and form clusters differently:

  • Centroid-based: Iterative algorithms where similarity is derived from closeness to a cluster centroid.

  • Connection-based: Based on the notion that points closer in data space exhibit more similarity than those further away.

  • Density-based: Assigns areas separated by non-dense areas to different clusters.

  • Probability-based: Based on the probability that data instances belong to the same distribution.

• Algorithm selection considers:

  • Size of data set: Computationally expensive algorithms only suit small data sets.

  • Data type and quality: Most algorithms require continuous features and are sensitive to noise.

  • Clustering output: Not all algorithms can identify clusters of any shape.

Similarity Measures

• A similarity measure compares two instances and quantifies how similar or different they are.

• Functions typically use low values to indicate dissimilarity and large values to indicate similarity. However, when using distance as a metric, lower values indicate similarity.

Numerical Data Measures

• Euclidean distance: The distance between instance $\mathbf{a}$ and $\mathbf{b}$ in an $m$-dimensional feature space.

  • $Eucl(\mathbf{a}, \mathbf{b}) = \|\mathbf{a} - \mathbf{b}\|_2 = \sqrt{\sum_{i=1}^m (\mathbf{a}_i - \mathbf{b}_i)^2}$

• Manhattan distance (L1 norm):

  • $Manhattan(\mathbf{a}, \mathbf{b}) = \|\mathbf{a} - \mathbf{b}\|_1 = \sum_{i=1}^m |\mathbf{a}_i - \mathbf{b}_i|$

• Minkowski distance: A family of distance metrics including Euclidean ($p = 2$) and Manhattan ($p = 1$).

  • $Minkowski(\mathbf{a}, \mathbf{b}) = \|\mathbf{a} - \mathbf{b}\|_p = (\sum_{i=1}^m |\mathbf{a}_i - \mathbf{b}_i|^p)^{\frac{1}{p}}$

  • Larger $p$ values place more emphasis on large differences between feature values.

Data Specific Measures

• Binary data: Calculated as the proportion of features that are not equal.

  • $d_{SMC} = \frac{f_{01} + f_{10}}{f_{01} + f_{10} + f_{00} + f_{11}}$

  • $f_{01}$ is where $\mathbf{a}$ is 0 and $\mathbf{b}$ is 1.

  • $f_{10}$ is where $\mathbf{a}$ is 1 and $\mathbf{b}$ is 0.

  • $f_{00}$ is where both are 0, and $f_{11}$ is where both are 1.

• Ordinal data: Assign a numerical value (0 to 1) to categories/ranks. Distance is the absolute difference.

• Categorical data: Calculated as the portion of non-matching features.

  • $d(\mathbf{a}, \mathbf{b}) = \frac{m - j}{m}$, where $m$ is the number of features and $j$ is the number of matches.

• Mixed data types: Weighted combinations of distance measures are used. Gower’s distance is standard when features have equal importance:

  • $d_{Gower}(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^m \text{dist}_i$

  • If categorical: 0 if $a_i = b_i$, else 1.

  • If interval scale: $\frac{|a_i - b_i|}{R_i}$, where $R_i$ is the feature range.

  • If ordinal: $\frac{rank(a_i) - rank(b_i)}{n - 1}$.

• Text documents: Cosine similarity considers the angle between vectors rather than magnitude, which helps when comparing documents of different lengths.

  • $\text{similarity} = \cos(\theta) = \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\| \times \|\mathbf{b}\|}$

  • $\text{cosine distance} = 1 - \cos(\mathbf{a}, \mathbf{b})$

• Correlation: Used in genetics, treating instances as similar if their feature values are highly correlated regardless of numerical magnitude.

• Dynamic Time Warping (DTW): Used for audio or time series to find the optimal alignment by warping the time domain.

Partition-Based Clustering: K-Means

• K-means divides $n$ instances into $k$ disjoint clusters.

• Goal: Minimize the sum of squared error.

  • $\sum_{i=1}^n \min_{\mathbf{c}_1, \dots, \mathbf{c}_k} Dist(\mathbf{d}_i, \mathbf{c}_i)$

K-Means Algorithm

1. Select $k$ random cluster centroids, $\mathbf{c}_1$ to $\mathbf{c}_k$.

2. Repeat:

   • Calculate the distance of each instance $\mathbf{d}_i$ to each centroid.

   • Assign each instance to the nearest centroid cluster $C_i$.

   • Update each centroid to the average feature values of its assigned instances.

3. Until no instances change clusters (convergence).

K-Means++ Initialization

• Random initialization can lead to local minima (or stationary points).

• K-means++ algorithm:

  1. Select the first centroid $\mathbf{c}_1$ uniform randomly from data instances.

  2. For remaining centroids $C_2$ to $C_k$:

     • Calculate selection weights for each instance: $\frac{Dist(\mathbf{d}_i)^2}{\sum_{p=1}^n Dist(\mathbf{d}_p)^2}$.

     • Choose the next centroid randomly based on this weight distribution (higher probability for points further away).

Selecting K

• Elbow Method: Run k-means multiple times with different $k$. Plot SSE versus $k$. The "elbow" of the graph indicates a good value where SSE decrease rate slows.

• X-Means Algorithm:

  1. Start with a value for $k$.

  2. Apply k-means locally.

  3. Split cluster centroids into two along a random vector.

  4. Accept the new pair if splitting improved the Bayesian Information Criterion (BIC).

K-Means Limitations

• Incorrect clustering occurs with:

  • Different cluster sizes.

  • Different densities (dense areas may be split inappropriately to reduce SSE).

  • Non-spherical shapes.

  • Features on different scales. Descriptive features with larger values (e.g., height in cm vs. feet) will be emphasized and can dominate distance equations.

• Pre-processing involves scaling/normalizing features, encoding categorical data, and eliminating outliers.

• Post-processing includes splitting clusters with high SSE, merging close clusters, or deleting small outlier clusters.

K-Medoid Clustering (PAM)

• Partitioning Around Medoids (PAM) addresses k-means sensitivity to outliers and its inability to use arbitrary distances.

• A medoid is the actual data instance within a partition that has the minimum distance to all other instances in that partition.

• Algorithm:

  1. Specify $k$ and select $k$ instances as medoids.

  2. Assign instances to the nearest medoid.

  3. For each cluster, determine a new medoid (the instance with the lowest cost).

  4. Repeat until medoids stabilize.

Hierarchical Clustering

• Learns a hierarchy of clusters rather than a "flat" structure.

• Agglomerative (Bottom-up): Starts with every instance in its own cluster and merges them sequentially.

• Divisive (Top-down): Starts with all instances in one cluster and splits recursively (more computationally expensive).

Dendrograms

• Dendrograms visualize hierarchical clustering results.

• X-axis shows instances; Y-axis shows a similarity/merging measure.

• Horizontal lines represent merges. The height of the merge is proportional to how similar/dissimilar clusters are.

• Cutting the dendrogram horizontally at a specific height yields a discrete number of clusters.

Linkage Methods (Group-based Proximity)

• Single Link: Distance between clusters is the distance between the closest pair of instances.

  • $d_{12} = \min_{i \in C_1, j \in C_2} d(i, j)$

  • Suffers from "chaining," where elongated, undesirable clusters form because merges are strictly local.

• Complete Link: Distance is the distance between the furthest pair of instances.

  • $d_{12} = \max_{i \in C_1, j \in C_2} d(i, j)$

  • Tends to produce compact spherical clusters but struggles with varying densities.

• Average Link: Distance is the average of differences between all instance pairs across the two clusters.

  • $d_{12} = \frac{1}{|C_1||C_2|} \sum_{i \in C_1, j \in C_2} d(i, j)$

DIANA (Divisive ANAlysis) Algorithm

1. Create one cluster containing all data instances.

2. Identify the instance with the greatest average distance from all other instances in the cluster.

3. Splinter this instance into a new cluster.

4. Move instances from the original cluster to the new cluster if they are on average closer to the new cluster than the old one.

5. Repeat until every instance is isolated.

Cluster Evaluation and Tendency

• Cluster Tendency Analysis: Determining if data contains patterns or is random before clustering.

• Hopkins Statistic: Compares sample distances ($a_i$) and random uniform distribution distances ($r_i$).

  • $Hopkins = \frac{\sum_{i=1}^m r_i}{\sum_{i=1}^m a_i + \sum_{i=1}^m r_i}$

  • Statistic $\approx 1$ indicates clusters; $\approx 0.5$ indicates random data.

• Visual Inspection: Uses an Ordered Dissimilarity Matrix (ODM). Heatmaps of the ODM show structured blocks if data is not random.

Internal Cluster Metrics

• Internal metrics evaluate clustering without ground truth labels, focusing on compactness, separation, and connectivity.

• Dunn Index: Dividies minimum cluster separation by maximum cluster diameter.

  • $\text{Dunn} = \frac{\text{Min Separation}}{\text{Max Diameter}}$

• Silhouette Score ($s_i$): Measures how well instance $d_i$ belongs to its own cluster.

  • $a_i$: Average distance from $d_i$ to other members of its cluster.

  • $b_i$: Lowest average distance from $d_i$ to any other cluster.

  • $s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$

  • Overall score $s = \frac{1}{n} \sum_{i=1}^n s_i$. Small scores indicate points between clusters.

Cluster Validation and Interpretation

• Bootstrap Evaluation/Cluster Stability: Checks if results are consistent across data subsamples.

  1. Draw a subsample with replacement (bootstrapping).

  2. Apply clustering.

  3. Calculate Jaccard similarity coefficient between original and new clusters.

  4. Mean Jaccard coefficient $< 0.6$ suggests an unstable cluster.

• Jaccard Similarity Index: $\frac{\text{instances in both clusters}}{\text{total unique instances in both clusters}}$.

• Summary Statistics: Generating means or counts per cluster to see characterizing features (e.g., "Cluster 1 has low petal length").

• Parallel Coordinate Plots: Each vertical line represents a feature; horizontal lines connect feature values for individual data instances to visualize cluster trends.