… 1 …. Название Определение географического местоположения интернет ресурсов Дмитрий Соловьев, Андрей Калинин Поиск@Mail.Ru d.soloviev@corp.mail.ru, kalinin@corp.mail.ru. - презентация

1 … 1 …. Название Определение географического местоположения интернет ресурсов Дмитрий Соловьев, Андрей Калинин

2 … 2 …. Введение География для поиска информации Предпосылки Значительный рост региональной аудитории. 1 Суммарный рост В регионах

3 … 3 …. Введение География для поиска информации Предпосылки Рост количества региональных сайтов. 2 География распределение сайтов Рост количества региональных сайтов с по

4 … 4 …. Введение География для поиска информации Резюме 1. Региональные пользователи формируют пул региональных запросов. 2. Для региональных запросов наиболее релевантными будут региональные сайты.

5 … 5 …. Введение География для поиска информации Резюме Используя одни и те же слова, разные люди, хотят получить различные результаты. Для повышения качества ответа поисковой машины нужно учитывать взаимное расположение пользователя и сайта Задача не очень хорошо решается при помощи использования поиска по ключевым словам. Нужны дополнительные метаданные для формирования высокоуровневых семантических запросов

6 … 6 …. Введение Источники данных КаталогиКаталоги WHOIS Контент страниц Статистика посещений

7 … 7 …. Введение Цель Разработка и исследование методов привязки ресурса к географии. На основе анализа посещаемости ресурса пользователями На основе анализа контента страниц ресурса

8 … 8 …. Геопривязка ресурса на основе анализа посещаемости пользователей

9 … 9 …. Анализ посещаемости ресурса Предположение: Если сайт посещаем пользователями одного региона, то он имеет тематическую привязку, направленную на данный регион Предположение: Если сайт посещаем пользователями одного региона, то он имеет тематическую привязку, направленную на данный регион Можно осуществить локализацию данного ресурса

10 … 10 …. Анализ посещаемости ресурса Пример samara.irr.ru (Самара) samara.irr.ru (Самара) IRR.RU ekaterinburg.irr.ru (Екатеринбург) ekaterinburg.irr.ru (Екатеринбург) kazan.irr.ru (Казань) kazan.irr.ru (Казань) nizhniynovgorod.irr.ru (Нижний Новгород) nizhniynovgorod.irr.ru (Нижний Новгород) saint-petersburg.irr.ru (Санкт-Петербург) saint-petersburg.irr.ru (Санкт-Петербург)

11 … 11 …. Анализ посещаемости ресурса Описание метода - частота посещений ресурса для выбранного региона. - коэффициент неравномерности распределения пользователей в регионах. - нормализованная частота посещений в регионе Построим гистограмму распределения количества пользователей посетивших ресурс по регионам и введем обозначения: 1

12 … 12 …. Анализ посещаемости ресурса Описание метода 2 Выберем расчетный период. Путем проведения ряда экспериментов был определен оптимальный период: 1 месяц Путем проведения ряда экспериментов был определен оптимальный период: 1 месяц

13 … 13 …. Анализ посещаемости ресурса Описание метода 3 Как показали эксперименты, усреднение гистограммы за полный период может быть не корректно из-за возможных всплесков. Решение: Разделить весь диапазон на сегменты тогда

14 … 14 …. Анализ посещаемости ресурса Описание метода 4 Для каждого сегмента рассчитаем нормализованную частоту: частота посещений для региона, рассчитанная в рамках одного сегмента.

15 … 15 …. Анализ посещаемости ресурса Описание метода 5 Для каждого сегмента определяется регион с максимальной нормализованной частотой: - множество значений частот для данного сегмента.

16 … 16 …. Анализ посещаемости ресурса Описание метода 6 Для каждого региона в рамках одного сегмента вычислим пороговую величину: По всем сегментам региона рассчитывается агрегированная величина: - общее количество сегментов данных.

17 … 17 …. Анализ посещаемости ресурса 7 По результатам определяется принадлежность ресурса региону R на множестве Описание метода пороговый коэффициент исключает попадание ресурса в регион с низким рейтингом.

18 … 18 …. Геопривязка ресурса на основе анализа контента страниц

