层次聚类与非层次聚类的区别？

Question

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

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

无层次：模糊C均值与K均值

Answer 1

不要混淆算法、和任务。

K均值有多个算法.实际上至少有二十多个。例如，有些人使用k-d树来加速。它们都是启发式的，因为找到最优的k-均值解被证明是NP难的，我相信。

类似地，存在用于分层聚类的朴素O(n^3)运行时和O(n^2)存储方法，还有运行在O(n^2)时间和O(n)内存中的算法，如单链接分层聚类算法和完全连锁分层聚类算法。

最后但并非最不重要的一点是，如果使用DBSCAN并设置minPts=2，那么在epsilon高度剪切时，其结果实际上与单链路分层聚类相同。但是，有了适当的索引，DBSCAN在O(n log n)中运行(例如在ELKI中-- and实现没有那么聪明，它需要O(n^2)内存和运行时)。

那么，为什么对于相同的任务可以有如此不同的运行时呢？首先，一些算法(和实现)可能非常原始。易于实现和理解，但没有他们可能的聪明。其次，一些算法执行额外的工作，您可能感兴趣，也可能不感兴趣。单链接层次聚类计算层次结构；使用minPts=2的DBSCAN只对该层次结构进行一次切割--这是一个比完整层次结构简单得多的结果。最后但并非最不重要的是，有启发式。大多数k-意思变体都属于最后一类:通过接受错过全局最佳解决方案，您当然可以比执行彻底搜索更快。