第9章 聚类

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

  • 层次聚类
    不需要事先指定族的个数,以系统树的形式展现。
  • 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

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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,992评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,212评论 3 388
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,535评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,197评论 1 287
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,310评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,383评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,409评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,191评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,621评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,910评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,084评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,763评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,403评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,083评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,318评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,946评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,967评论 2 351

推荐阅读更多精彩内容

  • 文章内容主要摘自 https://blog.csdn.net/u011826404/article/details...
    一杭oneline阅读 900评论 0 0
  • 关键字 Q1:分类和聚类有什么不同? 第一,它们面对的根本问题不同。分类的根本问题是判断给定的某一个样本属于那一个...
    andyham阅读 1,331评论 0 13
  • 1. 前言 聚类任务是无监督学习,无监督学习的目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步...
    Aptitude阅读 573评论 2 0
  • 1. 章节主要内容 “聚类”(clustering)算法是“无监督学习”算法中研究最多、应用最广的算法,它试图将数...
    闪电随笔阅读 5,034评论 1 24
  • 9.1 聚类任务 在无监督学习任务中,包括了密度估计、异常检测以及聚类等。其中应用最广泛的是聚类。 聚类就是对大量...
    D系鼎溜阅读 1,112评论 0 1