Лекция - Internet алгоритмы - файл n1.doc

Лекция - Internet алгоритмы
скачать (6906.1 kb.)
Доступные файлы (2):
n1.doc5701kb.30.09.2011 21:39скачать
n2.pdf1989kb.28.09.2011 14:53скачать

n1.doc

А.В. Цыганов 2008
Internet алгоритмы I



65% startup компаний приходится на создание поисковых систем




Виды поиска в WWW


поиск по

известным адресам


Тематические

каталоги

Поисковые машины

Специализированный поиск в базах данных

(резервирование, поиск справочной информации о людях,

организациях …)


Wikipedia, arXiv, Math World, Planet Math, Science World,

Physics.org, The Math Forum, S.O.S. Mathematics,

www.springerlink.com, www.iop.org и.т.д.





Критерии профессионального поиска:
 контроль полноты охвата ресурсов;
 контроль достоверности информации, полученной из Сети (точность);
 высокая скорость проведения поиска;
 удобство, понятность и пр. субъективные критерии




Релеван́ тность (relevant) - степень соответствия запроса и найденного,

уместность результата.


Это субъективное понятие, поскольку результаты поиска, уместные для одного

пользователя, могут быть неуместными для другого.


Релевантным называется документ или страница в интернете, которая

формально соответствует сути сделанного через поисковую систему запроса.


При оценке релевантности информации, найденной в интернете, оценивается

· полнота информации, означающая, что ничего из имеющегося в интернете

не потеряно

· точность, показывающая, что не найдено ничего лишнего из имеющейся в

сети информации.

Что влияет на

релева́нтность?


</b>Что такое релевантность и пертинентность, как сделать<b> </b><b>релевантный</b><b> </b><b>сайт</b>, как оценить<br /> <br /> <b>релевантность</b><b> </b><b>сайта</b>,<b> </b><b>определение</b><b> </b><b>релевантности</b>











……

Что такое релевантность

…..

….Вопросы поиска необходимой информации в интернете, представляющем из себя огромное

информационное пространство с массой содержащихся разнообразных информационных

данных, потребность в которых испытывают все пользователи всемирной сети, являются очень

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



Семантические показатели - основаны на оценке релевантности между

документами и запросами
Полнота выдачи (ПВ)



ПВ =

��

�� + ��



а – множество релевантных и выданных системой документов
b – множество релевантных, но не выданных системой документов


Потери информации (ПИ)

ПИ =

��

�� + ��

а – множество релевантных и выданных системой документов
b – множество релевантных, но не выданных системой документов


Точность выдачи (ТВ)

ТВ =

��

�� + ��



а – множество релевантных и выданных системой документов
c – множество нерелевантных, но выданных системой документов


Информационный шум (ИШ)

ИШ =

��

�� + ��

а – множество релевантных и выданных системой документов
c – множество нерелевантных, но выданных системой документов


Пертинентность

Пертинентность (рertinence) – субъективно оцениваемое соответствие
полученной информации информационной потребности пользователя.

Грубо говоря это отношение объема полезной для пользователя информации
к объему информации полученной по запросу, т.е. КПД поиска.
Можно улучшить, используя учёт прошлых интересов данного пользователя,

учёт поведения пользователей на поисковике, уточнение формулировок

запросов, ранжирование по весовым критериям, ограничение числа

выданных в результате поиска документов……


В


свое


время


Google


реализовала


новые


алгоритмы


достижения

неформальной релевантности (пертинентности) и благодаря этому стала

самой популярной ПС в интернете…..


При создании сайтов, кроме решения важных вопросов дизайна сайта и его

наполненности, необходимо оценивать релевантность и пертинентность

сайта, с точки зрения отношения к нему существующих поисковых систем.




Алгоритм + Структура данных = Поисковая система


Как и любая программа, поисковая система оперирует со структурами данных

и исполняет алгоритм.


В настоящее время есть четыре класса поисковых алгоритмов.


Три алгоритма из четырех требуют «индексирования», предварительной

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

«индекс», призванный упростить и ускорить сам поиск.


Это алгоритмы инвертированных файлов, суффиксных деревьев и сигнатур.


Четвертый класс алгоритмов прямого поиска не требует индексирования.

