1. 层次聚类算法原理
层次聚类根据划分策略包括聚合层次聚类和拆分层次聚类，由于前者较后者有更广泛的应用且算法思想一致，因此本节重点介绍聚合层次聚类算法。
聚合层次聚类算法假设每个样本点都是单独的簇类，然后在算法运行的每一次迭代中找出相似度较高的簇类进行合并，该过程不断重复，直到达到预设的簇类个数K或只有一个簇类。
聚合层次聚类的基本思想：
1）计算数据集的相似矩阵；
2）假设每个样本点为一个簇类；
3）循环：合并相似度最高的两个簇类，然后更新相似矩阵；
4）当簇类个数为1时，循环终止；
为了更好的理解，我们对算法进行图示说明，假设我们有6个样本点{A,B,C,D,E,F}。
第一步：我们假设每个样本点都为一个簇类（如下图），计算每个簇类间的相似度，得到相似矩阵；
第二步：若B和C的相似度最高，合并簇类B和C为一个簇类。现在我们还有五个簇类，分别为A，BC，D，E，F。
第三步：更新簇类间的相似矩阵，相似矩阵的大小为5行5列；若簇类BC和D的相似度最高，合并簇类BC和D为一个簇类。现在我们还有四个簇类，分别为A，BCD，E，F。
第四步：更新簇类间的相似矩阵，相似矩阵的大小为4行4列；若簇类E和F的相似度最高，合并簇类E和F为一个簇类。现在我们还有3个簇类，分别为A，BCD，EF。
第五步：重复第四步，簇类BCD和簇类EF的相似度最高，合并该两个簇类；现在我们还有2个簇类，分别为A，BCDEF。
第六步：最后合并簇类A和BCDEF为一个簇类，层次聚类算法结束。
树状图是类似树（tree-like）的图表，记录了簇类聚合和拆分的顺序。我们根据上面的步骤，使用树状图对聚合层次聚类算法进行可视化：
也可用下面的图记录簇类聚合和拆分的顺序：
拆分层次聚类算法假设所有数据集归为一类，然后在算法运行的每一次迭代中拆分相似度最低的样本，该过程不断重复，最终每个样本对应一个簇类。简单点说，拆分层次聚类是聚合层次聚类的反向算法，读者可通过树状图去加强理解，一个是自底向上的划分，一个是自顶向下的划分。
更多详细内容可参考文章：https://mp.weixin.qq.com/s?src=11×tamp=1579049806&ver=2097&signature=dMqw*uVyGvimGlwnnjefqC6TTqTZk8VVlxTwXJi**muek6SSbNuGOlKWxXM4DEYtcDwuUVSur4XA7x6R4xTF51JZLeygx0gmgKuFs8-VTkRaba4v7d1jCtmY4h219Ztf&new=1
2.函数介绍
hclust()函数
在R语言中，用于实现层次聚类的函数是hclust()，其基本书写格式为：
代码语言：javascript复制hclust(d, method = "complete", members = NULL)参数:
D:指定用于系统聚类的数据集样本间的距离矩阵，可以利用函数dist()计算得到；
method：指定用于聚类的算法，"ward.D"和"ward.D2"均表示采用ward离差平方和法, "single"表示最短距离法, "complete"表示最长距离法, "average" (= UPGMA)表示类平均法, "median" (= WPGMC) 表示中间距离，"centroid" (= UPGMC)表示重心法，默认值为complete。
members：取值为NULL或长度为d的向量，用于指定每个待聚类的小类别是由几个样本点组成的。
此外，我们还需要介绍几个相关函数：dist(),cutree()和rech.hclust()。
dist()是计算函数
代码语言：javascript复制dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2)参数介绍：
x：指定用于计算距离的数据对象，可以是矩阵、数据框或dist对象。
method："euclidean"表示欧氏距离, "maximum"表示最大距离, "manhattan"表示绝对值距离, "canberra"表示兰氏距离, "binary"或 "minkowski"表示闵可夫斯基距离，默认值为"euclidean"。
diag：逻辑值，指定是否将距离矩阵的对角元素输出；
upper：逻辑值，指定是否将距离矩阵的上对角元素输出；
p：指定闵可夫斯基距离的范围。
cutree()函数
该函数用于将hcluster()的输出结果进行剪枝，最终得到指定类别的聚类结果，书写格式为：
cutree(tree, k = NULL, h = NULL)
参数介绍：
tree:指定函数hcluster()的聚类结果；
k：一个整数或向量，用于指定聚类的数目；
h：数字标量或向量，用于指定需要剪枝的树的高度。
3.分析实战
下面采用R语言中内置的数据集UScitiesD 进行操作演练，该数据收集了没过10个城市的距离。
data(UScitiesD)
UScitiesD
> class(UScitiesD)[1] "dist"
> mds2 <- -cmdscale(UScitiesD)
> plot(mds2, type="p",col=2, axes=FALSE, ann=FALSE)
> text(mds2, labels=rownames(mds2), xpd = NA)
>hcity.A <- hclust(UScitiesD, "average") # "wrong"
>plot(hcity.A,col="#487AA1",col.main="#45ADA8",col.lab="#7C8071",col.axis="#F38630",lwd=3,lty=1,sub="",axes=FALSE,hang=-1
>axis(side=2,at=seq(0,8000,2000),col="#F38630",lwd=2,labels=FALSE)
>mtext(seq(0,8000,2000),side=2,at=seq(0,8000,2000),line=1,col="#A38630",las=2)
上面的代码第一条命令选用平均法进行聚类分析，后续代码将结果进行可视化。
此外，还可以利用包RcolorBrewer中的函数heatmap函数直观地观察样本与变量的聚类情况。
> library(RColorBrewer)
> heatmap(as.matrix(UScitiesD),col=brewer.pal(9,"RdYlGn"),scale="column",margins=c(4,8))
还可以利用ape包对聚类系谱图进行一定的改进。
> library(ape)
> mypal<-c("#556270","#4ECDC4","#1B676B","#FF6B6B")> hcity.D2 <- hclust(UScitiesD, "ward.D2")
> clus4<-cutree(hcity.D2,4)
> par(bg="#E8DDCB",mar=rep(2.4,4),cex=1.3)
>plot(as.phylo(hcity.D2),type="fan",edge.width=2,edge.color="darkgrey",tip.color=mypal[clus4])
