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

Этот критерий почти совпадает с критерием (11.03). Переменная т, используемая для обозначения дерева, играет ту же роль, что и ъз. Заметим, что каждое дерево т характеризуется не только структурой, но так»ке уровнямн, которые приписаны вершинам. К сожалению, основной алгоритъг этой главы применить нельзя, так как трудно дать адекватное определение «близких деревьев».

Если бы да»ке н можно было формализовать понятие «возмущенного дерева», то это еще не дало бы простого способа вычисления результирующего пзмененля г'(т; Л*) . Для нахождения оптимального в смысле У(т; Х'") дерева часто использугот следующий алгоритм [Дигонсон, 1967; Ролф, 1970~. Прежде всего необходимо каким-либо способом ввести расстояние между двумя множествами векторов. 11апрпмер в ка- 1 честве такого можно использовать расстояние между двумя средними векторами. После того как это сделано, мо»кно применить следугощую птеративну1о процедуру: Шаг 1. Отнести каждый объект к конечной вершине уровня «0» и вычислить расстояние между каждой парой объектов.

Шаг Г. Добавить новую вершпцу, сделав ее предшествующей двум вершпнаъ1, соответству1ощнм паре наиболее близких объектов (классов). Уровень этой вершины равен расстояни1о между соответствующпъги об ьектами (1,лассами) . Шаг 8. Вычислить расстояние между классом, представленным новой вершиной, и объектами (классамк), соответствующими оставшимся конченым вершинам.

Шаг 4. Припять новуго вершину в качестве коночной и вычеркнуть те две вершины, слиянием которых она была образована. Если осталось две плн больше конечных вершин,— то возвратиться и шагу 2. В противном случае работа алгоритм заканчивается. Шаг 3 является наиъгенее обоснованной частью вышеприведенной процедуры. Результирующее дерево ъ1о~кет сильно зависеть от способа, которым вводится расстояние ъгеигду классами. Эта проблема в настоящее время является предметом исследований в теории иерархической классификации. 11.4.3. Классификация в режиме диалога. Замечено, что человек доволно успешно справляется с задачей классификацил. Очевидно, мы обладаем способностью устанавливать факт наличия классов путем «целостного восприятия». К сожалепиго, наша способность наблюдать объекты жестко ограничена тремя % 11А, пРОцедуРы лвтомлтпческой кллссиФиклции 359 358 гл.

11, лвтомлтическля кллссиэиклцпя измерениями. Однако в гл. 10 и, в частности, в 5 10.3 были рассмотрены алгоритмы отображения векторов в пространство меньшей размерности. Следовательно, данные, имеющие высокую размерность, можно отобразить в двух или трехмерное пространство. По этому отображению человек-наблюдатель мо1кег А А А А А с А Л А В В В ВВ В ВВВВ В ВВВВВ ВВВ ВЮВВ В ВВ ВВВ ВВВ Рис. 11.10. Отображение результатов классификации трех видов ирисов (Фукупага, 1971б1. легко выполнить классификацию.

В этом и состоит принцип классификации в режиме диалога. Сохранение расс то я н и й. В 5 10.3 было рассмотрено нелинейное отображение из и-х1ерпого пространства в двумерное пространство, минимизиру1ощее среднее расхождение между соответствующими расстояниями в обоих пространствах. Это отображение сравнительно хорошо сохраняет структуру распределений и может быть выведено на экран индикатора. На рис. 10.13 показано отображение данных, характеризующих три вида ра- '1 '1 1 1 1 ! 1 1 1 1 1 '1 1 1 1 1 А А А 1 А А 1 А А АА АА А А А А АА 1 .

А ААА 1А А А ААА ,А '. Л АА АЛАА Л А ААА Л АА А !ЛА А 1 1 1 А 1 А А 1 1 1 1 1 1 1 1 1 1 1 1 ! ! В! З' 1 1 ! 1 1 стений (ирисов). Глядя па индикатор, оператор может провести естественные границы этих распределений без какой-либо информации о принадлежности объектов к определенным классам.

Рассто янне до дну х т о чек. В задачах с двумя классамн для классификации можно использовать отображение, рассмотренное в ~ 103 под названием «расстояпие до двух точек». Ниже приводится описание соответствующей процедуры. Гпс. 11.11. Отображение результатов классификации двух видов ирисов (Фукупага, 1971б~. Шаг 1. Применить совместную нормировку (11.23) и (11.24). Шаг й Выбрать произвольно две точки 1Э1(0) и В2(0).

Шаг 8, Имея на 1-11 итерации точки 1Э1(1) н 1?2(1), отобразить все объекты на плоскость, откладывая по осям ~~У; — 1Э1(1) 112 и Пг, в,(г) р. Шаг 4. Провести границу, используя интуицию оператора. Если на начальных итерациях распределения плохо различимы, оператор может выбрать в качестве границы пряму1о под углом в 45', проходящую через начало координат. 1 1 1 1 З ! З В З В З З ВВВ В З В З В ЗВ 1В В В А 1ВВ В З А В З 1В В В 1В А А А А В ВА А ВВ А АА А В Я А А А ЗВ А ААААА А А АА А ЛААААА А А ААА 1 1 Я! 1 1 1 1 ,1 1 1 ! 1 1 360 ГЛ. 11.

АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ Шаг 5. В соответствии с проведенной границей, произвести перераспределение объектов по классам. Шаг 6. Если классификация хотя бы одного объекта У» изменилась, вычислить новые выборочные средние 01(с + 1) и УУ2(л+ 1) и повторить процедуру, начиная с 3-го шага. В противном случае работа алгоритма заканчивается. Описанная выше процедура в точности совпадала бы с процедурой, описанной в 9 11.2 и максимнзирующей критерий У», если бы в качестве границы на каждой итерации использовалась прямая, проходящая через начало координат под углом 45'. Различие между этими процедурамп состоит в том, что в первой из них имеется свобода выбора любой границы в соответствии с интуиппей оператора.

П р и м е р 11.4. Данные, характеризующие три вида об ьектов, классифнцпровались без учптеля следующим образом. Вначале все данные были пронормпрованы в соответствии с (11.23) и (]1.24), после чего примеиялась описанная выше процедура. Результат приведен на рис. 11.10. Вид 1пя яеяо(п (В на рис. 11.10) четко, без единой ошибки, отделился от двух других видов (А на рис. 11.10) после трех итераций. Затем, на втором этапе, все объекты, обозначенные символом А (1пя чегв]со]ог и 1г[в у!гп]п[са), совместно нормировались, и снова применялась процедура, описанная в этом параграфе. После пяти итераций алгоритм закончил работу, результат которой показан на рис.

11.11. Неправильно классифицированными оказались два объекта из одного класса и трп объекта из другого (в каждом классе было по 50 объектов). Так как известно, что 1г]я чегвтсо]ог и 1г]я зс!гд!И»са слегка перекрываются в пространстве признаков, этот результат является приемлемым, а качество класснфпкапии — близким к качеству классификации с учителем. ЗАДАЕ!ИЕ НА СОСТАВЛЕНИЕ ПРОГРАММ Составьте следующие программы: 11.1. Поиск классов иа заданном множестве данных путем минимизации критерия У» вида (11.15) или (11.25). Исходные данные: по 50 объектов каждого класса. генерироваяных в соответствии со стандартными данными а) 1 = 1, 2 и б) 1 = 1, 2, 3, 4.

