Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 53
Текст из файла (страница 53)
40А,~1' (10.27) (10. 28) где (=О, 5=0,, ()~) О, $~0, (10.29) а В ( ° ) — ранг расстояния, определяемый в соответствии с (10.18) . 2. Критерий «напряжения» [Крускал, 1964а, б]: ХХ 1 (4 — а1 )' обозначатот, соответственно, множества векторов-наблюден11й,векторов-признаков и индексов классификации. Член У0 характеризует степень соответствия структуры векторов-признаков структуре векторов-наблюдений.
Член У~ характеризует разделимость классов в пространстве У. Наконец, р — множитель, устанавливающий относительную важность у~ и 10 при определении у. Мера степени соответствия между У* и Х* строится, исходя из расстояний с~11 (= ~~у,— у,~)) и йа(= ЙХ; — ХД) между ооъектами в пространствах У и Х. К настоящему времени предло".кены три таких меры, или критерия: 1. Критерий л1онотонносттс [Шепард, 1962а, б]; у М ~ [л(а*) — л(а )) а"' Э(1 $10.2. УЛУЧШЕНИЕ РАЗДЕЛИМОСТИ м Ув = 1г Я„= 1г ~ Р (40;) (1/Х~),'»,' (у. В.) (у. т).)' 1=1 У1ЕО м - .~' Р (0,) (1/Х ) ~ ~~ у.
— И. 1~2 3=1 У,ев (10.33) где В; — математическое ожидание векторов у, отнесенных и классу у, а У1 — число объектов в классе у. Если использовать Я и Я в качестве Я1 и Я2 и нормировать систему координат так, чтобы матрица Я стала единичной матрицей, то этот критерий совпадает с критерием 11 (9.'13).
Можно переписать (10.33), выразив 1~ через расстояния между объектами. Читатель может легко проверить, что В некоторых случаях многие иа полагают равными нулю, в частности, для больших да. Критерий монотонности направлен на сохранение рангового порядка расстояний между объектами. Критерий напряжения устанавливает более жесткую связь между расстояниями в исходном пространстве и в пространстве призна- 7Ф КОВ. КрИтЕрИй НЕПрЕрЫВНОСтИ ОГраНИЧИВаЕт а41 дЛя МаЛЫХ д;;. В качестве 1~ можно использовать л1обой критерий разделимости. В гл. 9 мы рассматривали некоторые из таких критериев, в том числе критерии 11 — 14, представляющие собой меру разброса (см.
(9.13) — (9.16) ), расстояние Бхатачария и дивергепцию. В случае нелинейного преобразования фактор простоты играет существенно более важную роль прп оценке критериев. Поэтому, хотя имеется много критериев разделимости и все онп могут быть использованы в качестве У~, предпочтение отдается критериям, имеющим простой вид. Например, можно использовать след матрицы разброса внутри классов: (1!ио) В11 — х у 1 ~~', ~(1/~1..)а 1 (10.
32) где а — неотрицательный свободный параметр. 3. Критерий непрерывности [Шепард, 1966]: Х Х Ж/а.;)'. (10.31) 1(1 Суммирование производится по всем парам (г, 1). Веса иа обычно выбираются так, чтобы меньшим да соответствовали ббльшие веса. Типичное правило приписывания весов задается выраже- нием где 1, о„,.=о„., О (40А14 40А,) = 0 Оэ .ф~Оэ (10.36) где в качестве Р1 берется выборочное среднее ХУ;/У1. Выражение (10.34) представляет Ув в виде взвешенной суммы квадратов расстояний между Объектами Одного и того же класса.
Можно несколько видоизменить У~, приписав этим квадратам расстояний веса в соответствии с (10.32): М М т ',~~ ~ О (40А1, вА,) и,.ф",.'., (10.35) ~(1 $10.2. улучшение РАзделимости 317 Вводя обозначения 2~1,— 1т)т 2(у у )т (10.60) а) (10. 61) 1*' (1) — 1*' (О) с1*2 (2) — с1*2 (О) (10.62) 310 .гл, 1О. нелинейнОе пРеОБРАзОВ ъние пРОстРАнстВА Построенная таким образом функция расстояния является ключом к построению алгоритма нелиней~ного преобразования. Имея любые две точки в пространстве Х, можно определить расстояние между их образами в пространстве У.
К сожалению, для Рис. 10.8. Полиномиальные функции расстояний. а) и=1,0,т 3; б) и 0,1,г 7. данной конфигурации в пространстве Х обычно не существует конфигурации в пространстве У, которая находилась бы в точном соответствии с функцией расстояния. Однако мы сейчас помажем, что иногда можно построить конфигурацию, которая почти точно соответствует этой функции. Пусть сР' — евклидово расстояние в и-мерном пространстве У.
Тогда данную точку У можно однозначно определить набором расстояний между У и и+ 1 соответствующим образом выбранными опорными точками $'о, $'1, ..., $', Чтобы убедиться в этом, наметим, что можно образовать и уравнений ПУ вЂ” Т'1!!2 — !!У вЂ” ~'о!!2 = сР2(1) — сР'(О), 1' = 1, ..., и,' "(10.58) где сР'(1) — известные расстояния между У и $о Но уравнение (10.58) определяет прямую линию, так как квадратичные члены сокращаются, и мы получаем 2(~'о — ~';)'У = !1~0!Р— !!~' !!2+(А*'(1) — сР2(0), 1 = 1 .
и (10.59) можно записать уравнение (10.59) в матричной форме $'У =. И'+ С. ~,'(10.63) Если точки У1 выбраны таким образом, что матрица $' невырождена, то (10.63) можно разрешить относительно У. Опорные точки Уо, ..., У„в пространстве Х можно определить разными способами. Например, можно найти набор из и + 1 векторов, представляющих собой математические ожидания и+ 1 локальных «сгущений» объектов (детали этой процедуры рассматриваются в гл.
11). Их образы Уо, ..., У„в пространстве У, образующие матрицу $', можно найти следующим образом. 1. Вычислить и (и + 1) /2 парных расстояний между опорными точками в пространстве Х. 2. Используя функцию расстояния, найти соответствующие расстояния между точками в пространстве У. 3.
Найти и+1 точек в пространстве У, таких, что расстояния между ними совпадают с расстояниями, найденными на пре- 318 гл. 10. нелинейное пРеОБРА30ВАние пРОстРАнстВА дыдущем шаге. Это не представляет труда, так как размерность пространства лишь на единицу меньше числа точек. Таким образом, после того как по объектам обучающей последовательности определены опорные точки в пространствах Х и У, мы можем отобразить новый объект Х в пространство У с помощью следующего алгоритма.
1. Вычислить расстояние Ы(г) от отображаемой точки Х до: г-й опорной точки У~ для г = О, 1, ..., >г. 2. По И(г) вычислить сР(г), используя функцию расстояния. сР(г) = ~ [И(г)], г = 1, ..., )г. (10.64): 3. Решить (10.63), т. е. У $'-1[И'+ С(Х) ]. (10.65~ Уравнение (10.65) определяет У как линейное преобразование вектора С, который является нелинейной функцией от Х Это преобразование имеет очень простой вид.
Преобразование (10.65) можно упростить. Заметим, что линейный классификатор, определенный на У, может оказаться не лучшим, чем классификатор, определенный на С. Поэтому векторы С, так же, как и векторы У, можно Использовать в качестве признаков. Использование С вместо У исключает необходимость нахождения $; и выполнения трудоемкого линейного преобразования. В примере, который приводится ниже, будет выбран упрощенный метод. При выводе (10.63) предполагалось, что точка У, расположенная на заданном расстоянии от каждой опорной.
точки, действительно существует. Однако, если эти расстояния заданы произвольно, наличие такой точки гарантировать нельзя. Тем но менее, решение уравнения (10.63) дает некоторую точку. Как интерпретировать У в этом случае? Можно обойти это затруднение, если без дополнительной аргументации задать линейное преобразование в виде (10.65). К сожалению, этим мы наносим ущерб ранее приведенным аргументам, касающимся улучшени» разделимости. Однако геометрическая интерпретация может помочь объяснить, что происходит с У в этом случае.
Каждое уравнение в (10.59) или (10.63) определяет гиперплоокость, связанную с гипврсферами с центрами в $'0 и К и радиусами гр'(О) и гг*(г). При размерности 2 эта гиперплоскость превращается в прямую, связанную с двумя окружностями. В аналитической геометрии эта прямая называется радикальной осью двух окру)кностей [Моррилл, 1951]. Понятие радикальной оси двух окружностей иллгострируетсп рис. 10.9. Если две окружности пересекаются, радикальная ось является их 'общей хордой, проходящей через точки пересечения. $10.2.
УЛУЧШЕНИЕ РАЗДЕЛИМОСТИ Ра икальная ось нв существует, когда окружности являются ног еитрическнми. Решением уравнения (10.63) является пересечение радикальных осей )г пар гиперсфер. На рис. 10.10 показаны два случая, Ра1аальнан Рис, 10.9. Положение радикальной оси двух окружностей.
а) Пересекающиеся окружности; б) непеРесекающиеся окружности. когда нв существует точки У, находящейся на заданном расстоянии от каждой опорной точки. Решением уравнения (10.65) является, как показано на рисунке, пересечение радикальных осей. Это решение дает приемлемую .компромиссную точку. Возможны, однако, задачи, в которых расстояния между основными точками малы по сравнению с д*(г). В этом случае окружности являются почти концентрическими, и радикалытые оси плохо определены. Таким образом, опорные точки должны быть относительно широко расположены в пространстве. П р и м е р 10.4. Обьекты, показанные на рис.
10.11, нв являготся линейно разделимыми из-за того, что распределение жласса В бимодально. Однако, поскольку перекрытие незвлико, нелинейное преобразование может, по-видимому, улучшить разделимость. Эти объекты генерировались в соответствии с нормальными распределениями следугощим образом. Класс А: 100 объектов, порожденных нормалиным распределением с математическим ожиданием и ковариационной матрипей (10.66) О ~ О 1 ' Класс В: 2 раза по 50 объектов, порожденных двумя нор- мальными распределениями с математическими ожиданиями и .ковариационными матрицами Л~вг 5: Л~в2 = 5 ~вг = ~вя = О 1 (10.67) 321 $ 10.2. УЛУЧШЕНИИ РАЗДЕЛИМОСТИ Для построения функции расстояния при данных значениях р и г использовалось обучающее множество, включающее по 2Ь объектов из каждого класса.
Для простоты в качестве опорных В В ВУ В В В В .У В В.У ВВВ В Вз В В В З Вз .В а) В ВЗ В В В Вз В ВЗ В В В В ЗЗВВ З В ВУ З УЗ з з 1 1 ! ! 1 А А А А А АА АА А А А А А А АА АЯА А АА А АА А А ААА А А А А А ААА АА АА А АААААА А А А А А А А А А А АА АА А Рис. 10.12. График разброса отобраькенных обьектов для )т = 1, 0 и г = 3 1Кунтц, 1972а]. точек были приняты ЛХи, ЛХа! и ЛХ~2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
