WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

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

Представлены оценки временной сложности алгоритмов и эвристики.

Предлагается несколько показателей численной оценки полученного набора семантически близких слов с помощью тезаурусов WordNet и Moby.

2.1 Подход к поиску семантически близких слов Предлагаемый подход к поиску семантически близких слов (СБС) представлен на рис. 6. Входными данными для поиска семантически близких слов являются исходное слово, корпус документов1 и список слов, уточнённый пользователем2. Последовательность взаимодействия частей системы указана на рис. 6 числами (1-7). Входными данными для поискового алгоритма являются слово, заданное пользователем (1-2), и корпус текстов (2). Алгоритм строит упорядоченный список СБС (3), а пользователь получает возможность работать с ним благодаря визуализации (4-5). В ходе работы пользователь уточняет список СБС и может запустить алгоритм повторно (6-7). Достоинствами данного подхода являются (1) визуализация 1 Из корпуса выбирается документ, заголовок которого совпадает с исходным словом, заданным пользователем. Таким образом, в данной схеме приняты следующие допущения: (1) разные документы в корпусе имеют разные заголовки, (2) заголовки состоят из одного слова. Заметим, что можно расширить эти ограничения, если (1) вместо заголовков выполнять поиск по ключевым слова документов, (2) выполнять поиск подстроки в заголовке (тогда заголовок может состоять из нескольких слов).

Заметим также, если слово задано не в неопределённой форме, то его можно привести к ней с помощью модуля морфологической обработки русского языка Lemmatizer, описанного на стр. 106. Прочие ограничения для заголовков словарных статей указаны на стр. 74.

2 Список слов, найденный системой и уточнённый пользователем, то есть предполагается обратная связь для уточнения результатов поиска.

- 67 результатов поиска, (2) возможность уточнения запроса в ходе работы пользователя с программой.

Рис. 6. Подход к поиску семантически близких слов Перечисленные выше требования1 к корпусу проблемно-ориентированных текстов задают два типа документов с гиперссылками (статья и категория) и три вида отношений, то есть ссылок между документами в корпусе (статьястатья, статья-категория и категория-категория). Отношения между категориями являются иерархическими (родо-видовые и часть – целое).Авторы алгоритма извлечения синонимов из толкового словаря [84], [83] предложили гипотезу, по которой два слова считаются «почти синонимами» (near synonyms), если слова:

1. употребляются в определении одного и того же слова;

2. имеют общие слова в определениях.

Таким образом, в работах [84], [83] полагают, что если статьи толково­ го словаря оказались семантически близкими (то есть выполняются два пунк­ та, указанных выше), то и заголовки статей (слова, словосочетания) будут семантически близкими. Назовём это гипотезой 1.

Обобщение этой гипотезы на документы с гиперссылками предложил Kleinberg [125], используя понятия авторитетных и хаб-страниц3. Обобщение 1 См. Требования к корпусу проблемно-ориентированных текстов, гл. 1, стр. 24.

2 См. «Виды отношений в Википедии» в табл. 1 на стр. 184.

3 Cм. определения авторитетных и хаб-страниц далее в главе 1 в подразделе «Алгоритм HITS».

- 68 таково: пусть на страницу p ссылаются хаб страницы, которые могут иметь ссылки на авторитетные страницы.

