@@ -1,12 +1,16 @@
-- Алгоритм k-средних 
+= Алгоритм k-средних 
 
-Простейший алгоритм кластеризации (деления данных на относительно однородные группы — т. н. кластеры).
+----
+	1 Картинка: http://rextester.com/CMTMO13832 (старый вариант)
+	1 Картинка: http://rextester.com/ZNO68353 (новый вариант)
+----
+
+Простейший алгоритм кластеризации ‒ 
+деления данных на относительно однородные группы, т. н. кластеры. 
+Алгоритм $$k$$-средних делит имеющиеся данные на заданное число групп (кластеров) $$k$$.
+Алгоритм стремится минимизировать сумму квадратов расстояний от точек кластеров до центров кластеров. Алгоритм гарантирует только локальный, но не глобальный оптимум.
 
-Алгоритм k-средних делит имеющиеся данные на заданное число групп (кластеров) $$k$$.
-
-Алгоритм стремится минимизировать сумму квадратов расстояний от точек кластеров до центров кластеров.
-
-Алгоритм гарантирует только локальный, но не глобальный оптимум.
+Алгоритм является частным случаем АлгоритмEM.
 
 - Описание алгоритма
 
@@ -16,28 +20,38 @@
 
 -- Шаг 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. Эта процедура завершается тогда, когда после очередного пересчёта текущий центр масс совпадает с предыдущим.
+Происходит вычисление нового центра масс каждого кластера.
+Затем все точки заново разбиваются на кластеры по тому же правилу, 
+что и в шаге 2.
+Эта процедура завершается тогда,
+когда после очередного пересчёта текущий центр масс совпадает с предыдущим.
 
 - Недостатки алгоритма
 
 	1 Алгоритму необходимо указывать число кластеров. Самостоятельно он не может вычислить их оптимальное количество.
-	1 Результат работы алгоритма зависит от начального выбора центров масс. Два разных выбора почти всегда дадут два разных результата. Задача начального оптимального выбора начальных центров масс (в модификациях алгоритма k-средних) может быть значительно сложнее, чем сама процедура кластеризации. Это напоминает СимплексМетод, в котором задача поиска базисного плана может быть сопоставима по сложности (а иногда и сложнее), чем сам обход вершин выпуклого многогранника. 
-	1 Алгоритм не гарантирует глобального минимума, только локальный.
+	1 Алгоритм неустойчив: результат работы алгоритма зависит от начального выбора центров масс. Два разных выбора почти всегда дадут два разных результата. Задача начального оптимального выбора начальных центров масс (в модификациях алгоритма k-средних) может быть значительно сложнее, чем сама процедура кластеризации. Это напоминает СимплексМетод, в котором задача поиска базисного плана может быть сопоставима по сложности (а иногда и сложнее), чем сам обход вершин выпуклого многогранника. 
+	1 Алгоритм не гарантирует глобального минимума, только локальный. Подобные алгоритмы называются «жадными».
 
 - Модификации алгоритма
 
 Все модификации алгоритма можно свести к следующим улучшениям:
 
-	1 Поиск начального оптимального выбора центров масс. Допустим, мы хотим выбрать начальные центры масс таким образом, чтобы сумма расстояний между точками была наимбольшей. Если у нас $$n = 2000$$ наблюдений и мы хотим разбить данные на $$k = 3$$ кластера, то число возможных вариантов разбиения будет равно $$C sub n sup k$$ (числу сочетаний из $$n$$ по $$k$$): $$ C sub n sup k = n! over {k!(n - k)!} = 2000! over {3!(2000-3)!} = 2000! over {3!1997!} approx 1,3 cdot 10 sup 9$$ вариантов. Поэтому для выбора оптимального начального центра масс используют иные методы, например МетодГрадиентногоСпуска и его вероятностные (стохастические) модификации.
-	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 Различные процедуры поиска оптимального числа кластеров (обычно такие процедуры опираются на вероятностные методы).
 
 # КатегорияПрикладнаяМатематика | КатегорияАлгоритмы