LAB1 Мясникова О.А (Лабораторная работа 1)

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСИЙ ИНСТИТУТ(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Лабораторная работа №1 по дисциплине ВМСС

Поиск информации в INTERNET

Выполнила

студентка группы

А-13-08

Мясникова Ольга

Преподаватель:

Куриленко И.Е.

Москва, 2012

Цель работы.

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

Теоретическая информация.

Релева́нтность (лат. relevo — поднимать, облегчать) в информационном поиске — семантическое соответствие поискового запроса и поискового образа документа.

Адресация в сети Интернет

Основным протоколом сети Интернет является сетевой протокол TCP/IP. Каждый компьютер, в сети TCP/IP (подключенный к сети Интернет), имеет свой уникальный IP-адрес или IP – номер.

IP(Internet Protocol) - межсетевой протокол, который обеспечивает

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

другую;

UDP(User Datagram Protocol) - протокол пользовательских датаграмм,

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

проверки ошибок;

TCP(Transmissin Control Protocol) - протокол управления передачей,

обеспечивающий транспортировку с помощью IP с проверкой установления

соединения;

Адреса в Интернете могут быть представлены как последовательностью цифр, так и именем, построенным по определенным правилам. Компьютеры при пересылке информации используют цифровые адреса, а пользователи в работе с Интернетом используют в основном имена.

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

При записи числа отделяются точками, например: 195.63.77.21. Такой способ нумерации позволяет иметь в сети более четырех миллиардов компьютеров. 

Каждый пакет, проходящий по сети содержит адрес получателя, и идет

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

процесс направления пакета по лабиринту сетей, находящихся между

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

Для отдельного компьютера или локальной сети, которые впервые подключаются к сети Интернет, специальная организация, занимающейся администрированием доменных имен, присваивает IP – номера.

Первоначально в сети Internet применялись IP – номера, но когда количество компьютеров в сети стало больше чем 1000, то был принят метод связи имен и IP – номеров, который называется сервер имени домена (Domain Name Server, DNS). Сервер DNS поддерживает список имен локальных сетей и компьютеров и соответствующих им IP – номеров.

В Интернете применяется так называемая доменная система имен. Каждый уровень в такой системе называется доменом. Пространство имен DNS (иерархия доменов) имеет вид дерева доменов, с полномочиями, возрастающими по мере приближения к корню дерева. 
Первый домен в иерархии доменов - корневой домен, не имеющий имени. [Корень дерева имеет имя "."] 
Под ним находятся домены верхнего уровня (корневые домены): .com, .net, .org, .edu, .gov, .mil, .int и двухбуквенные национальные домены (.ru, .uk, .us, .fr, .jp и т.д.). 

Кстати, совсем скоро к доменам верхнего уровня будут добавлены следующие домены: .biz, .info, .name, .pro, .museum, .aero, .coop. 

По историческим причинам существует два вида доменов верхнего уровня. 
В США домены верхнего уровня отражают организационную структуру, и как правило имеют трехбуквенные имена: 

.gov - государственные учреждения 
.mil - военные учреждения 
.com - коммерческие организации 
.net - поставщики сетевых услуг 
.org - бесприбыльные организации 
.edu - учебные заведения 
.int - ... 

Для доменов вне США, в соответствии с территориальным расположением используются двухбуквенные коды стран (национальные домены). 
Например: 

www.ciberpolice.ru - в России 
www.berlin.de - а Германии 
www.hotex.nl - в Нидерландах 
и т.д.

Далее идут домены второго уровня (petrov.ru).
Доменами в зоне .ru ведает Российский НИИ Развития Общественных сетей (РосНИИРОС).

Среди доменов второго уровня есть домены общего пользования (generic) и домены открытого пользования (public).
Домен общего пользования зарегистрировать не дадут.

При работе в Internet используются не доменные имена, а универсальные указатели ресурсов, называемые URL (Universal Resource Locator). URL - это адрес любого ресурса (документа, файла) в Internet, он указывает, с помощью какого протокола следует к нему обращаться, какую программу следует запустить на сервере и к какому конкретному файлу следует обратиться на сервере. Общий вид URL: протокол://хост-компьютер/имя файла.

Домен второго уровня регистрируется у регистратора – организации занимающейся администрированием доменных имен, например http://www.imhoster.net/domain.htm. Домен третьего уровня приобретается, как правило, вместе с хостингом у хостинговой компании. Имя сайта выбирают исходя из вида деятельности, названия компании или фамилии владельца сайта. 

Три поколения поиска

Поиск 1.0

Первое поколение поисковых систем оценивало содержание страниц и ранжировало результаты поиска в основном исходя из частоты встречаемости ключевых слов. Такой способ давал определенные результаты, но очень быстро в определенных категориях ключевых слов образовалась путаница – по запросу «Бритни Спирс» вы получаете миллионы страниц, часть из которых не имеет никакого отношения к певице.

Поиск 2.0

С запуском Google, поиск стал больше опираться на данные сети – анализировалась не только одна страница, но и ссылки, ведущие на нее. Таким образом устанавливалась система авторитетности страниц, подобная системе оценки цитируемости работ, принятой в научном мире. Ссылки становились как бы «голосами» в пользу какой-либо страницы.

Поиск 3.0

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

Принципы построения и модели работы поисковых систем.

Модель поиска - это сочетание следующих составляющих:

1. способ представления документов

2. способ представления поисковых запросов

3. вид критерия релевантности

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

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

1. на основе его содержания

2. на основе его названия

Эти два процесса называются соответственно индексированием по содержанию и индексированием по заголовкам документов. В некоторых дескрипторных системах индексирование документов осуществляется вручную экспертами в предметной области системы, в других она выполняется автоматически. Представление документа в дескрипторных системах называется поисковым образом документа. Дескрипторные системы можно отнести к классу систем, ориентированных на библиографический поиск или «поиск по каталогу».

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

1. Простой вариант – запросом является идентификатор какого-либо класса из заданного классификатора. Критерий релевантности документа запросу – класс документа совпадает с классом в представлении запроса или является его подклассом.

2. Сложный вариант - в запросе можно указать несколько классов классификатора. Критерий релевантности документа запросу – класс документа совпадает с каким-либо из указанных в запросе классов или является его подклассом.

Модели, основанные на классификаторах, близки к булевским моделям.

В булевских моделях поиска пользователь может формулировать запрос в виде булевского выражения, используя для этого операторы И, ИЛИ, НЕТ. Термы запроса зависят от конкретного варианта модели поиска. В булевской модели, ориентированной на поиск «по тексту», термам будут слова, соответственно, критерием релевантности будет условие вхождения некоторого слова или словосочетания в тексте документа. В булевской модели, ориентированной на поиск по классификаторам, термами выражения будут идентификаторы классов классификатора. В модели с использованием Дублинского ядра термом будет значения элементов метаданных. Документ, имеющий совпадающие значения элементов метаданных со значениями, заданными в запросе, считается релевантным. В общем случае критерием релевантности документа запросу является истинность булевского выражения, заданного в запросе. Одним из достоинств является простота реализации данной модели. Главными недостатками считаются:

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

2. сложность использования – далеко не каждый пользователь может свободно оперировать булевскими операторами при формулировке своих запросов.

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

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

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

Функции оценки релевантности.

TF-IDF

 Его смысл сводится к тому, что чем больше локальная частота термина (запроса) в документе (TF) и больше «редкость» (то есть чем реже он встречается в других документах) термина в коллекции (IDF), тем выше вес данного документа по отношению к термину — то есть документ будет выдаваться раньше в результатах поиска по данному термину.

TF (term frequency — частота слова) — отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность слова ti в пределах отдельного документа.

 ,

где ni есть число вхождений слова в документ, а в знаменателе — общее число слов в данном документе.

IDF (inverse document frequency — обратная частота документа) — инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов.

 ,

где

|D| — количество документов в корпусе;

 — количество документов, в которых встречается ti (когда  ).

Таким образом, мера TF-IDF является произведением двух сомножителей: TF и IDF.

Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.

Достоинством данного метода является то, что он учитывает не конкретный документ, а все документы коллекции. Недостатком — существенное занижение веса документов включающих схожие определения и синонимы, документов большой длины, которые по определению будет проигрывать по TF коэффициенту, и завышение веса «коротких» документов, по этой же причине. Также многократное повторение в бесполезном тексте ключевого слова приводит к неверной высокой оценке.

PageRank

PageRank (пэйдж-ранк) — один из алгоритмов ссылочного ранжирования. 

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

PageRank — это числовая величина, характеризующая «важность» веб-страницы. Чем больше ссылок на страницу, тем она становится «важнее». Кроме того, «вес» страницы А определяется весом ссылки, передаваемой страницей B. Таким образом, PageRank — это метод вычисления веса страницы путём подсчёта важности ссылок на неё.

Надстройка для браузера Google Toolbar показывает для каждой веб-страницы целое число от 0 до 10, которое она называет PageRank, или важностью этой страницы с точки зрения Google. Однако механизм его расчета и что в точности обозначает это значение не раскрывается. По некоторым данным, эти значения обновляются лишь несколько раз в год (в то время, как внутренние значения PageRank пересчитываются непрерывно) и показывают значения PageRank страниц на логарифмической шкале.

Достоинство состоит в том, что учитывается не только содержание конкретной страницы, но и «мнение» и «популярность» среди других страниц. Недостатком является возможность искусственного увеличения PageRank путем создания пустых сайтов с множеством ссылок.