K-means ++ algoritmo

Question

ho letto il giornale k-means++: The Advantages of Careful Seeding e non ho ben capito l'algoritmo a condizione che:

"Sia D (x) denota la distanza più breve da un punto di dati x per il centro più vicino che abbiamo già prescelto.

1a. Scegliere un centro iniziale C1 uniformemente a caso da X.

1b. Scegliere il prossimo centro ci, selezionando ci = x '∈ x con probabilità (D (x')^2)/Sum_of (D (x)^2)

1 c. Ripeti il ​​passaggio 1b fino a quando non abbiamo scelto un totale di k centri.

2-4. Procedere come con lo standard algoritmo k-means "

(meglio guardare l'algoritmo nel link qui sotto)

Soprattutto passaggio 1b. Che cosa si intende per" selezionando ci = x' ∈ X con probabilità (D (x ')^2)/Sumof (D (x)^2). "Significa selezionare l'elemento che ha la maggior proporzione? E come può eseguire tale calcolo può portare a selezionare i centroidi ottimali?

Answer 1

http://en.wikipedia.org/wiki/K-means%2B%2B

1. Choose one center uniformly at random from among the data points. 
    2. For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen. 
    3. Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to D(x)2. 
    4. Repeat Steps 2 and 3 until k centers have been chosen. 
    5. Now that the initial centers have been chosen, proceed using standard k-means clustering. 

Answer 2

La funzione D (x) è definito per tutti i punti x ∈ X.

Nel passo 1b, dobbiamo scegliere un punto per essere un nuovo centro. Sceglieremo casualmente tra tutti i punti (che non sono già centri). Ma non daremo una possibilità uguale ad ogni punto; Assegneremo diverse probabilità a diversi punti prima di scegliere. Queste probabilità devono sommarsi a 1.

Considerare D (x)^2. Possiamo valutarlo in ogni punto e sommare i valori: Sum_of (D (x)^2).

Quindi possiamo assegnare ogni punto x 'una probabilità uguale a D (x')^2/Sum_of (D (x)^2). Queste probabilità si sommano fino a 1 e danno una migliore possibilità a punti lontani da tutti i centri esistenti.