Cluster Analysis - Clusters and Clusterings

Clusters and Clusterings

The notion of a "cluster" varies between algorithms and is one of the many decisions to take when choosing the appropriate algorithm for a particular problem. At first the terminology of a cluster seems obvious: a group of data objects. However, the clusters found by different algorithms vary significantly in their properties, and understanding these "cluster models" is key to understanding the differences between the various algorithms. Typical cluster models include:

• Connectivity models: for example hierarchical clustering builds models based on distance connectivity.
• Centroid models: for example the k-means algorithm represents each cluster by a single mean vector.
• Distribution models: clusters are modeled using statistical distributions, such as multivariate normal distributions used by the Expectation-maximization algorithm.
• Density models: for example DBSCAN and OPTICS defines clusters as connected dense regions in the data space.
• Subspace models: in Biclustering (also known as Co-clustering or two-mode-clustering), clusters are modeled with both cluster members and relevant attributes.
• Group models: some algorithms (unfortunately) do not provide a refined model for their results and just provide the grouping information.
• Graph-based models: a clique, i.e., a subset of nodes in a graph such that every two nodes in the subset are connected by an edge can be considered as a prototypical form of cluster. Relaxations of the complete connectivity requirement (a fraction of the edges can be missing) are known as quasi-cliques.

A "clustering" is essentially a set of such clusters, usually containing all objects in the data set. Additionally, it may specify the relationship of the clusters to each other, for example a hierarchy of clusters embedded in each other. Clusterings can be roughly distinguished in:

• 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 (e.g. a likelihood of belonging to the cluster)

There are also finer distinctions possible, for example:

• strict partitioning clustering: here each object belongs to exactly one cluster
• strict partitioning clustering with outliers: objects can also belong to no cluster, and are considered outliers.
• overlapping clustering (also: alternative clustering, multi-view clustering): while usually a hard clustering, objects may belong to more than one cluster.
• hierarchical clustering: objects that belong to a child cluster also belong to the parent cluster
• subspace clustering: while an overlapping clustering, within a uniquely defined subspace, clusters are not expected to overlap.