WWW.DISSERS.RU

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

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

Pages:     ||
|

p j q pi= 1-q, i=1,2,..., N (1.1) N kout j j : j i где N – общее число страниц; ji обозначает гиперссылку от страницы j к странице i; K (j) – это число исходящих ссылок страницы j; (1-q) – out амортизирующий коэффициент (damping factor)1. Набор уравнений (1.1) решается итеративно.

Оба алгоритма: PageRank и HITS предлагают общую идею итеративного вычисления авторитетных страниц, где авторитетность определяется наличием (количеством) и характером (степень авторитетности источника) ссылок. Однако есть и разница. Отличие алгоритма PageRank от алгоритма HITS в том, что у каждой страницы только один параметр, который соответствует её популярности, это вес PageRank. В алгоритме HITS каждой странице сопоставлено два параметра, которые определяют авторитетность и наличие ссылок на авторитетные страницы. Это соответственно параметры authority и hub. Отметим, что PageRank не требует дополнительных вычислительных затрат во время обработки запроса, HITS более дорогой с вычислительной точки зрения алгоритм.

В работе [89] указывают на сходство результатов работы HITS и PageRank2. Большинство документов, полученных как авторитетные в HITS, были представлены в результатах PageRank, но упорядочены были по другому. Однако в другой работе [80] при поиске авторитетных страниц с помощью алгоритмов HITS и PageRank по всей Английской Википедии и по некоторым подмножествам страниц (например: People, Historical Events, сильные поисковые системы, на основе данных TREC. Поскольку результаты работы поисковиков могут быть неудачными, постольку веса могут быть отрицательными, поэтому авторы вводят понятие неавторитетности (unauthority) и выделяют тип вершин, ссылающихся на неавторитетные вершины (unhubness). Тогда «хаб-документ – это документ, содержащий много ссылок на неавторитетные вершины, причём ссылки имеют большой отрицательный вес» [136].

1 О выборе амортизирующего коэффициента в алгоритме PageRank см. в работе [73].

2 В работе [89] авторы используют в Байесовой сети доверия веса, рассчитанные с помощью HITS, для поиска релевантных документов. С помощью HITS посчитали четыре веса для каждого документа: hub и authority, локальные (по запросу), глобальные (по всем документам).

- 29 Countries and Cities)1 были получены в общем разные классы концептов.

Также в работе [145] приводятся эксперименты по сравнению различных методов поиска похожих статей в ВП, в том числе сравнивают работу алгоритмов LocalPageRank2 и PageRankOfLinks (аналог PageRank) в пользу последнего. Авторы [145] делают вывод, метод HITS ищет хуже похожие статьи в ВП, чем PageRank, поскольку считают метод LocalPageRank аналогичным методу HITS. Скорее всего, это не верный вывод, поскольку LocalPageRank и HITS – разные алгоритмы – они используют разное число весов для каждой страницы. Таким образом, требуются дополнительные исследования по сравнению алгоритмов с помощью экспериментов.

О популярности алгоритма PageRank говорит наличие нескольких его модификаций. В работе [145] предложены методы Green, SymGreen для поиска «вершин, семантически связанных с исходной». Эти методы являются модификациями алгоритма PageRank на основе Марковских цепей.

Алгоритм распределения рангов (ArcRank) Алгоритм предназначен для поиска семантически близких слов, а не синонимов. ArcRank вычисляет рейтинг вершин аналогично алгоритму PageRank. Небольшая модификация в том, что вершинам источникам3 и висячим вершинам4 не присваиваются предельные значения.

В ArcRank дугам назначаются веса на основе весов вершин. Если |a | – s число исходящих дуг из вершины s, p – вес вершины t, тогда важность t ps/as rs,t= (relevance) дуги (s,t) определяется так [174]:

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

1 Подмножество определяется благодарю наличию категорий у страниц. Например статья в русской Википедии: «Куинджи, Архип Иванович» содержит такие категории, как: «Художники России», «Передвижники» и др., см. http://ru.wikipedia.org/wiki/Куинджи,_Архип_Иванович 2 В работе [145] указан недостаток LocalPageRank, присущий и HITS: в сильно связанном графе (например ВП), соседние вершины (для данной) – это значительная часть всего графа.

3 Нет входящих дуг, то есть слова не упоминаются ни в одной словарной статье.

4 Нет исходящих дуг, то есть словам не даны определения, они не встречаются в заголовках словарных статей.

