WWW.DISSERS.RU

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

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

Pages:     ||
|

Категории образуют дерево, то есть у каждой категории есть категорияродитель и несколько детей. Такая тематическая определённость страниц позволяет:

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

Применение способов оценки результатов поиска в Интернет к HITS алгоритму Поиск в Интернет (Web search) – это нахождение релевантных страниц, соответствующих запросу. Оценка качества поиска основана на оценке, сделанной человеком, так как релевантность – субъективное свойство. Не хватает объективной (численной) функции для определения качества поиска.

- 74 В классических информационно-поисковых системах (ИПС) результаты ранжируются (i) пропорционально частоте термов в документе, (ii) обратно пропорционально частоте терма по всем документам (относительно ключевых слов запроса) (TF-IDF схема).

При Веб поиске дополнительно учитывается множество параметров [76]: число ссылок, которые ссылаются на страницу; текст ссылки; положение искомого слова (наличие его в заголовке даёт больший вес странице); расстояние между искомыми термами на странице;

популярность страницы (число посещений); содержание текста в метаданных (metatags) [143], [93], [113]; принадлежность страницы определённой тематике; новизна ресурса; степень точности соответствия запросу.

В HITS алгоритме вес страницы распределяется равномерно между страницами, на которые она ссылается (см. формулы (2.1) и (2.2) для вычисления весов hub и authority). Предлагается учитывать положение ссылки на странице таким образом: чем выше на странице упоминается ссылка, тем больший вес она получит.

Поиск синонимов с помощью HITS алгоритма В работах [84], [83] предложена адаптация HITS алгоритма к поиску синонимов в словаре Webster1. Словарная статья состоит из заголовка и текста статьи. Словарные статьи ссылаются друг на друга (образуют граф) посредством упоминания слов, которые являются заголовками других статей.

С помощью алгоритма HITS можно найти авторитетные2 словарные статьи для исходной статьи. Авторы предполагают, что заголовки этих словарных статей будут содержать синонимы относительно заголовка исходной статьи.

При построении графа словаря часть статей словаря была отфильтрована, поскольку:

