Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 58
Текст из файла (страница 58)
е. сделаем преобразование г" =- 3 ь зХ. Пусть из условия максимума (! 1.1) определены линейные комбинации Ь'„..., Уч. Теперь они будут ортогональны, так как в новом базисе 8 = .— 1„. И пусть 9„..., ()„— соответствующие им значения функционала Ци (К Х). Вместо исходного р-мерного признакового пространства будем далее использовать с)-мерное пространство новых переменных г!' = ((х",Х), предварительно нормированных так, чтобы з'(го>) == 1 (при атом величина 9, не меняется). Расстояние между объектами будем вычислять следующим образом: 4у = ли~' о (г<а! — г(а!)а и ! где га =(УаХ;), о =ср(Щ, ср (.) — некоторая монотонно возрастающая функция.
Метрики для задач кластер-анализа с неколичественными переменными 1 1.2. где ! — номер исходной переменной; 1 — номер категории; 1, — число категорий т-й переменной. Иногда хэмминговой метрикой называют величины (11.2) и (11.2'), у которых отсутствует деление на р. Так как величины уа, могут принимать лишь значения 1 (для й-го объекта реализовалась 1чя категория а-й переменной) или О (в противном случае), то выражения (11.2) н (11.2') совпадают.
Теперь, по аналогии с евклидовой метрикой, можно подчеркнуть важность переменных или отдельных их категорий в формировании различий мс кду объектами, вводя веса либо для переменных, либо даже для отдельных категорий (т. е, бинарных переменных у,').
Некоторые из метрик для измерения расстояний между объектами, когда переменные являются неколичественными, приведены в гл. 5. Из них наиболее простой является хзммингова метрика, которую можно определить как число переменных, у которых объекты Ха, Х! попали н разные категории (11 2) (обн!ес число нереченных1 Расстояние Хэмминга можно рассматривать как квадрат евклидова расстояния в пространстве бинарных переменных, соответствующих категорияч исходных переменных (далее, для краткости, просто в пространстве категорий), т. е. Д(х, Х) = ! '.ь„~~~~ (у! — д','у)' (1 1.2') ь'= ! т =- 1 Один из подходов к присваиванию весов ез1' категориям состоит в переходе к дз-метрике, возникающей в множественном анализе соответствий. Веса для категорий в этой метрике возникают при решении оптимизационной задачи, имеющеи ясную статистическую интерпретацию (см.
п. 17,2.5), а не внесены извне. Поэтому можно полагать, что уз-метрика определяет некоторую есстественную» меру измерения отношений между объектами и, следовательно, ее целесообразно использовать при проведении кластер-анализа в качестве одно~о из основных претендентов. Другой способ введения весов, основанный на эвристических соображениях, предложен в работе 1174). Пусть для 1ьй переменной в категорию / попало пт объектов.
Тогда для двух случайно выбранных объектов определим вероятности следующих событии; у обоих объектов одна и та же )ъя категория 1-й переменной Р 1 у Р ( и а / У 1 1 / 1 ! ( и 1 7 и у й-го объекта реализовалась категория 1, а у 1-го— категория г Р' = Р 1уг у' = 1 ) = 2пг л')пз. Будем вводить веса категорий исходя из следующего соображения.
Пусть для 1-го признака для Ьго обьекта уз~ = 1 (реализовалась/-я категория), а для 1-го объекта — у1',= 1. Чем меньше вероятность Р„'такого события при случайном выборе объектов, тем более близкими их будем считать т. Чтобы получить теперь расстояние для объектов, можно воспользоваться следующим подходом. Определим меру близости между объектами в виде д,а ~ ~чР «11 й,г уг 111.З) 1=1у',г Вклад 1'-й переменной в ьз' (11 4) /,г где „'= (27Р„')И й+ 1)>. з Если оба объекта принадлежат к одной редкой группе (категории), то зто может оказаться более важным, чем сходство или различие по другим переменным.
Алгоритмы классификации с адаптивной метрикой 11.3. Один из способов получения метрики, подходящей для классификации, состоит в ее уточнении («настройке») в процессе работы самой процедуры классификации. 11.3.1. Адаптивная махаланобисова метрика. Квадрат расстояния между точкамн х; и х; задается в этом сз~учае (см. гл. 5) как а'(Хь Х„)= И' =(Х вЂ” Х Г Ч(Х вЂ” Х ), (11.7) где Ч вЂ” некоторая положительно-определенная симметричная матрица.
Для определенности положим, что определитель У равен 1, бе1 (Ч) = 1. Докажем следующую лемму. Л е м и а 11.1. Пусть расстояние между точками задано в виде (11 7); точки распадаются на Й непересекающихся кластеров б„..., Оь; 8 — матрица полного рассеивания (ковариационная матрица для Х). 304 Так как только одно из произведений у4,ум отлично от нуля, а все остальные равны нулю, то реально вклад А,* равен одному из весов в,',. Это взвешивание как раз и увеличивает сходство согласно вышеизложенному принципу— чем мень;пе вероятность реализованной комбинации категорий переменной для наблюдаемых двух объектов, тем больше сходство между этими объектами.
Выражение (11.3) есть не что иное, как скалярное произведение вида Л'=- у' В~'ь (11.5) где матрица Ф вЂ” блочно-диагональная матрица весов вп. Евклидово расстояние из Л' можно теперь получить, используя обычную формулу ~Р(Х„, Х~) =(У 1Гч — 2А'+~У,)ф, (11.6) где о ~)уь1чг=Уь®~ ь= ~ ~~ м~уу',. (=1/= ! Для введения метрики в пространстве неколичественных переменных можно использовать подход, основанный на оцифровке, т. е. присвоении меток неколичественным переменным, например по критерию (17.3!) (см.
й 17.3). Пусть теперь Ф' — величина внутриклассового рассеивания, вычисленная на основе расстояния (11.7), х (Р(Ч)= ~ ~ч~ Р(Хь Х ). (1 1.8) =< х<,х еа Минимальное значение )Р'(Ч) достигается на множестве положительно-определенных матриц У с единичным определителем тогда, ко<да матрица У = <х%-', где%— матрица внутриклассового разброса %=- — ' )' ~ (х,— х„)(х, х„), (1 1.9) => хех еа< а множитель <х выбран таким, чтобы 1У1 = а~%-'1=- 1, т. е.
<х = ~%1'<г. Д о к а з а т е л ь с т в о. Величину внутриклассового разброса можно представить в виде А ь %(Ч)= Х Х <1' — — Х Х (Х< — Х )'Ух «= хе хщео< < < х<. х „ее< х(Х< — Х„)= ~ ч' Зр(Ч(Х< — Х )(Х,— Х„)')= <-. <хпх еа, (11.10) =- и Бр (Ч%). Дальше доказательство аналогично доказательству теоремы а приложении 1 1106, гл. 121.
Рассмотрим теперь следующий двухфазный алгоритм классификации Фаза 1. При фиксированной метрике Ч<'> (1 — номер шага итерации) проводим разделение выборки Х с помощью алгоритма й-средних (Мак-Кина). Число классов й задается пользователем при начале работы алгоритма и дальше не меняется. Фаза 2. По полученной классификации вычисляем матрицу внутриклассового разброса %«< '> согласно формуле (11.9).
Вводим новую метрику с матрицей У«+ < > (%«+») — > (множитель а<+х вычисляется попутно в процесс обращения матрицы %, но, вообще говоря, его использование необязательно) и переходим к фазе 1. Остановка алгоритма производится либо когда матрица Ч<'> перестанет изменяться, либо когда относительное умень- 305 шение критерия цч станетменьше пороговой величины, т. е. либо Юн+ — Ч1Ч -„, либо ((ба — Уп+'1) < з»«. Сходимость алгоритма (в вычислительном отношении) следует из того, что на каждой фазе работы алгоритма значение критерия )Р' убывает.
11.3.2. Состоятельность алгоритма с адаптивной махаланобисовой метрикой. Рассмотрим следующую вероятностную модель — смесь элип- соидально-симметрич++ ных распределений + (см. гл. 19) с ограни+ В В в В ченными непересека- + В И ющимися носителями + + + В В В В и одинаковой ковариационной матри- 1+++ ик В цей " %. + + В а Тогда, если Х— + выборка из такого В распределения, то верна следующая рис. 11.1.
Классификация даииых табл. 11.1 Л е м м а 11.2. Алгоритм с адаптивной махаланобисовой метрикой есть ЕМ-алгоритм (см. гл, 6) решения уравнения правдоподобия для оценки параметров смеси: набора весов а, (1 =- 1, й), средних векторов компонент М, и матрицы ковар наций %. Соответствукацими оценками будут величины и,'л, Х„% (11.9), оцененные на последнем шаге работы алгоритма. Поскольку ЕМ-алгоритм дает оценку максимального правдоподобия, то состоятельность получаемых оценок (при и — сс) следует из общей теории. П р и и е р 11.1.
Рассмотрим набор двумерных данных из п. 12.5.2 (табл. !1.1). Результаты применения алгоритма из п. 11.3.1 представлены на диаграмме рассеивания (рис. 11.1) («крестик»вЂ” точки, отнесенные в 1-й кластер, «квадрат» — точки, отнесенные во 2-й кластер). Состав кластеров: первые 20 точек из табл. 1!.! — первый кластер, точки с 2! по 40— второй.
Как можно судить по рисунку, обычная евклидова метрика здесь не дала бы успешной классификации. 306 Та ба аца 11.1 Номер объекта Номер объекта к)! ! х(з! Исходная матрица "=О Матрица Ч после четырех итераций (конец рабаты алгорит- ма) практически совпала с результирующей матрицей, по- лученной в 1106!. 2,66 — 1,62 1!.3.3. Адаптивная взвешенная евклидова метрика. Предположим, что матрица Ч в (11.7) диагональна: Ч = )))ап (о',, ..., ор). Тогда (11.7) соответствует взвешенной евклидовой метрике.
Йеиствуя так же, как в лемме 11,1, можно показать, что веса о'„минимизирующие внутриклассовый разброс У' (Ч), определя)отея соотношениями От = ба)4)"т, (11.11) где и" — г-й диагональный элемент матрицы %-', а а — нормирующий множитель — выбирается так, чтобы П о,* = 1 е ! (вьпюлнение условия )Ч! =- 1). 1 2 3 4 б 6 7 8 9 )О 11 12 13 )4 !5 16 17 18 19 20 40,89 39,04 38,49 38,08 37,40 35,89 36,71 35,66 34,11 35,27 33,42 33,49 31,92 35 55 34,45 32,33 30,4! 29,86 31,78 28,0! 35,00 36,5) 34,79 33,49 31,85 31,95 33,49 30,55 30,55 29.11 29,! 1 27,74 27,74 27,74 25,62 25,62 25,62 23 97 23.97 22,05 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Зб 36 37 38 39 40 29,93 25.62 25,68 25,00 20,21 23,01 21,03 25,14 23,29 23,68 24,04 26,92 27 ЗЗ 29,38 28,42 30,21 28,36 25,96 21,71 ' 23,42 22,05 22,05 21,53 25,00 21,58 24,45 24,45 26,99 26,99 30,96 29,73 29,73 33,70 33,70 31,99 36,44 36,44 33,08 27,47 28,90 Состоятельность алгоритма, описанного в п.
11,3 1, будет теперь иметь место только в случае модели смеси распределений с дна! ональнои внутрикомпонентной матрицей рассеивания % (см. лемму 11.2). Поэтому на практике можно заменить (11.11) более простым выражением о« =. аа„'. (11.12) Состоятельность для смеси с диагональной внутрикомпонентной матрицеи имеет место и в этом случае, а точность оценок даже будет лучше, В случае недиагональной матрицы % оба способа вычисления весов приведут к смещенным оценкам параметров смеси.
Вычислительная сходимость алгоритма садаптивной диагональной матрицей следует из тех же соображений, что и в п. 11.3.1. В отличие от махаланобисовой метрики, результаты классификации в данном случае зависят от исходнон метрики. 11.3.4. Адаптивная взвешенная метрика типа «сити"блок».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
