Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 14
Текст из файла (страница 14)
9! В= — !в~У,(Х) Уз(Х)) бХ. (1. 43) Оно также инвариантно по отношению к взаимно однозначным отображениям координат, аддитивно по отношению к независимым компонентам, обращается в ноль при В случае модели Фишера В = /Р(8, (1.44) и в общем случае двух нормальных распределений (1.13) ! , /Х,+Е1 ~-1 в= — (м — м)'~ ' ') (и — м)+ 3 з ~ —,(х,+в,)~ + — 1п (1.45) з ! ~,1~/з! в !1/з ' С помощью расстояния Бхатачария удается оценить сверху среднюю ошибку классификации при использовании критерия отношения правдоподобия Ь < (л, и )'/з ехр ( — В).
Более подробно зти вопросы обсуждаются в )169! и (160, гл. Зи9!. 1.3. Два класса, заданные генеральнымн совокупностями В параграфе рассматривается случай, когда классы описаны путем указания всех входящих в них наблюдений. Введенные ранее понятия — такие, как отношение правдоподобия, различные характеристики качества классификации, могут быть определены и в этом случае. Для описываемых ниже правил классификации подход с явнымуказанием возможных наблюдений более естествен. Зтн правила (см. п. 1.3.2— 1.3.6) не опираются прямо на отношение правдоподобия, нов простых случаях дают хорошее приближение к решающему правилу, построенному на его основе.
Интерпретируемость полученных формул классификации часто служит з вт залогом их успешно~ о применения. В этом смысле выделяются древообразные алгоритмы (см. п. 1.3.2), методы поиска характерных закономерностей (см. и. 1.3.4) и определение областей компетентности нескольких правил (см. и. 1.3.5). 1.3.1. Вычисление основных показателей. С целью большев преемственности обозначении с последующими главами зададим классы с помощью последовательности пар (Х„, у„), й=-1, 2, ..., и), (1.46) где Մ— вектор возможного значения наблюдения, а у« ---- 1, если Хд принадлежит первому классу, и у« = 2, если второму.
Будем считать также, что новые наблюдения извлекаются наудачу и независимо друг от друга из ряда (1.46). Таким образом, априорная вероятность гипотезы Н~ 0' =-1, 2) пт — — Р(у =/) =~~.", 1/и; функция распределе«н«=г ния Х при гипотезе Н! будет г (Л ! Нт)= ~ 1/ль мд„=ь х„<г где л/ — — ~ 1. Использованная при суммировании запись м««-.=~ Ха ( Е означает, что дл Я всех 1 < ( ( Р имеем х«п! < ап>. Отношение правдоподобия в точке Х Ряд излагаемых ниже методов опирается на функции потерь, введенные в и. 1.1.4.
Они легко могут быть оценены по ряду (!.46). Так, например, определенная с помощью формул (1,3!) н (1,31') вероятность ошибочной классификации запишется (1.31") В дальнейшем будем широко оперировать понятием условного математического ожидания, каждый раз подразумевая, что читатель самостоятельно может перейти от формулы типа (1.3Г) к (1.31"). 1.3.2. Древообразные классификаторы. В основе описываемой ниже группы методов лежит понятие бинарного дерева — графа. Зти деревья принято изображать в перевернутом виде: корень — сверху, листья — - внизу (рис.!.5), при этом под словом «кореньз понимаем самый верхнии узел (вершнну) графа, а под словом «лист» — узеч, из которого вниз не вычодят стрелки к распочоженным ниже узлам.
С каждым узлом 1 дерева связаны следующие объекты: )«', — подмножество пространства наблюдения (Й); )㫠— подмножество генеральной совокупности (1.46) с Хлеб А, — правило классификации из разрешенного набора правил для Х с йн Крометого, для узлов «не-листьев» вводится правило разбиения Я, на два подмножества Янп и ймп, таких, что Я~п, () Рмо=г г Л)««„Н,=И. "КОРЕНЬ" Рис. 1,5. Пример графа лрезообразиого классификатора: Π— проке»куточиый узел; П вЂ” концевой узел — «лист» Древообразные классификаторы определяются рекурсивно. Для этого задаются: 1) критерий качества классификации на )7~', 2) разрешенный класс правил для построения А,; 3) способ построения Нно и Я„п, 4) правило объявления узла листом, т. е.
правило прекращения последующих делений. В качестве корневого (нулевого) узла принимается узел с )св, совпадающим со всем пространством возможных значений Х, н )гв - ((Хю ув), й 1, ..., и). Критерий качества классификации. Пусть с,— штраф за ошибочную классификацию, когда верна гипотеза Н, и функция потерь Я классификатора определена согласно (1.32'). Возьмем в качестве меры качества классификации на Рв классификатора Аг (1.47) Я()«„А,) =Е(д '(Х) )Хс Й~). При этом чем 1',1 меньше, тем классификатор лучше. Разрешенныи класс правил.
Используются максимально простые классификаторы: линейные, линейные с дополнительными предположениями, например о структуре зависимостей признаков; простейшие, относящие все наблюдения 69 Х Е Я, к одной из классифицируемых совокупностей. Среди всех допустимых правил в качестве А, выбирается правило, минимизирующее выбранную функцию риска. При этом ограничимся классами правил, на которых минимум достигается.
Простота разрешенного класса правил компенсируется структурой дерева. Правило разделения. Рассмотрим шкалу, в которой измерена 1-я координата Х (! = 1, ..., р). Если шкала номинальная, то элементарными событиями Т будем называть события вида хш = а или хо> Ф а, где а — одно из возможных значений хб'. Если же шкала порядковая или интервальная, то элементарными событиями будем называть события вида хш ~ ~а. Рассмотрим теперь всевозможные разбиения Я~ с помощью элементарных событий (йс () Т, И, П Т), таких, что ппп (Р(Х Е )~с () Т), Р(Х Е й, Д Т)) > е„(1.48) где е, — некоторое заданное число. Тогда по определению критерия качества классификации (1.47) (2Яс А,)=Р(ХЕ Т!ХЕЛЕНЕ(ч"~(Х)(ХЕЯ,()Т)+ + Р (Х Е Т1 Х Е Р,) Е (9 ' (Х) $ Х Е йю П Т) Рэ ) Р (Х Е Т ) Х Е йД 1п( Е (дл (Х) ( Х Е Яс П Т) + + Р(Х Е Т)ХЕ ЙД !п!Е(9л(Х) [ХЕ й~ ПТ).
(1.49) Нижняя грань в правой части (!.49) берется по всем допустимым классификаторам. Пусть Т, — одно из элементарных событий, удовлетворяющих (1.48), на котором достигается максимальная разность между левой и правой частями (1А9); положим тогда )('по — — Я, () Т, и 1т„п! — — й, () Т,.
Правило объявления узла листом. Узел 7 объявляется листом, если не существует элементарного события, удовлетворяющего условию (!.48), или такое событие существует, но Я(йо А4 — Р(Х Е Тд ! Х Е И,) Я (Ж ап А~ «))— — Р (Х Е Т~ ( Х Е )т (1) ) !в ф, < гь А, <р>) ~ ее. (!.50) Наглядный смысл условий (1.48), (1.50) очевиден: от усложнения классификатора должен быть заметный выигрыш и не следует слишком мельчить разбиения. Древообразные классификаторы обладают рядом привлекательных свойств.
Они относительно просты: при уменьшении е, и е, и соответствующем росте числа ветвей сходятся к классификатору, минимизирующему выбранную функцию потерь; инвариантны относительно монотонных преоб- 70 (1.51) Ф; (Х) = ъ ф(р(Х, Хь))/лл где <р (и) — некоторая известная положительная функция положительного аргумента, стремящаяся к нулю при и- оо, например ехр ( — ар") или (1 1 ара)-', где а ) О, р ) О. Правило классификации записывается: Ф,(Х) Ф, (Х) = (Н», 1Н, (1.52) Изложенный алгоритм близок с описываемым в 4 3.3 непараметрическим методом классификации. Различие заключается в том, что статистическому подходу более соответствовало бы использование: 1) вместо относительного потенциала в Х абсолютного, как лучше учитывающего априорные вероятности классов и 2) вместо разности (1.52) отношения Ф (х) )Н (1.53) 71 разований координат; легко интерпретируемы; при выборе в качестве допустимого класса простейших правил допускают наличие в классифицируемом векторе Х ненаблюдаемых, так называемых «стертых», координат, если, конечно, эти координаты не используются в качестве аргументов ветвления.
В отечественной литературе древообразные правила называют также логическим методом классификации (941. 1.3.3, Метод потенциальных функций, Это — исторически один из первых достаточно универсальных методов построения классификационных правил в условиях хорошей разделимости классов ~13, 131).
Он представляет собою пример результата научного направления, центр тяжести которого лежит не в оптимальном решении задачи классификации при дефиците выборочнон информации, а в разработке рекуррентной процедуры, удобной для ЗВМ и дающей решение в условиял большой выборки. Метод основан на предноложении, что объекты с близкими значениями Х принадлежат одному классу. Поэтому при классификации нового объекта Х надо лишь подсчитать «относительные потенциалы» в Х, порожденные объектами первого и второго классов, и отнести объект к тому классу, чей относительный потенциал выше. Более точно: пусть в пространстве наблюдений определено расстояние р, например евклидово.
Относительный потенциал в Х, созданный объектами ~-го класса, подсчитывается как 1.3.4. Поиск характерных закономерностей. Ниже описывается общая логическая схема одного из наиболее известных алгоритмов, возникшего из эвристических соображений одеятельносги человека при распознавании образов — алгоритма «Кора» 128, 431, В нем рассматриваются все возможные конъюнкции вида Тп П Т», () ". Л Т«, (1 ( 1«), (1.54) где Т вЂ” события, определенные в п.1.3.2 при введении правил разделения, а 1, — некоторое наперед заданное число (в алгоритме «Кора» 1« =- 3). Среди коныонкций выделяются те, которые характерны (верны на обучающей выборке чаще, чем некоторый порог 1 — е,) для одного из классов и не характерны для другого (верны реже, чем в доле случаев е, (в алгоритме «Кора» а, =- О)).