19 … 19 …. Анализа контента страниц 1 Решение задачи извлечения информации разобьем на части: Описание метода определение типовых шаблонов сайтов, на которых может размещаться информация о месте расположения организации; извлечение кандидатов для последующей привязки сайта к географической информации; фильтрация кандидатов. определение типовых шаблонов сайтов, на которых может размещаться информация о месте расположения организации; извлечение кандидатов для последующей привязки сайта к географической информации; фильтрация кандидатов.

20 … 20 …. Анализа контента страниц 2 Определение типовых шаблонов. Описание метода проанализирована структура сайтов организаций отобраны наиболее часто встречающиеся типовые шаблоны сайтов; по результатам анализа можно выделить следующие три этапа; проанализирована структура сайтов организаций отобраны наиболее часто встречающиеся типовые шаблоны сайтов; по результатам анализа можно выделить следующие три этапа;

21 … 21 …. Анализа контента страниц 3 Определение типовых шаблонов. Описание метода Поиск адресов на странице «Контакты» Поиск адресов на корневой странице сайта. Поиск ссылок на страницу «Контакты».

22 … 22 …. Анализа контента страниц 4 Одним из наиболее часто встречающихся мест расположения контактной информации является корневая страница Определение типовых шаблонов Возможные ссылки на контакты Возможный адрес

23 … 23 …. Анализа контента страниц 5 Часто встречающимся местом расположения контактной информации является страница «Контакты» Определение типовых шаблонов Возможный адрес

24 … 24 …. Анализа контента страниц 6 На корневой странице сайта или странице «Контакты» при помощи словаря городов ищем возможное вхождение адреса. Извлечение кандидатов Описание метода

25 … 25 …. Анализа контента страниц 7 Используя скрытую Марковскую модель оцениваем последовательность слов окружающих город. Вычисляем вероятность появления последовательности адреса в окрестности города Левый и правый контент оценивается отдельно Используем алгоритм «forward-backward» Извлечение кандидатов Описание метода

26 … 26 …. Анализа контента страниц 8 Извлечение кандидатов Описание метода Рассматриваем элементы почтового адреса как состояния модели. Уменьшаем количество состояний модели, переводя типовые части адреса в одно состояние. улица шоссе переулок транслируем множество известных географических названий в одно состояние последовательности

27 … 27 …. Анализа контента страниц 8 Извлечение кандидатов Описание метода Описывает город, найденный в словаре Примеры состояний скрытой Марковской модели Описывает страну, найденную в словаре Описывает один из известных модификаторов улицы (ул,...)

28 … 28 …. Анализа контента страниц 9 Извлечение кандидатов Описание метода Сформированное таким образом множество состояний модели:

29 … 29 …. Анализа контента страниц 9 Извлечение кандидатов Описание метода Уменьшение количеств состояний модели приводит к: необходимости вводить матрицы проекций элемента адреса на состояние. уменьшению размера обучающего множества

30 … 30 …. Анализа контента страниц 10 Извлечение кандидатов Описание метода Строим матрицу вероятностей переходов между состояниями модели: предшествующее состояние системы ; текущее состояние системы; рассматриваемый элемент последовательности, принадлежащий множеству

31 … 31 …. Анализ посещаемости ресурса 11 Извлечение кандидатов Описание метода Введем обозначения: t наблюдаемую величину в момент t t состояние, которое принимает система во время t

32 … 32 …. Анализ посещаемости ресурса 12 Извлечение кандидатов Описание метода Введем обозначения: i j элементы матрицы вероятностей перехода из состояния i в состояние j j вероятность получить данные в состоянии j

33 … 33 …. Анализ посещаемости ресурса 13 Извлечение кандидатов Описание метода Введем обозначения: dV Данные. Последовательность наблюдаемых d принимает значения из V Начальное распределение.

34 … 34 …. Анализ посещаемости ресурса 14 Извлечение кандидатов Описание метода По полученной модели: Последовательности: Найдем:

35 … 35 …. Анализа контента страниц 15 Извлечение кандидатов Описание метода Используя построенную модель и зная возможную точку расположения адреса на странице, найденную при помощи словаря городов, производим оценку контекста, в котором находится найденный город, используя процедуру «forward-backward»

