层次聚类算法(HAC)

1.什么是层次聚类算法

层次聚类就是通过对数据集按照某种方法进行层次分解，直到满足某种条件为止。按照分类原理的不同，层次聚类算法分成凝聚的和分裂的两种，取决于层次分解是以自底向上(合并)还是以自顶向下(分裂)方式形成。凝聚的层次聚类方法使用自底向上的策略，开始时每个对象自己是独立的类(N个)，然后不断合并成越来越大的类，直到所有的对象都在一个类中，或者满足某个终止条件。在合并过程中是找出两个最近的类让他们合并形成一个类，所以最多进行N次迭代就将所有对象合并到一起了。分裂的层次聚类方法使用自顶向下的策略，开始时所有对象都在一个类中(1个)，然后不断的划分成更小的类，直到最小的类都足够凝聚或者只包含一个对象。通俗理解凝聚的层次聚类算法就相当于秦始皇先后消灭韩、赵、魏、楚、燕和齐统一六国的过程，而分裂的层次聚类算法刚好是一个相反的过程。

2.凝聚层次聚类算法原理

输入：给定要聚类的N个对象以及N*N的距离矩阵(或者是相似性矩阵) 步骤：

1. 将每个对象归为一类, 共得到N类, 每类仅包含一个对象. 类与类之间的距离就是它们所包含的对象之间的距离.
2. 找到最接近的两个类并合并成一类, 于是总的类数少了一个.
3. 重新计算新的类与所有旧类之间的距离.
4. 重复第2步和第3步, 直到最后合并成一个类为止(此类包含了N个对象)或满足一定条件终止 根据步骤3的不同, 可将层次式聚类方法分单连接算法(single-linkage) 、全连接算法(complete-linkage) 以及 average-linkage.其中单连接算法采用的是最小距离、全连接算法采用的是最大距离、average-linkage采用的是平均距离。定义如下，其中|p-p’|是两个对象或点p和p’之间的距离。

3.实验结果

为了测试层次聚类的效果，小编采用中国32个省会城市的距离作为输入，分别利用单连接算法和全连接算法对32个省进行聚类。 按照大的地区划分，人们一般将我国划分成华中、华北、华南、西北、东北、西南和华东地区，共7部分。小编这里实验的时候也是聚成7类，看看实际的效果是不是跟我们预想的相同。下图1是单连接算法实验结果，图2是全连接算法结果。

图1 单连接算法结果

图2 全连接算法结果

为了直观显示，小编将同一类的在地图上用同一种颜色标注，结果如下。

图3 单连接算法地图效果显示

图4 全连接算法地图效果显示

可以看到全连接算法效果是挺不错滴，可能大家有疑问，为什么结果我们印象中西南、西北这些大区划分有出入呢，其中一个原因是小编在这里是根据省会城市之间的距离来对省进行聚类的，但省会城市位置一般都不是在省的中心位置呀，所有出入嘛。图3中的展示的单连接算法结果偏差还是蛮大的，其实这也正是单连接算法与全连接算法的不同的地方，单连接算法容易形成带状区域，就是链条形状，我们可以看到图3中很大一片南北走向的区域都是红色，而图4中的全连接算法就要好很多。