• не учитываются составные слова, то есть из нескольких термов (например, All Saints', Surinam toad);

1 Поиск выполнялся в словаре «Online Plain Text English Dictionary» (http://msowww.anu.edu.au/~ralph/OPTED), построенный на основе словаря «Project Gutenberg Etext of Webster’s Unabridged Dictionary» (http://www.gutenberg.net), который, в свою очередь, использует словарь «1913 US Webster’s Unabridged Dictionary» [84].

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

- 75 • многозначные слова рассматриваются как однозначные;

• исключили статьи, состоящие из чисел и формул (мат., хим.);

• исключили часто встречаемые слова, которые встречаются чаще чем в 1000 определений;

• рассматривались слова только той же части речи, что искомое.

Далее вычислялись авторитетные и хаб-вершины. Проводилась оценка полученных синонимов для четырёх слов разных типов [83]:

1. Слово, имеющее несколько синонимов (Dissappear);

2. Терминологическое, узкоспециальное слово (Parallelogram), в действительности не имеющее синонимов, однако существуют слова для названий предметов близких по сути (quadrilateral, square, rectangle, rhomb).

3. Многозначное слово (Sugar);

4. Общеупотребительное слово, обозначающее понятие, не имеющее однозначного определения (Science).

Авторы [83] сравнили свой метод (адаптация HITS к поиску слов в словарных статьях) с методом расстояний и методом PageRank, вычисляя синонимы для вышеуказанных четырёх слов. Их метод показал показал более хорошие результаты, чем эти два метода.

Суть метода расстояний (distance method) заключается в том, что два слова считаются синонимами, если:

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

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

В работе [83] предложили такую формализацию метода расстояний.

Расстояние между двумя словами равно сумме количества слов в определении первого слова, отсутствующих в определении второго, и количества слов в определении второго слова, отсутствующих в определении первого.

- 76 2.3 Адаптированный HITS алгоритм, включающий алгоритм иерархической кластеризации Постановка задачи. Дан направленный граф G=(V, E), где V – вершины (текстовые документы), E – дуги (ссылки между документами). Для каждой вершины определены значения двух весовых коэффициентов authority и hub:

{vV : av,hv}. Для каждой страницы v известны два списка: Г+(v) – это страницы, на которые ссылается данная статья, и Г(v) – это страницы, ссылающиеся на данную статью. Задана исходная страница s. Нужно найти похожие страницы.

Необходимо найти набор вершин A, похожих на вершину s. Похожесть определяется тем, что есть много хаб-вершин H, указывающих и на s, и на вершины из A. При этом вершины А являются авторитетными, то есть на них указывают многие вершины той же тематической направленности, что и исходная вершина s. Формализуем понятия похожести и авторитетности вершин, то есть формализуем постановку задачи.

Формализация понятия «похожие вершины» графа Необходимо найти множество вершин A, которые являются (i) авторитетными вершинами для исходной вершины s (то есть значение (2.3) больше относительно других подмножеств вершин той же мощности), (ii) похожими на исходную вершину s, то есть существует множество хабвершин H, ссылающихся одновременно и на исходную вершину s и на вершины из А (2.4), (iii) где H – это хаб-вершины (то есть значение (2.5) относительно других подмножеств вершин той же мощности). Задача выбрать множество A авторитетных вершин и множество H хаб-вершин в значении (2.6), где k — весовой параметр.

AV,A=N, av max (2.3) v A (2.4) AV, H V, a A hH : hs, a H V,H=M, hv max (2.5) v H AV, H V, k[0,1 ]:

(2.6) k av 1-k hv max v A v H - 77 Адаптированный HITS алгоритм t, d, N, Cmax sV Входные параметры алгоритма: ; ;, где • s – исходная вершина графа (исходный документ), требуется найти вершину похожую на исходную;

• t – размер корневого набора Rs (число страниц, включаемых в корневой набор);

• d – инкремент, параметр определяет размер базового набора B s (d входящих ссылок для каждого документа в корневом наборе будет добавлено в базовый набор, более подробно см. [125]);

• N – число похожих вершин (документов, или семантически близких слов), которые необходимо найти;

• C – максимально допустимый вес кластера (число статей и max категорий в кластере), где под кластером понимается набор статей, связанный ссылками с другими статьями и с категориями;

• – допустимая погрешность для останова итераций.

Шаги адаптированного HITS алгоритма представлены в виде блок-схемы на рис. 8. Шаги, предложенные автором, выделены пунктиром. Опишем более подробно шаги 2-6 адаптированного HITS алгоритма:

2. В корневой набор (root) включаются те страницы, на которые ссылается исходная страница; может быть включено не более t страниц (вместо поиска с помощью поискового сервера – в HITS алгоритме).

3. Для каждого страницы в корневом наборе: включаем все страницы, связанные исходящими ссылками и не более d страниц, связанных входящими ссылками. Так строим базовый набор страниц (Рис. 9).

4. Итеративно вычисляются веса с помощью формул Клейнберга (2.1) и (2.2) для поиска авторитетных и хаб-страниц среди страниц базового набора. Итеративные вычисления завершаются, когда суммарное изменение весов по всем вершинам a и h за одну итерацию меньше.

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

Рис. 8. Адаптированный HITS алгоритм 6. Для каждого кластера базового набора выбирается множество страниц A, содержащих N статей. Причём страницы - 79 множества А являются (i) авторитетными для исходной страницы s (то есть суммарное значение весов authority страниц из A велико относительно других подмножеств страниц той же мощности), (ii) похожими на исходную вершину s в смысле наличия множества хаб-страниц H, ссылающихся одновременно и на исходную вершину s и на вершины из А1.

Рис. 9. Построение базового набора страниц (а) в HITS и (b) в адаптированном HITS алгоритме Априори трудно сказать, чем лучше способ (a) или (b) при построении базового набора страниц (рис. 9). Основная задача при построении базового набора – включить как можно больше как можно более авторитетных страниц из пространства Интернет (в случае (a)), из пространства корпуса (в случае b). Оба этих подхода не могут гарантировать, что такое включение произойдёт2.

Построение базового набора страниц Адаптированный алгоритм построения базового набора страниц (шаги 1 и 2 адаптированного HITS алгоритма):

1 См. формулы (2.3)-(2.6) выше.

2 Одна из задач будущих исследований – настроить локальный поисковик (например, Google Desktop или Beagle) на корпус текстов, с которым работают в адаптированном HITS алгоритме. Тогда, можно будет сравнить два способа построения базового набора: (1) построение корневого набора с помощью поисковика и (2) построение корневого набора от исходной вершины (текущий вариант).

- 80 Subgraph(s,t,d) t, d sV,.

s: исходная страница.

t: число страниц в корневом наборе R.

s d: инкремент – число страниц, добавляемых в базовый набор B.

s Обозначим R – корневой набор из t страниц для страницы s;

s B – базовый набор страниц.

s R := первые t ссылок страницы s.

s For each p Rs Г+(p) – это набор всех страниц, на которые указывает p.

Г(p) – это набор всех страниц, которые ссылаются на p.

B += Г+(p).

s If |Г(p)| <= d then Bs += Г(p).

Else Bs += (d любых страниц из Г(p)).

End Return B s Число добавляемых страниц из Г(p) ограничено параметром d, так как на некоторые страницы могут указывать сотни и тысячи страниц.

Вычисление весов authority и hub После построения базового набора страниц применяется итеративный метод вычисления весов, также как и в HITS алгоритме. Каждой странице присваивается две величины: authority и hub, которые вычисляются методом Iterate() (шаг 3 алгоритма).

Iterate(, N):

N,, где – допустимая погрешность для останова итераций.

N – число похожих страниц (авторитетных), которые необходимо найти - 81 while (E > ) { Для каждой страницы из базового набора B :

s обновить значения: authority, hub (см. формулы (2.1) и (2.2)) av=1 hv= Нормализовать authority и hub так, что и vV vV Вычислить суммарное изменение веса по всем страницам:

E= hnew-holdanew-aold v v v v vV } Return N страниц с максимальным значением веса authority.

Временная сложность1 вычисления весов (в зависимости от N – числа страниц в базовом наборе) составляет O(IN2), где I – число итераций.

Поскольку для каждой страницы нужно обойти всех её соседей (в худшем случае их N).

Кластеризация на основе категорий статей Предлагается следующий алгоритм иерархической кластеризации, позволяет объединить документы в смысловые группы. Определим структуры данных, используемые в алгоритме, представим блок-схему (Рис. 10) и псевдокод алгоритма.

Структуры данных и параметры алгоритма:

• G=(V, E) – направленный граф, где V – вершины (статьи и категории, то есть два типа страниц, два типа вершин), E – дуги (три типа дуг: между статьями, между категориями, между статьями и категориями).

• E – массив рёбер, упорядоченный по весу (E [0] – ребро с sorted sorted минимальным весом).

• Clusters – список кластеров, которые нужно построить.

• C – максимально допустимый вес кластера (число статей и max категорий в кластере).

Для каждого ребра e определены следующие поля:

• е и е – это указатели на два соединяемых кластера;

c1 c1 Асимптотический анализ и, в частности, О-оценивание см. в [20], стр. 49-50.

- 82 • e – вес ребра (пересчитывается), равный суммарному весу weight объединяемых кластеров с и с.

1 Рис. 10. Иерархическая кластеризация Для кластера-вершины c определены такие поля:

• |с | – число объединённых рёбер кластера (рёбер между edges вершинами-категориями кластера);

• |с | – число статей, которые ссылаются на категории в кластере articles (знак мощности множества |.| используется в силу его наглядности, однако, поскольку |с | – это переменная, то ей можно articles присваивать значение (см. напр. строку 5b в алгоритме);

- 83 • c – вес кластера;

weight • Г(c) – массив рёбер, связывающих кластер с другими кластерами.

При вычислении веса кластера учитываются: число статей в кластере, веса объединяемых кластеров (см. формулу (2.7) ниже).

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

Предобработка (две косые черты '//' отделяют комментарий от псевдокода) 1. Построить кластеры (массив Clusters) по категориям: изначально каждый кластер соответствует отдельной вершине (категории).

Приписать каждому кластеру (за счёт содержащихся в кластере категорий):

a) |с | = число статей, которые ссылаются на категории в articles кластере, b) c = 1 + |с | // изначально вес кластера – это число weight articles категорий в кластере (изначально одна) и число статей, которые ссылаются на эту одну категорию;

c) c [0] = category // присваиваем кластеру уникальный category_id id идентификатор id первой (и единственной пока) категории, добавленной в кластер1.

2. Для каждого ребра между категориями создать ребро между кластерами. Каждому ребру e, соединяющему два кластера c1 и c2 определить вес так:

e = c1 + cweight weight weight 1 У каждой страницы (категории или статьи) Википедии есть уникальный идентификатор.

Pages:     ||
|



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

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