Анатомия поисковой системы

Любая поисковая система содержит три базовых части:

· Робот - краулер, спайдер, индексатор …..

Извлечение и накопление данных документов.

· Базы данных - обработка полученных данных и создание данных,

пригодных для поиска.

· Клиент – обработка запросов (поиск по созданным данным).
Существует масса других частей, однако их назначение заключается главным

образом именно в эффективной поддержке этих трёх базовых.


Анатомия поисковой системы (2)





Анатомия поисковой системы (3)





«Паук» (spider)
Web spider или Web scraper – это разновидности программных роботов или

агентов (в терминологии, предложенной Аланом Кеем (Alan Kay) в начале

1980-х годов).


Программный агент должен действовать в качестве посредника (proxy) между

пользователем

и

компьютерным

миром.

Такой

агент

может

иметь

определённую цель и должен работать над достижением этой цели в

отведённой ему области.


Цель может состоять в сборе информации или в понимании структуры какого-

либо Web-сайта и его полезности. Такие пауки автоматически извлекают

данные из Web-сайта ( например HTML-код документа) и передают их другим

приложениям, которые индексируют контент этого Web-сайта с целью

формирования наилучшего набора поисковых терминов.





"Web-скребок" (Web scraper) – это агент, который действует аналогично Web-

паукам, но более интересен с юридической точки зрения.

Scraper – это разновидность паука, которая нацелена на работу с

определённым Интернет-контентом, например, с данными о стоимости

продуктов или услуг.


Один из вариантов применения scraper-

агентов – конкурентное ценообразование,

т. е. выявление существующих на рынке

цен на определённую категорию товаров с

целью установления соответствующих цен

на собственную продукцию.

Кроме того, scraper способен объединять

данные

из

нескольких

источников

в

Интернете и предоставлять эту итоговую

информацию пользователю и т.д.






Глаза и ноги паука


Основными органами зрения и перемещения Web-паука в Интернете является

HTTP – ориентированный на сообщения протокол, с помощью которого клиент

подключается к серверу и посылает запросы.


В ответ на эти запросы сервер генерирует отклик. Каждый запрос или отклик

состоит из заголовка и тела. Заголовок содержит информацию о состоянии и

описание содержимого тела.


Протокол HTTP поддерживает запросы трех основных типов.

 Запрос типа HEAD запрашивает информацию об активах определенного

сервера.

 Запрос типа GET запрашивает сам актив, например, файл или

изображение.

 Запрос типа POST разрешает клиенту взаимодействовать с сервером через

Web-страницу (обычно через Web-форму).

Простой агент типа Web scraper (другое название – screen scraper) для сбора

информации о котировках акций - приведен сценарий на языке Ruby.
#!/usr/local/bin/ruby

require 'net/http'

host = "www.smartmoney.com"

link = "/eqsnaps/index.cfm?story=snapshot&symbol="+ARGV[0]

begin
# Create a new HTTP connection

httpCon = Net::HTTP.new( host, 80 )
# Perform a HEAD request

resp = httpCon.get( link, nil )
stroffset = resp.body =~ />/
subset = resp.body.slice(stroffset+14, 10)
limit = subset.index('<')
print ARGV[0] + " current stock price " + subset[0..limit-1] +

" (from stockmoney.com)\n"
end

«Червяк» (crawler)
· Программа, способная найти на web-странице все ссылки на другие

страницы.


· Ее задача – определить, куда дальше должен «ползти» «паук»,

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

Каждую найденную ссылку в документе crawler должен проверить на

правильность, с точки зрения интернет-имени сервера.

Для этих целей используется стандартный механизм DNS – однако если

рассматриваемая страница содержит массу ссылок на другие страницы и

при этом первичный сервер зоны, в которой располагаются данные

страницы в данный момент по каким-либо причинам не доступен, то

возникают

огромные

потери

времени

на

попытках

установления

соответствия - в итоге ваша страничка не индексируется!!!!


Web-пауки и краулеры минимизируют порождаемую ими нагрузку на Интернет

с помощью набора политик.


Чтобы представить масштабы проблемы, необходимо учесть, что Google

