Фукунага - Введение в статистическую теорию распознования образов, страница 58

АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ 5 11.3. Пепараметрические критерии качества классификации В этом параграфе мы получим другое семейство критериев, исходя из несколько иной точки зрения. Результаты, вообще говоря, не будут зависеть от обычных параметров, таких, как матрицы рассеяния. Поэтому мы называем эти критерии непариметрическими [Кунтц, 1972 б]. 11.3.1. Критерий согласованности. Для каждой пары векторов Х„, Л, можно определить расстояние |гх(Х„Х,) между ними. Нап риме р, 2.(х„, х,) = ~!х„— хд. '(11.60) Кроме того, предположим, что на й определена межклассовая метрика |2„(ю„~, ю„), т. е. ги (ю|7 7 юЙ.) = гх(2~~~7.7 г~~й ) Аналогично тому, как мы это делали при рассмотрении нелинейных преобразований, можно определить согласованность классификации й и конфигурации Х* следующим образом: 7"7' т ,7 (й; Х*) = (1/А|),~~,'~~ / (Хт, Хз) [|го (езц„, ю~ ) — |гх (Х„, Х,)~2.

т=2 я — 1 (11.63) Выражение (11.63) определяет общий впд пепараметрпческого критерия качества классификации. В таком общем виде этот критерий может оказаться неудобньп| для практического использования. Он содержит Ж(А2 — 1)/2 слагаемых. Это число становится огромньп| прп больших Аг. Поэтому с практической точки зрения желательно положить как можно больше весов /(Х„Х.) равнымн нулю. Простейшая весовая функция, допускающая содержательную интерпретацн|о, имеет вид Для малых Л критерий У(Й; Х*) можно приближенно представить в виде 77' т ,/ (й; Х*) = (1/Х),'~', ~ /„(х„Х,) |г' (ю„„, ю, ) — У„(й; Х*). т=2 я=1 (11.65) 11 3 НЕНАРЛМЕТРИЧЕСКИЕ КРИТЕРИИ КЛ'|ЕСТВА Дальнейшее упрощение мо|кет быть получено, если принять (11.62) в качестве определения |г 7 (17»А„, 177|,,).

В этом случае имеем .2„(О; Х*) = (1аЧ),'»' ~ /„(Хт7 Х,) [1 — о (а1,„|о„)12 ~~ — 2 =1 ~~ с'./„, (~; Х*), (11.66) ~1лен,г„а(|2; Х":) представляет собой число различных пар векторов, которые отнесены к разным классам. Этот критерий очень эффективен с точки зрения реализации, так как для его определепня требуются лишь простейшие вычисления.

Кроме того, этот критерий связан с верхней границей вероятности ошибки байесовского классификатора через расстояние Бхата.ария и неравенство 11епсеиа, как показано в (9.104) и в последующем обсуждении. Назовем 277о(Р; Х*) штрафной функиией с фиксированной окрестностью. 11.3.2. Непараметрический алгоритм автоматической классификации. Возвращаясь к общему случаю, мы можем описать алгоритм в терминах приращений У(Й; Х*) при изменении Й, т.

е. 4 Ж ЛУ (г, 2, 2) = (1/Л'),'»', / (Х,, Х„) ~ [д (|о,, |о „(2)) — |г - (Х;, Х„)12— т — 1 т~| — [|2„(о„,. (2), ю„„(2)) — сг~ (Х|, Хт)]2~. (11.68) Если пспользу|отся критерии 777(Й; Х*) н У77о(О; Х*), прпраще нпе имеет более простой внд: М„(2,2, г) = — (1/Ъ') ~'/„(Х,, Х,)[22 (»Ю т(2)) — г'.-( „.(г), „„(2))1, 7' — 1 7Ф1 (11.69) АУ„(2, У, 2) = (1/ Х) Х У„(Х1, Х,) [~ ( Ъ,. (2),, (2)) — ~(ю,, ю„„(2)) 1* т=1 7=г 7 (11.70) Как ЛУ77, так и АУ~71 содержит два члена, один из которых не зависит от 2.

Таким образом, можно записать их, как решаю- 348 сс ! 1 1 1 ! ! .1 1 ! ,7 ст) н, ,У 1Е) в, ппссмсп 11.2 11.3 1369 3072 150 150 8 10 1,0 0,75 115 7'9 182 ГЛ, 11. АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ щие функции на 1-й итерации. Приращению ЛУ,о соответствует РЕШаЮЩаЯ ФУНКЦИЯ Йве, ОПРЕДЕЛЯЕМаЯ ВЫРан1ЕНИЕМ 0„~ (У, у, у) = (1/Х) ~ ~„(Х1, Х,) 6 (о)у, о)А, (У)). (11.71) Й„е(1, У, У) пРеДставлЯет собой число вектоРов, отнесенных в У-и класс на у-Й итерации и отстоящих от Х! на расстояние, мень- шее ус.

