不同于分类和回归，聚类不需要事先的任何参考分类信息，可以简单地通过判断数据特征的相似性来完成对数据的归类。

• 层次聚类
  不需要事先指定族的个数，以系统树的形式展现。
• k均值聚类
  扁平聚类，不会生成聚类层次，需要事先确定族的个数，性能优于层次聚类。
• 基于模型的聚类
  以上两种是启发式聚类，不需要任何形式化的模型，而基于模型的则事先假定存在某个数据模型，并用EM算法试图求出最相近的模型参数和簇的个数。
• 基于密度的聚类
  将分布稠密的样本划分到同一个簇，并过滤低密度的区域。
  下面一一看下四种算法，并采用基于簇间距离平方和志平均侧影宽度进行聚类内部验证，通过Ground truth方法完成聚类的外部验证。

9.2 通过层次聚类处理数据

可以分成自底向上的凝聚（agglomerative)和自顶向下的分裂（divise）两种。首先都要通过距离相似性来判断对数据合并还是分裂处理。整个算法递归过程一直到全部归并到一个簇或不可再分为止，最后系统树图展现聚类层次结构。

# data
wget https://github.com/ywchiu/ml_R_cookbook/raw/master/CH9/customer.csv
# 只有60行，复制在这
ID,Visit.Time,Average.Expense,Sex,Age
1,3,5.7,0,10
2,5,14.5,0,27
3,16,33.5,0,32
4,5,15.9,0,30
5,16,24.9,0,23
6,3,12,0,15
7,12,28.5,0,33
8,14,18.8,0,27
9,6,23.8,0,16
10,3,5.3,0,11
11,4,8.6,0,13
12,14,21,0,25
13,12,28.5,0,33
14,7,16.1,0,16
15,4,17.4,0,9
16,6,4.6,0,21
17,14,23.6,0,22
18,8,15.9,0,19
19,17,25.9,0,18
20,8,20.4,1,39
21,7,10.9,1,17
22,14,33.7,1,17
23,3,5.6,1,12
24,18,21.1,1,26
25,12,30,1,28
26,3,4.8,1,12
27,6,9.1,1,11
28,9,29.4,1,32
29,5,10.2,1,17
30,1,4.5,1,8
31,10,10.9,1,17
32,12,25.4,1,27
33,13,25.5,1,36
34,13,20.1,1,26
35,1,4.5,1,8
36,4,11,1,12
37,10,27.6,1,41
38,4,12,1,23
39,7,10.6,1,15
40,7,10.9,1,17
41,3,8.3,1,8
42,7,16.1,1,16
43,7,11.5,1,19
44,9,15.6,1,21
45,11,24.9,1,25
46,9,29.4,1,32
47,6,23.8,1,16
48,5,14.9,1,17
49,7,15.1,1,21
50,18,21.1,1,26
51,3,5.3,1,11
52,10,17.8,1,29
53,15,27.9,1,23
54,8,12,1,22
55,9,19,1,20
56,3,7.2,1,15
57,13,25.2,1,47
58,8,11.3,1,22
59,6,8.1,1,10
60,11,26.3,1,45
# ###########聚类
customer <- read.csv('customer.csv', header = TRUE)
head(customer)
str(customer)
# 归一化
customer <- scale(customer[,-1])
# 自底向上
hc <- hclust(dist(customer, method = "euclidean"), method = "ward.D2");hc
Call:
hclust(d = dist(customer, method = "euclidean"), method = "ward.D2")

Cluster method   : ward.D2 
Distance         : euclidean 
Number of objects: 60 
plot(hc, hang = 0.01, cex=0.7)

离差平方和ward.D2法聚类树图
single最短距离法
距离有最短距离、最长距离（complete linkage）、平均距离和最小方差法。
拓展

9.3 将树分成簇

# 簇
fit <- cutree(hc,k=4)
fit
 [1] 1 1 2 1 2 1 2 2 1 1 1 2 2 1 1 1 2 1 2 3 4 3 4 3 3 4 4 3 4 4 4 3 3 3 4
[36] 4 3 4 4 4 4 4 4 4 3 3 4 4 4 3 4 3 3 4 4 4 3 4 4 3
table(fit)
fit
 1  2  3  4 
11  8 16 25 
plot(hc)
rect.hclust(hc,k=4, border = "red")
plot(fit)

