Содержание к диссертации
Введение
Глава 1. Проблемы автоматизации документального поиска в гипертекстовых ресурсах Интернет 10
1.1 Структура гипертекстовых ресурсов Интернет 10
1.2 Анализ современных средств поиска в гипертекстовых ресурсах Интернет 16
1.3 Методы оценки эффективности автоматизированного документального поиска 33
1.4 Выводы и постановка задачи 38
Глава 2. Повышение эффективности поиска информации в ресурсах Интернет на основе методов автоматического индексирования 41
2.1 Задача автоматического индексирования гипертекстовых документов 41
2.2 Анализ моделей документального поиска 43
2.3 Разработка метода определения весов терминов в документах 53
2.4 Методика автоматического индексирования 68
2.5 Исследование эффективности предложенного метода определения весов терминов 70
Выводы 74
Глава 3. Разработка методики автоматизированного формирования запроса 76
3.1 Поиск информации с уточнением запроса 76
3.2 Разбиение документов на группы 78
3.3 Выделение ключевых терминов в кластерах документов 93
3.4 Методика автоматизированного формирования запроса 94
3.5 Исследование эффективности методики автоматизированного формирования запроса 100
Выводы 107
Глава 4. Применение разработанных методов автоматизированного документального поиска в задачах информационно-аналитического обеспечения 109
4.1 Автоматизация поиска и отбора Интернет-ресурсов в системе анализа инновационных проектов 109
4.2 Применение разработанных методов при создании агентов Интернет 120
Выводы 123
Заключение 124
Литература 126
Приложение 136
- Анализ современных средств поиска в гипертекстовых ресурсах Интернет
- Разработка метода определения весов терминов в документах
- Выделение ключевых терминов в кластерах документов
- Применение разработанных методов при создании агентов Интернет
Введение к работе
Актуальность проблемы. Одним из основных источников информации сегодня являются ресурсы глобальной информационной сети Интернет, и обеспечение доступа к информации обычно связывается с обеспечением доступа именно к ресурсам Интернет. Развитие сети Интернет в наши дни связано в первую очередь с ростом объема информационных ресурсов и повышением качества инфраструктуры физических сетей. В течение следующих нескольких лет основными тенденциями дальнейшего развития будут дальнейший рост объемов ресурсов, накопление информации и увеличение числа пользователей имеющих доступ к глобальной информационной сети.
Проблемы поиска и извлечения полезной информации в условиях информационного переполнения Интернет и хаотичности организации данных становятся все более актуальными. Ресурсы Интернет, основой которых является распределенная гипертекстовая база данных, все больше используются в исследованиях, коммерции, информационном обслуживании и многих других областях. Без эффективных механизмов поиска и обработки информации огромные ресурсы глобальной сети оказываются бесполезными.
Основной технологией, обеспечивающей использование ресурсов Интернет в практической деятельности, является автоматизированный поиск информации. Этой проблеме посвящены многие коммерческие и исследовательские проекты, особое внимание уделяется расширению интеллектуальных возможностей средств поиска. Это связано с тем, что поиск нужной информации в Интернет крайне затруднен и рациональное использование его ресурсов все больше осложняется. Автоматизированные системы поиска информации в Интернет необходимы уже сейчас и будут еще более востребованы в ближайшем будущем.
Существующим автоматизированным поисковым системам, занимающимся глобальным индексированием и поиском информации в Интернет становится все трудней поддерживать свой индекс в актуальном состоянии. Объем найденной по запросу информации зачастую таков, что для его анализа требуется довольно много времени и труда специалистов. Кроме этого существующие глобальные поисковые средства почти не предоставляют услуг по анализу найденной информации.
Таким образом, совершенствование автоматизированных средств поиска информации в Интернет является важной и актуальной задачей для эффективного использования гипертекстовых ресурсов Интернет и дальнейшего развития глобальной информационной сети.
Поиск в гипертекстовых ресурсах Интернет основывается на методах документального поиска возникших еще до появления глобальной информационной сети. Этой проблеме посвящено большое количество работ. Еще в 1949 году Г. Зипф опубликовал работу, в которой описал законы, характеризующие внутреннюю структуру текста. X. Лун использовал законы Зипфа и сформулировал правила для определения значимых слов в тексте документа. Идеи, предложенные X. Луном, легли в основу многих работ его последователей. В нашей стране под руководством B.C. Чернявского и Д.Г. Лахути в шестидесятые годы прошлого века была создана первая в мире информационно-поисковая система с автоматическим индексированием документов.
В основе автоматизированного документального поиска лежит понятие модели поиска. В настоящее время разработано много различных моделей. Дж. Сэлтона, одного из основоположников документального поиска, можно отнести к авторам векторной модели документального поиска, кроме этого он также проделал большую работу в области автоматического индексирования
документов. С.Джонс СИ. Робертсон описали вероятностную модель документального поиска. Разработке латентно-семантической модели посвящены работы С.Дамайса, Г.Фурнаса, СДирвестера. В работах Д.О. Аветисяна и Р.Д. Аветисяна описываются энтропийная модель на основе статистической теории связи Шенона и корреляционная модель документального поиска, кроме этого предлагаются подходы к совмещению различных моделей таких как матричная и корреляционная.
Цели и задачи. Целью работы является создание программных средств для повышения эффективности автоматизированного документального поиска в гипертекстовых ресурсах Интернет.
Реализация поставленной цели предполагает решение следующих задач:
Обзор и сравнительный анализ моделей информационного документального поиска в распределенных гипертекстовых базах данных;
Исследование и анализ методов автоматического индексирования гипертекстовых документов;
Разработка метода определения весов терминов в документах при автоматическом индексировании;
Разработка методики автоматизированного формирования запроса;
- Создание программного средства реализующего разработанные методы.
Объект исследования. Объектом исследования являются программные
средства, модели и методы автоматизированного документального поиска в гипертекстовых ресурсах Интернет.
Методы исследования. При проведении исследований в работе использованы алгебраические методы, эвристические приемы и методы кластерного анализа.
Научная новизна. Научная новизна работы заключается в следующем:
разработан метод определения весов терминов в документах при автоматическом индексировании набора документов;
разработан метод определения весов терминов в кластерах при автоматическом индексировании кластеров документов;
разработана методика автоматизированного формирования запроса на основе кластеризации результатов информационного документального поиска;
предложен метод оценки качества распределения ключевых терминов кластеров между документами с использованием коэффициентов точности, полноты и шума, аналогичных коэффициентам использующимся для оценки качества результатов поиска.
Практическая значимость. Результаты проведенных исследований были использованы при создании программных средств. Разработанный метод определения весов терминов при автоматическом индексировании документов обеспечивает более точное дифференцирование терминов индекса документа, что позволяет использовать его для повышения эффективности различных поисковых процессов. Разработанные программные средства позволили использовать предложенные в работе новые методы при создании информационно-аналитической системы использующей информацию Интернет-ресурсов.
Реализация результатов. Разработанные в данной работе программные средства входят в состав информационного и программного обеспечения информационно-аналитической системы сопровождения инвестиционных проектов при исследовании инвестиционных возможностей и технико-экономическом обосновании проектов в Инженерно-техническом центре «ТехИнвестФинанс».
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях студентов, аспирантов и
молодых специалистов МИЭМ, Москва 2001 г., 2002 г., 2003 г., 2004 г.; VII Международной научно-практической конференции МГУ Сервиса «Наука -индустрии сервиса» «Информационные технологии в сфере сервиса», Москва МГУС 2002 г.; X Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании», Пенза 2002 г.; IV Международной ежегодной научно-практической конференции «Информационные технологии XXI века» Москва МГУС 2003 г.
Публикации. По материалам диссертационной работы опубликовано 10 печатных работ.
Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения.
В первой главе рассматриваются вопросы поиска и обработки информации в гипертекстовых ресурсах Интернет. Разбирается структура гипертекстовых ресурсов. Приводится анализ современных средств поиска и обработки информации в Интернет, выделяются существующие проблемы поиска. В заключение главы поставлены задачи исследования.
Во второй главе рассматриваются вопросы индексирования гипертекстовых документов. Определяются задачи автоматического индексирования. Описываются модели документального поиска и проводится их анализ. Предлагается усовершенствованный метод оценки весов терминов в документах на основе анализа существующих методов, и обобщенный алгоритм автоматического индексирования с учетом предложенного метода. Исследуется эффективность предложенного метода.
В третьей главе рассматриваются вопросы автоматизированного формирования запроса. Разбирается задача разбиения документов на группы. Приводится анализ методов автоматической кластеризации документов.
Предлагается метод определения весов терминов в кластерах документов. Предлагается методика автоматизированного формирования запроса на основе кластеризации результатов поиска с использованием разработанного метода оценки весов терминов. Исследуется эффективность предложенной методики.
В четвертой главе рассматривается использование разработанных методов для решения практических задач. Рассматривается информационно-аналитическая система, использующая разработанные методы, и применение разработанной методики в поисковых агентах Интернет.
В заключении подводятся итоги проделанной работы. Перечисляются основные результаты диссертации и следующие из них выводы.
Анализ современных средств поиска в гипертекстовых ресурсах Интернет
Системы поиска информации в Интернет относятся к классу документальных автоматизированных информационных систем.
В нормативно-правовом смысле информационная система определяется как "организационно упорядоченная совокупность документов (массивов документов) и информационных технологий, в том числе и использованием средств вычислительной техники и связи, реализующих информационные процессы" [20]. Автоматизированная система определяется как "Система состоящая из персонала и комплекса средств автоматизации его деятельности, реализующая информационную технологию выполнения установленных функций" [16].
Сейчас можно встретить более универсальные определения информационных систем, учитывающие накопленный опыт их создания и использования, как организованной совокупности программно-технических и других вспомогательных средств, технологических процессов и функционально-определенных групп работников, обеспечивающих сбор, накопление и предоставление информационных ресурсов в определенной предметной области, поиск и выдачу сведений, необходимых для удовлетворения информационных потребностей установленного контингента пользователей - абонентов системы. Информационные системы, в которых представление, хранение и обработка информации осуществляется с помощью вычислительной техники, называются автоматизированными.
По характеру представления и логической организации хранимой информации автоматизированные информационные системы принято разделять на фактографические, документальные и геоинформационные.
Фактографические автоматизированные информационные системы оперируют фактическими сведениями, представленными в виде специальным образом организованных совокупностей формализованных записей данных. Каждая из таких записей отражает сведения, по какому-либо факту или событию.
В геоинформационных автоматизированных системах данные организованны в виде отдельных информационных объектов, привязанных к общей электронной топографической основе.
В документальных автоматизированных информационных системах единичным элементом данных является неструктурированный на более мелкие элементы документ. Основной задачей таких систем является накопление и предоставление пользователю документов, содержание, тематика, реквизиты и т.п. которых соответствуют его информационным потребностям. Таким образом, такие системы можно охарактеризовать как единое хранилище документов с инструментарием для поиска и отбора необходимых документов. Исторически сложилось так, что за документальными автоматизированными системами укоренился термин информационно-поисковые системы, хотя, их следует называть документальные информационно-поисковые системы, поскольку фактографические системы также являются информационно-поисковыми [14].
Информационным документальным поиском называют процедуру отыскания документов содержащих ответ на заданные пользователем вопросы.
В Интернет можно выделить несколько видов документальных информационно-поисковых систем. Основные виды: 1) поисковые системы в Интернет; 2) Интернет каталоги; 3) гибридные системы.
Поисковые системы в Интернет осуществляют индексирование ресурсов Интернет, хранение проиндексированной информации и выдачи пользователю некоторой информации о документах, соответствующих его запросу. Информация может включать название документа, краткое описание документа или его отрывок и ссылку на документ. Все основные операции в поисковых системах автоматизированы. Поисковые системы используют, например, «Яндекс» (www.yandex.ru), «Rambler» (www.rambler.ru), «Google» (www.google.ru).
Основной отличительной чертой каталогов от других видов является то, что регистрация всех ресурсов зависит от людей. Окончательное решение, в какой раздел отнести тот или иной ресурс, какой описание он будет иметь, и какие ключевые слова ему будут соответствовать, решает человек - модератор каталога. Именно поэтому обычно результаты поиска в каталогах дают более релевантные результаты, чем поисковые системы. Поиск обычно осуществляется по описанию ресурса и ключевым словам. Как правило, также в каталоге существует тематическая разбивка на разделы и подразделы. Типичным представителем каталогов является «Yahoo!» (www.yahoo.com).
Гибридные системы совмещают в себе в тех или иных пропорциях каталоги и поисковые системы. Следует отметить, что сегодня все крупные поисковые порталы имеют в своем составе и поисковую систему и каталог, например, каталоги есть и у «Яндекс», «Google» [7].
В поисковых системах принято выделять три основные части: робот, индекс и систему поиска (рисунок 1.1). Робот - программа, которая, используя определенную стратегию, загружает гипертекстовые страницы с интернет-серверов, считывает полностью или частично их содержимое и индексирует его. Индекс представляет собой хранилище всех проиндексированных документов. Обычно документы хранятся в формализованном виде.
Система поиска отвечает за отбор документов в индексе, соответствующих запросу пользователя и выдачу информации пользователю.
Поисковые системы выполняют операцию поиска на основе поступившего от пользователя запроса. Запрос пользователя определяется его информационной потребностью.
Разработка метода определения весов терминов в документах
Основным этапом автоматического индексирования является определение весов терминов в документах. Рассмотрим эту задачу в рамках векторной модели документального поиска:
Эффективность автоматизированного документального поиска определяется величиной Д, при уменьшении Д эффективность увеличивается, т.е. формальная релевантность р, определяемая поисковой системой, должна совпадать с фактической релевантностью а, определяемой пользователем.
Так как фактическая релевантность а не может быть определена без участия пользователя, оценка эффективности поиска может быть проведена только экспериментальным путем.
В векторной модели формальная релевантность р зависит от формального представления запроса q, формального представления документа d и функции определения формальной релевантности ср. Запрос q представляет собой вектор размерности Nt, значение элементов вектора запроса определяется возможностями языка запросов поисковой системы. Документ d также представляет собой вектор размерности Nt, значение элемента вектора запроса соответствует весу термина. Вес термина wtJ определяется с использованием
функции /(Md) на основе матрицы сопряженности «документ - термин» Md, значения элементов которой соответствуют количеству раз, которое термин встретился в документе. В качестве функции формальной релевантности р используется скалярное произведение векторов запроса и документа, в этом случае наибольшее значение получают те документы, для которых ключевые термины, указанные в запросе, имеют наибольшие веса.
Таким образом, задача повышения эффективности автоматического индексирования сводится к определению такой функции /(Md), при которой А стремится к нулю.
В основе автоматического определения весов терминов векторной модели лежит следующий подход. Каждый документ набора рассматривается как некоторый объект из группы объектов, термины как параметры объекта, а количество раз, которое термин встретился в документе, как числовые значения параметров, тогда определение веса термина в документе сводится к выявлению параметров наилучшим образом характеризующих данный объект среди других объектов группы. Обозначим данный подход как подход характеризующего термина. С другой стороны наибольшие веса в документе должны быть у терминов, которые пользователь будет использовать в запросе для поиска этого документа. Таким образом, эффективность методов автоматического индексирования также определяется экспериментальным путем.
Конечная эффективность методов автоматического индексирования реализованных с использованием подхода характеризующего термина определяется, во-первых, соответствием самого метода подходу, т.е. возможности метода выделять характеризующие термины в документах набора, а во-вторых, соответствием подхода к конкретному набору документов и условиям поиска. Например, если набор состоит в основном из документов, посвященных одной тематике, и пользователь хочет найти документы, посвященные этой тематике, то ключевые термины, указанные им в запросе, не будут обладать наибольшими весами при использовании подхода характеризующего термина. Кроме этого, при выборе терминов для запроса пользователь чаще руководствуется семантическими аспектами документов, чем статистическим распределением терминов в документах. Рассматриваемый подход дает хорошие результаты при поиске одного документа в наборе разнородных документов. Из этого следует, что низкая эффективность метода определения весов терминов может быть вызвана плохим соответствием подхода условиям поиска и набору документов, при хорошем соответствии метода подходу.
Рассмотрим основные методы определения весов терминов в документах с точки зрения соответствия их описанному подходу.
Вес термина частотным методом оценивается исходя из того, в каких документах и сколько раз этот термин встречается [35, 14, 88]. Для его вычисления вводятся такие характеристики как частота термина и частота документа.
Частота термина - это отношение количества раз, которое термин встретился в документе к общему количеству терминов в документе. Эта характеристика позволяет определить, какие термины содержаться в документе, и отражает насколько часто термин встречается в документе. Для ее оценки используют выражение
Выделение ключевых терминов в кластерах документов
Ключевые термины групп документов предназначены для использования их при построении запроса, следовательно, это должны быть термины позволяющие отличить один кластер от другого. Таким образом, задача выделения таких терминов аналогична задаче определения весов терминов в документах при индексировании документов и для ее решения предлагается использовать подход, аналогичный подходу, используемому в разработанном методе определения весов терминов в документах. Кластеры представляют собой наборы документов и поэтому для определения веса отдельного термина в кластере для всех кластеров должны быть составлены терминологические портреты. В качестве терминологического портрета кластера используется объединение множеств всех терминов всех документов входящих в кластер. Тогда вес термина в кластере может быть вычислен по формуле: Частота термина в кластере - это отношение количества раз, которое термин встретился в кластере к общему количеству терминов в кластере: На входе этапа: набор документов выданных поисковой системой в результате поиска Dc = {Dc, \ і = \,Nd}, где Dc, - і -й документ набора. На выходе этапа: множество формализованных документов D = {d, / = \,Nd}, где d(. = (с/,„da,..,diNl) - вектор / -го документа, элемент вектора d0 соответствует весу у-го термина в /-м документе - wIJt а Л7, - количество терминов в /-м документе. Задача: преобразование множества документов Dc на естественном языке в множество формализованных документов D для последующей кластеризации документов. Метод решения: 1)
Выделение терминов в тексте набора документов Dc. Разделителями терминов в тексте считаются пробелы, символы табуляции и конца стоки, кроме этого термины не могут начинаться и заканчиваться знаками препинания. При этом формируется матрица сопряженности «документ термин» Md = (MdIJ);i = \,Nd;j = \,Nt, где Mdf. - количество раз которое у-й термин встретился в /-м документе. 2) Приведение терминов к начальной (канонической) форме на основе морфологического разбора. В настоящее время существуют различные готовые модули морфологического разбора, например, свободно распространяемые компоненты разработанные компанией «АОТ». 3) Составление стоп-листов, т.е. списков функциональных терминов служащих для связи слов в предложении и не имеющих отношения к смысловому содержанию документа и исключение таких терминов из рассмотрения, что соответствует исключению соответствующих столбцов терминов из матрицы «документ-термин» Md. 4) Присвоение терминам весов, значение которых определяет их важность в документе. Веса терминов рассчитываются на основе матрицы сопряженности «документ-термин» Md с помощью разработанного метода по формуле: w,,=tfll а1П где //, - частота у-го термина в /-м dfj документе, dfj - частота документа для у -го термина, о,у - характеристика, отражающая распределение у-го термина во всех документах набора кроме /-го документа. На входе этапа: множество формализованных документов D = {d, / = \,Nd}. На выходе этапа: множество кластеров документов С = {с, \ і = \,Nc}, где Nc количество кластеров. Задача: R - набор критериев, определяющих риск потерь и качество кластеризации; задача состоит в выборе оптимального, с точки зрения экстремальности критериев качества R, разбиения множества D на множество кластеров C = {c,\i = l,Nc}.
Метод решения: кластеризация множества документов D проводится с использованием иерархического агломеративного метода дальнего соседа. В качестве метрики, т.е. меры схожести документов, используется коэффициент косинуса - косинус угла между векторами документов в пространстве терминов размерности Nt. В методе дальнего соседа коэффициент схожести между двумя кластерами, принимается равным коэффициенту схожести между двумя наименее схожими документами, каждый из которых присутствует в одном из рассматриваемых кластеров. Таким образом, коэффициент схожести между любым документом кластера и наименее схожим с ним документом этого же кластера должен быть больше, чем коэффициент схожести этого документа с наименее схожим с ним документом другого кластера. Соответственно, для того чтобы документ принадлежал какому-либо кластеру, достаточно чтобы он был связан с наименее схожим с ним документом из этого кластера.
Применение разработанных методов при создании агентов Интернет
Разработанные методы и алгоритмы могут быть использованы при создании агентов Интернет. Агентами принято называть программы, обладающие свойством автономности, способные реагировать на внешние стимулы и выполнять действия по собственной инициативе. Агентные системы поиска информации разделяются на три группы: 1) Системы неспециализированных поисковых агентов. В простейшем случае агент ищет информацию по ключевым словам и словосочетаниям, обычно поддерживается передача запроса на несколько поисковых систем, настройка на конкретного пользователя и т.д. 2) Системы специализированных поисковых агентов. Приспособлены для поиска какой-либо определенной информации, например, котировки акций, книги, музыку и т.д. Обычно хорошо работают с определенным фиксированным форматом данных, адреса таких ресурсов могут быть жестко заданы в агенте. 3) Системы с использованием методов и средств искусственного интеллекта. В последнее время наметился сдвиг в сторону именно этой категории агентов. В таких системах используются такие средства искусственного интеллекта как представление знаний, правила вывода новых знаний, механизмы обучения, лингвистическая обработка текстов на естественном языке. Особенности использования агентов при поиске информации: 1) агенты могут самостоятельно искать информацию по заданию после отключения пользователя; 2) агенты могут создавать свою собственную базу знаний информационных ресурсов Интернет; 3) агенты могут осуществлять поиск интеллектуально, используя словари, распределенные базы данных, выделять контекст запроса, настраиваться на предпочтения пользователя. Пример общей схемы агента на основе тезауруса, использующего методику автоматизированного формирования запроса, изображен на рисунке 4.5. Пользователь формирует запрос с использованием средств построения запроса агента и информации о предметной области содержащейся в тезаурусе.
Сформированный запрос поступает в систему извлечения информации, которая передает запросы в поисковые системы в формате, понятном конкретным поисковым системам, получает информацию о документах от поисковых систем и извлекает документы. Полученная информация передается в систему анализа
Пример поискового агента информации. Система анализа информации с помощью разработанной методики автоматизированного формирования запроса разбивает документы на группы и для каждой группы выделяет ключевые термины. Результаты работы системы анализа поступают в систему формирования результата, в которой формируется отчет о работе, содержащий группы схожих документов и ключевые термины этих групп. Эта информация используется пользователем вместе с информацией уже имеющейся в тезаурусе для формирования нового запроса, а также для обновления тезауруса. Формирование актуального тезауруса является одной из проблем агентов, построенных на его основе, эта процедура может занимать много времени. Основным преимуществом использования разработанной методики автоматизированного формирования запроса в агентах Интернет является отсутствие жесткой привязки к тезаурусу, что позволяет уточнять запрос при отсутствии информации в тезаурусе и повышает мобильность агента. Данная глава посвящена практической реализации разработанных методов.
Основные результаты четвертой главы следующие: 1) предложенные в работе методы и алгоритмы были использованы при создании программного компонента входящего в состав модуля анализа текстов гипертекстов информационно-аналитической системы для анализа инновационных проектов, позволившей сократить время отбор ресурсов Интернет в среднем в 1,4 раза; 2) разработанная методика автоматизированного формирования запроса при использовании ее в агентах Интернет позволяет повысить мобильность агента за счет отсутствия жесткой привязки к тезаурусу. Работа посвящена методам повышения эффективности автоматизированного документального поиска в гипертекстовых ресурсах Интернет. Основные результаты работы следующие: 1) на основе проведенного анализа моделей документального поиска и анализа существующих методов определения весов терминов разработан усовершенствованный метод оценки весов терминов в документах набора, позволяющий учесть такой фактор как распределение термина во всех документах набора, на основе использования величины обратной средней частоте термина в документах; 2) разработана методика автоматизированного формирования запроса на основе кластеризации набора документов полученных в результате поиска и разработанного метода определения весов терминов в кластерах документов; 3) разработан метод оценки весов терминов в наборе кластеров документов при автоматическом индексировании, позволяющий учесть распределение термина во всех кластерах набора, на основе использования величины обратной средней частоте термина в кластерах документов; 4) предложен метод оценки качества распределения ключевых терминов кластеров между документами с использованием коэффициентов точности, полноты и шума, аналогичных коэффициентам использующимся для оценки качества результатов поиска; 5) разработано программное средство, реализующее разработанные методы документального поиска, с использованием технологии разработки приложений на основе компонентной объектной модели;
