Clustering and dimensionality reduction

Clustering aims to group data points so that items in the same group (cluster) are more similar to each other than to those in other groups. It is an unsupervised learning task because no labels are provided; the algorithm discovers structure on its own. Common uses include customer segmentation, image compression, and anomaly detection.

Clustering is unsupervised because it works on data that has no predefined output labels or target values. The algorithm must find patterns and groupings purely from the input features themselves. This contrasts with supervised learning, where each training example comes with a known correct answer.

K is the number of clusters you want the algorithm to partition the data into, and it must be chosen before running the algorithm. K-means then assigns each point to the nearest of K cluster centers (centroids). Choosing a good K is important, since too few or too many clusters can misrepresent the data structure.

K-means alternates between an assignment step and an update step. In the assignment step, each data point is assigned to the cluster whose centroid is nearest. In the update step, each centroid is recomputed as the mean of all points currently assigned to it, and these two steps repeat until the assignments stop changing.

Standard K-means uses Euclidean distance to measure how close points are to centroids. Because Euclidean distance sums squared differences across features, a feature with a large numeric range can dominate the distance and distort clusters. Therefore features are usually standardized (e.g., to zero mean and unit variance) before running K-means.

The elbow method helps choose a good number of clusters K for K-means. You plot the within-cluster sum of squares (inertia) against different K values; as K rises, inertia falls. The 'elbow' point, where the rate of decrease sharply slows, suggests a reasonable K because adding more clusters yields little further improvement.

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
inertias = []
for k in range(1, 10):
    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    inertias.append(km.inertia_)
plt.plot(range(1, 10), inertias, marker='o')

Inertia is the sum of squared distances between each data point and the centroid of the cluster it belongs to. Lower inertia means points are tightly packed around their centroids, indicating more compact clusters. K-means tries to minimize inertia, though it keeps decreasing as K grows, so it cannot alone tell you the best K.

K-means starts from randomly chosen initial centroids, and depending on that random start it can converge to different local minima. To address this, the algorithm is run multiple times with different initializations (controlled by n_init) and the result with the lowest inertia is kept. Smart initialization like k-means++ also reduces poor outcomes.

K-means++ is a smarter way to choose the initial centroids for K-means. Instead of picking all starting centers randomly, it spreads them out by selecting new centers with probability proportional to their squared distance from the nearest existing center. This reduces the chance of poor local minima and usually leads to faster, better convergence.

Agglomerative clustering starts with each data point as its own cluster and then repeatedly merges the two closest clusters. This bottom-up merging continues until all points form a single cluster or a stopping criterion is met. The full sequence of merges can be visualized as a tree called a dendrogram.

A dendrogram is a tree diagram that records the order and distance at which clusters are merged in hierarchical clustering. The height of each merge (the vertical link) represents how dissimilar the joined clusters are. You can 'cut' the dendrogram horizontally at a chosen height to obtain a particular number of clusters.

Linkage defines how the distance between two clusters is measured when deciding which to merge. Single linkage uses the closest pair of points, complete linkage uses the farthest pair, and average linkage uses the mean pairwise distance. The linkage choice strongly affects cluster shapes; for example, single linkage can produce long chained clusters.

Hierarchical clustering does not require you to specify the number of clusters in advance; you can decide K afterward by cutting the dendrogram at different heights. It also produces a full hierarchy of nested groupings, which can reveal structure at multiple scales. However, it is typically more computationally expensive than K-means for large datasets.

DBSCAN can find clusters of arbitrary, non-spherical shapes and can label sparse points as noise/outliers. K-means tends to assume roughly round, equally sized clusters because it relies on distance to a centroid. DBSCAN instead groups points that are densely packed together, so it handles irregular shapes and varying cluster counts well.

eps is the radius defining how close points must be to be considered neighbors, and min_samples is the minimum number of points required within that radius for a point to be a 'core point.' Together they define how dense a region must be to form a cluster. Points that fall in no dense region are labeled as noise.

from sklearn.cluster import DBSCAN
labels = DBSCAN(eps=0.5, min_samples=5).fit_predict(X)
# points labeled -1 are noise

Dimensionality reduction transforms data with many features into fewer features while preserving as much important information as possible. It is useful for reducing computation, removing noise and redundancy, mitigating the curse of dimensionality, and enabling visualization of high-dimensional data in 2D or 3D. It can also improve the performance of downstream models.

The curse of dimensionality refers to problems that arise when data has very many features. As dimensions grow, data points become sparse and distances between points become less meaningful, so methods relying on distance (like clustering or nearest neighbors) degrade. It also requires exponentially more data to cover the space, making learning harder.

PCA finds new axes, called principal components, that are linear combinations of the original features and are ordered by how much variance they capture. By keeping only the first few components, which hold most of the variance, you reduce dimensionality while retaining most of the data's spread. The components are mutually orthogonal (uncorrelated).

