我已经在 python 中实现了 k-means 聚类算法,现在我想用我的算法得到的聚类来标记新数据。我的方法是遍历每个数据点和每个质心以找到最小距离和与之关联的质心。但我想知道是否有更简单或更短的方法来做到这一点。
def assign_cluster(clusterDict, data):
clusterList = []
label = []
cen = list(clusterDict.values())
for i in range(len(data)):
for j in range(len(cen)):
# if cen[j] has the minimum distance with data[i]
# then clusterList[i] = cen[j]
其中 clusterDict 是一个字典,键作为标签,[0,1,2,....],值作为质心坐标。
有人可以帮我实现这个吗?
请您参考如下方法:
这是 numba 的一个很好的用例,因为它可以让你将其表达为一个简单的双循环而不会造成很大的性能损失,这反过来又可以让你避免使用 np.tile 的过多额外内存。跨三维复制数据只是为了以矢量化的方式进行。
从其他答案中借用标准矢量化 numpy 实现,我有这两个实现:
import numba
import numpy as np
def kmeans_assignment(centroids, points):
num_centroids, dim = centroids.shape
num_points, _ = points.shape
# Tile and reshape both arrays into `[num_points, num_centroids, dim]`.
centroids = np.tile(centroids, [num_points, 1]).reshape([num_points, num_centroids, dim])
points = np.tile(points, [1, num_centroids]).reshape([num_points, num_centroids, dim])
# Compute all distances (for all points and all centroids) at once and
# select the min centroid for each point.
distances = np.sum(np.square(centroids - points), axis=2)
return np.argmin(distances, axis=1)
@numba.jit
def kmeans_assignment2(centroids, points):
P, C = points.shape[0], centroids.shape[0]
distances = np.zeros((P, C), dtype=np.float32)
for p in range(P):
for c in range(C):
distances[p, c] = np.sum(np.square(centroids[c] - points[p]))
return np.argmin(distances, axis=1)
然后对于一些样本数据,我做了一些时序实验:
In [12]: points = np.random.rand(10000, 50)
In [13]: centroids = np.random.rand(30, 50)
In [14]: %timeit kmeans_assignment(centroids, points)
196 ms ± 6.78 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [15]: %timeit kmeans_assignment2(centroids, points)
127 ms ± 12.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
我不会说 numba 版本肯定比 np.tile 快版本,但显然它非常接近,同时不会产生 np.tile 的额外内存成本。 .
事实上,我注意到在我的笔记本电脑上,当我将形状变大并使用 (10000, 1000) 作为 points 的形状时和 (200, 1000) 对于 centroids 的形状, 然后 np.tile生成了一个 MemoryError ,同时 numba函数在 5 秒内运行且没有内存错误。
另外,我实际上注意到使用 numba.jit 时速度变慢了在第一个版本上(使用 np.tile ),这可能是由于在 jitted 函数内创建了额外的数组,再加上当您已经调用所有矢量化函数时,没有多少 numba 可以优化这一事实。
而且在尝试使用广播来缩短代码时,我也没有注意到第二个版本有任何显着改进。例如。将双循环缩短为
for p in range(P):
distances[p, :] = np.sum(np.square(centroids - points[p, :]), axis=1)
并没有真正帮助任何事情(并且在所有 points[p, :] 中重复广播 centroids 时会使用更多内存)。
这是 numba 的真正好处之一。您真的可以以一种非常直接的、基于循环的方式编写算法,这种方式符合算法的标准描述,并允许更好地控制语法如何解包到内存消耗或广播中……所有这些都不会放弃运行时性能。
