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) приводит к расстоянию рср между классами, вычисленному как среднее из расстояний между всеми парами элементов, один из которых берется из одного класса, а другой из другого.
Обсуждение Эконометрика
Комментарии, рецензии и отзывы