Кластерный анализ

Таким образом, для  случая v=2, когда мы имеем всего  два количественных признака, расстояние d_ij будет равно длине гипотенузы прямоугольного треугольника, которая соединяет собой две точки в прямоугольной системе координат. Эти две точки будут отвечать i-тому и j-тому наблюдениям выборки. Нередко вместо обычного евклидового расстояния используют его квадрат d²_ij. Кроме того, в ряде случаев используется "взвешенное" евклидово расстояние, при вычислении которого для отдельных слагаемых используются весовые коэффициенты. Для иллюстрации понятия евклидовой метрики используем простой обучающий пример. Матрица данных, приведенная ниже в таблице, состоит из 5 наблюдений и двух переменных.   
 

Используя евклидову  метрику, вычислим матрицу межобъектных расстояний, состоящую из величин d_ij - расстояние между i-тым и j-тым объектами. В нашем случае i и j - номер объекта, наблюдения. Поскольку объем выборки равен 5, то соответственно i и j могут принимать значения от 1 до 5. Очевидно также, что количество всех возможных по парных расстояний будет равно 5*5=25. Действительно, для первого объекта это будут следующие расстояния: 1-1; 1-2; 1-3; 1-4; 1-5. Для объекта 2 также будет 5 возможных расстояний: 2-1; 2-2; 2-3; 2-4; 2-5 и т.д. Однако число различных расстояний будет меньше 25, поскольку необходимо учесть свойство неразличимости тождественных объектов - d_ij = 0 при i = j. Это означает, что расстояние между объектом №1 и тем же самым объектом №1 будет равно нулю. Такие же нулевые расстояния будут и для всех остальных случаев i = j. Кроме того, из свойства симметрии следует, что d_ij = d_ji для любых i и j. Т.е. расстояние между объектами №1 и №2 равно расстоянию между объектами №2 и №1. Ниже приведена симметричная (d_ij = d_ji) квадратная матрица с нулевой (d_ij = 0 при i = j) диагональю.   
 

Вспомнив школьную алгебру, нетрудно вычислить количество расстояний d_ij в одном из треугольников матрицы (верхнем или нижнем). Всего в матрице количество элементов (чисел) равно N*N (в нашем случае 5*5=25).  Вычтем из этого числа количество элементов находящихся на диагонали, равно объему выборки N. Далее разделим количество элементов находящихся над диагональю и под диагональю на два. В результате этого получим следующее выражение: (N*N - N)/2= N*(N-1)/2. Итак, для нашего случая всего будет 5*(5-1)/2=10 разных расстояний. 

А теперь попытаемся вычислить некоторые их этих расстояний самостоятельно, например, между объектом №1 и №2. Вначале вычислим квадрат  этого расстояния, а потом извлечем из него квадратный корень. d²₁₂ = [(5-6)² + (11-11)² ]= 1² + 0² =1. Отсюда получаем, что d₁₂ =1. Аналогично вычислим величину d²₁₃ а затем и d₁₃ : d²₁₃ =[(5-6)² + (11-12)² ] = 1² + 1² = 2. Откуда находим, что корень квадратный из двух с точностью до второго знака после запятой равен 1,41. Запомним, что минимальная величина в данной матрице равна 1 и отвечает расстоянию d₁₂. Чуть ниже мы увидим, что процесс кластеризации этих 5 наблюдений начнется именно с объектов №1 и №2. Рекомендуем нашим читателям самостоятельно вычислить расстояние между 4 и 5 объектами, убедившись, что оно действительно равно 1,41.

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

При р = 2 мы получаем обычное Евклидово расстояние. Ниже приводится выражение для обобщенной метрики Минковского.

Выбор конкретного  значения степенного показателя "р" производится самим исследователем. 

Частным случаем  расстояния Минковского является так называемое манхэттенское расстояние, или "расстояние городских кварталов" (city-block), соответствующее р=1:

Таким образом, манхеттенское расстояние является суммой модулей разностей соответствующих признаков объектов. Устремив p к бесконечности, мы получаем метрику "доминирования", или Sup-метрику: 

которую можно представить также в виде d_ij = max| x_ik - x_jk|.

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

Здесь через X_i и X_j обозначены вектор-столбцы значений переменных для i-того и j-того объектов. Символ Т в выражении (X_i - X_j)^Тобозначает так называемую операцию транспонирования вектора. Символом S обозначена общая внутригрупповая дисперсионно-ковариационная матрица. А символ ^-1 над S означает, что необходимо обратить матрицу S (желающих более детально разобраться с этими математическими тонкостями отправляем к вполне доступным для медиков и биологов книгам [6-10]). В отличие от метрики Минковского и евклидовой метрики, расстояние Махаланобиса через матрицу дисперсий-ковариаций S связано с корреляциями переменных. Когда корреляции между переменными равны нулю, расстояние Махаланобиса эквивалентно квадрату евклидового расстояния. 

В случае использования  дихотомических (имеющих всего два  значения) качественных признаков широко используется расстояние Хемминга

