Материал: Методические указания к лабораторным работам №1-4 по дисциплине «Современные технологии обработки информации». Разинкин К.А

6. Статистическое расстояние между классами

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

В качестве меры рассеяния элементов используют матрицу рассеяния

След trS_x матрицы S_x (т. е. сумму диагональных элементов) называют статистическим рассеянием множества элементов или внутри-групповой суммой квадратов

.

Можно показать, что

где суммирование проводится для значений i<j.

Таким образом, использование trS_x в качестве меры рассеяния класса связано с евклидовой метрикой. Определитель матрицы рассеяния на­зывают обобщенной дисперсией множества элементов .

Рассмотрим два класса , и S_m и их объединение

Тогда матрица рассеяния для класса равна

,

где

Матрицу рассеяния S_x для класса S(l, m) можно преобразовать так

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

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

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

В модуле Cluster Analysis пакета STATISTICA реализуются следующие методы кластеризации[7]:

• соединения (древовидная кластеризация), Joining (tree clustering);

• метод K -средних (K-means clustering);

• двухвходовое объединение (Two-way joining).

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

Первая опция (Joining) представляет группу так называемых иерархиче­ских алгоритмов кластеризации. В основе этих алгоритмов лежит идея по­следовательной кластеризации. Пусть исходное множество содержит п объ­ектов .

В качестве расстояния между объектами X_t и Xj выбирается некоторая метрика р. Выбор метрики необходимо сделать в опции distance measure па­нели Joining.

1. Метод одиночной связи (Single Linkage). Кластеры объединяются ис­ходя из расстояния, измеряемого по методу «ближайшего соседа». Группы, между которыми расстояния самые маленькие, объединяются. Каждое объ­единение уменьшает число групп на единицу. Расстояние между группами определяется как расстояние между ближайшими членами групп. Метод приводит к «цепным» кластерам.

2. Метод полной связи (Complete Linkage). Расстояние между группами определяется как расстояние измеряемое по принципу «дальнего соседа». Расстояние между объединяемыми кластерами равно диаметру наимень­шей сферы, содержащей оба кластера. Метод создает компактные кластеры в виде гиперсфер, которые плохо объединяются с другими кластерами. Если кластеры имеют удлиненную форму, то метод не работает.

3. Метод невзвешенного попарного среднего (Unweightedpair-group avera­ge). Расстояние между кластерами определяется по принципу «средней связи».

4. Метод взвешенного попарного среднего (Weighted pair-group average). Расстояние между кластерами определяется по принципу «средней связи», но с учетом в качестве весов числа объектов, содержащихся в кластерах.

5. Невзвешенный центроидный метод (Unweighted pair-group centroid). Расстояния между кластерами определяется как расстояние между их «цен­трами тяжести»

6. Взвешенный центроидный метод (Weighted pair-group centroid). Расстоя­ние между классами определяется как расстояние между их «центрами тя­жести», но с учетом весов, определяемых по количеству объектов в каждом кластере (т. е. с учетом размеров кластеров).

7. Метод Уорда (Ward's metod). В этом методе в качестве целевой функ­ции используется сумма квадратов расстояний между каждым элементом и «центром тяжести» класса, содержащего этот элемент. Кластеризация представляет последовательную процедуру, на каждом шаге которой объе­диняются два таких класса, при объединении которых происходит мини­мизация статистического расстояния между классами , вычисляемого по формуле

Рассмотрим работу иерархического алгоритма кластеризации на про­стом примере.

Пример. 3. Провести кластеризацию четырех объектов методами оди­ночной связи (Single Linkage) и полной связи (Complete Linkage). Каждый объект определяется двумя признаками

Решение

Расстояние между объектами и определим как квадрат евклидовой метрики

Таким образом, расстояние между первым и вторым объектами равно:

=(0 + 1)²+(-2-0)²=5, а между первым и третьим объектами

(0-1)² +(-2-2)² =17 и т. д.

На первом шаге матрица расстояний между объектами , имеет вид

Наиболее близки первый и второй объекты: = 5, следовательно, эти объекты объединяются в один кластер.

На втором шаге имеем следующие кластеры:

Определяем расстояние между кластерами по методу «ближайшего со­седа»:

min min(17;8)=8

min min(20;25)=20;

Для вычисления расстояния между кластерами можно воспользоваться формулой (1):

Расстояние по принципу «ближайшего соседа» определяется при . Таким образом, например, расстояние между пер­вым и вторым кластерами по формуле (1) равно

Матрица расстояний D₂ между тремя кластерами на втором шаге име­ет вид

Как следует из матрицы расстояний D₂ наиболее близки первый и вто­рой кластеры: , следовательно, эти кластеры объединяются в один кластер.

Таким образом, на третьем шаге имеем следующие кластеры:

min min(20;13)=13.

Матрица расстояний D₃ между двумя кластерами на третьем шаге

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

Теперь рассмотрим работу алгоритма, в случае, когда расстояние между кластерами определяется по принципу «дальней связи» - Complete Linkage.

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

На втором шаге имеем следующие кластеры:

Далее определяем расстояние между объектами по принципу «дальней связи»:

max max(17;8)=17.

max max(20;25)=25.

Матрица расстояний D₂ между тремя кластерами на втором шаге име­ет вид

.

Таким образом наиболее близки второй и третий кластеры: =13. Эти кластеры объединяются и на третьем шаге имеем следующие кластеры:

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

max max(17;25)=25.