Математическое обеспечение для разработки и анализа систем распознавания образов, использующих рандомизированные алгоритмы

• Автор: Шалымов, Дмитрий Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 126 с. : ил.

Оглавление
Введение

1 Задачи распознавания образов, классификации и кластеризации

1.1 Распознавание образов.

1.2 Формальная постановка задачи

1.3 Примеры задач распознавания образов.

1.3.1 Распознавание слов речи

1.3.2 Распознавание печатных текстов на арабском языке

1.4 Программные средства аналитического ПО

2 Рандомизированные алгоритмы кластеризации

2.1 Алгоритмы кластеризации при известном количестве кластеров

2.2 Состоятельность оценок алгоритма РАСА в задаче распознавания слов речи
2.3 Устойчивость и качество кластеризации.
2.4 Рандомизированный метод определения количества кластеров 7
2.5 Доказательства теорем
3 Программный комплекс для разработки и анализа систем распознавания образов
3.1 Структура программного комплекса.
3.2 Визуализация и снижение размерностиЮС
3.3 Апробация алгоритмов устойчивой кластеризации
Заключение.
Литература


Результаты диссертационной работы были представлены в проекте “Разработка программного комплекса кластерного анализа данных большого объема”, который победил и конкурсе “У. М.Н. И.К. Публикации. Основные результаты диссертации опубликованы в восемнадцати работах. Из них три публикации [,,] в журналах из перечня ВАК. Работы [9-,-,0] написаны в соавторстве. В работах [9—,—] О. Н.Грапичипу принадлежат общие постановки задач, а Д. С.Шалымову - реализации и обоснования описываемых методов, создание демонстрационных примеров и программных средств. В работе [0] Д. С.Шалымов является автором I—VI секций. К.Скрьп'ану принадлежит участие в реализации вычислительного ядра и соавторство в IV секции, посвященной организации его внутренней структуры, Д. Любимову принадлежит участие в создании демонстрационных примеров, проиллюстрированных на рис. Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 6 источников. Текст занимает 6 страниц, содержит рисунка и две таблицы. Во введении обосновывается актуальность тематики диссертационной работы и кратко излагаются сс основные результаты. В первой главе вводятся основные понятия и формальные постанов-ки задач исследований предметной области, дается исторический контекст развития итеративных алгоритмов кластеризации, рассматриваются примеры применения классификации и кластеризации в задачах распознавания образов. В гг. В процессе классификации обнаруживаются признаки, которые характеризуют группы объектов исследуемого набора данных - классы (кластеры). По этим признакам каждый сигнал можно отнести к тому или иному классу. Получающееся разбиение естественным образом характеризует структуру множества данных и может быть исполг/зопапо п дальнейшем для ее определения. В п. С содержательной точки зрения процесс распознавания образов трактуется как классификация входных сигналов х из некоторого множества X, заключающаяся в построении правила сопоставления каждой точке х € X некоторого образа (класса) X(В диссертации для упрощения рассматриваются 'только задачи однозначной классификации, хотя это ограничение и не носит принципиального характера и может быть расширено. Выбор правила классификации порождает разбиение множества X на классы. Будем считать, что правило классификации однозначно определяется конечномерным набором г/ и задана функция l(rj) возвращающая количество классов при классификации по правилу г). Всякий способ классификации г/ связан с потерями, которые обычно характеризуются с помощью штрафных функций стоимости qf:(x,r}) при отнесении точки х к классу с номером к. В типичных случаях, когда X — вещественное векторное пространство, значения штрафных функций qk(xtrj) возрастают при удалении х от центра соответствующего образа (класса). В диссертации рассматривается следующее правило классификации: при заданных 7) и функциях г/'(х, г}), к = 1,. Например, если па X задана норма || • || и в множестве данных I классов, а т/ — набор векторов центров классов: rf = (, ,)> то можно считать = {/,7/} и в качестве qk(x, 7]) можно задать расстояние до центра к-го класса 0k: qk(x,rj) = ||ж — 0h\2. При этом множество X разбивается наI классов Xifa), ^2(),. Хк(л) относятся все точки х, находящиеся к центру вк ближе, чем к любому другому. Интеграл $хк(ц) IIх — ^'И2 определяет рассеяние точек х в подмножестве Хк(г)). Як(х,г))Р(&х). Тогда задача кластеризации множества данных из I классов состоит в определении набора центров т)[, минимизирующего суммарную стоимость разбиения. Задача устойчивой кластеризации является обобщением для случая нахождения заранее неизвестного оптимального значения количества классов и соответствующего набора центров Т)[*. В системах, работающих в режиме реального времени в условиях изменяющейся со временем обстановки, распределение Р(-) очень часто бывает’ неизвестно. Будем предполагать, что в режиме реального времени па вход поступает последователь! Р(-). Требуется предложить алгоритм построения последовательности оценок {г;,,} набора т? Решение задачи дополнительно осложняется тем, что па практике функции & = 1,2,. Г]) = (р{х, V) + к = 1,2,. Г}). В следующем пункте 1.