42725

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

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

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

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

Русский

2013-10-30

732 KB

18 чел.

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

В отчёте:

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

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

Выводы.


 

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

58494. Дидактические игры на уроках французского языка 467.5 KB
  Ход работы: ученику предлагается конверт с разрезанной внутри картинкой, на одной стороне которой изображен вид спорта, игры, действия или спортивного сооружения, а на другой – его графическое написание с транскрипцией.
58496. Робинзон Крузо Даниэля Дефо. Урок французского языка 467 KB
  В уроке приведен достаточно сложный с точки зрения грамматики и лексики текст для 7 класса. Необходимо изменить его согласно уровню класса либо предложить другой текст. Составьте словарь по тексту, чтобы легче было работать при первом прочтении на уроке.
58497. УРОК ГЕОГРАФИИ 27.5 KB
  Учитель Ребята сегодня мы будем проходить новую тему Франция. Учитель Ну и куда ты собралась на лето Где отдыхать будешь Иванова Как обычно у бабушки в одной из четырёх Франций которым по площади равна наша Московская область.
58498. Урок-путешествие «По следам Робинзона» 34.5 KB
  Озвучивается тема урока по следам Робинзона Крузо Задумывались ли вы когданибудь над тем существовал ли Робинзон Крузо этот мужественный герой в действительности и если да то где расположен его остров Дети высказывают предположения.
58499. Принципы, этапы контролируемой чистки. Способы мотивации пациента 51 KB
  Для мотивации пациента кабинет гигиены и профилактики предполагает обязательное наличие умывальника, зеркала и специальных средств, предназначенных для информирования пациентов...
58501. Весільні обряди в усній народній творчості. Веснянки, гаївки, заклички 40.5 KB
  Діти: Стрітення. Діти вибігали на вулицю і співали: Пташок викликаю З теплого краю. Ідіть діти і здоровте хлібом людей. Хто з вас знає які заклички Діти відповідають: Прийди до нас весно Із радістю із великою до нас милістю Із житом зернистим Із пшеницею золотою І вівсом кучерявим.
58502. Урок – гра «О, математик!» 45.5 KB
  Який гвіздок міцніше тримається у дерев’яній стіні (важче витягти із стіни) – круглий, квадратний чи трикутний, якщо їх забивають на одну глибину і площі їх поперечного перерізу рівні? (Трикутний, він має більшу бічну поверхню)