Какова вероятность популярности новой веб-страницы?
3. Алгоритм
3.1 Система
Во-первых, давайте опишем общую систему предлагаемого алгоритма. Согласно предыдущим исследованиям в данной области [7, 16, 20], мы задаём единый источник расчета стоимости индексирования по всем страницам. Другими словами, принимаем во внимание фиксированное время
, которое понадобится роботу на загрузку одной страницы. Таким образом, каждые секунд робот выбирает страницу для загрузки из своей очереди страниц на индексацию. Очередь страниц на индексацию постоянно обновляется по мере обнаружения новых ссылок на страницы. Очередь страниц на индексацию может обновляться по ряду причин. Новые URL могут быть обнаружены роботом или могут прийти из логов тулбара браузера, например. В данной работе мы не рассматриваем проблему обнаружения новых адресов, а в ходе своего исследования мы брали новые адреса, поступившие из тулбара браузера.3.2 Метрика
Была предложена [12] следующая метрика для измерения эффективности алгоритма. Полезность страницы
, которую мы получим от индексации страницы i по прошествии времени 
после её появления выражается в общем числе кликов, которое эта страница получит со страницы выдачи после того, как она (страница i) будет проиндексирована. Важно отметить, что мы рассматриваем только страницы, которые представляют интерес в краткосрочной перспективе. В таком случае, качество алгоритма в момент времени t (среднее арифметическое от интервалов T) будет выражаться следующим образом:
Важно также отметить, что число кликов по странице выдачи зависит от ряда причин, включая особенности пользовательского поведения и систему ранжирования, а не только от алгоритма индексации. Поэтому не всегда очевидно как интерпретировать изменение в количестве кликов при изменении политики индексации. Так, например, меняется ли количество кликов только из-за изменения политики индексации страниц, либо зависит ещё и от метода ранжирования и тогда это количество может быть разным при применении разных одинаково хороших политик индексации? На самом деле, мы считаем, что разумней в данном случае обращаться к пользовательским логам, которые мы можем получить из данных тулбара и выбрать количество посещений как основной ориентир, который заменит нам показатель кликов — этого будет достаточно для измерения эффективности индексации. Таким образом, полезность
которую мы получим если проиндексируем страницу i с задержкой будет в дальнейшем обозначать количество посещений этой страницы после того, как она была проиндексирована.Как это будет показано в разделе 4.1, мы оцениваем успешность алгоритма на базе данных, собранных за один месяц. Таким образом, пусть T = 1 месяц, а
будет означать среднюю пользу (или полезность) применения данной политики индексации в секунду за этот месяц.3.3 Стратегия индексации
Как мы условились в разделе 3.1, каждые
секунд наш алгоритм должен выбирать страницу из очереди страниц на индексацию. Наша задача — каждый раз выбирать соответствующий URL для того, чтобы проиндексировать страницу при условии, что очередь на индексацию динамически изменяется.Для этого мы примем во внимание динамику изменения популярности следующим образом. В [12] было показано, что полезность
, которая является результатом индексации страницы u с некоторым опозданием 
— экспонентно затухает со временем.Таким образом, эта полезность может быть апроксимирована при помощи
с некоторыми параметрами 
и 
. Мы можем видеть, что при
, мы получим 
, которое будет выражать общую популярность страницы u, то есть, в нашем случае общее количество посещений страницы пользователями с момента её создания, а будет обозначать спад её популярности. Для каждой страницы u мы предсказываем параметры
и так, как это описано в разделе 3.4. И наконец, стратегия будет выбрана следующая. Каждые секунд мы выбираем страницу с максимальным показателем ожидаемой полезности. То есть, для каждой страницы u мы каждые секунд вычисляем её рейтинг, который в дальнейшем используется для того, чтобы ранжировать все новые страницы в очереди на индексацию: 
где это время, которое прошло с момента обнаружения страницы u. После чего мы индексируем страницу с наивысшим рейтингом в очереди. Время, когда страница была обнаружена для простоты апроксимируется со временем, когда она была создана. Поэтому мы допускаем, что первое посещение этой страницы, зафиксированное в пользовательских логах тулбара близко ко времени создания страницы.
3.4 Ожидаемая популярность страницы
В этом разделе мы рассмотрим метод прогнозирования параметров
и для конкретного URL u. Мы рассмотрим модель дерева решений на основе gradient boosting со списком характеристик, описанных далее в этой секции. Напомним, что представляет собой общее число посещений страницы u, зафиксированных через тулбар. Поскольку распределение всех для всех страниц u в нашем блоке данных представляет собой большие числа, то мы имеем дело с большими значениями . Для того, чтобы составить политику индексации, нам нужно знать порядок величины, в то время как определение точного числа не так важно. Как это и бывает с распределением вероятностей, выраженных большими величинами [19], мы прогнозируем значение 
, уменьшая среднеквадратическое отклонение на обучающей выборке. Мы также определяем спад популярности
. Пусть 
будет означать число посещений за время t (в наших экспериментах измеряемое в часах) после того как URL u был обнаружен. Мы тренируем нашу модель дерева принятия решений которая предсказывает соотношение к числу всех посещений страницы u, то есть, значение 
(в этом случае мы уменьшаем среднеквадратическое отклонение). Затем мы можем определить уровень спада 
следующим образом. Исходя из уравнения 
следует, что 
. Вычислим логарифм и получим 
и тогда мы можем определить через 
Таким образом, прогнозируемая польза от индексации страницы u с задержкой
после её появления будет иметь следующее значение: 
Список литературы
1. Abiteboul, S., Preda, M., Cobena, C.: Adaptive on-line page importance compu-
tation. In: Proc. WWW Conference (2003)
2. Abramson, M., Aha, D.: What’s in a URL? Genre classification from URLs. In:
Conference on Artificial Intelligence, pp. 262-263 (2012)
3. Bai, X., Cambazoglu, B.B., Junqueira, F.P.: Discovering urls through user feed-
back. In: Proc. CIKM Conference, pp. 77-86 (2011)
4. Baykan, E., Henzinger, M., Marian, L., Weber, I.: A comprehensive study of fea-
tures and algorithms for url-based topic classification. ACM Trans. Web (2011)
5. Baykan, E., Henzinger, M., Weber, I.: Eficient discovery of authoritative resources.
ACM Trans. Web (2013)
6. Cho, J., Schonfeld, U.: Rankmass crawler: a crawler with high personalized pager-
ank coverage guarantee. In: Proc. VLDB (2007)
7. Edwards, J., McCurley, K.S., Tomlin, J .A.: Adaptive model for optimizing perfor-
mance of an incremental web crawler. In: Proc. WWW Conference (2001)
8. Fetterly, D., Craswell, N., Vinay, V.: The impact of crawl policy on web search
effectiveness. In: Proc. SICIR Conference, pp. 580-587 (2009)
9. Hastie, T., Tibshirani, R., Friedman, J .H.: The elements of statistical learning:
data mining, inference, and prediction: with 200 full-color illustrations. Springer,
New York (2001)
10. Kan, M.Y.: Web page classification without the web page. In: Proc. WWW Con-
ference, pp. 262-263 (2004)
11. Kumar, R., Lang, K., Marlow, C., Tomkins, A.: Eficient discovery of authoritative
resources. Data Engineering (2008)
12. Lefortier, D., Ostroumova, L., Samosvat, E., Serdyukov, P.: Timely crawling of high-
quality ephemeral new content. In: Proc. CIKM Conference, pp. 745-750 (2011)
13. Lei, T., Cai, R., Yang, J.M., Ke, Y., Fan, X., Zhang, L.: A pattern tree-
based approach to learning url normalization rules. In: Proc. WWW Conference,
pp. 611-620 (2010)
14. Liu, M., Cai, R., Zhang, M., Zhang, L.: User browsing behavior-driven web crawl-
ing. In: Proc. CIKM Conference, pp. 87-92 (2011)
15. Olston, C., Najork, M.: Web crawling. Foundations and Trends in Information
Retrieval 4(3), 175-246 (2010)
16. Pandey, S., Olston, C.: User-centric web crawling. In: Proc. WWW Conference
2005
17. Pandiy, S., Olston, C.: Crawl ordering by search impact. In: Proc. WSDM Con-
ference (2008)
18. Radinsky, K., Svore, K., Dumais, S., Teevan, J., Bocharov, A., Horvitz, E.: Model-
ing and predicting behavioral dynamics on the web. In: Proc. WWW Conference,
pp. 599-608 (2012)
19. Tsur, O., Rappoport, A.: What’s in a hashtag?: content based prediction of
the spread of ideas in microblogging communities. In: Proc. WSDM Conference,
pp. 643-652 (2012)
20. Wolf, J.L., Squillante, M.S., Yu, P.S., Sethuraman, J., Ozsen, L.: Optimal crawling
strategies for web search engines. In: Proc. WWW Conference (2002)
Этот и другие переводы вы можете найти в блоге компании ALTWEb Group на Хабре. Аналитический отдел компании проводит исследования и обзоры текущих проблем поиска и использует полученные знания при разработке собственных продуктов, таких например, как не имеющий на данный момент отечественных (почти) или зарубежных (совсем) аналогов продукт для повышения ранжирования сайта на базе поведенческих факторов: SERPClick. Благодарим за предоставленный перевод. Подпишитесь на наш блог, если хотите всегда быть в курсе!
Источник: habrahabr.ru/company/altweb/blog/239453/
Обсуждение