11.2. Использун данные заданин 11Ла и б, найдите классы, максимизирующие критерии У» вида (11.17) или (11.27). 11.3. Использун данные заданин 11.1а и 11Лб, найдите классы с помощ«но процедуры, основанной на прав»тле фиксированной окрестности (с»ритерий У, (11Л6) ). 11.4. Используя данные примера 11.2, постройте дерево и выполните классификацию данных на два класса. 11.5. Разбейте данные заданин 11.1а на две группы, использун отобраисеиие, определнслюе расстоянием каждого объекта до двух точек.

ЛИТЕРАТУРА А б р а м с о н, Б р а в е р м а н (АЬгаспяоп Ел(., Вгззсгп»ап Р.) [1962]. 1,еаг»з!пи Со гесоип!хе раССегпя !и а ганс(оп» епз !гопп»епС.— ЕЕСЕ Тгапз. ЕпЕогваНоп Т]зеогу !Т-8, 53 — 63 (С)гарСег 7). Ай»зерл»ан М.А„Браверман Э.М.,Розонозр Л.И.[1964]. Метод иотен»псальных функций в задаче о восстановлении хара»стеристики функционального преобразователя по случайно наблюдаемым точкам.— Автоматика и телемсхаиика, М 12 (гл.

7). А л а й с (АПа!я В. С.) [1964]. Вс!вс1!оп о1 теаяпгвгпспС Сот ргес]!сС!оп.— 8СапЕогсЕ 'с!пн. ТесЬ. Вор. 6103-9 (СЬарсегя 5, 8). А н д е р с о н [1963]. Введение в многомерный статистичес»с»сй анализ. — М.; »Э»»зматгиз. А н д е р с о н, Б а х а д у р (Апс]егзоп Т. Ж, ВаЬас!пг В. В.)[1962]. С1аяя!Е!саС!оп !пСо Св»о п»»»11!хат!аСе поги»а1 йяСг!Ьи((опя в»ЕСЬ »Е]ЕЕегспС сохаг!апсе п»а1г!сея.— Апп. Ма1Ь.

81аС. 33, 422 — 431 (СЬарСег 4). Б а х а д у р (Ва]зас(иг В. В.) [1967]. Оп с1азя!Е!сзС!оп Ьаяес( оп геяропявя Со п йсЬоСотопя !Сеп»я.— 1и с»81исЕ!ея !и ЕСе»п Асн»]уя!я апс! Ргейс1!оп». (Н, Бо!отоп, ей). 81апсЕЕогсЕ Ип!з . Ргеяя, 81апЕог»1, Са!!Еогп!а (СЬврСег 6). Б е н и е т (ВеппеС В. 8.) [1969], Тйе ЕпСг(пя!с с]!п»ес»я!опа)!Су оЕ я)апа! соНсс1»оия.— 1ЕЕЕ Тгапз. ЕпЕогп»аС!оп Т!»еогу 1Т-15, 517 — 525;СЬарСег 10).

Г> л о й д о н (В1аус]оп С. С.) [1966]. Оп а ра11сгп с!аяя!ЕСса1!оп гся»11С оЕ А!хегп»ап, Вгаз сгп»ап, а»»»Е Вохопоег.— 1ЕЕЕ Тгапь. ЕВЕогп»аС!о»з ТЬеогу 1Т-12, 82 — 83 (СЬв!»Сег 7). Б л з и у з л л, Г и р пз а к (В(ас)св»еН Р. апс! 6!гя1»!с!с М. А.) [1954] «ТЬеогу оЕ Батсз апс! 81аС!з1!са1 Вес!я(оия».— СЬар1сгз 9 аис! 10. Ч"1- !еу, Мсв» с'ог)с (СЬарСсг 3). Б о л л (Ва]1 С.