贪心聚类算法速度提升

我正在尝试在 python 中实现一个非常简单的贪婪聚类算法，但很难优化它的速度。该算法将采用距离矩阵，找到具有最多小于预定距离截止值的分量的列，并将行索引（具有小于截止值的分量）存储为簇的成员。簇的质心是列索引。然后，从距离矩阵中删除每个成员索引的列和行（产生一个较小但仍为方阵的矩阵），并且该算法会依次迭代较小的距离矩阵，直到找到所有簇。因为每次迭代都依赖于最后一次（形成一个新的距离矩阵，以便集群之间没有重叠的成员），所以我认为我无法避免 python 中的缓慢 for 循环。我尝试过 numba (jit) 来加速它，但我认为它正在恢复到 python 模式，因此不会导致任何速度增益。下面是该算法的两种实现。第一个比后者慢。任何关于加速的建议都是非常受欢迎的。我知道 scipy 或 sklearn 中实现的其他聚类算法（例如 DBSCAN、kmeans/medoids 等），但我非常热衷于在我的应用程序中使用当前的算法。在此先感谢您的任何建议。

方法 1（较慢）：

def cluster(distance_matrix, cutoff=1):
    indices = np.arange(0, len(distance_matrix))
    boolean_distance_matrix = distance_matrix <= cutoff
    centroids = []
    members = []
    while boolean_distance_matrix.any():
        centroid = np.argmax(np.sum(boolean_distance_matrix, axis=0))
        mem_indices = boolean_distance_matrix[:, centroid]
        mems = indices[mem_indices]
        boolean_distance_matrix[mems, :] = False
        boolean_distance_matrix[:, mems] = False
        centroids.append(centroid)
        members.append(mems)
    return members, centroids

方法 2（更快，但对于大矩阵仍然很慢）：

它以 sklearn 最近邻实现形成的邻接（稀疏）矩阵作为输入。这是我能想到的获取聚类相关距离矩阵的最简单、最快的方法。我相信使用稀疏矩阵也可以加快聚类算法的速度。

nbrs = NearestNeighbors(metric='euclidean', radius=1.5, 
algorithm='kd_tree')            
nbrs.fit(data)    
adjacency_matrix = nbrs.radius_neighbors_graph(data)   

def cluster(adjacency_matrix, gt=1):
    rows = adjacency_matrix.nonzero()[0]
    cols = adjacency_matrix.nonzero()[1]
    members = []
    member = np.ones(len(range(gt+1)))
    centroids = []
    appendc = centroids.append
    appendm = members.append
    while len(member) > gt:
        un, coun = np.unique(cols, return_counts=True)
        centroid = un[np.argmax(coun)]
        appendc(centroid)
        member = rows[cols == centroid]
        appendm(member)
        cols = cols[np.in1d(rows, member, invert=True)]
        rows = rows[np.in1d(rows, member, invert=True)]
    return members, centroids