Меры близости и различия в кластерном анализе.

Функции расстояния и сходства Неотрицательная вещественная функция называется функцией расстояния (метрикой), если:

а) для всех и из ;

б) лишь для ;

в) ;

г) , где − любые три точки из (так называемое “правило треугольника”).

Значение функции d для двух заданных точек эквивалентно расстоянию между Оⁱ и О^j.

В качестве примера функций расстояний приведем наиболее употребительные:

1) евклидово расстояние ;

2) сумма абсолютных отклонений, называемая иногда метрикой города, ;

3) расстояние Махаланобиса ,

где – матрица, обратная матрице рассеяния (см. (9.3)) .

Расстояние Махаланобиса часто называют обобщенным евклидовым расстоянием; оно инвариантно относительно невырожденного линейного преобразования Υ=BХ, то есть .

Первые две метрики представляют частный случай так называемой -метрики:

.

Для -метрики справедливо соотношение для любых тогда и только тогда, когда .

Обобщением l_p-метрики является «взвешенная» l_p-метрика ,

где w_i – некоторый неотрицательный «вес», пропорциональный степени важности i-й компоненты при решении вопроса об отнесении объекта к тому или иному классу.

Расстояния между N объектами могут быть сведены в квадратную симметричную матрицу расстояний

. (9.2)

Понятием, противоположным расстоянию, является понятие сходства. Мерой сходства называют неотрицательную вещественную функцию, удовлетворяющую следующим аксиомам:

1) ;

2) ;

3) .

Значения функции сходства элементов множества О можно объединить в матрицу сходства

.

Величину обычно называют коэффициентом сходства. Приведем в качестве примера функции сходства для объектов, описываемых дихотомическими признаками, т.е. такими, которые могут принимать значения нуль или единица. Для заданных точек и обозначим через число совпадающих единичных (нулевых) координат, через – число координат, имеющих 1 в и 0 в , сходным образом определяется . Мерами сходства будут функции:

1) ; 2) ; 3) .

Заметим, что подбирая подходящее преобразование, можно перейти от мер расстояния к мерам сходства.

Меры близости и расстояния могут задаваться также с помощью так называемых потенциальных функций F(U,V) = f(d(U,V)), где U и V – любые две точки из Е_n, d(U,V) – метрика. В качестве примера приведем две такие функции: F(U,V) = exp(– ad²(U,V)), a>0; F(U,V) = (1 + ad²(U,V))^-1.

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

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

2. Использование обычного евклидова расстояния можно признать оправданным, если:

а) компоненты вектора наблюдений взаимно независимы и имеют одну и ту же дисперсию;

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

в) пространство признаков совпадает с геометрическим пространством (n= 1, 2, 3).

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

Рассмотрим теперь меры близости между кластерами. Введение понятия расстояния между группами объектов оказывается целесообразным при конструировании многих процедур кластеризации. Пусть К_i – i-й кластер, содержащий объектов; – арифметическое среднее наблюдений, входящих в K_i, т.е. – выбранная метрика.

Рассмотрим наиболее употребительные расстояния между кластерами:

1) расстояние, измеряемое по принципу ближайшего соседа (nearest neighbour)

;

2) расстояние, измеряемое по принципу дальнего соседа (furthest neighbour)

;

3) статистическое расстояние между кластерами ;

4) расстояние, измеряемое по центрам тяжести кластеров .

Легко видеть, что пропорционально , если в качестве метрики используется евклидово расстояние;

5) мера близости, основанная на потенциальной функции F(K_l,K_m) =

Иллюстрация трех приведенных мер представлена на рис. 8.

Рис.8. Примеры расстояний между кластерами