=Paper=
{{Paper
|id=None
|storemode=property
|title=Определение географического местоположения интернет-ресурсов
(Determining the Geographic Location of Internet Resources)
|pdfUrl=https://ceur-ws.org/Vol-803/paper6.pdf
|volume=Vol-803
|dblpUrl=https://dblp.org/rec/conf/rcdl/SolovievK11
}}
==Определение географического местоположения интернет-ресурсов
(Determining the Geographic Location of Internet Resources)
==
https://ceur-ws.org/Vol-803/paper6.pdf
Определение географического местоположения
интернет ресурсов
©Дмитрий Соловьев, Андрей Калинин
Поиск@Mail.Ru
d.soloviev@corp.mail.ru, kalinin@corp.mail.ru
Аннотация Поиск информации, основанный на
географических критериях достаточно общая задача.
В статье рассматривается решение задачи Примеры могут включать: путешественников,
определения географического которые хотят получить информацию о цели
местоположения веб-ресурса. Документ путешествия; аналитиков, подготавливающих отчет
включает описание двух методов привязки о данной местности, планирование расширения
сайта к географии: анализ статистики бизнеса в других регионах. За более подробным
посещаемости и анализ контента страниц объяснением областей, в которых используется
ресурса, основанного на скрытой поиск информации с учетом географических
Марковской модели. критериев можно обратиться к [4]. В любом случае
эту задачу можно разбить на две составляющие:
1. Введение определение географического положения ресурса и
поиск информации с учетом геоданных. Нужно
С первых дней становления интернета много отметить, что понятие географического положения
усилий было потрачено на совершенствование
ресурса не обязательно подразумевает его
организации, навигации и поиска документов. физическое нахождение в конкретной местности, а
Возможно, что поиск по инвертированному индексу больше связанно с отображением его в реальные
ключевых слов является, сегодня, одной из наиболее
объекты, например: компании, региональные СМИ,
полезных техник, позволяющей пользователям или объединение пользователей по региональным
находить информацию по заданной теме. В тоже тематикам, например, региональный сайт
время, глобальное расширение интернета приводит
бесплатных объявлений. Для решения первой части
к тому, что количество найденной информации, поставленной задачи нужно определиться с
получаемой пользователем при поиске с источниками и методиками экстракции информации.
использованием только ключевых слов, слишком К таким техникам можно отнести: извлечение
велико. Используя одни и те же слова, разные люди, информации из каталогов или анализ базы WHOIS.
в зависимости от условий, хотят получить
За подробным описанием таких методик экстракции
различные результаты. Например, задавая запрос геоинформации можно обратиться к [5]
[установка окон ПВХ], человек, проживающий в Интересным источником географической
Хабаровске ожидает увидеть в результатах те
информации может являться непосредственно сам
страницы, которые относятся к локальным контент. Например, веб-страницы сайта компании
компаниям, занимающихся установкой окон, а не могут содержать адреса и телефоны, как головного
получать страницы компаний расположенных в
офиса, так и региональных ее представительств.
Екатеринбурге. Такая задача не очень хорошо Страницы, сообщающие о новых событиях, также
решается при помощи использования поиска по могут содержать информацию о месте, где данное
ключевым словам. В то же время он может стать
событие проводится.
отправной точкой формирования высокоуровневых Многие веб-ресурсы рассчитаны на посещение
семантических запросов, которые могут пользователями из определенного региона,
использоваться для нахождения такой информации.
например, к таким ресурсам можно отнести
Таким образом, можно сформировать городские порталы, местные издания газет. Кроме
дополнительные метаданные страницы, используя того, такие ресурсы могут не содержать прямых
которые, можно повысить качество ответа
указаний на свое географическое
поисковой машины. Метаданными, описывающими месторасположение непосредственно в контексте
локализацию страниц в поиске, является страниц. Поэтому, в этом случае можно
информация о географическом положении ресурса. использовать информацию, получаемую от
пользователей посещающих данный ресурс. В
Труды 13й Всероссийской научной конференции
«Электронные библиотеки: перспективные методы и данном случае можно оперировать статистикой
технологии, электронные коллекции» - RCDL’2011, посещений пользователей с учетом их региональной
Воронеж, Россия, 2011. привязки.
38
Нужно отметить, что уровень детализации Поддомен Регион
геопривязки ресурса в зависимости от условий
может меняться. В некоторых случаях однозначно http://saint-petersburg.irr.ru Санкт-Петербург
определить геопринадлежность веб-ресурса нельзя http://nizhniynovgorod.irr.ru Нижний Новгород
из-за его нахождения в различных географических
контекстах. Одни веб-ресурсы могут получать http://samara.irr.ru Самара
жесткую привязку к местности, вплоть до номера … ...
дома; другие могут содержать только укрупненную
информацию: город, район или область. Таблица 1. Региональные поддомены сайта
Целью публикации является разработка и http://irr.ru
исследование методов привязки ресурса к географии
для получения качественных данных, которые могут
быть впоследствии использованы для поиска
информации с учетом географических критериев. В 14000
статье предлагаются к рассмотрению две методики,
позволяющие решить задачу определения 12000
географической дислокации ресурса, а так же 10000
приводятся оценки точности и полноты этих
методов. Дополнительно рассматривается 8000
возможные направления использования полученных
6000
данных. Для решения поставленной задачи мы
использовали непосредственно контент веб-сайтов, а 4000
также анализ посещаемости ресурсов
пользователями. 2000
0
2. Геопривязка ресурса на основе Самара Москва Тольятти Саратов
анализа посещаемости пользователей
Одним из источников информации о Гистограмма 1: Распределение посещаемости
географическом местоположении ресурса могут сайта samara.irr.ru за сутки
служить данные о пользователях и распределение их Самаре. Это обстоятельство нужно учитывать при
посещаемости по регионам. Можно предположить, построении гистограммы, и с этой целью были
что если сайт интересен и посещаем пользователями введены нормирующие коэффициенты, отражающие
одного региона, то он имеет тематическую привязку, распределение пользователей Интернета по
направленную на данный регион, и как следствие регионам. Таким образом, частотная характеристика
можно осуществить локализацию данного ресурса. региона в гистограмме учитывает еще и
В качестве наиболее характерного примера можно
взять электронное издание «Из рук в руки» (irr.ru). коэффициент неравномерности распределения k .
Ресурс имеет деление на поддомены третьего Тогда нормализованная частота посещений в
уровня, каждый из которых принадлежит регионе Fr будет равна:
определенному городу или региону. В таблице 1
приведены примеры поддоменов третьего уровня,
используемых в качестве региональных. Можно Fr = k ∗ f k
предположить, что, например, поддомен samara.irr.ru
будет более интересен пользователям, Следующим шагом определения
проживающим в Самаре, чем пользователям, принадлежности ресурса региону является выбор
проживающим в Нижнем Новгороде. Таким периода, за который будет рассчитана гистограмма
образом, если построить гистограмму распределения. Путем проведения ряда
распределения количества пользователей экспериментов был определен оптимальный период
посетивших ресурс по регионам, то у равный одному месяцу. Как показали эксперименты,
рассматриваемого ресурса будет наблюдаться усреднение гистограммы за полный период может
максимум посещений в регионе Самара. На быть не корректно, поскольку в некоторых случаях
гистограмме 1 приведен пример распределения дает ошибочный результат. Например, при сильных
посещаемости для сайта samara.irr.ru за сутки. всплесках посещаемости ресурса пользователями
Можно аннотировать частоту посещений ресурса других регионов, в коротком промежутке времени.
для заданного региона как f r . Такое поведение характерно для региональных
издательств, когда на ресурсе размещаются
Для корректного решения поставленной задачи
публикации описывающие положение дел в других
так же необходимо принять во внимание тот факт,
географических регионах. Чтобы исключить
что распределение количества пользователей по
влияние всплесков посещаемости, весь диапазон
регионам не равнозначно, т. е. пользователей,
делится на сегменты, и для каждого сегмента Frs
использующих Интернет в Москве больше, чем в
39
рассчитывается нормализованная частота − фильтрация кандидатов.
s
посещений пользователей по регионам F r : 3.1 Определение типовых шаблонов
Frs = k r ∗ f rs На этом этапе была проанализирована структура
s
- где f r - частота посещений для региона, сайтов организаций, и на основе полученной
рассчитанная в рамках одного сегмента. информации были отобраны наиболее часто
Далее для каждого сегмента определяется регион встречающиеся типовые шаблоны сайтов. По
с максимальной нормализованной частотой: результатам анализа можно выделить следующие
s три этапа:
Frmax = maxF s • Поиск адресов на корневой странице сайта.
s
- где F множество значений частот для данного • Поиск ссылок на страницу «Контакты».
сегмента. • Поиск адресов на странице «Контакты».
Для каждого региона в рамках одного сегмента Как показывают результаты экспериментов,
s одним из наиболее часто встречающихся мест
вычислим величину Rr такую что:
расположения контактной информации является
s
⎧⎪1, Frs = Frmax
s
корневая страница. В тоже время, эта страница
R =⎨
r может не являться достоверным источником
⎪⎩0, Frs < Frmax
s
информации, поскольку существуют сайты,
По всем сегментам региона рассчитывается например, размещающие объявления, включающие
агрегированная величина Rragr в себя хорошо читаемые адреса, часть из которых
может быть включена в главную страницу. В данной
N работе для адресов, извлеченных с корневой
∑R s
r,i
страницы сайта, применяется дополнительная
фильтрация.
s
R r,i ∈N,i=1
Rragr = Еще одним наиболее часто встречающимся
N местом расположения контактной информации
- где N - общее количество сегментов данных. является страница «Контакты». Как правило, на нее
По результатам определяется принадлежность существуют ссылки с главной страницы, и они в
ресурса региону R , на множестве N agr : большинстве случаев подчиняются ряду правил.
Например, текст ссылки может содержать слово
«контакты», «О нас» и т. д.
site ∈ R, Rragr = maxN agr ∧ Rragr ≥ K tr
3.2 Извлечение кандидатов
Значение порогового коэффициента K tr задается Как уже говорилось ранее, при анализе сайта
производятся попытки извлечь информацию об
таким, чтобы исключить попадание ресурса в адресах из корневой страницы сайта и (или) со
регион с низким рейтингом. В наших работах этот страницы «Контакты». Существуют множество
коэффициент принимался равным 0,6. подходов к извлечению информации из
неструктурированных текстов [6,7]. Мы в своей
3. Геопривязка ресурса на основе работе использовали комбинированную методику,
анализа контента страниц ресурса основанную на словарном поиске города, вероятно
входящего в адрес, и скрытой Марковской модели,
Как уже было сказано ранее, одним из которая позволяет оценить последовательность слов
источников информации о геопривязке сайта может окружающих найденный город. Левый и правый
служить сам контент. Как правило, такими контекст оценивался отдельно. Поскольку в данной
источниками являются сайты организаций, на задаче требуется вычислить только вероятность
которых публикуется информация о местах их появления последовательности адреса в окрестности
расположения, включающая в себя адреса и города, то для решения использовался алгоритм
телефоны. Извлекая эту информацию из страниц «forward-backward».
сайтов, можно осуществить геопривязку сайта более Если рассматривать элементы почтового адреса
точно, чем при помощи метода описанного в как состояния модели, то в рамках локально
предыдущей секции. решаемой задачи количество состояний можно
Решение задачи извлечения информации, в значительно уменьшить, что приведет к упрощению
нашем случае, было разбито на несколько частей: самой модели. Например, можно объединить все
− определение типовых шаблонов сайтов, на модификаторы улиц в одно состояние. В этом случае
которых может размещаться информация о — улица, шоссе, переулок... образуют состояние
месте расположения организации;
msstate . Таким же образом, можно транслировать
− извлечение кандидатов для последующей
привязки сайта к географической множество известных географических названий в
информации; одно состояние последовательности.
Сформированное таким образом множество
40
tw state Описывает город, найденный в словаре
cn state Описывает страну, найденную в словаре
mt state Описывает один из известных модификаторов города (г., сел...)
ms state Описывает один из известных модификаторов улицы (ул, ...)
mh state Описывает один из известных модификаторов дома.(д., ...)
mf state Описывает модификатор квартиры (кв., офис...)
Таблица 2. Пример состояний скрытой Марковской модели для адреса
состояний модели
S = {s1, s2, .., sn }, n = 19 3.3 Фильтрация кандидатов
Уменьшение количеств состояний модели Извлеченные адреса проходят фильтрацию.
приводит к необходимости вводить матрицы Первый этап фильтрации заключается в том, что из
проекций элемента адреса на состояние модели и в страницы также извлекается дополнительная
то же время приводит к значительному уменьшению информация, как например, телефон, который
размера обучающего множества, на основе которого ставится в соответствие одному или нескольким
определяются последовательности смены состояний адресам, извлеченным из страницы.
Одно из сопоставлений это проверка кода
s1, ..., sn . Затем строится матрица вероятностей региона, указанного в номере телефона на
переходов между состояниями Ps' (s | v ) , где соответствие городу, указанному в адресе.
Второй этап фильтрации включает набор
s' ∈ S - предшествующее состояние системы; эмпирических правил, которые накладываются на
s∈S - текущее состояние системы; v- выделенный адрес. К таким правилам, например,
относится ограничение на возможное количество
рассматриваемый элемент последовательности,
{
принадлежащий множеству V = v1, ..., vm . Можно } цифр, содержащихся в номере дома. После
применения ряда правил извлеченный адрес либо
обозначить состояние, которое принимает система принимается, как один из адресов, описывающий
во время t как qt , а наблюдаемую величину в местоположение организации, либо отклоняется.
момент t как yt . Элементы матрицы вероятностей 4. Использование извлеченной
перехода из состояния i в состояние j обозначим географической информации
как aij = p (qt+1 = s j | qt = si ) , а вероятность Извлеченная географическая информация
методами, описанными ранее, используется для
получить данные vk в состоянии j обозначим как решения задач связанных с ранжированием
b j (k ) = p (vk | s j ) . Обозначим данные через документов в поиске, а так же привязки найденных
сайтов к картографическому сервису.
D = d1....dT (последовательность наблюдаемых, d i Для осуществления ранжирования с учетом
географической информации, необходимо знать
принимает значение из V ). Также для построения
регион пользователя, который, прежде всего,
модели нужно учесть начальное распределение
{ } ( )
р = р j , р j = p q1 = s j . В нашем случае мы по
определяется по его IP адресу. Если в регионе
пользователя существуют локальные сайты,
полученной модели Л = ( A, B, р ) и
которые, в том числе, релевантны запросу, то они
попадают в региональное ранжирование.
последовательности D найдем p (D | Л) . При использовании в сервисе картографии
Формально можно записать: данные проходят дополнительную нормализацию и
проверку на соответствие реальным адресам.
p(D | Л) = ∑ p (D | Q, Л) p(D | Л) Данные для проверки берутся из картографической
Q базы.
Используя построенную модель и зная
возможную точку расположения адреса на странице, 5. Оценка других источников извлечения
найденную при помощи словаря городов, географической информации
производим оценку контекста, в котором находится
найденный город, используя процедуру «forward- В нашей работе мы опираемся на два основных
backward». За более подробным описанием источника получения информации о географии
алгоритма можно обратиться к [1]. сайта: анализ статистики посещений сайта и
извлечение информации непосредственно из
страниц сайта. Есть так же и другие источники,
41
Количество Сайтов получивших Точность Полнота охвата
сайтов взятых для географическую геопривязки веб исходных данных
анализа привязку ресурса
Анализ контента 20 миллионов. 330604 97% 1,6%
страниц
Анализ 1 миллион 121609 76% 12%, или от всего
статистики множества 0,6%
посещаемости
Суммарно по 20 миллионов 440213 80% 2,2%
сайтам.
Суммарно по 3, 9 миллиарда 1,3 миллиарда - 33%
страницам страниц страниц, получили
географический
признак
Таблица 4: Полнота охвата базы сайтов
Регион Сайты, попавшие в регион
Санкт-Петербург 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
Таблица 3: Пример сайтов, приписанных региону по сумме двух методов
которые можно было бы использовать для исключались статистически не значимые данные,
определения географической принадлежности сайта. например, сайты с суточной посещаемостью менее
Например, в [5] описаны методы получения 100 посетителей. После обработки, полученные
информации о месте положения сервера путем результаты объединялись и загружались в единую
анализа маршрута IP пакета. К сожалению, многие базу для последующего решения задач связанных с
сайты располагаются на площадках нелокальных ранжированием и отображением найденной
провайдеров, и в полученной таким способом информации. Результаты анализа обоих этапов
информации, будут содержаться ошибочные приведены в таблице 3. Также в таблице
результаты. представлена суммарная характеристика по обоим
Так же в качестве источника информации можно этапам. Нужно учесть, что при слиянии результатов
рассматривать и некоторые каталоги, в которых частично произошло пересечение по сайтам. Так же
организации могут размещать информацию о себе, в было рассчитано, какое количество страниц
том числе и о своем месте расположения. В силу получили географическую привязку для сайтов,
некоторых особенностей устройство таких принадлежащих регионам. Как видно из таблицы 3,
каталогов таково, что практически отсутствует суммарное количество сайтов, получивших
механизм контроля введенной информации. По этой геопривязку, не превышает трех процентов. В тоже
причине информация, содержащаяся в таких время этот набор сайтов дает порядка одной трети
каталогах, может содержать как ошибки, так и всех станиц находящихся в базе. На диаграмме 1
подлоги. приведено распределение сайтов по регионам, как
видно из диаграммы самым большим регионом, в
6. Эксперименты который попадают сайты, является Москва.
В качестве примера были взяты два самых
Для экспериментов была взята база страниц крупных региональных города России и один из
скачанных из интернета, содержащая порядка 20 Украины, для них случайным образом отобрали пять
миллионов сайтов и 3,9 миллиарда страниц. Из этих сайтов, получившие в качестве географического
данных на основе анализа контента страниц признака идентификатор этого города. Результаты
проводилась географическая привязка сайта представлены в таблице 4
алгоритмом, описанным в п.3. Так же была Для оценки точности мы отобрали случайным
проанализирована статистика посещаемости образом порядка 100 сайтов и проверили точность
миллиона сайтов (данные Top@Mail.Ru), для попадания географической привязки, проставленной
определения привязки сайта к его географическому суммарно по двум методам, и по каждому методу
расположению на основе алгоритма описанного в отдельно, сопоставив ее с реальной информацией
п.2. При анализе статистики из рассмотрения доступной на сайте.
42
7. Выводы региональных сайтов по географическим запросам.
Оценки проводились независимо для трех
В статье рассматриваются два метода получения различных регионов. В результате этого
информации для геопривязки ресурса: на основе эксперимента, мы получили удовлетворительное
анализа посещаемости пользователей и на основе качество ответов поисковой машины, по всем трем
анализа контента страниц ресурса. Как показали регионам.
эксперименты, наиболее точным методом является
метод, построенный на основе анализа контента. В
его случае точность достигает 97%. Это
Литература
обусловливается рядом ограничений, а именно: [1] Cappe O., E. Moulines, T. Ruden. Inference in
3%
hidden Markov Models. Springer. 2005. 652 p.
[2] Han J. and M. Kamber. Data Mining: Concepts and
Techniques. Morgan Kaufmann, San Francisco, 2006 .
[3] Jones C.B., R. Purves, A. Ruas, M. Sanderson, M.
41%
38%
Sester, M.J. van Kreveld, R. Weibel. Spatial Information
Retrieval and Geographical Ontologies An Overview of
the SPIRIT Project. SIGIR 2002: In SIGIR’02,
Tampere, Finland, 387-388. 2002.
[4] Larson R.R. Geographic Information Retrieval and
Москва Spatial Browsing. https://sherlock.ischool.berkeley.edu/
4%
Санкт-Петербург 14% geo_ir/PART1.html
Екатеринбург [5] McCurley K.S. Geospatial Mapping and Navigation
of the Web. 10th International World Wide Web
Все
Conference (WWW-2001), Hong Kong, ACM Press, p.
Мультирегиональные 221-229 . 2001.
[6] Zheyuan Y. High accuracy postal address extraction
Диаграмма 1: Распределение сайтов по регионам from Web pages. 2007
[7] Прокофьев П. А. Использование методов
использованием предопределенных шаблонов для извлечения информации при географической
нахождения страницы с адресом; использованием привязке текстов на русском языке. Электронные
словаря городов; сопоставление номера телефона и библиотеки: Перспективные Методы и Технологии,
города, а так же существующие формальные Электронные коллекции. Труды RCDL. 2009. c. 254-
правила для записи адреса. Все эти ограничения 258
позволяют достичь достаточно высокой точности,
при определении географии веб-ресурса. С другой Determining the Geographic Location of
стороны, эти ограничения приводят к снижению Internet Resources
полноты, в случаях, если адрес записан без прямого
указания города или с неизвестным городом, если © D.V. Soloviev, A.L. Kalinin.
страница с контактами расположена по адресу,
который не описан в известных шаблонах поиска. This paper describes extraction of geospatial
Метод, реализованный на основе анализа information for Web resources. The document includes
статистики посещаемости, обладает большей a description of two methods for binding site to
полнотой относительно анализируемого множества geography based on: analysis of visit statistics and
сайтов (12%). В то же время, он обладает рядом analysis of the web page's content by hidden Markov
недостатков: множество анализируемых сайтов model (HMM).
ограничивается только данными, доступными из
статистики посещаемости, а это всего 5% от общего
множества сайтов; много статистически не
значимых сайтов, порядка 87%, которые выпадают
из рассмотрения; большая вероятность ошибки, чем
в случае использования метода анализа контента, из-
за неверного сопоставления IP адреса пользователя
его реальному местоположению.
Таким образом, используя эти два метода, в
эксперименте получили привязку к географии
только 2,2. процента сайтов. В то же время, в
количестве страниц это отношение составляет
порядка 33% от всех страниц, взятых для анализа.
Достаточно сложно оценить количество страниц,
которые должны реально получить геопривязку,
поэтому мы проводили оценку качества фильтрации
43