from sklearn.decomposition import PCA
pca = PCA(n_components=2)
X_reduced = pca.fit_transform(X)

The first principal component is the direction in feature space along which the data varies the most, that is, it captures the largest possible variance. Projecting data onto this single axis retains more information than any other single direction. Each subsequent component captures the most remaining variance while being orthogonal to the previous ones.

The explained variance ratio of a principal component is the fraction of the dataset's total variance that the component captures. By summing these ratios over the components you keep, you can see how much of the original information is retained. This helps you decide how many components are enough, for example keeping enough to retain 95% of the variance.

pca = PCA().fit(X)
print(pca.explained_variance_ratio_.cumsum())

PCA is driven by variance, so features measured on large scales would dominate the principal components regardless of their true importance. Standardizing each feature to a comparable scale (often zero mean and unit variance) ensures every feature contributes fairly. Without standardization, PCA results can be misleading and reflect units rather than structure.

PCA is a linear technique because each principal component is a linear combination of the original features. A consequence is that PCA may fail to capture complex non-linear structure, such as data lying on a curved manifold. For such cases, non-linear methods like t-SNE, UMAP, or kernel PCA are often more effective.

t-SNE (t-distributed Stochastic Neighbor Embedding) is a non-linear technique used mainly to visualize high-dimensional data in two or three dimensions. It tries to keep similar points close together in the low-dimensional map, revealing clusters and local structure. It is great for visualization but not typically used as a preprocessing step for other models.

t-SNE focuses on preserving local neighborhoods, not global distances, so the spacing and sizes of clusters in the plot can be misleading. Two clusters appearing far apart are not necessarily more different than two that appear close. Also, results depend on the perplexity setting and random initialization, so plots can vary between runs.

The silhouette score measures how well each point fits its own cluster compared to the nearest other cluster, combining cohesion and separation. It ranges from -1 to +1: values near +1 mean well-matched clusters, near 0 mean overlapping clusters, and negative values suggest points may be in the wrong cluster. The average silhouette helps compare clustering quality across different K.

from sklearn.metrics import silhouette_score
score = silhouette_score(X, labels)

A centroid is the mean position of all points in a cluster and may not coincide with any actual data point. A medoid is an actual data point in the cluster that is most centrally located (minimizing total distance to other members). Algorithms like K-medoids use medoids, which makes them more robust to outliers than K-means.

PCA can produce at most min(number of samples, number of features) principal components (and at most one fewer than the number of samples once the data is mean-centered). You then choose to keep fewer components than the original number of features to reduce dimensionality. The kept components are ranked by variance, so you discard the lowest-variance directions to lose the least information.

Distance-based algorithms like K-means and DBSCAN compute distances between points, so features on larger numeric scales contribute disproportionately to those distances. Scaling features to comparable ranges (standardization or normalization) ensures each feature influences the clustering fairly. Skipping scaling can cause clusters to be driven by an arbitrary unit choice rather than real structure.

K-means struggles with clusters of very different sizes or densities because it minimizes squared distance to centroids, which biases it toward roughly equal, spherical clusters. A small dense cluster near a large spread-out one can be split or absorbed incorrectly. Density-based methods like DBSCAN often handle such cases better.

Orthogonal means the principal components are perpendicular to one another in feature space, which makes them mutually uncorrelated. As a result, each component captures a distinct, non-overlapping portion of the data's variance. This decorrelation is one reason PCA is useful for removing redundancy among correlated features.

Reducing dimensions first (for example with PCA) can remove noise and redundant features, making distance measurements more meaningful and clustering faster. In high dimensions, distances tend to become similar for all point pairs, weakening clustering; fewer informative dimensions can sharpen the structure. However, over-reducing can discard useful information, so the number of components should be chosen carefully.

A common example is customer segmentation, where a business groups customers by purchasing behavior to target marketing more effectively. Other examples include grouping similar documents or news articles, compressing images by clustering pixel colors, and detecting unusual network activity as anomalies. In each case, the algorithm groups similar items without predefined labels.

fit_predict runs the clustering algorithm on the data and returns the cluster label assigned to each sample in one step. It combines fitting the model (learning the clusters) with predicting the membership of each point. For example, KMeans.fit_predict(X) returns an array where each element is the cluster index of the corresponding row in X.

from sklearn.cluster import KMeans
labels = KMeans(n_clusters=3, n_init=10, random_state=0).fit_predict(X)

For visualization, the goal is usually to map data to 2D or 3D so humans can see patterns, and methods like t-SNE or UMAP that preserve local neighborhoods are popular. For modeling, the goal is to keep enough informative, often interpretable and reproducible components to feed into another algorithm, so PCA is commonly preferred. Visualization methods can distort distances and are often non-deterministic, making them less suitable as model inputs.