Clustering

Dataset

Three simulated datasets noisy.circles, noisy.moons, blobs of 1500 observations x 2 features containing 2, 2, and 3 clusters respectively.

head(noisy.circles)

##           x1          x2 y
## 1 -0.4412984 -0.26011650 1
## 2  0.6052318 -0.65733542 0
## 3  1.0344003  0.05708226 0
## 4  0.4442293  0.03467232 1
## 5 -0.2264144  0.46547732 1
## 6  0.5648620 -0.81670969 0

k-means

The k-means optimization problem is to find the set C of cluster centers \(\mathbf c \in \mathbb R^m\), with \(|C| = k\), to minimize over a set of examples \(\mathbf x \in \mathbb R^m\) the following objective function: \[ \min \sum_{\mathbf x \in X} ||f(C, \mathbf x) - \mathbf x||^2 \] Here, \(f(C, \mathbf x)\) returns the nearest cluster center \(\mathbf c \in C\) to \(\mathbf x\) using Euclidean distance.

noisy.circles.km <- kmeans(noisy.circles[,1:2], centers = 2, iter.max = 100,
                           nstart = 10)
noisy.moons.km <- kmeans(noisy.moons[,1:2], centers = 2, iter.max = 100,
                         nstart = 10)
blobs.km <- kmeans(blobs[,1:2], centers = 3, iter.max = 100,
                   nstart = 10)

head(noisy.circles.km$cluster, 10)

##  [1] 1 2 2 2 1 2 2 1 2 2

noisy.circles.km$centers

##           x1         x2
## 1 -0.4007305  0.2630556
## 2  0.4004353 -0.2627844

k-medoids

Similar to the k-means algorithm, but in the k-medoids algorithm, the center of the subset is a member of the subset, called a medoid (i.e., cluster centers \(\mathbf c \in X\)). In the k-means algorithm, the center of the subset is the centroid.

noisy.circles.pam <- pam(noisy.circles[,1:2], k = 2, cluster.only = T)
noisy.moons.pam <- pam(noisy.moons[,1:2], k = 2, cluster.only = T)
blobs.pam <- pam(blobs[,1:2], k = 3, cluster.only = T)

head(noisy.circles.pam, 10)

##  [1] 1 1 2 2 2 1 1 2 1 2

Heirarchial Clustering

Hierarchical clustering groups data into a multilevel cluster tree or dendrogram. hclust() constructs the agglomerative hierarchical cluster tree.

Model specifications:

• Linkage criteria: Complete Linkage, \(\max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}\)

• Similarity measure: Euclidean distance, \(d(x, y) = \|x - y\|_2\)

• Desired number of groups = 2, 2, 3 for circles, moons, blobs respectively. (This determines where to cut the tree).

# euclidean distance and complete-linkage
noisy.circles.hc <- hclust(dist(noisy.circles[,1:2]))
noisy.circles.hc.clus <- cutree(noisy.circles.hc, k = 2)

noisy.moons.hc <- hclust(dist(noisy.moons[,1:2]))
noisy.moons.hc.clus <- cutree(noisy.moons.hc, k = 2)

blobs.hc <- hclust(dist(blobs[,1:2]))
blobs.hc.clus <- cutree(blobs.hc, k = 3)

head(noisy.circles.hc.clus, 10)

##  [1] 1 1 2 2 2 1 1 2 1 2

Remarks

Each point within a cluster gets assigned to one and only one cluster. In k-means, cluster points assigned to the same centroid belong to the same cluster. The centroid can be considered as a prototypical point inside the cluster. Similarly, k-medoids chooses medoids as cluster centers instead of the centroid. Usually a dendrogram is used to visualize the grouping produced by a hierarchical clustering algorithm. In a dendrogram, the dissimilarity between two child nodes is proportional to the height of their least common ancestor.