Лекция 5 Распознавание и классификация образов на основе использования предположения о близости описаний


Скачать 77.05 Kb.
НазваниеЛекция 5 Распознавание и классификация образов на основе использования предположения о близости описаний
Дата публикации12.03.2013
Размер77.05 Kb.
ТипЛекция
referatdb.ru > Математика > Лекция

- -

Лекция 5
Распознавание и классификация образов на основе использования

предположения о близости описаний
В случаях, когда недопустимы предположения классического подхода, применяются похожие методы классификации, основанные на более слабом предположении, что объекты, описания которых расположены близко друг от друга в пространстве описаний, по-видимому, принадлежат одному и тому же классу. Это предположение принято называть предположением о близости описаний. Простой пример: пол конкретного человека обычно можно определить, выясняя его схожесть с произвольно выбранным мужчиной или с произвольно выбранной женщиной. Точнее, классификация основана на оценке среднего расстояния между описаниями неизвестного объекта и каждого объекта из известного множества, т.е. предполагается усреднение по измерениям для объектов из этого множества. Ещё один пример: установление происхождения классической греческой скульптуры или мраморной кладки по результатам измерения относительного количества различных изотопов химических элементов в мраморе. Обнаружено, что мрамор из античных карьеров можно отличать по отношению концентраций углерода-13 к углероду-12 и кислорода-18 к кислороду-16. Разумеется, необходимы обоснованные правила отнесения с разной надёжностью каждого из исследуемых фрагментов скульптуры или кладки к соответствующему карьеру.

По определению евклидова расстояния квадрат расстояния между двумя точками x и y в пространстве D равен

x, y)=

Интуитивно ясно, что объект с описанием x похож на объекты с описаниями, принадлежащими некоторому множеству , если мало среднее значение квадрата расстояния между x и точками из Y .Таким образом, точка x близка к множеству Y , если мала величина

x,y)=x, y).

При сравнении двух множеств оценивается среднее расстояние между парами точек, взятых по одной из каждого множества. Для множеств X и Y, содержащих соответственно и точек, средне значение квадрата расстояния между X и Y равно

x, y).

Чем дальше в среднем друг от друга точки из X и Y , тем больше значение


Для оценки плотности расположения точек внутри множества обычно используется среднее значение квадрата расстояния между точками этого множества:

x,y).

Общая идея, лежащая в основе подхода, использующего понятие близости, состоит в преобразовании пространства описаний D в пространство D, в котором все точки одного множества расположены близко друг к другу, а точки различных множеств удалены друг от друга на некоторое расстояние. Пространство можно считать результатом линейного преобразования мерного пространства , если каждая точка x отображается в точку x по формуле

x x W,

где W – симметричная (mm)-матрица. Компоненты вектора x задаются равенствами

x

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

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

Имеется интересная геометрическая интерпретация этого критерия. Можно представить себе составную меру в виде прямой в m-мерном пространстве, выходящей из начала координат пространства D. Любая точка будет проектироваться на эту прямую. Прямая выбирается таким образом, чтобы точки одного множества проектировались в одну и ту же область, а разных множеств – в разные области. Эффективность такого подхода можно проиллюстрировать результатами его использования при решении упомянутой ранее задачи классификации – установлении происхождения материала археологических мраморных обломов при помощи изотопов. На рис.1 приведены результаты измерений, полученные для образцов из различных карьеров. Данные, определяющие оси, выведены из отношений и с помощью сложных расчётов, в которых измерения исследуемого фрагмента сопоставлялись с аналогичными измерениями для стандартных образцов.

Рис.1. Отклонения содержания углерода-13 и кислорода-18 (относительно стандарта PDP) в образцах мрамора из античных карьеров. Треугольниками обозначены мраморные обломы (Крейг и Крейг, 1972).



На рис.5.2 изображены проекции точек из множеств, соответствующих образцам из карьеров Парос, Гиметт и Пентели, на прямую L, представляющую собой составную меру, которая определяется взвешенными суммами упомянутых выше отношений кислорода и углерода.

Соответствующие вычислительные процедуры используют три вспомогательные матрицы G, V и T. Для любой пары точек x, y определим матрицу G(x,y) порядка m с элементами

x, y)= (x, y).


