Ранжирование по содержимому

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

В этом разделе мы рассмотрим несколько способов вычисления ранга на основе самого запроса и содержимого страницы, а именно: Частота слов

Количество вхождений в документ слова, указанного в запросе, помогает определить степень релевантности документа. Расположение в документе

Основная тема документа, скорее всего, раскрывается ближе к его началу. Расстояние между словами

Если в запросе несколько слов, то они должны встречаться в документе рядом.

Самые первые поисковые машины часто работали только с подобными метриками и тем не менее давали пристойные результаты. В следующих разделах мы посмотрим, как можно улучшить результат, принимая во внимание информацию, внешнюю по отношению к самой странице, например количество и качество указывающих на нее ссылок. Но сначала нам понадобится новый метод, который принимает на входе запрос, получает строки, помещает их в словарь и отображает в виде отформатированного списка. Добавьте в класс searcher следующие функции:

def getscoredlist(self,rows,wordids): totalscores=dict([(row[0],0) for row in rows])

# Сюда мы позже поместим функции ранжирования weights=[]

for (weight,scores) in weights: for url in totalscores: totalscores[url]+=weight*scores[url]

return totalscores

def geturlname(self,id): return self.con.execute(

"select url from urllist where rowid=%%d" % id).fetchone( )[0]

def query(self,q):

rows,wordids=self.getmatchrows(q) scores=self.getscoredlist(rows,wordids)

rankedscores=sorted([(score,url) for (url,score) in scores.items( )],\ reverse=1)

for (score,urlid) in rankedscores[0:10]:

print ‘%f\t%s’ % (score,self.geturlname(urlid))

Сейчас этот метод не применяет к результатам никакого ранжирования, но отображает URL, оставляя место для будущего ранга: >> reload(searchengine)

>> e=searchengine.searcher(‘searchindex.db’)

>> e.query(‘functional programming’)

0.000000 http://kiWitobes.com/wiki/XSLT.html

0.000000 http://kiWitobes.com/wiki/XQuery.html

0.000000 http://kiwitobes.com/wiki/Unified_Modeling_Language.html

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

Функция нормализации

Все рассматриваемые ниже функции ранжирования возвращают словарь, в котором ключом является идентификатор URL, а значением – числовой ранг. Иногда лучшим считается больший ранг, иногда – меньший. Чтобы сравнивать результаты, получаемые разными методами, необходимо как-то нормализовать их, то есть привести к одному и тому же диапазону и направлению.

Функция нормализации принимает на входе словарь идентификаторов и рангов и возвращает новый словарь, в котором идентификаторы те же самые, а ранг находится в диапазоне от 0 до 1. Ранги масштабируются по близости к наилучшему результату, которому всегда приписывается ранг 1. От вас требуется лишь передать функции список рангов и указать, какой ранг лучше – меньший или больший: def normalizescores(self,scores,smallIsBetter=0): vsmall=0.00001 # Предотвратить деление на нуль if smallIsBetter: minscore=min(scores.values( ))

return dict([(u,float(minscore)/max(vsmall,l)) for (u,l) \ in scores.items( )]) else:

maxscore=max(scores.values( )) if maxscore==0: maxscore=vsmall

return dict([(u,float(c)/maxscore) for (u,c) in scores.items( )]) Каждая функция ранжирования вызывает эту функцию для нормализации полученных результатов.

Частота слов

Метрика, основанная на частоте слов, ранжирует страницу исходя из того, сколько раз в ней встречаются слова, упомянутые в запросе. Если я выполняю поиск по слову python, то в начале списка скорее получу страницу, где это слово встречается много раз, а не страницу о музыканте, который где-то в конце упомянул, что у него дома живет питон.

Ниже приведена соответствующая функция, добавьте эту функцию в класс searcher:

def frequencyscore(self,rows):

counts=dict([(row[0],0) for row in rows]) for row in rows: counts[row[0]]+=1 return self.normalizescores(counts)

Эта функция создает словарь, в котором для каждого идентификатора URL, встречающегося в списке rows, указано, сколько раз в нем попадаются слова, указанные в запросе. Затем она нормализует ранги (в данном случае чем больше ранг, тем лучше) и возвращает результат. Чтобы активировать ранжирование документов по частоте слов, измените строку функции getscoredlist, где определяется список weights, следующим образом:

