Python k均值算法

Question

我在找用Python实现的k-means算法的例子，想用它来对我的坐标数据库进行分类和缓存。

Answer 1

对于连续的数据，k-means算法非常简单。

你只需要一组平均值，然后对每个数据点，找出它最接近的那个平均值，并把这个新数据点加到那个平均值上。你的平均值就代表了输入数据中最近的主要数据聚类。

我会不断地进行平均，所以不需要保留旧的数据来计算新的平均值。假设旧的平均值是k，下一个数据点是x，还有一个常数n，表示要保留多少个过去的数据点来计算平均值，那么新的平均值可以用下面的公式计算：

k*(1-(1/n)) + n*(1/n)

这里是完整的Python代码

from __future__ import division
from random import random

# init means and data to random values
# use real data in your code
means = [random() for i in range(10)]
data = [random() for i in range(1000)]

param = 0.01 # bigger numbers make the means change faster
# must be between 0 and 1

for x in data:
    closest_k = 0;
    smallest_error = 9999; # this should really be positive infinity
    for k in enumerate(means):
        error = abs(x-k[1])
        if error < smallest_error:
            smallest_error = error
            closest_k = k[0]
        means[closest_k] = means[closest_k]*(1-param) + x*(param)

你可以在所有数据处理完后直接打印出平均值，但实时观察它的变化要有趣得多。我用这个方法处理了20毫秒的声音频率包，经过一两分钟的对话，它就能为短音“a”、长音“o”和辅音“s”建立起一致的分类。真奇怪！

Answer 2

SciPy的 kmeans2() 函数在数值计算上有一些问题：之前有人报告说在0.6.0版本中出现了“矩阵不是正定的 - 不能计算Cholesky分解”的错误信息，而我在0.7.1版本中也遇到了同样的问题。

目前，我建议使用 PyCluster 来替代。下面是一个使用示例：

>>> import numpy
>>> import Pycluster
>>> points = numpy.vstack([numpy.random.multivariate_normal(mean, 
                                                            0.03 * numpy.diag([1,1]),
                                                            20) 
                           for mean in [(1, 1), (2, 4), (3, 2)]])
>>> labels, error, nfound = Pycluster.kcluster(points, 3)
>>> labels  # Cluster number for each point
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], dtype=int32)
>>> error   # The within-cluster sum of distances for the solution
1.7721661785401261
>>> nfound  # Number of times this solution was found
1

Answer 3

更新：（在这个原始回答发布十一年后，是时候更新一下了。）

首先，你确定你想用k-means算法吗？这个页面提供了一些不同聚类算法的优秀图示总结。我建议你除了看图示外，特别关注每种方法所需的参数，想想你是否能提供这些参数（比如，k-means需要你提前知道要分成多少个类，但在开始聚类之前你可能并不知道这个数字）。

这里有一些资源：

旧回答：

Scipy的聚类实现效果很好，其中包括一个k-means的实现。

还有scipy-cluster，它采用的是聚合聚类；这个方法的好处是你不需要提前决定要分成多少个类。

Python k均值算法

8 个回答

撰写回答