python - K-Means:将集群分配给新数据点

我已经在 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 函数中创建了额外的数组，再加上当您已经调用 all 时，没有多少 numba 可以优化向量化函数。

而且我在尝试使用广播来缩短代码时也没有注意到第二个版本的任何显着改进。例如。将双循环缩短为

for p in range(P):
    distances[p, :] = np.sum(np.square(centroids - points[p, :]), axis=1)

并没有真正帮助任何东西(并且在所有 points[p, :] 中重复广播 centroids 时会使用更多内存)。

这是 numba 的真正好处之一。你真的可以用一种非常简单的、基于循环的方式来编写算法，这种方式符合算法的标准描述，并允许更好地控制语法如何解包到内存消耗或广播......所有这些都不会放弃运行时性能。

关于python - K-Means:将集群分配给新数据点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49869287/

Numba

python - K-Means:将集群分配给新数据点