3.2. расстояние между объектами (кластерами) и мера близости

3.2. расстояние между объектами (кластерами) и мера близости

Наиболее трудным и наименее формализованным в задаче классификации является определение понятия однородности объектов.

В общем случае понятие однородности объектов задается либо введением правила вычисления расстояний p(xi,xj) между любой парой исследуемых объектов (х1, х2, ... , хп), либо заданием некоторой функции r(xi,Xj), характеризующей степень близости i-го и j-го объектов. Если задана функция p(xi,Xj), то близкие с точки зрения этой метрики объекты считаются однородными, принадлежащими к одному классу. Очевидно, что необходимо при этом сопоставлять р(х^) с некоторыми пороговыми значениями, определяемыми в каждом конкретном случае по-своему.

Аналогично используется и мера близости r(xi,xj), при задании которой мы должны помнить о необходимости выполнения следующих условий: симметрии r(xi,xj)= r(xj,xi);

максимального сходства объекта с самим собой r(xi,xi)= max r(xi,xj), при 1< i,j<n, и моноi j

тонного убывания r(xi,xj) по мере увеличения p(xi,xj), т.е. из p(xk,xi)>p (xi,xj) должно следовать неравенство r(xk,xl)<r(xi,xj).

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

Рассмотрим наиболее широко используемые в задачах кластерного анализа расстояния и меры близости.

Обычное Евклидово расстояние

рн (хг, x,)

ЕX -x;i)2, (3.1)

i=1

где х;ixj i величина i -ой компоненты у і-го (j-го) объекта (i =1,2,...,к; i,j=1,2,..., n) Использование этого расстояния оправдано в следующих случаях:

а) наблюдения берутся из генеральной совокупности, имеющей многомерное нормальное распределение с ковариационной матрицей вида а Ек, т.е. компоненты Х взаимно

независимы и имеют одну и ту же дисперсию, где Ек единичная матрица;

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

в) признаковое пространство совпадает с геометрическим пространством.

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

Xii — Хі

til = ,

Si

где Xii значение і -го признака у i-го объекта; xi среднее значение і -го признака;

Si

i=1

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

«Взвешенное» Евклидово пространство

)2 (3.2)

Г

1

уРв( Xi, Xi) = .

i=1

применяется в тех случаях, когда каждой компоненте xi вектора наблюдений X удается приписать некоторый «вес» со i, пропорционально степени важности признака в задаче классификации. Обычно принимают 0<со i <1, где i =1,2,...k.

Определение «весов», как правило, связано с дополнительными исследованиями, например, организацией опроса экспертов и обработкой их мнений. Определение весов ш i только по данным выборки может привести к ложным выводам.

Хеммингово расстояние

Используется как мера различия объектов, задаваемых дихотомическими признаками. Это расстояние определяется по формуле

k

рн(Xi,Xj) = Z|Xu -(3.3)

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

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

В данной задаче объектом классификации является отрасль народного хозяйства, а матрица межотраслевого баланса представлена элементами sij, характеризующими сумму годовых поставок i-ой отрасли в j-ю в денежном выражении. В качестве меры близости {rij} принимают симметризованную нормированную матрицу межотраслевого баланса. С целью нормирования денежное выражение поставок i-ой отрасли в j-ю заменяют долей этих поставок по отношению ко всем поставкам i-ой отрасли. Симметризацию же нормированной матрицы межотраслевого баланса можно проводить, выразив близость между i-й и j-й отраслями через среднее значение из взаимных поставок, так что в этом случае

rij=rji.

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

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

Пусть sii-я группа (класс, кластер), состоящая из ni объектов; xi среднее арифметическое векторных наблюдений si группы, т.е. "центр тяжести" i-й группы;

р (s і ,sm) расстояние между группами s е и sm.

Наиболее употребительными расстояниями и мерами близости между классами объектов являются:

расстояние, измеряемое по принципу «ближайшего соседа»,

^пшСЯ Sm ) = т in р( ^, Xj ); (3.4)

расстояние, измеряемого по принципу «дальнего соседа»,

pmax (Я Sm ) = maXs р(X,, Xj ); (3 . 5)

расстояние, измеряемое по «центрам тяжести» групп,

, Sm ) = Р( X і, Xm У, С3-6)

расстояние, измеряемое по принципу «средней связи», определяется как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп

pcp.(Se, Sm) = — 2 2 p(Xi, Xj). (3.7)

Академиком А.Н. Колмогоровым было предложено «обобщенное расстояние» между классами, которое включает в себя в качестве частных случаев все рассмотренные выше виды расстояний.

Расстояния между группами элементов особенно важно в так называемых агломе-ративных иерархических кластер-процедурах, так как принцип работы таких алгоритмов состоит в последовательном объединении элементов, а затем и целых групп, сначала самых близких, а затем все более и более отдаленных друг от друга.

При этом расстояние между классами sY_ и S(m,q), являющиеся объединением двух других классов sm и sq, можно определить по формуле

p1,( m,q) = P(S l, S(mq)) = ap1m + Pftq + Wmq + ^(pim plq ), (3.8) где p1m = p(S I, Sm ); p 1q = p(S1, Sq ) U pmq = p(Sm , Sq )

расстояния между классами s і, sm и sq;

а, в, 8 и у числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм.

Например, при а= в=-8=1/2и у=0 приходим к расстоянию, построенному по принципу «ближайшего соседа». При а= в=8=1/2 и у=0 расстояние между классами определяется по принципу «дальнего соседа», то есть как расстояние между двумя самыми дальними элементами этих классов.

И, наконец, при

а = m ; в = —, У=8=0

соотношение (3.8) приводит к расстоянию рср между классами, вычисленному как среднее из расстояний между всеми парами элементов, один из которых берется из одного класса, а другой из другого.