Как именно работает k-means ++? - PullRequest
Новая
       2

Как именно работает k-means ++?

36 голосов
/ 29 марта 2011

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

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

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

Ответы [ 3 ]

60 голосов
/ 29 марта 2011

Интересный вопрос.Спасибо, что обратили мое внимание на эту статью. Ссылка на PDF здесь оригинальной статьи.

Проще говоря, центры кластеров первоначально выбираются случайным образом из набора входных векторов наблюдений, где высока вероятность выбора вектора 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).

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

I 'мы кодировали процедуру инициализации в 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
6 голосов
/ 03 сентября 2017

Один лайнер.

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

3 голосов
/ 04 апреля 2011

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

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

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: <pre> p1 1 5 6 p2 9 4 3 p3 2 3 1 p4 4 5 6 p5 7 8 9 p6 4 5 4 p7 2 5 6 p8 3 4 5 p9 6 7 8

...