Python 中的 k-means 算法

Question

我尝试为 MNIST 数据集实现 k-means 算法。但由于结果远非如此，可能存在一个（或多个）我目前没有看到的错误。代码非常简单。这是我到目前为止所做的：

import numpy as np

# Load images
I = np.load("mnist_test_images.npy").astype(float) # (10000,784)
L = np.load("mnist_test_labels.npy").astype(int) # (10000,1)

# Scale
I = 2.0*(I/255.0-0.5)

images = len(I)

# Random initialization of centers for k=10 clusters
M = np.random.randn(10,28*28)

guess = np.zeros((len(I),1))
step = 0
while (True):
    # Compute distance of every image i to the center of every cluster k
    # image i belongs to cluster with smallest distance
    for i in range(images):
        d = np.sum((M-I[i])**2,axis=1)
        guess[i] = np.argmin(d)

    # Update the centers for all clusters
    # New center is the mean of all images i which belong to cluster k
    for k in range(10):
        idx, _ = np.where(guess == k)
        if len(idx) > 0:
            M[k] = np.mean(I[idx],axis=0)

    # Test how good the algorithm works
    # Very similar to first step
    if (step % 10 == 0):
        fitness = 0
        for i in range(images):
            dist = np.sum((M-I[i])**2,axis=1)
            if L[i] == np.argmin(dist):
                fitness += 1
        print("%d" % fitness, flush=True)

    step += 1

代码看起来很简单。但是某处可能存在错误。当我测试它时，准确度从大约 10-20% 下降到 5-10% 或者几乎立即收敛，但没有达到 30% 以上。我不能承认任何学习。集群中心的随机初始化会导致这种行为吗？

谢谢！

Answer 1

问题是您将其视为一种监督学习方法，但它是无监督的。在我看来，应该避免整个 "unsupervised learning" 术语，因为它可能会产生很大的误导。事实上，我根本不会将大多数 "unsupervised" 方法称为 "learning"。

聚类不仅仅是 "unsupervised classification"。这是一项非常不同且困难得多的任务。这个任务太难了，我们甚至还不知道如何真正评估它。

我是你的情况，有几个问题：

您假设 kmeans 会找到 0 到 9 的数字。由于它是无监督的，它很可能不会。相反，它可能会发现有倾斜的数字、不同的线宽、不同种类的数字等。
您假设簇 0 对应于数字 0 来评估它。事实并非如此。簇标签没有意义。 MNIST 在这里是一个非常糟糕的选择，因为巧合的是它的 classes 也是数字。但是 kmeans 将始终使用 0 到 k-1 的标签，即使对于苹果和香蕉也是如此。
您假设评估必须随着每次迭代而变得更好。但这是无人监督的！
一个class可能包含多个簇
类可能没有标签是分不开的，这样形成一个簇
kmeans 等方法对异常值很敏感。您可能有一些非常小的集群，它们只模拟了几个坏数据点。

Python 中的 k-means 算法

k-means algorithm in Python

python

cluster-analysis

k-means