K-means ++ algorytm

Question

czytam gazetę k-means++: The Advantages of Careful Seeding i nie bardzo rozumiem algorytmu przewidzianego która jest:

„Niech D (x) oznacza najkrótszą odległość od punktu danych X do najbliższego centrum już mamy wybrany.

1a. wybrać początkowe centrum c1 równomiernie losowo z X.

1b. Wybór następnego środkowego cl, wybierając CI = x '∈ x z prawdopodobieństwem (D (x')^2)/Sum_of (D (x)^2)

1 do. Powtarzaj krok 1b, dopóki nie wybraliśmy w sumie k centrów.

2-4. Należy postępować zgodnie ze standardową K oznacza algorytm „

(lepiej przyjrzeć algorytmu w linku powyżej)

zwłaszcza kroku 1b. Co one oznaczają przez” wybierając CI = x”∈ X z prawdopodobieństwem (D (x ')^2)/Sumof (D (x)^2) "Czy chodzi o wybór elementu, który ma największą proporcję? A w jaki sposób wykonanie takich obliczeń może doprowadzić do wyboru optymalnych centroidów?

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

Funkcja D (x) jest zdefiniowany dla wszystkich punktów x ∈ X.

W kroku 1b musimy wybrać punkt, który będzie nowym centrum. Będziemy wybierać losowo pomiędzy wszystkimi punktami (które nie są już centrami). Ale nie damy równej szansy na każdy punkt; przed dokonaniem wyboru przydzielimy różne prawdopodobieństwa do różnych punktów. Te prawdopodobieństwa muszą wynosić 1.

Rozważyć D (x)^2. Możemy to ocenić w każdym punkcie i zsumować wartości: Sum_of (D (x)^2).

Następnie możemy przypisać każdemu punktowi x 'prawdopodobieństwo równe D (x')^2/Sum_of (D (x)^2). Te prawdopodobieństwa dają maksymalnie 1 i dają większą szansę na punkty daleko od wszystkich istniejących centrów.