在python中优化均值

Question

我有一个函数,用于更新K-means算法中的质心(平均值).我运行了一个分析器,发现这个函数使用了大量的计算时间.

看起来像:

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'

PS.因为您发布的算法将数据保存在dict(self.clusters)和属性lookup(.points)后面,所以您不得不使用慢速Python循环来获取数据.通过坚持使用numpy阵列可以实现主要的速度增益.有关更好的数据结构的想法,请参阅k-means聚类的scipy实现.