42725

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

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

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

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

Русский

2013-10-30

732 KB

20 чел.

Лабораторная работа №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.  от состава информативных признаков

В отчёте:

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

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

Выводы.


 

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

48691. Двухцепная линия электропередачи 110-220 кВ (дистанционная и токовые защиты) 676.5 KB
  Ульянова Электроэнергетический факультет Кафедра ТОЭ Курсовой проект Двухцепная линия электропередачи 110220 кВ дистанционная и токовые защиты Выполнил студент группы ЭЭ2104 Гордеев А. Чебоксары 2008 Содержание Тип и основные параметры элемента защиты Расчет отпаек Расчёт защиты элемента сети Выбор защиты линии
48693. Прикладная алгебра 2 MB
  Понятие группы, подгруппы, факторгруппы, индекса группы по подгруппе. Теорема Лагранжа. Понятие поля. Построение конечных полей с помощью неприводимых многочленов (привести пример). Полиномиальное и степенное представление элементов поля.
48694. Разработка аналого-цифровых преобразователей (АЦП) 1.55 MB
  Преобразователь использует конвейерную девяти каскадную архитектуру с полностью дифференциальными аналоговыми схемами и имеет отношение сигнал шум и искажения SNDR 60 дБ при полномасштабном входном сигнале частотой 5 МГц.1 Блоксхема конвейерных АЦП. 1 показана общая блоксхема конвейерных АЦП с k каскадами. Такая схема и будет использоваться в нашей курсовой работе.
48695. Система народного образования 50.8 KB
  Только в нашей стране впервые в мире выдвинута задача введения всеобщего обязательного среднего образования высокого уровня, дающего молодежи возможность получения на этой базе специального образования, приобретения рабочей квалификации или продолжения обучения
48696. Описать структуру с именем TRAIN 746.5 KB
  Алгоритм функции print_str представлен на рисунке Алгоритм функции input_str представлен на рисунке Алгоритм функции print_str представлен на рисунке 2. Рисунок 2 Алгоритм функции input_str представлен на рисунке 3.
48697. Изготовление детали «Упор» 1.03 MB
  Прокат в металлургии – это продукция, получаемая на прокатных станках путём прокатки. Прокатывается металл, полученный на предыдущей стадии обработки металла – литьё. Обычно его называют «прокат металла» или «металлопрокат».
48698. Практическое использование возможностей MS WORD и EXCEL 724.5 KB
  Изучение операционной системы Windows, компонентов MS Word и Excel и получение практических навыков работы с современными информационными технологиями. Получение представления о формировании табличной базы данных и о возможностях при работе с ней на примере базы данных в MS Excel.
48699. Следящая система управления зеркалом телескопа 12.3 MB
  Задачей данной курсовой работы является введение в основы проектирования системы автоматического регулирования. На основе следящей системы работают многие системы управления например телескопа радиолокационной антенны зенитного орудия и т. минВ Коэффициент усиления ЭМУ КЭМУ = 7 Коэффициент передачи сельсинов Кс = 076 В град Коэффициент передачи редуктора Кр = 0075 Добротность системы определяется численными значениями оценок: Максимальная скорость слежения Umx = 9 град с Максимальная...