Распознавание образов. Начальный курс теории
Покупка
Новинка
Основная коллекция
Тематика:
Математическое моделирование
Издательство:
НИЦ ИНФРА-М
Автор:
Бондаренко Наталья Сергеевна
Год издания: 2025
Кол-во страниц: 185
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Магистратура
ISBN: 978-5-16-019365-6
ISBN-онлайн: 978-5-16-112028-6
DOI:
10.12737/2111834
Артикул: 813118.01.01
В данном учебном пособии рассмотрены задачи распознавания образов, дискриминантного анализа, таксономии, сравнения с эталоном, классификации признаков, выбора признакового пространства. Изучены основные группы признаков, рассчитываемых по изображениям и используемых для их распознавания. Освещены способы классификации на основе сравнения с эталоном, байесовского классификатора и деревьев принятия решений.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Для студентов, обучающихся в области информационных технологий, прикладной математики и программной инженерии.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Магистратура
- 09.04.01: Информатика и вычислительная техника
- 09.04.02: Информационные системы и технологии
- 09.04.03: Прикладная информатика
- 09.04.04: Программная инженерия
- ВО - Специалитет
- 09.05.01: Применение и эксплуатация автоматизированных систем специального назначения
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Н.С. БОНДАРЕНКО РАСПОЗНАВАНИЕ ОБРАЗОВ. НАЧАЛЬНЫЙ КУРС ТЕОРИИ УЧЕБНОЕ ПОСОБИЕ Москва ИНФРА-М 2025
УДК 004.93(075.8) ББК 16.63я73 Б81 Бондаренко Н.С. Б81 Распознавание образов. Начальный курс теории : учебное пособие / Н.С. Бондаренко. — Москва : ИНФРА-М, 2025. — 185 с. — (Высшее образование). — DOI 10.12737/2111834. ISBN 978-5-16-019365-6 (print) ISBN 978-5-16-112028-6 (online) В данном учебном пособии рассмотрены задачи распознавания образов, дискриминантного анализа, таксономии, сравнения с эталоном, классификации признаков, выбора признакового пространства. Изучены основные группы признаков, рассчитываемых по изображениям и используемых для их распознавания. Освещены способы классификации на основе сравнения с эталоном, байесовского классификатора и деревьев принятия решений. Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения. Для студентов, обучающихся в области информационных технологий, прикладной математики и программной инженерии. УДК 004.93(075.8) ББК 16.63я73 Данная книга доступна в цветном исполнении в электронно-библиотечной системе Znanium ISBN 978-5-16-019365-6 (print) ISBN 978-5-16-112028-6 (online) © Бондаренко Н.С., 2024
Список принятых сокращений БД — база данных ИНС — искусственная нейронная сеть КНП — кратчайший незамкнутый путь ЛДФ — линейная дискриминантная функция МНК — метод наименьших квадратов ПНС — полносвязная нейронная сеть CART — Classification and Regression Tree FOREL — Formal Element ID3 — Identify an MP3 MNIST — Modified National Institute of Standards and Technology 3
Введение Учебное пособие написано на основе преподавания автором дисциплины «Распознавание образов» в ФГБОУ ВО «Донецкий государственный университет». В частности, материалы пособия использовались при обучении данной дисциплине в дистанционном режиме. Целью пособия является ознакомление студентов с базовыми понятиями теории распознавания образов и дискриминантного анализа, основными алгоритмами классификации и таксономии, а также с деревьями принятия решений. Актуальность решения задач распознавания образов подтверждается массой различных применений, например в военном деле, системах безопасности, оцифровке сигналов и т.п. На текущий момент задача распознавания образов в общей постановке не решена, но существует значительное количество программного кода, который решает частные случаи этой задачи. Таким образом, задача распознавания образов является эвристической1, по это му каждый исследователь вынужден искать свой подход, например использовать ИНС, фильтрацию изображений и т.п. Проблема распознавания образов приобретает огромное значение именно в наше время, в условиях информационных перегрузок. С ростом автоматизации систем управления и обработки информации и систем принятия решений возникла необходимость обеспечить работу многих технологических процессов без участия человека. Главным образом речь идет о процессах, связанных с рутинной, однообразной работой. Помимо этого, применение распознающих систем, работа которых основывается на цифровой обработке данных, обусловлена тем, что в ряде ситуаций человек вообще не в состоянии решить поставленную задачу с требуемыми скоростью и качеством. В качестве примера подобной ситуации можно указать противо ракетный маневр самолета в сложных метеоусловиях. При изучении дисциплины «Распознавание образов» студенты сталкиваются с тем, что учебный материал разбросан по разным ли1 Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи. Позволяет ускорить решение задачи в тех случаях, когда точное решение не может быть найдено. 4
тературным источникам, примеры и упражнения в этих источниках отсутствуют, а теоретический материал изложен языком, трудным для понимания. Предполагается, что данное учебное пособие компенсирует недостаток учебной литературы в области распознавания образов. Каждая глава пособия включает теоретический материал, при необходимости содержащий описание методики решения задач, а также демонстрационные примеры. В конце каждой главы приводятся упражнения, тестовые задания и вопросы для самоконтроля. Учебное пособие состоит из введения, девяти глав, заключения и библиографического списка. В первой главе выполнена общая постановка задачи распознавания образов; рассмотрены вектор признаков и модель изображения; изучено применение ИНС в распознавании образов на примере как полносвязных, так и сверточных нейронных сетей. Во второй главе приводится постановка задачи дискриминантного анализа для двух и k образов. Обсуждается вопрос соотношения между данными задачами. Третья глава знакомит читателей с алгоритмами кластеризации и моделью таксономии. Вводится понятие функции расстояния, рассматриваются наиболее часто используемые метрики. Приводится постановка задач кластеризации и таксономии, описывается алгоритм таксономии FOREL. Изучается классификация алгоритмов кластеризации. Четвертая глава посвящена рассмотрению признаков, используемых при распознавании изображений. Особое внимание уделено цепным кодам как примеру геометрических признаков, а также применению операции свертки к изображениям. В пятой главе рассматривается задача сравнения с эталоном применительно к словам. К основным понятиям в рамках данной задачи относятся мера близости двух слов, расстояние Левенштейна и редакционное предписание. В шестой главе приводятся минимально необходимые теоретические сведения, касающиеся наивного байесовского классификатора. В качестве примера рассмотрена задача классификации текстов. Изучены частные случаи байесовского классификатора — многомерный и мультиномиальный. Седьмая глава посвящена изложению базовых понятий, связанных с деревьями принятия решений, рассмотрению их типов и процесса конструирования деревьев решений, в частности алгоритмов CART и ID3. 5
В восьмой главе изучены основные положения линейного дискриминантного анализа: приведена постановка соответствующей задачи, значительное внимание уделено выбору признакового пространства и линейному классификатору. В девятой главе вводится понятие комитетов системы множеств и неравенств. Рассмотрены примеры различных комитетных конструкций. Пособие соответствует рабочей программе учебной дисциплины «Распознавание образов», преподаваемой во втором семестре магистратуры направления подготовки 09.03.04 «Программная инженерия» факультета математики и информационных технологий ФГБОУ ВО «ДонГУ». Данная дисциплина относится к вариативной части образовательной программы; она включает 17 часов лекций, 17 часов практических занятий, 34 часа лабораторных занятий и 148 часов самостоятельной работы студента. Учебное пособие ориентировано на студентов, которые обучаются в области информационных технологий, прикладной математики и программной инженерии, а также на широкий круг читателей, желающих ознакомиться с основными понятиями дисциплины «Распознавание образов». В результате изучения учебной дисциплины «Распознавание образов» студент будет: знать • принципы постановки задачи распознавания образов; • как применять искусственные нейронные сети (ИНС) в задачах распознавания образов; • принципы постановки задачи дискриминантного анализа для двух и k образов; • принципы постановки задачи таксономии и основы алгоритма FOREL для ее решения; • классификацию признаков, используемых при распознавании изображений; • способы классификации слов на основе сравнения с эталоном; • теоретические сведения о наивном байесовском классификаторе; • определение и основы конструирования дерева решений; • основные понятия линейного дискриминантного анализа; • комитетные методы решения задач распознавания; уметь • выполнять грамотную постановку задач, связанных с распознаванием образов, в частности возникающих при обработке изображений с использованием компьютерных систем; 6
• разрабатывать алгоритмы решения поставленных задач на основе наиболее подходящих подходов; • выполнять формализованное описание поставленных задач и алгоритмов их решения; • реализовывать разработанные алгоритмы с использованием языков программирования; владеть • математическим и алгоритмическим аппаратом, применяемым при решении задач распознавания. 7
Глава 1. ЗАДАЧА РАСПОЗНАВАНИЯ ОБРАЗОВ 1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ. ПРИМЕРЫ ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ Под образом будем понимать множество всех объектов (предметов, процессов, явлений, ситуаций, сигналов), сходных друг с другом в некотором фиксированном отношении. Распознать образ объекта — значит указать, к какому образу (классу похожих объектов) он относится. Задача распознавания образов — это задача описания и классификации (узнавания, диагностики) объектов той или иной природы; задача выработки понятия о классе объектов. Одна из постановок задачи распознавания образов состоит в целесообразном разбиении заданной совокупности объектов на однородные классы. Объекты, вошедшие в один класс, должны быть «похожи» друг на друга или близки друг к другу по некоторому критерию «похожести» или близости. Объекты же из разных классов должны быть различными, достаточно далекими друг от друга. Рассмотрим примеры некоторых задач распознавания: 1) узнавание объектов — отнесение их к классу сходных объектов, например «буквы», «цифры», «птицы», «кошки» и т.п.; 2) медицинская диагностика, в рамках которой классами могут являться определенные заболевания; 3) техническая диагностика, позволяющая определить тип неисправности сложной технической системы; 4) классификация в биологии, в рамках которой осуществляется иерархическое разбиение живых объектов на классы; 5) классификация в социологии, предполагающая разделение определенной группы населения на однородные в каком-либо отношении подгруппы и выделение типопредставителей в каждой из них; 6) типология систем, представляющая собой обобщение задач предыдущих пунктов: некоторый класс систем требуется разбить на однородные группы с выделением типопредставителей в каждой группе; 8
7) классификация и диагностика ситуаций, в рамках которых необходимо распознать тип ситуации и принять соответствующее заранее заготовленное для этой ситуации решение. Например, к данной задаче относится распознавание производственных ситуаций диспетчером, управляющим некоторым технологическим процессом; 8) разбиение пространства. Пусть М и N — выпуклые непересекающиеся многогранные множества в пространстве . n Необходимо найти полупространство n P ⊂ такое, чтобы: , P M ⊃ . P N = ∅ ∩ Это полупространство определяет разбиение n на два класса: Р или \ . n P Подобная задача имеет многочисленные важные применения, в частности в математической экономике. 1.2. ВЕКТОР ПРИЗНАКОВ В ряде случаев под образом целесообразно понимать структурированное описание изучаемого объекта или явления, представленное вектором признаков ( ) 1,..., , n x = ξ ξ (1.1) где i ξ — вещественные числа, интерпретируемые как значения параметров или признаков объекта, i = 1, …, n. Очевидно, что ( ) 1,..., n x = ξ ξ есть вектор пространства . n Поэтому к нему применимы операции сложения векторов, умножения вектора на скаляр, а также скалярного произведения двух векторов. Скалярное произведение векторов , n x y ∈ будем обозначать через ( ) , . x y Пример 1.1. Пусть в качестве объекта выступает яблоко. Обозначим: 1 ξ — высота яблока, см; 2 ξ — диаметр в средней части, см; 3 ξ — вес, кг; 4 ξ — содержание железа, %; 5 ξ — длина плодоножки, см. Тогда вектор признаков в соответствии с (1.1) имеет вид ( ) 5 1 5 ,..., . x = ξ ξ ∈ 9
1.3. МОДЕЛЬ ИЗОБРАЖЕНИЯ Чтобы представить двумерное изображение в виде n-мерного вектора (1.1), представляющего собой модель изображения, нужно: 1) разбить область изображения на элементарные ячейки — прямоугольники; 2) просмотреть эти элемен ты строка за строкой слева направо и сверху вниз; 3) в качестве і-й координаты вектора записать 1, если в і-ю ячейку попал элемент изображения, иначе записать 0. Пример. Составим модель изображения, представленного на рис. 1.1. С этой целью разобьем область изображения на девять элементарных ячеек (по три ячейки по горизонтали и вертикали). Пронумеруем данные ячейки слева направо и сверху вниз. Из рисунка видно, что элемен ты изображения попали во все ячейки, кроме пятой. Поэтому все координаты вектора признаков будут равны 1, кроме пятой, которая равна 0: ( ) 1,1,1,1, 0,1,1,1,1 . x = 1 2 3 4 5 6 7 8 9 Рис. 1.1. Кодирование изображения вектором ( ) 1,1,1,1, 0,1,1,1,1 x = 10