Clustering

Clustering, also known as cluster analysis, is a data analysis technique that partitions a set of objects into groups, or clusters, such that objects within the same cluster are more similar to each other than to objects in other clusters, according to a specific similarity or distance measure defined by the analyst. It is a main task of exploratory data analysis and a common technique for statistical data analysis, used in fields including pattern recognition, image analysis, information retrieval, bioinformatics, data compression, computer graphics, and machine learning. As an unsupervised learning method, clustering does not rely on labeled data; instead, it discovers inherent structures and groupings in the data without prior knowledge of class labels.

The term "clustering" encompasses a family of algorithms and tasks rather than a single specific algorithm. Different algorithms vary significantly in their understanding of what constitutes a cluster and how to efficiently identify clusters. Popular notions of clusters include groups with small distances between members, dense areas of the data space, intervals, or particular statistical distributions. Consequently, clustering can be formulated as a multi-objective optimization problem, and the appropriate algorithm and parameter settings (such as the distance function, density threshold, or number of expected clusters) depend on the individual dataset and the intended use of the results. Cluster analysis is not an automatic task but an iterative process of knowledge discovery or interactive multi-objective optimization, often requiring trial and error to adjust data preprocessing and model parameters until the result achieves desired properties.

Besides the term clustering, several similar terms exist, including automatic classification, numerical taxonomy, botryology (from Greek βότρυς 'grape'), typological analysis, and community detection. The subtle differences often lie in the use of the results: in data mining, the resulting groups are the matter of interest, whereas in automatic classification, the resulting discriminative power is of interest.

History

Cluster analysis originated in anthropology with the work of Driver and Kroeber in 1932. It was introduced to psychology by Joseph Zubin in 1938 and Robert Tryon in 1939, and famously used by Raymond Cattell beginning in 1943 for trait theory classification in personality psychology. Since then, clustering has evolved into a fundamental tool across numerous scientific disciplines, with hundreds of published algorithms developed over the decades.

Cluster Models

The notion of a "cluster" cannot be precisely defined, which is a key reason for the diversity of clustering algorithms. There is a common denominator: a group of data objects. However, different researchers employ different cluster models, and each model can be implemented by various algorithms. Understanding these cluster models is essential to understanding the differences between algorithms. Typical cluster models include:

• Connectivity models: Hierarchical clustering builds models based on distance connectivity, where clusters are formed by linking objects based on proximity.
• Centroid models: The k-means algorithm represents each cluster by a single mean vector, or centroid, and assigns objects to the nearest centroid.
• Distribution models: Clusters are modeled using statistical distributions, such as multivariate normal distributions used by the expectation-maximization (EM) algorithm.
• Density models: Algorithms like DBSCAN, OPTICS, and HDBSCAN define clusters as connected dense regions in the data space, separated by sparse areas.
• Subspace models: In biclustering (also known as co-clustering or two-mode clustering), clusters are modeled with both cluster members and relevant attributes, allowing clusters to exist in different subspaces of the data.
• Group models: Some algorithms do not provide a refined model for their results and simply provide the grouping information.
• Graph-based models: A clique, a subset of nodes in a graph where every two nodes are connected by an edge, can be considered a prototypical form of cluster. Relaxations of the complete connectivity requirement, known as quasi-cliques, are used in algorithms like the HCS clustering algorithm.
• Signed graph models: In signed graphs, every path has a sign from the product of the signs on the edges. Under balance theory assumptions, edges may change sign, resulting in a bifurcated graph. The weaker "clusterability axiom" (no cycle has exactly one negative edge) yields results with more than two clusters or subgraphs with only positive edges.
• Neural models: The most well-known unsupervised neural network is the self-organizing map, and these models can usually be characterized as similar to one or more of the above models, including subspace models when neural networks implement forms of Principal Component Analysis or Independent Component Analysis.

Types of Clustering

