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

Estoy teniendo problemas para entender completamente el algoritmo k-means++. Me interesa exactamente cómo se escogen los primeros k centroides (el resto es como en los k-means originales).

  1. ¿Se usa la función de probabilidad basada en la distancia o gaussiana?
  2. Al mismo tiempo, el punto más lejano (de los otros centroides) es elegido para un nuevo centroide.

Apreciaré 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 matrices, por favor díganos cuál es para qué.

Author: Steve Tjoa, 2011-03-29
Source

3 answers

Pregunta Interesante. Gracias por traer este documento a mi atención. Enlace PDF aquí del artículo original.

En términos simples, los centros de clúster se eligen inicialmente al azar del conjunto de vectores de observación de entrada, donde la probabilidad de elegir el vector x es alta si x no está cerca de ningún centro elegido previamente.

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

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

He codificado el procedimiento de inicialización en Python; no se 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

EDITAR con aclaración: La salida de cumsum nos da límites para particionar el intervalo [0,1]. Estas particiones longitud igual a la probabilidad de que el punto correspondiente sea elegido como centro. Entonces, puesto que r se elige uniformemente entre [0,1], caerá exactamente en uno de estos intervalos (debido a break). El bucle for comprueba en qué partición r se encuentra.

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
 46
Author: Steve Tjoa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-29 15:18:22

He preparado una implementación de código fuente completa de k-means++ basada en el libro "Inteligencia colectiva" de Toby Segaran y la inicialización de k-menas++ proporcionada aquí.

De hecho hay dos funciones de distancia aquí. Para los centroides iniciales se utiliza un estándar basado en numpy.interior y luego para la fijación del centroide se utiliza el Pearson one. Tal vez el Pearson uno también se puede utilizar 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: {[1]}

 3
Author: Anton Andreev,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-04 15:54:36

Un revestimiento.

Digamos que necesitamos seleccionar 2 centros de clúster, en lugar de seleccionarlos todos aleatoriamente{como hacemos en simples k significa}, seleccionaremos el primero aleatoriamente, luego encontraremos los puntos que están más lejos del primer centro{Estos puntos probablemente no pertenecen al primer centro de clúster ya que están lejos de él} y asignaremos el segundo centro de clúster cerca de esos puntos lejanos.

 2
Author: rollthedice32,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-04-07 05:48:38