红框标记不同簇
无意中画了这个图，也挺好
除了指定cutree函数中的簇个数，还可以通过设置height值来指定聚类树的高度，达到切割树的目的。
拓展

# 单独标记某簇
plot(hc)
rect.hclust(hc,k=4,which =2,border = "red")
# 不同颜色不同簇 dendextend包
dend %>% color_branches(k=4) %>% plot(horiz=TRUE, main="Horizontal Dendrogram")
# 加红框
dend %>% rect.dendrogram(k=4, horiz = TRUE)

image.png
水平聚类，彩框
分割线

9.4 使用k均值法处理数据

扁平聚类，一层划分得到k簇，需要先确定簇个数，效率优于层次聚类。

# knn
set.seed(22)
fit <- kmeans(customer,4)
fit
# 簇中心条形图
barplot(t(fit$centers),beside = TRUE, xlab = "cluster", ylab = "value")
# 簇散点图
plot(customer, col=fit$cluster)

4簇不同属性条形图

分裂聚类，目的是使组内平方和最小。还可以规定具体的聚类方法，如Hatigan-Wong, Lloyd, Forgy以及MacQueen。

9.5 绘制二元聚类图

二元聚类将变量减少为两个主要成分，再利用组件（轴线和椭圆）展示数据聚类的结果。

# 二元聚类
library(cluster)
clusplot(customer, fit$cluster, color = TRUE, shade = TRUE)
# 标记并放大
par(mfrow=c(1,2))
clusplot(customer, fit$cluster, color = TRUE, shade = TRUE)
rect(0.5,-1.15,3,-0.4,border = "orange", lwd = 2)
clusplot(customer, fit$cluster, color = TRUE, xlim = c(0.5,3),
         ylim = c(-1.15,-0.4))

图画得有点累，找坐标
拓展
clusplot使用了princomp和cmdscale两个函数降维操作得到主成分

# cmdscale
par(mfrow=c(1,1))
mds <- cmdscale(dist(customer), k=2)
plot(mds,col=fit$cluster)

cmdscale MDS

9.6 聚类算法比较

可以使用簇内距离或者簇间距离作为评判标准，fpc包的cluster.stat函数

# 算法比较
install.packages("fpc")
library(fpc)
single_c <- hclust(dist(customer), method = "single") #层次聚类 最短距离法
hc_single <- cutree(single_c, k=4)
# 层次聚类 最长距离法
complete_c <-  hclust(dist(customer), method = "complete")
hc_complete <- cutree(complete_c, k=4)
set.seed(22)
# km均值
km <- kmeans(customer,4)
# 基本统计
cs <- cluster.stats(dist(customer), km$cluster)
cs[c('within.cluster.ss', 'avg.silwidth')]
# 列表显示
sapply(list(kmeans=km$cluster, hc_single =hc_single, hc_complete=hc_complete), 
       function(c) cluster.stats(dist(customer), c)[c('within.cluster.ss', 'avg.silwidth')])
                  kmeans    hc_single hc_complete
within.cluster.ss 61.3489   136.0092  65.94076   #距离平方和，同一簇之间对象相关性，越小相关性越大
avg.silwidth      0.4640587 0.2481926 0.4255961 # 平均轮廓值，既考虑簇内聚合又考虑簇间分离度

最长距离层次聚类优于最短距离层次聚类和km算法。如下也可以输出聚类统计信息：

km$withinss
[1] 20.89159  5.90040 22.58236 11.97454
km$betweenss
[1] 174.6511

9.7 从簇中抽取轮廓

轮廓系数取值0-1，越接近于1，聚类效果越好。

# 轮廓
kms <- silhouette(km$cluster, dist(customer))
summary(kms)
Silhouette of 60 units in 4 clusters from silhouette.default(x = km$cluster, dist = dist(customer)) :
 Cluster sizes and average silhouette widths:
       25         8        16        11 
0.5164434 0.5464597 0.3794910 0.4080823 
Individual silhouette widths:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.1931  0.4030  0.4890  0.4641  0.5422  0.6333 
plot(kms)

k均值聚类对象轮廓

9.8 获得优化的k均值聚类

k均值算法效率高也易于实现，可以使用距离平方和来确定哪个k值能实现最好的效果。