- 30 Алгоритм WLVM Алгоритм векторной модели ссылок Википедии (англ. Wikipedia Link Vector Model или WLVM) вычисляет сходство двух статей ВП на основе содержащихся в них ссылок [134]. Алгоритм включает шаги:

1. по заданному термину получить все статьи ВП с похожими заголовками;

2. обработать ссылки (разрешить «редиректы»1; для ссылок на страницы «дизамбиги»2 взять все ссылки, перечисленные на «дизамбигах»);

3. подсчитать вес ссылок (см. ниже);

4. построить вектор (исходящих) ссылок для каждой страницы;

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

Семантическое сходство двух страниц ВП определяется углом между векторами ссылок этих страниц. Сходство будет выше, если обе страницы ссылаются на страницу, на которую мало ссылаются другие страницы.

Вес ссылки с исходного документа на целевой определяется по правилам:

• 1 или 0, если есть или нет такая ссылка в исходном документе;

• обратно пропорционально общему числу ссылок на целевой документ.

А именно, вес ссылки w со страницы a на страницу b рассчитывается по t t w a b =a b log формуле:, где t — общее число страниц в ВП.

x b x=Для оценки алгоритма использовался тестовый набор 353-TC.3 Была предпринята малоуспешная попытка автоматически выбирать верное значение для ссылок на многозначные статьи: коэффициент корреляции Спирмена с эталонным набором оказался равным 0.45, при разрешении 1 «Редирект» – это страница-перенаправление; «разрешить редирект» означает подменить ссылки xyz на xz, спрямляя путь до целевой статьи.

2 «Дизамбиги» – статьи Википедии, содержащие перечисление значений. Создаются для многозначных терминов, см., например, статью «Лемма».

3 Тестовый набор подробно описан на стр. 127. Сравнение результатов работы алгоритма WLVM с другими см. в табл. 4.6 на стр. 130.

- 31 многозначных статей вручную — 0.72. Доступна реализация WLVM алгоритма.Алгоритмы построения и анализа ссылок: Similarity Flooding, алгоритм извлечения синонимов из толкового словаря и другие Одна из задач, рассматриваемых в диссертации2, относится к типу задач scheme / ontology alignment (другое название – scheme / ontology matching).

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

Этот тип задач замечателен тем, что включает и лексическую3, и семантическую4 компоненты. Обзор современных работ по scheme / ontology matching представлен в [164], критический обзор открытых (open source) программных систем изложен в [190].

Кратко опишем несколько работ, посвящённых данной теме. Затем более подробно осветим алгоритм Similarity Flooding и алгоритм извлечения синонимов из толкового словаря.

Итак, в работе [77] для обнаружения неявных (latent) связей между вершинами считают число общих соседей двух вершин. Сходство двух вершин (relevance measure) вычисляется как отношение числа общих вершин к числу всех соседних вершин ([77], стр. 3). Авторы поставили себе общую задачу – обнаружение отношений в семантическом графе5. Эксперименты 1 Программа Wikipedia Miner Toolkit, см. http://sourceforge.net/projects/wikipedia-miner.

2 В данной работе предлагается оригинальный алгоритм поиска похожих вершин графа, см. гл. 2.

3 Примером использования лексической компоненты в задачах scheme / ontology alignment может быть задача сравнения графов (graph matching), задача сравнение строк (например, сравнение имён) и др. [164].

4 Пример семантической компоненты – использование формальной онтологии верхнего уровня SUMO, DOLCE (там же, стр. 9).

5 Семантический граф – это граф, который содержит вершины разных типов и отношения между ними, также разных типов [77]. Семантическая сеть (semantic network) – это направленный граф с вершинами, соответствующими концептам, и рёбрам, представляющим семантические отношения между концептами - 32 заключались в предсказании возможных атак и уязвимостей служб безопасности на основе видеофильмов и данных терактов.

Поиск похожих вершин в графах возможен с помощью поиска соответствий между вершинами (отображений). Во-первых, точное соответствие, одна вершина к одной (рассматривается в данной работе, стр. 86). Во-вторых, неточное – многие к одной или многие к многим, то есть кластер концептов отображается в один концепт. В работе [97] предложен алгоритм неточного сравнения графов онтологий1 на основе максимизации ожидания2. Онтология представлена в виде направленного графа с метками.