индексирует более 8 млрд. Web-страниц. Поиск в Интернете весьма дорог, как с

точки зрения пропускной способности, необходимой для передачи Web-

контента индексатору, так и с точки зрения вычислительных затрат на

индексирование результатов.


Политики поведения определяют, какие страницы Web-краулер должен вводить

в индексатор и как часто Web-краулер должен возвращаться на какой-либо Web-

сайт для повторной проверки, а также т.н. "политику вежливости".


Web-серверы могут запрещать работу краулеров с помощью стандартного

файла robot.txt, который сообщает краулерам о том, что можно, а что нельзя

просматривать на данном сервере + такие директивы как Disallow, Allow, User-

agent, Crawl-delay и другие.

Индексатор (Indexer)

· Программа, которая «разбирает» web-страницу на составные

части и анализирует их.
· Вычленяются и анализируются заголовки, ссылки, текст

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

шрифтом, курсивом и т.п.
( вспомните про алгебраический тип данных )




База данных (database)
· Хранилище всех данных, которые поисковая система загружает и

анализирует.

· Требует огромных ресурсов как для хранения, так и для последующей

обработки.


В 2008 году

63,272 Machines

126,544 Processors

253,088 GHz Proccessing ability

126,544 GB Memory

5,062 TB Hard Drive Space

Data center Google in US





Система выдачи результатов поиска (Search Engine

Results Engine - клиент)




Индексация и индекс

· Процесс загрузки информации из интернета и предварительного

анализа ее поисковой машиной называют индексацией.


· База данных ПС, в которой храниться вся информация – это и есть

индекс , грубо говоря.





Перед нами упорядоченный по алфавиту список слов. Для каждого слова

перечислены все «позиции», в которых это слово встретилось (первая цифра

- глава, вторая - стих)
Поисковый алгоритм состоит в отыскании нужного слова и загрузке в память

уже созданного списка позиций.





Вопрос, что индексировать
· волк или волка или волку.
· ЗАмок или заМОК ( ударение)
· Большие/маленькие буквы - General Motors
· Пунктуация - C.Ш. А. или США (сокращение, аббревиатура).
· Числа (в каком формате?) 3/12/91, Март 12,1991
55 В.С, В-55
· Как обрабатывать синонимы и омонимы, индексировать

эквивалентные слова или расширять/уточнять запрос?
· Классы эквивалентности:

автомашина и автомобиль

опушка – край леса или меховая обшивка одежды?


Пример - выделение корня
· Сокращаем слова к их корню до их индексирования

-языковая зависимость

-например, бегун, побег, пробежка все сокращаются к бег.
Для примера, слова бегун

и бегунок предполагаются

относящимися к слову бег

Так как корни бег и бег

совпадают с корнем бег.
"алгоритм стемминга", от слова стем - "корень".


Пример - алгоритм Портера
· Обычный алгоритм для выделения корня в англоязычных текстах
· Соглашения + 5-фазное сокращение
– фазы применяют последовательно
– каждая фаза состоит из набора команд
– пример соглашения: из правил в составной команде, выбираем

применимое к самому длинному суффиксу.
· Типичные правила Портера


– Прилагательное
– Множественное число
существительное
единичное число

The Porter Stemming AlgorithmPorters homepage. (англ.)

The Porter Stemming AlgorithmProject «Snowball» (англ.)

The English (Porter2) stemming algorithm (улучшенная версия алгоритма)Project

«Snowball» (англ.)







Механизмы и алгоритмы поиска
Каждая поисковая система использует свой алгоритм поиска и его детали

представляют

собой

ноу-хау

разработчиков

поисковика.



(есть классификация алгоритмов и систем)


Алгоритм поиска – метод, руководствуясь которым поисковая система

принимает решение, включать или не включать ссылку на web-страницу

в результаты поиска.


ПC осуществляет отбор на основании постоянно меняющихся критериев -

например:

· Title (заголовок): Имеется ли ключевое слово в заголовке?

· Domain/URL (Домен/адрес): Имеется ли ключевое слово в имени домена / в

адресе страницы?

· Style (стиль): (STRONG или B), Курсив (EM или I), Заголовки HEAD.

· Density (плотность): Количество ключевых слов относительно всего текста

