Unit 7: Unsupervised Learning - Subjective Questions

Clustering is an unsupervised learning technique that divides unlabeled data into groups called clusters. Objects within the same cluster should be more similar to one another than to objects in other clusters.

Role in unsupervised learning:

• Discovers hidden structures without predefined class labels.
• Summarizes large datasets through representative groups.
• Identifies unusual observations or outliers.
• Supports exploratory data analysis and feature engineering.

Common applications include customer segmentation, document grouping, image segmentation, anomaly detection, and biological taxonomy.

Hard clustering:

• Assigns every observation to exactly one cluster.
• Membership is binary: an object either belongs or does not belong to a cluster.
• K-Means, K-Modes, and K-Median are examples.

Soft clustering:

• Assigns each observation a degree or probability of membership in multiple clusters.
• Membership values generally satisfy and .
• Fuzzy C-Means and Gaussian mixture models are examples.

For a customer who purchases both sports and electronic products, hard clustering places the customer in one segment, whereas soft clustering may assign partial membership to both segments.

A typical clustering workflow includes:

1. Define the objective: Decide what useful groups should represent.
2. Select features: Retain variables relevant to the clustering task.
3. Clean the data: Handle missing values, duplicates, and invalid observations.
4. Transform features: Encode categorical variables and scale numerical variables when required.
5. Select a similarity measure: Examples include Euclidean, Manhattan, or matching dissimilarity.
6. Choose an algorithm and hyperparameters: For example, choose K-Means and the value of .
7. Fit the model: Generate cluster assignments and representatives.
8. Evaluate the result: Use internal, external, and stability measures.
9. Interpret clusters: Profile each cluster and verify that the groups are meaningful for the application.

K-Means minimizes the within-cluster sum of squared errors, also called inertia:

where:

• is the number of clusters.
• is the set of observations assigned to cluster .
• is the centroid of cluster .
• is the squared Euclidean distance from an observation to its centroid.

Minimizing produces clusters that are compact around their centroids. The objective is non-convex when assignments and centroids are optimized together, so the algorithm may converge to a local rather than global optimum.

The K-Means algorithm proceeds as follows:

1. Select the required number of clusters .
2. Initialize centroids .
3. Assignment step: Assign each observation to its nearest centroid:
   
4. Update step: Recalculate each centroid as the arithmetic mean of its assigned observations:
   
5. Repeat the assignment and update steps.

The algorithm stops when cluster assignments no longer change, centroid movement falls below a tolerance, improvement in the objective is negligible, or a maximum number of iterations is reached. Each iteration does not increase the objective, so the procedure eventually converges.

For a fixed one-dimensional cluster containing observations, define its squared-error objective as:

Differentiate with respect to :

Set the derivative equal to zero:

Therefore:

The second derivative is , confirming a minimum. In multiple dimensions, the objective separates coordinate-wise, so the optimal centroid is the vector of coordinate means.

K-Means can produce different results for different initial centroids because its objective is non-convex. Poor initialization may cause:

• Convergence to an inferior local optimum.
• Unbalanced or empty clusters.
• Slow convergence.
• Unstable results across runs.

K-Means++ initialization:

1. Select the first centroid uniformly at random.
2. For every observation , compute , its distance to the nearest selected centroid.
3. Select the next centroid with probability proportional to .
4. Repeat until centroids have been selected.
5. Run ordinary K-Means.

K-Means++ tends to spread initial centroids across the data and generally improves convergence and clustering quality. Multiple random restarts can provide additional robustness.

Important methods for selecting include:

• Elbow method: Plot within-cluster sum of squares against and locate the point after which improvement diminishes sharply.
• Silhouette analysis: Select a producing a high average silhouette coefficient.
• Gap statistic: Compare observed compactness with that expected under a reference distribution.
• Calinski-Harabasz index: Prefer values of with high between-cluster separation relative to within-cluster dispersion.
• Davies-Bouldin index: Prefer the value of with a lower index.
• Stability analysis: Repeat clustering on perturbed samples and choose a stable solution.
• Domain knowledge: Ensure that the selected number of clusters is meaningful and actionable.

No measure should be used blindly; statistical scores, stability, and interpretability should be considered together.

K-Means works best when clusters are approximately spherical, compact, similarly sized, similarly dense, and separable using Euclidean distance.

Major limitations:

• must be specified in advance.
• It is sensitive to initial centroid selection.
• Outliers can strongly shift arithmetic means.
• It may fail on non-convex clusters.
• It can divide clusters of different sizes or densities incorrectly.
• It is sensitive to differences in feature scale.
• It is designed for numerical data because computing a mean for nominal categories is not meaningful.
• Irrelevant or highly correlated features can distort distances.

Possible remedies include scaling features, removing or treating outliers, performing multiple restarts, selecting robust features, or using algorithms better suited to the data geometry.

Distance-based clustering is affected by the numerical magnitude of each feature. A feature measured on a large scale can dominate the distance even when it is not more important.

For example, if annual income ranges from to while age ranges from to , income may dominate Euclidean or Manhattan distance.

