Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 52
Текст из файла (страница 52)
Данные состоят нз 30 точек, расположенных на единичных интервалах вдоль трехмерной спирали: х, (й) = сон х„ х, (й) = з( п х„ х,(уг) =й))у2, ус=0, 1, ..., 28. На рнс. 6.21, а показано перспективное представление трехмерных данных. Когда был использован критерий е,у, после двадцати итераций процедуры градиентного спуска была получена двумерная конфигурация, показанная на рис. 6.21, б.
Конечно, сдвиги, вращения и отражения этой конфигурации были бы одинаково хорошими решениями. В неметрических многомерных задачах масштабирования величины бп представляют собой различия, чьи числовые значения не так важны, как их упорядочение. Идеальной была бы такая конфигурация, в которой упорядочение расстояний г(гу было бы одинаковым с упорядочением различий бп. Упорядочим т=п(п — 1)У2 различий так, что 6; 1,(...(бову„, н пусть Ы;у — любые гп чисел, удовлетворяющие ограничениям монотонности: г) Вторую частную производную также легко вычислить, так что можно нспользовать алгоритм Ньютона.
Заметим, что прн уг=у единичный вектор от у уг до уу не определен. Если возянкает такая ситуация, то (уг — у )Уйц может быть заменен любым единичным вектором. е) Этот пример взят нз статьи Саммона (Л. 'йг. Яатгпоп, лг.) «А попппеаг гпарр(па 1аг ба1а з1гцс1цге апа1узвз, 1ЕЕЕ Тгагм. Сотр., С-18, 401 — 409 (Мау 1969) Г*. 6. Обучение бга учителя и группироепа В общем случае расстояния Им не удовлетноряют этим ограничениям и числа Ым не будут расстояниями. Одяако степень, с которой дм удовлетворяет этим ограничениям, измеряется величиной у, = ш!и Д (г(,у — д;~)г, Ец ч<! где всегда предполагается, что 3» удовлетворяет ограничениям монотонности.
Таким образом, У,в — мера того, в какой степени ° ее еее еее ° ° ° ° ° ° ° ° ° ее ° ее ее ° ° аг а а и Рис. 6.21. двумерное представление точек данных в трехмерном пространстве (Семион, !969). а — спираль, б — точки отобраиеенин. конфигурация точек у„..., у„соответствует первоначальным данным.
К сожалению, 1,„нельзя использовать для определения оптимальной конфигурации, так как это может свести конфигурацию к одной точке. Однако этот дефект легко устраняется следующей нормировкой: (48) моа ~ бе ч< Таким образом, 1,„инвариантно относительно сдвига, вращения и растяжения конфигурации, и оптимальной можно считать ту конфигурацию, которая минимизирует функцию критерия. Экспе.
риментально было показано, что, когда число точек больше размерности пространства отображения, ограничения на монотонность являются очень сильными. Этого можно ожидать, поскольку число 267 б.!4. Грунлирсена и уменьшение розмерноенш ограничений растет пропорционально квадрату числа точек, что служит основанием для часто встречаемого утверждения о том, что данная процедура дает возможность получить метрическую информацию из неметрических данных.
Качество представления обычно улучшается при увеличении размерности пространства отображения, и иногда необходимо выйти из трехмерного пространства, чтобы получить приемлемо малое значение У,„. Однако это небольшая цена за возможность использования многйх процедур группировок, имеющихся для точек данных в метрическом пространстве. 6.14. ГРУППИРОВКА И УМЕНЬШЕНИЕ РАЗМЕРНОСТИ Так как большая размерность является камнем преткновения для многих процедур распознавания образов, были предложены многочисленные методы уменьшения размерности.
В противоположность процедурам, которые мы только что рассматривали, большинство этих методов обеспечивает функциональное отображение, так что можно определить отображение произвольного вектора признаков. Классическими процедурами являются анализ главных компоненлг и фаюлорныгу анализ, оба из которых уменьшают размерность путем формирования линейных комбинаций признаков '), Если мы рассматриваем задачу как задачу удаления или объединения (т. е. группирования) признаков с сильной корреляцией, то ясно, что методы группировки применимы к этой задаче, В терминах матриц данных, где и строк представляют Н-мерные выборки, под обычной группировкой нужно понимать группировку строк — при этом для представления данных используется меньшее число центров групп,— в то время как под уменьшением размерности нужно понимать группировку столбцов — при этом для представления данных используются комбинированные признаки.
Рассмотрим простую модификацию иерархической группировки для уменьшения размерности. Вместо матрицы размера ах а расстояний между выборками мы рассмотрим матрицу корреляций )с=(рц! размера е(хег', где коэффициент корреляции р!) относится к ковариациям (или ковариациям выборок) как оц РО =,е-— е пиалу х) Целью анализа главных компонент (иавестного в литературе по теории связы как разложение Кархунена — Лозва) являечся нахождение представления в пространстве меньшей размерности, учитывающего дисверсни признаков. Целью факторного анализа является нахождение представления в пространстве меньшей размерности, учитывающего корреляции между признахами.
Для более глубокого ознакомления см. книги Кепба!1 М. О., 6(пзг! А. еТЬе зачался !Ьеогу о1 Ма1!знсзы ч. 3, сь. 43 (На1пег, (Чем 'г'ог(г, 1966) или Наппап Н. Н. «Модегп (ас(ог апа!уз!зе (()и!чегз!!у о( СЫсако Ргем, СЫсако апд Ьапдоп, 2пб еб., 1967). Гл. 6. Обучение бег учивеля и группировка Так как 0(ри(1, причем для некоррелированных признаков р',г —— О, а для полностью коррелированных признаков рм — — 1, то ри играет роль функции подобия для признаков. Два признака, для которых р',г велико, хорошие кандидаты на объединение в один признак; таким образом, размерность снижается на единицу. Повторение этого процесса приводит к следующей иерархической процедуре: Процедура: Иерархическое Уменьшение Размерности 1. Пусть Й=-д и Г;=(х;), г=1,..., д.
Цикл: 2. Если г)=гг', останов. 3. Вычислить матрицу корреляций и найти наиболее коррелированиую пару групп признаков, скажем гт, и Ур 4. Объединить У; н У и стереть Т; и уменьшить 3 иа единицу. 5. Перейти к Цикл. Вероятно, самым простым способом слияния двух групп признаков является их усреднение. (Это предполагает, что признаки были масштабированы так, что их числовые значения сравнимы.) Имея такое определение нового признака, несложно определить матрицу корреляции для групп признаков. Возможны различные модификации такого подхода, ио мы их не будем рассматривать.
С точки зрения классификации образов из всех способов уменьшения размерности наибольшей критики заслуживает то, что все они связаны с достоверным представлением данных. Наибольшее внимание обычно уделяется тем признакам нли группам признаков, которые обладают наибольшей изменчивостью. Но для классификации нам нужно разделение, а не представление. Грубо говоря, наиболее интересны те признаки, для которых разница между средними значениями классов велика по сравнению со стандартным отклонением, а не те, для которых велики стандартные отклонения. Короче говоря, нас интересует нечто подобное методу множественного днскриминантного анализа, описанному в гл. 4.
Растет количество теоретических работ по методам уменьшения размерности для классификации образов. Некоторые из этих методов стремятся сформировать новые признаки на основе линейных комбинаций старых. Другие из них стремятся создать меньшее подмножество первоначальных признаков. Основная проблема этой теории состоит в том, что деление распознавания образов на извлечение признаков, а затем классификацию теоретически является искусственным.
Полностью оптимальный выделитель признаков не может быть чем бы то ии было иным, как оптимальным классификатором. Только тогда, когда накладываются ограничении на классификатор нли на размер множества выборок, можно сформулировать нетривиальную (и очень сложную) задачу. В литературе можно найти различные способы преодоления этой проблемы при д.вд. Бидлиогра4инесиие и историяеисие сведения 269 некоторых обстоятельствах, и мы отметим несколько отправных точек для такой литературы. Обычно более продуктивен путь, когда знание области действия задачи позволяет получить более информативные признаки.
В части П этой книги Мы займемся систематическим изучением способов извлечения признаков из визуальных данных и более общей задачей анализа зрительных сцен. 6.15. БиБлиОГРАФические и истОРические сВедения Литература по обучению без учителя и группировкам так обширна и рассеяна среди различных областей науки, что предлагаемый список можно рассматривать как случайную выборку. К счастью, некоторые из источников имеют обширную библиографию, что облегчает нашу задачу. Исторически дата первых источников восходит по меньшей мере к 1894 году, когда Карл Пирсон использовал выборки для определения параметров смеси двух нормальных плотностей одной переменной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
