¿Cómo funciona exactamente k-means ++?

Question

Tengo problemas para comprender completamente el algoritmo k-means ++. Me interesa exactamente cómo se seleccionan los primeros k centroides (el resto es como en los k-means originales).

1. ¿La función de probabilidad se basa en la distancia o Gaussian?
2. Al mismo tiempo, se selecciona el punto distante más largo (de los otros centroides) para un nuevo centroide.

Agradeceré una explicación paso a paso y un ejemplo. El de Wikipedia no es lo suficientemente claro. También un código fuente muy bien comentado también ayudaría. Si está utilizando 6 arreglos, por favor díganos cuál es para qué.

Answer 1

Interesante pregunta. Gracias por traer este documento a mi atención. PDF link here of the original paper.

En términos simples, centros de los conglomerados se eligen inicialmente al azar a partir del conjunto de vectores de observación de entrada, donde la probabilidad de elegir vector x es alta si x no está cerca de cualquiera de los centros seleccionados previamente.

Aquí hay un ejemplo unidimensional. Nuestras observaciones son [0, 1, 2, 3, 4]. Deje que el primer centro, c1, sea 0. La probabilidad de que el siguiente centro de clúster, c2, sea x es proporcional a ||c1-x||^2. Entonces, P (c2 = 1) = 1a, P (c2 = 2) = 4a, P (c2 = 3) = 9a, P (c2 = 4) = 16a, donde a = 1/(1 + 4 + 9 + dieciséis).

Suponer c2 = 4. Entonces, P (c3 = 1) = 1a, P (c3 = 2) = 4a, P (c3 = 3) = 1a, donde a = 1/(1 + 4 + 1).

He codificado el procedimiento de inicialización en Python; No sé si esto te ayuda.

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 

edición con una aclaración: La salida de cumsum nos da límites para dividir el intervalo [0,1]. Estas particiones tienen una longitud igual a la probabilidad de que se elija el punto correspondiente como centro. Entonces, dado que r se elige uniformemente entre [0,1], caerá exactamente en uno de estos intervalos (debido a break). Los for controles de bucle para ver qué partición r es en

Ejemplo:.

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 

Answer 2

he preparado una aplicación fuente completo de k-medias ++ basadas en el libro "inteligencia colectiva" por Toby Segaran y la k - Inicialización demenos ++ proporcionada aquí.

De hecho, aquí hay dos funciones de distancia. Para los centroides iniciales se usa uno estándar basado en numpy.inner y luego para la fijación de centroides se usa el de Pearson. Quizás el Pearson uno también se puede usar para los centroides iniciales. Dicen que es mejor.

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' 

datos.txt:

 
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 

Answer 3

un trazador de líneas.Digamos que necesitamos seleccionar 2 centros de clusters, en lugar de seleccionarlos al azar {como lo hacemos en k medios} simple, seleccionaremos el primero al azar, luego buscaremos los puntos que están más alejados del primer centro {Es muy probable que estos puntos lo hagan no pertenecen al primer centro de clúster ya que están lejos de él} y asigne el segundo centro de clúster cerca de esos puntos lejanos.