Как можно реализовать алгоритм K-Means ++?

У меня проблемы с полным пониманием алгоритма K-Means ++. Меня интересует, как именно выбираются первые центроиды k, а именно инициализация, как и остальные, как в оригинальном алгоритме K-средних.

Используется ли функция вероятности на основе расстояния или гауссова?
В то же время самая длинная дальняя точка (от других центроидов) выбрана для нового центроида.

Буду признателен пошаговое объяснение и пример. То, что в Википедии, недостаточно ясно. Также очень хорошо прокомментированный исходный код также поможет. Если вы используете 6 массивов, пожалуйста, сообщите нам, какой из них предназначен для чего.

Ответы

Ответ 1

Интересный вопрос Спасибо за то, что вы обратили мое внимание на этот документ - K-Means ++: Преимущества тщательного посева

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

Вот одномерный пример. Наши наблюдения [0, 1, 2, 3, 4]. Пусть первый центр, c1, равен 0. Вероятность того, что следующий центр кластера, c2, равен x, пропорциональна ||c1-x||^2. Итак, P (c2 = 1) = 1a, P (c2 = 2) = 4a, P (c2 = 3) = 9a, P (c2 = 4) = 16a, где a = 1/(1 + 4 + 9 + 16).

Предположим, с2 = 4. Тогда P (c3 = 1) = 1a, P (c3 = 2) = 4a, P (c3 = 3) = 1a, где a = 1/(1 + 4 + 1).

Я кодировал процедуру инициализации в Python; Я не знаю, поможет ли это вам.

def initialize(X, K):
    C = [X[0]]
    for k in range(1, K):
        D2 = scipy.array([min([scipy.inner(c-x,c-x) for c in C]) for x in X])
        probs = D2/D2.sum()
        cumprobs = probs.cumsum()
        r = scipy.rand()
        for j,p in enumerate(cumprobs):
            if r < p:
                i = j
                break
        C.append(X[i])
    return C

ОБНОВЛЕНИЕ с уточнением: Вывод cumsum дает нам границы для разбиения интервала [0,1]. Эти перегородки имеют длину, равную вероятности выбора соответствующей точки в качестве центра. Итак, поскольку r выбирается равномерно между [0,1], он попадает точно в один из этих интервалов (из-за break). Цикл for проверяет, в каком разделе r находится.

Пример:

probs = [0.1, 0.2, 0.3, 0.4]
cumprobs = [0.1, 0.3, 0.6, 1.0]
if r < cumprobs[0]:
    # this event has probability 0.1
    i = 0
elif r < cumprobs[1]:
    # this event has probability 0.2
    i = 1
elif r < cumprobs[2]:
    # this event has probability 0.3
    i = 2
elif r < cumprobs[3]:
    # this event has probability 0.4
    i = 3

Ответ 2

Один лайнер.

Скажем, нам нужно выбрать 2 центра кластеров, вместо того, чтобы выбирать их все случайным образом (как мы это делаем простым k средним), мы выберем первый случайным образом, а затем найдем точки, наиболее удаленные от первого центра {Эти точки, скорее всего, делают не принадлежат первому кластерному центру, так как они находятся далеко от него}, и назначьте второй кластерный центр рядом с этими дальними точками.

Ответ 3

Я подготовил полную реализацию k-средств ++ на основе книги "Коллективный разум" Тоби Сегарана и инициализации k-menas ++, представленной здесь.

Действительно, здесь есть две функции расстояния. Для начальных центроидов стандартный используется на основе numpy.inner, а затем для фиксации центроидов используется Pearson. Возможно, Pearson можно также использовать для начальных центроидов. Говорят, это лучше.

from __future__ import division

def readfile(filename):
  lines=[line for line in file(filename)]
  rownames=[]
  data=[]
  for line in lines:
    p=line.strip().split(' ') #single space as separator
    #print p
    # First column in each row is the rowname
    rownames.append(p[0])
    # The data for this row is the remainder of the row
    data.append([float(x) for x in p[1:]])
    #print [float(x) for x in p[1:]]
  return rownames,data

from math import sqrt

def pearson(v1,v2):
  # Simple sums
  sum1=sum(v1)
  sum2=sum(v2)

  # Sums of the squares
  sum1Sq=sum([pow(v,2) for v in v1])
  sum2Sq=sum([pow(v,2) for v in v2])    

  # Sum of the products
  pSum=sum([v1[i]*v2[i] for i in range(len(v1))])

  # Calculate r (Pearson score)
  num=pSum-(sum1*sum2/len(v1))
  den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
  if den==0: return 0

  return 1.0-num/den

import numpy
from numpy.random import *

def initialize(X, K):
    C = [X[0]]
    for _ in range(1, K):
        #D2 = numpy.array([min([numpy.inner(c-x,c-x) for c in C]) for x in X])
        D2 = numpy.array([min([numpy.inner(numpy.array(c)-numpy.array(x),numpy.array(c)-numpy.array(x)) for c in C]) for x in X])
        probs = D2/D2.sum()
        cumprobs = probs.cumsum()
        #print "cumprobs=",cumprobs
        r = rand()
        #print "r=",r
        i=-1
        for j,p in enumerate(cumprobs):
            if r 0:
        for rowid in bestmatches[i]:
          for m in range(len(rows[rowid])):
            avgs[m]+=rows[rowid][m]
        for j in range(len(avgs)):
          avgs[j]/=len(bestmatches[i])
        clusters[i]=avgs

  return bestmatches

rows,data=readfile('/home/toncho/Desktop/data.txt')

kclust = kcluster(data,k=4)

print "Result:"
for c in kclust:
    out = ""
    for r in c:
        out+=rows[r] +' '
    print "["+out[:-1]+"]"

print 'done'

data.txt: