python - 如果向量在欧几里德空间中距离太近，则使用快速/内存保护方式从数组中删除向量

Question

为了使聚类成为一项更可行的任务，我想从数组中删除项目，如果它们有另一个项目在 n 维欧几里德空间中的某个阈值内。此截断的输入数据是像素级特征向量数组。我的第一个想法是计算所有项目之间的成对欧氏距离矩阵，然后对它们进行操作:

indices = list(range(len(X)))
dist_matrix = euclidean_distances(X,X)

index = 0
while True:
    deletion = np.where(dist_matrix[index]<=threshold)[0]
    indices = [i for i in indices if i==index or i not in deletion]
    try:
        index = indices[indices.index(index) + 1]
    except IndexError:
        break

dictionary = []
for index in indices:
    dictionary.append(X[index])

但是，当使用 sklearn.metrics.pairwise.euclidean_distances 创建距离矩阵时，这会导致我的大型数据集出现内存错误。执行此操作的有效、内存保守的方式是什么？我已经意识到这个距离矩阵的计算是导致聚类算法出现问题的原因，所以我希望能够通过截断输入数组来避免计算这么大的距离矩阵。

Answer 1

根据维度数 n、点数 N、每个维度中问题的大小 L 以及您可接受的分隔距离 d，一种选择是将您的空间划分为维度 d 的框并最多保留每个网格框中的一个点。内存需求将从 O(N^2) 变为 O((L/d)^n)，运行时间将从 O(N^2) 变为 O(N + (L/d)^n)，因此如果 L/d 和 n 不太大，它可能会更有效。

或者，使用以下算法可能是实用的

 for each point p in points
   for each point q in points
     if p <> q and p.dist(q) < Dmin
       q.delete

这应该是 O(N^2) 的运行时间和 O(0) 的额外内存。