performance - 层次聚类和非层次聚类的区别？

Question

我想看看两者的性能是否可以根据它们所处理的目标函数进行比较？

分层：单链接、完全链接和平均链接算法

非分层：模糊 C 均值和 K 均值

Answer 1

不要混淆算法和任务。

k-means 有不止一种算法。实际上至少有两打。例如，有些人使用 kd-trees 进行加速。而且它们都是启发式的，因为我相信找到最佳 k-means 解决方案通常是 NP-hard 的。

类似地，层次聚类有朴素的O(n^3)运行时和O(n^2)内存方法，然后有诸如用于单链接层次聚类的 SLINK 和用于完全链接层次聚类的 CLINK 等算法，它们可以在O(n^2)时间和O(n)内存中运行。

最后但同样重要的是，如果你使用 DBSCAN 和 set ，minPts=2当在 epsilon然而，通过适当的索引，DBSCAN 可以运行O(n log n)（例如在 ELKI 中 - scipy 实现并不那么聪明，它需要O(n^2)内存和运行时）。

那么为什么你可以为显然相同的任务有如此不同的运行时呢？首先，一些算法（和实现）可能非常原始。易于实施和理解，但没有他们想象的那么聪明。其次，一些算法会执行您可能感兴趣或可能不感兴趣的额外工作。单链接层次聚类计算层次结构；DBSCANminPts=2只对这个层次结构进行了一次切割——比完整层次结构简单得多。最后但并非最不重要的一点是启发式方法。大多数 k-means 变体都属于最后一类：通过接受错过全局最佳解决方案，您当然可以比执行穷举搜索更快。