DBSCAN - 设置最大簇跨度限制

Question

据我了解，DBSCAN可以指定一个半径（epsilon），比如100米。但由于DBSCAN在寻找聚类时要考虑密度可达性，而不是直接的密度可达性，因此可能会得到一个最大距离大于100米的聚类。更极端的情况下，您甚至可以设置100米的半径，并最终得到一个1公里的聚类：请参见来自scikit learn的图像数组中的[2][6]示例。（如果我误解了DBSCAN，也非常乐意被告知我是个白痴。）

是否有一种像DBSCAN这样的基于密度的算法，但考虑到聚类内任意两点之间的最大距离的阈值？

- user139014

Answer 1

DBSCAN算法确实没有对聚类施加总大小限制。

epsilon值最好理解为分离两个聚簇的间隙的大小（这些聚簇至多包含minpts-1个对象）。

我认为，你实际上并不是在寻找聚类：聚类是发现数据结构的任务。这种结构可以是简单的（如k-means），也可以是复杂的（如层次聚类和k-means发现的任意形状的聚簇）。

你可能正在寻找向量量化-将数据集减少到一组较小的代表集，或集合覆盖-查找给定集合的最佳覆盖，而不是聚类。

但是，我也有这样的印象，即你并不确定自己需要什么以及为什么需要。

DBSCAN的一个优势是它具有密度连接组件的数学定义结构。这是一个强大的（除了一些罕见的边界情况以外）明确定义的数学概念，而DBSCAN算法是发现这种结构的最优效率算法。

然而，直接密度可达性并不定义一个有用的（划分）结构。它只是不将数据划分为不相交的分区。

如果您不需要这种强的结构（即您不做"结构发现"中的聚类，而只是想像向量量化一样压缩数据），那么您可以尝试“Canopy预聚类”。它被视为针对聚类设计的预处理步骤。从本质上讲，它类似于DBSCAN，但它使用两个epsilon值，并且结构在任何方面都不能保证是最优的，但会高度依赖于您数据的排序方式。如果您适当地对其进行预处理，它仍然可能很有用。除非您处于分布式设置中，否则Canopy预聚类至少与完整的DBSCAN运行一样昂贵。由于要求不严格（特别是，“簇”可能重叠，并且对象预计属于多个“簇”），因此更容易并行化。

另外，您可能也正在寻找"完全链接层次聚类"。如果您在所需的高度处剪切树状图，则得到的聚类应该所有对象之间的最大距离都符合要求。唯一的问题是层次聚类通常是O(n^3)，即它无法扩展到大型数据集。DBSCAN在良好的实现中以O(n log n)运行（具有索引支持）。

- Has QUIT--Anony-Mousse

Answer 2

我曾经遇到同样的问题，最终通过将DBSCAN与KMeans聚类结合使用来解决：首先，我使用DBSCAN识别高密度聚类并删除离群值，然后将任何大于250英里（在我的情况下）的聚类分开。以下是代码：

from sklearn.cluster import DBSCAN 
clustering = DBSCAN(eps=0.3, min_samples=100).fit(load_geocodes[['lat', 'long']])
load_geocodes.loc[:,'cluster'] = clustering.labels_

import mpu
def calculate_cluster_size(lat, long):
    left_top = (max(lat), min(long))
    right_bottom = (min(lat), max(long))
    distance = mpu.haversine_distance(left_top, right_bottom)*0.621371
    return distance

for c, df in load_geocodes.groupby('cluster'):
    if c == -1:
        continue # don't do this for outliers
    distance = calculate_cluster_size(df['lat'], df['long'])
    print(distance)
    if distance > 250:
        # break clusters into more clusters until the maximum size of a cluster is less than 250 Miles
        max_distance = distance
        i = 2
        while max_distance > 250:
            kmeans = KMeans(n_clusters=i, random_state=0).fit(df[['lat', 'long']])
            df.loc[:, 'cl_temp'] = kmeans.labels_
            max_temp_cl_size = 0
            for temp_cl, temp_cl_df in df.groupby('cl_temp'):
                temp_cl_size = calculate_cluster_size(temp_cl_df['lat'], temp_cl_df['long'])
                if temp_cl_size > max_temp_cl_size:
                    max_temp_cl_size = temp_cl_size 
            i += 1
            max_distance = max_temp_cl_size
        load_geocodes.loc[df.index,'subcluster'] = kmeans.labels_

- Muriel