weights=[(1.0,self.frequencyscore(rows))] Теперь можно снова выполнить поиск и посмотреть, что получится при использовании этой метрики: >> reload(searchengine)

>> e=searchengine.searcher(‘searchindex.db’) >> e.query(‘functional programming’)

1.000000 http://kiwitobes.com/wiki/Functional_programming.html 0.262476http://kiwitobes.com/wiki/Categorical_list_of_programming_languages. html

0.062310 http://kiwitobes.com/wiki/Programming_language.html 0.043976 http://kiwitobes.com/wiki/Lisp_programming_language.html 0.036394 http://kiwitobes.com/wiki/Programming_paradigm.html

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

Расположение в документе

Еще одна простая метрика для определения релевантности страницы запросу – расположение поисковых слов на странице. Обычно, если страница релевантна поисковому слову, то это слово расположено близко к началу страницы, быть может, даже находится в заголовке. Чтобы воспользоваться этим наблюдением, поисковая машина может

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

Добавьте в класс searcher следующий метод:

def locationscore(self,rows):

locations=dict([(row[0],1000000) for row in rows]) for row in rows: loc=sum(row[1:])

if loc<locations[row[0]]: locations[row[0]]=loc

return self.normalizescores(locations,smallIsBetter=1) Напомним, что первый элемент в каждой строке row – это идентификатор URL, а за ним следуют адреса вхождений всех поисковых слов. Каждый идентификатор может встречаться несколько раз, по одному для каждой комбинации вхождений. Для каждой строки этот метод суммирует адреса вхождений всех слов и сравнивает результат с наилучшим, вычисленным для данного URL к текущему моменту. Затем окончательные результаты передаются функции normalize. Заметьте, параметр smallIsBetter означает, что ранг 1,0 будет присвоен URL с наименьшей суммой адресов вхождений.

Чтобы выяснить, как будет выглядеть результат, если учитывать только расположение в документе, измените определение списка weights следующим образом:

weights=[(1.0,self.locationscore(rows))] А теперь снова выполните запрос в интерпретаторе: >> reload(searchengine)

>> e=searchengine.searcher(‘searchindex.db’) >> e.query(‘functional programming’)

Вы увидите, что страница Functional programming по-прежнему на первом месте, но за ней следуют примеры языков функционального программирования. Ранее были возвращены документы, в которых поисковые слова встречались несколько раз, но это, как правило, были обсуждения языков программирования вообще. Теперь же присутствие поисковых слов в первых предложениях документа (например, Haskell is a standardized pure functional programming language) придает ему гораздо более высокий ранг.

Важно понимать, что ни одна из вышеупомянутых метрик не лучше другой во всех случаях. Оба списка приемлемы в зависимости от намерений ищущего, и для достижения оптимальных результатов для конкретного набора документов и приложения требуется задавать разные веса. Поэкспериментировать с заданием весов для обеих метрик можно, изменив строку weights примерно так: weights=[(1.0,self.frequencyscore(rows)), (1.5,self.locationscore(rows))]

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

Расстояние между словами

Если запрос содержит несколько слов, то часто бывает полезно ранжировать результаты в зависимости от того, насколько близко друг к другу встречаются поисковые слова. Как правило, вводя запрос из нескольких слов, человек хочет найти документы, в которых эти слова концептуально связаны. Это более слабое условие, чем фраза, заключенная в кавычки, когда слова должны встречаться точно в указанном порядке без промежуточных слов. Рассматриваемая метрика допускает изменение порядка и наличие дополнительных слов между поисковыми.

Функция distancescore очень похожа на locationscore: def distancescore(self,rows):

#    Если есть только одно слово, любой документ выигрывает!

if len(rows[0])<=2: return dict([(row[0],1.0) for row in rows])

#    Инициализировать словарь большими значениями mindistance=dict([(row[0],1000000) for row in rows])

for row in rows: dist=sum([abs(row[i]-row[i-1]) for i in range(2,len(row))])

if dist<mindistance[row[0]]: mindistance[row[0]]=dist return self.normalizescores(mindistance,smallIsBetter=1)

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

Вы можете следить за любыми ответами на эту запись через 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