42725

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

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

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

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

Русский

2013-10-30

732 KB

27 чел.

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

В отчёте:

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

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

Выводы.


 

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

80754. The Verb. The Old English verb 28.59 KB
  The inflection of the verb in the Germanic languages is much simpler than it was in Indo-European times. A comparison of the Old English verb with the verbal inflection of Greek or Latin will show how much has been lost. Old English distinguished only two simple tenses by inflection a present and a past, and, except for one word...
80755. Methods of sentence analysis. Subordination grammar and constitutional grammar 26.75 KB
  The nominative parts of the simple sentence, subject, predicate, object, adverbial, attribute parenthetical enclosure addressing enclosure. The parts are arranged in a hierarchy. The ultimate and highest of this integral modification is the scheme as a whole.
80756. Verb. Morphological classification symantic and structural classification of verbs 28.04 KB
  There are exist finite and non-finite forms of a verb. Non-finite forms or the so called verb its are infinitive, the participle and the gerund. The verb forms differ in their meaning, as function. the finite form them denotes a process.
80757. NOUN. SEMANTIC AND STRUCTURAL CLASSES OF NOUNS 27.98 KB
  The categorical functional properties of the noun are determined by its semantic properties. The most substantive function of the noun is hat of the subject in the sentence. The function of the object in the sentence is also typical of the noun as the substance word.
80758. THE ARTICLE AND ITS STYLISTIC POTENTIAL 27.64 KB
  Newspaper style was the last of all styles of written literary english to be recognized as a specific form of writing standing apart from other forms. Information in the english newspaper is conveyed through the medium of: brief news item, press reports (parlimentary, of court proceeding...
80759. SYNTATICAL EXPRESIVE MEANS AND STYLISTIC DEVISES 27.52 KB
  Within the language as a system there establish themselves certain definite types of relations between words, word-combinations, sentences and also between larger spans of utterances. The term supra-phrasal unit is used to denote larger unit than a sentence.
80760. Synonyms, euphemisms and antonyms 28.96 KB
  Traditional linguistics defines synon. As words of the same category of parts of speech conveying the same concept but differing either in shades of meaning or in stylistic characteristics. A more modern and effective approach to the classification of synonyms may based on the definition describing synonyms as words differing in connotations...
80761. Phraseological Units and the principles of their classification 30 KB
  Phraseological units because they sum up the collective experience of the community.They moralize (Hell is paved with good intentions), give worring If you sing before breakfast, you will worry before night), criticize (Everyone calls his own guse swans).
80762. Object of the Theory of Grammar. Its place among Other Linguistic Sciences 29.78 KB
  Language is social by nature: it is inseparably connected with the people who are its creators users. L. consists of three parts (sides): the phonological system, the lexical system, the grammatical system; without any one of them three is no human L. in the above sense.