python - 在 python 中优化均值

Question

我有一个函数可以更新 K 均值算法中的质心(均值)。我运行了一个分析器并注意到这个函数使用了大量的计算时间。

看起来像:

def updateCentroid(self, label):
    X=[]; Y=[]
    for point in self.clusters[label].points:
        X.append(point.x)
        Y.append(point.y)
    self.clusters[label].centroid.x = numpy.mean(X)
    self.clusters[label].centroid.y = numpy.mean(Y)

于是我思索，有没有更高效的方法来计算这些点的均值？如果没有，是否有更优雅的方式来制定它？ ;)

编辑:

感谢所有精彩的回复!我在想也许我可以使用类似的方法累积地计算平均值:

其中 x_bar(t) 是新平均值，x_bar(t-1) 是旧平均值。

这将导致类似于此的功能:

def updateCentroid(self, label):
    cluster = self.clusters[label]
    n = len(cluster.points)
    cluster.centroid.x *= (n-1) / n
    cluster.centroid.x += cluster.points[n-1].x / n
    cluster.centroid.y *= (n-1) / n
    cluster.centroid.y += cluster.points[n-1].y / n

它并没有真正起作用，但你认为这可以通过一些 tweeking 来起作用吗？

Answer 1

K-means 算法已在 scipy.cluster.vq 中实现.如果您尝试更改该实现的某些内容，那么我建议您先研究那里的代码:

In [62]: import scipy.cluster.vq as scv
In [64]: scv.__file__
Out[64]: '/usr/lib/python2.6/dist-packages/scipy/cluster/vq.pyc'

附言。因为您发布的算法将数据保存在 dict (self.clusters) 和属性查找 (.points) 后面，所以您被迫使用慢速 Python 循环来获取您的数据。坚持使用 numpy 数组可以显着提高速度。有关更好的数据结构的想法，请参阅 k-means 聚类的 scipy 实现。