страницы называется плотностью ключевого слова.

· MetaInformation (мета данные): - мета ключевые слова (meta keywords) и

мета описания (meta description).

· Outbound Links (ссылки наружу): Какие ссылки есть на странице и содержит

ли они и ключевое слово?

·Inbound Links (внешние ссылки): Имеются ли в Интернет ссылки на данный

сайт? Каков текст ссылки? «внестраничный» критерий (автор страницы не

всегда может им управлять).

· Insite Links (ссылки внутри страницы): Какие ссылки на страницы данного

сайта содержит эта страница?
Закономерности поиска

· Правило Парето
· Правило S

· Законы Зипфа-Мандельброта

· Закономерность Брэдфорда

· Закономерность Хипса
Правило Парето 80/20


Анализируя


общественные


процессы,


Парето

рассматривал социальную среду как пирамиду.


В результате кропотливых исследований ученый

сформулировал математическую зависимость между

величиной дохода и количеством получающих его лиц.


Ученый в 1906 году установил, что 80 процентов земли

в Италии принадлежит лишь 20 процентам ее

жителей.


Парето пришел к выводу, что параметры полученного

Вильфредо

Парето

им

распределения

примерно

одинаковы

и

не

различаются принципиально в разных странах и в

разное время.




Распределение Парето

Распределение доходов по Парето описывается уравнением:

N = A p+1,

где Х величина дохода, N - численность людей с доходом, равным или выше Х,

A и p - коэффициенты уравнения - Х ?1, p > 0.

Распределение Парето обладает свойством устойчивости, т.е. сумма двух

случайных переменных, имеющих распределение Парето, также будет иметь

это распределение.
Wiki




При информационном поиске достаточно определить 20% необходимых

ключевых слов, позволяющих найти 80% требуемых документов.


80% посещений Web-сайта приходится лишь на 20% его Web-страниц.


При создании (программировании) необходимо учитывать то, что

наиболее

сложным

функциональным

возможностям

системы,

на

реализацию которых ушло > 80% трудозатрат будут использоваться не

более, чем 20% пользователей данной системы.


Если предположить, что идеальная система имеет 100% необходимых

функций, а систему, которая реализует 90% функций можно создать за 10

человеко-лет, то для доведения функциональности системы до уровня 95%

потребуется еще не менее 10-ти человеко-лет.


Таким образом, цена последних 5-ти процентов равна цене всей

системы, работающей с функциональностью 90%.

О переходе количества в качество

Если система достигла 99% своей идеальной функциональности, то дальнейшие

попытки ее совершенствования ведут, в лучшем случае, к повышению качества

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

по оси абсцисс затраченные ресурсы на развитие системы, а по оси ординат -

уровень функциональности, то график будет иметь вид кривой,
у которой в начале наблюдается резкий подъем, и которая стабилизируется –

распределение Парето.




Буква S технологического прогресса

В реальной жизни бывают случаи, когда после длительного процесса

стабилизации происходит резкий взлет этой кривой выше уровня 100%, т.е.

график принимает вид перевернутой буквы S.

Этот феномен обычно бывает связан с появлением новых подходов и

взглядов на ставшие уже традиционными устоявшиеся процессы.



Законы Зипфа (Ципфа)Мандельброта

· Зипф заметил, что длинные слова встречаются в

текстах любого языка реже, чем короткие.

· Это по всей видимости связано с природой человека

и вообще любого живого существа.

· На основе этого наблюдения Зипф вывел два закона.





Первый закон Зипфа


·


·
·

·


·
·

Первый закон связывает частоту появления (вхождения) того или иного слова с

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

Зипф обнаружил, что произведение частоты вхождения слова и его ранга

является постоянной величиной.

Такая зависимость обычно отображается гиперболой.

Значение константы Зипфа для разных языков различно, но внутри одной

языковой группы оно остается неизменным.
Для русского и украинского языков коэффициенты Зипфа составляют

приблизительно 0,06-0,07.


Первый закон Зипфа

0,07

0,06

0,05

0,04

0,03

0,02

0,01

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Ранг слова в списке






Второй закон Зипфа

·Частота вхождения слов и количество слов, входящих в текст с данной

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

