知识卡片
层次聚类两条路线
层次聚类不预设类数,而是生成一棵可切割的树。凝聚路线以 AGNES 为代表:初始每点自成一类,计算类间距离矩阵,合并最近的两类,重复到全部归为一类或满足终止条件。分裂路线以 DIANA 为代表:全部点先为一类,选到其他点平均距离最大的点作新类种子,再对每点算 Di=d_avg(pi,C1)−d_avg(pi,C2),把 Di>0 的点搬入新类,直到所有 Di,得到两个类后递归分裂。AGNES 复杂度 O(n²log n),简单易解释,但合并不可撤销——新类一旦形成就不能再拆开,早期错并无法修正。DIANA 把 n 个点分成两类的可能有 2^(n−1)−1 种,只能靠上述启发式近似,因而更慢。两条路线都让类数由切树位置决定,这是与[[K均值与Lloyd迭代]]的根本差别。
结构图:
flowchart TD
A["每点自成一类"] --> B["合并最近两类"]
B --> C{"是否只剩一类"}
C -- 否 --> B
C -- 是 --> D["得到树状图"]
E["全部点为一类"] --> F["选平均距离最大的种子点"]
F --> G["按 Di 逐个搬移点"]
G --> H{"所有 Di 均小于 0"}
H -- 否 --> G
H -- 是 --> I["分成两类并递归"]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第8章 聚类分析
原书出处 · 1 处
- 第8章 聚类分析 · 查看原书依据
上述方法的优点在于简单易懂,结果容易解释。不足之处在于一旦两个类合并为一个新的类,这个新类不能再分解。AGNES算法的复杂度为O(n2logn),不适合大规模的数据集。
参考来源
- 位置:《大数据挖掘与统计机器学习》第8章 聚类分析(源文件:extracted/大数据挖掘与统计机器学习/_epub-src/OEBPS/Text/chapter10_0001.xhtml,8.1.2 层次聚类)
- 结论依据:原文给出 AGNES 的四步合并流程、O(n2logn) 复杂度与「一旦合并不能再分解」的不足,并给出 DIANA 的种子点选择与 Di 判据。
- 原始内容:上述方法的优点在于简单易懂,结果容易解释。不足之处在于一旦两个类合并为一个新的类,这个新类不能再分解。AGNES算法的复杂度为O(n2logn),不适合大规模的数据集。