КЛАСТЕРНЫЙ АНАЛИЗ Класс 2 Класс 1 Класс 3 ОБЪЕКТ Х1 ХnХn ПРИЗНАКИ

1. Симметрия. Даны два объекта х и у; расстояние между ними удовлетворяет условию d(x,y)=d(y,x) Неравенство треугольника. Даны три объекта x, y, z; расстояния между ними удовлетворяют условию d(x, y) d(x, z)+ d(y, z). 3. Различимость нетождественных объектов. Даны два объекта х и у: если d(х, z) 0, то х у. 4. Неразличимость идентичных объектов. Для двух идентичных объектов х и х d(x,x)=0, т.е. расстояние между этими объектами равно нулю. Пусть w i i-я группа (класс, кластер) объектов, N i число объектов, образующих группу w i, вектор i среднее арифметическое объектов, входящих в w i

1. Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров: 2. Расстояние дальнего соседа расстояние между самыми дальними объектами кластеров: 3. Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

4. Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

МЕРЫ РАССТОЯНИЯ КЛАСТЕРНОГО АНАЛИЗА 1.Евклидово расстояние расстояние(x,y) = { (x i - y i ) 2 } 1/2 2. Квадрат евклидова расстояния расстояние(x,y) = (x i – y i ) 2 3. Расстояние городских кварталов (манхэттенское расстояние ). расстояние(x,y) = |x i – y i | 4. Расстояние Чебышева. расстояние(x,y) = max |x i – y i |

5. Степенное расстояние. расстояние(x,y) = { |x i – y i | p } 1/r 6. Процент несогласия. расстояние(x,y) = (Количество x i y i )/ i Правила объединения или связи Центроид кластера

Кластер 1 Кластер 2 Кластер 3

- Одиночная связь (метод ближайшего соседа). - Полная связь (метод наиболее удаленных соседей). - Невзвешенное попарное среднее. - Взвешенное попарное среднее. - Невзвешенный центроидный метод. - Взвешенный центроидный метод (медиана). - Метод Варда.

АГЛОМЕРАТИВНЫЕ МЕТОДЫ ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЙ - ДЕНДРОГРАММЫ 1. Построение матрицы расстояний (меры расстояния) 1-1; 1-2; 1-3; 1-4; ; 1-104; 1-105; 2-1; 2-2; 2-3; 2-4; ; 2-104; 2-105; ; ; 103-1; 103-2; ; ; ; 104-1; 104-2; ; ; ; 105-1; 105-2; ; ; Два наблюдения (монокластера), между которыми самое минимальное расстояние, объединяются в один кластер 3. Анализ оставшихся монокластеров и присоединение нового объекта к существующему кластеру либо объединение двух наблюдений в кластер

признаки расстояние

Squared Euclidean distances (cars.sta) PRICE ACCELER BRAKING HANDLING MILAGE PRICE,0 62,4 43,930,757,7 ACCELER62,4,048,651,636,8 BRAKING43,948,6,040,437,4 HANDLING30,751,640,4,052,2 MILAGE57,736,837,452,2,0 Матрица расстояний по признакам

объекты

Acura Audi BMW Buick CorvetteChryslerDodge Acura,09,97,97,716,55,75,8 Audi9,9,01,45,06,02,53,0 BMW7,91,4,08,03,42,12,0 Buick7,75,08,0,019,42,93,9 Corvette16,56,03,419,4,09,58,3 Chrysler5,72,52,12,99,5,0,2 Dodge5,83,02,03,98,3,2,0 Матрица расстояний

Итерационные методы Метод k-средних Мак-Кина 1) выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров; 2) при необходимости формируются промежуточные кластеры; 3) после назначения всех наблюдений отдельным кластерам производится замена первичных кластерных центров на кластерные средние; 4) предыдущая итерация повторяется до тех пор, пока изменения координат кластерных центров не станут минимальными.

1 шаг 2 шаг Назначение объекта – кластером и центроидом Расчет расстояний до всех объектов и объединение с ближайшим объектом в кластер 3 шаг Пересчет центроидов классов 4 шаг Расчет расстояний от центроидов до объектов и объединение с ближайшим объектом в кластер Шаг 2-4 повторяется итерационно

Шаг N Шаг N+1 Окончательные центроиды Расчет расстояний от центроидов до объектов Перетягивание ближайших объектов, пересчет центроидов Повторение шагов N и N+1 до минимального изменения координат центроидов

Standard Mean Deviatn.Variance PRICE, , , ACCELER-, , , BRAKING,099270,484478, HANDLING,280263,423215, MILAGE-,876397,655936, Статистики для классов Standard Mean Deviatn.Variance PRICE -,434787,386686, ACCELER,365078,721615, BRAKING-, , , HANDLING-, , , MILAGE,408985,867383, класс 1класс

ГРАФИК СРЕДНИХ

ПОСЛЕ УДАЛЕНИЯ НЕЗНАЧИМЫХ ПРИЗНАКОВ

Standard Mean Deviatn.Variance PRICE,195402,622618, ACCELER,788538,558425, MILAGE-,480841,648858, Статистики для классов Standard Mean Deviatn.Variance PRICE 1,119891, , ACCELER-1,59237,595372, MILAGE-,89508,658416, КЛАСС 2 КЛАСС Standard Mean Deviatn.Variance PRICE -,604276,118952, ACCELER,006119,541236, MILAGE,742706,828777,686872