пределах одного языка.
·С другой стороны, на каком бы языке текст ни был написан, форма

кривой

Зипфа

останется

неизменной.

Отличаться

будут

лишь

коэффициенты.
частота вхождения слов






Следствия законов Зипфа

· Законы Зипфа универсальны. Они применимы не только к текстам.


· В аналогичную форму выливается, например, зависимость между

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


· Характеристики популярности ресурсов интернета отвечают законам

Зипфа.


· В законах Зипфа отражается «человеческое» происхождение объектов –

т.е. можно отличать искусственное от природного – например

распределение кратеров на Луне.


·
Известный математик Бенуа Мандельброт математическим путѐм пришѐл к аналогичной

первому закону Зипфа зависимости f*re = c , где e - близкая к единице переменная величина,

которая

может

изменяться

в

зависимости

от

свойств

текста

и

языка


Как ПС используют законы Зипфа


· Из анализа графика можно предположить, что наиболее значимые

для текста слова лежат в средней части графика.

0,07

0,06

0,05

0,04

0,03

0,02

0,01

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Ранг слова в списке





Центральная часть графика

Центральная зона графика содержит термины (слова), наиболее характерные
именно для данного текста – по правилу Парето их будет около 20%!.

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

Каждая ПС по-своему решает, какие слова отнести к наиболее значимым.

Однако, если к числу значимых будет отнесены слишком много слов, то

важные термины будут забиты «шумом» случайных слов.

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


Стоп-слова

Для того, чтобы безошибочно сузить диапазон значимых слов, создается словарь

«бесполезных» слов или «стоп-слов».


Словарь этих слов («стоп-лист») содержит, например, артикли и предлоги, частицы

и личные местоимения (а, без, более, бы, был, была, были, было, быть, в, вам,

вас, весь, во, вот, все, всего, всех, вы, где, да, даже, для, до, его, ее, если, есть, ещё,

же, за, здесь, и, из, из-за, или, им, их, к, как, как-то, ко, когда, кто, ли, либо, мне,

может, мы, на, надо, наш, не, него, неё, нет, ни, них, но, ну, о, об, однако, он, она,

они, оно, от, очень, по, под, при, с, со, так, также, такой, там, те, тем, то, того, тоже,

той, только, том, ты, у, уже, хотя, чего, чей, чем, что, чтобы, чьё, чья, эта, эти, это,

я), а также целый ряд других слов. Их конкретный перечень может состоять от

нескольких сот до нескольких тысяч слов и различен для разных поисковых

машин..

Для уменьшения размера индекса поисковой системы стоп-слова не

включаются в индекс и не учитываются при поиске.
Весовой коэффициент

При определении значимых слов применяется и т.н. «весовой коэффициент».
· Часто встречаемое на всех сайтах слово - имеет весовой коэффициент,

близкий к нулю.
· Слово встречаемое редко на всех сайтах- может иметь весьма высокий

коэффициент.

Параметр, определяющий «весовой коэффициент», называется инверсная

частота термина.

ПС может вычислять «весовой коэффициент» с учетом местоположения слова

внутри документа, взаимного расположения разных слов, морфологических

особенностей и т.п.
Необходимо например для того, чтобы ПС могла игнорировать некоторые

часто встречающиеся слова - прайс, сайт, Интернет, и т.д


Закономерность Брэдфорда
Основной смысл закономерности С. Брэдфорда заключается в следующем:

если научные журналы расположить в порядке убывания числа помещенных

в них статей по конкретному предмету, то полученный список можно разбить

на три зоны таким образом, чтобы количество статей в каждой зоне по

заданному предмету было одинаковым.


Эти


три


зоны


составляли:


профильные


журналы,


посвященные

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

области, и журналы, тематика которых весьма далека от рассматриваемого

предмета.


С. Брэдфорд установил, что количество журналов в третьей зоне будет

примерно во столько раз больше, чем во второй зоне, во сколько раз число

наименований во второй зоне больше, чем в первой


P3 : P2 = P2 : P1 = N,


где P1 - число журналов в 1-й зоне, P2 - во 2-й, P3 - число журналов в 3-й

зоне.

Исходя из реалий развития сети Интернет, ее можно рассматривать как

