Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 48
Текст из файла (страница 48)
Рассмотрим более детально алгоритмы семейства, реализующие выделение таксонов при помощи поиска локальных максимумов функции плотности распределения объектов в признаковом пространстве Х. Алгоритм иа основе модельной локальной плотности. Выберем в качестве модельной некоторую плотность распределения («(Х), имеющую единственный максимум в нуле, и пусть Хх ~ Х» — такая область, что Рь (Х с Хх) — -)». Будем считать, что Х, является носителем плотности )«(Х), т. е.
Х» = — (Х Е Х»: Г«(Х) ) О). Возьмем 246 оценку плотноети распределения 1 (Х) по выборке (Х„ , Х„) в виде я я 7(Х)= ч~ р,~„(Х вЂ” Х,), р,»О, ~ н!=1, ! 1 ! ! где тр!) — веса точек (Х!). Тогда первые два блока алгоритма можно описать следующим образом: 1. Для каждого Х! выделим подвыборку Х (1) = (Х!,, ..., Х! !), составленную из всех элементов Хл для которых Х; — Х,б 14.. 2.
Упорядочнм выборку (Х„..., Х„) при помощи плотности ) (Х), т. е, считая, что Х! ~ Хл если т) (Х;)»7 (Х!). Например, возьмем модельную локальную плотность в К« вида 11х(1! т«вЂ” 1,(Х) =1,.„(Х) =с,,.11 — — ) (';--) где с„,« —— га = (2а + р) пз и а' — дис[(2а+ р) «1" ~ тг(а)«« персия случайного вектора в Я«с плотностью распределения ~, (Х) (см. $20.2). Рассмотрим семейство алгоритмов для области Х« = = — (Х с К«, !!Х ~ ~ < г).
Это семейство имеет два управляющих параметра: г и и. Похожими на элемент Х! считаются все элементы выборки, отстоящие от него не более чем на г, т. е. Х (!) = (Х,: ~~ Х! — Хт (~ ( г ). При фиксированном гс ростом !х в модельной плотности г„„, (Х) о' убывает и в упорядочении выборки все большее значение начинает иметь разброс кортежа Х (!) относительно Х„т. е. на первые места выходят Х; с меньшим разбросом кортежа Х!!! относительно Х!.
Для модельной плотности ~р, з (Х) н одинаковых весов р!, 1 ( !' < л, классификация проводится при помощи плотности распределения л !!х! - '„ 2 ( — ~~-) = с-! ! =-'ы. '~ ( — 1(Х вЂ” Х, 1(*)„' «гФ 1(х- !((и~ »л, которая с точностью до константы —,.' совпадает с функционалом качества в алгоритме Форель. Ясно, что выделение первого таксона в алгоритме Форель представляет собои градиентный поиск локального максим) ма плотности 1 (Х). Таким образом, если выборка представляет собой объединение сгустков, каждый из которых полностью помещается в шар радиуса г, то алгоритм Форель даст практически тот же результат, что и алгоритм классификации методом Эратосфена (АКМЭ) для плотности1»,» (Х). Следующий таксон алгоритмом Форель выделяется после того, как из выборки удалены точки первоготаксона, и т, д., что в ряде случаев (например, не угадан порог г) приводит к сильнои зависимости результата классификации от выбора начальной точки, в то время как в АКМЭ вообще отсутствует необходимость выбора начальной точки.
Алгоритм на основе ближайших соседей. В этом алгоритме классификация проводится, по существу, при помощи оценки плотности распределения, получаемой по методу «ближайших соседей». Выберем параметр А, О ( А < 1, и возьмем в качестве л» целую часть числа ),а, где л — объем выборки, поступившей на классификацию. Первые два блока этого алгоритма будут следующими. 1. Лля каждого Х» составим кортеж Х (1) = (Х; = Х;, ..., Х~,) из т ближайших к нему элементов. 2, Пусть 5 1Х (1), Х~) — разброс кортежа Х (1) относительно Х,, Упорядочим выборку (Х,, ..., Х„), считая, что Х~ ~ Х„если 5 (Х (1), Х ~) ( 5 (Х (1), Хэ)- В блоке 2 можно испольэовать также следующий способ упорядочения выборки (Х,, ..., Х,): 2'. Пусть г, (т) — расстояние от Х~ до самого дальнего из т ближайших к нему соседей (Х;, = Хо "., Х; Упорядочим выборку (Х„..., Х„), считая Х~ ~ Хл если г; (пт) ( гэ (и).
Описанные здесь блоки 1 и 2' вместе с блоком 3, общим для всех алгоритмов метода просеивания, составляют алгоритм Уишарта 13321, предложенный им в качестве альтернативы агломеративной процедуры иерархической классификации по методу «ближайшего соседа» в тех случаях, когда она приводит к нехарактерным для исследуемого явления объединениям типа «цепочного эффекта». ВЫВОДЫ 1, Описаны наиболее известные и хорошо зарекомендовавшие себя при решении прикладных задач алг оритмы разбиения исследуемой совокупности объектов на классы как при известном, так и при неизвестном заранее числе классов. 2.
Общим для всех рассмотренных алгоритмов является то, что в них распределение объектов по классам (классификация) осуществляется при помокни сформированного в ходе классификации набора «ядер» классов. Понятие ядра класса в широком смысле обсуждается в и. 7.4, 3. Алгоритмы различаются правилами распределения объектов по классам, типом ядер, тем, является ли класс четким или нечетким (см.
й 7.5) подмножеством исследуемои совокупности объектов, является ли набор управляющих параметров фиксированным или настраиваемым в ходе классификации (см. й' 7.3), а также тем, как пост> пают объекты на классификацию: вся совокупность сразу 1параллельные алгоритмы) или порциями по одному, по нескольку (последовательные алгоритмы). Глав а 8.
ИЕРАРХИЧЕСКАЯ КЛАССИФИКАЦИЯ Основные определения 8.1. Пусть Х = (Х„..., Х„) — конечное множество. О п р ед ел е н и е 8.1. Иерархией з на Х называется система подмножеств (классов) (5:5 с Х), такая, что 1) Хба; 2) (Х ) ~ з„1 = 1, ..., л; 3) если классы 5 и 5' из з имеют не пустое пересечение, то 5' с 5 либо 5 с: 5'. П р и м е р 8.1. Пусть Х = (Х,„..., Х,). Тогда система подмножеств з = ((Х,)„~' =- 1, ..., 7, (Х„Х,), (Х, Х„Х,), (Х„Х„Х,), Х) является иерархией на Х. Исследование структуры иерархий удобно вести в терминах теории графов 1831.
О п р е д е л е н и е 8.2. Графом 6 =6 (з) иерархии з на Х называется ориентированный граф (У, Е), вершины и с У которого соответствуют множествам 5 с з, а ребра е ŠŠ— парам (5', 5), таким, что: 5' Ф 5 5' с: 5 и в з не существует 5" чь 5', для которого 5' с 5" с 5. Ребро е = (5', 5) изображается стрелкой с началом 5' и концом 5.
П р и м е р 8.2. Граф 6 = (У, Е) иерархии з из примера 8.1 имеет множество вершин: У = (и, = (Х,), 1 = 1, 7, ~', = (Х,, Х,), и„= (Х.ь Х„, Ха), и„= (Х,, Х,, Х,), о„= Х) (рис 8 1). В графе иерархии вершина может быть концом несколы.их стрелок, но, каь следует из 3 ) определения 8 1, она является началом только одной стрелки. О и р е д ел е н и е 8.3. Иерархия называется бинарной, если любое множество 5 Е з, содержащее более одного элемента, является объединением множеств 5' и 5"' из з, где 5' П 5"Р= И 4 ' ~а мха, Рис, 8.1. Граф 6 (К Е) иерархии а аа примера вл Иерархия з из примера 8 1 не является бинарной, так как множество (Х„, Х„Х,) нельзя представить в виде объединения двух множеств изз. Нетрудно показать, что в любой бинарной иерархии з разбиение множества 5 Е з иа подмно- кества 5' и 5" из а, т.
е. представление 5 = 5' (1 5", однозначно. Иерархия является бинариои тогда и только тогда, когда в ее графе каждая вершина, соответствующая множеству, содержащему более одного элемента, является концом двух стрелок. О п р е д е л е н и е 8 4. Иерархическон классификацией данного множества объектов Х = (Х,, Х„) называется построение иерархии з на Х, отражающей наличие однородных, в определенном смысле, классов Х и взаимосвязи между классами. Алгоритмы иерархической классификации бывают: дивизимнае, в которых множество Х постепенно разделяется на все более мелкие подмножества, и агломерагпивные, в которых точки множества Х постепенно объединяются во все более крупные подмножества.
Графы иерархий, полученных при помощи этих алгоритмов, называются соответственно дивизимными и агломеративными Если их изобразить на плоскости так, как на рис 8.2, то видно, что они описывают процедуру классификации при движении вверх по оси ординат Поэтому дивизимные алгоритмы называют также нисходящими (движение против стрелок), а агломеративные — восходящими (движение вдоль стрелок). Методы и алгоритмы иерархической классификации В основе алгоритмов иерархической классификации лежит тот или инои критерии качества Я (5,, ..., 5ь) разбиения множества 5 на подмножества 5,, ..., 5„(см. 2 8.4).
Обычно используются бинарные алгоритмы, ко~да я = 2 В этом случае (',((5,, 5,) имеет смысл близости р (5„5,) между множествами 5, и 5, (см 2 5 3). Далее, говоря об алгоритмах иерархической классификации, будем иметь в виду только бинарные алгоритмы. 8.2.1. Дивизимные алгоритмы. Дивизимные алгоритмы сзроятся на принципе разделения множества 5 на подмножества (51, 5з), такие, что (5(, 5$)=агя шах р(5„, 5з). (8 1) з,цз,=з В реально используемых алгоритмах берется некоторое приближенное решение задачи (8.1), так как точное решение ее ~ рудоемко даже при относительно небольшом объеме элементов в 5 Вид меры близости р (5,, 5,) может меняться в ходе алгоритма.
Изложим на важном примере основные приемы разделения класса 5 на подклассы 5, и 5 в дивизимных алгоритмах. Пусть Х = (Х„..., Х„), где Х, = (х<», ..., х<л>) с Гсл В качестве критерия однородности класса 5 ~ Х возьмем статистический разброс а(5) =- ~ !)Х вЂ” г!), (8.2) хез где 2 = — ~ Х вЂ цен класса 5 и ))Х вЂ” 2))' — квад- 1 151 хмз рат евклидова расстояния между Х и У. Положим р(5м 5з) =Я(5,05з) — Я(5,) — Я(5з), 5, П 5,= В, (8.3) т. е.
мерой близости между классами считаем приращение статистического разброса при объединении классов. Пусть Г (5„5,) == 1~ (5,)- (~ (5,). Для фиксированного класса 5 имеем: р (5„5,) + г (5„5,) = сонэ(. Следова- тельно, для решения задачи (8.!) разделения класса 5 до- статочно найти (5*о 52) = агп ппп Р(5„5 ).
(8.4) ь~0зз=з Функционал Р (5п 5х) является функционалом качест- ва разбиения 5 на подклассы 5, и 5, в методе 2-средних, по- этому для получения классов 5; и 5х можно использовать алгоритмы 2-средних (см. и. 7.2.1). Опишем теперь распространенный способ разделения множества 5 на подмножества при помощи линейного клас- сификатора: 5, =- (Х Е 5: о' Х а), 5з=(Х Е 5: о' Х . а), где о ЕЮп, ((о1= 1. Для данного вектора о Е КР, 1(о)1 = 1, рассмотрим проек- цию ш КР-~- Ж; Х-+ у = о'Х и обозначим через 5 образ множества 5. Положим р (5„5,)=Я (5, () 5,) — Я (5,)— — Я (5,), где Я ( ) — как и выше, статистический разброс.
Пусть р,(я,~~= — „' (Ху)'. —.' (Хг)'. Тогда имеет место формула: / ~2 р(5,5д= Р.(5.. 5з) — „~2.'У), хс ь где ш, гп, и т, — число элементов в множествах 5, 5, и 5, соответствейно. Следовательно, для фиксированного 5 достаточно найти: (51, 52)=ага гпах Р,(5о 5з). (8.6) ввоза Пусть у, > у, > ... > у,„— упорядоченная числовая по- следовательность элементов множества 5 «Р'.
Так как ищем на прямой точку а, разделяющую зту последователь- ность на две части, то 5( ) Ь ° ". р,).5 5(юх) Ь,+ °" и) (8.6) для некоторого т„т. е. в этом случае вместо метода 2-средних можно применить для решения задачи (8.8) метод последовательного перебора. Вычислив числовую последовательность (<р (и,) = Р>(5, (т,), 5з (и,)), т, = 1, т — 1), получим пару (5; 5,(т!), 5> —— 5, (т!), где т! = агя шах <р(т ), <м~<ччт — ! и, следовательно, 5~=(ХЕ5>п Х<у„.~, 5э=-5 .5*,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
