Ортогонализация

Формальная постановка задачи классификации

Классификация с обучением и без обучения

Признаки и классификаторы

Предмет распознавания образов

Распознавание образов – это научная дисциплина, целью которой является классификация объектов по нескольким категориям или классам. Объекты называются образами.

Классификация основывается на прецедентах.

Прецедент – это образ, правильная классификация которого известна.

Прецедент – ранее классифицированный объект, принимаемый как образец при решении задач классификации. Идея принятия решений на основе прецедентности – основополагающая в естественно-научном мировоззрении.

Будем считать, что все объекты или явления разбиты на конечное число классов. Для каждого класса известно и изучено конечное число объектов – прецедентов. Задача распознавания образов состоит в том, чтобы отнести новый распознаваемый объект к какому-либо классу.

Задача распознавания образов является основной в большинстве интеллектуальных систем. Рассмотрим примеры интеллектуальных компьютерных систем.

1. Машинное зрение. Это системы, назначение которых состоит в получении изображения через камеру и составление его описания в символьном виде (какие объекты присутствуют, в каком взаимном отношении находятся и т.д.).
2. Символьное распознавание – это распознавание букв или цифр.
• Optical Character Recognition (OCR);
• Ввод и хранение документов;
• Pen Computer;
• Обработка чеков в банках;
• Обработка почты.
3. Диагностика в медицине.
• Маммография, рентгенография;
• Постановка диагноза по истории болезни;
• Электрокардиограмма.
4. Геология.
5. Распознавание речи.
6. Распознавание в дактилоскопии (отпечатки пальцев), распознавание лица, подписи, жестов.

Измерения, используемые для классификации образов, называются признаками. Признак – это некоторое количественное измерение объекта произвольной природы. Совокупность признаков, относящихся к одному образу, называется вектором признаков. Вектора признаков принимают значения в пространстве признаков. В рамках задачи распознавания считается, что каждому образу ставится в соответствие единственное значение вектора признаков и наоборот: каждому значению вектора признаков соответствует единственный образ.

Классификатором или решающим правилом называется правило отнесения образа к одному из классов на основании его вектора признаков.

Пример 1. Иллюстрация понятий признаков и классификатора и идеи распознавания (классификации). Рассмотрим задачу диагностики печени по результатам инструментального исследования (рис.1.1). Доброкачественные (левый рисунок – класс A) и злокачественные (правый рисунок – класс B) изменения дают разную картину. Предположим, что имеется несколько препаратов в базе данных, про которые известна их принадлежность к классам A и B (правильная классификация). Очевидно, что образцы отличаются интенсивностью точек изображения. В качестве вектора признаков выберем пару: среднее значение () и среднеквадратичное отклонение () интенсивности в изображении.

Рис. 1.1. Образы-прецеденты, соответствующие классу A (слева) и B (справа)

Рис. 1.2. Распределение векторов признаков прецедентах класса A (кружки) и класса B (крестики). Признаки - средние значения и средние отклонения яркости в образах. Прямая линия разделяет вектора из разных классов

На рис.1.2 представлены изображения этих образов в пространстве признаков. Точки, соответствующие прецедентам разных классов, разделяются прямой линией. Классификация неизвестного образа (соответствующая точка изображена звездочкой) состоит в проверке положения точки относительно этой разделяющей прямой.

Практическая разработка системы классификации осуществляется по следующей схеме (рис.1.3). В процессе разработки необходимо решить следующие вопросы.

1. Как выбрать вектора признаков? Задача генерации признаков – это выбор тех признаков, которые с достаточной полнотой (в разумных пределах) описывают образ.
2. Какие признаки наиболее существенны для разделения объектов разных классов? Задача селекции признаков – отбор наиболее информативных признаков для классификации.
3. Как построить классификатор? Задача построения классификатора – выбор решающего правила, по которому на основании вектора признаков осуществляется отнесение объекта к тому или иному классу.
4. Как оценить качество построенной системы классификации? Задача количественной оценки системы (выбранные признаки + классификатор) с точки зрения правильности или ошибочности классификации.

увеличить изображение
Рис. 1.3. Основные элементы построения системы распознавания образов (классификации)

В зависимости от наличия или отсутствия прецедентной информации различают задачи распознавания с обучением и без обучения. Задача распознавания на основе имеющегося множества прецедентов называется классификацией с обучением (или с учителем).

Рис. 1.4. Изображение различных типов поверхности и кластеризация соответствующих векторов признаков

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

Пример 2. Рассмотрим съемку со спутника и классификацию поверхности по отраженной энергии (рис.1.4). На рисунке изображены снимок из космоса (слева) и результат кластеризации векторов признаков, рассчитанных для различных элементов изображения (справа). Распределение образов, изображенных точками () по классам осуществляется на основе анализа "скоплений" этих точек в пространстве признаков.

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

Будем использовать следующую модель задачи классификации.

- множество объектов распознавания (пространство образов).

- объект распознавания (образ).

- индикаторная функция, разбивающая пространство образов на непересекающихся классов . Индикаторная функция неизвестна наблюдателю.

– пространство наблюдений, воспринимаемых наблюдателем (пространство признаков).

- функция, ставящая в соответствие каждому объекту точку в пространстве признаков. Вектор - это образ объекта, воспринимаемый наблюдателем. В пространстве признаков определены непересекающиеся множества точек , соответствующих образам одного класса.

- решающее правило – оценка для на основании , т.е. .

Пусть – доступная наблюдателю информация о функциях и , но сами эти функции наблюдателю неизвестны. Тогда – есть множество прецедентов.

Задача заключается в построении такого решающего правила , чтобы распознавание проводилось с минимальным числом ошибок.

Обычный случай – считать пространство признаков евклидовым, т.е. . Качество решающего правила измеряют частотой появления правильных решений. Обычно его оценивают, наделяя множество объектов некоторой вероятностной мерой. Тогда задача записывается в виде .

40. Ортогонализация Шмидта. Выделение главных компонент. Базис Карунена-Лоэва.

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81_%D0%93%D1%80%D0%B0%D0%BC%D0%B0_%E2%80%95_%D0%A8%D0%BC%D0%B8%D0%B4%D1%82%D0%B0

http://dic.academic.ru/dic.nsf/enc_mathematics/3738/%D0%9E%D0%A0%D0%A2%D0%9E%D0%93%D0%9E%D0%9D%D0%90%D0%9B%D0%98%D0%97%D0%90%D0%A6%D0%98%D0%AF

Перевод

ОРТОГОНАЛИЗАЦИЯ

процесс ортогонализации,- алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства V ортогональной системы ненулевых векторов, порождающих то же самое подпространство в V. Наиболее известным является процесс ортогонализации Шмидта (или Грама - Шмидта), при к-ром по линейно независимой системе a_l,..., a_k строится ортогональная система b_l,..., b_k такая, что каждый вектор b_i (i=1,...,k).линейно выражается через a_l,..., a_i то есть b_i =, где C=||g _ij || - верхняя треугольная матрица. При этом можно добиться того, чтобы система { b_i } была ортонормированной и чтобы диагональные элементы g _ij матрицы Сбыли положительны; этими условиями система { b_i } и матрица Сопределяются однозначно..

Процесс Грама-Шмидта состоит в следующем. Полагают b₁=а ₁;если уже построены векторы b_l,..., b_i то

где

j=1,...,i, найдены из условия ортогональности вектора b_i+1 к b_l,..., b_i. Геометрии, смысл описанного процесса состоит в том, что на каждом шагу вектор b_i+1 является перпендикуляром, восстановленным к линейной оболочке векторов a_l,..., a_i до конца вектора b_i+1. Произведение длин | b_i |...|b _k | равно объему параллелепипеда, построенного на векторах системы { а _i }, как на ребрах. Нормируя полученные векторы b_i, получают искомую ортонормированную систему. Явное выражение векторов b_i через a_l,..., a_k дает формула

(определитель в правой части следует формально разложить по последнему столбцу). Соответствующая ор-тонормированная система имеет вид

где Г _i - Грама определитель системы a_l,..., a_j.

Этот процесс применим также и к счетной системе векторов.

Процесс Грама-Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхней треугольной матрицы с положительными диагональными элементами, что есть частный случай Ивасавы разложения.

http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82

http://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-07-pca.pdf

https://www.google.by/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CD8QFjAD&url=http%3A%2F%2Fwww.tvd-home.ru%2Fdocs%2Fpca.doc&ei=WrX2UNHTOpHgtQaLnIDgBQ&usg=AFQjCNEMGhRMF3GE93_faJiyvVYWxK_H4g&bvm=bv.41018144,d.Yms&cad=rja

Метод главных компонент (МГК)

Представим себе, что наблюдается D сигналов, каждый из которых есть сумма d (d < D) «источников». Например, это могут быть звуковые сигналы, снимаемые с помощью микрофонов, при том, что источников звука меньше, чем микрофонов. С помощью МГК можно по наблюдаемым сигналам определить количество источников, а также выделить сигналы самих источников.

Обозначим , …, временные ряды источников. Если каждый временной ряд представить, как вектор-столбец, то из них можно составить матрицу размером

(1)

Предположим, что наблюдаемые сигналы, получаются как линейные комбинации этих источников, тогда для i -го сигнала будем иметь:

. (2)

То есть, например, микрофоны расположены в разных местах и коэффициент определяется расстоянием от i -го микрофона до k -го источника. Обозначим X матрицу размером , столбцами которой будут временные ряды сигналов. Из коэффициентов составим матрицу A. Тогда выражение (2) в матричном виде запишется как:

. (3)

(Кому не нравится транспонирование, меняйте местами индексы i и k в (2)).

Поскольку столбцы матрицы X получаются как линейные комбинации d < D величин, то они линейно зависимы. В частности это означает, что если на каждую строку X посмотреть как на координаты точки в D- мерном пространстве, то эти координаты также линейно зависимы, то есть точки лежат в некотором подпространстве (на d -мерной гиперплоскости).

Метод главных компонент, по сути, состоит в выборе нового ортогонального базиса, где базисные вектора будут направлены так, чтобы дисперсия проекций упомянутых точек на каждый базисный вектор была максимальной. В результате первые d векторов будут параллельны гиперплоскости, где лежат все точки, а остальные будут ей перпендикулярны и дисперсия проекций на них будет равна 0.

Нахождение новых базисных векторов и дисперсий проекций на них происходит следующим образом. Рассчитывается матрица ковариаций наблюдаемых сигналов:

(4)

Для этой матрицы находятся собственные числа и собственные вектора. Собственные вектора как раз и будут новыми базисными векторами, а соответствующие собственные числа – дисперсиями проекций точек на них. Ненулевыми будут только d собственных чисел

http://www.keldysh.ru/papers/2006/prep19/prep2006_19.html

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%B0%D1%80%D1%83%D0%BD%D0%B5%D0%BD%D0%B0_%E2%80%94_%D0%9B%D0%BE%D1%8D%D0%B2%D0%B0

Дата добавления: 2014-01-04