Тот же результат из K-средств и последовательных K-средних?

Question

Получаем ли мы такой же результат, если применим K-средства и последовательные методы K-методов к одному набору данных с теми же начальными настройками? Объясните свои причины.

Лично я думаю, что ответ №. Результат, полученный последовательными К-средствами, зависит от порядка представления точек данных. И конечное условие не одно и то же.

Здесь крепится псевдокод двух алгоритмов кластеризации.

К-означает

Make initial guesses for the means m1, m2, ..., mk 
Until there is no change in any mean 
    Assign each data point to the cluster whose mean is the nearest. 
    Calculate the mean of each cluster. 
    For i from 1 to k 
     Replace mi with the mean of all examples for cluster i. 
    end_for 
end_until 

Последовательный К-означает

Make initial guesses for the means m1, m2, ..., mk 
Set the counts n1, n2, ..., nk to zero 
Until interrupted 
    Acquire the next example, x 
    If mi is closest to x 
     Increment ni 
     Replace mi by mi + (1/ni)*(x - mi) 
    end_if 
end_until 

Answer 1

Правильно, результаты могут быть разными.

Точки: x1 = (0,0), x2 = (1,1), x3 = (0,75,0), x4 = (0,25,1); m1 = (0,0,5), m2 = (1,0,5). K-означает присваивает x1 и x4 кластеру m1, x2 и x3 в m2-кластер. Новые средства: m1 '= (0.125,0.5) и m2' = (0.875,0.5), и переназначение не происходит. При последовательном K-средстве, после назначения x1, m1 перемещается в (0,0), x2 перемещается m2 в (1,1). Тогда m1 является самым близким к x3, поэтому m1 переходит в (0,375,0). Наконец, m2 ближе всего к x4, поэтому m2 переходит в (0,625,1). Это снова стабильная конфигурация.