DBSCAN算法和数据挖掘聚类算法

Question

如何在分类数据（蘑菇数据集）上实现DBSCAN算法？

什么是单程聚类算法？

你能提供一个单程聚类算法的伪代码吗？

Answer 1

阅读前k项并按住它们。计算它们之间的距离。

对于每个剩余的项：

• 找出第k项目的，它是最接近，而这两个项之间的距离。

• 如果这比k个项目中任意两个之间的最近距离更长，那么可以将新项目与这两个项目中的一个交换，并且至少不会减少任何两个新k项目之间的最近距离。尽可能地增加这个距离。

假设集合中的所有项目可以被分成升< = k个簇，使得同一集群中的任何两个点之间的距离比在不同的簇的任何两个点之间的距离更小。然后在运行此算法后，您将保留每个群集至少一个点。

Answer 2

您可以使用任意距离函数运行DBSCAN而不做任何更改。索引部分将更加困难，因此您可能只会获得O(n^2)的复杂性。

但是，如果仔细观察DBSCAN，它所做的只是计算距离，将它们与阈值进行比较并计算对象。这是它的一个关键优势，它可以很容易地应用于各种数据，所有你需要的是定义一个距离函数和阈值。

我怀疑有一个DBSCAN版本，因为它依赖于成对距离。你可以修剪这些计算中的一部分（这是索引起作用的地方），但基本上你需要将每个对象与其他对象进行比较，所以它在O(n log n)而不是一遍。

单程：我相信最初的k-means是一个一遍算法。前k个对象是你的初始手段。对于每个新对象，您选择关闭平均值并用新对象更新（增量）。只要你不对数据集做另一次迭代，这就是“一次通过”。 （虽然结果会比劳埃德风格的K-means更糟糕）。