Математические методы распознавания образов (курс лекций, А.Е. Лепский, А.Г. Броневич)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Литература)
(Разбиение класса на кластеры (обучающее векторное квантование))
Строка 27: Строка 27:
# Способы определения расстояния между вектором-образом и классом.
# Способы определения расстояния между вектором-образом и классом.
-
=== Разбиение класса на кластеры (обучающее векторное квантование) ===
+
=== Разбиение класса на кластеры ===
# Постановка [[кластеризация|задачи кластеризации]].
# Постановка [[кластеризация|задачи кластеризации]].
# [[Алгоритм k-средних|Алгоритм k-внутригрупповых средних (k-means)]].
# [[Алгоритм k-средних|Алгоритм k-внутригрупповых средних (k-means)]].

Версия 20:44, 7 августа 2009

Математические методы распознавания образов — односеместровый курс лекций, читаемый студентам 4-го курса факультета естественно-научного и гуманитарного образования специальности 010200 «Прикладная математика и информатика» Таганрогского Технологического института Южного федерального университета. Основная цель курса — формирование, прежде всего, математических знаний и навыков по основным разделам теории распознавания образов, привитие навыков разработки детерминистских и стохастических систем распознавания, нейронных сетей, развитие интуиции студентов для лучшего понимания основных идей, лежащих за этими методами.

Авторы курса — А. Е. Лепский, А. Г. Броневич.

Лабораторные работы разработаны А. Е. Лепским, А. В. Гончаровым.

Содержание

Лекции. Часть I. Детерминистский подход в теории распознавания образов

Предмет распознавания образов

  1. Основные задачи теории распознавания образов.
  2. Типы характеристик образов.
  3. Типы систем распознавания.
  4. Математическая постановка задач распознавания. Распознавание как некорректная задача.

Классификация с помощью решающих функций

  1. Понятие решающих функций.
  2. Линейные решающие функции (ЛРФ).
  3. Общий подход к нахождению линейных решающих функций. Алгоритм Хо-Кашьяпа.
  4. Обобщенные решающие функции (ОРФ).
  5. Задача понижения размерности.

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

  1. Способы стандартизации признаков и векторов-образов.
  2. Способы измерения расстояний между векторами признаков.
  3. Способы определения расстояния между вектором-образом и классом.

Разбиение класса на кластеры

  1. Постановка задачи кластеризации.
  2. Алгоритм k-внутригрупповых средних (k-means).
  3. Алгоритмы расстановки центров кластеров.
    • Алгоритм простейшей расстановки центров кластеров.
    • Алгоритм, основанный на методе просеивания.
    • Алгоритм максиминного расстояния.
    • Алгоритм ИСОМАД (ISODATA).

Метод (машина) опорных векторов

  1. Линейно разделимый случай.
  2. Линейно неразделимый случай.

Нейронные сети и проблемы распознавания

  1. Понятие персептрона.
    • Алгоритм обучения персептрона.
    • Сходимость алгоритма персептрона.
    • Алгоритм обучения слоя персептронов разделению нескольких классов.
  2. Идеология нейроинформатики.
  3. Элементы нейронных сетей.
  4. Архитектуры нейронных сетей.
  5. Математические возможности нейронных сетей.
  6. Базовые математические задачи, решаемые нейронными сетями.
  7. Основные алгоритмы обучения нейронных сетей.

Метод потенциальных функций

Лекции. Часть II. Статистический подход в теории распознавания образов

Вероятностные характеристики среды распознавания и основные задачи статистической теории распознавания образов

Байесовский классификатор

  1. Постановка задачи байесовской классификации
  2. Простейший байесовский классификатор
  3. Отклонение величины средней ошибки неправильной классификации от наименьшей при небайесовской классификации
  4. Обобщенный байесовский классификатор

Минимаксный критерий классификации

Критерий Неймана-Пирсона

Критерии классификации в случае нормального распределения признаков в каждом классе

  1. Критерии классификации в случае нормального одномерного распределения признаков
    • Байесовская классификация
    • Минимаксный классификатор
    • Классификатор Неймана-Пирсона
  2. Классификация в случае многомерного нормального распределения признаков в классах
    • Многомерное нормальное распределение
    • Байесовский классификатор для нормального многомерного распределения признаков в классах
    • Вероятности ошибки неправильной классификации в случае байесовского классификатора для нормального распределения признаков в классах

Статистическое оценивание вероятностных характеристик

  1. Параметрическое оценивание вероятностного распределения
  2. Непараметрические методы оценивания
    • Гистограммный метод оценивания
    • Адаптивный гистограммный метод оценивания
    • Методы локального оценивания
    • Метод оценивания с помощью аппроксимации функции плотности

Приложения

  1. Нахождения дискриминантной функции по прецедентам методом потенциальных функций
  2. Построение байесовского классификатора по выборке двумерных нормально распределенных векторов
  3. Построение гистограмм функций плотности распределения
  4. Построение байесовского классификатора по прецедентам

