Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 52
Текст из файла (страница 52)
Для четырех объектов, показанных на рис. 10.5, а, можно найти преобразование, переводящее их в одномерное пространство и сохраняющее ранговый порядок (рпс. 10.5, б). Рис. 10.5. Истинная размерность и ранговый норядо * а * * а и) в1ва > а)вз > Ав>а)ва > ~айвз > а4за! б) а) > д > в1 > а4 > а ' > ~*. вз вз в, вз> * * * * * * г) вввз > авва > а4вв > а4ва > а4вз > а4за) г) В > в1 > ц > в1 > 1 > ва ~в вв за вз за Н 1о для четырех объектов на рпс.
10.5, в такого преобразования не существует. Ближайшим к нему является преобразование пое, показанное на рис. 10.5, г, при котором ранги д1з и д1«отличаются от рангов д)з и с114. Из этого примера легко увидеть, что чем больше объектов мы имеем, тем труднее отобразить эти объекты 11 К. Фукунага 4>06 Гл. 10. нелинейное преоБРАЗОВАние пРОстРАнстВА на прямую без нарушения рангового порядка, если объекты не расположены на одномерной кривой без крутых изгибов.
Соотношение расстояний между точками Хг, Хз и Х4 на рис. 10.4 оказывается важным при оценке истинной размерности.. Однако ранги расстояний И)3 и 035 не так уже существенны для характеристики структуры данных на этом рисунке. Поэтому требование сохранения ранга- можно ослабить, относя его лиш). к локальным расстояниям между объектами, и при этом все еще получить приемлемую оценку истинной размерности. Размер локальной области, в пределах которой ранги должньг сохраняться, выбирается из практических (инженерных) соображений.
Например, если выбрать две локальные области, как показано пунктирными линиями на рис. 10.5, в, то для первой области сохраняются соотношения 5113 ) с1)г ) с[гз, а для второй— 41г4 ) с)гз ) с134 (рис. 10.5, г). Поэтому можно сделать вывод, что истинная размерность данных на рис. 10.5, в равна 1. Являются ли данные на рис. 10.5, в одно- или двумерными — это весьма субъективный вопрос, на который нельзя дать однозначного ответа.
Теперь, когда мы установили ограничения на процедуру растягивания, нужно организовать эту процедуру таким образом, чтобы она приводила к уменьшению размерности исходных данных. РассмотРим РаспРеДеление РасстоЯний 41и межДУ объектами Х; и Хь равномерно распределенными в и-мерном шаре единичного диаметра. Плотность вероятности р (51) имеет вид Дй ипс[и — 1 [и 1)/2 (1 ) — 1/2 ~~ (1ч о1) ф(.+~) Т $10.1.
ИСТИННАЯ РАЗМЕРНОСТЬ ИСХОДНЫХ ДАННЫХ 307 Х4, показанные на рис. 10.4, сближать друг с другом, кривая будет выпрямляться. Наименьшая величина, до которой можно уменьшить размерность без нарушения рангового порядка, есть истинная размер- Таблица 10.3 Математическое ожидание и дисперсия расстояния с[ между объектами *) Дисперсия чаг (д) и ! Дисперсия чаг (о) Размерность и Ыатемат ичес кое ожидание Е[в) Математическое ожидание Е<в) Размерность и *) [Бен»ет, 19091. ность.
Существует много способов увеличения дисперсии 41 без нарушения рангового порядка. Расмотрим один из ннх 1Беннет, 19691. 70 0,33 0,45 0,51 0,55 0,58 0,60 0,056 0,045 0,036 0,029 0,024 0,020 7 8 9 10 0,61 0,62 0,63 0,64 0,71 0,018 0,015 0,014 0,012 0,000 где  — бета-функция. Нас, в частности, интересует дисперси>г расстояния 41 как функция размерности и. Соответствующие данные приведены в табл. 10.3. Кроме того, на рис. 10.6 изображены плотности вероятности р„(51) для разных и. Дисперсия возрастает с уменьшением и. Хотя на практике равномерное распределение объектов не встречается, можно тем не менее предположить, что обратная зависимость между и и И имеет место.
Это свойство подсказывает итеративный алгоритм для уменьшения размерности множества векторов. На каждой итерации вычисляется среднее значение Ии по всем парам объектов. Это среднее значение является оценкой математического ожидания Е (Ц. Если два объекта отстоят более чем на Е (й), то они отодвигаются друг от друга. В противном случае они сдвигаются ближе друг к другу. Таким образом, на каждой итерации дисперсия расстояний между объектами должна увеличиваться, а размерность — уменьшаться. Заметим, что если точки Хг, Хз и 0,Лт 050 070 100 К Рис. 10.6. Плотность вероятности расстояния д [Беннет, 19691. 1.
Д . Дисперсию 41 увеличива)от путем смещения каждого объек'та Х; согласно следующему правилу: Х, ~- Х, + '~', (Х, — Х/) [а (д;/ — Е ®)]/Е (д). (10.22) Об щее смещение Х, состоит из Х вЂ” 1 ненулевых компонент. Если Ие ) Е (д~, то существует компонента, отодвигающая объект 11е ЛОЯ гл. 10. нелинейнОЫ пРеОБРА30ВАние пРОстРАнстВА Х; от объекта Хь Если Ио ( Е(й), то существует компонента, сдвигающая Х, по направлению к Хь Знаменатель Е ® является нормирующим множителем, а а — настраиваемый параметр. Суммирование производится для учета влияния всех объектов па 1-й объект.
2. Если смещение объекта Х, нарушает ранговый порядок, следует изменить Х, таким образом, чтобы уменьшить это нарушение. Это можно сделать следующим образом: Х, -Х,. — ."~ (Х,. — Х,), Ы(а,,) — Л(а",,)), (10.2З) т. е. когда новый ранг г1(д;;) меньше, чем предыдущий ранг Й(до); это значит, что дц стало слишком большим и оно умень- ШаЕтСЯ ПРОПОРЦИОНаЛЬНО РаЗНОСтИ Л (д;,) — гГ (011). НаСтРаИВаемый параметр ( служит для корректировки степени изменения.
Суммирование может производиться не по всем 1, чтобы алгоритм реагировал лишь на нарушения локальных ранговых порядков. Преобразования такого типа первоначально были предложены для решения некоторых задач психологии, например, следующей задачи [Шепард, 1962а, б~. Совокупность из Х объектов характеризуется набором из Л(й — 1)/2 чисел — попарных степеней сходства 512,..., Я~ 1 ~. При этом физический смысл имеет лишь относительная величина, или ранг каждого Яо.
Задача состоит в том, чтобы получить осмысленное геометрическое представление этих объектов. В (У вЂ” 1)-мерном пространстве всегда можно разместить Х объектов так, чтобы расстояния между объектами до удовлетворяли любому наперед заданному ранговому порядку. Следовательно, вначале Л объектов размещаются таким образом, чтобьг ранги до соответствовали рангам Яо. После этого размерность пространства уменьшается до истинной размерности. Замечательно, что результирующие конфигурация и парные расстояния прл этом полностью определены. Кроме того, в психологических эадачах имеет смысл предположение о монотонной связи между субъективным сходством и геометрическим расстоянием. $ 10.2.
Улучшение разделимости с помощью нелинейного преобразования $10.2. улучп1ен11е РАзделимостп например, по 200 — 300 объектов, для их индикации в пространстве низкой размерности и последующего анализа. Однако, если мы хотим, чтобы нелинейное преобразование было полезным для распознавания образов, то его следует обобщить в двух направлениях. Цель распознавания образов состоит в том, чтобы классифицировать объекты. Классификация по наблюдаемым векторам может оказаться сложной из-за сложности разделяющей поверхности и высокой размерности.
Векторы наблюдений должны быть преобразованы в векторы признаков, которые можно было бы классифицировать с помощью более простых решающих правил. В равной степени важно, чтобы преобразование, найденное для конечного множества классифицированных объектов, можно было применить без использования итеративных процедур, быть может, и к бесконечной последовательности еще не классифицированных объектов. В противном случае преобразование окажется «вычислительным монстром», практическая ценность которого весьма ограничена.
В этом параграфе мы рассмотрим алгоритм нелинейного преобразования для улучшения разделимости в задачах распознавания образов. Цель состоит в изменении структуры расстояний между объектами с соблюдением ограничений, накладываемых структурой исходного распределения. Обычно стремятся уменьшить расстояния между парами объектов, относящихся к одному и тому же классу (расстояния внутри классов), сохраняя неизменными расстояния между объектами, относящимися к разным классам (расстояния между классами). Интуиция подсказывает, что такого рода преобразования должны облегчать разделимость классов. Это стремление к улучшению разделимости ограничивается требованием, чтобы распределение объектов до некоторой степени сохраняло свои исходные свойства. 10.2.1.
Улучшение разделимости, сохранение структуры, расстояния между объектами выборки. Пусть дано множество из Х классифицированных векторов (Х1,..., Х~). Пусть 1-и вектор принадлежит классу 01~,, где А'; — положительное целое число, 1 /с; ЛХ, М вЂ” число классов. Итеративное преобразование пе- 4 ( /. (,И,ЛХ реводит это множество в множество из Л векторов-признаков (У~, У2,...,У,,). Функциональный вид этого преобразования явно ие определен.
Признаки У, выбираются таким образом, чтобы максимизировать критерий вида Как было показано, неллнейное преобразование позволяет уменьшить размерность конфигурации точек. Его можно рассматривать как эффективный метод предварительной обработки (не в реальном времени) небольших множеств исходных данных, .~ (у*; Х*, и) = у, (у„, у„. „„ ~ Р а( 1 А Х1 ХА) У (У й)+РУ (У* Хэ) (10.24) ГЛ. 10, НЕЛИНЕИНОЕ ПРЕОБРАЗОВАНИЕ ПРОСТРАНСТВА где Х*= [Х',Х',... ХЦ'„ у*= [у',у;... у'1' (10.25) (10.26) и Й =- [40Д, 40А,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
