以距离矩阵为输入的聚类[评估]算法

Question

有没有人能推荐一些可以使用距离矩阵作为输入的聚类算法？或者也可以基于距离矩阵来评估聚类的“好坏”的算法？

目前，我使用的是对Kruskal算法(http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)的修改，将数据分成两个集群。不过，它有一个问题。当数据没有不同的聚类时，算法仍然会创建两个聚类，一个聚类包含一个元素，另一个包含所有其他元素。在这种情况下，我宁愿有一个包含所有元素的集群，而另一个集群是空的。

有没有能够进行这种类型的聚类的算法？

有没有什么算法可以估计聚类完成得有多好，或者更好地估计数据中有多少聚类？

算法应该只使用距离(相似性)矩阵作为输入。

Answer 1

还是同样基于距离矩阵的能够评估聚类“好坏”的算法？

KNN在评估聚类分配的“优劣”时应该是有用的。下面是操作步骤：

给定一个距离矩阵，每个点根据它所属的集群(它的“集群标签”)进行标记：

1. 将每个点的聚类标签与k最近邻点所隐含的聚类标签进行对比k最近邻域表示另一个聚类，该分类点会降低聚类的总体“优度”评级
2. 求和每个像素的“优度评级”贡献，以获得整个聚类的总“优度评级”

与k-means聚类分析不同，您的算法将返回有关分类不佳的点的信息。您可以使用该信息将某些点重新分配给新集群，从而提高集群的整体“质量”。

由于算法对群集的质心的放置一无所知，因此对全局群集密度一无所知，因此确保局部和全局密度的群集的唯一方式将是针对k值的范围运行该算法，并找到在k值的范围内最大化优度的布置。

对于大量的点，您可能需要优化此算法；可能需要使用哈希表来跟踪相对于每个点最近的点。否则，这个算法将需要相当长的时间来计算。

Answer 2

可用于估计集群数量的一些方法包括：

• Minimum Description Length
• Bayesian Information Criterion
• The gap statistic

Answer 3

scipy.cluster.hierarchy运行3个步骤，就像Matlab clusterdata一样

Y = scipy.spatial.distance.pdist( pts )  # you have this already
Z = hier.linkage( Y, method )  # N-1
T = hier.fcluster( Z, ncluster, criterion=criterion )

在这里linkage可能是一个改良的克鲁斯卡尔，不知道。这个SO answer (嗯)使用了上面的内容。

作为聚类的一种度量，对于2d/3d点，半径=到聚类中心的rms距离是快速和合理的。

告诉我们你的Npt，ndim，ncluster，hier/flat？集群是一个较大的区域，一种尺寸不能适合所有尺寸。