Некоторые методы анализа распределений Q-граммов в задачах классификации данных и приближенного поиска по шаблону

• Автор: Иванко, Евгений Евгеньевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Екатеринбург
• Количество страниц: 125 с. : ил.

* ГЛАВА 1. ОБЗОР ДОСТИЖЕНИЙ В ОБЛАСТЯХ КОНСТРУИРОВАНИЯ ДЕСКРИПТОРОВ ТРЕХМЕРНЫХ ОБЪЕКТОВ И СКОРОСТНОГО ПРИБЛИЖЕННОГО ПОИСКА ПО ШАБЛОНУ В СТРОКАХ
1Л Информационные объекты и дескрипторы
1.2 Обзор некоторых дескрипторов трехмерных объектов
1.3 Краткий обзор роли дескрипторов в некоторых
фундаментальных техниках распознавания образов
1.3Л Статистическая классификация (statistical classification)
1.3.2 Синтаксический (структурный) подход
^ 1.3.3 Нейронные сети
1.3.4 РАМ-алгорнтм
1.4 Расстояние редактирования и ограничения неэмпирических методов приближенного поиска, основанных на расчете расстояния редактирования
1.5 Эмпирики семейства BLAST
1.6 Метод block-distance («блочного расстояния»)
1.7 Анализ распределений д-граммов
1.8 Выводы
ГЛАВА 2. q-ГРАММ СТАТИСТИЧЕСИКЕ ПОДХОДЫ В
* КОНСТРУИРОВАНИИ ДЕСКРИПТОРОВ И ПРИБЛИЖЕННОМ
* ПОИСКЕ В СТРОКАХ
2.1.1 Дескриптор DQG, отражающий распределение я-мерных g-граммов
2.1.2 Дескриптор QSN, отражающий распределение совместных появлений пар п-мерных g-граммов
2.2.1 Алгоритм q-AS (q-gram Approximate Searching / ф q-грамм приближенный поиск)

2.2.2 Модели строк и искажений в строках, используемые при
ф выборе параметров алгоритма q-AS
2.2.3 q-Subword complexity (сложность по подстрокам длины q) случайных строк
* 2.2.4 Упрощенный алгоритм выбора параметров Алгоритма q-AS
2.2.5 Особенности и перспективы Алгоритма q-AS
2.2.6 Выводы
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
3.1.1 Качественные эксперименты по применению дескрипторов DQG и QSN в задачах кластеризации данных
3.1.2 DQG-дескриптор для 3D объектов
® 3.1.3 Сравнительный benchmark-тест PSB-2004
3.1.4 Количественные эксперименты по применению дескриптора

DQG в задачах классификации 3D объектов
3.2.1 Экспериментальное исследование методов выбора параметров для Алгоритма q-AS
3.2.2 Эксперименты по применению Алгоритма q-AS
3.2.3 Сравнение Алгоритма q-AS с эмпирической системой приближенного поиска BLAST
3.3 Выводы
^ ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. ВАЗОВАЯ КЛАССИФИКАЦИЯ В PSB-2004
ПРИЛОЖЕНИЕ 2. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ 2-GR ДЕСКРИПТОРА С ПОМОЩЬЮ
СИСТЕМЫ ТЕСТОВ PSB-2004
ПРИЛОЖЕНИЕ 3. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ ФОРМУЛЫ ДЛЯ СРЕДНЕГО КОЛИЧЕСТВА РАЗЛИЧНЫХ ПОДСТРОК ЗАДАННОЙ ДЛИНЫ В ХАОТИЧЕСКИХ СТРОКАХ ФИКСИРОВАННОЙ ДЛИНЫ НАД КОНЕЧНЫМ АЛФАВИТОМ.... 118 ПРИЛОЖЕНИЕ 4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ ПО ПРИБЛИЖЕННОМУ ПОИСКУ В НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЯХ С ПОМОЩЬЮ
АЛГОРИТМА Q-AS

Автоматическое (машинное) распознавание, описание, классификация и группировка образов - это важные задачи в целом ряде инженерных и научных дисциплин, таких как искусственный интеллект и робототехника, биология, психология, медицина, экономика.
Интерес к распознаванию образов существенно возрос за последние десять лет. Исследования в этой области стимулируются возникновением большого числа интересных, важных и сложных прикладных задач. Среди таких задач можно назвать: поиск в некоторых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности (data mining), классификация документов, финансовое прогнозирование, организация и обработка баз данных мультимедиа объектов, биометрика. В таблице 1 перечислены некоторые важные области применения технологий распознавания образов.
Проблемная область Приложен ИИ Входные образы Классы образов
Биоинформатика Анализ ДНК и РНК I юсл едо вате л ы юстей Последовательности ДНК и РНК Известные гены
Data mining Поиск значимой информации Точки в мног омерном пространстве Разделенные кластеры
Классификация документов Поиск в сети Интернет Текстовый файл Семантические области (напр.наука, искусство, спорт)
Автоматика 11роверка печатных плат Изображения плат Годна/брак
Поиск в БД мультимедиа- объектов Поиск в Интернете Видео, аудио, изображение Жанр
Биометрика Идентификация личности Изображение лица, сетчатки глаза, паппилярного узора Отнесение к группе допуска
Распознавание речи Управление автоматикой с помощью речи Запись звуковой волны Произнесенные слова
Аэрофотосъемка Автоматическое картографирование Фотография Опознанные объекты па фотографии
Таб.1. Сводная таблица некоторых областей применения методов распознавания образов [34].

информационном объекте / Согласно Алгоритму увеличение функции К"' должно проводиться для каждой пары Количество возможных

точек вхождения для /" составит ]~[ (Л', -
увеличение функции К"' будет проводиться У =(2/71 + 1)"]""] (/V,-(у+ 1) раз

каждом увеличении требуется находить ту ячейку ассоциативного массива, хранящего функцию К№, значение в которой необходимо увеличить. Всего
ассоциативный массив содержит не более |л|ч —1^/2 ячеек,
следовательно, процесс поиска нужной ячейки займет не более
1одг[Ач И" —71/2] операций. В итоге порядок временной сложности
составит с|/<-/уЦ|л|Л' j • (2т +1)" П Ы, - ц +1J. #
Следствие Аналогично Следствию Теоремы 1, при условии, что величины ц и т не превосходят 10, размер алфавита А и размерность п областей определения информационных объектов фиксированы, временная сложность и порядок требуемой памяти Алгоритма зависят только от размеров
области определения информационного объекта. В этом случае выражения
Теоремы 2 примут следующий вид: порядок памяти о 1с^2[ ]"[А( ] ] и временная сложность: О р| А,
Пусть заданы два информационных объекта
/,:{1...А|}х...х{1 А'} -> А и /2 :{1 А|2}х...х{1 А2}->/ , обозначим
п п
N] = ]_]У' ’ М2 = ГК • Пусть далее с помощью Алгоритма 2.2 получены