Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Столбцы оптимальной матрицы йг являются обобщенными собственными векторами, соответству- ющими наибольшим собственным значениям в 5втвг = Л15мвег. (97) Следует сделать несколько замечаний относительно этого реше- ния. Во-первых, если 5иг — невырожденная матрица, то задачу, как и прежде, можно свести к обычной задаче определения собст- венного значения. Однако в действительности это нежелательно, так как при этом потребуется ненужное вычисление матрицы, обратной 5ш. Вместо этого можно найти собственные значения как корни характеристического полинома )5,— Л5 )=О, а затем решить (5в — Лг5 )тиг=о непосредственно для собственных векторов твы Поскольку 5в является суммой с матриц ранга единица или менее и поскольку только с — 1 из ннх независимые матрицы, 5в имеет ранг с — 1 нли меньше.

Так что ие более с — 1 собственных значений не нули и искомые векторы весовых функций соответствуют этим ненулевым собственным значениям. Если разброс внутри класса изотропный, собственные векторы будут просто собственными векторами матрицы 5в, а собственные векторы с ненулевыми собственными значениями стягивают пространство, натянутое на векторы шг — щ. В этом частном случае столбшя матрицы Гр" можно найти, просто применяя процедуру ортонормирования Грама — Шмидта к с — 1 векторам ш;. Наконец, заметим, что, вообще говоря, решение для Ж не является однозначным. Допустимые преобразования включают вращение и масштабиРование осей различными путями. Это все линейные преобразования из (с — 1)-мерного пространства в (с — 1)-мерное пространство, и они ) Вывод решения можно найти в книге Я.

'йГ11йв, Ма1йешацса1 Я1а)Ы)ст, РР З77 — 578 (Уорн %)1еу, Неге Уогй, 1962). (Русский перевод; Уилкс С., Математическая статистика, еНаука», М., 19б7.1 Гл. 4. Оеаараиетричеекие иетадее 136 не меняют значительно положения вещей. В частности, они оставляют функцию критерия л (В') инвариантной. Как и в случае с двумя классами, множественный дискриминантный анализ в первую очередь позволяет сократить размерность задачи. Параметрические или непараметрические методы, которые могут не сработать в первоначальном (многомерном) пространстве, могут хорошо действовать в пространстве меньшей размерности. В частности, можно будет оценить отдельные ковариационные матрицы для каждого класса и использовать допущение об общем многомерном нормальном распределении после преобразования, что было невозможно сделать с первоначальными данными.

Вообще преобразование влечет за собой некоторое ненужное перемешивание данных и повышает теоретически достижимый уровень ошибки, а проблема классификации данных исе еще остается. Существуют другие пути уменьшения размерности данных, и мы вернемся к этой теме в гл. 6. Существуют также другие методы дискриминантного анализа; некоторые из иих упоминаются в литературе к этой главе. Одним нз самых фундаментальных и наиболее широко используемых методов все же остается метод Фишера. 4.12.

БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ В данной главе мы рассмотрели некоторые фундаментальные непараметрические методы, которые играют значительную роль в статистической классификации образов. Неупомянутыми остались многие другие вопросы непараметрической статистики, и заинтересованный в этих вопросах читатель может обратиться к работам Гиббоиса (1971) или Томаса(1970) за введением в литературу по этим вопросам. Классической традицией в статистике является вывод оценок плотности распределения вероятностей из эмпирических функций распределения (Фиш, 1963), но для многомерного случая это довольно громоздкий метод. В часто упоминаемом, но довольно труднодоступном отчете Фикса и Ходжеса (1951) разработаны методы применения оценки плотности распределения в теории классификации. Эта работа явилась отправной для большинства дальнейших исследований в области оценки плотности распределения.

Наше изложение метода окна Парзена является некоторым обобщением одномерной формулировки Розенблатта (1956). В действительности работа Розеиблатта предшествовала работе Парзена (1962), но Парзен еще раньше использовал аналогичные методы для оценки спектров, и термин «окно Парзенае является хорошо установившимся. Кроме того, что Парзен продемонстрировал точечную сходимость, ои показал, что оценка плотности является асимптотнчески нормальной, и определил условия, при которых резуль.

