Содержание к диссертации
Введение
ГЛАВА 1. Обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках 12
1.1 Информационные объекты и дескрипторы 12
1.2 Обзор некоторых дескрипторов трехмерных объектов 17
1.3 Краткий обзор роли дескрипторов в некоторых фундаментальных техниках распознавания образов 21
1.3.1 Статистическая классификация (statistical classification) 21
1.3.2 Синтаксический (структурный) подход 22
1.3.3 Нейронные сети 23
1.3.4 РАМ-алгоритм 24
1.4 Расстояние редактирования и ограничения неэмпирических методов приближенного поиска, основанных на расчете расстояния редактирования 27
1.5 Эмпирики семейства BLAST 32
1.6 Метод block-distance («блочного расстояния») 35
1.7 Анализ распределений -граммов 39
1.8 Выводы 40
ГЛАВА 2. q-грамм статистичесике подходы в конструировании дескрипторов и приближенном поиске в строках 42
2.1.1 Дескриптор DQG, отражающий распределение /7-мерных -граммов 43
2.1.2 Дескриптор QSN, отражающий распределение совместных появлений пар «-мерных -граммов 47
2.2.1 Алгоритм q-AS (q-gram Approximate Searching/ q-грамм приближенный поиск) 52
2.2.2 Модели строк и искажений в строках, используемые при выборе параметров алгоритма q-AS 58
2.2.3 q-Subword complexity (сложность по подстрокам длины q) случайных строк 66
2.2.4 Упрощенный алгоритм выбора параметров Алгоритма q-AS 70
2.2.5 Особенности и перспективы Алгоритма q-AS 72
2.2.6 Выводы 73
ГЛАВА 3. Экспериментальные исследования 16
3.1.1 Качественные эксперименты по применению дескрипторов DQG и QSN в задачах кластеризации данных 76
3.1.2 DQG-дескриптор для 3D объектов 82
3.1.3 Сравнительный benchmark-тест PSB-2004 84
3.1.4 Количественные эксперименты по применению дескриптора DQG в задачах классификации 3D объектов 87
3.2.1 Экспериментальное исследование методов выбора параметров для Алгоритма q-AS 88
3.2.2 Эксперименты по применению Алгоритма q-AS 91
3.2.3 Сравнение Алгоритма q-AS с эмпирической системой приближенного поиска BLAST 92
3.3 Выводы 94
Заключение 97
Список литературы 102
- Краткий обзор роли дескрипторов в некоторых фундаментальных техниках распознавания образов
- Расстояние редактирования и ограничения неэмпирических методов приближенного поиска, основанных на расчете расстояния редактирования
- Дескриптор QSN, отражающий распределение совместных появлений пар «-мерных -граммов
- Количественные эксперименты по применению дескриптора DQG в задачах классификации 3D объектов
Введение к работе
Автоматическое (машинное) распознавание, описание, классификация и группировка образов - это важные задачи в целом ряде инженерных и научных дисциплин, таких как искусственный интеллект и робототехника, биология, психология, медицина, экономика.
Интерес к распознаванию образов существенно возрос за последние десять лет. Исследования в этой области стимулируются возникновением большого числа интересных, важных и сложных прикладных задач. Среди таких задач можно назвать: поиск в некоторых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности (data mining), классификация документов, финансовое прогнозирование, организация и обработка баз данных мультимедиа объектов, биометрика. В таблице 1 перечислены некоторые важные области применения технологий распознавания образов.
Таб.1. Сводная таблица некоторых областей применения методов распознавания образов [34].
Обзор содержания номеров одного из наиболее авторитетных журналов, посвященных распознаванию образов - "IEEE Transactions on Pattern Analysis and Machine Intelligence" показал, что, начиная с 1979 по 2000 год, около 3000 статей было посвящено распознаванию образов [34].
Одним из основных свойств информации представленной в вычислительной машине является дискретность, иными словами информация о распознаваемом объекте представлена в вычислительной машине как множество элементарных информационных единиц - букв или цифр. Одномерные данные записываются в виде конечных последовательностей над конечным алфавитом (сюда можно отнести текст и оцифрованные звукозаписи). Двумерные данные представляются матрицами над конечным числовым множеством (наиболее часто встречающиеся двумерные данные -это двумерные изображения, где значения элементов матриц отражают уровни яркости или цвета соответствующих участков изображения). Трехмерные данные аналогично могут записываться как трехмерные матрицы над конечным множеством чисел (так, например, представляются данные, полученные с помощью 3D сканера; элемент матрицы в этом случае отражает уровень яркости его отсутствие/наличие либо цвет участка пространства).
Существуют многочисленные методы автоматической обработки дискретной машинной информации, в частности в задачах распознавания образов. Для строковых данных одним из распространенных методов является использование подстрок длины q, называемых ^-граммами. В настоящей работе сделана попытка обобщить понятие ^-грамма для двух- и трехмерных данных. Введенное понятие «-мерного ^-грамма используется для конструирования аналогичных строковым методов анализа 2D и 3D графической информации. Примером одномерного ^-грамма может служить связная подстрока длины q строки текстового файла. Одномерные ^-граммы широко применяются при лингвистическом анализе текстов [102], архивации данных [66], в задачах поиска по шаблону в строках [61,63]. Примером
двумерного g-грамма является квадратный участок изображения размером qxq пикселей. Такие структуры используются, например, при анализе текстур и конструировании графических фильтров для изображений [27,35,68].
Несмотря на широкое использование, потенциал методов, связанных с анализом «-мерных ^-граммов, далеко не исчерпан. В данной работе проводится теоретическая разработка и практическая апробация новых эффективных алгоритмов, основанных на анализе распределений «-мерных ^-граммов в информационных объектах. Для исследования были выбраны два крупных класса проблем распознавания образов, являющиеся актуальными на сегодняшний день.
Первый класс проблем связан с применением дескрипторов в задачах сопоставления информационных объектов некоторых типов. Дескриптор здесь - это небольшой по размеру информационный объект, ставящийся в соответствие исходному информационному объекту [32,33,80,81], конструируемый так, чтобы формально выраженная степень схожести двух дескрипторов характеризовала степень схожести двух исходных информационных объектов. Обычно конструирование дескрипторов подчинено идее сокращения времени и памяти, необходимых для определения степени схожести двух информационных объектов. Такой подход часто используется в приложениях, осуществляющих автоматическую классификацию и кластеризацию множеств информационных объектов в условиях жестких ограничений на время сопоставления, либо доступную память. В настоящей работе исследовались дескрипторы, основанные на гистограммах «-мерных ^-граммов и гистограммах совместных появлений пар «-мерных ^-граммов. В ходе работ было проведено как качественное, так и количественное тестирование этих дескрипторов, в результате чего удалось эмпирически найти наиболее эффективную форму дескрипторов для автоматической классификации в ряде актуальных задач.
Задачи второго класса состоят в конструировании алгоритмов приближенного поиска (approximate searching) по шаблону в строках. Основным требованием, предъявляемым к исследуемым алгоритмам, является линейная временная сложность 0(п), где п - длина строки данных в которой осуществляется поиск. На сегодняшний день не существует неэмпирических алгоритмов (при работе которых поставленная задача гарантированно решается) приближенного поиска, имеющих временную сложность лучше, чем О(кп) и не требующих более чем полиномиального времени для предварительной обработки строк и более чем полиномиального размера памяти для хранения информации в процессе поиска по шаблону [53]. Интерес к исследованиям подобного рода продиктован в первую очередь быстрым развитием генетики и возникновением ряда задач скоростного поиска в крупных нуклеотидных последовательностях. Существующие неэмпирические алгоритмы приближенного поиска часто оказываются недостаточно эффективными в приложениях связанных с исследованием генома. В связи с этим в приложениях, использующихся для приближенного поиска в нуклеотидных последовательностях, обычно применяют эмпирические методы, основанные на обнаружении областей вероятного местонахождения шаблона, либо на обнаружении областей, где шаблона вероятно нет. Сужение области поиска ведет к увеличению скорости работы с одной стороны и к появлению неконтролируемых ошибок с другой. В случае задач поиска в нуклеотидных последовательностях такой выход оказывается приемлемым [3].
Кроме требований к скорости работы алгоритмов, биологи предъявляют ряд специфических требований, одно из которых состоит в возможности приближенного поиска в условиях взаимных перестановок небольших частей нуклеотидных последовательностей (intrasequence rearrangements) [47]. Такие перестановки часто встречаются в результате генетической изменчивости, порождая схожие организмы, и представляют интерес для биологов. Существующие методы приближенного поиска не
позволяют удовлетворительно обрабатывать строки, подвергшиеся перестановке подстрок. Причиной тому является неподходящая модель искажений, использующаяся в большинстве современных методов. Обычно единичное искажение строки представляют как операцию редактирования (вставки, удаления или замены символа). При такой модели искажений ставится задача нахождения в строке данных подстроки, которая может быть превращена в шаблонную не более чем заданным количеством операций редактирования. Минимальное количество операций редактирования, требующихся для превращения некоторой строки в шаблон, называется «расстоянием редактирования» [89] между строкой и шаблоном. В рамках описанной модели задача приближенного поиска сводится к поиску подстрок, отличающихся от шаблона не более чем на заданное расстояние редактирования. Искажение в виде перестановки подстрок в строке данных обычно ведет к резкому увеличению расстояния редактирования между участками строки данных, подвергшимися перестановке подстрок и шаблонной строкой. А это, в свою очередь, не позволяет применять описанную идеологию приближенного поиска с точностью до заданного расстояния редактирования.
Изложенные проблемы побудили автора провести исследование методов приближенного поиска, удовлетворяющих двум критериям:
алгоритмическая сложность исследуемого метода должна быть лучше, чем О(кп);
метод должен позволять осуществлять поиск в строках, подвергнутых перестановкам небольших частей друг относительно друга;
В ходе работы был предложен эффективный эмпирический алгоритм, решающий поставленные задачи приближенного поиска. С помощью математического аппарата теории вероятности получены оценки на параметры алгоритма, определяющие область применения разработанного метода в рамках модели строковых последовательностей, близких к хаотическим. В ряде экспериментов продемонстрировано, что разработанный
метод и полученные оценки могут применяться в задачах приближенного поиска в строковых последовательностях, отражающих генетические нуклеотидные цепочки. Кроме того, сравнительные тесты показали, что в случае длинной шаблонной строки предложенный метод работает существенно быстрее, чем распространенные эмпирические аналоги, использующиеся на практике. Таким образом, вторая основная задача диссертации была успешно решена.
В основе двух описанных исследований лежит использование небольших выпуклых подмножеств элементарных информационных единиц дискретного информационного образа, называемых в диссертации п-мерными ^-граммами.
Представленная диссертация состоит из введения, трех глав, заключения и приложений. В первой главе диссертации приводится обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках. Приводятся примеры известных дескрипторов трехмерных фигур, рассматривается ряд фундаментальных техник распознавания образов, в которых могут применяться дескрипторы. Здесь же рассматриваются основные подходы к приближенному поиску в строках. В частности рассмотрен подход к поиску, связанный с расчетом расстояния редактирования, а также эмпирические алгоритмы семейства BLAST, использующие идеологию поиска с точностью до заданного расстояния редактирования. Также представлен алгоритм, позволяющий осуществлять приближенный поиск в условиях перестановок подстрок. Особое внимание уделено обзору временных сложностей некоторых распространенных алгоритмов приближенного поиска.
Вторая глава диссертации посвящена изложению теоретической части исследований настоящей диссертации. Здесь вводится формальное понятие информационного объекта и представлены алгоритмы конструирования дескрипторов произвольных информационных объектов. Проводится оценка временной сложности представленных алгоритмов и порядка требуемой
памяти. Во второй главе также рассматривается оригинальный алгоритм приближенного поиска и приводится оценка входных параметров этого алгоритма. Также рассматривается временная сложность алгоритма и порядок требуемой памяти. В ходе исследования параметров предложенного алгоритма выводится формула, в явном виде выражающая количество различных подстрок заданной длины в конечной строке, сгенерированной случайным образом над конечным алфавитом, что является самостоятельным результатом диссертации. В итоге предлагается простой метод выбора основного параметра в предложенном алгоритме приближенного поиска. В конце главы формулируются направления дальнейшего теоретического исследования в рассмотренных областях.
Третья глава посвящена практическому исследованию алгоритмов и оценок, полученных в главе 2. В частности здесь приводится ряд качественных экспериментов по кластеризации информационных объектов различной природы: изображений, звукозаписей, трехмерных объектов и ДНК-последовательностей с помощью дескрипторов, получаемых в результате применения алгоритмов второй главы. Также в третьей главе рассматривается один из самых современных benchmark-тестов дескрипторов трехмерных моделей - Princeton Shape Benchmark 2004 [53]. С помощью этого теста проводится количественный анализ предложенных в главе 2 дескрипторов на примере трехмерных объектов. Далее в главе приводится ряд экспериментов, посвященных проверке точности полученной в главе 2 формулы, выражающей среднее количество различных подстрок в случайно сгенерированных строках. Здесь же приводится ряд экспериментов по проверке предложенных методов выбора параметров алгоритма приближенного поиска, представленного в главе 2, а также по применению сформулированного алгоритма в задачах, близких к практическим задачам приближенного поиска в длинных нуклеотидных последовательностях. Также проводится сравнение скоростей работы предложенного алгоритма с одной из самых эффективных эмпирических систем BLAST.
Демонстрируется, что в случае достаточно длинных шаблонов скорость работы предложенного метода существенно превосходит скорость работы алгоритмов BLAST. В конце главы формулируются направления дальнейшего экспериментального исследования в рассмотренных областях.
Автор выражает особые благодарности: научному руководителю, д.т.н. Юрию Ильичу Кузякину за всестороннюю помощь и поддержку в процессе научной работы и подготовки диссертации; н.с. отдела системного обеспечения ИММ УрО РАН Денису Сергеевичу Перевалову за неоценимую помощь в научных исследованиях, подготовке и оформлении научных статей и диссертации, а также за множество ценных советов. Автор также выражает благодарности профессору кафедры компьютерных наук Эско Укконену, университет города Хельсинки, Финляндия; доктору компьютерных наук Гонзало Наварро, университет Чили; н.с. отдела компьютерных наук Филу Шилэйну, Принстонский университет за помощь в работе с Princeton Shape Benchmark - 2004.
Краткий обзор роли дескрипторов в некоторых фундаментальных техниках распознавания образов
Задачи второго класса состоят в конструировании алгоритмов приближенного поиска (approximate searching) по шаблону в строках. Основным требованием, предъявляемым к исследуемым алгоритмам, является линейная временная сложность 0(п), где п - длина строки данных в которой осуществляется поиск. На сегодняшний день не существует неэмпирических алгоритмов (при работе которых поставленная задача гарантированно решается) приближенного поиска, имеющих временную сложность лучше, чем О(кп) и не требующих более чем полиномиального времени для предварительной обработки строк и более чем полиномиального размера памяти для хранения информации в процессе поиска по шаблону [53]. Интерес к исследованиям подобного рода продиктован в первую очередь быстрым развитием генетики и возникновением ряда задач скоростного поиска в крупных нуклеотидных последовательностях. Существующие неэмпирические алгоритмы приближенного поиска часто оказываются недостаточно эффективными в приложениях связанных с исследованием генома. В связи с этим в приложениях, использующихся для приближенного поиска в нуклеотидных последовательностях, обычно применяют эмпирические методы, основанные на обнаружении областей вероятного местонахождения шаблона, либо на обнаружении областей, где шаблона вероятно нет. Сужение области поиска ведет к увеличению скорости работы с одной стороны и к появлению неконтролируемых ошибок с другой. В случае задач поиска в нуклеотидных последовательностях такой выход оказывается приемлемым [3].
Кроме требований к скорости работы алгоритмов, биологи предъявляют ряд специфических требований, одно из которых состоит в возможности приближенного поиска в условиях взаимных перестановок небольших частей нуклеотидных последовательностей (intrasequence rearrangements) [47]. Такие перестановки часто встречаются в результате генетической изменчивости, порождая схожие организмы, и представляют интерес для биологов. Существующие методы приближенного поиска не позволяют удовлетворительно обрабатывать строки, подвергшиеся перестановке подстрок. Причиной тому является неподходящая модель искажений, использующаяся в большинстве современных методов. Обычно единичное искажение строки представляют как операцию редактирования (вставки, удаления или замены символа). При такой модели искажений ставится задача нахождения в строке данных подстроки, которая может быть превращена в шаблонную не более чем заданным количеством операций редактирования. Минимальное количество операций редактирования, требующихся для превращения некоторой строки в шаблон, называется «расстоянием редактирования» [89] между строкой и шаблоном. В рамках описанной модели задача приближенного поиска сводится к поиску подстрок, отличающихся от шаблона не более чем на заданное расстояние редактирования. Искажение в виде перестановки подстрок в строке данных обычно ведет к резкому увеличению расстояния редактирования между участками строки данных, подвергшимися перестановке подстрок и шаблонной строкой. А это, в свою очередь, не позволяет применять описанную идеологию приближенного поиска с точностью до заданного расстояния редактирования.
Изложенные проблемы побудили автора провести исследование методов приближенного поиска, удовлетворяющих двум критериям: 1. алгоритмическая сложность исследуемого метода должна быть лучше, чем О(кп); 2. метод должен позволять осуществлять поиск в строках, подвергнутых перестановкам небольших частей друг относительно друга; В ходе работы был предложен эффективный эмпирический алгоритм, решающий поставленные задачи приближенного поиска. С помощью математического аппарата теории вероятности получены оценки на параметры алгоритма, определяющие область применения разработанного метода в рамках модели строковых последовательностей, близких к хаотическим. В ряде экспериментов продемонстрировано, что разработанный метод и полученные оценки могут применяться в задачах приближенного поиска в строковых последовательностях, отражающих генетические нуклеотидные цепочки. Кроме того, сравнительные тесты показали, что в случае длинной шаблонной строки предложенный метод работает существенно быстрее, чем распространенные эмпирические аналоги, использующиеся на практике. Таким образом, вторая основная задача диссертации была успешно решена. В основе двух описанных исследований лежит использование небольших выпуклых подмножеств элементарных информационных единиц дискретного информационного образа, называемых в диссертации п-мерными -граммами.
Представленная диссертация состоит из введения, трех глав, заключения и приложений. В первой главе диссертации приводится обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках. Приводятся примеры известных дескрипторов трехмерных фигур, рассматривается ряд фундаментальных техник распознавания образов, в которых могут применяться дескрипторы. Здесь же рассматриваются основные подходы к приближенному поиску в строках. В частности рассмотрен подход к поиску, связанный с расчетом расстояния редактирования, а также эмпирические алгоритмы семейства BLAST, использующие идеологию поиска с точностью до заданного расстояния редактирования. Также представлен алгоритм, позволяющий осуществлять приближенный поиск в условиях перестановок подстрок. Особое внимание уделено обзору временных сложностей некоторых распространенных алгоритмов приближенного поиска.
Расстояние редактирования и ограничения неэмпирических методов приближенного поиска, основанных на расчете расстояния редактирования
Границы в л-мерном пространстве свойств, отделяющие вектора объектов, принадлежащих различным классам, устанавливаются обычно на множестве обучающих объектов (обучающим здесь и далее мы называем множество, на котором проводится обучение алгоритма). Часто границы классов определяются с помощью вероятностного распределения образов, принадлежащих к каждому классу. Сами классы могут быть, как заданы наперед, так и выявлены в результате анализа областей скопления точек, соответствующих объектам обучающего множества.
Наравне с теоретико-вероятностным, также распространен аналитический подход к разделению классов. В этом случае задается параметрическая форма границы (например, линейная, квадратичная) и, на множестве обучающих объектов, находится наилучшая граница решения заданной формы. Такая граница может быть построена, например, методом минимизации среднеквадратичной ошибки. [34]
Во многих задачах распознавания, связанных с обработкой сложных образов, оправдан иерархический подход к конструкции информационного образа. Так информационный образ может быть составлен из более простых частей, которые, в свою очередь, также могут состоять из более простых. Простейшие части называются примитивами. Произвольный информационный образ представляется в терминах взаимосвязи между этими примитивами. В синтаксическом распознавании образов строится формальная аналогия между структурой информационного образа и синтаксисом некоторого языка. Информационные образы рассматриваются как предложения, принадлежащие некоторому языку и подчиняющиеся некоторой грамматике. Таким образом, большое количество различных комплексных информационных образов может быть представлено относительно небольшим числом примитивов и грамматических правил. Грамматика каждого класса шаблонов выводится при настройке алгоритма на множестве тестовых объектов.
Описанная парадигма применяется в ситуации, когда образы имеют определенную структуру, которую возможно зафиксировать в наборе правил. Такие образы возникают, например, при анализе электрокардиограмм, текстурных изображений и форм контуров. Применение синтаксического подхода обычно связано с множеством трудностей, связанных в основном с сегментацией искаженных образов (выделением примитивов) и выделением правил грамматики на тестовом множестве. Синтаксический подход часто приводит к возникновению большого числа комбинаторных возможностей, что в свою очередь заставляет создавать большие обучающие множества и задействовать существенные вычислительные мощности. [88]
Как и в статистическом методе распознавания образов, для нейронной сети каждый информационный образ должен быть представлен как точка или вектор в л-мерном пространстве некоторых своих свойств. После того как формализация проведена, перед нейронной сетью ставится аналогичная статистическим методам задача разделения точек пространства на непересекающиеся кластеры. Как и при статистической классификации, вектор, соответствующий информационному образу, является дескриптором в смысле Определения 1.3.
Нейронную сеть можно считать распараллеленной вычислительной системой, состоящей из большого числа простых процессоров с множеством взаимосвязей. В моделях нейронных сетей, формализуемых часто в виде взвешенных ориентированных графов, реализуются некоторые организационные принципы (например, обучение, обобщение, адаптация, отказоустойчивость, распределенные представление данных и вычисления) Вершинами этих графов являются искусственные нейроны. Ребра графов определяют вход и выход для каждого нейрона. Основной особенностью нейронной сети является способность выделять сложные нелинейные зависимости между входными и выходными данными, используя последовательные обучающие процедуры и изменяя собственную структуру согласно особенностям обрабатываемых данных.
В задачах распознавания образов наиболее часто используются модель нейронной сети с прямой связью, называемая многослойным перцептроном. Эта модель формализуется в виде графа, в котором вершины-нейроны расположены слоями. При этом нейроны не имеют связей внутри слоев, а нейроны каждого слоя, кроме последнего, связаны с нейронами последующего слоя однонаправленными ребрами [50]. В процессе обучения нейронной сети веса на ребрах варьируются так, чтобы на входных данных, принадлежащих обучающему множеству, сеть выдавала верные выходные данные. В результате такого обучения сеть становится способна верно решить текущую задачу классификации или кластеризации для многих входных данных, не принадлежащих обучающему множеству.
Возрастающая популярность нейронных сетей в задачах распознавания образов связана преимущественно с двумя фактами: 1) алгоритмы нейронных сетей, по-видимому, слабо зависят от специфики исследуемой области; 2) для пользователя доступны эффективные обучающие алгоритмы, с помощью которых нейронная сеть может быть настроена на решение той или иной задачи [73].
Дескриптор QSN, отражающий распределение совместных появлений пар «-мерных -граммов
Помимо описанных подходов к приближенному поиску, существует семейство эмпирических алгоритмов, основанных на анализе распределений -граммов в строках. Начало исследованиям в этой области было положено работой Эско Укконена [63]. На сегодняшний день ведется активная разработка прикладных инструментов приближенного поиска, основанных на подходе Укконена. В своей основе данный подход, называемый далее q-грамм подходом, может быть описан следующим образом.
Пусть, как и прежде, п - длина строки данных, т - длина шаблона. При заданном параметре к требуется найти все подстроки строки данных, имеющие длину т и содержащие не менее m-k-q -граммов строки шаблона [63].
Одной из современных реализаций данного метода является система приближенного поиска QUASAR [14]. Теоретическая временная сложность алгоритма, являющегося основой системы QUASAR составляет О(пт) [14]. Система QUASAR, также как и описанная выше система BLAST, является эмпирической, однако в отличие от нее позволяет осуществлять приближенный поиск в условиях перестановок подстрок (intrasequence rearrangement). Учитывая этот факт, QUASAR представляет собой, по-видимому, наиболее эффективный на сегодняшний день прикладной инструмент приближенного поиска. Существует также тенденция к объединению систем BLAST и QUASAR. В настоящей диссертации проводится дальнейшее развития семейства методов приближенного поиска, основанных на идеологии анализа распределений д-граммов, предложенной Укконеном.
В первой главе предложена формальный метод установления схожести двух информационных объектов и указаны две основные сложности, возникающие при таком сопоставлении: проблема выделения существенных свойств информационных объектов и проблема сокращения времени, затрачиваемого на процесс сопоставления. В качестве одного из путей решения указанных затруднений рассматривается конструирование вторичных информационных объектов - дескрипторов. При этом степень различия дескрипторов используется в качестве степени различия исходных информационных объектов. При конструировании дескрипторов часто удается акцентировать необходимые особенности первичных информационных объектов, а также, в ряде случаев, существенно снизить время сопоставления. Таким образом, использование дескрипторов позволяет решить ряд актуальных задач в области распознавания образов и является перспективным направлением для исследований.
Исследование одного семейства дескрипторов, позволяющих в ряде случаев эффективно сочетать решения проблемы скорости и проблемы точности определения схожести объектов, является одной из основных задач настоящей диссертации. Эти исследования представлены во второй и третьей главах. Оставшаяся часть первой главы посвящена краткому обзору существующих алгоритмов приближенного поиска в строках. Основным фактором, затрагиваемым в обзоре, являлась временная сложность алгоритмов. Обзор показал, что известные алгоритмы, решающие задачу приближенного поиска в различных постановках имеют временную сложность не менее О(тп) или О(кп) , где допустимое количество ошибок к в свою очередь обычно линейно зависит от длины шаблона т. Такая временная сложность не позволяет применять данный подход в ряде задач приближенного поиска крупных шаблонов в крупных строках данных (например, в некоторых задачах анализа нуклеотидных последовательностей). Таким образом, разработка систем поиска, не зависящих существенным образом от длины шаблона, является не только интересной теоретической задачей, но и актуальной проблемой в области обработки крупных нуклеотидных последовательностей. Другим важным требованием к разрабатываемой системе является возможность осуществлять приближенный поиск в строках, подверженных взаимным перестановкам подстрок. Перестановки частей в нуклеотидных последовательностях являются широко распространенным следствием биологической изменчивости организмов. Для исследования получающихся при этом схожих генных последовательностей эволюционно близких организмов требуются эффективные инструменты приближенного поиска. Создание скоростного метода приближенного поиска, позволяющего работать со строками, подверженными перестановкам частей позволит существенно расширить инструментарий ученых-биологов, занимающихся исследованием генома. Данная задача исследуется во второй и третьей главах диссертации. Подходы, используемые в диссертации для исследования двух сформулированных в настоящей главе направлений, основаны на анализе распределений q-грашюв обобщенных для случая /г-мерных информационных объектов. Теоретическому изложению данных подходов посвящена следующая глава.
Количественные эксперименты по применению дескриптора DQG в задачах классификации 3D объектов
Пусть заданы параметры q,Leli, строка данных v = (v,,...,v„+,H) и строка шаблона и = (?/,,...,г/„,+ н), где п т » q, V/ = \...n + q-\, j = \...m + q-\: v itj є A = {a1...a } . Далее пусть применяется Алгоритм q-AS для приближенного поиска строки шаблона в строке данных, тогда справедливо: 1 .Порядок требуемой памяти Алгоритма q-AS составит 0(n\og2 п), Функцию hi можно представить в виде ассоциативного массива, содержащего не более, чем т элементов, так как количество различных q-граммов, содержащихся в строке длины т, не может превосходить т. В каждой ячейке массива содержится 0 или 1, следовательно, порядок памяти, необходимый для хранения функции hi, составит О(т). Кроме того, в ходе алгоритма используются множества индексов І н R. Каждое из них содержит номера символов строки данных, а значит, общее число элементов в каждом из этих множеств не превзойдет п. Очевидно также, что величина каждого из чисел, входящих во множества индексов / и R не превосходит п, следовательно, для хранения каждого индекса достаточно \og2n ячеек памяти. При этом общий порядок памяти, требуемой для хранения множеств I и R, составит 0(n\og2n) . Аналогичным образом можно оценить память, требуемую для хранения функции g f: 0(L\og2n). Учитывая, что т п, L n, а порядок памяти для хранения функции h4u составляет О(т), порядок требуемой памяти для Алгоритма q-AS в целом составит 0{n\og2 п). 2. Алгоритм q-AS состоит из последовательных шагов. Рассмотрим временную сложность для каждого шага. Для расчета функции h4u на втором шаге алгоритма потребуется считать каждую подстроку длины q в шаблонной строке. Если считана /-тая подстрока (v,,...,v,+ H) , то для считывания следующей подстроки (v,+1,...,v/+(/) потребуется отбросить первый символ /-той строки и добавить в ее конец новый символ v . Таким образом, считывание подстрок потребует О(т) операций. Для каждой считанной подстроки требуется провести проверку и, возможно, изменение функции hi.
Будем считать, что h l представлена в виде упорядоченного ассоциативного массива, содержащего не более тіп{/;г,л 7} элементов (тех, на которых функция отлична от нуля), тогда процесс поиска нужного элемента потребует не более log2(min{w,/4 /}) операций. Как отмечено выше, такой процесс повторяется не более О(т) раз, а значит, порядок временной сложности второго шага Алгоритма q-AS составит О иІс ДтіпІ/и ЛІ 7})). Рассмотрим теперь временную сложность третьего шага алгоритма. Для построения функции gl потребуется прочитать каждую подстроку длины q строки данных. Для /-той прочитанной подстроки необходимо установить принадлежность к строке шаблона. Процесс установления потребует не более Iog2(min{/H,/i }) операций. В случае принадлежности, следует увеличить значение g ([iL/n]). Следовательно, временная сложность всего третьего шага составит C?(w log2 (тїп{/гг,уі / }j). На четвертом шаге алгоритма происходит построение множества /. Для построения этого множества требуется рассчитать сумму, определяющую функцию G, для каждой подстроки длины m+q-1 строки данных. Если такая сумма S, рассчитана для некоторой подстроки (v,,...,vm,t+ir2) , то для следующей подстроки (vi+l,...,v/+m+(H) соответствующая сумма Sl+I получается из суммы Si отбрасыванием первого и добавлением нового слагаемого: f ((vi+m,...,v/+lll+iH)) . Для определения значения нового слагаемого в ассоциативном массиве, представляющем функцию hi, потребуется log2(min{/??, }) операций. Следовательно, расчет значений G потребует не более 0[tjlog2[m m{m,\A\ }jJ операций, причем среднее значение G и максимум можно найти в ходе расчета значений G. При наличии функции G для построения множества / также потребуется не более О(п) операций. Таким образом, алгоритмическая сложность всего шага также составит О(п). На пятом шаге происходит построение подмножеств Вк множества /, составленных из подряд следующих индексов, на которых функция G превосходит заданный порог. Это действие требует одного прохода множества /, что в свою очередь требует 0(п) операций. Для конструирования множества R также потребуется не более О(п) операций, так как ]Г \вк / ввиду того, что подмножества Вк не пересекаются, а \l\ n + q-l . Таким образом, порядок временной сложности пятого шага составит 0(п). Общая временная сложность Алгоритма q-AS складывается из временных сложностей шагов 2-5 и имеет порядок: o(/7zlog2(min{;H,/l /})) + O log minlw, ! })) + 6 (/7log2(min{w, /})) + О(п) + 0(п) = o(/2log2(min{m,/f})). # Функцию gl:{0,...,/.-1} - Nu{0}, полученную на шаге 3 алгоритма q-AS удобно изобразить на плоскости, как это сделано на Рисунке 2.1. При этом получающиеся изображения иногда можно не подвергать дальнейшей обработке, так как можно визуально выделить области строки данных, предположительно приблизительно совпадающие с шаблонной строкой.