На страницу p будут похожими (similar у Kleinberg'a, семантически близкие в нашей терминологии) те из авторитетных страниц, на которые ссылаются те же хаб-страницы, которые, в свою очередь, ссылаются на страницу p. Назовём это гипотезой 2.

Использование этих двух гипотез позволит нам (1) использовать гиперссылки для поиска похожих документов, (2) считать ключевые слова (например, заголовки документа) семантически близкими для похожих документов.

Таким образом исходными данными для поисковых алгоритмов будут направленный граф (вершины – это статьи, дуги – это ссылки) и дерево категорий (вершины – категории, дуги связывают категории-родителей и категории-детей). Направленный граф и дерево связаны, поскольку вершины направленного графа (статьи) связаны с одной или несколькими вершинами дерева категорий.

Общая идея адаптированного алгоритма1 заключается в следующем.

Документы корпуса связаны друг с другом ссылками2 наподобие Интернет страниц. У каждого документа есть ключевые слова, его характеризующие и ему соответствующие; в простейшем случае – это заголовок документа. Если, таким образом, для документа найдены (с помощью HITS алгоритма) похожие документы, то можно утверждать, что найдены похожие заголовки, являющиеся семантическими близкими словами для заголовка исходного документа3. Остаётся улучшить HITS алгоритм за счёт особенностей рассматриваемого корпуса текстов4.

1 Исходный HITS алгоритм представлен в главе 1 в подразделе «Алгоритм HITS» (стр. 27). Отметим работу [125], в которой предлагается искать похожие Интернет страницы на основе структуры ссылок.

2 Предлагаемый адаптированный HITS алгоритм применим только к корпусам текстам, удовлетворяющим ряду требований, см. «Требования к корпусу проблемно-ориентированных текстов» в главе 1 на стр. 24.

3 Здесь и далее под статьёй, страницей, документом, вики-текстом подразумевается текстовый документ корпуса. Разница между страницей, статьёй и категорией объясняется в подразделе «Замечания о категориях и ссылках Википедии» на стр. 186.

4 Под особенностями корпуса подразумевается (1) наличие категорий (категории классифицируют документы, то есть определяют их тематическую принадлежность; сами категории в идеале образуют иерархическую структуру) и (2) наличие двух списков страниц для каждой статьи (кто ссылается на - 69 Причиной использования категорий для установления связи между страницами (относительно оригинального алгоритма HITS, который оперирует только ссылками) является следующее: «входящие ссылки» (inlinks), то есть ссылки на данную страницу, «содержат ссылки, связь которых с основной страницей может быть весьма слаба, в то время как в одну категорию обычно помещают страницы сходной тематики»1.

2.2 HITS алгоритм (формализация, анализ, поиск синонимов) Формализация задачи Дан направленный граф G=(V, E), где V – вершины (Интернет страницы), E – дуги (ссылки). Для каждой страницы v известны два списка: Г+(v) – это страницы, на которые ссылается данная статья, и Г(v) – это страницы, ссылающиеся на данную статью. Необходимо найти набор страниц, соответствующих запросу s (релевантность), на которые при этом ссылаются многие страницы (авторитетность).

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

Требуется идеальная коллекция (множество страниц) S : такая, что она небольшая (подходит для вычислительно «тяжёлых» алгоритмов), содержит много релевантных страниц, большинство страниц являются авторитетными (в идеале — все).

Клейнберг [125] предлагает следующий алгоритм для поиска M страниц максимально похожих (подразумевается максимальное значение веса страницы – authority) на заданную страницу v:

1. Поиск с помощью общедоступного интернет поисковика (например, AltaVista) релевантных страниц – это корневой набор S (root set).

2. Расширение корневого набора (с целью включения авторитетных страниц в набор) страницами, которые связаны данную статью Г(v), на кого ссылается данная статья Г+(v)).

1 Цит. по http://ru.wikipedia.org/wiki/Википедия:Категории.

- 70 ссылками с корневым набором – это базовый (base) набор страниц (рис. 7).

3. Итеративное вычисление весов (authority и hub) у вершин базового набора для поиска авторитетных и хаб-страниц.

Завершение итераций, когда суммарное изменение весов меньше наперёд заданного.

4. Выбрать M страниц с максимальным значением веса authority) из базового набора.

Рис. 7. Расширение корневого набора страниц (root) до базового (base) [125] Каждому документу в HITS алгоритме сопоставляются веса a (authority) и h (hub), которые показывают, соответственно, насколько документ является авторитетным и насколько он является хорошим хаб-документом. Формулы алгоритма HITS для итеративного вычисления весов таковы:

h = ai, j (2.1) i : j, i E a = hi j (2.2) i :i, j E где h и a показывают соответственно насколько документ j (1) является j j хорошим указателем на релевантные документы (то есть j-ый документ рассматривается как хаб-документ) и (2) является авторитетным документом.

Доказательство сходимости итеративного процесса вычисления весов h и a, j j использующее собственные значения матрицы смежности графа G, представлено в [125] и [81].

- 71 Детальное описание HITS алгоритма представлено в [125]. Описание изменений в алгоритме для адаптации к поиску в вики ресурсах представлено ниже1.

Дополнительные замечания Приведём положения Клейнберга [125] и свои замечания к ним:

1) Авторитетные страницы должны быть авторитетными именно для данного запроса.

Изменение авторитетности (веса страницы) в зависимости от запроса приводит к тому, что вычисления выполняются в режиме онлайн, то есть после формулирования запроса. Остаётся открытым вопрос о возможности предварительной предобработки, позволяющей ускорить поиск авторитетных и хаб-страниц.

2) Нет такого (внутреннего) свойства страницы, по которому можно было бы определить её авторитетность.

