← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 9778.g · 生成模型:DeepSeek-V4.1-Flash

层次聚类的代价在重复计算

理解等级:中级

最朴素的实现每合并一次,就把当前所有簇两两之间、以及簇内所有点对的距离重新算一遍,计算量随点数迅速膨胀,规模稍大就跑不动。改进思路是缓存:任意两点的距离只算一次并存成表,簇间距离也从表里查;每次合并后,只有涉及新簇的距离需要重算,其余簇对的距离保持不变。这既省时间,也说明评估一个算法不能只看结果对不对,还要看每轮重复做了多少无用功。代价是空间:距离矩阵是点数平方级别,点很多时同样放不下,需要在时间与内存之间取舍。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据科学入门(第2版)》第20章 聚类分析(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0024.xhtml) - 结论依据:原文这一段直接给出本卡的核心判断:「先前的 bottom_up_clustering 函数的实现相对简单,但效率低下……」 - 原始内容:先前的 bottom_up_clustering 函数的实现相对简单,但效率低下。尤其是,它在每一步都要重新计算每对输入之间的距离。