分层与非分层聚类之间的区别？

Question

我想看看两者的性能是否可以根据他们工作的目标函数进行比较？

层次：单机联动，完全连锁和平均连锁算法

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

Answer 1

不要混淆算法和任务。

没有为k-均值多于一个的算法。其实至少有二打。例如，有些人使用k-d-trees进行加速。他们都是启发式的，因为我相信，找到最优的k-means解决方案在整体上表现为NP-hard。

同样，存在用于分级聚类的幼稚O(n^3)运行时和O(n^2)内存方法，然后有算法，诸如早产为单一联结分层聚类和CLINK完整联动分级聚类，在O(n^2)时间和O(n)存储器中运行。

最后但并非最不重要的，如果你使用DBSCAN并设置minPts=2，结果将有效地同单链路聚类时在epsilon高度切割。然而，通过适当的索引，DBSCAN运行在O(n log n)（例如，在ELKI中 - scipy的实现不是那么聪明，它需要O(n^2)内存和运行时）。

那么，为什么你可以有明显相同的任务，例如不同的运行时间？首先，一些算法（和实现）可能只是非常原始的。易于实施和理解，但不够聪明。其次，一些算法执行您可能感兴趣或可能不感兴趣的额外工作。单链接层次聚类计算层次结构; DBSCAN与minPts=2只有通过这种层次结构单一切 - 比完整的层次结构中的多简单的结果。最后但并非最不重要的，有启发式。大多数k-means变种都属于最后一类：通过接受错过全球最佳解决方案，当然可以比进行彻底搜索更快。