Я написал свой собственный алгоритм кластеризации Shared Nearest Neighbor (SNN), согласно оригинальной работе .По сути, я получаю ближайших соседей для каждой точки данных, предварительно вычисляю матрицу расстояний с помощью расстояния Жакара и передаю матрицу расстояний в DBSCAN.
Чтобы ускорить алгоритм, я вычисляю расстояние Жакара между двумя точками данных, если они являются ближайшими соседями друг друга и имеют более определенного количества общих соседей.Я также использую симметрию матрицы расстояний, так как я вычисляю только половину матрицы.
Однако мой алгоритм медленный и занимает гораздо больше времени, чем обычные алгоритмы кластеризации, такие как K-Means или DBSCAN.Может кто-нибудь посмотреть на мои коды и предложить, как я могу улучшить свои коды и сделать алгоритм быстрее?
def jaccard(a,b):
"""
Computes the Jaccard distance between two arrays.
Parameters
----------
a: an array.
b: an array.
"""
A = np.array(a, dtype='int')
B = np.array(b, dtype='int')
A = A[np.where(A > -1)[0]]
B = B[np.where(B > -1)[0]]
union = np.union1d(A,B)
intersection = np.intersect1d(A,B)
return 1.0 - len(intersection)*1.0 / len(union)
def iterator_dist(indices, k_min=5):
"""
An iterator that computes the Jaccard distance for any pair of stars.
Parameters:
indices: the indices of nearest neighbors in the chemistry-velocity
space.
"""
for n in range(len(indices)):
for m in indices[n][indices[n] > n]:
if len(np.intersect1d(indices[n], indices[m])) > k_min:
dist = jaccard(indices[n], indices[m])
yield (n, m, dist)
# load data here
data =
# hyperparameters
n_neighbors =
eps =
min_samples =
k_min =
# K Nearest Neighbors
nbrs = NearestNeighbors(n_neighbors=n_neighbors).fit(data)
distances, indices = nbrs.kneighbors()
# distance matrix
S = lil_matrix((len(distances), len(distances)))
for (n, m, dist) in iterator_dist(indices, k_min):
S[n,m] = dist
S[m,n] = dist
db = DBSCAN(eps=eps, min_samples=min_samples, metric='precomputed',
n_jobs=-1).fit(S)
labels = db.labels_