Common transformations include:

• Standardization:
• Min-max scaling:
• Robust scaling: Center by the median and scale using the interquartile range.

The chosen transformation should reflect domain meaning. Scaling is unnecessary only when features already have comparable, intentionally meaningful units.

K-Modes is a partition-based clustering algorithm designed for categorical variables. It replaces the two numerical-data components of K-Means:

• The arithmetic mean is replaced by the mode, the most frequent category for each feature.
• Squared Euclidean distance is replaced by a categorical dissimilarity measure.

Its basic procedure is:

1. Initialize modes.
2. Assign each observation to its nearest mode.
3. Update every cluster mode using the most frequent value of each attribute.
4. Repeat until assignments or modes stop changing.

K-Modes is suitable for categorical data because a mode is a valid category, whereas the arithmetic mean of labels such as red, green, and blue is undefined.

For two categorical objects and with attributes, simple matching dissimilarity is:

where:

Consider:

The first and third attributes differ, while the second matches. Therefore, .

A weighted form can assign different importance to attributes or account for category frequencies. However, basic matching dissimilarity treats every mismatch equally.

For each cluster, K-Modes computes a representative vector by selecting the most frequent category independently for every attribute.

For cluster , the representative value for attribute is:

where is when the condition is true and otherwise.

For example, if a cluster has color values red, red, blue, and red, its color mode is red.

When two or more categories have the same maximum frequency, a tie may be resolved by:

• Retaining the previous mode if it is tied.
• Selecting one category deterministically.
• Choosing randomly among tied categories.
• Using global category frequency as a secondary rule.

A consistent tie-breaking rule improves reproducibility.

K-Median partitions numerical observations into clusters and represents each cluster using a component-wise median. A common objective is the sum of Manhattan distances:

where is the component-wise median of cluster .

By contrast, K-Means minimizes squared Euclidean distances:

K-Median procedure:

1. Initialize representatives.
2. Assign observations to the nearest representative using Manhattan distance.
3. Replace each representative by the coordinate-wise median.
4. Repeat until convergence.

Because medians are less influenced by extreme values than means, K-Median is generally more robust to outliers.

All three are iterative partitioning algorithms that require the number of clusters , alternate between assignment and representative-update steps, and may converge to local optima. The correct choice depends mainly on the variable types, desired distance measure, cluster geometry, and robustness requirements.

The within-cluster sum of squares is defined as:

It measures cluster compactness:

• A low value means observations are close to their assigned centroids.
• A high value indicates dispersed clusters.
• It is the objective directly minimized by K-Means.

WCSS always stays the same or decreases as increases, reaching zero when every distinct observation can become its own cluster. Therefore, it should not be used alone to select . The elbow method examines the trade-off between a lower WCSS and increased model complexity.

For observation , let:

• be its average distance to other observations in its own cluster.
• be the smallest average distance from it to observations in any other cluster.

The silhouette coefficient is:

Its range is :

• A value near indicates that the observation is compactly placed in its own cluster and separated from others.
• A value near indicates overlapping clusters or a boundary observation.
• A negative value suggests that the observation may have been assigned to the wrong cluster.

The average silhouette over all observations provides an overall clustering score. It can also be examined cluster by cluster to detect weak groups.

The Davies-Bouldin index evaluates each cluster using its similarity to the most similar competing cluster. One form is:

where:

• is the within-cluster scatter of cluster .
• is the distance between representatives of clusters and .

A low value indicates compact clusters whose representatives are far apart. Therefore, lower Davies-Bouldin values are preferred.

Advantages include not requiring true class labels and combining compactness with separation. Limitations are dependence on the selected distance measure and a tendency to favor particular cluster shapes and partitions.

The Calinski-Harabasz index, also called the variance ratio criterion, is:

where:

• is between-cluster dispersion.
• is within-cluster dispersion.
• is the number of clusters.
• is the number of observations.

The numerator measures how widely cluster representatives are separated, while the denominator measures how dispersed observations are within clusters. The degrees-of-freedom terms adjust these quantities for and sample size.

A higher value usually indicates compact, well-separated clusters. The index is useful for comparing different values of on the same dataset, but it does not guarantee that clusters are meaningful or stable.

Internal evaluation uses only features and cluster assignments:

• WCSS or inertia measures compactness.
• Silhouette coefficient measures compactness and separation.
• Davies-Bouldin and Calinski-Harabasz indices compare cluster quality.

External evaluation compares clusters with known reference labels that were not used to train the model:

• Adjusted Rand Index measures agreement between pairs of assignments while correcting for chance.
• Normalized Mutual Information measures shared information between cluster and class labels.
• Purity measures the dominant reference class in each cluster, although it tends to increase with more clusters.

Stability evaluation repeats clustering after resampling observations, perturbing data, changing initialization, or varying hyperparameters. Results are compared using assignment agreement or co-clustering frequencies.

A reliable assessment combines these methods with domain interpretation because a geometrically strong partition may not be useful, and reference classes may not match the natural structure of the data.