Содержание к диссертации
Введение
Глава 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 Модели процесса поиска информации 31
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
4.6.3 Латентный семантический анализ распределенного корпуса. 103
Приложение 120
- Основные понятия информационного поиска
- Основные определения
- Поиск по корпусу
- Описание разработанного программного продукта
Введение к работе
Современный этап развития науки характеризуется увеличением темпа роста научного знания, в том числе представленного документально. Ежегодно в мире появляется 5 млрд. научных книг и статей, 250 тыс. диссертаций и отчетов[17]. Фонд диссертаций Российской государственной библиотеки, в котором хранятся отечественные кандидатские и докторские диссертации с 1944 года, на 1 января 2010 года насчитывал свыше 976 тыс. экземпляров[21].
Данная тенденция будет продолжаться. 8 июля 2010 г. на заседании Президентского совета по развитию информационного общества президент РФ Д.А.Медведев сказал: «Особое внимание... должно быть уделено формированию единой базы научных диссертаций в электронном виде и обеспечению прозрачности процедуры их защиты»[14].
На момент написания данной работы электронная библиотека диссертаций РГБ содержала более 620 000 полных текстов диссертаций и авторефератов, а электронный архив авторефератов докторских диссертаций на сайте Высшей аттестационной комиссии - почти 10 000 авторефератов.
Создание базы диссертаций или авторефератов ведет к необходимости их автоматизированного анализа для повышения эффективности доступа к этим документам. Однако современные информационно-поисковые системы стремятся в первую очередь к повышению скорости обработки запросов пользователей и поэтому используют достаточно простые алгоритмы и эвристики.
Важнейшим недостатком большинства существующих информационно-поисковых систем является отсутствие интеллектуального анализа данных, что ведет к большим затратам на поиск данных. Как указывалось в работе[17, с. 119], «по расчетам американских ученых, если открытие или изобретение предполагает стоимость 10 тыс. долларов, то их дешевле открыть заново, нежели отыскать в завалах информации».
Вопросами автоматизации анализа естественного языка занимались многие ученые как в нашей стране, так и за рубежом:
• в области автоматического понимания текстов — Р. Шенк, Э. В. Попов, Н. Н. Леонтьева, Э. Ф. Скороходько;
• в области разработки информационно-поисковых систем -П. И. Браславский, И. Е. Кураленок, И. С. Некрестьянов, Б. В. Добров, Д. В. Ланде, Н. В. Лукашевич;
• в области разработки семантических моделей текста -Т. А. Гаврилова, В. Ф. Хорошевский, А. Е. Ермаков, A. Maedche, Е. Alfonseca, Е. Agirre; • в области выделения терминов из текста — Е. И. Большакова, К. Frantzi.
Работы этих авторов привели к созданию ряда методов анализа естественного языка, позволяющих в автоматизированном режиме обрабатывать неструктурированные тексты.
Однако существующие модели информационного поиска обладают рядом недостатков: традиционные модели отличаются низкой эффективностью поиска, сложностью формулировки запроса, новые модели - необходимостью создания вручную хранилищ знаний, используемых для поиска.
Таким образом, в настоящее время существует актуальная научная и техническая задача, состоящая в разработке методик, позволяющих автоматизировать анализ представленного документально научного знания. Решение такой задачи позволит повысить эффективность обработки информации при анализе научного знания.
Объектом исследования является корпус документов научной полнотекстовой информации.
Предмет исследования - методы, модели и алгоритмы обработки текстовой информации.
Целью настоящей работы является повышение эффективности аналитической обработки научной информации, представленной в виде распределенных корпусов текстовых документов.
Поставленная цель достигается решением следующих задач:
1. Провести системный анализ процесса обработки неструктурированной текстовой информации для выявления системных характеристик корпуса документов.
2. Разработать семантическую модель корпуса документов и алгоритм ее построения на основе латентно-семантического анализа, использующий статистические меры оценки веса терминов. 3. Разработать алгоритм уточнения поискового запроса на сгенерированной семантической модели корпуса, использующий поиск в глубину и в ширину и кластерный анализ множества терминов.
4. Модифицировать существующую информационную технологию поиска и анализа документов путем применения разработанных алгоритмов и разделения этапа семантического анализа текста на локальный и глобальный этапы.
5. Апробировать модифицированную информационную технологию обработки информации с использованием вновь разработанной автоматизированной системы.
Методы исследования. Для решения поставленной задачи применялись методы системного анализа, линейной алгебры, кластерного анализа, теории графов, теории множеств, теории информации, теории алгоритмов.
Научная новизна.
1. По результатам теоретико-множественного и теоретико-информационного анализа выделены системные характеристики корпуса документов, позволяющие расширить набор параметров информационного поиска.
2. Модифицирована информационная поисковая технология в части анализа и систематизации распределенного научного знания, позволяющая в процессе интеллектуального анализа неструктурированной текстовой информации генерировать семантические модели корпуса документов.
3. Разработан алгоритм построения трехмерной семантической модели корпуса документов, позволяющей представить его в форме графа для дальнейшей визуализации и анализа с использованием введенной системы количественных оценок свойств корпуса.
4. Разработан алгоритм уточнения поискового запроса, осуществляющий кластерный анализ множества терминов и эмулирующий движение по семантической модели корпуса документов как поиск на графе в глубину и ширину. Предложены критерии останова: достижение заданного уровня энтропии, измеряющей детализацию термина, достижение заданного порога количественных характеристик термина.
Практическая ценность работы. Результаты работы могут применяться для анализа как распределенных, так и централизованных хранилищ данных и использоваться для обработки любых документальных знаний, содержащих персоналии, названия организаций, даты и другие устойчивые выражения.
Реализация результатов работы. Результаты исследования реализованы в госбюджетных научно-исследовательских работах ФГОУ ВПО «Астраханский государственный технический университет» «Теоретический анализ и математическое моделирование информационных систем», «Теоретический анализ и математическое моделирование систем поддержки принятия управленческих решений»; внедрены в учебный процесс Астраханского государственного технического университета и в муниципальном бюджетном учреждении г. Астрахань «Информационно-аналитический центр»
На основе модифицированной информационной технологии разработана автоматизированная система «Информационно-аналитическая система интеллектуального анализа текстовых электронных ресурсов», прошедшая государственную регистрацию.
Личный вклад автора. В работах, выполненных в соавторстве, автору принадлежат формализация задачи, построение моделей, разработка алгоритмов, проектирование и реализация программного обеспечения.
Апробация научных результатов. Основные положения докладывались и обсуждались на конференциях студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2007-2009), XIV-XVI Международных молодежных научных форумах «Ломоносов» (Москва, 2007-2009), V Всероссийской межвузовской конференции молодых ученых (Санкт-Петербург, 2008), XXI-XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Саратов, 2008; Псков, 2009), I Международной научно-практической конференции «Эволюция системы научных коммуникаций ассоциации университетов прикаспийских государств» (Астрахань, 2008), Всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Москва, 2009), V Всероссийской научно-инновационной конференции студентов, аспирантов и молодых ученых (Москва, 2009), 54-ой Научно-практической конференции профессорско-преподавательского состава Астраханского государственного технического университета (Астрахань, 2010), Международной научно-практической конференции «Фундаментальные и прикладные исследования университетов, интеграция в региональный инновационный комплекс» (Астрахань, 2010).
Публикации. Основные положения диссертационной работы отражены в 16 опубликованных научных работах, среди которых 3 статьи в журналах, рекомендованных ВАК, 1 свидетельство о регистрации программы для ЭВМ и 12 публикаций в сборниках международных, всероссийских научных конференций.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав основного текста, заключения, списка литературы из 96 наименований и 2 приложений. Общий объем работы 107 страниц машинописного текста, который включает 38 рисунков, 16 таблиц и 39 формул.
Во введении обоснована актуальность темы, определены цель и задачи исследования.
Первая глава посвящена обзору и анализу результатов исследований по системному анализу и автоматизированной обработке неструктурированной текстовой информации. Рассмотрены существующие типы моделей информационного поиска, типовая архитектура современных информационно-поисковых систем. Практика показывает слабую востребованность методов семантической обработки текстовой информации, поскольку они опираются на онтологии, тезаурусы или семантические сети, создание которых требует привлечения экспертов. Практическое применение получили методы, использующие статистическую обработку текста и не осуществляющие его семантический анализ.
Необходимым компонентом информационной технологии обработки научного знания является семантический анализ. При этом наиболее перспективными для обработки научного знания являются методы семантического анализа текста, не использующие для анализа никаких хранилищ знаний, собирающие все необходимые данные только из анализируемого текстового корпуса и сводящие к минимуму участие эксперта в процессе обработки.
Для оценки эффективности информационного поиска общепринятыми являются метрики, использующиеся конференцией по оценке систем текстового поиска Text Retrieval Conference (TREC) и Российским семинаром по оценке методов информационного поиска (РОМИП): полнота, точность, аккуратность, ошибка и F-мера. Данные характеристики взяты за основу для оценки достижения цели исследования.
Во второй главе произведен системный анализ неструктурированной текстовой информации, представленной в виде корпуса текстов научного знания, позволивший отделить ряд системных характеристик объекта исследования. Предложенные характеристики могут быть использованы для детализации поисковых запросов.
Разработана трехмерная семантическая модель корпуса документов, позволяющая представить корпус в виде взвешенного графа для последующего анализа. Модель, включающая множества документов, терминов и набор матриц, определяющих меры сходства между компонентами модели, отражает системные закономерности и связи, характерные для корпуса документов.
Теоретико-информационный анализ корпуса позволяет сформулировать новую системную характеристику, определяющую степень детализации термина, - информационную энтропию.
Разработан алгоритм построения семантической модели корпуса документов, включающий три этапа обработки информации: формирование списка терминов корпуса, определение для каждого документа доминантных терминов, латентный семантический анализ.
Разработанная семантическая модель позволяет применить к анализу корпуса документов алгоритмы поиска на графе, а также расширить набор параметров информационного поиска выделенными системными характеристиками.
В третьей главе описан разработанный алгоритм уточнения запроса пользователя. Описана модифицированная информационная поисковая технология.
Сформулирована классическая задача информационного поиска на вновь разработанной семантической модели.
Решена задача уточнения поискового запроса путем добавления к нему новых терминов, семантически связанных с терминами запроса.
Рассмотрены два варианта алгоритма уточнения поискового запроса: с использованием поиска в ширину и с использованием поиска в глубину. В качестве критериев останова алгоритма предложено использовать выделенные в работе системные характеристики элементов корпуса, расширяющие набор параметров информационного поиска
В целях экономии вычислительных ресурсов при обработке корпуса по описанным выше принципам предлагается использовать распределенную обработку данных и проводить индексацию документов непосредственно на тех веб-серверах, на которых они находятся. Распределенная обработка данных и разработанные алгоритмы были использованы для модификации существующей информационной поисковой технологии путем разделения этапа семантического анализа текста на локальный и глобальный этапы и применения алгоритмов: построения семантической модели - для семантического анализа, расширения поискового запроса - на этапе анализа запроса.
В четвертой главе рассмотрена архитектура разработанной автоматизированной системы и описан эксперимент по сравнению разработанной системы с одним из популярных программных аналогов.
Эксперимент показал, что по ряду параметров разработанная автоматизированная система опережает автоматизированную систему «Персональный поиск Яндекса», а по остальным параметрам несущественно отстает от него.
В приложениях приведены свидетельство о государственной регистрации программы для ЭВМ и акты о внедрении результатов научной работы.
Основные понятия информационного поиска
Под текстовым корпусом в современной лингвистике понимается ограниченный в размере набор текстов, пригодный для машинной обработки и отобранный так, чтобы наилучшим образом представлять языковое множество[83]. Похожий смысл имеет понятие коллекции текстовых документов. В данной работе будет использоваться термин «корпус». Информационный поиск - процесс поиска в больших корпусах документов неструктурированных данных, соответствующих информационной потребности пользователя[27]. Информационная потребность — необходимость в информации, выражаемая в информационном запросе, т. е. запросе к информационно-поисковой системе. Информационно-поисковая система[53] (ИПС) — автоматизированная система, предоставляющая возможность поиска в корпусе документов, как правило, текстовых, неструктурированных. Если документ семантически соответствует запросу, то его называют релевантным этому запросу. Хранилищем данных в ИПС служит индекс - информационный массив, в котором хранятся результаты анализа документов в удобной для дальнейшей обработки форме. «Индексный терм» — слово или термин, которое сохраняется в индексе и считается значимым при информационном поиске (в отличие от «стоп-слов», которые отбрасываются при обработке текста). Индексация — процесс создания индекса из корпуса документов. Под термином в данной работе понимается слово или словосочетание на естественном языке, описывающее какое-либо понятие предметной области. Назовем словарем предметной области совокупность терминов этой области, словарем документа — совокупность терминов этого документа, словарем корпуса — совокупность словарей всех документов, входящих в этот корпус. Если термин относится к той же предметной области, что и документ, в котором он употребляется, то назовем такой термин доминантным для этого документа. 1.2 Информационная технология поиска текстовых документов Под информационной технологией в данной работе понимается процесс, использующий совокупность средств и методов сбора, обработки и передачи данных для получения информации нового качества о состоянии объекта, процесса или явления. На рис. 2 представлена типовая структура информационной технологии индексации и поиска текстовых документов, использующейся в современных поисковых системах (в конкретных программных реализациях отдельные этапы могут отсутствовать). 1.2.1 Агент Агент или краулер (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). Корпус текстовых документов обычно представляется в виде матрицы С «термин-документ» вида где tx...tm -доминантные термины всех документов корпуса; Д...Д, - документы корпуса; w.j — веса терминов в соответствующих документах. К текстовому корпусу применимо определение системы — совокупность взаимосвязанных элементов, объединенных единством цели (или назначения) и функциональной зависимостью, причем свойство самой системы не сводится к сумме свойств составных элементов[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 позволяет применить для его анализа графовые алгоритмы и математический аппарат теории графов, а также выделить системные характеристики корпуса и его элементов.
Поиск по корпусу
Алгоритм уточнения запроса пользователя — человеко-машинная интерактивная процедура, в процессе которой существующий запрос дополняется новыми терминами по мере вербализации информационной потребности пользователя. В ходе дальнейшего изложения термины «уточнение запроса» и «расширение запроса» будут использоваться как синонимы, поскольку алгоритм реализует как пополнение запроса новыми терминами, так и возможное удаление из запроса кластеров не интересующих пользователя терминов. Для уточнения запроса целесообразно предоставить пользователю возможность навигации по графу G . При этом может быть использован один из способов обхода графа, в частности, поиск в глубину или в ширину. Вариант алгоритма, использующий поиск в глубину, требует участия пользователя уже при начале работы алгоритма, однако позволяет точнее подобрать множество терминов. Пользователь осуществляет обход графа, указывая, какие термины его интересуют. В этом случае достижение критериев останова алгоритма 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).
