Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 57
Текст из файла (страница 57)
37) Таким образом, в случае равных ковариационных матриц направляющий вектор оптимальной гиперплоскости совпадает по направлепи1о с ве11торол1 Р2, а следовательно, и с вектором разности 12~ Шаг 1. Выбрать начальную классификацию ьг (0) и вычислить О1(0), ..., 1)ы(0). Шаг 2.
По вычисленным на 7-й итерации выборочным средним г,г1(г), ..., О„,(/) переклассифицировать казидый объект У;, отнеся его к классу с ближайшим Ц-(/). Шаг 3. Если классификация какого-либо объекта У< изменлегся, вычислить новые выборочные средние О1(/+1), ..., 0.,~(/+1) для нового задаяия класса и вернуться к шагу 2; в противном случае — закончить вычисления. Эта конкретная реализация основного алгоритма, которую мы будем называть правилом ближайшего среднего, хорошо известна. Она положена в основу ранее упоыинавшейся процедуры 1800АТА, хотя эта последняя работает .в исходной системе координат. Свойства сходимости этой процедуры при.больших У исследовались в [Маккуин, 19671. а40 341 ЦЫ вЂ” — В;,,' Ь,КЛ Ч„= Р(о!)О;, Ч,„=Р (са!) (1 — Ь;), (11.39) 11.40) '(11.41) где РМ> 4 рд! — ~г Р (11.
43) Гл $ !. АвтоылтическАя клАссиФикАция средних значений .О! — 02[= —.02/Р(а!) = О!/Р(аг)1. Покажем, что правило ближайшего среднего устанавливает разделяющую гиперплоскость перпендикулярно к вектору разности средних значений. Это свойство, которым не обладает исходнаи система координат, является значительным преимуществом нормированной системы координат.
Для случая равных ковариационпых матриц можно показать, что алгоритм сходится к разде- Рис. 11.2. Разделение дву-х рас!!ределений. ляющей гиперплоскости, перпендикулярной .О! — 02 в широком диапазоне начальных классификаций. Пусть на некоторой итерации объекты разделяются гиперплоскостью с направляющим вектором К Предположим, что эта гиперплоскость находится на расстоянии !! от .О! и на расстоянии 12 от .02, как показано на рис. 11.2.
Пусть У! и Уг — центры «вероятностных масс», лежащих по обе стороны гпперплоскости. Тогда, в соответствии с правилом ближайшего среднего, направление следующей гиперплоскости будет совпадать с вектором У! — Уг. На каждой итерации гиперплоскость делит каждое распределение на две части, лежащие по обе стороны гиперплоскости. Таким образом, имеем четыре вероятностные массы В;;, ! = 1, 2; у = р, гг (см. рис. 11.2). Центры Ун и абсолютные значения Ч;; этих четырех масс можно получить следующим образом: Г,„= 0;+ — ьК,7„ (11.38) $ !!.2.
ПАРАМЕТРИЧЕСКИЕ КРИТЕРИИ КЛЧЕСТВЛ а = (2л) — !/г и ехр — —,и2~ йи ==- (2л) '/г ехр ~ — ф;/г; г г '/ ! (11.42) ехр — 2 и') с[и = —. — его(~ 1;/8!) '(если 0< находится в области В;„то используется положительный знак; если 0< находится в В;„, то — отрицательный знак) и ~г ф~тК $~ (11.44) Здесь У! — это центр масс В!, и Вг„а (/2 — центр масс Л!„и Вг . Следовательно, У! и Уг можно вычислить следующим образом: ~/1 (ЧЮ!э + Ч2Хгч)/(Ч!ю + Чгю)1 '(1 1.45 )' г/2 = (Ч!и~/!в + Чгв! /ги) /(Ч!а + Чгл) ° (11.46) Подставляя выражения (11.38) — (11.43) в (11.45) и (11.46), имеем ~/1 ~ 2 Р (а!,) Р (а!2) (Ь! — 12) (В, — В~) + (Р (а!,) (а!/г,) К1+ Р (в2) (а2/г2) К2) $' (~( ) Ь + ( ) Ьд[~ — (Р( ) Ь +Р(!а») Ьз)) (11.47) В случае равных ковариационных матриц К! — — Кг — — К и з! = гг = 8.
(114!8) Далее, пользуясь условиями совместной нормировки (11.23) и (11.24) (или (4.62) и (4.63)), матрицы К и 02 можно выразить в виде функции от .О!. Таким образом, (11.47) принимает вид У! — Уг — — с!.О! + сгР, (11.4[) ) где Р (а!!) (Ь! — Ь2) — (1/г) (Р (а!,) /Р (!а2)) (Р (а!,) а! + Р (а!~) а») О! ~' с— >,Р (а! ) Ь '+ Р (в ) Ь ) [1 — ~(Р (а!~) Ь + Р(в ) Ь )) (11. 50) (1/~) (Р (а),) ат+ Р (а!~) а2) (11.51) (Р(в)Ь +Р(в)Ь )[1 — '(Р(а) )Ь +Р(в)Ь )[' 342 которое, в виде (2л) — 1/2 =- (2л) — '/2 (11.50) >О ГЛ.
11. АВТОМАТИЧЕСКАЯ КЛАССИхххнтхАЦИЯ Направляющий вектор новой гиперплоскости имеет две со- ставляющие, одна из которых совпадает по направлению с Г, а другая — с В1. Если коэффициент прп В1 имеет тот же знак, т что и 01Г, то направляющие векторы последующих гиперплоско- стей будут все ближе и ближе подходить к В1. Для того чтобы доказать, что этот факт действительно имеет место, нужно пока- зать, что числитель выражения для с1 (11.50) имеет тот же знак, тхх что и В1)' (поскольку сг и знаменатель с1 всегда положитель- ны), Нам достаточно рассмотреть случай, когда В1')' ) О (случай т т В11' ( О рассматривается аналогично) .
Для случая В1 Г ) О, как видно нз рпс. 11.2, г, + гг (В1 — Вг)т à — [1/Р (о)г)]01Р'х и условие сходпмости принимает вид Ь, — Ь, — [(г, +- г,) /г] (Р (о)1) а, + Р (о)г) аг) > О. (11.53) Легко видеть, что для некоторых сочетании параметров неравенство (11.53) не выполняется. Можно, однако, вычислить Р Щ Р4 05 08 Р(ц) Апушрнвя виувяп~нтпи Рис. 11.3.
Области сходимости [Фукунага, 197Эг]. а) йС0,1; б) й-1; г) й-10; г) й=100; д) й (0,1; г) й = 1; ж) й = 10; г) й = 100. границы области значений параметров, где оно выполняется. Результат приведен на рпс. 11.3. Неравенство (11.53) содержит три параметра г1/г, гг/г и Р(о)1) [Р(о)г) = 1 — Р(о)1)1, или й = (г1+ г~)/г, и = г1/(г1+ гг) и Р(о) ) ..(11.54) ф 11.2. ПАРАМЕТРИЧЕСКИЕ КРИТЕРИИ КАЧЕСТВА з,з На рис. 1'1.3 показаны области сходимости в координатах а и Р(101) для различных гс. Как видно из рисунка, область сходи- мости достаточно велика и не включает лишь крайние значения Р(ю1) пли сс.
Сходимость в случае неравных ковариаг1ионных матрии,, Как уже говорилось ранее (см. рис, 4.1Ои формулу (4.68)), гиперплоскость, перпендикулярная к вектору разности средних значений, дает приемлемое разделение двух нормальных распределений после совместной нормировки даже в том случае, когда ковариацпонные матрицы различны. Однако, когда К1~~ Ф Кг, найти область сходимости, как мы это сделали выше, трудно.
Сходпмость можно доказать, если гиперплоскость проходит через определенную точку. Поэтому можно сказать, что некоторая область сходимости вблизи этой точки должна существовать. Предположим, что гиперплоскость проходит через точку, в которой а1/г1 = аг/хг = г. (11.55) Тогда, подставляя (11.23) и (11.24) в (11.47), получим Р(о),)(Ьт — Ьг) 7(Р(о)1)/Р(о'г)) ~)11'] Г~, ] УУ (Р (охт) Ьт + Р (о~2) Ьг) [1 х ( $) $ + Р (о)2) Ьг)] Рассуждая так же, как мы это делали выше, получим следующее условие сходпмостн: Ь, — Ь, — 'у (В1р') /Р (о)г) > О, (11.57) используя (11.52) и ('1 1.55), можно представить Ь,— (,,/,)г,— Ь,— (а/,)г,~о, (11.58) ехр — —,и ~ сги — (г,!г,) ехр ~ — —.
г Iх-~— 1 / 1 2 2 2 1 1) — /,е — ехр ( — е и ) еи — Оеар ) ех!е ( — —, ~Че';) 1 г 1 ) г г — х /гх 1е /'х [ехр ( — — и') — ехр ( — —,~х!хх)1 ге + 0 12/гх 1 2 2 + ехр и ехр — —,г l~, гги 0 это неравенство выполняется для всех г)/г1 и гг/гг. 345 344 Нормированная система координат Исходная система координат Полученный класс Полученный класс 1 2 1 2 Фактический /1 класс 12 14 70 Фактический /1 класс 12 100 0 19 81 86 30 *) 1Фукунагя, 1970г1.
Нормированная система координат Исходная система координат Полученный класс Полученный класс 1 2 3 1 2 3 Факти геский 1 класс 3 100 2 0 27 73 0 18 0 82 84 26 14 16 О 73 1 11 75 Фактический 1 класс 2 3 *) 1Фукунага, 1970г1, ГЛ. 11. АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ Таким образом, если гиперплоскость проходит через точку, в которой выполняются соотношения (11.55), новый вектор РаЗНОСтн СРЕДНИХ 1,г) — гг2 СОСтаВЛЯЕт МЕНЬШИЙ УГОЛ С ВЕКТОРОМ х.)1 — Р2, чем Г. В окрестности этой точки должна существовать область сходимостп (хотя теоретического обоснования этого утверждения мы не имеем).
Пример 11.1. В дополнение к теоретическим исследованиям, рассмотрим результаты численных экспериментов. В этих Табл ица 11Л Результаты классификации для стандартных данных 1=1, 2 е) экспериментах объекты генерировались в соответствии с нормальными распределениями с заданньв|11 математическими ожиданиями и коварпацпоннымп матрицами. Математические ожидания и ковариации брались из стандартных данных. Таблица 11 о Результаты класснфтпгацип для стандартных данных 1=-1, 2, 3 *) Д в а к л а с с а. В первом эксперименте генерировалось по 100 объектов каждого класса в соответствии со стандартными данными, 1= 1, 2, Вначале объекты классифицировались в исходной системе координат в соответствии с решающим прави- Е 11,2, ПАРАМЕТРИЧЕСКИЕ КРИТЕРИИ КАЧЕСТВА лом ближайшего среднего.
Затем производилась «совместная нормировка» объектов и они снова классифицпровались. В табл. 11.1 приведены матрицы, показыва)ощие количество правильно и неправильно классифицированных объектов в каждом случае. В случае, когда предварительно была сделана Рис. 11.4. График разброса зксперпментальных объектов. а) исходное распределение; б) после совместной нормировки 1Фунунага.
1970 г1, совместная нормировка, число неправильно класспфпцпрованных объектов оказалось х)епыпим. Т р и к л а с с а. В этом эксперименте генерировалось по 100 объектов каждого класса в соответствии со стандартными' данными 1= '1, 2, 3. Далее применялась та же самая процедура. Результаты приведены в табл. 11.2.
На рнс. 11.4 показаны проекции данных на плоскость в исходной и нормированной системах координат. 346 347 где 1, о„т = |о„,„ 0 |о|, =,~'= |о|, . (11. 67) или |2<, (|о|, 7 |о„) с) О, |о„=,~~ |о|,, (11 62) О, |О„„=- |О„. 11, |гх (Х„, Х,) ( Л, У" (х"' х') (О, |г (х„, х,) л. (11.64) ГЛ. 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
