cluster analysis

cluster analysis, in statistics, set of tools and algorithms that is used to classify different objects into groups in such a way that the similarity between two objects is maximal if they belong to the same group and minimal otherwise. In biology, cluster analysis is an essential tool for taxonomy (the classification of living and extinct organisms). In clinical medicine, it can be used to identify patients who have diseases with a common cause, patients who should receive the same treatment, or patients who should have the same level of response to treatment. In epidemiology, cluster analysis has many uses, such as finding meaningful conglomerates of regions, communities, or neighbourhoods with similar epidemiological profiles when many variables are involved and natural groupings do not exist. In general, whenever one needs to classify large amounts of information into a small number of meaningful categories, cluster analysis may be useful.

Researchers are often confronted with the task of sorting observed data into meaningful structures. Cluster analysis is an inductive exploratory technique in the sense that it uncovers structures without explaining the reasons for their existence. It is a hypothesis-generating, rather than a hypothesis-testing, technique. Unlike discriminant analysis, where objects are assigned to preexisting groups on the basis of statistical rules of allocation, cluster analysis generates the groups or discovers a hidden structure of groups within the data.

Classification of methods

In a first broad approach, cluster analysis techniques may be classified as hierarchical, if the resultant grouping has an increasing number of nested classes that resemble a phylogenetic classification, or nonhierarchical, if the results are expressed as a unique partition of the whole set of objects.

Hierarchical algorithms can be divisive or agglomerative. A divisive method begins with all cases in one cluster. That cluster is gradually broken down into smaller and smaller clusters. Agglomerative techniques usually start with single-member clusters that are successively fused until one large cluster is formed. In the initial step, the two objects with the lowest distance (or highest similarity) are combined into a cluster. In the next step, the object with the lowest distance to either of the first two is identified and studied. If it is closer to a fourth object than to either of the first two, the third and fourth objects become the second two-case cluster; otherwise, the third object is included in the first cluster. The process is repeated, adding cases to existing clusters, creating new clusters, or combining those that have emerged until each object has been examined and allocated to one cluster or stands as one separate cluster by itself. At each step of the process, a different partition is formed that is nested in the partition generated in the following step. Usually, the researcher chooses the partition that turns out to be the most meaningful for a particular application.

Distance and similarity are key concepts in the context of cluster analysis. Most algorithms, particularly those yielding hierarchical partitions, start with a distance-or-similarity matrix. The cell entries of this matrix are distances or similarities between pairs of objects. There are many types of distances, of which the most common is the Euclidean distance. The Euclidean distance between any two objects is the square root of the sum of the squares of the differences between all the coordinates of the vectors that define each object. It can be used for variables measured at an interval scale. When two or more variables are used to calculate the distance, the variable with the larger magnitude will dominate. To avoid that, it is common practice to first standardize all variables.

The choice of a distance type is crucial for all hierarchical clustering algorithms and depends on the nature of the variables and the expected form of the clusters. For example, the Euclidean distance tends to yield spherical clusters. Other commonly used distances include the Manhattan distance, the Chebyshev distance, the power distance, and the percent disagreement. The Manhattan distance is defined as the average distance across variables. In most cases, it yields results similar to the simple Euclidean distance. However, the effect of single large differences (outliers) is dampened (since they are not squared). The Chebyshev distance may be appropriate when objects that differ in just one variable should be considered different. The power distance is used when it is important to increase or decrease the progressive weight that is assigned to variables on which the respective objects are very different. The power distance is controlled by two user-defined parameters, r and p. Parameter p controls the progressive weight that is placed on differences on individual variables, while parameter r controls the progressive weight that is placed on larger differences between objects. If r and p are equal to 2, then that distance is equal to the Euclidean distance. The percent disagreement may be used when the data consist of categorical variables.

Linkage rules

When clusters are composed of a single object, the distance between them can be calculated with any of the aforementioned distances. However, when clusters are formed by two or more objects, rules have to be defined to calculate those distances.

The distance between two clusters may be defined as the distance between the two closest objects in the two clusters. Known as the nearest neighbour rule, this approach will string objects together and tends to form chainlike clusters.

Other popular linkage rules are the pair-group average and the pair-group centroid. The first of those rules is defined as the average distance between all pairs of objects in the two different clusters. That method tends to form natural distinct clumps of objects. The pair-group centroid is the distance between the centroids, or centres of gravity, of the clusters.

The most frequently used nonhierarchical clustering technique is the k-means algorithm, which is inspired by the principles of analysis of variance. In fact, it may be thought of as an analysis of variance in reverse. If the number of clusters is fixed as k, the algorithm will start with k random clusters and then move objects between them with the goals of minimizing variability within clusters and maximizing variability between clusters.