基于R语言的数据挖掘之聚类算法--层次方法
层次聚类主要分凝聚层次聚类和分裂层次聚类，凝聚层次聚类起初将每个观测视为一类，然后根据不同的计算距离方法运用到类的合并中，不断的重复计算距离并合并，最终将所有观测聚为一类；分裂层次聚类恰好与凝聚层次聚类相反。该两类过程可以看一下《数据挖掘：概念与技术》书中图示：
本文主要从凝聚的角度探讨聚类算法的运用，而聚类最重要的是计算类与类之间的距离。下面介绍一下7种常用的层次聚类方法，这7种方法的不同在于距离计算的不同：
1、最长距离法：类间的距离为一类中任一观测与另一类中任一观测间距离的最大值；
计算公式：
可视化理解：
2、最短距离法：类间的距离为一类中任一观测与另一类中任一观测间距离的最小值；
计算公式：
可视化理解
3、中间距离法：由于最长距离法夸大了类间距离，最短距离法低估了类间距离，而该方法则是介于两者之间的距离；
计算公式：
可视化理解：
4、类平均法：两类之间的距离是观测对之间的平均距离。类平均法趋向于合并具有较小偏差的类，而且稍微有点倾向于产生相同方差的类；
计算公式：
可视化理解：
5、重心法：两类之间的距离为它们的重心或均值之间的(平方)欧氏距离。重心法在处理异常值上比其他层次方法更稳健，但在其他方面不如Ward或类平均法的效果好；
计算公式：
可视化理解：
6、Ward最小方差法：该方法源于方差分析，类中各对象到类重心(均值)的平方欧氏距离之和。其思路为：两类合并后，离差平方和就会增加，每次选择使离差平方和增加最小的两类进行合并；
计算公式：
7、McQuitty相似分析法：类似于中间距离法。
计算公式：
聚类步骤：
1）将每一个观测对象视为一个类；
2）计算n各类之间的距离，得到距离矩阵；
3）将距离最近的进行合并
4）不断重复1）2）3）步骤，直至所有对象聚为一类。
可以通过下图直观的了解层次聚类的步骤：
应用：
可以通过R语言中stats包的hclust函数实现以上7种聚类方法，还可以结合plot与rect.hclust函数绘制层次聚类的谱系图。首先看一下hclust函数和rect.hclust函数的语法：
hclust(d, method = "complete", members = NULL)
d为一个距离矩阵，可以通过stats包中的dist函数计算一个数值型矩阵或数据框的距离
method为指定聚类的方法，可以是以上7种方法中的一种，默认为最长距离法。
rect.hclust(tree, k = NULL, which = NULL, x = NULL, h = NULL,
border = 2, cluster = NULL)
tree是一个hclust对象
k指定要聚类的个数
border指定图中边界颜色
实战
接下来实战部分的数据来源于《Clementine数据挖掘方法》中第10章示例，数据结构如下：
1、数据预处理
由于变量的值受量纲不同有大有小，需要标准化处理
data <- read.table('hclust_data.csv', head = TRUE, sep = ',')
row.names(data) <- data$Region
mydata <- scale(data)
2、计算距离矩阵
d <- dist(x = mydata, method = 'euclidean')
3、聚类算法的运用（以下一一尝试7种方法的比较）
1）最长距离法：
该方法将北京和上海聚为一类；将天津、山西和宁夏聚为一类；将浙江、安徽、河北、湖北、湖南、江苏、山东、广东、河南和四川归为一类，剩余的归为一类。
2）最短距离法：
该方法将北京和上海聚为一类；西藏和天津单独为一类；剩余的聚为一类。
3）中间距离法
4）类平均法
该方法将北京和上海聚为一类；西藏单独聚为一类；天津、山西、内蒙古和宁夏聚为一类；剩余的归为一类。
5）重心法
该方法将北京和上海聚为一类；天津和西藏单独聚为一类；剩余的全归为一类。
6）word最小方差法
该方法将北京和上海聚为一类；将江苏、山东、广东、河南和四川聚为一类；将天津、山西、内蒙古和宁夏聚为一类；最后将剩余的聚为一类。
7）McQuitty相似分析法
该方法将北京和上海聚为一类；将江苏、山东、广东、河南、四川、安徽、河北、湖北、湖南、浙江、辽宁、吉林和福建聚为一类；将天津、山西、内蒙古和宁夏聚为一类；将剩余的归为一类。
通过上面的7种聚类算法的比较，我们可以将综合发展水平比较高的北京和上海聚为一类；将天津、山西、内蒙古和宁夏这些经济总量不是很高的省市归为一类；将江苏、广东、浙江等归为一类；剩余的归为一类。这样的结果与《Clementine数据挖掘方法》中K-Means算法基本一致。
其实，这7种聚类算法还是存在比较大的差异，需要根据具体的业务和经验选择最终的聚类效果。
最后借用沈浩老师的话：层次聚类主要用在变量聚类中，如果对样本聚类，要求样本量不能太大，否则计算过程会消耗大量的时间，而且还可能不一定有用。
总结：文中所涉及到的R包和函数
stats包
scale()
dist()
hclust()
plot()
rect.hclust()
参考文章及数目：
blog.csdn.net/yillc/article/details/6746509
http://www.itongji.cn/article/1209142R012.html
http://bbs.pinggu.org/thread-3201417-1-1.html
https://cran.r-project.org/web/views/Cluster.html
《数据挖掘：概念与技术》
《SAS系统STAT》
《Clementine数据挖掘方法》