Литература

скачать курс лекций (3.8 Mb, PDF)

скачать презентацию к курсу лекций, часть 1 (4.3 Mb, PDF)

скачать презентацию к курсу лекций, часть 2 (1.5 Mb, PDF)

Лабораторные работы

В качестве основной вычислительной среды для проведения лабораторных работ используется MatLab. Предлагаются к выполнению следующие лабораторные работы:

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

Методические указания к практическим и лабораторным занятиям скачать (PDF)

Индивидуальные задания

В рамках курса предусмотрено выполнение индивидуальных заданий. Необходимо предложить решение одной из сформулированных ниже задач и осуществить программную реализацию предложенных методов. По результатам проделанной работы нужно составить отчет, в котором необходимо обосновать выбор метода решения задачи, а также провести исследование предложенных методов по следующим критериям: качество работы, требования к вычислительным ресурсам, скорость работы, область применимости. Отчет также должен содержать четкую математическую постановку решаемой задачи, краткий обзор (1 — 2 с.) существующих подходов к решению этой задачи, описание предложенных алгоритмов и методов, листинг программы (с комментариями), список используемой литературы. Предлагаемые к решению задачи по характеру анализируемой информации разделены на группы (текст, звук, изображения). Кроме перечисленных ниже задач, можно предложить свою задачу, при этом необходимо обосновать ее актуальность.

Текст

1. Система классификации текстов по жанрам (поэзия, роман, фантастика и т.п.)

Крупный книжный интернет-магазин решил привлечь новых покупателей за счет размещения на своем сайте удобного рубрикатора книжных произведений. При этом выяснилось, что для 70% книг отсутствует информация о жанре произведения, что не позволяет их добавить в пользовательский рубрикатор, а следовательно снижает уровень продаж. Поскольку в ассортименте интернет-магазина находится более 100 000 наименований, руководство магазина отказалось от ручной классификации книг и обратилось к Вам с просьбой разработать метод, позволяющий автоматически классифицировать книги. О книгах доступна следующая информация: изображение обложки, имена авторов, название книги, год издания, аннотация и текст первых 20-30 страниц с сохранением оригинального форматирования. Необходимо предложить метод, позволяющий на основании доступной информации автоматически классифицировать книги. Кроме того, предложить способ визуализации рубрикатора.

2.Система проверки авторства литературных произведений

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

3. Построение рекомендующей системы для литературных произведений

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

4. Система выявление плагиата в текстовых документах

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

5. Система выявления плагиата в текстах программ

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

Звук

6. Разработка системы поиска нечетких дубликатов

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

7. Разработка системы навигации по большим музыкальным коллекциям

Крупный производитель mp3-плееров решил порадовать своих покупателей интеллектуальными возможностями очередной новинки. Планируемый объем памяти новинки превышает 100 ГБ, таким образом, остро встает проблема навигации по музыкальным коллекциям и поиска нужного произведения. Вам необходимо разработать метод визуализации музыкальных коллекций, а также разработать процедуру формирования списков произведения по запросу пользователя.

8. Разработка рекомендующей системы музыкальных произведений

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

Изображения

9. Классификация изображений по жанрам

Популярный интернет-сервис планирует ввести новую систему навигации по коллекции изображений. Основная идея предлагаемой системы навигации заключается в разделении некоторой области на подобласти, соответствующие тематикам изображений. Технический отдел компании обратился к Вам с просьбой разработать соответствующий алгоритм кластеризации изображений по жанрам. Для разработки метода кластеризации Вам предоставлена часть коллекции изображений, для которых пользователи добавили описание (тэги). Предложенный способ кластеризации должен удовлетворять следующим требованиям: похожие изображения должны отображаться в близки точки на плоскости навигации, а изображениям из различных жанров должны соответствовать удаленные точки плоскости навигации.

10. Разработка системы поиска нечетких дубликатов изображений

Популярный интернет-сервис для защиты авторских прав своих пользователей решила внедрить поисковую систему, позволяющую отслеживать незаконное появление авторских фотографий в Сети. Как правило, ворованные фотографии подвергаются некоторой обработке — масштабированию, изменению гаммы, кадрированию и т.п. Технический отдел компании предложил Вам разработать метод поиска нечетких дубликатов изображений в Сети. Обычной практикой при нахождении незаконного размещения изображения является отправка грозного письма в адрес администрации соответствующего сайта. Ввиду того, что ежедневно более 1000 пользователей обращаются с жалобами на подобное нарушение, необходимо рассмотреть возможность сделать процесс обработки подобных случаев полностью автоматическим. Для оценки такой возможности, нужно рассчитать характеристику поискового алгоритма в терминах полнота/точность.

11. Построение рекомендующей системы изображений

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

12. Поиск изображений по содержанию

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

13. Система извлечения информации из изображений для маркетинговых исследований

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

Ссылки

Личные инструменты