42725

Методы классификации основанные на сравнении с эталоном

Лабораторная работа

Математика и математический анализ

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

Русский

2013-10-30

732 KB

22 чел.

Лабораторная работа №1

«Методы классификации основанные на сравнении с эталоном»

1 Системы распознавания образов. Задача классификации

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

Многие задачи анализа изображений можно успешно решить с помощью классической системы распознавания образов, блок-схема которой показана на рисунке 1.1. Системы распознавания образов предназначены для классификации входных данных или их частей на несколько категорий (или классов).

Рисунок 1.1 – Блок-схема системы распознавания образов

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

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

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

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

Можно ожидать, что измеренные признаки обучающей выборки будут группироваться в соответствии с принадлежностью фрагментов к классам. В этом случае будут установлены границы областей принятия решений для разделения признаков новых фрагментов, подлежащих классификации (см. рисунок 1.2). Однако следует отметить два ограничения методов распознавания образов. Во-первых, в случае распознавания изображений, входные данные имеют огромные размеры и во многих случаях число возможных классов очень велико, поэтому объем вычислений, который должно выполнять устройство распознавания образов, часто оказывается невыполнимым. Более важное ограничение состоит в том, что методами классификации нельзя провести структурный анализ сцены, для которой, например, требуется получить описание типа «тело A расположено выше и правее тела B».

Рисунок 1.2 – Пример классификации обучающей выборки
по двум признакам

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

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

Пусть  обозначают m возможных классов образов, подлежащих распознаванию и пусть  – вектор замеров признаков, где  представляет k-ый замер.

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

Пусть  обозначает, что вектор признаков X входного образа принадлежит классу . Тогда можно записать, что для всех  выполняется следующее условие:

(1.1)

Таким образом, в пространстве признаков  граница разбиений, называемая границей между областями, относящимися соответственно к классам , , выражается уравнением:

(1.2)

 

Общая схема классификатора, использующего критерий (1.1), и типичный двумерный пример приведены на рисунке 1.3 и рисунке 1.4 соответственно.

Рисунок 1.3 – Общая схема классификатора с разделяющей функцией

1.2 Классификатор по минимальному расстоянию

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

Рисунок 1.4 – Пример классификатора с разделяющей функцией в случае для двух признаков

Каждый класс представляется своим центром масс . Основанное на этой модели простое разделение пространства признаков задается поиском минимального расстояния от вектора признака до каждого класса. Для выполнения этой операции мы вычисляем расстояние вектора признака m до каждого центра класса :

(1.3)

 

Тогда признак приписывается к классу, до которого он имеет кратчайшее расстояние.

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

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

Размер класса мог бы приниматься во внимание посредством введения масштабного множителя в вычисление расстояния (1.3). Таким образом, признак должен быть ближе к узкому классу, чтобы связываться с ним. Во-вторых, мы можем определить максимальное расстояние для каждого класса. Если расстояние признака больше, чем максимальное расстояние для всех классов, то объект отклоняется как не принадлежащий ни одному из распознанных классов.

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

1.3 Метод ближайших соседей

Метод ближайших соседей — простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

Классифицируемый объект относится к тому классу, которому принадлежит ближайший объект обучающей выборки.

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

2. Практическая часть

Скалярное умножение векторов.

где p - число информативных признаков.

Абсолютное значение вектора (норма).

Решение задач:

Задать три вектора A, B, C в двумерном евклидовом пространстве.

  1.  Рассчитать направляющие косинусы для A,B  и  B,C. Сделать вывод.

  1.  Рассчитать евклидово расстояние для A,B  и  B,C. Сделать вывод.

  1.  Рассчитать расстояние Танимото для A,B  и  B,C. Сделать вывод.

Задача.

В самолете за каждый лишний сантиметр, выходящий за габариты необходимо заплатить 3 рубля, а за каждый лишний килограмм веса - 4 рубля. Всего у пассажира – тридцать рублей. Функция классификации:

3 × ΔS  +  4  × Δm  ≥  30

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

Варианты:

2 × ΔS  +  3  × Δm  ≥  15

3 × ΔS  +  4  × Δm  ≥  30

4 × ΔS  +  5  × Δm  ≥  50

3 × ΔS  +  2  × Δm  ≥  20

Репрезентативная выборка:

ΔS

Δm

Класс [0,1]

1

1

2

0

2

5

6

1

Результаты  принятия решения службой контроля багажа сводятся в таблицу

ΔS

Δm

