Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика, страница 15

Если коэффициент корреляции между какими-либо двумя выделенными конък»нкциями по модулю более 1 — а„то оставляется «наилучшая» с точки зрения различения классов из них, а если конъюнкции эквивалентны, то более короткая (имеющая в представлении (1.54) меньшее 1) или просто отобранная ранее. Параметры е,, е,, е, подбираются так, чтобы общее число отобранных (информативных) конъюнкций не превосходило некоторого числа гп.

Для нового наблюдения Х подсчитывается т, — число характерных для (.го класса отобранных коньюнкций„которые верны в точке Х. Если гп, ) и», то принимается решение, что верна гипотеза г»'„в противном случае — что верна гипотеза Н». Поскольку при отборе коньюнкций в принципе возможен полный перебор, вычислительный процесс должен быть организован эффективно, чтобы не рассматривать бесперспективные ветви. Алгоритм «Кора» зарекомендовал себя удачным в ряде прикладных областей 128, 821.

Идея поиска закономерностей, характерных для одного из классов, положена в основу алгоритма автоматизированного поиска гипотез [491, 1.3.5. Коллективы решающих правил. В прикладных исследованиях для классификации наблюдений иногда одновременно используется не одно, а несколько решающих правил. При этом, естественно, встает вопрос о выборе правила объединения частных заключений и как ответ иа него возникает двухуровневая схема принятия решения (рис, 1.6).

На рисунке первый уровень — блоки А, -- Аы второй — блок синтеза. В изложенном выше алгоритме «Кора», если считать отдельными правилами отобранные конъюнкции, решение принимается большинством «голосов», осуществившихся при Х конъюнкциях. В системах, в которых используются высокоспецифическне (см, п. 1.2.1) правила риска, объеди- 72 пение возможно по принципу емаксимум предсказанного риска>. В ПЗП предложен третий подход — выделение областей компетентности каждого из использованных алгоритмов. Пусть функция потерь (',! ()с, А) правила А на множестве Я определена по формуле (!А7). Правило Ам (1 < < !е (Е) считается на Й компетентным среди правил У А!(! <1(Е), если (~ (Я, А,.) = ш !п (;! (й, г1,).

с При классификации сначала выбирается наиболее компетентный алгоритм, за- ем го помощью прини- рис. ! 6. двухуровневая схема мается решение (рис 1.7, принятия решения где Р— блок выбора наиболее компетентного алгоритма). Пусть пространство наблюдений !с разбито на Е областей йь таких, что 7( .= ([ 7т! и й! П )хп —— 0 при ! зь !' и для каждого зс, указан компетентный на нем алгоритм Ап. Тогда на первом шаге по значению Х находится !с,: Х с )с, Рис. !.7. Схема классификации с использованием ооластей компетентности и по !с! — номер компетентного на нем алгоритма !е.

На втором шаге правило А и применяется к Х. В качестве примера изложенного подхода можно указать древообразные классификаторы (см. п. 1.3.3), где механизм нахождения 77, -- ветви дерева (без листьев), правило решения А,*— правило соответствующего листа. Опишем два простейших правила нахождения областей компетентности. Мепшд априорного разбиения пространства наблюдения Я на подобласти основан на профессиональных соображениях конкретной науки, Для каждой из введенных подобластей находят компетентное на ней пранило классификации. Этот метод удобен тем, что введенные области легко строить и интерпретировать. Во втором методе области ком- 73 петентности Я~) строятся локально путем построения алгоритма, с помощью которого для каждого наблюдения можно вычислить, какой области Р, оно принадлежит.

Пусть для каждого Х, можно ввести семейство вложенных друг в друга расширяющихся окрестностей. Фиксируем какое-либо число /г и для Х„найдем наименьшую окрестность О (Х „), которая включает в себя не менее й точек последовательности (1.46). Пусть далее сн =- 1, если !.е наблюдение последовательности классифицировано А~ алгоритмом правильно, и сп —— - О в противном случае; с, = Хс,, где суммирование проводится по всем точкам, принадлежащим 0(Х,), и (!.и) см = гпах сь Тогда точка Х, объявляется принадлежащей области комиетентности правила Ам.

Чтобы обойти случаи, когда максимум в (1.55) достигается иена одном, а на нескольких значениях 1„, ..., 1,, положим (* равным наименьшему из них. 'т' Если на Я определено расстояние между точками р, то окрестности можно задавать с помощью расстояний и в определении сь вместо 1 брать д (р (Х„Х„)), где и-- некоторая убывающая функция от положительного аргумента. Например, д (р) = 1((а -(- р), где а > О. В 1!31! предлагается для выделения областей компетентности использовать также метод потенциальных функций. !.4.

Отбор информативных переменных Любое практическое исследование с применением методов статистической классификации включает в себя в виде специального этапа отбор информативных для классификации переменных. Дело здесь заключается не столько в экономии затрат иа сбор не- или малоинформативных признаков, сколько в том, как увидим в следующей главе, что включение в решающее правило в условиях дефицита выборочной информации малоинформативных признаков ухудшает (!) среднюю эффективность классификации.

В этом параграфе рассматриваются два принципиально отличных подхода к отбору переменных. В первом нз пих делаются сильные математические предположения о характере классифицируемых распределений и это позволяет четко и однозначно ответить на вопросы, следует или нет включать рассматриваемую переменную в решающее правило и если нет, то почему.

Во втором подходе специальных предположений не делается, предла- гаются некоторые эвристические итеративные процедуры, каждый шаг которых разумен, но общий результат их применения осмыслить и изучить трудно. 1.4.1. ййодеаь Фишера с дополнительными предположениями о структуре зависимостей признаков. Рассмотрим сначала простейшую математическую модель двух нормальных распределений с независимыми переменными Ж,=Ж Ж, =Ж ) + ч~ (х«> (ш<О ! п>«>)<2) п«(п>«> ш<У>). «, т>еа Решающее правило и расстояние Махаланобиса между Ж„и Ж, согласно (1.12), (1.39) имеют вид /< (Х) = Х (х<'> — (л>«>+ п><О)/2) (л>«> — т«>) а< ' ~~с; (1.56) <Р(Ж„Ж )=Х(т"> — т<'>)ап< ', (1 57) Естественно считать неинформативными переменные, у которых не отличаются средние, т.

е. соответствующие то>— — и«<> = О, и малоинформативными переменные. у которых (т<'> — и><><>)'о< ' ( з, где е — некоторое число. Таким образом, в простейшей математической модели об информативности переменной можно судить по ее одномерным распределениям при Н, и Н,. В общем случае это неверно. так как даже переменные, имеющие идентичныеодномерные распределения при Н, и Н„могут нести существенную информацию о проверяемых гипотезах в силу взаимозависимости переменных. В качестве примера вернемся к рис. !.!.

Распределения х<'> при обеих гипотезах совпадают, однако эта переменная в совокупности с х<'> существенна для классификации. Рассмотрим теперь модель Фишера с древообразной структурой зависимостей (ДСЗ) переменных !12, п. 4.2.31 Ж, =- Ж (М,, Е) и Ж, = Ж (М,, Х), где Х имеет ДСЗ. Внедиагональные элементы л-< = Цоо!! отличны от нуля тогда, когда они принадлежат 6 — графу структуры зависимостей распределений. На основании (!.12) й(,>() ь (х«> (и>«> 1 п>«>)<2)п«(п<«> п><О) ! В последнюю сумму наряду с парой (<, 1) входит и (), <). Таким образом, в й <Х) входят только те переменные, для которых или 1) их индивидуальный вклад в разделение отличен от нуля, т.

е. т<,'~ — о<<О Ф О, или 2) индивидуальныи вклад равен нулю, но они непосредственно связаны на < рафе структуры зависимостей с переменными 1, для которых т<п — т<п ~ О. Этот результат остается верным и для распределений с Й (й)-зависимостью 112, 4.41. 1.4.2. Функции потерь. Пусть 5 с= (1, ..., Р) — некоторое подмножество координат Х. Обозначим Х<з> входящие в него компоненты Х. Для того чтобы произвести отбор информативного подмножества координат, вводится функция потерь <! (5), обладающая следующими свойствами: для 5< =-5 а(51).=--(г(5); (1.88) для <Э (5,) =- <;! (5) наборы признаков 5, и 5 считаются эквивалентными, для <,< (5,) ) <,< (5) набор признаков 5 считается предпочтительнее набора 5,.

В качестве <;1 (5) можно взять, например, ожидаемую ошибку байесовского классификатора <,<а (5) = Е (1 — щах и, (Х<з>)), (1.59) где п, (Х<з<) — условная вероятносты ипотезы Н< при наблюдении Х<з<, а математическое ожидание берется по мере Р (Х) =.- ли,Р (Х ~ Н,). Нетрудно показать, что для <,<л условие (1.58) выполняется. Это условие помогает эффективно организовать процесс отбора признаков. Пусть, например, исследованы два подмножества признаков 5, и 5ч и пусть <! (5,) (<',< (5,), тогда нет необходимости исследовать любое из подмножеств 5„так как в силу (!.88) заранее известчо, что они менее предпочтительны, чем 5,.

Это соображение легло в основу многих высокоэффективных вычислительных алгоритмов. Заметим, что для определения с< можно использовать любую из мер разделимости распределений, введенных в п. 1.1.8. Для это~о достаточно положить <,< (5) = — гп (Р, (Х< з>), Р, (Х<з>)), где и< — соответствующая мера, а Р, (Х<з)) — функция распределения Х<з> при условии, что верна гипотеза Н< (< =- = 1, 2). Взаимоотношения между различными функциями потерь систематизированы в 1!891. Лля нас только важно, что нет функции потерь, которая отбирала бь< признаки в том же порядке, что и (!в.