层次聚类算法是一个应用广泛的算法,小编最近要做对比实验,实现了其中一个版本,为了验证实验效果,结合我国各省会城市之间的距离,对省进行聚类看看效果如何。所有本文从3部分来介绍,首先简介层次聚类算法,然后讲解其实现原理,最后结合一个实例进行分析对比。

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’之间的距离。

dist

3.实验结果

根据上述凝聚层次算法原理,小编用c++实现了一个版本,感兴趣的可以从我的github下载源码。为了测试层次聚类的效果,小编采用中国32个省会城市的距离作为输入,分别利用单连接算法和全连接算法对32个省进行聚类。按照大的地区划分,人们一般将我国划分成华中、华北、华南、西北、东北、西南和华东地区,共7部分。小编这里实验的时候也是聚成7类,看看实际的效果是不是跟我们预想的相同。

下图1是单连接算法实验结果,图2是全连接算法结果。为了直观显示,小编将同一类的在地图上用同一种颜色标注,结果如下图3图4。

单连接

图1 单连接算法结果

全连接

图2 全连接算法结果

单连接地图

图3 单连接结果在地图中的显示效果

全连接地图

图4 全连接结果在地图中的显示效果

3 收藏


直接登录