Рис.2.Проекции на соответствующие оптимальные дискриминантные собственные векторы.
Предположим, что исходные данные состоят из k множеств наблюдений, соответствующих k классам. Обозначим через V усреднённую матрицу G (x, y) по всем парам точек x и y из различных множеств Xи X, а через T – усреднённую матрицу G(x, y) по всем парам независимо от принадлежности их какому-то классу. Алгебраически это можно записать следующим образом:

V=xy,

X= n=

T=x, x).

Для дальнейшего рассмотрения необходимо напомнить, как определяются собственные векторы и собственные значения матрицы. Рассмотрим для заданной квадратной матрицы А порядка n следующее уравнение

Аx=x,

где x- неизвестный числовой вектор, высота которого равна порядку А, а неизвестное число. Данное уравнение при любом обладает тривиальным решением x=0. Однако, нас интересуют только такие , при которых эта система имеет нетривиальные решения. Эти значения называются собственными значениями матрицы А, а решения x данного уравнения при таких её собственными векторами.

Собственные значения и собственные векторы находятся следующим образом. Так как x=x, где - единичная диагональная матрица, то можно записать

(А)x=0, (1)

т.е. мы имеем дело с системой из n алгебраических линейных однородных (без свободных членов) уравнений с n неизвестными, где n порядок матрицы А. Для наличия нетривиального решения необходимо и достаточно, чтобы определитель системы равнялся нулю, т.е.

det (А)=0.

Это уравнение называется характеристическим уравнением матрицы А, оно служит для определения собственных значений Так, для матрицы
А

характеристическое уравнение имеет вид



При раскрытии определителя получаем алгебраическое уравнение, степень которого равна порядку матрицы А, т.е. матрица порядка n имеет n собственных значений, среди которых, правда, могут быть совпадающие.

Определив какое-либо собственное значение, можем найти соответствующие собственные векторы из векторного уравнения (1), переписанного в виде системы скалярных уравнений


Если W – матрица, строки которой являются собственными векторами матрицы VT(T- обратная к T матрица, TT= ), то w - собственный вектор, соответствующий наибольшему собственному значению. Для определения обратной матрицы необходимо знать следующее правило: если



то

где большими буквами обозначены алгебраические дополнения соответствующих элементов в матрице

Собственный вектор w определяет направление прямой, выходящей из начала координат пространства D и максимально разделяющей точки различных множеств. Прямая линия L образует с j-ой осью dпространства D угол, такой, что



Определение прямой L завершается этап распознавания образов. На этапе классификации объект относится к классу i в зависимости от положения на прямой L проекции его описания y. Для любой точки x обозначим

x w1.

Вектор из класса классифицируется, как описание объекта, тогда и только тогда, когда величина
y) =

минимальна.

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

Сравнение статистического анализа и основанного на понятии близости распознаваемых образов.

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

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

.

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

Похожие рефераты:

Процедуры распознавания зависят от понятия расстояния между двумя...
Методы классификации распознавания образов, использующие евклидовы пространства описаний
Процедуры распознавания зависят от понятия расстояния между двумя...
Методы классификации распознавания образов, использующие евклидовы пространства описаний
Лекция 10 Грамматическая классификация образов
Если можно определить алгоритм, осуществляющий это, то язык называют рекурсивным, а грамматика разрешимой
Лекция 15. Доходы, расходы и прибыль банков Понятие доходов банка и их классификация
Понятие и классификация прибыли банка по видам банковских операций, направления ее распределения и использования
Методические указания к выполнению контрольной самостоятельной работы по специальному курсу
Шестаков К. М. Лабораторный практикум по специальному курсу «Распознавание образов в потоках данных»: Учебное пособие для студентов...
4. Лекция Сущность, классификация
Тема Лекция Сущность, классификация, структура и участники инновационных проектов
I. информационные системы связи
Под информацией нужно понимать не сами объекты и процессы, или их свойства, а представляющие характеристики предметов и процессов,...
Инструкция Для того чтобы помочь Вам выбрать профессию с учетом Ваших...
Просим Вас внимательно прочитать пару описаний и сначала выбрать для себя тот вид занятия, которым Вы предпочли бы заняться. Затем...
Дорога к подлинной близости." конференция "Я и Ты. Парадоксы близости" Что такое близость?
Анна Юхневич практикующий психолог, сертифицированный гештальт-терапевт, нлп-практик
Лекция Классификация проектов и их жизненный цикл Классификация проектов
Для удобства анализа проектов, а также систем управления ими, множество разнообразных проектов классифицируется по разным основополагающим...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза