问数据挖掘中的DBSCAN算法和聚类算法

EN

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

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

我怀疑是否有一次通过的DBSCAN版本，因为它依赖于成对距离。您可以删除其中的一些计算(这是索引发挥作用的地方)，但本质上您需要将每个对象与其他每个对象进行比较，因此它是在O(n log n)中进行的，而不是一遍。

One-pass:我相信最初的k-means是一种one-pass算法。前k个对象是你的初始均值。对于每个新对象，选择关闭均值并使用新对象(以增量方式)更新它。只要你不在你的数据集上进行另一次迭代，这就是“一次通过”。(不过，结果将比劳埃德式的k-means更糟糕)。

读一读前k条，然后拿着它们。计算它们之间的距离。

对于其余的每一项：

• 找出它与k个项目中的哪些项目最近，以及这两个项目之间的距离。
• 如果这大于k个项目中任意两个项目之间的最近距离，则可以将新项目与这两个项目中的一个项目交换，并且至少不会减小新k个项目中任何两个项目之间的最近距离。这样做是为了尽可能地增加此距离。

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