Алгоритм Similarity Flooding Кратко опишем один из алгоритмов, решающих описанную выше задачу scheme / ontology alignment, – алгоритм Similarity Flooding, ключевая идея которого в том, что «два элемента считаются сходными, если сходны их соседи. Сходство двух элементов распространяется на их соседей» [132]. На первом шаге в соответствии с входными схемами, которые нужно сравнить (например SQL таблицы или запросы), строятся два графа. На втором шаге задаются начальные значения сходства между вершинами двух графов, путём сравнивая имён вершин. На третьем шаге итеративно вычисляется сходство вершин до тех пор, пока суммарное изменение степени сходства по всём вершинам больше наперёд заданного. Значение сходства между вершинами учитывается для вычисления сходства соседних вершин. На четвёртом шаге выбираются наиболее похожие пары вершин.

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

(см. http://en.wikipedia.org/wiki/Semantic_network).

1 В таком графе концептам соответствуют вершины, отношениям – дуги.

2 См. http://en.wikipedia.org/wiki/Expectation-maximization_algorithm.

- 33 Алгоритм извлечения синонимов из толкового словаря В работах [84], [83], [174] французские учёные, под руководством Винсента Блондела (Vincent Blondel), предлагают обобщение HITS алгоритма для поиска синонимов в толковом словаре.Предположим, что (1) синонимы имеют много общих слов в определениях (в статьях толкового словаря); (2) синонимы часто употребляются в определении одних и тех же вокабул2. Построим граф G, в котором вершины соответствуют вокабулам словаря. Строится дуга от вершины u к v, если слово, соответствующее v, встречается в определении вокабулы u.

Пусть ищем синонимы для слова w. Для этого строим G (подграф графа w G), включающий (1) все вершины из G, ссылающиеся на w и (2) все вершины, на которые ссылается w. Считаем сходство слов относительно слова w, чтобы выбрать лучшие слова как синонимы.

Сходство между вершинами графа вычисляется так. Каждой вершине i x1 x2 xграфа G назначаем три веса,, с начальным значением w i i i единица. Веса обновляются итеративно по такому правилу:

x1 x• Вес равен сумме весов всех вершин j, на которые указывает i j вершина i;

x2 x• Значение равно сумме весов (вершин, на которые i j xуказывает вершина i) и (вершин, указывающих на i).

j x3 x• Значение равно сумме весов вершин, указывающих на i.

i j На каждом шаге веса одновременно обновляются и нормализуются.

xСинонимами считаются слова с максимальным значением (центральный i 1 Обобщение, поскольку Блондел вводит понятие структурный граф и получает, что в алгоритме Клейнберга HITS [125] структурный граф состоит всего из двух вершин (hub authority), при этом все вершины рассматриваемого графа G имеют по два веса (hub и authority), которые показывают насколько эти вершины графа G похожи на вершину hub и authority соответственно. Для поиска синонимов в словаре Блондел предлагает использовать структурный граф из трёх вершин (1 2 3), таким образом, вершины графа словаря будут иметь по три весовых значения.

2 Вокабула – заголовок словарной статьи (лексикографический термин).

- 34 вес). Вычисления проводились на английском словаре Вебстера.

Построенный граф содержал 112 169 вершин, 1 398 424 рёбер.

Алгоритмы статистического анализа текста: ESA, поиск контекстно-связанных слов Алгоритм ESA В работе [103] авторы описали алгоритм ESA, позволяющий представить значение любого текста в терминах концептов ВП.1 Оценка эффективности метода выполнена за счёт автоматического вычисления степени семантической связи между фрагментами текста произвольной длины на ЕЯ.

Для ускорения работы построили инвертированный индекс: слову соответствует список концептов, в статьях которых оно появляется. Была выполнена предобработка концептов ВП:

• удалили концепты, которым соответствуют небольшие статьи (меньше 100 слов, меньше 5 исходящих и входящих ссылок);

• удалили стоп-слова и редкие слова;

• получили леммы слов (тексты на английском языке).

В алгоритме ESA на вход подаются два текста. По ним строятся два вектора из концептов ВП следующим образом. По фрагменту текста (1) строится вектор по TF-IDF схеме, (2) из инвертированного индекса выбираются концепты и объединяются во взвешенный вектор2. Произведение этих векторов и даёт вектор концептов ВП релевантных фрагменту текста. Для сравнения текстов сравнивают два вектора, например, с помощью косинусного коэффициента.

Эксперименты в работе [103] показали преимущество ESA в точности поиска семантически близких слов в ВП по сравнению с алгоритмами поиска 1 ESA – это аббревиатура от «Explicit Semantic Analysis» (явный семантический анализ). Название выбрано в противовес «скрытому семантическому анализу» (LSA), поскольку в ESA концепт – это название статьи. То есть концепты явные, формулируются человеком, легко объяснить их значение.

Pages:     ||
|



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

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