Правило классификации на У-й итерации имеет вид 0 ~(У, У'с(У+ 1), У) = 1пах0,~(е, у, У), (11.72) т. е. Х! перебрасывается в тот класс, который в настоящий момент имеет наибольшее число членов, отстоящих от Х< меньше, чем на ус. 11азовем эту реализацию основного алгоритма правилом фиксированной окрестности. Как критерий У,е, так и связанный с ннм алгоритм пме!от весьма естественную физическую Интерпретацию. 11енулевой вклад в У„дают векторы, близкие к границам, разделяющим классы. Таким образом, У„в меньше, когда эти границы проходят через области, в которых векторы расположены с малой плотностью. Рассмотрим границу, разделяющу1о классы у, и у2 на У-й итерации.

Предположим, что плотность является более высокой с той стороны границы, где расположен класс у . Тогда Т а б л и ц а 11.3 Данные, характериэуа щие эффективность процедуры, основа!,ссс1! па правиле фиксированной окрсстност!с векторы, лежащие вблизи границы, будут переброшены и класс.у,, а граница переместится в направлении меньшей плотности. Таким образом, процедура, основанная па правиле фиксированной окрестности, представляет собой метод поиска «долин».,"-)то разумный способ классификации векторов в условиях отсутствия априорной информации. Описанная выше процедура легко программируется.

Па рпс. 11.5 и 11.6 и в табл. 11.3 приведены результаты двух машинных экспериментов. В таблице для каждого эксперимента приводится число объектов У)У, предполагаемое число классов М, размер окрестности Й, число у)сХЛ разных пар точек, находящихся Г ! ! 1 1 1 1 1' 1 1 1 1 ! ! 1 й м Ы Р» с'! о ч с ~4 О3 о со сб о ~. сб о с~ н '8' о о о Ы й щ ос о~ со '4 а5 о о с~ о со о о ~ ~Д а5 о ° э о а$ :с 350 ГЛ.