36 … 36 …. Анализа контента страниц 16 Пример Описание метода Состояния модели С страна S улица D район города H номер дома F квартира T город O разделители... Вероятность вхождения слова с большой буквы в состояния модели: C 1, S 0.54, D 0,45 Вероятность вхождения цифр в состояния модели: H 0.85, F … Элемент матрицы вероятностей перехода: T O (0.33) S (0.33) T (0.33)...

37 … 37 …. Фильтрация кандидатов Извлеченные адреса проходят фильтрацию Из страницы извлекается дополнительная информация, как например, телефон, который ставится в соответствие одному или нескольким адресам. Например, проверяем код региона, указанного в номере телефона на соответствие городу, указанному в адресе

38 … 38 …. Эксперименты

39 … 39 …. Эксперименты Для экспериментов была взята база страниц скачанных из интернета, содержащая порядка 20 миллионов сайтов и 3,9 миллиарда страниц На этих данных на основе метода анализа контента страниц проводилась географическая привязка сайта. 1

40 … 40 …. Эксперименты Был взята база статистики посещаемости из - 1 миллион сайтов. Был взята база статистики посещаемости из - 1 миллион сайтов. На этих данных на основе метода анализа статистики посещаемости проводилась географическая привязка сайта. 2

41 … 41 …. Эксперименты Для оценки точности мы отобрали случайным образом порядка 100 сайтов и проверили точность попадания географической привязки, проставленной суммарно по двум методам, и по каждому методу отдельно, сопоставив ее с реальной информацией доступной на сайте. 3

42 … 42 …. Эксперименты 4 Анализ контента страниц Количество сайтов взятых для анализа 20 миллионов Сайтов получивших географическую привязку Точность геопривязки веб ресурса97% Полнота охвата исходных данных1,6%

43 … 43 …. Эксперименты 5 Анализ статистики посещаемости Количество сайтов взятых для анализа 1 миллион Сайтов получивших географическую привязку Точность геопривязки веб ресурса76% Полнота охвата исходных данных12%

44 … 44 …. Эксперименты 6 Суммарно по сайтам Количество сайтов взятых для анализа 20 миллионов Сайтов получивших географическую привязку Точность геопривязки веб ресурса80% Полнота охвата исходных данных2,2%

45 … 45 …. Эксперименты 7 Пример сайтов, приписанных региону по сумме двух методов Санкт-Петербург spbgu.ru, flot.com, 5-tv.ru, saint-petersburg.ru, newspb.ru Екатеринбург oblgazeta.ru, doskaurala.ru, medgorodok.ru, urbc.ru, uralweb.ru Киев ati.com.ua, pregnancy.org.ua, football.ua, realt.ua, ukranews.com Были взяты два самых крупных региональных города России и один в Украине, для них случайным образом отобрали пять сайтов, получившие в качестве географического признака идентификатор этого города

46 … 46 …. Эксперименты 8 Распределение сайтов по регионам

47 … 47 …. Выводы

48 … 48 …. Выводы 1 Наиболее точным методом является метод, построенный на основе анализа контента. В его случае точность достигает 97%. Это обусловливается использованием предопределенных шаблонов, словарей, формальных правил для записи адреса.

49 … 49 …. Выводы 2 Использованием предопределенных шаблонов, словарей, формальных правил для записи адреса... приводят к снижению полноты

50 … 50 …. Выводы 3 Метод, реализованный на основе анализа статистики посещаемости, обладает большей полнотой относительно анализируемого множества сайтов - 12%.

51 … 51 …. Выводы 4 Недостатки Ограничивается только данными, доступными из статистики посещаемости, - 5% от общего множества сайтов Много статистически не значимых сайтов, порядка 87%, Возможно неверное сопоставления IP адреса пользователя его реальному местоположению.

52 … 52 …. Выводы 5 Привязку к географии получили: 2,2 % сайтов. 33% от всех страниц Привязку к географии получили: 2,2 % сайтов. 33% от всех страниц По двум методам суммарно

53 … 53 …. Выводы 6 Оценка проводилась независимо для трех различных регионов. В результате этого эксперимента, мы получили удовлетворительное качество ответов поисковой машины, по всем трем регионам. Оценка качества фильтрации региональных сайтов по географическим запросам