Теория кластерного анализа

Теоретическая часть по «Кластерному анализу»

 

 Методы кластерного  анализа

Методы кластерного анализа  можно разделить на две группы:

- иерархические;

- неиерархические.

Каждая из групп  включает множество подходов и алгоритмов. Используя различные методы кластерного анализа, аналитик может получить различные решения для одних и тех же данных. Это считается нормальным явлением.

 Иерархические  алгоритмы

Суть иерархической  кластеризации состоит в последовательном объединении меньших кластеров  в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

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

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

Принцип работы описанных выше групп методов  в виде дендрограммы показан на рис. 1.

Рисунок 1

 

Иерархические методы кластеризации различаются  правилами построения кластеров. В  качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).

Иерархические методы кластерного анализа используются при небольших объемах наборов  данных. Преимуществом иерархических методов кластеризации является их наглядность.

Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа.

Дендрограмма  описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

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

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

Существует много способов построения дендограмм. В дендограмме  объекты могут располагаться  вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рис. 2.

Рис. 2. Пример дендрограммы

 

Числа 11, 10, 3 и  т.д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

Пусть K_i - i-я группа (класс, кластер), состоящая из n объектов;

  - среднее арифметическое векторных наблюдений K_i  группы, т.е. «центр тяжести» i - й группы;

r (K_i , K _j)=r_ij – расстояние между группами K_i и K_j .

Обобщенная  алгомеративная процедура. На первом шаге каждый объект считается отдельным кластером. На следующем шаге объединяются два ближайших объекта, которые образуют новый класс, определяются расстояния от этого класса до всех остальных объектов, и размерность матрицы расстояний D сокращается на единицу. На p -ом шаге повторяется та же процедура на матрице D_(n-p)(n-p), пока все объекты не объединятся в один класс.

Если сразу  несколько объектов (классов) имеют  минимальное  расстояние, то возможны две стратегии: выбрать одну случайную  пару или объединить сразу все  пары. Первый способ является классическим и реализован во всех процедурах (иногда его называют восходящей иерархической классификацией). Второй способ называют методом ближайших соседей (не путать с алг. “Ближайшего соседа”) и используют реже.

Результаты работы всех иерархических процедур обычно оформляют в виде так называемой дендограммы (рис. 3-5). В дендограмме номера объектов располагаются по горизонтали, а по вертикали - результаты кластеризации.

Рис. 3	Рис. 4
Рис. 5

 

 

 

Расстояния между  кластерами

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

Здесь имеются  различные возможности: например, вы можете связать два кластера вместе, когда любые два объекта в  двух кластерах ближе друг к другу, чем соответствующее расстояние связи. Другими словами, вы используете  правило ближайшего соседа для определения расстояния между кластерами; этот метод называется методом одиночной связи. Это правило строит волокнистые кластеры, т.е. кластеры сцепленные вместе только отдельными элементами, случайно оказавшимися ближе остальных друг к другу. Как альтернативу вы можете использовать соседей в кластерах, которые находятся дальше всех остальных пар объектов друг от друга. Этот метод называется метод полной связи. Существует также множество  других методов объединения кластеров, подобных тем, что были рассмотрены здесь, и модуль Кластерный анализ предлагает широкий выбор таких методов.

1. Расстояние “Ближайшего соседа” (Одиночная связь). Первый шаг 1.–7. совпадает с первым шагом алгоритма Обобщенная алгомеративная процедура. Расстояние равно расстоянию между ближайшими объектами классов.

.

2. Расстояние “Дальнего соседа” (Полная связь). Расстояние равно расстоянию между самыми дальними объектами классов.

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

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

5. Невзвешенный центроидный метод. В этом методе расстояние  между двумя кластерами определяется как расстояние между их центрами тяжести.

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

7. Метод Варда (Ward, 1963). В этом методе в качестве целевой функции применяют внутригрупповую сумму квадратов отклонений, которая есть ни что иное, как сумма квадратов расстояний между каждой точкой (объектом) и средней по кластеру, содержащему этот объект. На каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов (SS). Этот метод направлен на объединение близко расположенных кластеров.

 

Процедуры эталонного типа

Наряду с иерархическими методами классификации, существует многочисленная группа так называемых итеративных методов кластерного анализа (метод k - средних.).

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

Метод k - средних удобен для обработки больших статистических совокупностей.

Математическое  описание алгоритма метода k - средних.

Пусть имеется n наблюдений, каждое из которых характеризуется m признаками X₁, X₂,…, X_n. Эти наблюдения необходимо разбить на k кластеров. Для начала из n точек исследуемой совокупности отбираются случайным образом или задаются исследователем исходя из каких-либо априорных соображений k точек (объектов). Эти точки принимаются за эталоны. Каждому эталону присваивается порядковый номер,  который одновременно является и номером кластера. На первом шаге из оставшихся (n-k) объектов извлекается точка X_i с координатами (x_i1, x_i2, ... , x_im) и проверяется,к какому из эталонов (центров) она находится ближе всего. Для этого используется одна из метрик, например, евклидово расстояние. Проверяемый объект присоединяется к тому центру (эталону), которому соответствует минимальное из расстояний. Эталон заменяется новым, пересчитанным с учетом присоединенной точки, и вес его (количество объектов, входящих в данный кластер) увеличивается на единицу. Если встречаются два или более минимальных расстояния, то i-ый объект присоединяют к центру с наименьшим порядковым номером. На следующем шаге выбираем точку  X_i+1 и для нее повторяются все процедуры. Таким образом, через (n-k) шагов все точки (объекты) совокупности окажутся отнесенными к одному из k кластеров, но на этом процесс разбиения не заканчивается. Для того чтобы добиться устойчивости разбиения по тому же правилу, все точки  X₁, X₂,…, X_n опять подсоединяются к полученным кластером, при этом веса продолжают накапливаться. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается. В противном случае цикл повторяется. Окончательное разбиение имеет центры тяжести, которые не совпадают с эталонами, их можно обозначить C₁,C₂ ,… ,C_k.  При этом каждая точка X_i (i=1,2,…,n) будет относиться к такому кластеру (классу) l, для которого расстояние минимально. Возможны две модификации метода k - средних. Первая предполагает пересчет центра тяжести кластера после каждого изменения его состава, а вторая – лишь после того, как будет завершен просмотр всех данных. В обоих случаях итеративный алгоритм этого метода минимизирует дисперсию внутри каждого кластера, хотя в явном виде такой критерий оптимизации не используется.