тирующая мода выборки сходится к истинной моде. Связь между 4цз. Бибяиаерафические и исясарические медекия !зт оценкой плотностей и оценкой спектров говорит о том, что, работая с характеристическими функциями, можно получить интересные результаты в частотной области. Ватсон н Лндбеттер (1963), пользуясь этим методом, показали, как можно было бы оптимизировать функции окна в случае с конечным числом выборок, если бы можно было наложить ограничения на спектр неизвестных плотностей.

Несомненно, этот метод можно было бы использовать для переноса многих результатов теории фильтрации в решение проблемы оценки плотностей. За исключением работ Фикса н Ходжеса, все эти результаты приводились для одномерного случая. Основные обобщения для многомерного случая были сделаны Мерти (1965, 1966) и Какоулосом (1966). Строгое доказательство того, что метод й„ближайших соседей дает состоятельную оценку многомерной плотности, приведено Лофтсгарденом и Квешенберри (!966).

Удивительные результаты классификации методом ближайшего соседа получены в работе Ковера и Харта (1967), авторы которой установили также границы действия правила й ближайших соседей. Вагнер (1971) расширил эти результаты, показав, что вероятность условной ошибки прн п выборках сходится с вероятностью единица к среднему значению вероятности ошибки Ре(а).

Хелман (1970) показал, как можно дополнить правило ближайшего соседа, чтобы оно позволяло включить в рассмотрение отказы от принятия решений. Важные вопросы скорости сходимости рассматривались Ковером (1968). Поскольку уровень ошибки правила ближайшего соседа ограничивает уровень Байеса, его можно использовать для измерения трудности, присущей задаче классификации образов. Ковер (1969) высказывает предположение, что даже в случае с небольшим числом выборок результаты будут свидетельствовать о том, насколько хорошо будет работать любая непараметрическая процедура, использующая те же самые выборки, Фрелик и Скотт (1971) проводят экспериментальное сравнение использования правил окна Парзена н ближайшего соседа для оценки уровня ошибки Байеса.

У всех этих методов есть один общий недостаток — для них следует хранить полное множество выборок, поиск по которому производится каждый раз, когда нужно классифицировать новый вектор признаков. Предлагался ряд методов уменьшения числа выборок, но только для немногих нз них известны какие-либо статистические свойства. Барус (1966) предложил интересную аппроксимацию для процедуры Фикса и Ходжеса, а Харт (1968) — сжатое правило ближайшего соседа.

Задача нахождения эффективного небольшого опорного множества будет являться, по существу, задачей разбиения совокупности на группы. Более того, определенные процедуры разбиения совокупности иа группы, такие, как предложенные Себестьяном (1962) и Себестьяном и Эди (1966), можно считать эвристическими методами аппроксимации плотно- !Зз Гл. 4. 44елараметрические мелаЪ стей распределения вероятностей.

Тартер, Холкомб и 'Кронмел (1967) предложили использовать для оценки плотности распределения вероятностей разложение в ортогональные ряды. Идея получения полиномиальных разделяющих функций путем аппроксимации оценки окна Парзена о помощью рядов Тейлора была высказана Спештом (1967). Мейзел (1969) указал, что для сходимости таких разложений может потребоваться много членов, и связал метод окна Парзеиа с методом потенциальных функций Аркадьева и Бравермана (1966). Метод потенциальных функций соотнесен с адаптивными методами и методами стохастической аппроксимации, рассмотренными в гл.

5. Большинство из этих методов связано с получением апостериорных вероятностей. Однако Цыпкин (1966) и Кашьяп и Блайдон (1968) показали, что теоретически их также можно использовать для оценки плотностей распределения. Необходимость в преимущественно бинарных измерениях во многих практических системах распознавания образов вынесла вопросы оценки совместной вероятности бинарных переменных за рамки чисто академического интереса. Разложение Радемахера — Уолша часто встречается в теории переключений„и оно тесно связано с разложением Бахадура — Лазарсфельда. Бахадур (1961) дает расширение этого последнего разложения, перенося его с бинарного случая на общий дискретный случай.

Если же разложения по ортогональным функциям минимизируют среднеквадратичную ошибку, Браун (1959) и Льюис (1959) показывают, что при определенных условиях аппроксимация произведений максимизирует энтропию. Иго (1969) приводит границы уровня ошибки, возникающей в результате усечения разложений в ряд. Идея об упрощении аппроксимаций за счет ограничения характера зависимости изучалась Чоу (1962) и Абендом, Харли и Кеналом (1965), которые, в частности, интересовались естественными пространственными зависимостями в бинарных картинах.

Характеристики

Список файлов книги