K-средства ++ алгоритм

Question

Я прочитал газету k-means++: The Advantages of Careful Seeding и не совсем понятно, алгоритм при условии, которое:

«Пусть D (х) обозначим кратчайшее расстояние от точки данных х до ближайшего центра мы уже выбраны.

1a. Выберите начальный центр равномерно c1 при случайном из X.

1b. Выберите следующий центр CI, выбирая Ci = х '∈ X с вероятностью (D (х')^2)/Sum_of (D (x)^2)

1 с. Повторите шаг 1b, пока мы не выбрали всего k центров.

2-4. Действуйте со стандартными к-означает алгоритм «

(Лучше смотреть на алгоритме в приведенной выше ссылке)

Тем шаг 1b. Что они означают» выбрать Ci = х»∈ X с вероятностью (D (x ')^2)/Sumof (D (x)^2) ». Они означают выбор элемента, который имеет наибольшую долю? И как выполнить такое вычисление может привести к выбору оптимальных центроидов?

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

Функция D (x) определен для всех точек x ∈ X.

На шаге 1b мы должны выбрать точку, которая будет новым центром. Мы будем выбирать случайным образом между всеми точками (которые не являются центрами). Но мы не будем давать равных шансов каждому моменту; мы будем назначать разные вероятности для разных точек до того, как мы выберем. Эти вероятности должны составлять до 1.

Рассмотрим D (x)^2. Мы можем оценить это в каждой точке и добавить значения: Sum_of (D (x)^2).

Тогда мы можем присвоить каждой точке x 'вероятность, равную D (x')^2/Sum_of (D (x)^2). Эти вероятности составляют до 1 и дают больше шансов на удаленные точки от всех существующих центров.