Кластерный анализ. Расстояние между объектами. Расстояние между кластерами (стр. 2 из 5)
На рисунке мы видим несколько групп "похожих" примеров. Примеры (объекты), которые по значениям X и Y "похожи" друг на друга, принадлежат к одной группе (кластеру); объекты из разных кластеров не похожи друг на друга.
Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.
Например, пусть G включает n стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития.
Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок, который называют целевой функцией. Например, в качестве целевой функции может быть взята внутригрупповая сумма квадратов отклонения:
где xj - представляет собой измерения j-го объекта.
Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.
Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Хi и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Хi и Хj из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Хi , Хj) называется функцией расстояния (метрикой), если:
а) d(Хi , Хj) ³ 0, для всех Хi и Хj из Ер
б) d(Хi, Хj) = 0, тогда и только тогда, когда Хi = Хj
в) d(Хi, Хj) = d(Хj, Хi)
г) d(Хi, Хj) £ d(Хi, Хk) + d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер.
Значение d(Хi, Хj) для Хi и Хj называется расстоянием между Хi и Хj и эквивалентно расстоянию между Gi и Gj соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).
Наиболее часто употребляются следующие функции расстояний:
1. Евклидово расстояние d2(Хi , Хj) =
2. l1 - норма d1(Хi , Хj) =
3. Сюпремум - норма d¥ (Хi , Хj) = sup
k = 1, 2, ..., р
4. lp - норма dр(Хi , Хj) =
Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.
Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p ´ n:
Тогда расстояние между парами векторов d(Хi , Хj) могут быть представлены в виде симметричной матрицы расстояний:
Понятием, противоположным расстоянию, является понятие сходства между объектами Gi. и Gj. Неотрицательная вещественная функция S(Хi ; Хj) = Sij называется мерой сходства, если :
1) 0£ S(Хi , Хj)<1 для Хi ¹ Хj
2) S(Хi , Хi) = 1
3) S(Хi , Хj) = S(Хj , Хi)
Пары значений мер сходства можно объединить в матрицу сходства:
Величину Sij называют коэффициентом сходства.
1.3. Методы кластерного анализа.
Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).
Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Хi и Хj определяется по формуле:
1) Метод полных связей.
Суть данного метода в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который меньше некоторого порогового значения S. В терминах евклидова расстояния d это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Таким образом, h определяет максимально допустимый диаметр подмножества, образующего кластер.
2) Метод максимального локального расстояния.
Каждый объект рассматривается как одноточечный кластер. Объекты группируются по следующему правилу: два кластера объединяются, если максимальное расстояние между точками одного кластера и точками другого минимально. Процедура состоит из n - 1 шагов и результатом являются разбиения, которые совпадают со всевозможными разбиениями в предыдущем методе для любых пороговых значений.
3) Метод Ворда.
В этом методе в качестве целевой функции применяют внутригрупповую сумму квадратов отклонений, которая есть ни что иное, как сумма квадратов расстояний между каждой точкой (объектом) и средней по кластеру, содержащему этот объект. На каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров.
4) Центроидный метод.
Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:
d2 ij = (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.
2. Расстояние между объектами. Расстояние между кластерами.
2.1. Расстояние между объектами (кластерами) и мера близости
Наиболее трудным и наименее формализованным в задаче классификации является определение понятия однородности объектов. В общем случае понятие однородности объектов задается либо введение правила вычисления расстояний ρ(xi,xj) между любой парой исследуемых объектов (х1, х2, ... , хn), либо заданием некоторой функции r(xi,xj), характеризующей степень близости i-го и j-го объектов. Если задана функция ρ(xi,xj), то близкие с точки зрения этой метрики объекты считаются однородными, принадлежащими к одному классу. Очевидно, что необходимо при этом сопоставлять ρ(хi,xj) с некоторыми пороговыми значениями, определяемыми в каждом конкретном случае по-своему.
Аналогично используется и мера близости r(xi,xj), при задании которой мы должны помнить о необходимости выполнения следующих условий: симметрии r(xi,xj)= r(xj,xi); максимального сходства объекта с самим собой r(xi,xi)= r(x
i,xj), при 1≤ i,j≤n, и монотонного убывания r(xi,xj) по мере увеличения ρ(xi,xj), т.е. из ρ(xk,xl)≥ρ (xi,xj) должно следовать неравенство r(xk,xl)≤r(xi,xj).Выбор метрики или меры близости является узловым моментом иссле-дования, от которого в основном зависит окончательный вариант разбиения объектов на классы при данном алгоритме разбиения. В каждом конкретном случае этот выбор должен производиться по-своему в зависимости от целей исследования, физической и статистической природы вектора наблюдений Х, априорных сведений о характере вероятностного распределения Х.
Рассмотрим наиболее широко используемые в задачах кластерного анализа расстояния и меры близости.
Обычное Евклидово расстояние
(1.1)где хie,, xje - величина е-ой компоненты у i-го (j-го) объекта (е=1,2,...,к, i,j=1,2,...,n)
Использование этого расстояния оправдано в следующих случаях:
а) наблюдения берутся из генеральной совокупности, имеющей многомерное нормальное распределение с ковариационной матрицей вида σ2Ек, т.е. компоненты Х взаимно независимы и имеют одну и ту же дисперсию, где Ек - единичная матрица;
б) компоненты вектора наблюдений Х однородны по физическому смыслу и одинаково важны для классификации;
в) признаковое пространство совпадает с геометрическим пространством.
Естественное с геометрической точки зрения евклидово пространство может оказаться бессмысленным (с точки зрения содержательной интерпретации), если признаки измерены в разных единицах. Чтобы исправить положение, прибегают к нормированию каждого признака путем деления центрированной величины на среднее квадратическое отклонение и переходят от матрицы Х к нормированной матрице с элементами
где 
- значение e-го признака у i-го объекта
- среднее значение e-го признака; 
- среднее квадратическое отклонение е-го признака.