type
status
password
date
slug
summary
category
URL
tags
icon
层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：
- 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。例如AGNES
- 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。
AGNES
层次凝聚的代表是AGNES(AGglomerative NESting)算法。AGNES 算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度有多种不同的计算方法。聚类的合并过程反复进行直到所有的对象最终满足簇数目。
算法步骤
AGNES（自底向上凝聚算法）算法的具体步骤如下所示：
输入：包含个对象的数据库。
输出：满足终止条件的若干个簇。
(1) 将每个对象当成一个初始簇；
(2) REPEAT
(3) 计算任意两个簇的距离，并找到最近的两个簇；
(4) 合并两个簇，生成新的簇的集合；
(5) UNTIL 终止条件得到满足。
距离计算
上述算法的关键在于如何计算聚类簇之间的距离？实际上每个簇是一个样本集合，因此只需要采用关于集合的某种距离即可。例如给定聚类簇和，两个簇的距离可以通过以下定义得到：
- 最小距离：
- 最大距离：
- 均值距离：。其中
- 平均距离：
显然最小距离是由两个簇的最近样本决定、最大距离由两个簇的最远样本决定、均值距离由两个簇的中心位置决定、而平均距离则由两个簇的所有样本共同决定。当聚类距离由 、 或 计算时，AGNES算法被相应地称为“单链接”、“全链接”或“均链接”算法。
算法举例
使用AGNES算法对下面的数据集进行聚类，以最小距离计算簇间的距离。刚开始共有5个簇：、、、和。
样本点 | A | B | C | D | E |
A | 0 | 0.4 | 2 | 2.5 | 3 |
B | 0.4 | 0 | 1.6 | 2.1 | 1.9 |
C | 2 | 1.6 | 0 | 0.6 | 0.8 |
D | 2.5 | 2.1 | 0.6 | 0 | 1 |
E | 3 | 1.9 | 0.8 | 1 | 0 |
- 簇和簇的距离最近，将二者合并，得到新的簇结构：、、和。
样本点 | AB | C | D | E |
AB | 0 | 1.6 | 2.1 | 1.9 |
C | 1.6 | 0 | 0.6 | 0.8 |
D | 2.1 | 0.6 | 0 | 1 |
E | 1.9 | 0.8 | 1 | 0 |
- 接下来簇和簇的距离最近，将二者合并，得到新的簇结构：、和。
样本点 | AB | CD | E |
AB | 0 | 1.6 | 1.9 |
CD | 1.6 | 0 | 0.8 |
E | 1.9 | 0.8 | 0 |
- 接下来簇和簇的距离最近，将二者合并，得到新的簇结构：和。
样本点 | AB | CDE |
AB | 0 | 1.6 |
CDE | 1.6 | 0 |
- 最后只剩下簇和簇，二者的最近距离为1.6，将二者合并，得到新的簇结构：。
终止条件
层次聚类方法的终止条件：
- 设定一个最小距离阈值，如果最相近的两个簇的距离已经超过，则它们不需再合并，聚类终止。
- 限定簇的个数k，当得到的簇的个数已经达到k，则聚类终止。
算法性能分析
AGNES算法比较简单，但一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。增加新的样本对结果的影响较大。
假定在开始的时候有个簇，在结束的时候有1个簇，因此在主循环中有次迭代，在第次迭代中，我们必须在个簇中找到最靠近的两个进行合并。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为 ，该算法对于数据量很大的情况是不适用的。
DINAN
输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）
输出：聚类结果
(1) 将样本集中的所有的样本归为一个类簇；
(2) repeat：
在同一个类簇（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a,b；
将样本a，b分配到不同的类簇c1和c2中；
计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)<dis(b)，则将样本点归到c1中，否则归到c2中；
util： 达到聚类的数目或者达到设定的条件