Результаты классификации с использованием различных метрик

cos 0

cos 1

Ре 0

Ре 1

Рт 0

Рт 1

11

12

13

  1.  Составить репрезентативную обучающую последовательность из 10 экспериментов + 3 «контрольных выстрела».
  2.  Отобразить их графически.
  3.  Решить задачу классификации методом сравнения с эталоном, различными метриками (направляющие косинусы, евклидово расстояние, расстояние Танимото). Оценить распознающую (классификация признаков, попадающих в тренировочную выборку) и обобщающую (классификацию новых признаков) способность классификатора. В качестве эталона можно использовать центр масс множества точек (среднее значение).
  4.  Решить задачу методом k-ближайших соседей, используя те же метрики.
  5.  Сделать выводы.

Примечание: в выводе необходимо отразить, насколько качество классификации зависит от различных факторов:

  1.  от обучающей выборки.
  2.  от качества обучения
  3.  от модели
  4.  от состава информативных признаков

В отчёте:

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

Таблицы с решениями задач классификации.

Выводы.


 

А также другие работы, которые могут Вас заинтересовать

37545. ОСНОВЫ ФИЛОСОФСКИХ ЗНАНИЙ. Учебно-методическое пособие 792 KB
  Природа человека и смысл его существования 104 Тема 14. В современном представлении философией называется область теоретических знаний о мире в целом о месте человека в нем и о принципах взаимоотношения человека с миром. Мировоззрение – это целостный взгляд на мир и место в нем человека. В его структуру входят: знания о мире; ценности с позиций которых человек осмысливает мир; убеждения и идеалы которые определяют поступки человека.
37546. ФІЛОСОФІЯ. МЕТОДИЧНІ ВКАЗІВКИ ДО ПРАКТИЧНИХ ЗАНЯТЬ 414 KB
  Написание рефератов по философии. Методические указания определяются рабочей программой конспектом лекций и дополнительно снабжаются краткой версией полнотекстовой базой данных философских источников кафедры психологии философии и образовательных технологий. Самостоятельное изучение курса философии базируется на принципах личного поиска исходя из мировоззрения личности и одновременно предметности освоения своей специальности будущими учеными. Для сохранения диалектической природы философии в предложенных для самостоятельного чтения...
37548. КУРС ФИЛОСОФИИ В ТАБЛИЦАХ 48.16 KB
  Философия о человеке Историческая эпоха философии Что такое человек Античность Микрокосмос Душа тело Душа есть проявление идеи Платон Душа это форма человека Аристотель Средние века Духовность душа тело; духовность есть связь человека с Богом посредством веры любви надежды совести Новое время Существо разумное и действующее по законам разума Локк Кант Проявление общественных отношений Маркс Существо волевое и страстное Ницше ХХ в. Философия об обществе Историческая эпоха философии Что такое общество Античность...
37550. Возникновение и история развития проблемы защиты информации 762.5 KB
  Возникновение и история развития проблемы защиты информации Проблема зашиты информации вообще говоря имеет многовековую историю. Применение же специальных мер в целях сохранения информации в тайне практиковалось еще в древние времена: достоверно например известно что выдающийся политический деятель и полководец древнего Рима Цезарь использовал для этих целей криптографическое преобразование текстов сообщений вошедшее в историю под названием шифра Цезаря хотя по современным представлениям и весьма примитивное. Но поскольку здесь...
37551. Обществознание. Человек в мире человека 746.5 KB
  Значимость вопроса к чему может привести человека безудержное развитие техники настолько велика что в настоящее время эта отрасль человеческой деятельности стала едва ли не главной проблемой понимания нашей ситуации. Антропогенная цивилизациябазируется на утверждении человека основной ценностью функционирования общества в целом и отдельных его подси стем. Необходимо проанализировать предпосылки становления нового типа цивилизации выделив из числа важнейших следующие: эрозия ценностей техногенной цивилизации исходящих из культа силы как...
37552. Таможенная экспертиза минеральных вод импортного происхождения реализуемых на территории Российской Федерации 205.5 KB
  Изучить ассортимент минеральной воды реализуемой в торговой сети города Троицка; оценить качество минеральной воды, реализуемой в торговой сети г. Троицка, по органолептическим показателям; установить оптимальное соотношение цены и качества; Установить код ТНВЭД и характеристику минеральной воды по ТН ВЭД РФ. на заключительном этапе проанализировать результаты проведенных исследований, сделать выводы по всем разделам курсовой работы.