Методы построения типологических групп (основные понятия кластерного анализа)

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

- требования симметрии (d(O_i, O_j)= d(O_j, O_i) и r(O_i, O_j)= r(O_j, O_i));

- требования максимального сходства объекта с самим собой (r(O_i, O_i)= r(O_j, O_i));

- требования при заданной метрике  монотонного убывания r(O_i, O_j) по d(O_i, O_j), т.е. из d(O_k,O_l) d(O_i, O_j) должно с необходимостью следовать выполнение неравенства r(O_k,O_l) r(O_i, O_j).

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

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

    Евклидово расстояние.  Это наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется по формуле

,

где - значения k-го признака для i-го и j-го объектов, а p – число характеристик.

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

  

   Взвешенное евклидово расстояние.

.

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

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

 

     Хеммингово расстояние (расстояние городских кварталов), также называемое «манхэттенским» или «сити-блок» расстоянием.

.

Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако, отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат).

4. Расстояния между классами объектов

  

     При конструировании различных процедур классификации (кластер-процедур) в ряде ситуаций оказывается целесообразным введение понятия расстояния между целыми группами объектов. Приведем примеры наиболее распространенных расстояний, характеризующих взаимное расположение отдельных групп объектов. Пусть S_i – i-я группа (класс, кластер) объектов, n_i - число объектов, образующих группу S_i , векторо - среднее арифметическое векторных наблюдений, входящих в S_i (другими словами,  - «центр тяжести» i-й группы), а - расстояние между группами S_l и S_m. 

   Метод ближнего соседа или одиночная связь.

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

   Метод наиболее удаленных соседей или полная связь.

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

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

   Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего).

.

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

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

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

   Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения).

   В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.

.

  

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

5. Пример

    

     Приведены результаты опроса пяти студентов 3 курса, о том сколько времени в день каждый из них тратит:

А) на учебу ( ч.);

Б) на интернет ( ч.). 

 

    

    Требуется:

С помощью  алгомеративного иерархического алгоритма  провести классификацию студентов  и построить дендограмму:

1) при  использовании обычной евклидовой метрики методом а) ближайшего соседа; б)     дальнего соседа; в) центров тяжести; г) средней связи;

2) при  использовании взвешенной евклидовой  метрики (с весами w₁=0,95 и w₂=0,05)   методом ближайшего соседа.

    Решение

   1а) Проведем классификацию, выбрав при обычном евклидовом расстоянии принцип «ближайшего соседа».

    В обычной евклидовой метрике  расстояние между наблюдениями 1 и 2 равно

     Аналогично находим расстояние между всеми пятью наблюдениями и строим матрицу расстояний

   Из матрицы расстояний следует, что объекты 2 и 3 наиболее близки (d_2.3=0,56), поэтому объединим их в один кластер. После объединения объектов имеем четыре кластера: S₁, S_2,3, S₄, S₅.

     Расстояние между кластерами будем находить по принципу «ближайшего соседа». Так, расстояние между кластером S₁и S_2,3 равно:

d(1,(2,3))=min(d_1.2, d_1.3)=min(2,06; 1,52)=1,52

Проводя аналогичные расчеты для d(4,(2,3)) и d(5,(2,3)), по.лучим матрицу расстоянй

Объединим наблюдения 4 и 5 имеющие наименьшее расстояние d_4,5=1,39. После объединения имеем три кластера S₁, S_(2,3), S_(4,5).

     Вновь строим матрицу расстояний. Для этого необходимо рассчитать расстояния d(1; (4,5)) и d((2,3);(4,5)):

d(1; (4,5))=min(d_1.4,d_1.5)=3,36; 

d((2,3);(4,5))=min(d_2.4, d_2.5, d_3.4, d_3.5)=1,82.

     Получим матрицу расстояний

     Далее объединяем кластеры S₁ и S_(2.3), расстояние между которыми, как это видно из матрицы D₃, минимально: d_1,(2..3)=1,52. В результате этого получим два кластера: S_(1.2.3) и S_(4.5). Матрица расстояний будет иметь вид:

Из матрицы  D₄ следует, что на расстоянии d_{(1.2.3).(4.5)}=1.82 все пять наблюдений объединяются в один кластер. Результаты кластерного анализа представим графически в виде дендрограммы рис.1.

  

Рис.1. Дендограмма (обычное евклидово расстояние, ближайший сосед)

    

      На основании анализа результатов применения кластерной процедуры можно сделать вывод, что наилучшим является разбиение пяти студентов на два кластера: S_(1.2.3) и S_(4.5). 

     1б) Проведем классификацию, выбрав при обычном евклидовом расстоянии принцип «дальнего соседа».

     Как и в случае (1а), мы используем обычное евклидово расстояние, поэтому матрица D₁ остается без изменения. Согласно агломеративному алгоритму объединения в один кластер объекты 2 и 3, как наиболее близкие d_2..3=0,56. После объединения имеем четыре кластера: S₁, S_2,3, S₄, S₅.

     Вычисляя расстояние между кластерами по принципу «дальнего соседа», имеем:

d_1.(2,3)=max(d_1.2,d_1.3)=2,06;

d_4.(2,3)= max(d_4.2,d_4.3)=2,65;

d_5.(2,3)= max(d_5.2,d_5.3)=2,24.

     Соответственно, имеем новую матрицу  попарных расстояний:

   Объединим объекты 4 и 5 в один  кластер, как наиболее близкие  (d_4,5=1,39).

   После объединения имеем три  кластера: S₁, S_(2,3), S_(4,5).