Оптимизация среднего значения в питоне

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

Это на самом деле не работает, но вы думаете, это может работать с некоторыми настройками?

Answer 1

Алгоритм K-средних уже реализован в 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.Поскольку алгоритм, который вы опубликовали, хранит данные за продиктованным (self.clusters) и поиском атрибутов (.points), вы вынуждены использовать медленный цикл Python, чтобы просто получить ваши данные.Основное увеличение скорости может быть достигнуто за счет прилипания с массивами.Посмотрите scipy реализацию кластеризации k-средних для идей по лучшей структуре данных.

Answer 2

Дорогая часть вашей функции - это, безусловно, итерация по точкам.Избегайте его вообще, сделав self.clusters[label].points сам массив-пустышку, а затем вычислите среднее значение непосредственно на нем.Например, если точки содержат координаты X и Y, объединенные в одномерный массив:

points = self.clusters[label].points
x_mean = numpy.mean(points[0::2])
y_mean = numpy.mean(points[1::2])

Answer 3

Почему бы не избежать создания дополнительных массивов?

def updateCentroid(self, label):
  sumX=0; sumY=0
  N = len( self.clusters[label].points)
  for point in self.clusters[label].points:
    sumX += point.x
    sumY += point.y
  self.clusters[label].centroid.x = sumX/N
  self.clusters[label].centroid.y = sumY/N

Answer 4

Хорошо, я нашел решение с скользящей средней, которое быстро без изменения структуры данных:

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

Это уменьшило время вычисления (для всего алгоритма k означает) до 13% от исходного =)

Спасибо всем за отличное понимание!

Answer 5

Возможно, добавленные функции numpy's mean добавляют немного накладных расходов.

>>> def myMean(itr):
...   c = t = 0
...   for item in itr:
...     c += 1
...     t += item
...   return t / c
...
>>> import timeit
>>> a = range(20)
>>> t1 = timeit.Timer("myMean(a)","from __main__ import myMean, a")
>>> t1.timeit()
6.8293311595916748
>>> t2 = timeit.Timer("average(a)","from __main__ import a; from numpy import average")
>>> t2.timeit()
69.697283029556274
>>> t3 = timeit.Timer("average(array(a))","from __main__ import a; from numpy import average, array")
>>> t3.timeit()
51.65147590637207
>>> t4 = timeit.Timer("fromiter(a,npfloat).mean()","from __main__ import a; from numpy import average, fromiter,float as npfloat")
>>> t4.timeit()
18.513712167739868

Похоже, лучшая производительность numpy достигается при использовании fromiter.

Answer 6

Без дополнительных списков:

def updateCentroid(self, label):
    self.clusters[label].centroid.x = numpy.fromiter(point.x for point in self.clusters[label].points, dtype = np.float).mean()
    self.clusters[label].centroid.y = numpy.fromiter(point.y for point in self.clusters[label].points, dtype = np.float).mean()

Answer 7

Один из способов - добавить x_sum и y_sum к вашему объекту "скоплений" и суммировать координаты по мере добавления точек.Если что-то движется, вы также можете обновить сумму по мере движения очков.Тогда получение центроида - это просто деление x_sum и y_sum на количество точек.Если ваши точки являются сложными векторами, которые можно добавить, вам даже не нужно суммировать компоненты, просто сохраняйте сумму всех векторов и умножайте на 1 / len в конце.

Answer 8

Это проблема с профилировщиками, которые говорят только о функциях. Это метод, который я использую , и он определяет дорогостоящие строки кода, включая точки, где вызываются функции.

Тем не менее, существует общая идея, что структура данных свободна. Как спросил @ Michael-Anderson, почему бы не избежать создания массива? Это первое, что я увидел в вашем коде, что вы строите массивы, добавляя их. Вам не нужно.

Answer 9

Попробуйте это:

def updateCentroid(self, label):

    self.clusters[label].centroid.x = numpy.array([point.x for point in self.clusters[label].points]).mean()
    self.clusters[label].centroid.y = numpy.array([point.y for point in self.clusters[label].points]).mean()