Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 51
Текст из файла (страница 51)
10. нелинейное пРеОБРАзОВАние пРОстРАнстВА % 10.1. ИСТИННАЯ РАЗМЕРНОСТЬ ИСХОДНЫХ ДАННЫХ ляются доминирующими, означает, что эта разность значительна, и может быть использовано для выбора п0 собственных значений и при наличии шума. 10.1.2. Неитеративный алгоритм. Так как истинная размерность данных определяется локальными размерностями, то при неограниченном числе наблюдений и отсутствии шума истинная размерность находится уменьшением размера локальных Областей до тех пор, пока получаемая размерность не достигнет предельного значения.
На практике, Од1нако, имеется несколько факторов, усложняющих эту процедуру: 1) ограниченное число наблюдений; 2) наличие шума; 3) большой расход машинного времени. Рассмотрим первые два пункта более подробно. Так как максимальная размерность множества выборочных векторов имеет размерность, меньшую, чем число векторов, необходимо обеспечить наличие достаточного числа векторов в каждой локальной области. При ограниченном числе наблюдений может оказаться, что при достаточном числе векторов локальная область будет слишком большой для того, чтобы множество д1анных вблизи данной точки можно было аппроксимировать поверхностью.
В таких локальных областях оценка размерности оказывается выше, чем истинная размерность. Наиболее простая процедура оценки локальной размерности состоит в вычислении собственных значений выборочной ковариационной матрицы в локальной области и подсчете числа доминирующих собственных значений. Величина порога, выбранного для отд1еления доминирующих собственных значений, влияет на оценку размерности. Пусть величина порога О, составляет е% От величины наибольшего собственного значения. Число объектов, необходимое для оценки числа доминирующих собственных значений, обычно во много раз меньше, чем требуется для оценки самих собственных значений. Опыт показывает, что это число М должно лишь в 2 — 3 раза превышать число доминирующих собственных значений п0, независимо от числа переменных п.
Например, при п0 = 3 достаточно, чтобы У = 6 —: 9 даже для п = = 1000. Так как д1ля большинства приложений п0 (( и, то для Опред1еления собственных значений следует пспользовать метод, примененный в примере 2.20. Добавление шума приводит к необход1имости ограничивать снизу размеры локальных областей. Это показано на рис. 10.3. Как говорилось выше, при большом размере области можно получить завышенную оценку истинной размерности. С другой стороны, уменьшение размера локальной области уменьшает доминирующие собственные значения относительно составляющей шума,' Поэтому мы.
должны выбрать некоторое компромиссное 1<а<3, 02<па<08, '(10.14),; ;значение размера локальных областей. Кроме того, необход1имо 'установить более высокий порог для предотвращения влияния шума на оценку размерности. Так как эти настраиваемые пара, метры зависят от исходных данных то желательно иметь гибкую 1 вычислительную систему, такую, чтобы оператор имел возможность целенаправленно менять ~г : эти параметры при переходе : от задачи и задаче и от одной локальной области к другой.
Рассмотрим один из вомож- ° Ф ных алгоритмов ре1пения этой задачи [Фукунага, 1971а]. Выбор размера ло- ° ° кальных областей. Хотя . размер локальной области мо— жет меняться от области к Об- х~ ' ласти, удобнее вначале выбрать его фиксированным. Подходя- Рис. 10.3. Влияиие шума.
щий размер выбирается после изучения связи межд1у размером н результирующей размерностью в окрестности объекта, ближайшего к выборочному среднему значению всего множества объектов. Размер зад1ается или рад1иусом гиперсферы, или числом объектов в локальной области. Оператор должен иметь возможность корректировать размер всякий раз, когд1а в этом возникнет необходимостьь. 2. Выбор локальных центров. Решение этой зад1ачи требует поиска в пространстве высокой размерности и включает много компромиссных решений, касающихся, например, выбора размера локальной области, величины перекрытия и метода поиска. Одно из возможных решений состоит в том, чтобы в качестве первого локального центра выбрать первый объект из списка объектов.
Объекты локальной области, построенной вокруг этого первого объекта, используются для определения локальной размерности, а затем исключаются из списка. Эта процедура повторяется до тех пор, пока список не станет пустым. Для определения истинной размерности исходных д1анных вычисля1отся статистики локальных размерностей. П р и м е р 10.1. Гауссовская последовательность является распростра.пенной случайной функцией, так как она с приемле- мой точностью аппроксимирует многие сигналы, встречающиеся на практике, а для ее описания достаточно трех параметров, как показано в (10.2). В рассматриваемом примере параметры а и п1 были равномерно распределены в интервалах 303 302 Таблица 101 Нормированные собственные значения Число об ьек- тов 0,00 0 00 О,ОЗ 0,05 0,84 1,28 1,62 2,07 4,60 1,00 1,00 1,00 1,00 1,00 0,15 0,27 0,31 0,47 0,56 0,02 0,04 0,04 0,07 5 10 15 25 100 0,00 0,00 0,01 0,05 ! 0,01 0,19 ~ 0,13 0,00 Ггг.
]г и о Ог Хвц с угсг )минимальная размерность) )максггмальная размерность) )минимальная размерность) )максимальная размерность) (минимальная размерность) 1максимальная размерность) 0,81 0,83 1,60 2,43 1,92 2,15 5 5 10 10 15 15 1,00 1,00 1,00 1,00 1,00 1,00 0,00 0,67 0,39 0,38 0,55 0,56 Число областей разных размеров гразмзр задается числом объек.гов) 0,03 О,ОО 0,07 0,00 0,05 0,00 Локаль- ная размеР- ность Критерии 0,00 1О 15 1З5 0,00 0,01 0 20 4 0 0 О 0 0 0 12 10 2 0 0 0 13 4 4 0 О 24 0 0 О 13 11 0 0 12 3 Число областей разных разме- ров гразмер задается числом объектов) Локальная раз- мерность Критерий 15 ~ 100 Г ~ 1О *) гсру!сунагз, 1971о ].
*) гсрукуггзгз, 1971а]. ГЛ. 10. НЕЛИНЕйг)ОЕ ПРЕОВРЛЗОВЛНИЕ ПРОСТРАНСТВА Прим.р гауссовской случайной последовательности с двумя случайными параметрами *) а) Нормированные собственные значения Вокруг вектора, блиясвгггяего к вектору выборочного средн;го б) Число локальных областей в зависимости от локаль- ных размерностей и размера области % 10.1. ИСТИННАЯ РАЗМЕРНОСТЬ ИСХОДНЫХ ДАННЫХ а о = 0,1. При каждом случайно выбранном наборе параметров генерировалось 100 20-мерных объектов. Результаты, относящиеся к этому примеру, приведены в табл.
10.1. Данные приведены лишь для некоторых типичных локальных областей, так как разница между максимальными и минимальными размерностями невелика. Табл. 10.1б — это одна из итоговых таблиц, построенных в процессе работы алгоритма. Опа показывает, что истинная размерность равна 2. Глобальное разложение Карунена — Лоева дает размерность 4 для критерия Р)0 и 6 для критерия Р). П р и м е р 10.2. В этом примере для генерирования данных также использовалась гауссовская последовательность с тремя случайными параметрами, равномерно распределенными в интервалах 1 ( а ( 3, 0,2 ( тп ( 0,8, 0,05 ( а (0,20. '(10.15) При каждом случайно выбранном наборе параметров генерировалось по 125 20-мерных объектов.
В табл. 10.2 приведены итоТаблица 10.2 Игсгзвая таблица гауссоескои последовательности с тремя случайными параметрами *) говые результаты. Таблица показывает, что истинная размерность равна 2 и 3, в то время как размерность глобального разложения Карунена — Лоева равна 4 и 7 для критериев ь]10 и й) соответ- ственно. 10.1.3. Итеративный алгоритм. Конфигурация векторов в и- мерном пространстве может иметь истинную размерность, мень- 305 Уг г Лг Х~ У4 Ув Уг 1'~ I I $ / / 1 / 1 в 1 / в ) 'Хв~ .Х \ Ф в ! Ю / I ~ г Х~ ~)--- — -=~ г г Уав ~Уг ~г У в / ! г / (10.16) г) (10.17) С~15 ) С~45 ~ ° ° ° ) аа23в Л (с1 ) ~ (~ 1).
(10.18) 304 гл. 10. нелинейное пРеОБРА30ВАние пРОстРАнстВА шую чем )2. Это означает, что указанная конфигурация паходится на )те-мерной гиперповерхности в )2-мерном пространстве ()тс~п). Эту гиперповерхность можно рассматривать как результат нелинейного искажения некоторой линейной гиперповерхности. Это искажение можно устранить с помощью итеративного процесса ..аУт «растягивания».
На рис. 10.4 поу казано множество из пяти вектоУ~ .. ров, располо)кенных на кривой У4~ .- (сплошная линия) в двумерном Хг .Ф' г пространстве. Эти точки развертываются в прямую линию (пунктирная линия). После этого истинную размерность можно опредег лить методом Карунена — Лоева. Растягивание — вид нелинейРис.
10.4. Растягивание данных. ного преобразования. По мере того как происходит процесс растягивания, анализ Карунена — Лоева показывает, что для объяснения наблюдаемых свойств исходных данных требуется все меньше и меньше переменных. Но по определению существенной размерности имеется некоторое минимальное число переменных, которые необходимо принять в расчет для объяснения свойств исходных, не растянутых данных. Следовательно, на процесс растягивания должно быть наложено некоторое ограничение, которое мы сейчас рассмотрим. Свойство исходных данных, которое должно быть сохранено при растягивании,— это ранговый порядок расстояний между объектами выборки. 11усть ди — расстояние между 1-м и )-м объектами, т.
е. с~и = /~Хз ХД, 1, У = 1, 2, ..., Л. Если эти расстояния удовлетворяют условию то говорят, что ранг ~)5 равен 1, ранг с145 равен 2 и т. д.: В результате преобразования от Х, к У; расстояния между объ- ектами ,~" ~~у у ~~; 7 = 1,2, ..., ЛГ. (10.19) Величины И1), вообще говоря, отличны от де, но нам хотелось % 10 1 ИСТИННАЯ РАЗМЕРНОСТЬ ИСХОДНЫХ ДАННЫХ бы сохранить их ранги, т. е. сделать так, чтобы ранг дз) остался равным рангу ди. Л(д;)) = Л(д))), ю, У = 1, 2, ..., Х. (10.20) Для того чтобы увидеть связь между истинной размерностью и ранговым порядком, рассмотрим следующие простые примеры. П р и м е р 10.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
