Clustering analysis is a method of forming clusters based on the similarity or relationship between each data, such that the data in a cluster are similar and the data in other clusters are different. At this time, the higher the similarity within a cluster, the better, and the differences between clusters should be as different as possible. However, it is generally difficult to define a cluster, and it is unclear how many clusters to divide into. Many types of clustering analysis models have been developed to apply to various types of data, but there is hardly a single clustering analysis model that is satisfactory for all types of applications. Each clustering analysis model can show different performance when the data dimension is low or high, when the data size is small or large, when the data density is small or high when there are few or many outliers or extreme points, and when the data properties are discrete or continuous. In general, after applying several clustering analysis models, an appropriate model is selected based on the analyst's judgment.

In this chapter, we first introduce the hierarchical clustering model, which has been used for a long time. Then, we introduce the \(\small K\)-means clustering, which is widely used.

Clustering analysis models can also be divided into exclusive clustering analysis, where one data must belong to one cluster, and inclusive clustering analysis, where one data can belong to multiple clusters. The \(\small K\)-means clustering model is an exclusive clustering analysis, and the fuzzy clustering model and the mixed distribution clustering model are inclusive clustering analyses. The fuzzy cluster and mixed distribution clustering models indicate the weight or probability that each data belongs to each cluster as a number between 0 and 1. However, since the inclusive clustering analysis model generally classifies one data into a group with a higher probability, the final data cluster can be an exclusive clustering analysis.

In addition, clustering analysis models are also classified into prototype-based models, density-based models, and graph-based models. The prototype-based model determines the form of the cluster based on how close the data is to the prototype of each cluster, which has been determined in advance. The \(\small K\)-means clustering model is a prototype-based model. In the case of continuous data, the cluster average is usually set as the prototype, and in the case of discrete data, the mode of the cluster is used as the prototype. The density-based model is a method that considers an area where data is distributed as a cluster when the density is very high. The graph-based model is a method that considers each data as a node, connects the nodes based on a set distance, and then determines the data corresponding to the connected nodes as a cluster. The Kohonen clustering model belongs to this.

Various measures can be considered for evaluating these factors, such as the response within a cluster, cohesion and separation between clusters. In the case of clustering models that utilize distance or similarity between data, the cohesion of cluster \(\small G_{i}\) and the separation between two clusters \(\small G_{i}\) and \(\small G_{j}\) are defined as follows. Here, \(\small d(\boldsymbol x, \boldsymbol y)\) is the distance between data \(\boldsymbol x\) and data \(\boldsymbol y\). $$ \small \begin{align} \text{Cohesion} (G_{i}) &= \sum_{\boldsymbol x , \; \boldsymbol y \; \in \; G_{i}} \; d(\boldsymbol x, \boldsymbol y) \\ \text{Separation} (G_{i} , G_{j}) &= \sum_{\boldsymbol x \; \in \; G_{i}} \; \sum_{\boldsymbol x \; \in \; G_{j}} \; d(\boldsymbol x, \boldsymbol y) \end{align} $$

In the clustering model based on the prototype, the cohesion and separation are defined as follows when the centroids of clusters \(\small G_{i}\) and clusters \(\small G_{j}\) are \(\small \boldsymbol c_{i}\) and \(\small \boldsymbol c_{j}\), respectively. $$ \small \begin{align} \text{Cohesion} (G_{i}) &= \sum_{\boldsymbol x \; \in \; G_{i}} \; d(\boldsymbol x, \boldsymbol c_{i} ) \\ \text{Separation} (G_{i} , G_{j}) &= d(\boldsymbol c_{i}, \boldsymbol c_{j}) \end{align} $$ In the case of cohesion, if the distance \(d(\boldsymbol x, \boldsymbol c_{i} )\) between the data \(\boldsymbol x \) of cluster and the center \(\boldsymbol c_{i} \) is defined as the squared Euclidean distance, the cohesion of cluster \(\small G_{i}\) becomes the sum of squared error (SSE).

