Некоторые методы анализа распределений Q-граммов в задачах классификации данных и приближенного поиска по шаблону тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Иванко, Евгений Евгеньевич

• Иванко, Евгений Евгеньевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Иванко, Евгений Евгеньевич

ВВЕДЕНИЕ.

ГЛАВА 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 Выводы.

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

Автоматическое (машинное) распознавание, описание, классификация и группировка образов - это важные задачи в целом ряде инженерных и научных дисциплин, таких как искусственный интеллект и робототехника, биология, психология, медицина, экономика.

Интерес к распознаванию образов существенно возрос за последние десять лет. Исследования в этой области стимулируются возникновением большого числа интересных, важных и сложных прикладных задач. Среди таких задач можно назвать: поиск в некоторых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности (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).

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

Список литературы диссертационного исследования кандидат физико-математических наук Иванко, Евгений Евгеньевич, 2006 год

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.