知识卡片
层次聚类的代价在重复计算
最朴素的实现每合并一次,就把当前所有簇两两之间、以及簇内所有点对的距离重新算一遍,计算量随点数迅速膨胀,规模稍大就跑不动。改进思路是缓存:任意两点的距离只算一次并存成表,簇间距离也从表里查;每次合并后,只有涉及新簇的距离需要重算,其余簇对的距离保持不变。这既省时间,也说明评估一个算法不能只看结果对不对,还要看每轮重复做了多少无用功。代价是空间:距离矩阵是点数平方级别,点很多时同样放不下,需要在时间与内存之间取舍。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 聚类分析 · 查看原书依据
先前的 bottom_up_clustering 函数的实现相对简单,但效率低下。尤其是,它在每一步都要重新计算每对输入之间的距离。
参考来源
- 位置:《数据科学入门(第2版)》第20章 聚类分析(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0024.xhtml)
- 结论依据:原文这一段直接给出本卡的核心判断:「先前的 bottom_up_clustering 函数的实现相对简单,但效率低下……」
- 原始内容:先前的 bottom_up_clustering 函数的实现相对简单,但效率低下。尤其是,它在每一步都要重新计算每对输入之间的距离。