# 优化km聚类
nk<- 2:10
set.seed(22)
# 每个簇距离平方和
WSS <- sapply(nk, function(k){
   kmeans(customer, centers = k)$tot.withinss
})
WSS
plot(nk,WSS,type = "l", xlab = "no. of k", ylab = "within sum of squares")
# 平均轮廓
SW<- sapply(nk, function(k){
   cluster.stats(dist(customer), kmeans(customer,centers = k)$cluster)$avg.silwidth
})
SW
plot(nk,SW, type = "l",xlab = "no. of k", ylab = "average ailhouette width")
nk[which.max(SW)]
[1] 4

不同k平方和线图
不同k平均轮廓

9.9 使用密度聚类方法处理数据

将分布稠密和稀疏的样本分开，DBSCAN是最著名的算法。

# 密度聚类
install.packages("mlbench")
library(mlbench)
install.packages("fpc")
library(fpc)
set.seed(2)
p <- mlbench.cassini(500)
plot(p$x)
ds <- dbscan(dist(p$x), 0.2,2,countmode=NULL,method="dist");ds # 可达距离0.2，最小可达点个数2，计算进度NULL，距离矩阵作为计算依据
dbscan Pts=500 MinPts=2 eps=0.2
        1   2   3
seed  200 200 100
total 200 200 100
plot(ds,p$x)
#预测
y<- matrix(0,nrow = 3, ncol = 2)
y[1,] <- c(0,0)
y[2,] <- c(0,-1.5)
y[3,] <- c(1,1)
y
     [,1] [,2]
[1,]    0  0.0
[2,]    0 -1.5
[3,]    1  1.0
#预测
y<- matrix(0,nrow = 3, ncol = 2)
y[1,] <- c(0,0)
y[2,] <- c(0,-1.5)
y[3,] <- c(1,1)
y
predict(ds,p$x,y)
[1] 3 1 2

Cassini问题图
聚类结果彩色散点图

两个参数eps和MinPts，分别是最大邻域半径和邻域半径范围内的最小点数。可以调用fpc::plotcluster函数生成一个判别投影图

9.10 基于模型的聚类方法

# ########模型
install.packages("mclust")
library(mclust)
mb <- Mclust(customer)
par(mfrow=c(1,1))
plot(mb)
summary(mb)
---------------------------------------------------- 
Gaussian finite mixture model fitted by EM algorithm 
---------------------------------------------------- 

Mclust VII (spherical, varying volume) model with 5 components: 

 log-likelihood  n df       BIC       ICL
      -220.7207 60 29 -560.1775 -561.8828

Clustering table:
 1  2  3  4  5 
11  8 17 17  7 

不同成分BIC
不同特征组合分类
不同组合分类不确定性
密度估计

基于概率的方法，而不启发式构建簇，假设服从某未知分布，并试图找出这个分布，有限混合模型是一类常见的模型，单个模型分配线性权重再组合得到结果模型，提供一个灵活模型框架解释数据分布概率。步骤是首先确定模型数量及概率分布类型，然后构建并计算每个模型后验概率，最后分配到概率最大类别。BIC用于选择簇的个数。簇个数为5.

相异度矩阵的可视化

用来评估聚类的质量，热力图可以实现，相似的颜色深，如对角线。

# 相异度矩阵的可视化
install.packages("seriation")
library(seriation)
dissplot(dist(customer), labels = km$cluster, 
         options = list(main="Kmeans Clustering With K=4"))
dissplot(dist(customer), labels = hc_complete,
         options = list(main="Hierachical Clustering ") )

相异度矩阵图
层次聚类
拓展
dist和image也可以实现image(as.matrix(dist(customer)))

heapmap当然也可以

heatmap(customer,Rowv = as.dendrogram(hclust(t(dist(customer)))), Colv = as.dendrogram(hclust(dist(t(customer)))))

9.12 外部验证评估

# 外部验证
install.packages("png")
library(png)
img2 <- readPNG('handwriting.png',TRUE)
img3 <- img2[,nrow(img2):1]
b <- cbind(as.integer(which(img3 < -1) %% 28), which(img3 < -1)/28)
plot(b,xlim = c(1,28), ylim = c(1,28))
# km
set.seed(18)
fit <- kmeans(b,2)
plot(b,col=fit$cluster,xlim = c(1,28), ylim = c(1,28))
# dbscan
ds <- dbscan(b,2)
ds
plot(ds,xlim = c(1,28), ylim = c(1,28))

手写数字散点图
kmeans
dbscan

这里部分理解了计算机处理图像的方式。