2.6. Агломеративный иерархический алгоритм кластер-анализа

Общая схема всех алгоритмов: формируется последовательность порогов , которая связана с построением дерева кластеризации. Начинается с кластеризации, при которой каждая точка есть отдельный кластер.

На первом шаге объединяются те точки, мера близости которых не превышает , т.е.

.
На втором шаге объединяются те, у которых порог близости не превышает и т.д. до тех пор пока все точки не объединятся в один класс, или на определенном уровне число кластеров будет стабилизировано, и при этом все точки внутри класса удовлетворяют порогу .

Прежде всего, для построения правила останова будет использовано понятие минимального дистанционного разбиения , где e-эталон.

и при этом следующий шаг


Разбиение называется несмещенным, если это разбиение с точностью до множества меры нуль совпадает с минимальным дистанционным разбиением порождаемым векторами средних

где - совокупность точек, принадлежащих ; - число точек в .

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

  1. определены оценки средних
  2. наибольшее внутрикластерное расстояние на множестве кластеров меньше наименьшего межкластерного расстояния, то есть
    где - расстояние между точками одного кластера:
    - расстояние между разными кластерами.
    может быть определено разными способами:
    1. как максимальное расстояние между парой точек из этих кластеров:
    2. как расстояние между центрами кластеров: , , аналогично.

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

Начальный этап

Заданы последовательность , начальный набор средних , где , i=1..N. Начальное разбиение , где , i=1..N, .

1-ая итерация:

  1. Определим разбиение путем отыскания точек , ближайших к центру , и их объединения в один класс.


    (1)

    до тех пор пока не получится:
    - число кластеров полученных на 1-ой итерации.

  2. Вычисляем центры новых кластеров

На 2-ой итерации объединяем соседние кластеры, расстояние между которыми

r-ая итерация (r>1):

  1. Последовательно по рекуррентным формулам находим новое разбиение путем слияния ближайших кластеров и их центры (переменные r-го уровня иерархии).


       (2)

    - число кластеров, полученных на r-ой итерации.

  2. Вычисляем переменные r-го уровня иерархии (центры)
    (3)

Продолжаем выполнять итерации до тех пор, пока не начнут выполнятся условие (то есть, когда расстояние между каждой парой кластеров не станет )

Лемма Пусть для заданного кластера внутрикластерное расстояние (максимальному пороговому значению), тогда при реализации алгоритма суммы отклонений текущих средних (центров кластеров) на r-той итерации от некоторых истинных эталонных значений кластеров, которое определяется следующим образом:

( - число кластеров, полученных на r-ой итерации)
строго убывает, то есть , и начиная с некоторого номера становится равной нулю, т.е. .

Следствием этой леммы является теорема, устанавливающая достаточное условие сходимости к несмещенному разбиению .

Теорема: Пусть выборка допускает правильную кластеризацию относительно множества , где - центр кластера , причем максимальное пороговое значение находится в следующих пределах , где - максимальное внутрикластерное расстояние, а - минимальное межкластерное расстояние при данном разбиении.
Тогда этот алгоритм за конечное число шагов сходится к несмещенному разбиению , а центры независимо от выбора значений .

REM (здесь основным является выбор )

Если выборка не допускает правильной кластеризации, то данный алгоритм сходится к кластеризации , в которой заданные центры классов являются наиболее представительными.