закономерность, относящуюся к ранговому распределению Web-сайтов,

относительно вхождения в них Web-страниц, релевантных некоторой

области знаний.

Закон Хипса
В компьютерной лингвистике эмпирический закон Хипса связывает объем

документа с объемом словаря уникальных слов, которые входят в этот

документ.

v(n) = Kn?,

где v – это объем словаря уникальных слов, составленный из текста, который

состоит из n уникальных слов. K и ? – обусловленные эмпирически параметры.

Для европейских языков K принимает значение от 10 до100, а ? - от 0.4 до 0.6.

Закон Хипса справедлив не только для уникальных слов, но и для многих

других информационных объектов, описываемых не экспоненциальной, а

степенной зависимостью.



Модели информационного

поиска

Все многообразие моделей традиционного информационного поиска (IR)

принято делить на три вида:


· теоретико-множественные (булевская, нечётких множеств,

расширенная булевская),

· алгебраические (векторная, обобщённая векторная, латентно-

семантическая, нейросетевая)

· вероятностные.


Большинство поисковых систем функционируют безо всяких математических

моделей, так как

их разработчики не ставят перед собой задачу

реализовывать абстрактную модель.


Как только речь заходит о повышении качества поиска, о большом объёме

информации, о потоке пользовательских запросов, кроме эмпирически

проставленных коэффициентов полезным оказывается оперировать каким-

нибудь пусть и несложным теоретическим аппаратом.


Модель поиска – это некоторое упрощение реальности, на основании

которого получается формула (сама по себе никому не нужная), позволяющая

программе принять решение: какой документ считать найденным и как его

ранжировать.


После принятия модели входящие в эмпирические формулы коэффициенты

приобретают физический смысл и становятся понятней.



Булевская модель
Это самая простая модель, основанная на теории множеств где запросы

представляются в виде булевских выражений из слов и логических операторов

И, ИЛИ, НЕ. Релевантными считаются документы, которые удовлетворяют

булевскому выражению в запросе.


Недостатки

1.

2.

3.

недостаточно возможностей для описания сложных запросов

результатов запроса либо слишком много либо слишком мало

проблематичность при ранжирования результатов





Булевская модель

Матрица документ-термин C(d,t) показывает какие встречаются слова t и в

каких документах d


Запрос:
q = a И ( b ИЛИ (НЕ c) )
53
C(d,t)

t1 a

t 2 b

t 3 cd 1100d 2110d 3101d 4010d 5111




Документы и запросы

представляются в виде векторов в

N-мерном евклидовом

пространстве.

Компоненты вектора

соответствуют N терминам,

образующим пространство.

Чем больше используется

терминов, тем сложнее понять

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

являются общими для подобных

документов.

Как выбирать размерность

пространства терминов N ?

Как вычислять весовые

коэффициенты wt?


Векторная модель





Векторная модель



Релевантность в векторной модели







Достоинства:

1.

2.

3.

Учет весов повышает эффективность поиска

Позволяет оценить степень соответствия документа запросу

Косинусная метрика удобна при ранжировании



Недостатки

1. Нет достаточного теоретического обоснования для построения

пространства терминов

2.

Поскольку термины не являются независимыми друг от друга, то они не

могут быть полностью ортогональными

Пример

·
В каких из русских сказок есть слово волк, но нет упоминания медведя и

поросенка?


Вектор слово-документной встречаемости
0, если слова нет

в документе, 1 если есть



Три поро-

сенкаКрасная

ШапочкаКолобокТеремокмедведь0011волк1111поросенок1000мышь0001бабушка0110


Итак мы имеем вектора из 0/1 для каждого слова размерности равной

количеству документов.


Запрос:


В каких из русских сказок есть слово волк, но нет упоминания медведя и

поросенка?


Ответ:


возьмем вектора для медведя (дополнение), волка и поросенка(дополнение)


и выполним между ними побитное умножение


1100&1111&0111 = 0100второй документ!





Вероятностные модели

Заключаются в оценке вероятности того, что документ d является

релевантным по отношению к запросу q

Вероятность вычисляется на основе теоремы Байеса:

P(R) – вероятность того, что случайно выбранный из коллекции

