Содержание к диссертации
Введение
Глава 1. Современное положение и результаты исследований по системному анализу неструктурированной текстовой информации 13
1.1 Основные понятия информационного поиска 13
1.2 Информационная технология поиска текстовых документов 14
1.2.1 Агент 14
1.2.2 Индексатор 16
1.2.3 Семантический анализ корпуса 18
1.2.4 Анализ запроса 20
1.2.5 Поиск 25
1.3 Модели информационного поиска 26
1.4 Поиск по смыслу и латентно-семантический анализ 29
1.5 Модели процесса поиска информации ЗГ
1.6 Сравнительная характеристика групп ИПС 34
1.7 Оценка поисковых систем 36
1.8 Анализ научной информации 38
1.9 Постановка задачи исследования 39
Глава 2. Системный анализ неструктурированной текстовой информации, представленной в виде корпуса текстов научного знания 44
2.1 Основные определения 44
2.2 Алгоритм построения семантической модели корпуса 50
2.2.1 Получение списка терминов из документа 50
2.2.2 Выделение доминантных терминов 53
2.3 Латентный семантический анализ 55
2.4 Пример применения латентного семантического анализа 58
2.5 Поиск по корпусу 65
Глава 3. Интеллектуальный анализ корпуса текстов научного знания ... 68
3.1 Поиск по корпусу 68
3.2 Алгоритм уточнения запроса пользователя 68
3.3 Пример работы алгоритма уточнения запроса 74
3.4 Описание модифицированной информационной технологии 77
Глава 4. Автоматизированная система анализа корпуса текстов научного знания 85
4.1 Описание разработанного программного продукта 85
4.2 Структура индекса 89
4.3 Информационный агент и индексация 90
4.4 Описание исходных данных 92
4.5 Морфологический анализ текста 93
4.6 Тестирование системы 96
4.6.1 Тестирование на одном компьютере 96
4.6.2 Индексация распределенного текстового корпуса 101
Приложение
- Основные понятия информационного поиска
- Основные определения
- Поиск по корпусу
- Описание разработанного программного продукта
Введение к работе
Актуальность темы. Современные системы и устройства управления, навигации и радиолокации, а также информационно-измерительные комплексы широко применяют системы синхронизации (СС). Эти системы выполняют многочисленные задачи; к числу наиболее распространенных из них относятся: синхронизация и демодуляция двоичных символов цифровой информации, измерение частоты и фазы сигналов, тактовая синхронизация, синтез сложных радиотехнических сигналов, синтез сетки высокостабильных частот, стабилизация частот генераторов различных диапазонов, когерентная демодуляция аналоговых и цифровых сигналов с частотной и фазовой модуляцией.
Повсеместное внедрение цифровых систем синхронизации (ЦСС) привело к повышению эффективности перечисленных выше устройств. При этом повысились точность и надежность СС, увеличились их быстродействие и помехоустойчивость. В тоже время усложнились алгоритмы обработки информации, а также программы оптимизации параметров СС и устройств в целом.
Особое значение при проектировании и создании СС имеют проблемы оценки устойчивости этих систем при воздействии помех различного рода. При этом статистические моменты фазовой и частотной ошибок слежения (среднее и среднеквадратическое значения) не дают полной информации о поведении СС. Поскольку СС - существенно нелинейная система, то в ряде случаев необходимо знание плотностей распределения вероятностей (ПРВ) переменных состояния. Особенностью СС с рядом других систем (не фазовых) является существование множества устойчивых состояний равновесия, а в отдельных предельных случаях и устойчивых периодических движений 1-го и 2-го рода, что еще более усложняет картину при действии шумов.
Исследования СС существенно усложняются, если наряду с шумовой (флуктуационной) помехой на СС воздействует узкополосная негауссовская помеха. Здесь особенно важным является исследование СС при воздействии гармонических помех. К таким помехам относятся помехи соседних каналов в системах радиосвязи, помехи многолучевости, помехи космическим навигационным системам (GPS и ГЛОНАСС), организованные помехи радиолокационным станциям.
Основным методом исследования СС при наличии гауссовского шума на входе в настоящее время является метод марковских случайных процессов. Пионерами использования этих методов применительно к СС являются Р.Л.Стратонович и В.И.Тихонов. Существенный вклад в развитие теории синхронизации при наличии гауссовского шума на входе сделали Б.И. Шахтарин, В. Линдсей, А. Витерби, Дж. Холмс, В.Д. Шалфеев, Н.Н. Удалов, В.Н. Белых, В.Н. Кулешов, В.Д. Разевиг, В.В. Шахгильдян, А. Вайнберг и другие. В результате к настоящему времени теория непрерывных СС при наличии шумовых воздействий в основном завершена. В то же время теория дискретных систем синхронизации (ДСС) даже при шумовых воздействиях
разработана весьма незначительно. И если в непрерывных СС достаточно подробно методом марковских процессов исследованы системы 1, 2-го порядков, применительно к ДСС - это в основном касается систем только 1-го порядка. Такие исследования выполнены М.И. Жодзишским, В.Н. Кулешовым, В.В. Шахгильдяном, Б.И. Шахтариным, В.Н. Белых, В.П. Сизовым, Дж. Холмсом, X. Осборн, С. Гуптой.
Исследованиям дискретных СС в условиях даже простейших узкополосных помех посвящено ограниченное число работ. Одной из первых работ, где рассмотрены комбинированные воздействия на непрерывную СС (сигнал + шум + гармоническая помеха) является статья Журавлева А.Г.
Подобную ситуацию можно объяснить следующими причинами. Во-первых, представляет собой достаточно серьёзную проблему переход к марковским моделям, не существует общей методики перехода; ситуация значительно усложняется в условиях узкополосных воздействий. Во-вторых, необходимо обеспечить строгий переход от марковской модели к векторному уравнению Колмогорова - Чепмена, корректно подстроив условную плотность вероятности перехода; сложность вызвана периодическим характером нелинейности. В-третьих, усложняется задача о среднем времени до срыва слежения. Даже наличие простого сигнала без помехи, но с изменяющейся частотой, существенно усложняет решение задачи о срыве.
Очевидно, что результатов исследования даже непрерывных СС при комбинированных воздействиях в настоящее время явно недостаточно. Кроме того, необходимо разрабатывать теорию ДСС, включая цифровые, при комбинированных воздействиях.
В связи с вышеизложенным, тема диссертации, посвященной разработке алгоритмов анализа систем синхронизации при воздействии гармонических и шумовых помех, является достаточно актуальной.
Задачи, решаемые в диссертации. Для достижения поставленной цели в диссертации решаются следующие основные задачи:
Разработка математических моделей ряда непрерывных и дискретных СС с учетом воздействия на них как шумовых, так и гармонических воздействий.
Разработка алгоритмов анализа статистических характеристик СС при комбинированном воздействии шумовых и гармонических помех.
Разработка методики решения интегрального уравнения Колмогорова-Чепмена приближёнными методами, описывающего состояние СС.
Исследование ДСС первого порядка приближённым методом Галёркина.
Анализ плотности распределения вероятности (ПРВ) фазовой ошибки в непрерывной системе при комбинированном воздействии помех приближённым методом.
Анализ двухконтурной СС (схемы Костаса) и получение ее статистических характеристик.
Положения, выносимые на защиту.
Марковские модели ряда непрерывных и дискретных СС при комбинированных воздействиях в виде смеси полезного колебания, детерминированной помехи и широкополосного гауссовского шума.
Методика приближенного исследования методом гармонического баланса и усреднения непрерывных СС при комбинированном воздействии.
Разработанные разностные схемы уравнений ФПК и уравнений Понтрягина, позволяющие численно находить ПРВ сигнала рассогласования в переходном режиме, а также среднее время и вероятность до срыва слежения.
Алгоритмы анализа статистических и динамических характеристик ДСС 1-го и ДСС 2-го порядков.
Сравнительные характеристики ДСС 1-го и ДСС 2-го порядков.
Результаты исследований статистических характеристик двухконтурной СС (схемы Костаса).
Научная новизна результатов.
Разработана разностная схема уравнения Фоккера-Планка-Колмогорова (ФПК) и уравнение Понтрягина, позволяющие получать ПРВ сигнала рассогласования в переходном режиме, а также численно находить среднее время и вероятность до срыва синхронизации.
Получены статистические характеристики фазового рассогласования ДСС 1 и 2-го порядка, дисперсии фазовой ошибки слежения при использовании метода Галёркина и численно-аналитических методов.
За счёт применения имитационной модели СС и разработанных методик, в отношении ряда систем получены уточняющие данные по сравнению с известными результатами.
Получены области применения приближённых методов при анализе дискретных СС 1-го порядка.
Приближенным методом гармонического баланса получены динамические характеристики непрерывных СС и на их основе и с использованием метода усреднения исследованы статистические характеристики этих систем.
Разработана модель двухконтурной схемы синхронизации в виде схемы Костаса при комбинированном воздействии и найдена дисперсия сигнала фазового рассогласования при двух моделях сигнальной формы.
Общая методика исследований. Разрабатываемые в диссертации методы анализа динамических и статистических характеристик непрерывных и дискретных СС базируются на общих положениях качественных методов теории систем автоматического управления и теории разностных уравнений, теории марковских процессов и цепей.
Для решения поставленных задач используется компьютерное моделирование, численное решение нелинейных стохастических разностных уравнений.
Разработанные методы и алгоритмы анализа статистических характеристик непрерывных и дискретных, в том числе и цифровых, СС ориентированы на использование персональных компьютеров.
Практическая ценность диссертации
В диссертации разработаны имитационная модель СС и методики исследования, позволяющие определить основные статистические характеристики различных непрерывных и дискретных СС. Разработаны алгоритмы для расчёта статистических характеристик; созданные автором программы апробированы в МГТУ им. Н.Э. Баумана, Институте криптографии, связи и информатики Академии ФСБ России, в С.-Петербургском Государственном Университете аэрокосмического приборостроения, а также в ОАО "Концерн "Созвездие".
На основе разработанных методик и алгоритмов автором создано программное обеспечение для анализа статистических характеристик различных непрерывных и дискретных систем. Разработанные программы позволяют оптимизировать параметры фильтра в цепи управления с целью обеспечения заданных статистических свойств непрерывных и дискретных СС при воздействии полезного сигнала и помехи.
Предложенные и развитые в диссертации методики и разрабатываемые на их основе алгоритмы и программы могут быть использованы в научно-исследовательских и опытно-конструкторских работах для анализа статистических свойств непрерывных, дискретных СС и синтеза дискретных СС различного назначения.
Внедрение результатов работы осуществлено в:
НИР «Перспектива - СЧ» (ОАО «Концерн Созвездие»).
НИР [Синхронизация в радиосвязи и навигации, 2007 г.,
ГР 01200710182], на кафедре «Автономные информационные и управляющие системы» МГТУ им Н.Э. Баумана.
3. Учебные процессы.
3.1. Лабораторные работы на кафедре «Автономные информационные и
управляющие системы» МГТУ им Н.Э. Баумана.
Учебное пособие [6].
Институт криптографии, связи и информатики (ИКСИ) Академии ФСБ.
3.4. С.-Петербургский Государственный Университет аэрокосмического
приборостроения.
Апробация работы. Основные результаты работы докладывались на научно-технической конференции РНТОР и ЭС им. А.С. Попова, 2008, вып. №63, с.268-270., на семинарах кафедры СМ-5 МГТУ им. Н.Э.Баумана, а также на научных семинарах кафедры «Компьютерной математики и программирования» ГУАП (С.-Петербург, 2009 и 2010 г.).
Публикации. Основные результаты диссертации изложены в 9 работах, из них 1 отчет по НИР и 4 работы опубликовано в научных изданиях, входящих в Перечень ВАК.
Объём и структура диссертации.
Диссертация состоит из введения, пяти разделов, заключения, списка литературы (80 наименований), приложения и изложена на 163 листах машинописного текста, включая 48 листов иллюстраций.
Основные понятия информационного поиска
Под текстовым корпусом в современной лингвистике понимается ограниченный в размере набор текстов, пригодный для машинной обработки и отобранный так, чтобы наилучшим образом представлять языковое множество[83]. Похожий смысл имеет понятие коллекции текстовых документов. В данной работе будет использоваться термин «корпус». Информационный поиск - процесс поиска в больших корпусах документов неструктурированных данных, соответствующих информационной потребности пользователя[27]. Информационная потребность — необходимость в информации, выражаемая в информационном запросе, т. е. запросе к информационно-поисковой системе. Информационно-поисковая система[53] (ИПС) — автоматизированная система, предоставляющая возможность поиска в корпусе документов, как правило, текстовых, неструктурированных. Если документ семантически соответствует запросу, то его называют релевантным этому запросу. Хранилищем данных в ИПС служит индекс - информационный массив, в котором хранятся результаты анализа документов в удобной для дальнейшей обработки форме. «Индексный терм» — слово или термин, которое сохраняется в индексе и считается значимым при информационном поиске (в отличие от «стоп-слов», которые отбрасываются при обработке текста). Индексация — процесс создания индекса из корпуса документов. Под термином в данной работе понимается слово или словосочетание на естественном языке, описывающее какое-либо понятие предметной области. Назовем словарем предметной области совокупность терминов этой области, словарем документа — совокупность терминов этого документа, словарем корпуса — совокупность словарей всех документов, входящих в этот корпус. Если термин относится к той же предметной области, что и документ, в котором он употребляется, то назовем такой термин доминантным для этого документа. Под информационной технологией в данной работе понимается процесс, использующий совокупность средств и методов сбора, обработки и передачи данных для получения информации нового качества о состоянии объекта, процесса или явления. На рис. 2 представлена типовая структура информационной технологии индексации и поиска текстовых документов, использующейся в современных поисковых системах (в конкретных программных реализациях отдельные этапы могут отсутствовать). Агент или краулер (crawler) - программный модуль, который обходит Веб или заданный список директорий на жестком диске, посылая новые или обновившиеся страницы на сервер, где они индексируются. Агента называют также поисковым роботом или пауком. Одно из популярных определений агента заключается в следующем: «Агент - аппаратная или программная сущность, способная действовать в интересах достижения целей, поставленных перед ним владельцем и/или пользователем»[12,85]. В. Б. Тарасов[54] выделяет два типа агентов: материальные (например, роботы) и виртуальные, существующие только в программной среде (software robots или softbots). Агент ИПС является мобильным виртуальным агентом -программой, которая покидает клиентский компьютер и перемещается на удаленный сервер для выполнения своих действий, после чего возвращается обратно.
Основные определения
С помощью теоретико-множественного моделирования представим текстовый документ в виде D= T,W , где T-{tt \i = l...m} - множество доминантных терминов документа, W {wl\i = l...m} - множество весов терминов, показывающих важность термина tt для документа D. Данная модель основана на модели, которая в англоязычной литературе называется «набор слов»[24] (bag of words). Корпус текстовых документов обычно представляется в виде матрицы С «термин-документ» вида К текстовому корпусу применимо определение системы — совокупность взаимосвязанных элементов, объединенных единством цели (или назначения) и функциональной зависимостью, причем свойство самой системы не сводится к сумме свойств составных элементов[32]. Корпус обладает свойствами системы: расчленимостью, целостностью, связанностью, неаддитивностью[55]. Таким образом, корпус можно рассматривать как систему, а термины и документы — как системные признаки корпуса. В данной работе предлагается представление корпуса в виде семантической модели А (рис. 13): где D = {D{ і = l...ri} - множество документов корпуса; Т = {tf / = \...m) - множество терминов корпуса; SD =(s )(i— \,...,n;j = 1,...,п) - матрица, в которой элемент s? отражает меру сходства между документами Di и D-; S =(sy) (i = l,...,m;j = 1,...,m) - матрица, в которой элемент s- отражает меру сходства между терминами /,. и t,; StD = (s P) (і = 1,...,m;j = 1,...,и) - матрица, в которой элемент s P отражает меру сходства между термином ti и документом Dj. Предложенная семантическая модель позволяет представить корпус в виде взвешенного графа G= X,R , где X= D,T - множество вершин графа, состоящее из множества документов корпуса и множества входящих в них терминов, R= RD,Rl ,RtD - множество ребер, соединяющих документы и термины между собой и друг с другом, и определена функция w: R - 9Ї, на множестве ребер принимающая значения в действительных числах. Ребро (Di}Dj)sRD между вершинами Д. є и DjeD существует, если s? є, где є 0 - заданный порог. Вес этого ребра - значение s?. Аналогично, ребро (t t eR1 между вершинами /,-еГ и t- є Т существует, если s\j є , а ребро (tf,D.)eRtD между вершинами tteT и DjeD существует, если s P єш, где є О и є О - заданные пороги. Весами этих ребер являются соответственно значения s\j и s P. Для удобства дальнейшего изложения обозначим подграф графа G, состоящий только из документов и ребер между ними, GD = D,RD , а подграф графа G, состоящий только из терминов и ребер между ними, G = T,R . Представление корпуса документов в виде графа G= X,R позволяет применить для его анализа графовые алгоритмы и математический аппарат теории графов, а также выделить системные характеристики корпуса и его элементов.
Поиск по корпусу
Постановка классической задачи информационного поиска в корпусе выглядит следующим образом: Для заданного запроса Тд = {tf ,...,tq q}необходимо построить подграф ребер, соединяющих документы и термины между собой и друг с другом, причем Релевантность документа Д. є/)9 запросу q может быть определена по стандартным формулам векторной модели информационного поиска или по формуле Алгоритм уточнения запроса пользователя — человеко-машинная интерактивная процедура, в процессе которой существующий запрос дополняется новыми терминами по мере вербализации информационной потребности пользователя. В ходе дальнейшего изложения термины «уточнение запроса» и «расширение запроса» будут использоваться как синонимы, поскольку алгоритм реализует как пополнение запроса новыми терминами, так и возможное удаление из запроса кластеров не интересующих пользователя терминов. Для уточнения запроса целесообразно предоставить пользователю возможность навигации по графу G . При этом может быть использован один из способов обхода графа, в частности, поиск в глубину или в ширину. т-ым уровнем детализации термина ґ, а множество — контекстом термина /, состоящим из пЕ уровней. Обозначим множество терминов, входящих в контекст Е, ,...,?-. Входными данными алгоритма являются: J максимальное количество терминов в запросе N ; минимальная степень вершины для спуска на следующий уровень максимальный эксцентриситет вершины для спуска на следующий уровень есстт; минимальная энтропия термина для спуска на следующий min уровень Яг Вариант алгоритма, использующий поиск в глубину, требует участия пользователя уже при начале работы алгоритма, однако позволяет точнее подобрать множество терминов. Пользователь осуществляет обход графа, указывая, какие термины его интересуют. В этом случае достижение критериев останова алгоритма LmWi, Nmax, degmin, eccmzx , #min носит рекомендательный для пользователя характер. В этом варианте алгоритма контексты терминов пересекаться не могут (рис. 19, а), что позволяет сократить ручную работу пользователя. Вариант алгоритма, использующий поиск в ширину, сводит участие пользователя в процессе построения расширенного запроса к минимуму, реализуя автоматическое построение контекста. Пользователь задает критерии останова Zmax, Nmax, degmin, есстах, #min, и обход графа осуществляется автоматически до тех пор, пока соответствующие параметры имеют допустимые значения. При этом контексты терминов могут пересекаться (рис. 19, б). Если поисковый запрос задан в виде то может быть использован как поиск в глубину, так и поиск в ширину, а если поисковый запрос задан в виде то используется только поиск в ширину, т.к. при поиске в глубину отсутствие пересечений между контекстами дало бы в результате пустое множество.
Описание разработанного программного продукта
Для реализации принципов и алгоритмов, описанных в главах 2-3, было разработано веб-приложение на языке программирования С# по технологии ASP.NET на платформе Microsoft .NET Framework. В качестве среды разработки была выбрана Microsoft Visual Studio 2010 Ultimate, в качестве сервера базы данных - Microsoft SQL Server. Программный продукт имеет клиент-серверную архитектуру. Физическая архитектура автоматизированной системы показана на диаграмме развертывания (рис. 27). Автоматизированная система содержит четыре пользовательские модуля (агент, индексация, анализ, поиск) и модуль администрирования. Пользовательские модули устанавливаются на каждый из сайтов, участвующих в системе. Отдельно устанавливается система администрирования. Информационный агент по заданному расписанию осуществляет обход того сайта, на котором он установлен, или только заданных ему страниц. Агент необходим по той причине, что различные системы управления контентом, установленные на сайтах, имеют различные подходы к организации иерархии директорий, поэтому простого указания директории для индексирования недостаточно. Задача агента - получить адреса документов и их параметры (в случае автореферата параметрами будут автор работы, дата защиты, специальность, название работы и т. д.) и сохранить их в базе данных. Модуль индексации, используя заданные ему параметры (минимальный порог TF IDF, C-value и т.д.), строит индекс для файлов, найденных агентом, т. е. выделяет в каждом тексте доминантные термины и сохраняет информацию о них и их вхождениях в базе данных. Модуль анализа проводит латентный семантический анализ и сохраняет в базе данных полученные значения сходства терминов и документов и веса каждого термина в документе. Таким образом в базе данных хранится построенная этим модулем семантическая модель. Модуль поиска в интерактивном режиме помогает пользователю сформулировать запрос, дополнив его новыми терминами, и осуществляет поиск в индексе релевантных запросу документов. Доступ к интерфейсу модулей агента, индексации и анализа осуществляется владельцем веб-ресурса, к интерфейсу модуля пользователя -любым посетителем веб-ресурса. Настройка прав доступа к системе осуществляется администратором с помощью модуля администрирования. База данных хранится на сервере баз данных. Таким образом, благодаря использованию общей базы данных каждый из веб-серверов индексирует только собственный файловый архив, но имеет доступ к индексу, содержащему данные о файловых архивах всех веб-серверов, участвующих в системе. Работа пользовательских модулей в пределах веб-сервера показана на диаграмме потоков данных (рис. 28). В системе существуют три категории пользователей: 1. Администратор системы, настраивающий права доступа для владельцев веб-ресурсов, участвующих в системе, и отвечающий за функционирование системы. 2. Владелец веб-ресурса, настраивающий обработку данных своего веб-ресурса. 3. Посетитель веб-ресурса, осуществляющий поиск по текстовому корпусу. Основные функции, доступные пользователям системы, показаны на диаграмме прецедентов (рис. 29). Рис. 29. Диаграмма прецедентов Администратору доступны функции «Регистрация владельцев веб-ресурсов» и «Настройка ролей и прав доступа». Администратор регистрирует участников системы и назначает им права доступа. Владельцу веб-ресурса доступны функции, предоставляемые модулями агента, индексации и анализа, а также настройка этих модулей. Посетитель веб-ресурса может осуществлять поиск по текстовому корпусу, задавая исходный поисковый запрос, выбирая дополнительные термины и удаляя лишние. Определив индекс как информационный массив, в котором в сжатом виде хранятся результаты анализа текстовых документов, составим его структуру способами информационно-логического моделирования. Мифологическая модель, отображающая основные сущности системы, их атрибуты и связи между ними, представлена на диаграмме «сущность-связь» (рис. 30). Матрицы SD и S хранятся в индексе в таблицах «Сходство документов» и «Сходство терминов» соответственно. Значения из матрицы StD хранятся в таблице «Вхождение термина». Сущность «Термин» содержит собственно термин в начальной форме (главное слово в словосочетании поставлено в форму именительного падежа и единственного числа, а зависящие от него прилагательные, если они есть, согласуются с ним) и количество документов, в которых употребляется данный термин. Сущность «Документ» содержит путь к файлу, дату его последней индексации, количество слов, употреблений терминов и уникальных терминов в документе, размер файла, фамилию, имя и отчество автора работы, название работы, дату защиты, код специальности, название отрасли наук, по которой защищалась работа, код диссертационного совета, название организации, в которой выполнялась работа, адрес веб-страницы, на которой находятся сведения о работе, и время в секундах, затраченное на индексацию файла. Сущность «Вхождение термина» содержит информацию о вхождении термина в документ: код термина, код документа, частоту вхождения термина в документ, меру C-value для термина в этом документе, меру TF (Term Frequency), вес термина в документе, определенный с помощью латентного семантического анализа, и меру TF IDF. Меры TF и TF IDF хранятся вместе для ускорения расчетов.
