Алгоритм К-средних

Метод K-средних – это метод кластерного анализа, целью которого является разделение m наблюдений на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центу (центроиду) которого оно ближе всего.

Назначение. С помощью онлайн-калькулятора можно проводить классификацию объектов методом К-средних с построением дендрограммы (например, для построения типологической группировки).

Инструкция. Укажите количество данных, нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения).
Размерность матрицы разбиения x

Алгоритм разделительной кластеризации, основан на разбиении множества элементов векторного пространства на заранее определенное число кластеров k. Метод относится к неирархическим алгоритмам кластеризации. Алгоритм представляет собой итерационную процедуру:

  1. Выбирается число кластеров k.
  2. Из исходного множества данных случайным образом выбираются k записей, которые будут служить начальными центрами кластеров.
  3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера. При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
  4. Вычисляются центроиды – центры тяжести кластеров. Каждый центроид – это вектор, элементы которого представляют собой средние значения признаков, вычисленные по всем записям кластера. Затем центр кластера смещается в его центроид.
Процесс итерации прекращается, когда границы кластеров не перестанут изменяться от итерации к итерации, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор записей.

Достоинства алгоритма k-средних:

  • простота реализации;
  • интуитивная понятность и прозрачность алгоритма;

Недостатки алгоритма k-средних:

  • число кластеров надо знать заранее;
  • зависимость результата от инициализации центров кластеров;
  • вычислительная сложность;

    Пример. Даны четыре объекта, каждый определяется двумя признаками. Разбить объекты на три кластера методом k-средних. Первоначально первые три объекта образуют начальные кластеры, метрика – квадрат евклидова расстояния: X1(2;3), Х2(3;2), Х3(7;3), Х4 (5;-3).

Открыть диалог Discus