When there are \(\small K\) clusters and the number of data in cluster \(\small G_{i}\) is \(\small n_{i}\), the cohesion of the entire clustering model is calculated as the weighted sum of the cohesion of each cluster, and the weight value \(\small w_{i}\) can be \(\small n_{i}\), \(\small \frac{1}{n_{i}}\), or other various measures ​​depending on the situation. $$ \small \text{Cohesion of total model} = \sum_{i=1}^{K} \; w_{i} \times (\text{Cohesion of cluster} \; G_{i} ) $$

The result of hierarchical clustering is often displayed in a dendrogram similar to a tree, as shown on <Figure 8.2.1>, which shows the relationship between clusters and subclusters and the order in which clusters are formed. The subset plot displays the entire data as one set, as shown in <Figure 8.2.2>, and displays each hierarchical cluster as a subset plot within this set.

\( \small \qquad ESS_{i} = \sum_{j=1}^{n_{i}} \; \sum_{k=1}^{m} \; (x_{ijk} - \overline x_{ik} )^2 \)

\( \small \qquad ESS = \sum_{i=1}^{K} \; ESS_{i} = \sum_{i=1}^{K} \; \sum_{j=1}^{n_{i}} \; \sum_{k=1}^{m} \; (x_{ijk} - \overline x_{ik} )^2 \)

First, each data itself forms a cluster, then, since \(ESS_{i}\) for all i, \(ESS\) = 0. At each stage of creating a cluster, the merging of all possible pairs of clusters is considered, and the clusters are merged to create a new cluster so that the increment of \(ESS\) (information loss) due to the merging of two clusters is minimized. The increment of \(ESS\) that occurs when grouping two clusters \(\small G_{i}\) and \(\small G_{j}\), whose sizes are \(n_{i}\) and \(n_{j}\) respectively, is as follows, and the Ward linkage method defines this increment as the distance between the two clusters \(\small G_{i}\) and \(\small G_{j}\). $$ \small \qquad d(G_{i}, G_{j}) = \frac{|| \boldsymbol c_{i} - \boldsymbol c_{j} ||^2 }{\frac{1}{n_{i}} + \frac{1}{n_{j}} } $$ Here, \( \boldsymbol c_{i}\) and \( \boldsymbol c_{j} \) are the averages of two clusters \(\small G_{i}\) and \(\small G_{j}\) respectively. This result differs from the centroid linkage method because the Ward linkage weights the distance between clusters means when calculating the distance between clusters. The Ward linkage method tends to merge clusters of similar size.

An example of R commands for a Hierarchical clustering with 30 iris data is as follows.

> library(stats)	copy r command
> iris <- read.csv('iris30.csv', header=T, as.is=FALSE)	copy r command
> attach(iris)	copy r command
# select Sepal.Length, Sepal.Width, Petal.Length, Petal.Width from iris data > iris4 <- iris[, c(2,3, 4, 5)]	copy r command
# calculate distance matrix using squared Euclid distance > dist(iris4, method = 'euclidean')	copy r command
> hclustIris4 <-hclust(distIris4, method = "ward.D")	copy r command
> hclustIris4 Call: hclust(d = distIris4, method = "ward.D") Cluster method : ward.D Distance : euclidean Number of objects: 30	copy r command
# plot hierarchical clusters > plot(hclustIris4) <Figure 8.2.8> Hierarchical clustering dendrogram using R	copy r command

The clustering model requires an appropriate distance measure between data and a cluster. \(\small K\)-means clustering model first determines the number of clusters \(\small K\) and selects the initial center of each cluster. Then, each data is classified into a cluster with the closest cluster center, and the center of each cluster is recalculated. We can use the various distance measures studied in Chapter 2, and in the case of continuous data, the Euclidean distance is generally used. This method is repeated until there is no change in the cluster center. The basic procedure of the \(\small K\)-means clustering model is summarized as follows.