документ D является релевантным


P(d|R) – вероятность случайного выбора документа d из множества

релевантных документов


P(d) – вероятность случайного выбора документа d из коллекции D
61




Google Page Rank

Все его используют, но мало кто знает, как он работает и как его вычисляют.


Поиск среди миллиардов существующих и миллионов создаваемых каждый

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

PageRank, только один из сотен факторов, используемых Google для

улучшения качества поиска.


Но как он работает, и какие факторы на него влияют, а какие нет, и, что

мы знаем о PageRank?








Алгебраическое определение

Рассмотрим восемь web-страниц связанных соответствующими

гиперссылками и найдем PageRank этих страниц



Начнем с построения матрицы гиперссылок H

элемент которой в ith строке и jth столбце определяется по правилу


������ =

��

����


если ���� ? ����

�� в противном случае



Здесь
���� - страничка с номером j , которая имеет

���� гиперссылок на другие страницы,



����

множество страниц на которые ведут

гиперссылки с i - той страницы














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





Теперь найдем стационарный вектор матрицы гиперссылок (т.е. вектор
отвечающий единичному собственному значению)

HI=I


Элементы этого вектора и есть значения PageRank соответствующей
страницы.

Чем больше эти значениетем вышекачестводанной страницы.












Метод простых итераций:


I 0
I 1
I 2
I 3
I 4
...
I 60
I 61


1
0
0
0
0.0278 ...
0.06
0.06



0

0.5

0.25

0.1667 0.0833 ...

0.0675 0.0675


0
0.5
0
0
0
...
0.03
0.03


0
0
0.5
0.25
0.1667 ...
0.0675 0.0675



0

0

0.25

0.1667 0.1111 ...

0.0975 0.0975



0

0

0

0.25

0.1806 ...

0.2025 0.2025



0

0

0

0

0

0

0.0833 0.0972 ...

0.0833 0.3333 ...

0.18

0.295

0.18

0.295











Теоретическое решение n??


















Будущие поисковые машины

· Каталоги сайтов: регистрация сайтов сообществами

· Каталоги запросов: регистрация и разметка запросов

вебмастерами

· Структурированная выдача: по теме и типам

документов.

· Читаемость выдачи: названия, аннотации, тэги от

сообществ

· Понимание запроса: запросы на ЕЯ, распознавание

темы, уточнение запроса

· Новые виды заработка на поиске: регистрация

запросов, сайтов, ранжирование, хостинг поиска


Отдельный разговор:


·

·

·

·

·

·
Мобильный поиск (борьба за смартфон)

Локальный поиск и геотаргетинг (борьба за кофе - Nokia)

Блогопоиск и новостные поисковики (борьба за аффтара)

Многоязыковый поиск и перевод (борьба с языковым барьером)

Национальные проекты (борьба против Гугла)

Ну и так далее .................


Источники:
1. Юрий Лифшиц - курс "Алгоритмы для Интернета"

2. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. - СПб.: Питер, 2000.

3. Добрынин В. Теория информационно-логических систем. Информационный поиск. - СПб.,

2002.

4. Леонтьева Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы. - М.:

Издательский центр "Академия", 2006.

5. Пенроуз Р. Новый ум короля: О компьютерах, мышлении и законах физики. – М.: УРСС, 2003.

6. Библиотека на www.nigma.ru

7. Страница Леонида Бойцова

8. Русский национальный корпус, http://www.ruscorpora.ru

9. Частотный словарь Сергея Шарова, http://www.artint.ru/projects/frqlist.asp

10. Поисковые машины и поисковая оптимизация, http://searchengines.ru РОМИП,

http://romip.narod.ru

11. Список стоп-слов, http://forum.searchengines.ru/showthread.php?postid=7670

12. Страница Андрея Коваленко, http://linguist.nm.ru

13. Cайт "Автоматическая Обработка Текста", http://www.aot.ru

14. Гусев В.С. Google: эффективный поиск. Краткое руководство. – М.: «Вильямс», 2006.

15. Ландэ Д.В. Поиск знаний в INTERNET. Профессиональная работа.: Пер. с англ. – М.:

«Вильямс», 2005.

Internet алгоритмы I
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации