Python聚类算法

Question

我一直在搜索针对特定问题的聚类算法，使用scipy和sklearn。我需要将N个粒子的种群表征成k个组，其中k不一定已知，此外，没有先验的链接长度（类似于这个问题）。

我已经尝试了kmeans，如果您知道要分多少个簇，则效果很好。我也尝试了dbscan，但除非您告诉它停止（或开始）寻找簇的特征长度尺度，否则其效果不佳。问题是，我可能有成千上万个这些粒子集群，我无法告诉kmeans/dbscan算法他们应该依据什么去进行聚类。

这里有一个dbscan找到的示例：

您可以看到这里确实有两个独立的种群，但是，通过调整epsilon因子（相邻集群参数之间的最大距离），我根本无法让它看到这两个粒子集群。

还有其他算法适用于此吗？我正在寻找尽可能少的先验信息-换句话说，我希望算法能够做出关于什么可能构成单独集群的“聪明”决策。

- astromax

Answer 1

我找到了一种不需要先验信息/猜测并且在我要求的任务中表现非常好的算法。它被称为 Mean Shift，位于 SciKit-Learn 中。相对于其他算法（如亲和传播），它也比较快速。

以下是它所给出的一个例子：

我想指出的是，文档中提到它可能不会很好地扩展。

- astromax

---

根据所选的Mean Shift内核，您可以稍微加快它的速度。这里有一篇不错的文章，描述了一些优化方法，可用于使Mean Shift更具可伸缩性。http://sociograph.blogspot.com/2011/11/accessible-introduction-to-mean-shift.html - mattnedrich

谢谢提供信息 - 我会去查看的。 - astromax

MeanShift需要输入“带宽”作为参数，这听起来并不像是“没有先验”信息？ - K.-Michael Aye

如果您没有提供一个，特定的实现会为您选择一个。最重要的是，它不需要就群集数量做出选择。 - astromax

Answer 2

• 在使用DBSCAN时，提前将数据或距离进行规模化/归一化处理可能会有所帮助，这样epsilon的估计将是相对的。

• 有一个DBSCAN的实现 - 我认为是Anony-Mousse某个地方标记为“四处流传”的 - , 它带有一个epsilon估计器函数。只要不输入大型数据集，它就可以工作。

• 在github上有几个不完整版本的OPTICS。也许你可以找到一个来适应你的目的。仍在尝试弄清楚使用同一种提取方法的minPts会产生什么影响。

- embert

Answer 3

你可以尝试使用最小生成树（Zahn算法），然后移除类似于alpha shapes的最长边。我将其与Delaunay三角剖分和凸包一起使用：http://www.phpdevpad.de/geofence。你也可以尝试使用分层聚类，例如clusterfck。

- Micromega

---

clusterfck是一个带有k-means和分层聚类的js库。它计算最近邻。 - Micromega

Answer 4

你的图表显示你选择的minPts参数太小了。

看看OPTICS，它不再需要DBSCAN的epsilon参数。

- Has QUIT--Anony-Mousse

---

是的，对于这张图片你说的是对的 - 我已经尝试过调整minpoints和epsilon，但都没有效果。我会去看看OPTICS算法。你有相关的参考资料吗？ - astromax

它在维基百科上，并包含在ELKI中。 - Has QUIT--Anony-Mousse

谢谢 - 我真的希望有一个Python函数/库，而不是Java。 - astromax

我看过一个Python版本，但那个版本有很多问题；实际上它再次执行的是DBSCAN而不是OPTICS。 - Has QUIT--Anony-Mousse