18c0693f

Описание алгоритма


  1. Первоначальное распределение объектов по кластерам.

    Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому кластеру соответствует один центр.

    Выбор начальных центроидов может осуществляться следующим образом:

    • выбор k-наблюдений для максимизации начального расстояния;
    • случайный выбор k-наблюдений;
    • выбор первых k-наблюдений.

    В результате каждый объект назначен определенному кластеру.

  2. Итеративный процесс.

    Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.

    Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:

    • кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;
    • число итераций равно максимальному числу итераций.

    На рис. 14.1 приведен пример работы алгоритма k-средних для k, равного двум.


Рис. 14.1.  Пример работы алгоритма k-средних (k=2)

Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.