@@ -1,21 +1,57 @@
-- Алгоритм k-средних (k-means)
+= Алгоритм k-средних 
 
-Простейший алгоритм кластеризации (деления данных на относительно однородные группы).
+----
+	1 Картинка: http://rextester.com/CMTMO13832 (старый вариант)
+	1 Картинка: http://rextester.com/ZNO68353 (новый вариант)
+----
+
+Простейший алгоритм кластеризации ‒ 
+деления данных на относительно однородные группы, т. н. кластеры. 
+Алгоритм $$k$$-средних делит имеющиеся данные на заданное число групп (кластеров) $$k$$.
+Алгоритм стремится минимизировать сумму квадратов расстояний от точек кластеров до центров кластеров. Алгоритм гарантирует только локальный, но не глобальный оптимум.
 
-Алгоритм k-средних делит имеющиеся данные на заданное число групп $$k.$$
+Алгоритм является частным случаем АлгоритмEM.
 
 - Описание алгоритма
 
 -- Шаг 0
 
-Выбирается число групп $$k > 2.$$
+Задаётся число групп $$k >= 2.$$
 
 -- Шаг 1
 
-Случайно выбираются $$k$$ точек, которые назначаются начальными центрами масс: $$M sub 1 (x sub 1 , y sub 1 ), M sub 2 (x sub 2 , y sub 2 ), ldots , M sub k (x sub k , y sub k ).$$
+Случайно выбираются $$k$$ точек,
+которые назначаются начальными центрами масс кластеров:
+$$M sub 1 (x sub 1 , y sub 1 ),$$
+$$M sub 2 (x sub 2 , y sub 2 ),$$
+$$ldots , M sub k (x sub k , y sub k )$$.
+
+-- Шаг 2
+
+Проводится начальное разбиение на кластеры.
+Точка принадлежит тому кластеру,
+расстояние до центра масс которого будет наименьшим.
+
+-- Шаг 3
+
+Происходит вычисление нового центра масс каждого кластера.
+Затем все точки заново разбиваются на кластеры по тому же правилу, 
+что и в шаге 2.
+Эта процедура завершается тогда,
+когда после очередного пересчёта текущий центр масс совпадает с предыдущим.
 
 - Недостатки алгоритма
 
+	1 Алгоритму необходимо указывать число кластеров. Самостоятельно он не может вычислить их оптимальное количество.
+	1 Алгоритм неустойчив: результат работы алгоритма зависит от начального выбора центров масс. Два разных выбора почти всегда дадут два разных результата. Задача начального оптимального выбора начальных центров масс (в модификациях алгоритма k-средних) может быть значительно сложнее, чем сама процедура кластеризации. Это напоминает СимплексМетод, в котором задача поиска базисного плана может быть сопоставима по сложности (а иногда и сложнее), чем сам обход вершин выпуклого многогранника. 
+	1 Алгоритм не гарантирует глобального минимума, только локальный. Подобные алгоритмы называются «жадными».
+
 - Модификации алгоритма
 
+Все модификации алгоритма можно свести к следующим улучшениям:
+
+	1 Поиск начального оптимального выбора центров масс. Допустим, мы хотим выбрать начальные центры масс таким образом, чтобы сумма расстояний между точками была наибольшей. Если у нас $$n = 2000$$ наблюдений и мы хотим разбить данные на $$k = 3$$ кластера, то число возможных вариантов разбиения будет равно $$C sub n sup k$$ (числу сочетаний из $$n$$ по $$k$$): $$ C sub n sup k = size -2 { n! } over size -2 {k!(n - k)!} = size -2 { 2000! } over size -2 {3!(2000-3)!} = size -2 2000! over size -2 {3!1997!} approx 1","3 cdot 10 sup 9$$ вариантов. Поэтому для выбора оптимальных начальных центров масс используют иные методы, например, МетодГрадиентногоСпуска и его вероятностные (стохастические) модификации.
+	1 Изменение алгоритма, по которому считаются расстояния (с обычного евклидового расстояния до, например, суммы средних по разнице координат, т. н. «расстояние городских кварталов»).
+	1 Различные процедуры поиска оптимального числа кластеров (обычно такие процедуры опираются на вероятностные методы).
+
 # КатегорияПрикладнаяМатематика | КатегорияАлгоритмы