Основы информационных технологий

§2.7. Алгоритм k-средних (k-means) 
Наиболее распространен среди неиерархических методов алгоритм k-
средних, также называемый быстрым кластерным анализом. В отличие 
от иерархических методов, которые не требуют предварительных пред-
положений относительно числа кластеров, для возможности использова-
ния этого метода необходимо иметь гипотезу о наиболее вероятном ко-
личестве кластеров. Алгоритм 
k
-средних строит 
k
кластеров, располо-
женных на возможно больших расстояниях друг от друга.
Основной тип задач, которые решает алгоритм 
k
-средних, – наличие 
предположений (гипотез) относительно числа кластеров, при этом они 
должны быть различны настолько, насколько это возможно. Выбор числа 
k
может базироваться на результатах предшествующих исследований, 
теоретических соображениях или интуиции.

---

– 52 – 
Пусть имеется 
n
объектов, и пусть задано 
k
– количество кластеров, 
которые требуется сформировать. Алгоритм разбивает объекты на 
k
групп (
k
≤ 
n
), где каждая группа представляет один кластер. Кластеры 
формируются таким образом, чтобы минимизировать некоторый крите-
рий, часто называемый функцией схожести. В алгоритме 
k
-средних 
функция схожести формируется на основе центров тяжести кластеров.
Данный алгоритм действует следующим образом: 
1) случайным образом выбираются 
k
объектов, каждый из которых 
изначально представляет центр своего кластера; 
2) каждый из оставшихся объектов сопоставляется с тем кластером, 
центр которого наиболее близок в смысле расстояния; в результате 
каждый объект принадлежит некоторому кластеру; 
3) для каждого полученного кластера заново вычисляется центр тя-
жести, и так далее. 
Данный процесс повторяется до тех пор, пока выбранный критерий 
не перестанет уменьшаться. При этом обычно используется критерий 
суммы квадратов ошибок. 
На рис.14 приведен пример работы алгоритма 
k
-средних для 
k
, рав-
ного двум. Выбор числа кластеров является сложным вопросом. Если нет 
предположений относительно этого числа, рекомендуют создать 2 кла-
стера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.