WWW.DISSERS.RU

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

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

Pages:     ||
|

- 84 Алгоритм 1. E = sort(e ); // сортировка рёбер по весу sorted weight 2. while(|E | > 0 && (E [0] < C )) BEGIN sorted sorted max 3. e = E [0]; // v, v – вершины смежные ребру e sorted 1 4. E = E \ Г(v ); // удалить из упорядоченного массива рёбер рёбра sorted sorted смежные v 5. merge(e); // объединить вершины-кластеры v и v в кластер v, 1 2 то есть добавить вершину v в кластер v, изменив свойства v так:

2 1 a) v += v ; // увеличить размер кластера (число категорий и статей) 1 weight 2 weight b) |v | += |v |; // увеличить число статей 1 articles 2 articles c) |v | += |v |; // увеличить число рёбер 1 edges 2 edges d) v [] += addUnique(v []); // добавить категории без повторов 1 category_id 2 category_id (на основе уникальности идентификаторов) 6. passEdges(); // все рёбра смежные вершине v2 передать вершине v(рёбра без повторений, это не мультиграф).

7. E = E \ edge (v, v ); // удалить ребро (v, v );

sorted sorted 1 2 1 8. updateEdgesOfMergedCluster; // обновить указатели на вершины, удалить ребра (вершины и рёбра, смежные удаляемой вершине) 9. updateEdgeWeight(v ); // пересчитать значения весов для всех рёбер смежных v10. remove(Clusters, v ); // удалить кластер v из массива кластеров 2 11. E = sort(e ) // пересортировка рёбер, сложность O(N), т. к. нужно sorted weight обновить порядок только тех рёбер, которые смежны вершине v 12. END 13. Return Clusters Результат работы алгоритма – это кластеры категорий (Clusters). По кластеру категорий получаем кластер статей, поскольку для каждого кластера c определено значение с (список статей, ссылающиеся на категории в articles кластере).

Заметим, что одна статья может ссылаться на несколько категорий.

Поэтому одна статья может принадлежать нескольким кластерам. Но категория принадлежит ровно одному кластеру.

- 85 Варианты объединения результатов АHITS алгоритма и алгоритма кластеризации Могут быть реализованы следующие варианты:

1) Использовать информацию о каждой вершине (hub, authority) (в алгоритме кластеризации) для вычисления начального веса кластера на этапе предобработки, в шаге 1б:

nvarticle (2.7) cweight=1k hvav v: vC Здесь h и a вычислены с помощью адаптированного HITS алгоритма, k – v v весовой коэффициент (параметр), наличие единицы объясняется тем, что на этапе предобработки кластер содержит только категорию. Суммирование проводится по всем статьям, которые ссылаются на категории кластер.

2) Выбрать (после кластеризации) из каждого кластера подмножество hub, authority статей с максимальным весом и представить пользователю как наборы синонимов и близких по значению слов (для исходного слова), сгруппи­ рованные по значению. Открытым остаётся вопрос – как определить число значений (здесь – кластеров) у слова На данный момент число кластеров определяется максимально разрешённым весом кластера (параметр алгоритма кластеризации C ).

max Временная сложность алгоритма Обозначим C – число категорий, N – число статей (число страниц в базовом наборе). Первый шаг предобработки требует O(CN) операций, второй – O(C2). Тогда предобработка в целом требует O(CN+C2) операций.

В алгоритме первый шаг (сортировка рёбер) требует не более O(C2) операций. Циклов (шаг 2) должно быть не больше числа рёбер, то есть O(C2), так как на каждом витке цикла удаляется одно ребро. Наиболее вычислитель­ но затратным будет пятый шаг, так как для объединения вершин необходимо O(C+N) операций, поскольку нужно обойти категории и статьи, соседние для объединяемых кластеров. Тогда предобработка и алгоритм кластеризации в целом требуют O(CN + C2) + O(C2(C + N)) = O(C3 + NC2) - 86 Временная сложность [20] вычисления весов (hub, authority) в HITS алго­ ритме составляет O IkN, где I – число итераций в адаптированном HITS k алгоритме. Тогда общая сложность адаптированного HITS алгоритма будет:

OC3N C2 Ik N (2.8) где: I – число итераций на шаге 3 в адаптированном HITS алгоритме;

k C – число категорий;

N – число статей (число страниц в базовом наборе).Эвристика: фильтрация на основе категорий статей Предлагается следующий способ сужения поиска похожих документов в корпусе документов с категориями.

N Дано:

(глубина поиска) и Category – чёрный список кате­ Blacklist горий, про которые заранее известно, что документы с такими категориями не подходят, то есть не являются похожими на исходный документ.

