python之使用 DBSCAN 进行聚类非常慢

我正在试验集群，我很惊讶它看起来有多慢。我生成了一个随机图，其中包含 30 个社区，每个社区包含 30 个节点。社区中的节点有 90% 的机会连接，不在同一社区的节点之间的边有 10% 的机会连接。我正在测量两个节点之间的相似性作为 Jaccard similarity在他们的邻居组之间。

这个玩具示例仅在 dbscan 部分花费了大约 15 秒，如果我增加节点数量，这个时间会非常迅速地增加。由于总共只有 900 个节点，这看起来非常慢。

from __future__ import division 
import numpy as np 
from sklearn.cluster import dbscan 
import networkx as nx 
import matplotlib.pyplot as plt 
import time 
 
#Define the Jaccard distance. Following example for clustering with Levenshtein distance from from http://scikit-learn.org/stable/faq.html 
def jaccard_distance(x,y): 
    return 1 - len(neighbors[x].intersection(neighbors[y]))/len(neighbors[x].union(neighbors[y])) 
 
def jaccard_metric(x,y): 
    i, j = int(x[0]), int(y[0])     # extract indices 
    return jaccard_distance(i, j) 
 
#Simulate a planted partition graph. The simplest form of community detection benchmark. 
num_communities = 30 
size_of_communities = 30 
print "planted partition" 
G = nx.planted_partition_graph(num_communities, size_of_communities, 0.9, 0.1,seed=42) 
 
#Make a hash table of sets of neighbors for each node. 
neighbors={} 
for n in G: 
    for nbr in G[n]: 
        if not (n in neighbors): 
            neighbors[n] = set() 
        neighbors[n].add(nbr) 
 
print "Made data" 
 
X= np.arange(len(G)).reshape(-1,1) 
 
t = time.time() 
db = dbscan(X, metric = jaccard_metric, eps=0.85, min_samples=2) 
print db 
 
print "Clustering took ", time.time()-t, "seconds" 

How can I make this more scalable to larger numbers of nodes?

请您参考如下方法:

这里有一个解决方案可以在我的机器上将 DBSCAN 调用速度提高大约 1890 倍:

# the following code should be added to the question's code (it uses G and db) 
 
import igraph 
 
# use igraph to calculate Jaccard distances quickly 
edges = zip(*nx.to_edgelist(G)) 
G1 = igraph.Graph(len(G), zip(*edges[:2])) 
D = 1 - np.array(G1.similarity_jaccard(loops=False)) 
 
# DBSCAN is much faster with metric='precomputed' 
t = time.time() 
db1 = dbscan(D, metric='precomputed', eps=0.85, min_samples=2) 
print "clustering took %.5f seconds" %(time.time()-t) 
 
assert np.array_equal(db, db1) 

这里是输出:

... 
Clustering took  8.41049790382 seconds 
clustering took 0.00445 seconds