k-means ++ подходит для больших данных? - PullRequest
Новая
       7

k-means ++ подходит для больших данных?

0 голосов
/ 03 мая 2018

Я использовал этот Python-код k-means ++ для инициализации k центров, но он очень длинный для больших данных, например, 400000 точек 2 измерения: 

class KPlusPlus(KMeans):
def _dist_from_centers(self):
    cent = self.mu
    X = self.X
    D2 = np.array([min([np.linalg.norm(x-c)**2 for c in cent]) for x in X])
    self.D2 = D2

def _choose_next_center(self):
    self.probs = self.D2/self.D2.sum()
    self.cumprobs = self.probs.cumsum()
    r = random.random()
    ind = np.where(self.cumprobs >= r)[0][0]
    return(self.X[ind])

def init_centers(self):
    self.mu = random.sample(self.X, 1)
    while len(self.mu) < self.K:
        self._dist_from_centers()
        self.mu.append(self._choose_next_center())

def plot_init_centers(self):
    X = self.X
    fig = plt.figure(figsize=(5,5))
    plt.xlim(-1,1)
    plt.ylim(-1,1)
    plt.plot(zip(*X)[0], zip(*X)[1], '.', alpha=0.5)
    plt.plot(zip(*self.mu)[0], zip(*self.mu)[1], 'ro')
    plt.savefig('kpp_init_N%s_K%s.png' % (str(self.N),str(self.K)), \
                bbox_inches='tight', dpi=200)

Есть ли способ ускорить k-means ++?

Ответы [ 3 ]

0 голосов
/ 04 мая 2018

K-означает, что для инициализации ++ требуется O (n * k). Это достаточно быстро для малых k и больших n, но если вы выберете k слишком большое, это займет некоторое время. Это примерно так же дорого, как одна итерация (медленного) варианта Ллойда, поэтому, как правило, использование kmeans ++ окупается.

Ваша реализация хуже, по крайней мере, O (n * k²), потому что она выполняет ненужные пересчеты. И он, вероятно, всегда выбирает ту же точку, что и следующий центр.

Обратите внимание, что у вас также есть только инициализация, но не фактические значения kmeans.

0 голосов
/ 15 мая 2018

Я еще не проводил никаких экспериментов, но Scalable K-Means ++ кажется довольно хорошим для очень больших наборов данных (возможно, для тех, которые даже больше, чем вы описываете). Вы можете найти статью здесь и другой пост, объясняющий ее здесь .

К сожалению, я не видел ни одного кода, которому бы доверял ...

0 голосов
/ 03 мая 2018

Первоначальный посев оказывает большое влияние на время выполнения k-средних. В этом посте вы можете найти несколько стратегий, чтобы ускорить его.

Возможно, вы могли бы подумать об использовании варианта Сиднеша Хандельвала K-средних , который был опубликован в материалах Европейской конференции по поиску информации (ECIR 2017). Siddhesh предоставил реализацию Python в GitHub , и она сопровождается некоторыми другими предыдущими эвристическими алгоритмами.

...