Для использования этих данных нужно выполнить фильтрацию стра­ ниц при построении корневого и базового набора страниц (первые два шага адаптированного HITS алгоритма), состоящую в следующем. Если категории страницы, или их надкатегории (не более N уровней относительно исходной страницы2) принадлежат списку Category, то страница пропускается и Blacklist не добавляется в корневой / базовый набор, иначе – добавляется.

Данная эвристика была реализована в программе Synarcher, см.

подраздел «Модуль визуализации: интерфейс и функции» на стр. 99.

2.4 Вычисление меры сходства вершин графа. Оценка временной сложности. Эвристики Дано: направленный граф G=(V, E), где V – вершины (страницы), E – дуги w V (ссылки),. Для каждой страницы v известны два списка: Г+(v) – это страницы, на которые ссылается данная статья, и Г(v) – это страницы, ссылающиеся на данную статью. Для каждой вершины определены значения {v V : av,hv} двух весовых коэффициентов authority и hub:.

1 Из числа статей и категорий в Английской (659 358, 113 483) и Немецкой (305 099, 27 981) Википедиях (на 01.2006 г. по [94]) следует, что три слагаемых оценки отличаются друг от друга менее чем в 104.

2 Полагаем, что категория c1 страницы – это первый уровень, надкатегория c2 категории c1 – это второй уровень, надкатегория c3 категории c2 – это третий уровень и т.д.

- 87 Необходимо найти набор вершин A, похожих на вершину w.

Определение похожести вершин графа приведено ниже и оно отличается от приведённого в подразделе «Формализация понятия «похожие вершины» графа» на стр. 76 тем, что (i) в результате работы алгоритма строится массив сходства вершин, (ii) не используются понятия авторитетных и хаб-страниц.

Задачу поиска похожих статей, которую решает адаптированный HITS алгоритм можно переформулировать в терминах теории графов так.

Задача поиска похожих вершин графа.

w V Дано: направленный граф G=(V, E), где V – вершины, E – дуги,.

ziV,i=1... n Найти: n вершин графа G максимально похожие на w, ya,b упорядоченные по степени сходства. Степень сходства между двумя вершинами а и b определим рекуррентно:

k b1-k y x, y a x a, y b ya,b=, 0k1 (2.9) y v, w v,w V V Первое слагаемое1 в числителе (2.9) – это число общих вершин среди соседей вершин a и b, второе слагаемое – это суммарное сходство соседей вершин a и b. В знаменателе – суммарное сходство по всем парам графа G. Весовой коэффициент k позволяет выбрать компонент, который оказывает большее влияние на суммарное сходство: число общих соседей или степень сходства между соседними вершинами.

ya,b=Таким образом,, если (1) у вершин a и b нет общих соседей и (2) среди вершин соседних a и b степень сходства равна нулю:

y x, y= (2.10) x a, y b где a, b – это множество соседних вершин для вершин a и b соответственно. Такая постановка задачи определяет следующий алгоритм поиска похожих вершин графа.

1 Таким образом, получили рекуррентную формулу вычисления меры сходства между вершинами одного графа алгоритма SimRank [119] (стр.5, формула (5)). Разница заключается в наличии первого слагаемого в формуле (2.9), определяющего число общих соседей. Очевидно, что об общих соседях можно говорить в случае поиска похожих вершин для одного графа, а не в общем случае сравнения вершин разных графов.

- 88 Алгоритм поиска похожих вершин графа CalcSimilarVertices(G,, k) G=(V,E) – граф c N вершинами, k, где – погрешность вычислений k – весовой коэффициент Y[][] – сходство между вершинами графа 1. // инициализация Y2. for(i=0; i ) { 10. norma = 11. for(i=0; i

x vi, y v j 14. norma += Y[i][j] 15. } 16. } 17. for(i=0; i

norma 20. Ydelta[i][j] = |Y[i][j] – Yold[i][j]| 21. Yold[i][j] = Y[i][j] 22. } 23. } N error= Ydelta[i][ j] 24.

i, j =25. } 1 Другой вариант инициализации – начальное значение весов вершин может быть вычислено, например, с помощью HITS алгоритма (вес authority берётся за начальный).

- 89 В шагах 13, 14, 19 реализуется формула (2.9) вычисления сходства между iой и j-ой вершинами графа. Шаги 20, 21 и 24 вычисляют суммарное изменение (error) на данном шаге итерации (цикл while).

В результате работы алгоритма получаем симметричный массив сход­ ства вершин Y[][]. Теперь для поиска упорядоченного списка максимально похожих вершин, например на j-ую, достаточно отсортировать одномерный массив Y[j][].

Остаются открытыми следующие вопросы:

доказательство сходимости итеративного алгоритма;

скорость сходимости в реальных экспериментах.

Оценка временной сложности Шаги вложенных циклов 9, 11, 12 и 9, 17, 18 дают сложность O(IN2), где I – число итераций, N – число вершин в графе.

Шаг 13 требует поиска пересечений всех соседей двух вершин. Поиск пересечения двух множеств размерности N требует O(N) операций (например с помощью меток). Тогда временная сложность алгоритма O(IN3).

Постараемся уменьшить временную сложность [20] алгоритма с помощью эвристик.

Эвристики1) В первой эвристике предлагается рассматривать не все пары вершин (как кандидаты на «похожие» вершины), а только те, у которых совпадают не менее L соседей.

При этом циклы на шагах 11, 12 и 17, 18 потребуют не O(N2) операций, а O(M2), где M – число вершин, которые имеют не менее L общих вершин.

Число M можно определить (сравнив попарно вершины на наличие не менее L соседей) до выполнения алгоритма за время O(N3), где N – число вершин графа. Вычислив M, можно принять решение: будет ли эвристика 1 В алгоритме SimRank [119] предлагается следующая эвристика: отсекать вершины (pruning), находящиеся на значительном расстоянии от вершины v, и поэтому, вероятно, имеющей мало общих вершин с отсекаемыми. Таким образом, в SimRank рассматриваются (как потенциально похожие) вершины, удалённые не более чем на радиус r друг от друга (где радиус – это один из параметров алгоритма).

- 90 давать значительный выигрыш в скорости при данном L либо нужно увеличить L и повторить вычисления.

Таким образом, вычисление степени сходства между M вершинами с помощью функции CalcSimilarVertices потребует времени O(IM3). После этого один раз выполняется тело цикла while (шаги 10-23) для вычисления степени сходства между всеми N вершинами за O(N2) операций. Таким образом, суммарная временная сложность составит O(IM3+N3).

2) Предлагается эвристика (для алгоритма поиска похожих вершин графа), использующая результаты работы HITS алгоритма.

После применения HITS алгоритма к графу G=(V, E) с N вершинами получено M особых вершин (а именно: авторитетные и хаб-страницы), причём M – это параметр алгоритма.

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

k Число итераций I (вслед за работой1) можно оценить, как:

O Nhlog h, где h – это число правильно найденных авторитетных вершин, k O N k всего найдено k авторитетных вершин. Необходимое условие:.

Далее аналогично первой эвристике: (1) выполнение функции CalcSimilarVertices потребует O(IM3) операций для вычисления значения степени сходства между M вершинами и (2) O(N2) для вычисления степени сходства между всеми N вершинами. Суммарная временная сложность будет 3 2 O IM N I N.

k k Преимущество перед первой эвристикой второй эвристики 3 2 (вычисляемой соответственно за O(IM3+N3) и O IM N I N операций) k k в том, что число обрабатываемых вершин M задаётся напрямую, а не вычисляется (за O(N3)) через параметр L (число общих соседей).

1 Peserico E., Pretto L. The rank convergence of HITS can be slow. 2008. http://arxiv.org/abs/0807.3006.

- 91 2.5 Показатели численной оценки семантической близости списка слов Для экспериментальной оценки алгоритма необходимо научиться численно автоматически оценивать набор слов, сформированный AHITS алгоритмом.

Можно указать, по крайней мере, два способа использования такой оценки.

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

Таким образом, разработано несколько показателей численной оценки полученного набора синонимов: SER, ER и коэффициент Спирмена.

SER (Strong Error Rate) – число слов (в процентах от общего числа найденных слов), которые не имеют отношения к исходному слову (определяется либо вручную – экспертом, либо автоматически – по наличию/ отсутствию в тезаурусе, например WordNet, Moby1).

Wordsw Wordsw Wordsw AHITS WordNet Moby SERw= (2.11) Wordsw Wordsw Wordsw AHITS WordNet Moby ER (Error Rate) – число слов (в процентах), не являются синонимами (определяется вручную экспертом либо автоматически – по наличию/отсутствию в тезаурусе WordNet).

Wordsw Wordsw AHITS WordNet ERw = (2.12) Wordsw Wordsw AHITS WordNet Где Wordsw – множество слов, найденных с помощью AHITS адаптированного HITS алгоритма для слова w, Wordsw – список WordNet синонимов из тезауруса WordNet для слова w, Wordsw – список слов Moby 1 Moby Thesaurus List by Grady Ward, см. http://www.dcs.shef.ac.uk/research/ilash/Moby - 92 близких по значению из тезауруса Moby. Очевидно, что ER SER, поскольку в SER вычитаются слова из обоих тезаурусов: WordNet и Moby.

Открытые вопросы:

1. Сильно ли изменятся значения SER и ER, если в знаменателе будет стоять только Wordsw Вероятно, это сильно связано с числом AHITS найденных синонимов адаптированным HITS алгоритмом.

Pages:     ||
|



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

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