Кластерный анализ. 
Теория вероятностей и математическая статистика. 
Математические модели

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

Имеется много методов, решающих эту задачу, наиболее распространен среди них агломеративно-иерархический кластерный анализ, который последовательно объединяет наблюдения, начиная с самых близких, во все более крупные группы. Результаты этого последовательного объединения представляются в виде дендрограммы. Можно по-разному определять как близость отдельных наблюдений, так и сформированных из них групп — кластеров (от англ, cluster — гроздь, скопление).

Исходные данные в задачах кластерного анализа задаются в виде таблицы (матрицы), строки которой соответствуют различным наблюдениям, а столбцы — различным переменным.

Если рассматривать строки-наблюдения, как точки в пространстве переменных, то естественно использовать в качестве меры различия между наблюдениями г и к евклидово расстояние между соответствующими им точками в m-мерном евклидовом пространстве.

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

где.

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

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

Вычислив каким-либо способом расстояния между всеми парами наблюдений, получают матрицу расстояний

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

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

Сначала все наблюдения считаются отдельными кластерами. На первом шаге в матрице расстояний ищется минимальный внедиагональный элемент (поскольку матрица симметрична, достаточно просмотреть ее поддиагональную часть). Пусть этот элемент находится на пересечении i-й строки и j-го столбца, что означает, что среди всех пар кластеров, каждый из которых состоит из одного наблюдения, наиболее близки между собой г-й и j-й кластеры. Эти два кластера объединяются в один, и общее число кластеров уменьшается на единицу — их становится п — 1 вместо исходных п. При этом возникает проблема определения расстояния от вновь образованного кластера i + j до остальных кластеров.

Рассмотрим некоторые возможные варианты.

1. Можно определить расстояние от i + j до любого другого кластера к как минимум из расстояний от г до А; и от j до к:

Этот метод называется методом минимальной связи, или методом ближайшего соседа.

2. Определить расстояние от i+j до любого другого кластера к как максимум из расстояний от г до к и от j до к:

— это метод максимальной связи, или метод дальнего соседа.

3. Определить расстояние от i+j до любого другого кластера к как среднее арифметическое из расстояний от г до к и от j до к:

— метод средней связи.

Второй и последующий шаги аналогичны первому — каждый раз объединяются два самых близких кластера и вычисляются расстояния от нового объединенного кластера до остальных. На каждом шаге общее число кластеров сокращается на единицу, и процесс заканчивается, когда все кластеры объединятся в один.

Метод средней связи имеет модификацию, называемую методом взвешенной средней связи. Она отличается тем, что если на некотором шаге объединяются кластеры от i и j, состоящие соответственно из /V, и Nj наблюдений, то расстояние от их объединения до любого другого кластера к вычисляется не как простое среднее, а как среднее взвешенное из расстояний от i до к йот j до к:

Метод дальнего соседа имеет тенденцию формировать кластеры одинакового размера и может не учитывать реальной неоднородности расположения наблюдений в пространстве признаков. Метод ближайшего соседа, наоборот, хорошо отслеживает локальные неоднородности и может выявлять кластеры довольно сложной формы и разного размера. Однако возможно объединение очень разных кластеров, если между ними случайно имеется цепочка близких наблюдений. Компромиссом между этими двумя методами является метод взвешенной средней связи.

Результаты кластерного анализа удобно представлять в виде дендрограммы, графически показывающей последовательность объединений с учетом расстояний между объединяющимися кластерами. Визуальный анализ дендрограммы позволяет определить число кластеров, на которые естественным образом разбивается совокупность наблюдений объединение сильно различающихся кластеров отражается на дендрограме скачкообразным увеличением межкластерного расстояния.

На рис. 3.6 приведен пример работы агломеративно-иерархического кластерного анализа. Данные состоят из 12 наблюдений, характеризующихся двумя переменными У) и Yi (они представлены на рис. 3.6, а в виде точек на плоскости). Здесь наглядно иллюстрируется процесс объединения наблюдений в кластеры: сначала объединяются наиболее близкие друг к другу наблюдения 6 и 4, затем — 3 и 1, потом к 3 -I- 1 присоединяется 2 и т. д. (рис. 3.6, а). На рис. 3.6, б представлена дендрограмма — результат работы алгоритма, на которой ясно видно, что совокупность наблюдений четко разделена на два кластера. Конечно, это еще лучше видно из представления точек на плоскости (см. рис. 3.6, а), но это возможно только потому, что рассматривается случай двух переменных. Дендрограмму же можно получить.

Рис. 3.6. Пример работы агломеративно-иерархического кластерного.

анализа:

а — процесс объединения наблюдений в кластеры; б — дендрограмма.

Рис. 3.7. Пример работы метода /^-средних: а — 1-й шаг алгоритма; б — 2-й шаг алгоритма при любом числе переменных, поскольку она строится на основе анализа расстояний между наблюдениями, а их можно вычислять для любого числа переменных (см. формулы для евклидова или манхеттеновского расстояний).

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

Несомненным преимуществом метода /(«-средних является возможность классифицировать наборы из многих сотен и даже тысяч наблюдений, тогда как с помощью агломеративноиерархического метода, хотя теоретически и возможно, но слишком громоздко обрабатывать более 100 — 200 наблюдений. Недостатки метода состоят в необходимости априорного задания числа кластеров, отсутствии наглядного представления результатов и зависимости результатов от начального выбора центров — при неудачном их выборе алгоритм может дать классификацию, не соответствующую реально имеющейся.