11. АВТОМЛТИ'1ЕСКЛЯ КЛЛССИФИКЛЦИН 5 11.г. 1н:ПА1'Ам!",тРически1" .ИРитеРии клчествл 351 друг от друга на расстоянии, меньшем В, число потребовавшихся итераш1й 1ТЕВ, а также начальные и конечные штрафы У,(((1) и У,(((Р) . В экспериментах, использовалпсь следующие данные. Пример 11.2. Два класса, данные двумерные, по 75 обьектов в каждом классе: х, = асоз0+ т(+ и(, хг — — а яп 0 + шг + пг, (11.73) ('1 1.74) Лг 1 О ~ 1 6 О (11.75) Совместная нормировка применялась ко всем данным. Рис. 11.5 и 11.6 показывают, что классификация получается приемлемой.

Процедура довольно чувствительна к величине свободного параметра В. Если В слишком велико, появляется тенденция к объединению всех векторов в один класс. С другой стороны, если В слишком мало, то из-за наличия «пробелов» в распределениях образуется много устойчивых границ.

ДЛя даННОГО В ОбОЗНаЧИМ ЧЕРЕЗ Л'„[ ( г1((У вЂ” 1)/2] ЧИСЛО пар точек, находящихся друг от друга на расстоянии, меньшем В. Тогда можно указать следующее эмпирическое правило вьнюра В: выбирать В таким, чтобы Х„м 1ОХ Это правило гарантирует, что объем памяти, требуемой для реализации описанной процедуры, будет находиться в разумных пределах и лишь линейно расти с ростом У. 11.3.3. Асимптотические свойства процедуры.

При очень больших У приведенные выше рассуждения можно формализовать. Пусть Г, — область векторного пространства, содержащая те векторы Хь которые относятся к классу /. Пусть КГ, (Х)— где п1 и пг — независимые, одинаково распределенные нормальные случайные величины с пулевыми среднпмп и единичными дисперсиями; ш, и шг для каждого класса фиксированы: ш( = = О и шг = Π— для 1-го класса; т( = О и тг —— — 20 — для 2-го класса; 0 — нормально распределенная случайная величина со средним 0 и среднеквадратичным отклонением г1/4, где 0 = л для 1-го класса, 0 = О для 2-го класса, для обоих классов а = 20. Пример 11.3.

Три класса, данные двумерные, по 5О объектов в каждом классе: 1-й и 2-й классы — такие же, как и в примере 11.2, со значенияъ1и параъ1етров т( = О, шг — — О и О,„= л для 1-го класса; ш, = 20, шг —— О и 0 = О для 2-го класса. 3-й класс генерируется в соответствии с двумерныъ1 нормальным распределением со средним вектором М и ковариационной матрицей Х характеристическая функция Г,, т. е. 1, если Х~Г;„ КГ (Х)= О, если Хф Г;. (11. 76) 'Тогда (11.71) можно переписать в виде ало ((, /) = (1/Х) 2~ /в (Х1 Х,) Кг (Х„), (11.77) где для простоты опущен индекс итерации 1.

Когда У становится большим, правая часть (11.71) превращается в интеграл ('„„(Ю, () ~ (н (Л~, % Р Ж ~(~ ~ Орп (Хр((), (11.78) Г; где р(Х) — плотности вероятности «смеси», в соответствии с которой распределены векторы Хь Если для любого вектора У. определить Я,(У) как множество всех векторов, отстоящих от У пе более чеъ1 на В, то можно записать В-,,(У) = ~ р(Х) аХ. (11.79) ГРЙя(У> Рассмотрим вектор У, лежап:ий па текущей границе классов 11 и уг, и предположим, что Яд(У) содержит лишь векторы, отнесенные только к классу у( или только к классу уг. Тогда У заново классифицируется в соответствии с правилом У вЂ” +- класс 1.„, Р (л(Нл И ~ Р (% Нл ~, .

' (11.8'.~) Г, (-(Яя(Г1 Г, (-(Я„(Г1 р(Х) м р(У) + [ ~ р(У)]'(Х вЂ” У), (11.81) ~р (У) = [др/дх(~ х=г... др/дх. ~ х=;]'. (11.82) где Кроме того, могкно считать, что граница — это гиперплоскость, Если выполняется верхнее неравенство, то в силу непрерывности все векторы в малой окрестности границы переходят в класс /г и граница перемещается в область, пре;кде занятую классоъ1 у(. Аналогичное рассуждение применимо и к нижнему неравенству. Если имеет место равенство, граница стациоиарпа. Когда стационарная граница неустойчива, пабл1одается тенденция ее удаления от стационарных точек при неболыпих возмущениях. Если В достаточно мало, то плотность р(Х) в Я,(У) можно представить усеченным рядом Тейлора: 352 Д'~лъуя ~ "~гуру~~ ! ~гцЯц~ У вЂ” экласс 7'„ (ЧР (~ )Г 1' У вЂ” экласс 7'„ (11.84) гтт ~и тя гл.

11. АвтомАтическАя кллсспФПНАция разделяющая Яв(У) па два полушара равного объема. Тем самым имеем ;~ )Х) НХ~ (;~ )У) ЙХ-)- г) г)вл(г) г; гЪд<г) + ))по'))' ) )т — )'))» = Г; Г)вн1Г) Лл+1 „и~г р(У)]тГ 2 1 2 (11 83) Г и+1 где и — объем Яв(у), а У вЂ” единичная нормаль к границе вточке У, направленная в сторону класса 71. Знак «+» используется для й = 1, а « — » — для й = 2. Таким образом, (11.80) принимает вид и граница является стационарной, если 1)р(у) не имеет нормальной составляющей.

Пусть теперь стационарная граница подвергнута малому возмущению, так что ее единичный нормальный вектор становится равным 1". На этой границе имеется точка У', удовлетворяющая соотношению У' = У + р 1", (11.85) где р — скаляр.