Suppose there are \(m\) variables \(\small \boldsymbol x = (x_{1}, x_{2}, ... , x_{m}) \) and \(n\) number of data observed for these variables. Let the \(\small K\) clusters be \(\small G_{1}, G_{2}, ... , G_{K}\), the number of data observed in each cluster be \(\small n_{1}, n_{2}, ... , n_{K}\), and the mean of each cluster be \(\small \boldsymbol c_{1}, \boldsymbol c_{2}, ... , \boldsymbol c_{K} \) as follows. $$ \boldsymbol c_{i} = \frac{1}{n_{i}} \; \sum_{\boldsymbol x \in G_{i}} \; \boldsymbol x $$ If \(\small d(\boldsymbol c_{i}, \boldsymbol x)\) is the distance between the center \(\small \boldsymbol c_{i}\) of cluster \(\small G_{i}\) and the data \(\small \boldsymbol x\), the measure of cluster performance can be defined as the sum of distances from all data to each center. $$ \text{(Performance measure of clustering)} = \sum_{i=1}^{K} \; \sum_{\boldsymbol x \in G_{i}} \; d( \boldsymbol c_{i} , \boldsymbol x) $$ When using the squared Euclid distance as a distance measure, the \(\small \boldsymbol c_{i}\) that minimizes this performance measure of clustering can be shown to be the mean of the cluster. Here, let us prove that \(\small \boldsymbol c_{i}\) is the cluster's mean when the data is only one-dimensional. The performance measure of clustering is the following within sum of squares (WSS) in the case of the squared Euclid distance. $$ \text{WSS} = \sum_{i=1}^{K} \; \sum_{x \in G_{i}} \; (c_{i} - x)^2 $$ In order to find \(\small c_{1}, c_{2}, ... , c_{K} \) that minimizes this WSS, we take partial differentiation for each \(\small c_{i}, i=1,2, ... , K\), and set it to 0. $$ \frac{\partial}{\partial c_{i}} \text{SSE} = \sum_{x \in G_{i}} \; 2 (c_{i} - x) = 0 $$ The solution to these simultaneous equations is as follows. $$ c_{i} = \frac{1}{n_{i}} \; \sum_{x \in G_{i}} \; x $$ That is, \(\small c_{1}, c_{2}, ... , c_{K} \) that minimize the SSE are each mean of the clusters.

If the data is one-dimensional and the absolute distance (Manhattan distance) is used as a distance measure, the performance measure of clustering becomes the sum of absolute error (SAE) as follows. $$ \text{SAE} = \sum_{i=1}^{K} \; \sum_{x \in G_{i}} \; | c_{i} - x | $$ It can be shown that the solution \(\small c_{1}, c_{2}, ... , c_{K} \) that minimizes this SAE are each median of the clusters. In general, the median is known to be less sensitive to extreme points or outliers.

\(\small K\)-means clustering module of 『eStatU』 provides a plot of the within sum of squares for various \(\small K\) as follows. After selecting \(\small K\), you can do clustering analysis by checking 'fixed K'.

An example of R commands for a \(\small K\)-means clustering with iris data when k = 3 is as follows.

K-means clustering with 3 clusters of sizes 38, 62, 50
Cluster means:
  Sepal.Length Sepal.Width Petal.Length Petal.Width
1     6.850000    3.073684     5.742105    2.071053
2     5.901613    2.748387     4.393548    1.433871
3     5.006000    3.428000     1.462000    0.246000
Clustering vector:
  [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 [38] 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 [75] 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 1 1 1 1 2 1 1 1 1
[112] 1 1 2 2 1 1 1 1 2 1 2 1 2 1 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1
[149] 1 2

Within cluster sum of squares by cluster:
[1] 23.87947 39.82097 15.15100
 (between_SS / total_SS =  88.4 %)
Available components:
[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
[6] "betweenss"    "size"         "iter"         "ifault"   

  [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 [38] 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 [75] 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 1 1 1 1 2 1 1 1 1
[112] 1 1 2 2 1 1 1 1 2 1 2 1 2 1 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1
[149] 1 2

To make a classification cross table, you can use a vector of Species and iriskmeans$cluster which is the cluster with table command as below. 'Setosa's are clustered 100% correctly, 'versicolor's are 48/50, but 'virginica's are 36/50.

Species       1  2  3
  setosa      0  0 50
  versicolor  2 48  0
  virginica  36 14  0