Некоторые методы анализа распределений Q-граммов в задачах классификации данных и приближенного поиска по шаблону тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Иванко, Евгений Евгеньевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2006
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ
На правах рукописи
Иванко Евгений Евгеньевич
НЕКОТОРЫЕ МЕТОДЫ АНАЛИЗА РАСПРЕДЕЛЕНИЙ О-ГРАММОВ В ЗАДАЧАХ КЛАССИФИКАЦИИ ДАННЫХ И ПРИБЛИЖЕННОГО ПОИСКА ПО ШАБЛОНУ
Специальность 01.01.09 - Дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Екатеринбург - 2006
Работа выполнена в отделе вычислительных сетей Института математики и механики Уральского отделения Российской Академии Наук
Научный руководитель: доктор технических наук, ведущий научный сотрудник Ю.И. Кузякин
Официальные оппоненты: доктор технических наук, профессор
В.Г. Лабунец
доктор физико-математических наук, доцент М.Ю. Хачай
Ведущая организация: Уральский Государственный Университет им. Горького
Защита состоится ЪО 2006 года в часов на заседании
диссертационного совета К 004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики Уральского отделения РАН по адресу: 620219, г. Екатеринбург, ГСП-384, ул. С. Ковалевской, 16.
С диссертацией можно ознакомиться в научной библиотеке ИММ УрО РАН Автореферат разослан «21» аи^лд 2006 года.
Ученый секретарь диссертационного совета, кандидат физико-математических наук, / П
старший научный сотрудник /В .Д. Скарин
3.оо6 ft_
3A55" ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
Автоматическое (машинное) распознавание, описание, классификация и группировка образов - это важные задачи в целом ряде инженерных и научных дисциплин, таких как искусственный интеллект и робототехника, биология, психология, медицина, экономика
Интерес к распознаванию образов существенно возрос за последние десять лет Исследования в этой области стимулируются возникновением большого числа интересных, важных и сложных прикладных задач Среди таких задач можно назвать поиск в некоторых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности (data mining), классификация документов, финансовое прогнозирование, организация и обработка баз данных мультимедиа объектов, биометрика В таблице 1 перечислены некоторые важные области применения технологий распознавания образов.
Проблемная область Приложения Входные образы Классы образов
Биоинформатика Анализ ДНК и ГНК последовательностей Последовательности ДНК и РНК Известные гены
Data mining Поиск значимой информации Точки в многомерном пространстве Разделенные кластеры
Классификация документов Поиск в сети Интернет Текстовые файлы Семантические области (наука, искусство, спорт ИТл)
Автоматика Проверка печатных плат Изображения плат Годна/брак
Поиск в базах данных мультимедиа-объектов Поиск в Интернете Видео, аудио, изображения Жанр
Биометрика Идентификация личности Изображения лица, сетчатки глаза, палпилярного узора Отнесение к группе допуска
Распознавание речи Управление автоматикой с помощью речи Записи звуковой волны Произнесенные слова
Аэрофотосъемка Автоматическое картографирование Фотографии поверхности планет Опознанные объекты на фотографии
Таб.1 Сводная таблица некоторых областей применения методов распознавания образов
РОС. НАЦИОНАЛЬНАЯ i БИБЛИОТЕКА j С. Петербург? f/,
' - ;
Обзор содержания номеров одного из наиболее известных журналов, посвященных распознаванию образов - "IEEE Transactions on Pattern Analysis and Machine Intelligence" показал, что, начиная с 1979 по 2000 год, около 3000 статей был0 посвящено распознаванию образов На сегодняшний день темпы развития знаний в этой области продолжают расти.
Задачи классификации данных и приближенного поиска по шаблону (approximate searching), рассматриваемые в представленной диссертации, занимают одни из важнейших мест в ряду задач распознавания образов Среди авторов, внесших весомый вклад в решение этих задач можно назвать такие имена как В Левенштейн, ДА Поспелов, С Альтшуль, Р Баеза-Ятес, А Джэйн, Г. Наварро, Р. Харалик и Э. Укконен.
Проблемы классификации данных встречаются практически во всех областях применения вычислительной техники и являются одними из самых актуальных задач современной информатики. Методы приближенного поиска по шаблону в строках позволяют обнаруживать области строк, схожие в том или ином смысле с заданным шаблоном Эти методы лежат в основе систем автоматического исправления ошибок, позволяют существенно расширить инструментарий обработки текстов, а также являются фундаментом для одного из самых многообещающих исследований современной науки -компьютерного исследования генома
Цель и задачи исследования
Целью данной работы является теоретическая разработка и практическая апробация эффективных алгоритмов, обеспечивающих решение ряда задач, принадлежащих двум крупным классам задач распознавания образов
Первый класс задач сводится к скоростному расчету меры близости между двумя произвольными информационными образами, фигурирующими в задаче распознавания Такая мера является основой для приложений, осуществляющих автоматическую классификацию и кластеризацию информационных множеств Ключевым понятием при расчете меры близости для систем, работающих в условиях ограниченного времени и доступной памяти, являются «дескрипторы» - небольшие по размеру блоки данных, содержащие избранную информацию об исходных информационных образах. Каждому информационному образу ставится в соответствие свой дескриптор. При этом мера близости между дескрипторами считается мерой близости и между исходными информационными образами. Таким образом, структура дескриптора определяет сам способ расчета меры близости между двумя информационными образами, включая такие важные количественные характеристики как объем требуемой памяти, точность и
скорость сопоставления. Разработка новых дескрипторов небольшого размера, позволяющих добиваться высокой скорости и точности сопоставления информационных образов, является первой целью исследования.
Задачи второго класса состоят в конструировании алгоритмов осуществляющих приближенный поиск по шаблону в строках, при условиях искажений в виде перестановок подстрок, и имеющих не более чем линейную по длине входных данных временную сложность. Интерес к исследованиям подобного рода продиктован быстрым развитием генетики и возникновением ряда задач скоростного поиска в нуклеотидных последовательностях Кроме требований к скорости работы алгоритмов, исследователями-биологами предъявляется ряд специфических требований, одно из которых состоит в разработке алгоритмов приближенного поиска, способных осуществлять поиск в условиях искажений в виде перестановок небольших частей нуклеотидных последовательностей (intrasequence rearrangements) Второй целью настоящей работы является конструирование метода приближенного поиска, удовлетворяющего двум следующим условиям" 1 временная сложность предлагаемого метода должна линейно зависеть от длины исследуемой строки данных; 2 метод должен быть применим в задачах приближенного поиска в условиях перестановок небольших частей строки данных друг относительно друга.
Научная новизна
Основные научные результаты диссертации являются новыми, представляют собой итог ряда теоретических и практических исследований и заключаются в следующем'
• Предложены два оригинальных дескриптора (DQG и QSN) для произвольных информационных объектов Понятие информационного объекта формально обобщает в себе такие распространенные информационные структуры как строки, двумерные и трехмерные изображения в пиксельном и вексельном форматах соответственно, звукозаписи в WAV-формате. На основе предложенных дескрипторов разработаны методы расчета мер близости для произвольных информационных объектов Результаты, полученные при использовании предложенных методов в качественных экспериментах по кластеризации информационных объектов различной природы -строк, изображений, звукозаписей, показали перспективность дальнейших исследований методов
• Метод расчета меры близости между информационными объектами, основанный на использовании дескриптора DQG протестирован для случая трехмерных вексельных объектов с помощью наиболее крупного и репрезентативного benchmark-теста,
разработанного Принсгонским университетом в 2004 году Занимая первое-второе места среди 13 тестируемых дескрипторов по размеру (512 байт) и скорости обработки, предложенный дескриптор показал высокую точность в классификационных тестах В частности, при классификации на 92 класса дескриптор занял 5-е место, на 44 класса - 6-е, на 6 - 1-е и на 2 - 3-е
• Разработан метод q-AS приближенного поиска по шаблону в строках, временная сложность которого составляет 0(п log1 т), где п - длина строки данных, т -длина шаблона Предложенный метод сочетает высокую скорость работы с возможностью осуществлять приближенный поиск по шаблону в условиях перестановок небольших частей последовательностей, что удовлетворяет одному из важных современных требований биологов к поисковым системам в нуклеотидных последовательностях Ранее такую возможность предоставляли только алгоритмы, обладающие временной сложностью 0(пт), неприменимые в ряде прикладных задач скоростного приближенного поиска крупных шаблонов
• С помощью математического аппарата теории вероятностей проведено исследование областей применимости метода приближенного поиска q-AS Разработаны способы выбора входных параметров предложенного алгоритма приближенного поиска в зависимости от параметров входной задачи' длин строк, размера алфавита, вида и количества допустимых искажений Применимость предложенных способов выбора параметров продемонстрирована экспериментально
• В ходе решения задачи исследования областей применимости метода приближенного поиска q-AS получено аналитическое выражение, приближающее среднее количество различных подстрок фиксированной длины в строках заданной длины, сгенерированных случайным образом над конечным алфавитом. В зарубежной литературе количество различных подстрок длины к в строке называется Ar-subword complexity (сложность по подстрокам длины к) и представляет интерес во многих областях теории информации как мера «хаотичности» строки Полученное выражение является новым теоретическим результатом и имеет самостоятельную ценность в области теории информации
• Теоретически предложенный метод q-AS позволяет осуществлять поиск разрывного шаблона, либо нескольких шаблонов за один сеанс поиска, требующий линейного от размера данных времени Насколько известно автору, такая возможность не встречалась ранее в алгоритмах приближенного поиска
• Сформулированный алгоритм приближенного поиска сравнивался с эмпирическим алгоритмом поиска в ДНК последовательностях семейства NCBI-BLAST,
ч
использующимся в крупнейших генных базах данных GenBank В случае, когда размер шаблона превышает 105 символов, предложенный метод показывает существенное преимущество в скорости работы Шаблоны размера более 105 символов относительно редко встречаются на практике, однако способ использования метода q-AS для поиска нескольких шаблонов за один сеанс предполагает объединение большого количества шаблонов в один составной разрывный шаблон, длина которого может быть велика В этом случае выигрыш в скорости имеет прикладное значение.
Методы исследования
В работе применялись как теоретические, так и экспериментальные методы исследований Для построения теоретических положений работы задействован математический аппарат теории вероятностей Достоверность теоретических положение продемонстрирована с помощью вычислительных экспериментов, качественно и количественно - как с использованием современного benchmark-Tecra PSB-2004, так и в сравнении с существующими эффективными алгоритмами.
Научная и практическая значимость
Предложенная работа имеет теоретическое и прикладное значение Метод приближенного поиска по шаблону, описанный в диссертации, является первым, насколько известно автору, методом, позволяющим осуществлять приближенный поиск за время, меньшее чем 0(пт), в условиях искажений в виде перестановок подстрок. В работе впервые предлагается формула, выражающая в явном виде среднее количество различных подстрок заданной длины в строках фиксированной длины сгенерированных случайным образом Эта формула представляет интерес в области теории информации
На практике технологии, опирающиеся на результаты, полученные в настоящей работе, могут найти применение в задачах автоматического распознавания образов в условиях жестких ограничений на скорость работы и доступный объем памяти, а также как элементы систем поиска в крупных базах данных нуклеотидных последовательностей
Апробация работы
Основные положения диссертационной работы прошли апробацию на международной конференции «СССТ-2004 (Computing, Controls, Communications Technologies)», Austin, Texas, USA; международной конференции «ICAPR-2005 (International Conference on Advances in Pattern Recognition)», Bath, UK (поддержано трэвел-грантом РФФИ 05-01-10735-з); а также на международной конференции «Диалог-
2004» в Москве, 35-ой региональной молодежной конференции «Проблемы теоретической и прикладной математики» в Куигурке, Свердловская область; расширенном семинаре отдела управляемых систем ИММ УрО РАН и расширенном семинаре кафедры системного программирования механико-математического факультета ЮУрГУ, Челябинск.
Публикации
Основные положения диссертации опубликованы в 6 печатных и одной электронной работе, перечень которых приведен в конце автореферата
Структур» и объем работы
Текст диссертации изложен на 125 страницах, включая 98 листов основного машинописного текста (состоящего из введения, трех глав и заключения с рисунками, таблицами и формулами), список литературы (104 названия) и 4 приложения.
СОДЕРЖАНИЕ РАБОТЫ ВВЕДЕНИЕ
Во введении кратко определяется предмет исследования, формулируются проблемные области в задачах классификации данных и приближенного поиска по шаблону. Рассматривается актуальность поставленных задач и предлагается краткий обзор состояния проблемных областей в настоящее время Исходя из сказанного, формулируется цель и задачи диссертации, а также направления и методы их решения Здесь же приводится содержание работы по главам, благодарности научным руководителям, консультантам, коллегам за помощь в работе
ГЛАВА 1
В первой главе проводится краткий обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках В первом разделе первой главы вводится формальное понятие информационного объекта:
Определение 1 п-мериым информационным объектом (далее просто информационным объектом) будем называть функцию' /: В А , где В - конечное подмножество
множества л-мерных векторов с целыми координатами: Вс2" , а А - конечное
*
подмножество множества целых чисел: Ac Z Множество А будем называть алфавитом л-мерного информационного объекта.
Введенное понятие обобщает такие распространенные виды данных как строки, изображения и звукозаписи в формате WAV. Используя понятие информационного объекта, приводится формальное определение дескриптора, после чего во втором разделе рассматривается ряд распространенных дескрипторов трехмерных объектов (Описанные дескрипторы сравниваются в третьей главе с предложенными автором.) Методы конструирования дескрипторов для информационных объектов, сформулированные во второй главе, опираются на приведенные в настоящей главе понятия В завершение обзора дескрипторных технологий в третьем разделе настоящей главы демонстрируется роль дескрипторов в таких фундаментальных подходах к распознаванию как статистическая классификация и нейронные сети, синтаксический подход и кластеризация без обучения
Остальная часть первой главы посвящена обзору методов приближенного поиска по шаблону в строках В четвертом разделе формально вводится понятие расстояния редактирования между строками Здесь же проводится формальная постановка задачи приближенного поиска с точностью до заданного числа операций редактирования и предлагается обзор временных сложностей существующих алгоритмов приближенного поиска, использующих методику, связанную с расчетом расстояния редактирования. В пятом разделе рассматриваются принципы работы системы эмпирического приближенного поиска BLAST, использующейся в крупнейшем хранилище генетической информации GenBank Эмпирическая система BLAST используется для сравнения по скорости с оригинальным методом приближенного поиска, предложенным в настоящей работе Первая глава завершается шестым и седьмым разделами, в которых рассмотрены методы приближенного поиска по шаблону, позволяющие осуществлять поиск в условиях искажений в виде перестановок подстрок. Перестановки частей в нуклеотцдных последовательностях являются широко распространенным следствием биологической изменчивости организмов и алгоритмы, способные осуществлять приближенный поиск в условиях таких перестановок, представляют интерес для исследователей-биологов.
ГЛАВА 2
Во второй главе диссертации изложена теоретическая часть проведенных исследований В разделе 2.1.1 второй главы формулируется обобщение известного понятия ^-грамма, использующегося при анализе строк, - понятие «-мерного д-грамма'
е
Определение 2 n-мерным q-граммом будем называть всякий л-мерный информационный объект fq ' Bf-у Af, где B1-{Q,...,q-l}". Размером ^-грамма будем называть величину q
Определение 3 Пусть задан л-мерный информационный объект /: В —> А, тогда будем говорить, что л-мерный g-грамм f содержится в информационном объекте/ если ¡.А,с А
2-3 (х,.....*я)еВ:Ч(у,.....yJeB,
(*!+У,.....x.+yJeB
Ь f(*,+y,.....*.+yJ = f,(y,.....У J
Всякий вектор (х,, .., лг„ J е В, удовлетворяющий указанному свойству 2, будем называть точкой вхождения ^-грамма /? в информационный объект / а количество различных точек вхождения / в/ будем называть порядком /ч в информационном объекте f.
После чего предлагается алгоритм конструирования дескриптора DQG по произвольному информационному объекту.
Алгоритм 1 Построение дескриптора DQG (Распределение ^-граммов / Distribution off-grams)
1. Пусть задан л-мерный информационный объект f ■ {],...,Nl}x...x{l,...,Nn} А и размер ^-грамма, причем
Vi^TZit.N,
2. Рассмотрим функцию KQ . QfJI J -* N^jfOJ, где Q1Jl A = {ft {0,...,q - I)" -* а} - множество л-мерных ^-граммов над алфавитом А Значение функции Ke(J~q) равно порядку ^-грамма f в /
3. Упорядоченную пару j будем называть DQG-дескриптором информационного объекта /
В том же разделе доказывается следующая
Теорема 1 Пусть задан л-мерный информационный объект
/ ■ ,} ,,Nn}~* А и размер ^-грамма, причем V< = 1...л: N, >q. Пусть к
информационному объекту/применен Алгоритм СХ^Ю и получен дескриптор ^^ ^'тогда справедливо
1. порядок требуемой для работы алгоритма 1Х)0 памяти составляет
2. временная сложность алгоритма 1ХКЗ составит (|Л|* )• П +
После чего приводится следствие из теоремы, выражающее временную сложность и порядок памяти при естественных ограничениях прикладных задач на п,д,\А\. Далее предлагается способ расчета меры близости между двумя произвольными информационными объектами /, и /2, основанный на сопоставлении соответствующих ООО-дескрипторов (к?,^) и (к^, ЛГ2) этих объектов:
(1)
„'1АГ' ' "" Н2
где каждый это один из | А |* возможных л-мерных ^-граммов над алфавитом А.
Раздел 2.1.2 посвящен разработке второго из предложенных методов построения дескрипторов информационных объектов. В начале раздела приводится определение окрестности л-мерного ^-грамма'
Определение 4 Пусть задан л-мерный информационный объект /: В-у А и л-мерные граммы /,,/,": {0,...,д-1}" -* А, содержащиеся в / Будем говорить, что #-грамм /? находится в т-окрестности диграмма в информационном образе / если существуют
такие точки вхождения (х° ,...,х°) и (х,.....хт) ^-граммов и / в информационный
объект/, что тах^х'- х^\< т.
Определение 5 Пусть задано т е N Каждую упорядоченную пару точек вхождения л:,...,*„)) «7-граммов // и /ч в информационный объект / для которых выполняется соотношение тах{|.х° - х, |}< т , будем называть точкой вхождения упорядоченной пары д-граммов (/,",/,) . Число различных точек вхождения упорядоченной пары ¡/-граммов (/,",/, ), сложенное с числом различных точек вхождения
¡О
упорядоченной пары (/",/,") в информационный образ /будем называть порядком пары q-граммов {f° ,/f } в /
После чего предлагается алгоритм конструирования дескриптора QSN по произвольному информационному объекту.
Алгоритм 2 Построение дескриптора QSN (Семантическая сеть f-граммов / Q-gram semantic network)
1 Пусть задан n-мерный информационный объект / :{1.....N!}у....у.( 1.....Nm} -у А, размер ^-грамма и размер окрестности т,
причем Vi = l...n:N, ¿q.
2 Рассмотрим функцию К" • -±Н<и{0} , где
~ {{/,'./,'}: /, '/,J: {0>"-><7-1}" ~ множество пар л-мерных q-граммов над алфавитом А. Значение функции К w ({/J, f* j) равно порядку пары 9-граммов {/,',/,2} в/
3 Упорядоченную пару j будем называть QSN-дескриптором информационного объекта /
И доказывается
Теорема 2 Пусть задан л-мерный информационный объект
/■ {/,..., N,}x...x {I.....Nn} -> А, размер ^-грамма и размер окрестности от, причем
V/ = 1...л. N, > q. Пусть к информационному объекту/применен Алгоритм QSN и
получен дескриптор ^ Тогда справедливо:
1. порядок требуемой для работы алгоритма (^И памяти составляет
о(И"" log,
2 временная сложность алгоритма QSN составит O^/og,^1*"^ (2m + l)"Y[Nl -q + /j
К
После чего приводится следствие из теоремы, выражающее временную сложность и порядок памяти при естественных ограничениях прикладных задач на л, т, q, \А\. Далее предлагается способ расчета меры близости между произвольными информационными объектами /, и /2, основанный на сопоставлении соответствующих QSN-дескрипторов (aT1*',Wi) и {к* ,N*) этих объектов
(2)
где каждый /' это один из | А |* возможных л-мерных ^-граммов над алфавитом А
В разделе 2.2.1 формулируется задача приближенного поиска по шаблону в строках в постановке, позволяющей эффективно осуществлять приближенный поиск в условиях искажений в виде перестановок подстрок
Определение 6 Пусть задана строка данных v = (v,,...,v„) и строка шаблона
и = (и,,...,ит), где V/ = l...n,j = \...т: е А = {а.....>а\л\) ■ Пусть, кроме того, заданы
параметры q,H £ N . Будем говорить, что подстрока (vt,. .,vltm_,) сгрики v, где I & i i i + т -1 <, п , приблизительно совпадает с шаблоном, если количество точек вхождения ^-граммов шаблона в эту подстроку превышает Я. При заданных <j,#eN задачу нахождения всех подстрок строки v, приблизительно совпадающих со строкой шаблона в указанном выше смысле, будем называть далее задачей приближенного поиска
После чего разрабатывается алгоритм, решающий поставленную задачу
Алгоритм 3 (q-AS / приближенный поиск на основе q-граммов / q-gram approximate searching)
1. Пусть заданы параметры q,Le N Пусть задана строка данных v = (v1,,..,vn<.f_1) и строка шаблона и = («,, ■■■,umtt _,) , где п> rn » q,Vi = l...n + q-l,j = l...m + q-l:vt,uf е Л = {а, ...а^}.
2. Пусть Q4, = {fq {0,...,q-1}-> A] - множество всевозможных одномерных q-граммов над алфавитом А Рассмотрим функцию ' Q,, —► {0,1} , где hl(f4) = 1, если f4 принадлежит шаблонной строке и и hi(f4) = 0 иначе
£
IfL.fJWT.,
3. Разбиваем строку данных на Ь близких по длине подстрок В каждой подстроке считаем количество точек вхождения 9-граммов, принадлежащих строке шаблона. Опишем этот процесс формально. Рассмотрим функцию
g' :(0,...,1-1}-+Ыи{0} . Для каждого параметра к = 0...1-1 значением этой функции будет количество таких позиций 1 = 1... и , для которых справедливо [|£/л]=* и ЛК/щ = (\......= /.
4. Теперь рассмотрим все подстроки строки данных, длина которых равняется длине строки шаблона. Рассмотрим функцию на этих подстроках
V/ = 1...л-т + 1:<7(|')= . Для функции в рассчитаем
1-1
1<г(0
среднее значение б = —- и максимум <3А, = шах {0(;)} . Рассмотрим
л-т + 1 '-1
множество / = {/:/ = +1 & > (ви - О) / 2}.
5. Наконец, для каждого подмножества подряд следующих индексов из множества / выделим один, на котором функция <? максимальна Рассмотрим
все подмножества Вк - /7,.....такие, что V/ = + с ^ е/, а
« / . Рассмотрим множество Л = |«я* :0(1И')- • Всякую
подстроку строки данных V где / е Л будем называть областью
шаблона в строке данных. Упорядоченная пара (/?, g'} является результатом работы алгоритма.
И доказывается
Теорем» 3 Пусть заданы параметры строка данных у = и строка
шаблона и = («,,...,umtrl) , где n^m»q, V» = \...n + q-\, j = l...m + q-i' vt,Uj e A = {<V--a^j} . Далее пусть применяется Алгоритм q-AS для приближенного поиска строки шаблона в строке данных, тогда справедливо:
1. Порядок требуемой памяти Алгоритма q-AS составит 0(пlog, л),
2. Временная сложность Алгоритма q-AS составит о^л min{log2 т, log2|^|?}j .
li
В разделе 2.2.2 исследуется способ выбора параметра q в алгоритме 3. Для этого вводится понятие хаотической строки:
Определение 7 Пусть V» = /... л ■ <р1 - независимые в совокупности случайные величины, равномерно распределенные на множестве А = {а,...а^} Пусть далее произошло
событие = у,&...&<рп = у„} , где V/ = 1...л' V, е А . Строку V = будем
называть хаотической строкой над алфавитом А.
Далее рассматривается модель «равномерных» искажений в строке, представленных операциями редактирования и перестановки подстрок, характеризующаяся долей искажений р и приводится алгоритм, проводящий такие искажения. Если средняя доля искажений в строке составляет /?, тогда при размере д-грамма q > ^/р в среднем каждый ?-грамм будет содержать искажение и Алгоритм q-AS окажется неприменим, следовательно, первым офаничением на параметр ц будем считать
ч±ур- (3)
Если значение параметра q столь мало, что практически все возможные ^-граммы встречаются как в строке шаблона, так и в строке данных, значит функция О, рассчитываемая в ходе работы алгоретма ч-Ав, не позволит выделить предположительное местонахождение шаблона в строке данных. Чтобы избежать такой ситуации следует выбрать q достаточно большим для того, чтобы в шаблоне содержалась лишь часть всевозможных ^-граммов Для решения этой задачи предложен следующий метод. Пусть заданы строка данных длины л символов и шаблонная строка длины т символов над алфавитом/!.
1. Рассмотрим хаотическую строку длины л над алфавитом А и некоторую ее подстроку длины т.
2. Выберем минимальное при котором выполняется
N,/N¿0.5, (4)
где Nр - среднее количество ^-граммов в хаотических строках дайны т, а N -среднее количество ^-граммов в случайно сгенерированных строках длины п.
3 Считаем, что Алгоритм ^-АБ применим для приближенного поиска при доле искажений, формируемых алгоритмом искажений, не превышающей
При выполнении эмпирического условия Np! N <0 5 лишь некоторая часть ^-граммов случайно сгенерированной строки данных принадлежит случайно сгенерированной подстроке шаблона Будем считать, что при выполнении соотношения (4) аналогично лишь некоторая часть «у-граммов исходной строки данных принадлежит исходной шаблона При этом функция G, рассчитываемая в ходе поиска исходного шаблона в исходной строке данных с помощью алгоритма q-AS, при условии выполнения ограничения (3), принимает более высокие по сравнению со средним значения в области подстрок строки данных, содержащих повышенное число ^-граммов шаблона Такая область и признается нами областью шаблона.
Для того, чтобы найти минимальное q, при котором выполняется Nf/N <,0.5 ,
требуется получить явное выражение для среднего количества различных ^-граммов в случайно сгенерированных строках фиксированной длины В англоязычной литературе количество различных подстрок длины q в строке длины л называется g-subword complexity
Такое явное выражение рассчитывается в разделе 2.2.3. Рассмотрим последовательность независимых экспериментов (Et,...,En^ ,), где в результате всякого эксперимента Е, случайная величина <pt принимает значение на множестве А = . Эксперимент Е, соответствует выбору /-того символа в генерируемой
строке длины п+q-l над алфавитом А. Рассмотрим также последовательность случайных
величин (£,,...,£„), где = 1, если подстрока (<р,.....<P,tr\) не встречалась ранее среди
подстрок множества ' J <'}, и =0 иначе. Будем считать, что строка,
составленная из случайных величин ($»,,..., $!>,,*,_>) , удовлетворяет модели случайного следования ^-граммов (q-RSC модели), если вероятность встретить на i-tom шаге новый q-грамм зависит только от количества различных ^-граммов, встретившихся до того (; > 2)
где V; = 1...Л ■ к, е {0,1} Для 1 = 1 очевидно />{£, = 1} = 1, = 0} = 0 Предположение (5) не является очевидным свойством случайно сгенерированных строк, однако позволяет
Р& = 11 = &... & fH = } = 1 - /И* ,
/
получить формулу, в явном виде приближающую среднее значение сложности по полсловам длины q (^-subword complexity) для случайно сгенерированных строк
я
Рассмотрим выражение tjn = Математическое ожидание rjn покажет среднее
количество различных ^-граммов в строках, удовлетворяющих условию (5) и имеющих длину п+д-1. В настоящей работе эта величина используется при выборе параметра q для алгоритма 3. В данном разделе доказывается Теорема, в которой выводится явное выражение для расчета математического ожидания цщ.
Теорем» 4 В указанных выше обозначениях и при предположении (5) справедливо
В разделе 2.2.4 учитывается результат (6) и соотношение (4) переписывается в
виде:
Далее в разделе проводится упрощение алгоритма выбора параметра д для приближенного поиска с помощью алгоритма 3 В практических задачах приближенного поиска, особенно в задачах, связанных с анализом нуклеотидных последовательностей, часто выполняется соотношение п 2 Ют Такое соотношение позволяет предположить, что существуют значения д е N, которые достаточно малы для того, чтобы в хаотической строке длины п+д-1 содержались практически все возможные ^-граммы, тогда как в существенно меньшей хаотической подстроке длины т+д-1 количество различных ^-граммов было бы
существенно меньше, чем |л|'.
Формализуя сказанное, запишем условие.
из которого следует приближенное выполнение (7) Следуя вышеприведенным соображениям, из всех значений q, для которых выполняется условие
А/С7.) = И'(1-^-1/ИГ)Г) (6)
(7)
одновременного выполнения условия
и
следует выбирать минимальные значения. Натуральные значения q удовлетворяющие 1 - (/ - l/\A* <0.5 выражаются следующим образом:
(9)
Все значения q, найденные с помощью (9) и удовлетворяющие (8) будем считать подходящими значениями для приближенного поиска подстрок строки данных,
отличающихся от строки шаблона не более чем на -(m + q-I) равномерно
Я
распределенных операций редактирования и перестановок подстрок (в терминах модели искажений раздела 2.2.2)
Отсутствие таких целых q, которые удовлетворяют соотношению (8) не значит, что задача (7) также не имеет решений в целых q В этом случае следует пользоваться иными методами поиска q (на практике можно попробовать осуществлять поиск при q = п\±2 ) В алгоритмах приближенного поиска, использующих анализ
распределений ^-граммов, обычно выбирают q = [logi/1( nj Экспериментально
установлено, что при п>10т и п<1015 выражения (8), (9) позволяют определить размер q-грамма пригодный для применения Алгоритма q-AS и меньший, чем flog^ nj При
уменьшении размера q-грамма увеличивается доля искажений, при которых возможен приближенный поиск
Завершается вторая глава разделом 2.2.5, в котором проведен обзор особенностей и перспектив развития Алгоритма q-AS В этом разделе выдвигаются гипотезы о возможности применения представленного алгоритма для приближенного поиска разрывного шаблона, либо параллельного поиска нескольких шаблонов, а также применения данного алгоритма к приближенному поиску заархивированной шаблонной строки в заархивированной строке данных при условии применения метода архивации, основанного на избыточности кодировки ASCII
ГЛАВА 3
В третьей главе представлены экспериментальные исследования теоретических положений диссертации, рассмотренных в главе 2 Первая часть третьей главы посвящена экспериментальным исследованиям в области методов конструирования дескрипторов и расчета меры близости между информационными объектами В разделе 3.1.1 приводятся результаты серии качественных экспериментов по кластеризации различных множеств
информационных объектов, проведенные с помощью РАМ-алгоритма с использованием DQG и QSN дескрипторов и соответствующих мер близости (1) и (2) Эксперименты проведены для двух и трехмерных двуцветных изображений, звукозаписей в формате WAV и ДНК-последовательностей
В разделе 3.1.2 рассматривается DQG-дескриптор для случая трехмерных вексельных объектов Демонстрируется, что объем памяти, требующейся для хранения этого дескриптора, составляет 512 байт в худшем случае и 256 байт в среднем Далее, в разделе 3.1.3 рассматривается сравнительный benchmark-тест PSB-2004, предложенный для сопоставления дескрипторов трехмерных фигур Принстонским университетом в 2004 году На сегодняшний день этот ben chm arfe-тест является самым крупным и репрезентативным тестом дескрипторов трехмерных объектов Тест содержит 907 трехмерных объектов, 4 классификации, построенные вручную, и 6 инструментов для анализа точности тестируемого способа расчета меры близости
В разделе 3.1.4 приведены количественные эксперименты по применению дескриптора DQG, описанного в разделе 3 12, проведенные с помощью benchmark-TecTa PSB-2004 В частности демонстрируется, что при классификации на 6 общих групп (строения, бытовые предметы, растения, животные, мебель, транспортные средства), предложенный автором DQG дескриптор занял первое место (из 13 возможных мест) по точности классификации. Высокие результаты получены также и при трех других детализациях (92 класса - пятое место, 44 класса - шестое место и 2 класса - третье место) Размер дескриптора в 512 байт (на практике - 256 байт) является наименьшим после дескрипторов ТО и SHELLS (обеспечивающих при этом существенно более низкую точность классификации) Скорость генерации дескриптора 2-GR оказалась самой высокой, а скорость сопоставления двух 2-GR дескрипторов также превосходится только скоростями генерации D2 и SHELLS
Остальная часть третьей главы содержит результаты экспериментального исследования метода приближенного поиска по шаблону, сформулированного в главе 2 В разделе 3.2.1 приводится экспериментальное исследование методов выбора параметров для Алгоритма q-AS Здесь экспериментально подтверждается применимость формулы (6) для выражения среднего количества различных подстрок заданной длины в случайно сгенерированных строках фиксированной длины над фиксированным алфавитом Здесь же приводятся эксперименты, демонстрирующие удовлетворительную точность методов выбора параметра q в алгоритме 3, изложенных в разделе 2 2.2
В разделе 3.2.2 представлены эксперименты по применению алгоритма q-AS В ходе первого эксперимента с помощью алгоритма q-AS осуществлялся поиск шаблонов
длины 1000 символов (что соответствует длине некоторых генов), выбранных из последовательности 22-ой хромосомы шимпанзе в строке данных представляющей ДНК последовательность 22-ой хромосомы человека. В ходе второго эксперимента осуществлялся поиск шаблона длины 1000 символов, выбранного из ДНК последовательности митохондрии человека Строками данных в этом эксперименте служили ДНК последовательности митохондрий различных млекопитающих Проведенная серия экспериментов по тестированию алгоритма q-AS и метода выбора q в условиях приближенных к условиям реальных биологических задач продемонстрировала возможность применения предложенного алгоритма в ряде задач приближенного поиска в нуклеотндных последовательностях.
Завершается третья глава разделом 3.2.3, в котором рассматриваются результаты сравнения скоростей работы алгоритма q-AS и эмпирической системы приближенного поиска BLAST, используемой в хранилище генетических данных GenBank В результате проведенного количественного сравнения продемонстрирована более высокая скорость работы Алгоритма q-AS при поиске больших (>10s символов) шаблонов.
Задачи поиска крупных шаблонов встречаются относительно редко на практике, однако замечание, сделанное в разделе 2.2.5, позволяет предположить возможность применения Алгоритма q-AS для поиска разрывных шаблонов или дяя параллельного поиска нескольких шаблонов. При этом выигрыш во времени, достигаемый с помощью Алгоритма q-AS по сравнению с системой BLAST, будет представлять практический интерес. Эксперименты по поиску разрывных шаблонов и по параллельному поиску нескольких шаблонов с помощью Алгоритма q-AS ведутся в настоящее время.
ЗАКЛЮЧЕНИЕ
В представленной работе исследовались вопросы применения методов анализа распределений и-мерных ^-граммов в двух важных задачах распознавания образов: расчете дескрипторной меры близости между произвольными информационными объектами и скоростном приближенном поиске в строках при условиях перестановок подстрок Ниже изложены основные результаты, полученные в ходе исследований, и сформулированы избранные направления развития исследований.
На основе анализа распределений n-мерных (/-граммов разработан эффективный способ построения дескрипторов и расчета меры близости между произвольными информационными объектами с использованием построенных дескрипторов. Проведенные эксперименты показали высокую различающую способность предложенных дескрипторов, что, учитывая их небольшой размер и высокую скорость обработки,
позволяет считать ^-грамм дескрипторы перспективным инструментом в области расчета меры близости между информационными объектами различной природы В развитие данной темы в первую очередь планируется провести количественные тесты, оценивающие результаты применения ^-грамм дескрипторов для классификации одномерных информационных объектов: ДНК последовательностей и звукозаписей
Предложенный метод расчета меры близости между информационными образами протестирован для случая трехмерных объектов с использованием наиболее крупного и репрезентативного ЬепсЬтатк-теста, разработанного Принстонским университетом в 2004 году Занимая первое-второе места среди 13 тестируемых дескрипторов по размеру (512 байт) и скорости обработки, предложенный дескриптор показал высокую точность в классификационных тестах В частности, при классификации на 92 класса дескриптор занял 5-е место, на 44 класса - 6-е, на 6 - 1-е и на 2 - 3-е Основным планируемым направлением развития здесь является разработка дескриптора трехмерных объектов, инвариантного относительно поворотов объектов
Предложен метод приближенного поиска по шаблону в условиях перестановок подстрок, имеющий временную сложность 0(п 1о%1 т), где п - длина строки данных, т -длина шаблона Эмпирические системы, широко применяемые на практике, имеют теоретическую временную сложность 0(пт) Такая временная сложность влечет существенное увеличение времени работы методов при увеличении длины шаблона.
В ходе исследования областей применимости предложенного метода приближенного поиска получено явное аналитическое выражение, приближающее среднюю сложность по подсловам конечных слов, записанных над конечным алфавитом В ходе дальнейших исследований в этом направлении планируется изучить асимптотическое поведение выражения и получить теоретически оценки приближения
Предложенный метод приближенного поиска сравнивался с инструментом эмпирического поиска в ДНК последовательностях семейства ЫСВ1-ВЬА8Т, использующимся в крупнейших базах данных геномов СепВапк. В ряде задач приближенного поиска шаблона превосходящего по длине 105 символов предложенный метод показал существенное преимущество в скорости работы.
Теоретически предложенный метод позволяет осуществлять поиск разрывного шаблона, либо нескольких шаблонов за один сеанс поиска, требующий линейного от совокупного размера данных времени. Насколько известно автору, это свойство не встречалось в существующих на сегодняшний день алгоритмах приближенного поиска Как отмечалось выше, существенный выигрыш при использовании предложенного метода достигается при поиске достаточно больших шаблонов. Однако крупные шаблоны
Ю
относительно редко встречаются на практике. Описанное свойство позволяет осуществлять поиск разрывного шаблона, составленного из множества более мелких шаблонов за линейное время Возникающая задача выделения конкретных шаблонов из найденной области существенно проще исходного поиска Описанная технология одновременного поиска нескольких шаблонов нуждается в экспериментальном исследовании, что также планируется проделать в будущем.
Кроме того, планируется исследовать устойчивость предложенного метода поиска к архивированию информационных образов, при котором не используются ссылки на предыдущие участки информационного образа (такими являются, например, алгоритмы, использующие избыточность кодировки ASCII).
Основные положения диссертации опубликованы в следующих работах:
1 Иванко ЕЕ Об одном методе поиска по шаблону на топографических картах Журнал Вычислительные технологии Новосибирск 2005 г. - Т. 10 №3 С 39-46
2 Ivanko Е, Perevalov D On Using Sign Method For 3D Images Recognition And Classification // International Conference on Computing, Communications and Control Technologies- CCCT'04, Austin, Texas USA 2004 - Volume V, P 248-251
3. E Ivanko, D Perevalov. Q-gram statistics descriptor in 3D shape classification 3rd International Conference on Advances in Pattern Recognition. Pp 360-367,200S.
4 E Ivanko, D Perevalov, В Wilson Provisional Patent Application 60/585738, USA, 2004
5 Иванко F. E , Перевалов Д С Об одном знаковом методе обработки информации и его применении для анализа текстов и контурных изображений /Проблемы теоретической и прикладной математики, труды 35-ой региональной молодежной конференции Екатеринбург, УрО РАН. 2004 г - С. 269-273
6 Иванко Е Е, Перевалов Д С Знаковый метод обработки информации и его применение к анализу текстов, классификации изображений и звукозаписей /Наука и будущее, идеи, которые изменят мир/ Материалы международной конференции (тезисы докладов) Москва 2004 г. - С.78-80
7. Перевалов Д, Иванко Е Использование ассоциативных семантических сетей для классификации звукозаписей. Статьи, принятые к публикации на сайте международной конференции Диалог-2004
http: / /www .dialoq-21 ■ ru/ftrchlv6/2004/Perevalov.htm
г\
Подписано в печать 13.04.2006. Формат 60x 84 1/16. Бумага типографская. Печать офсетная. Усл. печ. л. 1,5. Тираж 100 экз. Заказ 50
Размножено с готового оригинал-макета в типографии "Уральский центр академического обслуживания". 620219, г. Екатеринбург, ул. Первомайская, 91.
«3.QO&A
94 59
ВВЕДЕНИЕ.
ГЛАВА 1. ОБЗОР ДОСТИЖЕНИЙ В ОБЛАСТЯХ КОНСТРУИРОВАНИЯ ДЕСКРИПТОРОВ ТРЕХМЕРНЫХ ОБЪЕКТОВ И СКОРОСТНОГО ПРИБЛИЖЕННОГО ПОИСКА ПО ШАБЛОНУ В СТРОКАХ.
1.1 Информационные объекты и дескрипторы.
1.2 Обзор некоторых дескрипторов трехмерных объектов.
1.3 Краткий обзор роли дескрипторов в некоторых фундаментальных техниках распознавания образов.
1.3.1 Статистическая классификация (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, отражающий распределение /7-мерных ^-граммов.
2.1.2 Дескриптор QSN, отражающий распределение совместных появлений пар «-мерных ^-граммов.
2.2.1 Алгоритм q-AS (q-gram Approximate Searching/ ф q-грамм приближенный поиск).
2.2.2 Модели строк и искажений в строках, используемые при ф выборе параметров алгоритма q-AS.
2.2.3 q-Subword complexity (сложность по подстрокам длины q) случайных строк.
1 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 Сравнительный ЬепсЬтагк-тест 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 Выводы.
Автоматическое (машинное) распознавание, описание, классификация и группировка образов - это важные задачи в целом ряде инженерных и научных дисциплин, таких как искусственный интеллект и робототехника, биология, психология, медицина, экономика.
Интерес к распознаванию образов существенно возрос за последние десять лет. Исследования в этой области стимулируются возникновением большого числа интересных, важных и сложных прикладных задач. Среди таких задач можно назвать: поиск в некоторых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности (data mining), классификация документов, финансовое прогнозирование, организация и обработка баз данных мультимедиа объектов, биометрика. В таблице 1 перечислены некоторые важные области применения технологий распознавания образов.
Проблемная область Приложения Входные образы Классы образов
Биоииформатика Анализ ДНК и РНК 1 шел едо вателы юстей Последовательности ДНК и РНК Известные гены
Data mining Поиск значимой информации Точки в мног омерном пространстве Разделенные кластеры
Классификация документом Поиск в сети Интернет Текстовый файл Семантические области (напр.наука, искусство, спорт)
Автоматика Проверка печатных плат Изображения плат Годна/брак
Поиск в КД мультимедиа- объектов Поиск в Интернете Видео, аудио, изображение Жанр
Биометрика Идентификация личности Изображение лица, сетчатки глаза, паппилярного узора Отнесение к группе допуска
Распознавание речи Управление автоматикой с помощью речи Запись звуковой волны Произнесенные слова
Аэрофотосъемка Автоматическое картографирование Фотография Опознанные объекты па фотографии
Таб.1. Сводная таблица некоторых областей применения методов распознавания образов [34].
Обзор содержания номеров одного из наиболее авторитетных журналов, посвященных распознаванию образов - "IEEE Transactions on Pattern Analysis and Machine Intelligence" показал, что, начиная с 1979 по 2000 год, около 3000 статей было посвящено распознаванию образов [34].
Одним из основных свойств информации представленной в вычислительной машине является дискретность, иными словами информация о распознаваемом объекте представлена в вычислительной машине как множество элементарных информационных единиц - букв или цифр. Одномерные данные записываются в виде конечных последовательностей над конечным алфавитом (сюда можно отнести текст и оцифрованные звукозаписи). Двумерные данные представляются матрицами над конечным числовым множеством (наиболее часто встречающиеся двумерные данные -это двумерные изображения, где значения элементов матриц отражают уровни яркости или цвета соответствующих участков изображения). Трехмерные данные аналогично могут записываться как трехмерные матрицы над конечным множеством чисел (так, например, представляются данные, полученные с помощью 3D сканера; элемент матрицы в этом случае отражает уровень яркости его отсутствие/наличие либо цвет участка пространства).
Существуют многочисленные методы автоматической обработки дискретной машинной информации, в частности в задачах распознавания образов. Для строковых данных одним из распространенных методов является использование подстрок длины q, называемых ^-граммами. В настоящей работе сделана попытка обобщить понятие ^-грамма для двух- и трехмерных данных. Введенное понятие «-мерного ^-грамма используется для конструирования аналогичных строковым методов анализа 2D и 3D графической информации. Примером одномерного д-грамма может служить связная подстрока длины q строки текстового файла. Одномерные ^-граммы широко применяются при лингвистическом анализе текстов [102], архивации данных [66], в задачах поиска по шаблону в строках [61,63]. Примером двумерного ^-грамма является квадратный участок изображения размером дхд пикселей. Такие структуры используются, например, при анализе текстур и конструировании графических фильтров для изображений [27,35,68].
Несмотря на широкое использование, потенциал методов, связанных с анализом /7-мерных ^-граммов, далеко не исчерпан. В данной работе проводится теоретическая разработка и практическая апробация новых эффективных алгоритмов, основанных на анализе распределений /г-мерных ¿/-граммов в информационных объектах. Для исследования были выбраны два крупных класса проблем распознавания образов, являющиеся актуальными на сегодняшний день.
Первый класс проблем связан с применением дескрипторов в задачах сопоставления информационных объектов некоторых типов. Дескриптор здесь - это небольшой по размеру информационный объект, ставящийся в соответствие исходному информационному объекту [32,33,80,81], конструируемый так, чтобы формально выраженная степень схожести двух дескрипторов характеризовала степень схожести двух исходных информационных объектов. Обычно конструирование дескрипторов подчинено идее сокращения времени и памяти, необходимых для определения степени схожести двух информационных объектов. Такой подход часто используется в приложениях, осуществляющих автоматическую классификацию и кластеризацию множеств информационных объектов в условиях жестких ограничений на время сопоставления, либо доступную память. В настоящей работе исследовались дескрипторы, основанные на гистограммах «-мерных ^-граммов и гистограммах совместных появлений пар /7-мерных ^-граммов. В ходе работ было проведено как качественное, так и количественное тестирование этих дескрипторов, в результате чего удалось эмпирически найти наиболее эффективную форму дескрипторов для автоматической классификации в ряде актуальных задач.
Задачи второго класса состоят в конструировании алгоритмов приближенного поиска (approximate searching) по шаблону в строках. Основным требованием, предъявляемым к исследуемым алгоритмам, является линейная временная сложность О(п), где п - длина строки данных в которой осуществляется поиск. На сегодняшний день не существует неэмпирических алгоритмов (при работе которых поставленная задача гарантированно решается) приближенного поиска, имеющих временную сложность лучше, чем О(кп) и не требующих более чем полиномиального времени для предварительной обработки строк и более чем полиномиального размера памяти для хранения информации в процессе поиска по шаблону [53]. Интерес к исследованиям подобного рода продиктован в первую очередь быстрым развитием генетики и возникновением ряда задач скоростного поиска в крупных нуклеотидных последовательностях. Существующие неэмпирические алгоритмы приближенного поиска часто оказываются недостаточно эффективными в приложениях связанных с исследованием генома. В связи с этим в приложениях, использующихся для приближенного поиска в нуклеотидных последовательностях, обычно применяют эмпирические методы, основанные на обнаружении областей вероятного местонахождения шаблона, либо на обнаружении областей, где шаблона вероятно нет. Сужение области поиска ведет к увеличению скорости работы с одной стороны и к появлению неконтролируемых ошибок с другой. В случае задач поиска в нуклеотидных последовательностях такой выход оказывается приемлемым [3].
Кроме требований к скорости работы алгоритмов, биологи предъявляют ряд специфических требований, одно из которых состоит в возможности приближенного поиска в условиях взаимных перестановок небольших частей нуклеотидных последовательностей (intrasequence rearrangements) [47]. Такие перестановки часто встречаются в результате генетической изменчивости, порождая схожие организмы, и представляют интерес для биологов. Существующие методы приближенного поиска не позволяют удовлетворительно обрабатывать строки, подвергшиеся перестановке подстрок. Причиной тому является неподходящая модель искажений, использующаяся в большинстве современных методов. Обычно единичное искажение строки представляют как операцию редактирования (вставки, удаления или замены символа). При такой модели искажений ставится задача нахождения в строке данных подстроки, которая может быть превращена в шаблонную не более чем заданным количеством операций редактирования. Минимальное количество операций редактирования, требующихся для превращения некоторой строки в шаблон, называется «расстоянием редактирования» [89] между строкой и шаблоном. В рамках описанной модели задача приближенного поиска сводится к поиску подстрок, отличающихся от шаблона не более чем на заданное расстояние редактирования. Искажение в виде перестановки подстрок в строке данных обычно ведет к резкому увеличению расстояния редактирования между участками строки данных, подвергшимися перестановке подстрок и шаблонной строкой. А это, в свою очередь, не позволяет применять описанную идеологию приближенного поиска с точностью до заданного расстояния редактирования.
Изложенные проблемы побудили автора провести исследование методов приближенного поиска, удовлетворяющих двум критериям:
1. алгоритмическая сложность исследуемого метода должна быть лучше, чем О(кп);
2. метод должен позволять осуществлять поиск в строках, подвергнутых перестановкам небольших частей друг относительно друга;
В ходе работы был предложен эффективный эмпирический алгоритм, решающий поставленные задачи приближенного поиска. С помощью математического аппарата теории вероятности получены оценки на параметры алгоритма, определяющие область применения разработанного метода в рамках модели строковых последовательностей, близких к хаотическим. В ряде экспериментов продемонстрировано, что разработанный метод и полученные оценки могут применяться в задачах приближенного поиска в строковых последовательностях, отражающих генетические нуклеотидные цепочки. Кроме того, сравнительные тесты показали, что в случае длинной шаблонной строки предложенный метод работает существенно быстрее, чем распространенные эмпирические аналоги, использующиеся на практике. Таким образом, вторая основная задача диссертации была успешно решена.
В основе двух описанных исследований лежит использование небольших выпуклых подмножеств элементарных информационных единиц дискретного информационного образа, называемых в диссертации п-мерными ^-граммами.
Представленная диссертация состоит из введения, трех глав, заключения и приложений. В первой главе диссертации приводится обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках. Приводятся примеры известных дескрипторов трехмерных фигур, рассматривается ряд фундаментальных техник распознавания образов, в которых могут применяться дескрипторы. Здесь же рассматриваются основные подходы к приближенному поиску в строках. В частности рассмотрен подход к поиску, связанный с расчетом расстояния редактирования, а также эмпирические алгоритмы семейства BLAST, использующие идеологию поиска с точностью до заданного расстояния редактирования. Также представлен алгоритм, позволяющий осуществлять приближенный поиск в условиях перестановок подстрок. Особое внимание уделено обзору временных сложностей некоторых распространенных алгоритмов приближенного поиска.
3.3 Выводы
В настоящей главе рассматривались эксперименты, посвященные проверке дескрипторов информационных объектов и алгоритма приближенного поиска, предложенных в главе 2.
Качественные испытания предложенных дескрипторов, проведенные на различных типах информационных объектов, продемонстрировали универсальность предложенной технологии и удовлетворительную различающую чувствительность дескрипторов, а также показали перспективность дальнейшего исследования.
Количественное сравнение дескриптора DQG на основе PSB-2004 для трехмерных объектов показало следующее. DQG-дескриптор воксельных объектов, представленных в кубе 32x32x32, при q=2 является одним из наименьших существующих дескрипторов трехмерных фигур. В худшем случае его размер составляет 512 байт. На практике обычно достаточно 256 байт. Дескрипторы меньшего размера (D2, SHELLS), приведенные для сравнения в PSB-2004, показывают существенно более низкую точность при распознавании.
Скорость конструирования DQG-дескриптора оказалась самой высокой среди дескрипторов, представленных в PSB-2004. Скорость сопоставления двух дескрипторов уступает только тем же дескрипторам D2 и SHELLS.
Несмотря на небольшой размер, точность классификации, полученная при использовании DQG-дескриптора, оказалась высока. Во всех тестах DQG-дескриптор оказывался в верхней половине рейтинговой таблицы, содержащей кроме DQG результаты тестирования 12 распространенных дескрипторов. При классификации на 6 общих групп (строения, бытовые предметы, растения, животные, мебель, транспортные средства), предложенный 2-GR дескриптор занял первое место по точности классификации.
Небольшой размер и высокая скорость обработки DQG-дескриптора при относительно высокой различающей чувствительности позволяют прогнозировать высокую практическую значимость предложенного дескриптора для задач распознавания трехмерных образов в условиях жестких ограничений на скорость работы и доступную память.
В будущем планируется продолжить работы по конструированию дескрипторов. В частности планируется создать дескрипторы размера , не более чем DQG, но обладающие более высокой различающей чувствительностью и, таким образом, демонстрирующие более высокие результаты в тестах. Кроме того, планируется сконструировать DQG-дескриптор вексельных объектов, инвариантный относительно некоторых поворотов в пространстве.
Также в настоящей главе проведены эксперименты, посвященные исследованию предложенного в главе 2 Алгоритма q-AS. Первая серия экспериментов связана с проверкой формулы, выражающей в явном виде среднее количество различных подстрок заданной длины в хаотических строках фиксированной конечной длины над алфавитом фиксированного размера. Эксперименты показали высокую точность полученной в главе 2 формулы. В настоящей работе формула используется в методе выбора длины
-грамма в Алгоритме q-AS. Следует отметить, что полученная формула имеет самостоятельную ценность, являясь новым результатом в области теории информации.
Следующая серия экспериментов посвящена исследованию применимости предложенных в разделе 2.2.4 методов выбора размера q-грамма в алгоритме приближенного поиска q-AS. Проведенные эксперименты показали удовлетворительную точность предложенных теоретических оценок входного параметра q.
Также в главе приведены результаты количественного сравнения предложенного Алгоритма q-AS с эмпирическим алгоритмом семейства BLAST. В ходе сравнения продемонстрирована более высокая скорость Алгоритма q-AS при поиске больших (>106 символов) шаблонов.
В заключительной части главы приведена серия экспериментов по тестированию предложенного алгоритма в условиях приближенных к условиям реальных биологических задач. В ходе этих экспериментов осуществлялся приближенный поиск частей ДНК-последовательностей некоторых организмов в ДНК-последовательностях других близких организмов. При этом размер частей выбирался соизмеримым с размером гена. Эксперименты показали применимость предложенного алгоритма в ряде задач приближенного поиска в нуклеотидных последовательностях.
ЗАКЛЮЧЕНИЕ
В представленной работе исследовались вопросы применения методов, основанных на расчете распределений ¿/-граммов, в двух важных задачах распознавания образов: исследовании дескрипторной меры близости между произвольными информационными образами и скоростном приближенном поиске в строках при условиях искажений в виде перестановок подстрок. Оба направления являются актуальными для современной информатики, способствуя решению ряда важных практических задач. Технологии, основанные на анализе распределений ¿/-граммов, активно применяются в различных областях обработки информации. Несмотря на множество работ, посвященных применению ¿/-граммов в различных задачах, потенциал ¿/-грамм технологий далеко не исчерпан. В настоящей работе применение методов, основанных на расчете распределений ¿/-граммов, позволило получить новые, теоретически и практически ценные результаты.
Первая область применения ¿/-грамм технологий, рассматриваемых в настоящей работе, связана с конструированием методов определения степени схожести двух объектов, что является одним из важнейших этапов при решении задач автоматической классификации и кластеризации. В области исследования степени схожести между произвольными информационными объектами в свою очередь одной из важнейших задач является нахождение на практике оптимального соотношения между вычислительными затратами (по времени и памяти) и точностью используемой степени схожести. Первой задачей настоящей работы являлось исследование одного способа расчета меры близости для произвольных информационных объектов на основе анализа распределений ¿/-граммов. В ходе решения этой задачи получены следующие результаты.
На основе сопоставления дескрипторов в виде распределений 17-граммов и взвешенных графов, составленных с использованием ¿/-граммов, предложен эффективный алгоритм расчета меры близости между произвольными информационными объектами. Предложенные методы расчета мер близости использовались в качественных тестах по автоматической кластеризации двумерных двуцветных контурных изображений, трехмерных двуцветных воксельных изображений, аудиозаписей слов русского языка и музыкальных произведений, ДНК-последовательностей живых организмов. Проведенные эксперименты показали высокую точность классификаций, получаемых при использовании исследуемых дескрипторов и соответствующих мер близости. Учитывая небольшой размер дескрипторов и высокую скорость обработки, полученные данные позволяют считать g-грамм дескрипторы перспективным инструментом в области расчета меры близости между информационными объектами различной природы.
Предложенный метод расчета меры близости между информационными объектами количественно протестирован на примере трехмерных объектов с использованием наиболее крупного и репрезентативного ЬепсЬтагк-теста 3D объектов, разработанного Принстонским университетом в 2004 году. В ряде сравнительных тестов предложенный метод существенно превзошел аналоги по совокупности параметров. Так, занимая первое-второе места среди 13 тестируемых дескрипторов по размеру (512 байт) и скорости обработки, предложенный дескриптор показал высокую точность в классификационных тестах. В частности, при классификации на 92 класса дескриптор занял 5-е место, на 44 класса - 6-е, на 6 - 1-е и на 2 - 3-е. Относительно высокая точность классификации при условии небольшого размера и высокой скорости обработки позволяет считать разработанный дескриптор полезным прикладным инструментом для решения ряда задач скоростной классификации и поиска трехмерных объектов в крупных базах данных. Основным направлением развития здесь является разработка дескриптора, инвариантного относительно некоторых поворотов трехмерного информационного образа в пространстве.
Полученные результаты также показали целесообразность исследований д-грамм дескрипторов с помощью инструментария сравнительных тестов для различных типов информационных образов. В этом направлении в первую очередь планируется провести количественные тесты, оценивающие эффективность расчета мер близости с помощью ОСЮ и С)8Ы дескрипторов для линейных информационных объектов: ДНК последовательностей и \УА.У-звукозаписей.
Второй задачей, рассматривавшейся в настоящей диссертации, является задача приближенного поиска в строках. Современные темпы развития генетики и компьютерных технологий исследования генома предъявляют повышенные требования к методам приближенного поиска. Для исследования были выбраны две важные проблемы, стоящие перед создателями инструментов приближенного поиска в нуклеотидных последовательностях. Первая проблема состоит в увеличении скорости работы алгоритмов поиска и обусловлена увеличением объемов данных, подвергающихся обработке при генетическом анализе. Вторая проблема связана с отсутствием скоростных инструментов приближенного поиска в случае, когда строка искажена путем перестановок небольших подстрок. Такие искажения характерны при генетических мутациях и представляют интерес для биологов. Как и в случае задач исследования способов расчета степени схожести, задачи, поставленные в области приближенного поиска, решались на основе методов, опирающихся на расчет распределений ц-граммов. В ходе работ были получены следующие результаты. На основе анализа распределений ^-граммов разработан алгоритм приближенного поиска по шаблону, временная сложность которого не превосходит А(я1о§2(тт{ш,|л|''})) , где п - длина исследуемой строки данных, т - длина шаблона. Временная сложность схожих алгоритмов составляет О(пт). При этом алгоритм не требует существенного препроцессинга. Недостатком предложенного метода можно считать ограничение на допустимые искажения. На сегодняшний день метод сформулирован только для случая «равномерных» искажений в строке.
Существующие подходы к приближенному поиску по шаблону, имеющие близкую временную сложность, требуют более чем полиномиального по времени и размеру памяти препроцессинга. Эмпирические же системы, широко применяемые на практике, имеют теоретическую временную сложность, линейно зависящую от произведения длин строк шаблона и данных. Такая временная сложность влечет существенное увеличение времени работы алгоритмов при увеличении длины шаблона. Предложенный Алгоритм q-AS позволяет осуществлять скоростной поиск крупных шаблонов, не затрачивая существенного времени на препроцессинг. Кроме того, предложенный алгоритм обеспечивает удобное визуальное представление результатов поиска, позволяющее осуществлять непосредственный визуальный анализ.
В ходе экспериментов, описанных в настоящей работе, предложенный метод приближенного поиска сравнивался с инструментом эмпирического поиска в ДНК последовательностях семейства ЫСВ1-ВЬА8Т, считающимся на сегодняшний день самым мощным поисковым инструментов в нуклеотидных последовательностях и использующимся в крупнейших базах данных генных последовательностей вепБапк. В ряде задач приближенного поиска достаточно крупного шаблона предложенный алгоритм показал существенное преимущество в скорости работы.
При высокой скорости работы предложенный метод позволяет осуществлять поиск в условиях взаимной перестановки небольших частей последовательностей, что, как упоминалось выше, удовлетворяет одному из важных современных требований биологов к поисковым системам в нуклеотидных последовательностях. Перестановка частей нуклеотидных последовательностей является одной из форм мутаций, порождая новые организмы. Скоростной поиск с перестановками позволяет биологам повысить эффективность исследований мутирующих организмов, в частности вирусов, скорость мутации которых велика.
Развитие предложенного алгоритма планируется вести по нескольким основным направлениям. В их числе увеличение доли допустимых искажений при приближенном поиске и исследование методов решения задачи приближенного поиска в условиях резко неоднородных искажений.
Как отмечалось выше, существенный выигрыш при использовании предложенного метода достигается при поиске достаточно больших шаблонов. Однако крупные шаблоны относительно редко встречаются на практике. Теоретически предложенный метод позволяет осуществлять поиск разрывного шаблона, либо нескольких шаблонов за один сеанс поиска, требующий линейного от размера данных времени. Это свойство не встречалось в существующих на сегодняшний день алгоритмах приближенного поиска. Описанное свойство позволяет осуществлять поиск разрывного шаблона, составленного из множества более мелких шаблонов за линейное время. При этом возникающая вторичная задача выделения мелких шаблонов из найденной области существенно проще исходного поиска. Описанная технология одновременного поиска нескольких шаблонов нуждается в экспериментальном исследовании, включая количественное сравнение скорости работы с известными алгоритмами. Эти исследования планируется провести в будущем.
Также планируется исследовать устойчивость предложенного метода приближенного поиска к архивированию информационных образов, при котором не используются ссылки на предыдущие участки информационного образа (такими являются, например, алгоритмы, использующие избыточность кодировки ASCII).
Резюмируя можно отметить, что вопросы, поставленные в диссертации, актуальны для современной информатики. В ходе исследовательской работы удалось получить удовлетворительные решения поставленных вопросов на основе единого теоретического подхода. Для основных результатов диссертации сформулированы направления дальнейшего развития.
1. Abrahamson K., Generalized string matching, SI AM Journal on Computing, 16(6), 1039-1051, 1987.
2. Aho A.V., Algorithms for finding patterns in strings, Chapter 5 (pp. 255300) of Leeuwen J. van (ed.) Handbook of Theoretical Computer Science, Elsevier Science Publishers, Amsterdam.
3. Altschul, S.F., Gish, W., Miller, W., Myers, E.W. & Lipman, D.J. (1990) "Basic local alignment search tool." J. Mol. Biol. 215:403-410
4. Amir A., Landau G.M., and Vishkin U., Efficient pattern matching with scaling, Journal of Algorithms, 13(1), 2-32, 1992.
5. Ankerst M., G. Kastenmuller, H.-P. Kriegel, and T. Seidl, Nearest neighbor classification in 3D protein databases. In Proc. ISMB, 1999.
6. Aoe J., Computer Algorithms String Pattern Matching Strategies, IEEE Computer Society Press, Los Alamitos, California, 1994.
7. Baeza-Yates R., and Gonnet G.H., A new approach to text searching, Communications of the ACM, 35(10), 74-82, 1992.
8. Baeza-Yates R., Improved string matching, Software-Practice and Experience, 19(3), 257-271, 1989
9. Baeza-Yates R.A., Algorithms for String Searching: A Survey, ACM SIGIR Forum, 23(3-4), 34-58, 1989.
10. Basic Local Alignment Search Tool (NCBI). http://www.ncbi.nlm.nih.gov/BLAST
11. Blumer A., Blumer J., Haussler D., Ehrenfeucht A., Chen M.T., and Seiferas J., The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40(1), 31-55, 1985.
12. Boyer R.S., and Moore J.S., A fast string searching algorithm, Communications of the ACM, 20(10), 762-772, 1977.
13. Britten, R.J., Divergence between samples of chimpanzee and human DNA sequences is 5%, counting indels. Proc. Natl. Acad. Sci. USA 99: 13633-16335
14. S. Burkhardt, A. Crauser, P. Ferragina, H. P. Lenhof, and M. Vingron. q-gram based database searching using a suffix array (QUASAR). In Int. Conf. RECOMB, Lyon, April 1999.
15. Campbell R. J. and P. J. Flynn, A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding, 81:166210, 2001
16. Chang W, Marr T., Approximate string matching and local similarity, In Proc Combinatorial Pattern Matching 94, 259-273, Springer-Verlag, 1994.
17. Charras C., and Lecroq T., Exact string matching algorithms, Technical Report, 1997.
18. Chen D.-Y., M. Ouhyoung, X.-P. Tian, and Y.-T. Shen, On visual similarity based 3D model retrieval. Computer Graphics Forum, pages 223-232, 2003.
19. Colussi L., Fatest pattern matching in strings, Journal of Algorithms, 16( 2), 163-189, 1994
20. Crochemore M., and Rytter W., Text Algorithms, Oxford University Press, 1994.
21. Elad M. , A. Tal, and S. Ar, Content based retrieval of VRML objects an iterative and interactive approach. In 6th Eurographics Workshop on Multimedia 2001.
22. Galil Z., Giancarlo R., Improved string matching with k mismatches, Sigact News, 17,52-54, 1986.
23. GenBank. http://www.nebi.nlm.nih.gov/Genbank/index.html
24. Gheorghiciuc I., PhD Thesis, UNIVERSITY OF PENNSYLVANIA. 2004. The subword complexity of finite and infinite binary words.
25. Gribskov M., J.Devereux, Sequence Analysis Primer. Stockton Press, 1991.
26. Hall P., Dowling G., Approximate string matching, ACM Computing Surveys, 12(4), 381-402, 1980
27. Haralick R. M., K. Shanmugam, I. Dinstein, Textural features for image classification // IEEE Transactions on SMC 1973. SMC-3(6) P. 610-621.
28. Hetzel G., B. Leibe, P. Levi, and B. Schiele, 3D object recognition from range images using local feature histograms. International Conference on Computer Vision and Pattern Recognition, December 2001.
29. Horn B., Extended Gaussian images. Proc. of the IEEE, 72(12): 1671-1686, December 1984
30. Hume A., and Sunday D., Fast string searching, Software-Practice and Experience, 21 (11), 1221 -1248, 1991.
31. Ivanko E., Perevalov D. On Using Sign Method For 3D Images Recognition And Classification // International Conference on Computing, Communications and Control Technologies: CCCT'04, Austin, Texas USA. 2004. Volume V, P.248-251
32. Ivanko E., D. Perevalov., Q-Gram Statistics Descriptor in 3D Shape Classification. Proceedings of Third International Conference on Advances in Pattern Recognition. LNCS 3686-3687, Part II, pp. 360-367, August 2005
33. Ivanko E., Perevalov D., Wilson B. Provisional Patent Application 60/585738, USA, 2004.
34. Jain A., P. Duin, and J. Mao, «Statistical pattern recognition: A review». IEEE Transactions on PAMI 22(1), pp. 4-37, 2000.
35. Janson S., S. Lonardi, and W. Szpankowski. On average sequence complexity. Theoretical Computer Science, 326(1—3):213—227, 2004
36. Jarvelin K. and J. Kekalainen, IR evaluation methods for retrieving highly relevant documents. In 23rd Annual International ACMSIGIR Conference on Research and Development in Information Retrieval, 2000.
37. Kang S. and K. Ikeuchi, Determining 3-D object pose using the complex extended Gaussian image. In CVPR, pages 580-585, June 1991.
38. Kaufman L. and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, Inc. (1990).
39. Kazhdan M., T. Funkhouser, and S. Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symposium on Geometry Processing, June 2003.
40. Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.
41. Kurtz S., Approximate string searching under weighted edit distance, in Proc. WSP 96, 156-170, Carleton University Press, 1996.
42. Landau G.M., Vishkin U., Efficient String Matching with k Mismatches, Theoretical Computer Science, 43, 239-249, 1986
43. Landau G.M., Vishkin U., Fast String Matching with k Differences, Journal of Computer and System Sciences, 37, 63-78, 1988.
44. Leifman G., S. Katz, A. Tal, and R. Meir. Signatures of 3D models for retrieval, pages 159-163, February 2003.
45. Liu Z., Du X., and Ishii N., An improved adaptive string searching algorithm, Software-Practice and Experience, 28(2), 191-198, 1998.
46. Lopresti D., A. Tomkins, Block Edit Models for Approximate String Matching, Theoretical Computer Science, vol. 181, 1997, pp. 159-179
47. Manber U., "A text compression scheme that allows fast searching directly in the compressed file," technical report 93-07, Department of Computer Science, University of Arizona (March 1993).
48. Manolopoulos Y., and Faloutsos C., Experimenting with pattern matching algorithms, Information Sciences, 90(1-4), 75-89, 1996.
49. Mark J., Orr L., Introduction to Radial Basis Function Networks. Centre for Cognitive Science, University of Edinburgh
50. McCreight E., A space-economical suffix tree construction algorithm, Journal of the ACM, 23(2), 262-272, 1976.
51. Misener Ed.S., S.A.Krawetz, Bioinformatics Methods and Protocols (Methods in molecular biology, vl32), 513c
52. Navarro G., A guided tour to approximate string matching. Technical Report TR/DCC-99-5, Dept. of Computer Science, Univ. of Chile, 1999
53. Osada R., T. Funkhouser, B. Chazelle, and D. Dobkin, Matching 3D models with shape distributions. Shape Modeling International, pages 154-166, May 2001
54. Princeton Shape Benchmark (2004), http://shape.cs.princeton.edu/benchmark
55. Rijsbergen C. K., Information Retrieval. Butterworths, 1975
56. Saupe D. and D. V. Vranic, 3D model retrieval with spherical harmonics and moments. In B. Radig and S. Florczyk, editors, DAGM 2001, pages 392-397, September 2001
57. Schiele B. and J. L. Crowley, Recognition without correspondence using multidimensional receptive field histograms. International Journal of Computer Vision, 36(1 ):31-52, 2000.
58. Smit G. De V., A Comparison of Three String Matching Algorithms, Software-Practice and Experience, 12(1), 57-66, 1982.
59. Stephen G.A., : String Searching Algorithms book. Lecture Notes Series on Computing Vol. 3, World Scientific Publishing Co., Singapore 1994
60. Sutinen E., Tarhio J., On using q-gram locations in approximate string matching, In Proc ESA 95, 327-340, Springer-Verlag, 1995.
61. Taxonomy browser. http://www.ncbi.nlm.nih.gov/Taxonomy/
62. Ukkonen E., Approximate string matching with q-grams and maximal matches, Theoretical Computer Science, 1, 191-211, 1992.
63. Vandeborre J.-P., V. Couillet, and M. Daoudi, A practical aproach for 3D model indexing by combining local and global invariants. 3D Data Processing Visualization Transmission (3DPVT02), pages 644-647, June 2002.
64. Vranic D. V., An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres. In IEEE International Conference on Image Processing (ICIP 2003), volume 3, pages 757-760, September 2003
65. Welch T.A., A technique for high performance data compression / IEEE Computer 17(6):8-19, June 1984
66. Wu S., and Manber U., Fast text searching allowing errors, Communications of the ACM, 35(10), 83-91, 1992.
67. Yamada H., K.Yamamoto, K.Hosokawa, Directional mathematical morphology reformalized Hough Transformation for the analysis of topographic maps // IEEE Transactions on PAMI 1993 Vol.PAMI-15, N.4. P. 380-387.
68. Zaharia T. and F. Preteux, 3D shape-based retrieval within the MPEG-7 framework. In SPIE Conf. on Nonlinear Image Processing and Pattern Analysis XII, volume 4304, pages 133-145, January 2001
69. Анисимов Б.В., Курганов В., Распознавание и цифровая обработка изображений. М.1983
70. Гнеденко Б. В., А. Я. Хинчин., Элементарное введение в теорию вероятностей. Едиториал УРСС, 2003 г.
71. Горбань А.Н., Россиев Д.А., Нейронные сети на персональном компьютере. Н.1996
72. Гренадер У., Лекции по теории образов: В 3 тт. Анализ образов (кн.2) М. 1981
73. Дуда Р., Харт П., Распознавание образов и анализ сцен. М. Мир, 1976.
74. Загорулько Ю.А., Методы представления и обработки знаний: Семантические сети и системы продукций. Методическое пособие. Изд-во НГУ. Новосибирск, 1996
75. Иванко Е.Е., "Бессмысленные компьютеры остались в прошлом" / Научно-популярный журнал "Универсум". Москва. 2004 №5 С.27
76. Иванко Е.Е., Об одном методе поиска по шаблону на топографических картах. Вычислительные технологии. Новосибирск. 2005 г. Т. 10 №3 С.39-46.
77. Иванко Е.Е., Шемякин Д. А., Система картографирования и мониторинга сети./Телематика'2004/Сборник трудов всероссийской конференции. Санкт-Петербург. 2004 г. С. 102-103
78. Кнут Д., Искусство программирования. Т. 1 3. М., СПб., Киев: ИД «Вильяме», 2000.
79. Колмогоров А.Н., Теория информации и теория алгоритмов. М.: Наука, 1987.303 с.
80. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы, построение и анализ. М.: МЦНМО, 2000.
81. Котов В.Е., Сабельфельд В.К., Теория схем программ. М.: Наука, 1991.
82. Краснощеков П.С., Петров A.A., Принципы построения моделей. М.: Фазис, 2002.
83. Кузин Л.Т., Основы кибернетики, т.2. Основы кибернетических моделей. М. 1979
84. Кузин Л.Т., Синтаксическое распознавание образов (лингвистические модели распознавания). Основы кибернетики, т.2. сс. 173-185
85. Левенштейн В.И., Двоичные коды с исправлением выпадений и вставок символа 1, Пробл. перед, информ., 1,1, 1965, 12-25
86. Нефедов Е. И., Т. И. Субботина, А. А. Яшин., Современная биоинформатика. -М.:ГОРЯЧАЯ ЛИНИЯ ТЕЛЕКОМ, 272 С., 2005.
87. Ope О., Теория графов. М.: Наука, 1980.
88. Перевалов Д., Иванко Е., Использование ассоциативных семантических сетей для классификации звукозаписей. Статьи, принятые к публикации на сайте международной конференции Диалог-2004.http://www.dialog21 .ru/Archi ve/2004/Perevalov.htm
89. Подиновский В.В., Ногин В. Д., Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
90. Поляк Б.Т., Введение в оптимизацию. М.: Наука, 1984.
91. Поспелов Д. А., Логико-лингвистические модели в системах управления. Москва, Энергоиздат, 1981
92. Поспелов Д.А., Моделирование рассуждений. Опыт анализа мыслительных актов Москва, Радио и связь, 1989
93. Рубашкин В.Ш., Представление и анализ смысла в интеллектуальных информационных системах. М.: Наука, 1989
94. Сэведж Дж. Э., Сложность вычислений. М.: Факториал, 1998.
95. Ту Дж., Гонсалес Р., Принципы распознавания образов. М. 1978.- 413с.
96. Фаллер Д.М., Молекулярная биология клетки. Руководство для врачей. Изд-во Бином. 272 С.
97. Форсайт Д. А., Понс Ж., Компьютерное зрение. Современный подход. : Пер. с англ. М.: Издательский дом "Вильяме", 2004.
98. Хмелёв Д.В., Распознавание автора текста с использованием цепей A.A. Маркова / Вестник МГУ, сер.9: Филология, N02, 2000, с. 115-126
99. Чень Ч., Ли Р., Математическая логика и автоматическое доказательство теорем. М.1983.- 360с.
100. Яблонский C.B., Введение в дискретную математику. М.: Наука, 2001.
