Алгоритм PageRank

был придуман основателями компании Google, и вариации этой идеи теперь применяются во всех крупных поисковых машинах. Этот алгоритм приписывает каждой странице ранг, оценивающий ее значимость. Значимость страницы вычисляется исходя из значимостей ссылающихся на нее страниц и общего количества ссылок, имеющихся на каждой из них.

Теоретически алгоритм PageRank (названный по фамилии одного из его изобретателей Лари Пейджа (Larry Page)) рассчитывает вероятность того, что человек, случайно переходящий по ссылкам, доберется до некоторой страницы. Чем больше ссылок ведет на данную страницу с других популярных страниц, тем выше вероятность, что экспериментатор чисто случайно наткнется на нее. Разумеется, если пользователь будет щелкать по ссылкам бесконечно долго, то в конце концов он посетит каждую страницу, но большинство людей в какой-то момент останавливаются. Чтобы учесть это, в алгоритм Page- Rank введен коэффициент затухания 0,85, означающий, что пользователь продолжит переходить по ссылкам, имеющимся на текущей странице, с вероятностью 0,85.

На рис. 4.3 приведен пример множества страниц и ссылок.

Рис. 4.3. Вычисление ранга PageRank страницы A

Каждая из страниц B, C и D ссылается на A, и для них ранг уже вычислен. На странице B есть ссылки еще на три страницы, а на странице C – на четыре. D ссылается только на A. Чтобы вычислить ранг A, берем ранги (PR) каждой ссылающейся на A страницы, делим их на общее число ссылок на этой странице, складываем получившиеся значения, затем умножаем результат на коэффициент затухания 0,85 и добавляем минимальную величину 0,15. Вот как производится вычисление PR(A):

PR(A) = 0,15 + 0,85 X (PR(B)/ссылки(B) + PR(C)/ссылки(C) + + PR(D)/ссылки(D)) = 0,15 + 0,85 X (0,5/4 + 0,7/5 + 0,2/1) = 0,15 + 0,85 X (0,125 + 0,14 + 0,2) = 0,15 + 0,85 X 0,465 =0,54525

Обратите внимание, что D дает больший вклад в ранг A, чем B или C, хотя ее собственный ранг меньше. Это вызвано тем, что D ссылается только на A и, значит, привносит в результат свой ранг целиком. Несложно, да? Увы, имеется тут небольшая ловушка – в данном примере для всех страниц, ссылающихся на A, уже вычислен ранг. Но невозможно вычислить ранг страницы, пока неизвестны ранги ссылающихся на нее страниц, а эти ранги можно вычислить, только зная ранги страницы, которые ссылаются на них. Так как же вычислить значение PageRank для множества страниц, ранги которых еще неизвестны? Решение состоит в том, чтобы присвоить всем страницам произвольный начальный ранг (в программе ниже взято значение 1,0, но на самом деле точная величина несущественна) и провести несколько итераций. После каждой итерации ранг каждой страницы будет все ближе к истинному значению PageRank. Количество необходимых итераций зависит от числа страниц, но для того небольшого набора, с которым мы работаем, 20 должно быть достаточно.

Поскольку вычисление значения PageRank занимает много времени, а вычисленный ранг не зависит от запроса, то мы напишем функцию, которая заранее вычисляет ранг каждого URL и сохраняет его в таблице. При каждом вызове эта функция будет пересчитывать ранги всех страниц. Добавьте ее в класс crawler:

def calculatepagerank(self,iterations=20):

#       стираем текущее содержимое таблицы PageRank self.con.execute(‘drop table if exists pagerank’) self.con.execute(‘create table pagerank(urlid primary key,score)’)

#       в начальный момент ранг для каждого URL равен 1

self.con.execute(‘insert into pagerank select rowid, 1.0 from urllist’) self.dbcommit( )

for i in range(iterations):

print "Итерация %d" % (i)

for (urlid,) in self.con.execute(‘select rowid from urllist’): pr=0.15

# В цикле обходим все страницы, ссылающиеся на данную

for (linker,) in self.con.execute(

‘select distinct fromid from link where toid=%%d’ % urlid):

# Находим ранг ссылающейся страницы linkingpr=self.con.execute(

‘select score from pagerank where urlid=%%d’ % linker).fetchone( )[0]

# Находим общее число ссылок на ссылающейся странице linkingcount=self.con.execute(

‘select count(*) from link where fromid=%%d’ % linker).fetchone( )[0] pr+=0.85*(linkingpr/linkingcount)

self.con.execute(

‘update pagerank set score=%%f where urlid=%%d’ % (pr,urlid)) self.dbcommit( )

Вначале эта функция приписывает каждой странице ранг 1,0. Потом в цикле перебираются все URL и для каждой ссылающейся на него страницы из базы извлекается значение PageRank и общее число ссылок на ней. Строка, выделенная полужирным шрифтом, содержит формулу, применяемую к каждой из внешних ссылок. Эта функция будет работать несколько минут, но запускать ее необходимо только после обновления индекса. >> reload(searchengine)

>> crawler=searchengine.crawler(‘searchindex.db’) >> crawler.calculatepagerank( )

Итерация 0 Итерация 1

Если вам интересно, какие страницы из рассматриваемого набора имеют максимальный ранг, можете запросить базу данных напрямую:

>> cur=crawler.con.execute(‘select * from pagerank order by score desc’) >> for i in range(3): print cur.next( )

(438, 2.5285160000000002) (2, 1.1614640000000001) (543, 1.064252) >> e.geturlname(438)

u’http://kiwitobes.com/wiki/Main_Page.html’ Наивысший ранг имеет главная страница Main Page, что и неудивительно, поскольку на нее есть ссылки с любой страницы Википедии. Теперь, когда у нас есть таблица рангов, для ее использования достаточно написать функцию, которая будет извлекать ранг и выполнять нормализацию. Добавьте в класс searcher следующий метод: def pagerankscore(self,rows):

pageranks=dict([(row[0],self.con.execute(‘select score from pagerank where urlid=%%d’ % row[0]).fetchone( )[0]) for row in rows]) maxrank=max(pageranks.values( ))

normalizedscores=dict([(u,float(l)/maxrank) for (u,l) in \

pageranks.items( )]) return normalizedscores

Включите этот метод в список weights, например, так:

weights=[(1.0,self.locationscore(rows)), (1.0,self.frequencyscore(rows)), (1.0,self.pagerankscore(rows))]

Теперь при ранжировании результатов учитывается как содержимое страницы, так и ее ранг. Результаты поиска по фразе Functional programming выглядят даже лучше, чем прежде:

2.318146 http://kiwitobes.com/wiki/Functional_programming.html 1.074506 http://kiwitobes.com/wiki/Programming_language.html 0.517633http://kiwitobes.com/wiki/Categorical_list_of_programming_languages. html

0.439568 http://kiwitobes.com/wiki/Programming_paradigm.html 0.426817 http://kiwitobes.com/wiki/Lisp_programming_language.html

Значение PageRank трудно оценить в полной мере на таком замкнутом, строго контролируемом наборе документов, в котором, скорее всего, почти нет ни вовсе бесполезных страниц, ни страниц, созданных только для привлечения внимания. Но даже в этом случае видно, что PageRank – полезная метрика, позволяющая возвращать более общие страницы, относящиеся к теме запроса.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100