равное числу несовпадений значений соответствующих признаков для рассматриваемых i-того и j-того объектов.

Кроме этих достаточно известных и популярных метрик используются и такие метрики, как коэффициенты Рао, Хемминга, Роджерса-Танимото, Жаккара, Гауэра, меры близости Журавлева, Воронина, Миркина, метрики Брея-Кертиса, Канберровская и многие другие [5, 11-33]. 

3. ПЛОТНОСТЬ  И ЛОКАЛЬНОСТЬ КЛАСТЕРОВ

Как уже говорилось выше, главной целью кластерного  анализа является нахождение в выборке  групп объектов схожих между собой. Предположим, что каким-то из возможных методов мы получили такие группы - кластеры. Теперь имеет смысл обсудить наиболее важные свойства кластеров. Одно из таких свойств - это плотность распределения точек, наблюдений внутри кластера. Это свойство дает нам возможность определить кластер в виде скопления точек в многомерном пространстве, относительно плотное по сравнению с иными областями этого пространства, которые либо вообще не содержат точек, либо содержат малое количество наблюдений. Иными словами, насколько данный кластер является компактным, или же наоборот - достаточно разреженным. Несмотря на достаточную очевидность этого свойства, однозначного способа вычисления такого показателя (плотности) не существует. Наиболее удачным показателем, характеризующим компактность, плотность "упаковки" многомерных наблюдений в данном кластере, является дисперсия расстояния от центра кластера до отдельных точек кластера. Чем меньше дисперсия этого расстояния, тем ближе к центру кластера находятся наблюдения, тем больше плотность кластера.  И наоборот, чем больше дисперсия расстояния, тем более разрежен данный кластер, и, следовательно, есть точки находящиеся как вблизи центра кластера, так и достаточно удаленные от центра кластера. 

Следующее свойство кластеров - его размеры. Основным показателем  размера кластера является его "радиус". Это свойство наиболее полно отображает фактический размер кластера, если рассматриваемый кластер имеет  круглую форму и является гиперсферой в многомерном пространстве. Однако если кластеры имеют удлиненные формы, то понятие радиуса или диаметра уже не отображает истинного размера кластера. 

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

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

4. РАССТОЯНИЕ  МЕЖДУ КЛАСТЕРАМИ 

В более широком  смысле под объектами можно понимать не только исходные предметы исследования, представленные в матрице "объект-свойство" в виде отдельной строки, или отдельными точками в многомерном признаковом  пространстве, но и отдельные группы таких точек, объединенные тем или  иным алгоритмом в кластер. В этом случае возникает вопрос о том, каким  образом понимать расстояние между  такими скоплениями точек (кластерами) и как его вычислять. Отметим, что в этом случае разнообразных  возможностей еще больше, нежели в  случае вычисления расстояния между  двумя наблюдениями в многомерном  пространстве. Эта процедура осложняется  тем, что в отличие от точек  кластеры занимают определенный объем  многомерного пространства и состоят  из многих точек. Как, например, можно  определить расстояние от Новосибирска до Академгородка, от Хабаровска до Владивостока, или от Москвы до Санкт-Петербурга? Можно принять за это расстояние протяженность прямой линии соединяющей  главпочтамты этих городов. А можно  измерить расстояние между главпочтамтами по автомобильной дороге или по железной дороге. Но эти методы не единственные из возможных. Учитывая протяженность самих объектов, можно понять, что эти расстояния будут различаться, если их измерять между ближними окраинами этих городов, или между дальними окраинами. Не лишено смысла и измерение расстояния между геометрическими центрами этих городов. Вопрос только в том, что при этом считать геометрическим центром города?

Аналогично этим вариантам в кластерном анализе  широко используются межкластерные расстояния, вычисляемые по принципу ближайшего соседа (nearest neighbour) (расстояния между ближними домами двух городов), центра тяжести, дальнего соседа (furthest neighbour), медиан. Наиболее широко используются четыре метода: одиночной связи, полной связи, средней связи и метод Варда. Последний метод в ряде книга называется методом Уорда. В методе одиночной связи объект будет присоединен к уже существующему кластеру, если хотя бы один из элементов кластера имеет тот же уровень сходства, что и присоединяемый объект. Отсюда и название метода - одиночная или единственная связь. Для метода полных связей присоединение объекта к кластеру производится лишь в том случае, когда сходство между кандидатом на включение и любым из элементов кластера не меньше некоторого порога. Для метода средней связи имеется несколько модификаций, которые являются некоторым компромиссом между одиночной и полной связью. В них вычисляется среднее значение сходства кандидата на включение со всеми объектами существующего кластера. Присоединение производится в том случае, когда найденное среднее значение сходства достигает или превышает некоторый порог. Наиболее часто используют среднее арифметическое сходство между объектами кластера и кандидата на включение в кластер. 

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

http://www.chemstat.com.ru/node/40

Кластерный  анализ - метод группировки объектов в классы на основании экспериментальных данных о свойствах объектов.