python - Numpy - 聚类 - 距离 - 向量化

Question

我使用 sklearn Kmeans 对一个数据样本(400 k 个样本，维度 = 205、200 个簇)进行了聚类。

我想知道，对于每个集群，集群中心与集群最远样本之间的最大距离，以便了解集群的“大小”。这是我的代码:

import numpy as np
import scipy.spatial.distance as spd
diam = np.empty([200])
for i in range(200):
    diam[i] = spd.cdist(seed[np.newaxis, i, 1:], data[data[:, 0]==i][:,1:]).max()

“种子”是聚类中心(200x206)。 “seed”的第一列包含簇内样本的数量(此处无关紧要)。

“数据”是样本 (400kx206)。数据的第一列包含簇号。

问题:这是使用循环完成的(不是那么“numpy”)。是否可以对其进行“矢量化”？

Answer 1

我们可以更智能地编制索引并节省约 4 倍的成本。

首先让我们构建一些正确形状的数据:

seed = np.random.randint(0, 100, (200,206))
data = np.random.randint(0, 100, (4e5,206))
seed[:, 0] = np.arange(200)
data[:, 0] = np.random.randint(0, 200, 4e5)
diam = np.empty(200)

原回答时间:

%%timeit
for i in range(200):
    diam[i] = spd.cdist(seed[np.newaxis, i, 1:], data[data[:, 0]==i][:,1:]).max()

1 loops, best of 3: 1.35 s per loop

moarningsun的回答:

%%timeit
seed_repeated = seed[data[:,0]]
dist_to_center = np.sqrt(np.sum((data[:,1:]-seed_repeated[:,1:])**2, axis=1))
diam = np.zeros(len(seed))
np.maximum.at(diam, data[:,0], dist_to_center)

1 loops, best of 3: 1.33 s per loop

Divakar 的回答:

%%timeit
data_sorted = data[data[:, 0].argsort()]
seed_ext = np.repeat(seed,np.bincount(data_sorted[:,0]),axis=0)
dists = np.sqrt(((data_sorted[:,1:] - seed_ext[:,1:])**2).sum(1))
shift_idx = np.append(0,np.nonzero(np.diff(data_sorted[:,0]))[0]+1)
diam_out = np.maximum.reduceat(dists,shift_idx)

1 loops, best of 3: 1.65 s per loop

正如我们所看到的，除了更大的内存占用之外，矢量化解决方案并没有真正获得任何好处。为避免这种情况，我们需要返回到原始答案，这确实是做这些事情的正确方法，而是尝试减少索引量:

%%timeit
idx = data[:,0].argsort()
bins = np.bincount(data[:,0])
counter = 0
for i in range(200):
    data_slice = idx[counter: counter+bins[i]]
    diam[i] = spd.cdist(seed[None, i, 1:], data[data_slice, 1:]).max()
    counter += bins[i]

1 loops, best of 3: 281 ms per loop

仔细检查答案:

np.allclose(diam, dam_out)
True

这是假设 python 循环不好的问题。他们通常是，但并非在所有情况下。