Имя материала: Эконометрика

Автор: В.С. Мхитарян

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 - среднее значение і -го признака;

Подпись: 1 " _
— Е (Xii — xi)2 - среднее квадратическое отклонение l-го признака.

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, ... , хк наблюдаемых векторов Х сравнительно небольшое число наиболее существенно информативных, т. е. уменьшить размерность наблюдаемого пространства.

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

Пусть si- i-я группа (класс, кластер), состоящая из 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) приводит к расстоянию рср между классами, вычисленному как среднее из расстояний между всеми парами элементов, один из которых берется из одного класса, а другой из другого.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |