Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 59
Текст из файла (страница 59)
Невозмущенная граница неустойчива, если знак [Ур(у )]'1' отличен. от знака р. Рис. 11.7 иллюстрирует эту си- ~Р(У') туацию. Если градиент плотности ~р (У') ГЩ -- у направлен так, как показано на рисунке ~Р - У граница будет удаляться от стационарной границы. Условия неустойчивости можно также получить с помощью разложения Тейлора. Если возмущение мало, то ч (у') = чр(у) + [р2 (у)] (у' у) Р)1с. 11.7. Возмуще- (11.86) ние стационарной где Ч2р(у) — матрица с элементами [т7'р (У) ],, = д'р (Х) /(дх;дх;) ~,, (11 87) В таком случае имеем [ р(у)] ~'==- [ р(у)]'1" + ~Г ["р(у)]1". (11.88) Предположим, что ~'р (У) — неполож1ггельно определенная матрица.
Тогда второй член (11.88) или равен нулю, или имеет $11.4. ПРОЦЕДУРЫ АВТОМАТИЧЕСКОИ КЛАССИФИКАЦИИ 353 знак, противоположный знаку р. Теперь, так как допустимо лю- бое возмущение, то мы можем выбрать его таким, чтобы знак [~р(у)]'1", а следовательно, и знак [~р(у')]'$" был противоположен знаку р. Следовательно, если матрица У2р(у) неположительно определена, граница является неустойчивой.
Этот вывод существенно опирается на предположение о малости Л. На рис. 11.8 показана двумерная плотность вероятности со стационарными границами. Только одна из этих границ устойчива. Остальные границы неустойчивы относительно малых поворотов. Рис. И.8. Асимнтотическая эффективность правила фиксированной окрест- ности. Указанные асимптотические свойства, представляющие интерес сами по себе, дают некоторое обоснование применения правила с фиксированной окрестностью при ограниченном числе объектов.
В пользу этого правила говорят также численные примеры, показанные на рис. 11.5 и 11.6. 5 11.4. Другие процедуры автоматической классификации Мы закончим эту главу кратким обзором других постановок задачи автоматической классификации. Рассмотрение при этом будет носить значительно более поверхностный характер, чем в предыдущих параграфах. Читатель, желающий углубить свои знания в этой области, имеет возможность обратиться к цитированной в этой главе литературе. Сначала мы рассмотрим теоретико-информационный подход к автоматической классификации, а затем — теорию иерархической классификации. ГЛ. 11.
ЛВТОМЛТПх1ЕСКЛЯ КЛАССИФИКЛ!!ИЯ >54 11.4. ПРОЦЕДУРЫ ЛВТОМЛТПЧЕСКОЙ КЛЛССИФИКЛЦИИ Зд~Д 11.4.1. Статистическая связанность. Все упоминавшиеся до сих пор критерии основывались на попарпом сходстве объектов. В [Ватанабе, 1969] была предложена несколько икая постановка задачи автоматической классификации, при которой учитывается наличие статистической связи между переменными.
Вместо того, чтобы классифицировать независимо паб!Иодаемые объекты Х1, ..., Х„(как это обычно делается), вычисля!отея статистические связи между перемеппыь!и х1, ..., х„, и полученные результаты используются для классификации этих переменных, т. е. разделения их на разные группы. Классификация основана на степени статистической зависимости внутри подмножеств х;.
При этом естественно воспользоваться хорошо известной функцией энтропии. Рассмотрим все подмножества переменных х; вида Я„= (х1,„х~,, ..., хр„). (11.89) Индекс подмножества й принимает столько значений, сколько можно образовать подмножеств, а 7 — число переменных в Ус-м подмножестве.
11родположпм, что х; — днскретш.ш случайные величины. Тогда энтропия Я, определяется как Н ф~) = ~~ ... ~ р (хд„..., х1,,) 1п р (х1„, ..., х ), (11.90) х» х6 Энтропия максималы!а, когда переменные х; статистически не- зависимы, Кроме того, можно показать, что Н (~ ) ( ~~ Н ([х!11) ) 1 — 1 (11. 92) для л!обого подмножества Я„.
Статнстическая связанность Я„. определяется следующим образом: (11.93) Таким образом, С(Я,) — это неотрицательная величина, возрастающая по мере того, как элементы Я, становятся все более и более зависимыми. Статистическая связанность подмножества статистически независимых случайных величин равна нулю. Разделим множество Я, состоящее из всех и переменных х;, на два пепересекаю!цихся подмножества Я! и 52. Тогда сум- где р(х,„, ..., х1„) — плотность вероятности дискретных случайных величин: р (хА„..., х, ) = Рг !х,, =- х1„, ..., хА — — "= х1, ). (11.91) марная статистическая связанность обоих подмножеств не превьнпает статистической связанности исходного множества Я, так как согласно известным свойствам энтропии С(Я) [С(51) + С(52) ] = Н(51) + Н(52) — Н(О) ) О.
(11.94) Иам хотелось бы разделить случайные величины на М подмножеств Я1, ..., О',„с минимальной потерей статистической связанности. Таким образом, критерий, подлежащий мпнимизацш1, имеет вид М и У (Й; Я) =- С (Я) — ~~ С (Я,) = .~~ Н (Я;) — Н (Я). (11.95) Этот критерий полностью определен, когда известны совместные вероятности р(х1, ..., х„). На практике, однако, мы имеем только множество из Х наблюдении переменных х;. Следовательно, для того чтобы реализовать этот критерий, мы должны использовать наблюдения для оценки р(х1, ..., х.) методом относптельпь;х частот.
Нелишне напомнить здесь, что постановка задачи автоматической классификации, основанная на идее статистической связанности, отличается От той, которая рассматривалась ранее. Однако эта процедура единственная в своем роде и позволяет решать задачи, для которых другие известные методы непригодны. 11.4.2. Иерархическая классификация. Многие из существующих процедур автоматической классификации нацелены на построение дерева классификации.
Начальная вершина этого дерева соответствует всему множеству объектов, а каждая конечная вершина — отдельному объекту. За исключением конечных вершин, каждая вершина обозначает операцию ветвления, которая делит соответствующее мпо;кество объектов на непересекающиеся подмножества, образующие новые вершины. С другой стороны, каждая верн!Ина связана с «пред!пеству!Още11» вершиной, к которой ее объекты так1ке принадлежат. Наконец, каждой вершине можно приписать численную характеристику— ее уровень. Как и раньше, мы рассматриваем автоматическую класспфикапию как поиск представления, характеризующего некоторые аспекты совокупности объектов, В частности, нас интересует представление попарного сходства объектов с помощью дерева классификации.
Чтобы сделать это, мы должны определить расстояния ме1кду объектами на языке дерева классификации. Рассмотрим дерево классификации для Ю объектов. Оно состоит из начальной вершины, У конечных вершин и промежу- ГЛ. 11. АВТОМАТИЧЕСКАЯ КЛЛССИФИКАЦИЯ $11.4. ПРОЦЕДУРЫ ЛВТОМАТИЧЕСКОИ КЛЛССИФИКЛЦИИ 357 Явном д ввва'в ~я/ Х~ гГ Х, Х,~ Х.— Лв и выполняется ультрал1етрическое неравенство* ) с!т (Х11 Х ') ( 1пах (г!т (Х' Х~ ) дт (ХЛ1 Ху)1, ( 1 ! 98) 11усть объекты, как и раньше, характеризу1отся ътно~кеством векторов Х„..., Х, в метрическом пространстве.
Обозначим расстояния между объектами через г!х(Х;, Х1). Критерием качества классификации служит мера согласия между расстояниями на дереве и расстояниями меи ду объектами. Такая мера задает- *) Читатель может проверить, что неравенство треугольника явля. ется прямым следствием более сильного ультраметричесного неравенства, точных вершин. Каждая вершина, кроме начальной, имеет одну и только одну предшеству1огцуго вершину. Каждои вершине приписано число — ее уровень на дереве. Из любой конечной вершины можно построить и притом однозначно траекторию спуска, ведущую к предшествующей вершине, предшествующей этой предшествующей и т. д. до начальной вершины.
Расстоя- ние между л1обыми двумя Напльиаи вф7лыжу конечными верп1ипами моиз но определ11 гь как ! уровень верпц1пы, лежаГ7' щей на пересечении соот- Г ветствующих траекторий. Типичное дерево клас- Лрвувжутж~а~ сифи ка цип представлено 'УХ г4 веРЛУна 1а ри' 11.9. 1!а дереве ! 3 обозначены уровни, на- 1 чальнои вершины и про- 1 межуточных вершин. Показань1 траектории спуска для конечных вершин Х1 Рнс, 11.0 Дерево нам сифинацни. и Хз. Расстояние меж з ие между этими двумя вершинами г1,(Хц Хз) равно 3,7. Разумеется, приписывать вершинам уровни можно многими способами.
Введенное выше расстояние обладает метрическими свойствами, если уровни удовлетворяют следующим условиям: 1. Все конечные вершины имеют нулевой уровень. 2. Уровни всех не конечных вершин больше нуля. 3. Уровень вершины всегда меньше, чем уровень предшествующей ей вершины. В частности, если условия 1, 2 и 3 выполнены, то д,(Хь Х;) = г1,(Хо Х;) ) О (неотрицательность), (11.96)' г1,(Х;, Х„) = О, если ъ' = у (симметричность), (11.97) ся выражением г (г' Х*) =- Д .-~ 117 !ах (Х. Х7) — г1т (Х;, Ху)Р, (11.99) 1=2 1=-1 где ~н — весовые коэффициенты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
