AGNES 算法

AGNES (Agglomerative Nesting) 是一种采用自底向上层次聚类策略的层次聚类算法。AGNES 算法最初将每个对象作为一个簇，然后这些簇根据某些准则被逐步合并。

img-2024-05-04 20-10-42.png

两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有对象最终属于同一个簇或达到一个终止条件。

img-2024-04-30 10-43-09.png

此过程可以概括为

  1. 将数据集中的每个样本看作一个初始聚类簇
  2. 在算法运行的每一步中找出距离最近的两个聚类簇进行合并
  3. 不断重复上一步骤，直至达到预设的聚类簇个数。

合并准则：每次找到距离最近的两个簇进行合并。两个簇之间的距离由这两个簇中距离最近的样本点之间的距离来表示。关键在于，如何计算聚类簇之间的距离？

实际上，每个簇是一个样本集合，因此只需要采用关于集合的某种距离即可。可以采用单链接方法和相异性矩阵

算法

输入：样本集 ，聚类簇距离度量函数 ，聚类类数

输出： 个簇，达到终止条件规定的簇的个数

过程：

  • 初始化时，每一个样本本身都是一个簇
  • 重复
    • 根据不同簇中最近样本间的距离找到最近的两个簇
    • 合并这两个簇，形成新的簇
  • 直到达到定义的 的个数

特点

  • AGNES 算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。
  • 已做处理不能撤销，聚类之间也不能交换对象。假如在某一步没有很好地选择
  • 算法的时间复杂度为 ，因此不适用处理 很大的数据集。

例题

为了研究辽宁省等五省区某年度城镇居民生活消费的分布规律，对如下调查数据进行聚类。

省份
辽宁 7.90 39.77 8.49 12.94 19.27 11.05 2.04 13.29
浙江 7.68 50.37 11.35 13.30 19.25 19.25 2.75 14.87
河南 9.42 27.93 8.20 8.14 16.17 16.17 1.55 9.76
甘肃 9.16 27.98 9.01 9.32 15.99 15.99 1.82 11.35
青海 10.06 28.64 10.52 10.05 16.18 16.18 1.96 10.81

解：

注意到 最小，因此将河南和甘肃聚在一起，记为 ，放在第一行第一列，再次计算相异性矩阵

注意到 最小，因此将河南，甘肃和青海聚在一起，记为 ，放在第一行第一列，再次计算相异性矩阵

注意到 最小，因此将浙江，辽宁聚在一起，记为 。如果设置了聚类个数为 ，则此事就得到了两个类

Interactive Graph
Table Of Contents
AGNES 算法
算法
特点
例题