Иначе любая страница (усилиями авторов) стала бы авторитетной.

Поскольку быть авторитетной страницей значит привлекать бльшее число пользователей, и значит быть более доходной для коммерческих сайтов.

3) Проблема: страница может не содержать слова, которым соответствует её содержание. Например страница поисковика может не содержать слова “search”.

Анализ структуры ссылок (HITS алгоритм) решает эту проблему, поскольку (например, для данного примера со словом “search”) найдутся страницы, которые содержат искомое слово и ссылаются на релевантную страницу (в данном случае на поисковик).

Глобальность HITS алгоритма в том, что ставится задача поиска лучших авторитетных страниц во всём Интернете. Отметим, что анализ ссылок (здесь) отличается от кластерного анализа, так как элементы/кластеры образуют единое целое, чего не скажешь о страницах Интернет в целом.

Проблемы HITS алгоритма [81], [89]:

1 См. подраздел 2.3 «Адаптированный HITS алгоритм, включающий алгоритм иерархической кластеризации» на стр. 76.

- 72 • учитываются «только ссылки», что приводит к взаимному усилению веса страниц, ссылающихся друг на друга;• существуют «автоматически создаваемые ссылки», то есть ссылки, созданные программой, не выражают мнение человека о значимости страницы;• «не релевантные документы», граф содержит документы, не соответствующие теме запроса. Возникает проблема смещения темы (topic drift) из-за того, что большой вес имеют вершины-документы о популярных предметах (то есть имеющих много входящих ссылок), но таких, что уводят в сторону от исходной темы;• связность, если веб-граф представляет несколько несвязанных компонент, то HITS присвоит нулевые веса hub и authority всем страницам, кроме главной компоненты.

В [81] предложено расширение HITS алгоритма за счёт анализа текста документов, что в результате повысило точность поиска, особенно для редких запросов. Вес вершины вычисляется с помощью TF-IDF схемы(сравниваются первые 1000 слов документа и слова запроса).

Перемножаются значение веса authority и вес вершины (вычисленный по схеме TF-IDF), – теперь это будет новое значение authority, аналогично пересчитывается вес hub. При построении по запросу подграфа, используется 1 Этот случай относится к мультиграфу (например, Веб), содержащем множество дуг от одной вершины к другой. Такой проблемы нет в вики-текстах, поскольку вики в реализации MediaWiki не мультиграф:

между двумя страницами либо есть одна направленная ссылка, либо нет (см. таблицу pagelinks в БД).

2 Таким образом, нарушается основной принцип, на который полагаются такие алгоритмы, как: HITS и PageRank. К счастью эта проблема не существенна при поиске в вики-ресурсах, поскольку вики (и ссылки в них) по определению (см. стр. 51), создаются людьми, а не программой.

3 На эту же проблему указывает Hearst М. [112] (цит. по [81]), а именно: HITS алгоритм не находит часть документов, соответствующую менее популярной интерпретации запроса. Hearst предлагает возможные решения: (1) кластеризация документов на подтемы и анализ каждого подграфа с помощью HITS отдельно; (2) модификация HITS алгоритма, присваивающая рёбрам внутри кластера больший вес по сравнению с весом рёбер между кластерами.

4 «IDF (обратная частота термина в документах, обратная документная частота) – показатель поисковой ценности слова (его различительной силы)» [52]. В 1972 г. Karen Sparck Jones предложил эвристику:

«терм запроса, встречающийся в большом количестве документов, обладает слабой различительной силой (широкий термин), ему должен быть присвоен меньший вес, по сравнению с термином, редко встречающимся в документах коллекции (узкий термин)». Данная эвристика показала свою пользу на практике и в работе [155] представлено её теоретическое обоснование.

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

Тематическая связность авторитетных страниц Задача – извлечь тематически связанные авторитетные страницы из коллекции страниц S (см. выше). Простейший подход: упорядочить страницы по степени захода (число ссылок на страницу). Проблема такой простой схемы ранжирования в том, что могут быть найдены страницы с большой степенью захода, но тематически несвязанные.

Возможны следующие решения задачи:

1) Решение Клейнберга. Авторитетные страницы (по данной тематике) содержат не только большое число входных ссылок, но и пересекаются между собой. Это обеспечивается хаб-страницами, содержащими ссылки сразу на несколько авторитетных страниц (одной тематики).

2) Оригинальное решение (на основе решения Клейнберга). В Википедии каждой странице эксперты приписывают несколько категорий.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.