A "clustering" is essentially a set of clusters, usually containing all objects in the dataset. It may also specify the relationship of clusters to each other, such as a hierarchy of clusters embedded in each other. Clusterings can be roughly distinguished as:

• Hard clustering: Each object belongs to a cluster or not.
• Soft clustering (also fuzzy clustering): Each object belongs to each cluster to a certain degree, such as a likelihood of belonging.

Finer distinctions include:

• Strict partitioning clustering: Each object belongs to exactly one cluster.
• Strict partitioning clustering with outliers: Objects can also belong to no cluster, in which case they are considered outliers.
• Overlapping clustering (also alternative clustering, multi-view clustering): Objects may belong to more than one cluster, usually involving hard clusters.
• Hierarchical clustering: Objects that belong to a child cluster also belong to the parent cluster, creating a tree-like structure.
• Subspace clustering: While an overlapping clustering, within a uniquely defined subspace, clusters are not expected to overlap.

Algorithms

Clustering algorithms can be categorized based on their cluster model. There are possibly over 100 published clustering algorithms, and not all provide models for their clusters, making categorization difficult. There is no objectively "correct" clustering algorithm; as noted, "clustering is in the eye of the beholder." In fact, an axiomatic approach demonstrates that it is impossible for any clustering method to meet three fundamental properties simultaneously: scale invariance (results remain unchanged under proportional scaling of distances), richness (all possible partitions of the data can be achieved), and consistency between distances and the clustering structure. The most appropriate algorithm for a particular problem often needs to be chosen experimentally, unless there is a mathematical reason to prefer one cluster model over another.

Prominent clustering algorithms include:

• K-means: A centroid-based algorithm that partitions data into k clusters by minimizing the within-cluster sum of squares. It is simple and efficient but requires specifying the number of clusters and is sensitive to outliers.
• Hierarchical clustering: Builds a hierarchy of clusters either agglomeratively (bottom-up) or divisively (top-down). It does not require a predefined number of clusters and produces a dendrogram.
• DBSCAN: A density-based algorithm that identifies clusters as dense regions separated by sparse areas. It can find arbitrarily shaped clusters and handle outliers, but requires tuning parameters like epsilon and minimum points.
• Expectation-Maximization (EM): A distribution-based algorithm that models clusters as Gaussian distributions and iteratively estimates parameters to maximize likelihood.
• OPTICS: An extension of DBSCAN that produces a cluster ordering, making it more robust to varying densities.
• Self-organizing maps (SOM): A neural network model that maps high-dimensional data to a low-dimensional grid, preserving topological relationships.

Applications

Clustering is widely used across many domains. In pattern recognition, it helps identify groups in data for classification tasks. In image analysis, it is used for image segmentation and object detection. In information retrieval, clustering organizes documents by topic for search and recommendation. In bioinformatics, it groups genes or proteins with similar expression patterns. In data compression, clustering reduces data size by representing groups with prototypes. In computer graphics, it aids in color quantization and mesh simplification. In artificial intelligence, clustering is a core technique for unsupervised learning, enabling systems to discover patterns without labeled examples.

Challenges and Considerations

Clustering presents several challenges. Determining the optimal number of clusters is often difficult and may require domain knowledge or heuristics. The choice of distance metric significantly affects results; common metrics include Euclidean, Manhattan, and cosine similarity. High-dimensional data can suffer from the curse of dimensionality, where distances become less meaningful. Clustering results are sensitive to initialization and parameter settings, and there is no universal solution. Additionally, the iterative nature of clustering means that results should be validated using internal or external evaluation metrics, such as silhouette score or Rand index, to ensure they meet the desired properties.

Related Concepts

Clustering is closely related to other unsupervised learning techniques, such as dimensionality reduction and anomaly detection. It is often used in conjunction with data augmentation to generate synthetic samples or in preprocessing for supervised learning. In the context of deep learning, clustering can be integrated into neural network architectures for representation learning. The principles of clustering also underpin community detection in network analysis and market segmentation in business analytics.