DBSCANを使用したクラスタリングは驚くほど遅い

Question

クラスタリングを試していますが、どれほど遅いかは驚きです。 30個のノードを含む30のコミュニティを持つランダムグラフを作成しました。コミュニティ内のノードは90％の確率で接続され、同じコミュニティ内にないノード間のエッジは接続される確率は10％です。私は2つのノードの間で同様に隣人のセットの間の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" 

？ここで

Answer 1

私のマシン上で1890倍程度DBSCANコールをスピードアップソリューション：ここ

# 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