Борьба со спамом при помощи алгоритма Trustrank | Статьи SEOnews
Краткое изложение содержания
Создатели страниц, в которых содержится спам, прибегают к различным технологиям для достижения высоких результатов в выдаче и быстрой раскрутки сайта. Есть специальные эксперты, которые умеют идентифицировать спам, но данный процесс достаточно трудоемкий и дорогостоящий. В связи с этим предлагается полуавтоматическая технология выявления спама. Сначала отбирается несколько случайных страниц, которые будут оценены экспертом. Идентифицировав вручную несколько случайно выбранных страниц, в дальнейшем используется ссылочная структура Интернета для определения других страниц, которые, скорее всего, окажутся «хорошими» и правильными страницами. В данной работе обсуждаются возможные способы случайного отбора и обнаружения «хороших» страниц. Представляются результаты экспериментов, проводимых в Интернете и оценка эффективности работы технологии. Результаты показали, что существуют эффективные способы фильтрации спама.
1. ВВЕДЕНИЕ
Термин «интернет-спам» используют для обозначения страниц, содержащих многочисленные ссылки, специально созданные для введения поисковых систем в заблуждение. Например, порнографический сайт может способствовать распространению спама в Интернете, добавляя тысячи ключевых слов на домашнюю страницу, причем текст зачастую специально делается невидимым для пользователей. Поисковая система индексирует дополнительные ключевые слова и предоставляет порнографическую страницу в качестве ответа на запросы, содержащие эти слова. Так как добавленные ключевые слова не являются непристойной лексикой, пользователи попадают на страницы такого сайта. Еще одна техника быстрой раскрутки сайта – создание большого количества поддельных веб-страниц, указывающих на единственную целевую страницу. В связи с тем, что многие поисковые системы учитывают количество входящих ссылок при ранжировании страниц, целевая страница, скорее всего, появится раньше всех в результатах поиска.
Вопрос, является ли страница или группа страниц спамом (это касается и электронной почты), достаточно субъективный. Например, возьмем несколько сайтов, неоднократно ссылающихся на страницы друг друга. Такие ссылки могут просто свидетельствовать о сходной тематике сайтов, или быть созданы специально для повышения ранжирования страниц. Зачастую достаточно проблематично определить, какой из двух сценариев раскрутки был использован.
В целом, пользователи легко распознают явные и неприкрытые проявления спама. Например, большинство согласится, что если основная часть текста на странице сайта невидима пользователю и не соответствует тематике, то, очевидно, страница была добавлена с намерением ввести поисковую систему в явное заблуждение. Точно так же дело обстоит, если на странице встречается огромное количество URL, ссылающихся на такие хосты как:
- buy-canon-rebel-300d-lens-case.camerasx.com;
- buy-nikon-d100-d70-lens-case.camerasx.com;
особенно, если они относятся к одному IP адресу. Легко сделать вывод, что страница специально была создана, чтобы быстро запутать поисковые системы. (URL-спам основан на том факте, что многие поисковые системы уделяют особое внимание словам в именах хостов и придают этим словам больший вес, если они встречаются в тексте).Если большинство пользователей могут распознать явный спам, то для поисковой системы это не так просто. Крупнейшие поисковые порталы имеют в штате сотрудников, которые специализируются на отслеживании интернет-спама. Когда обнаруживается страница, содержащая спам, поисковая система прекращает обход страницы, контент не индексируется. Такой процесс отслеживания спама медленный и дорогостоящий, но он дает результаты. При отсутствии борьбы со спамом качество результатов поиска будет стремительно ухудшаться.Цель проведенного исследования – помочь экспертам, занимающимся отслеживанием спама. Основная задача – научиться идентифицировать страницы и сайты, которые являются спамом, и наоборот, которые содержат релевантный тематике контент. Методы, представленные в данной работе, могут иметь два назначения:
- как помощь при тщательном изучении страниц на предмет спама;
- как способ борьбы с результатами спама.
Процесс алгоритмической идентификации спама сложен, поэтому схемы, представленные в данной работе не будут оперировать без вмешательства специалиста.
Предлагаемый алгоритм работает следующим образом: случайной выборкой избираются страницы, которые должны быть исследованы на наличие спама. Эксперт исследует «случайные страницы», и сообщает алгоритму, присутствует ли на них спам. Впоследствии алгоритм идентифицирует другие страницы, которые, скорее всего, окажутся «хорошими», при учете их связи с «хорошими случайными» страницами.
В этой работе:
- Формализуется проблема веб-спама и алгоритма отслеживания спама.
- Определяются показатели оценки эффективности работы алгоритмов отслеживания спама.
- Представляются схемы для случайного отбора страниц, которые будут оценены вручную.
- Предлагается алгоритм TrustRank для определения вероятности «хороших» страниц.
- Обсуждаются результаты проведенной работы (роботы поисковой системы Alta Vista обошли 31 млн сайтов, 2 тыс. сайтов были изучены вручную). Предлагается любопытная статистика частоты встречаемости определенных видов контента.
2. ПРЕДВАРИТЕЛЬНАЯ ИНФОРМАЦИЯ
2.1. интернет-модель
Представляем модель сети в виде графа ς = (ν,ε),состоящего из множества ν страниц N и множества ε направленных ссылок, соединяющих страницы. На практике интернет-страница p может содержать многочисленные HMTL гиперссылки на некую другую страницу q. В этом случае мы представляем эти многочисленные ссылки как единственную ссылку (p,q) є ε. Мы также удаляем внутренние ссылки. На рис.1 представлен очень простой Интернет граф, состоящий из 4 страниц и 4 ссылок.
Рис.1 Простой Интернет граф
Каждая страница содержит входящие и исходящие ссылки. Количество входящих ссылок на страницу p представляет собой полустепень захода i(p). Количество исходящих ссылок – полустепень исхода w(p). Например, полустепень захода страницы 3 на рис.1 равна единице, а полустепень исхода – двум.
Страницы, которые не содержат входящие ссылки, называются страницами без ссылок. Страницы, которые не содержат исходящих ссылок, называются не ссылающимися страницами. Страницы, которые не содержат ни входящих, ни исходящих ссылок, называются изолированными. Страница 1 на рис.1 является страницей без ссылок, а страница 4 – не ссылающейся.
Рассмотрим 2 матрицы интернет-графов, которые в дальнейшем будут иметь важное значение. Одна из матриц – матрица перехода Т:
Матрица перехода, соответствующая графу на рис.1:
Рассмотри также обратную матрицу перехода U:
Необходимо обратить внимание, что U≠TT . Например, на рис.1 обратная матрица перехода выглядит так:
2.2. PageRank – алгоритм расчета авторитетности страницы, а также сам показатель в численном выражении. Так как предлагаемые алгоритмы основаны на PagеRank, в данном разделе предлагается его короткий обзор.Page Rank страницы будет достаточно высоким, если необходимое количество важных страниц указывают на эту страницу. Page Rank основывается на взаимном влиянии страниц. Страница не только сама оказывает влияние на другую страницу, но и испытывает влияние на себе. Показатели Page Rank r(p) страницы p определяются так:
где α – коэффициент распада. Равносильно матричное уравнение:
Таким образом, оценка некоторой страницы p представляет сумму двух компонентов. Одна часть оценки относится к страницам, которые указывают на страницу p. Другая (статическая) часть оценки подходит для всех веб-страниц.
Page Rank может вычисляться итерационно, например, с помощью метода Jacobi. В строго математическом смысле итерация должна переходить в конвергенцию. На практике принято использовать четко зафиксированное число итераций.
Стандартный алгоритм PageRank присваивает статическую оценку каждой странице, версия Page Rank со смещением функционирует по-другому. В матричном уравнении
вектор d может быть использован для присвоения нулевой статической оценки ряду страниц. Оценка таких специальных страниц распространяется во время итерации на указываемые страницы.
3. ОЦЕНКА СТЕПЕНИ ДОВЕРИЯ
3.1. Функции прогнозирования и доверия
В разделе 1 уже было сказано, что распознавание спама – задача, требующая вмешательства человека и его субъективной оценки. Существует понятие проверки страницы на спам с помощью двоичной функции прогнозирования (О) всех страниц p є ν:
На рис.2 представлены 7 интернет-страниц. «Хорошие» страницы представлены на белом фоне, «плохие» – на черном. Вызывая функцию прогнозирования для страниц 1-4, будет выдано значение 1.
Рис.2 Хорошие и плохие узлы сети
Процедура прогнозирования дорогостоящая и достаточно длительная. Поэтому применение подобной функции для всех страниц не приемлемо. При проведении анализа важно продемонстрировать избирательность, поэтому логичнее обратиться к эксперту для анализа некоторых интернет-страниц.
При анализе «хороших» страниц мы полагались на эмпирическое наблюдение:
«Хорошие» страницы редко указывают на «плохие».Данный вывод основан на интуиции: «Плохие» страницы создаются с намереньем ввести поисковые системы в заблуждение, они далеки от цели предоставления полезной информации. Таким образом, у людей, создающих «хорошие» страницы, нет ни малейшего основания ссылаться на «плохие» страницы.
Однако создателей «хороших» страниц тоже иногда вводят в заблуждение. Поэтому в Интернете можно встретить ссылки с «хороших» страниц на «плохие» (на рис.2 такая ссылка показана между страницами 4 и 5 и помечена звездочкой). Рассмотрим пример. Возьмем хорошую, но немодерируемую гостевую книгу. Спамеры могут разместить ссылку на свои спам-страницы, как часть «невинных» сообщений, размещаемых в этой «гостевой».
Иногда спамерские сайты представляют из себя т.н. «Honeypot» («горшочек меда»): сайты представляют собой набор страниц, которые содержат полезную информацию (например, копии документации Unix), в то же время на страницах содержатся скрытые ссылки на спам-страницы. «Honeypot», привлекая пользователей ссылаться на них, увеличивает ранжирование страниц, содержащих спам.
Необходимо подчеркнуть, что, в свою очередь, заспамленные страницы часто ссылаются на «хорошие» страницы. Например, создатели заспамленных страниц указывают на «хорошие» и важные страницы, с целью создания «Honeypot», либо в надежде, что большое количество исходящих ссылок будут способствовать повышению некоторых видов ранжирования.Для оценки страниц, не прибегая к показателю О, необходимо оценить, какова вероятность того, что данная страница Р является «хорошей». Выражаясь научным языком, определяется функция доверия Т имеющая диапазон значений от 0 (плохая страница) до 1 (хорошая страница) В идеале, для любой страницы р, Т(р) должно показывать вероятность того, что страница р – «хорошая».
Идеальный показатель функции доверия
T(p) = Pr[O(p) = 1]
Допустим, имеется 100 страниц, показатель доверия которых составляет 0.7. Предположим, что оценка страниц осуществляется с использованием функции прогнозирования. Тогда, если Т сработает нужным образом, для 70 страниц показатель прогнозирования составит 1, а для оставшихся 30 – 0.
Если Т не может точно определить вероятность того, что страница «хорошая», то данная функция все равно окажется необходимой при делении страниц на «хорошие» и «плохие», полагаясь при этом на приблизительные данные. Например, даны две страницы, p и q. Показатель доверия страницы р ниже показателя доверия страницы q. Из этого следует, что вероятность того, что страница р «хорошая» ниже вероятности того, что страница q «хорошая». Функция доверия Т окажется полезной, по крайней мере, при распределении результатов поиска, когда предпочтение отдается страницам, которые, вероятнее всего, являются «хорошими».
Одним из предпочтительных свойств функции доверия является «свойство упорядоченности доверия»
Один из способов понизить требования к показателю доверия – ввести пороговую величину δ.
Пороговый показатель функции доверия
Если страница p получает оценку выше показателя δ это свидетельствует о том, что страница «хорошая». В противном случае, о странице p ничего нельзя будет сказать. Функция Т предоставляет информацию, в соответствии с которой можно определить, что страницы, находящиеся в некотором подмножестве и имеющие высокий показатель доверия являются хорошими.
Обратите внимание, что функция Т с пороговым показателем не всегда влияет на сортировку страниц по принципу «хорошие»-«плохие».
3.2. Показатели оценки
В данном разделе представлены 3 показателя, которые помогают оценивать характеристики функции Т.
Допустим, имеется χ случайных интернет-страниц, для которых можно привлечь функции Т и О и оценить, как работают те или иные свойства для данного множества. (в разделе 6 будет рассказано, по какому принципу выбираются страницы, а пока мы считаем, что χ – множество случайных веб-страниц).
Первый показатель тесно связан с заданным показателем доверия. Вводится двоичная функция I(T, O, p, q), с помощью которой определяется, что «плохие» страницы получили показатель доверия равный или выше «хороших» страниц
Затем из выборки χ страниц составляются множества 
пар страниц (p,q), p ≠ q, затем вычисляется, с какими парами страниц функция доверия не допускает ошибок:
Pairwise Ordredness (упорядоченность пары)
Если pairord равен 1, то в функции доверия ошибок не было, если pairord равен 0, то в функции доверия неправильная для всех пар.
Два следующих показателя относятся к пороговому показателю уровня доверия. Вводятся показатели precision (точности) и recall (воспроизведения) для пороговой величины δ. Показатель Precision вычисляется как отношение хороших страниц, принадлежащих χ, ко всем страницам, принадлежащим χ, показатель доверия которых указан.
Подобным образом, мы определяем показатель Recall как отношение количества хороших страниц с указанным показателем доверия к общему количеству хороших страниц, принадлежащих χ.
4. Вычисление доверия
В разделе 4.3 будет построен алгоритм TrustRank. Прежде необходимо произвести подготовительную работу.
Итак, приступим к выявлению функции доверия. Начнем с самого простого. При условии, что кол-во L ограничено для вычисления функции О, начнем непосредственно с выборки множества S случайных страниц L и вызовем функцию прогнозирования для заданных элементов. (В разделе 5 будет рассказано, как оптимально выбрать случайные страницы). Обозначим подмножества «хороших» и «плохих» страниц S+ и S- соответственно.Так как оставшиеся страницы не проверяются экспертами, им присваивается показатель доверия, равный ½ из-за отсутствия информации.
Вводится понятие пустая функция доверия T0 для любых p є ν:
Например, присвоим L значение 3 и применим наш метод к примеру на рис.2 Случайно выбранное множество S может иметь значения {1, 3, 6}. Пусть o и t0 будут обозначать векторы прогнозирования и показателей доверия для каждой страницы соответственно. Тогда:
Для оценки поведения пустой функции доверия предположим, что наша выборка X состоит из 7 страниц, и и мы рассматриваем все возможные 42 (7*6) пары. Тогда показатель упорядоченности пары составит 17/21. Для порога δ =½ показатель precision составит 1, а показатель recall – ½.
4.1. Распространение функции доверия
Для дальнейшего подсчета показателя доверия воспользуемся несвязностью «хороших» страниц.
Случайным образом выбираем множество S из L страниц, которые будут подвержены прогнозированию. Предполагая, что «хорошие» страницы указывают на другие исключительно «хорошие» страницы, оценка 1 присваивается всем страницам, которые доступны в S+ множестве в М или менее переходов.
Соответствующая функция доверия TMопределяется так:
| M | pairord | prec | rec |
| 1 |
19/21 |
1 |
3/4 |
| 2 |
1 |
1 |
1 |
|
3 |
17/21 |
4/5 |
1 |
Таблица1: поведение М-шаговой функции доверия ТM, при M є {1, 2, 3} .
М-шаговая функция доверия
Где q
M p свидетельствует о существовании пути максимальной длины М со страницы q на страницу p. Такой путь не должен содержать «плохих» страниц.
Используя пример на рис.2 и случайную совокупность S = {1, 3, 6}, можно представить оценку доверия для М с разными значениями:
M=1: t1 = [1, 1, 1, ½, ½, 0, ½]
M=2: t2 = [1, 1, 1, 1, ½, 0, ½]
M=3: t3 = [1, 1, 1, 1, 1, 0, ½]
В таблице1 показано, что при M = 1 и M = 2 значения pairord и recall возрастают, а значение precision равнo 1. Однако все совсем не так обстоит при M = 3. Страница 5 получает оценку 1 благодаря ссылке с «хорошей»страницы 4 на «плохую» страницу 5 (на рис. 2 отмечено звездочкой).Как показал предыдущий пример, проблема заключается в том, что при показателе доверия M-step нет абсолютной уверенности в том, что страницы из совокупности «хороших» страниц на самом деле являются «хорошими».
4.2. Затухание показателя доверия
Наблюдения свидетельствуют о том, что мы понижаем показатель доверия, по мере того, как все дальше и дальше удаляемся от «хороших» случайных страниц. Существует много способов по достижению снижения показателя доверия. Рассмотрим две возможные схемы.
На рис.3 предложен один из способов, который называется trust dampening (падение доверия). Так как страница 2 находится на расстоянии одной ссылки от «хорошей» случайной страницы 1, то ей можно присвоить заниженную оценку доверия β, где β < 1. Так как страница 3 следует за страницей 2, которой присвоен показатель β, то ей присваивается заниженная оценка, равная β*β.
Необходимо выбрать способ, как присваивать показатель доверия страницам, которые содержат многочисленные входящие ссылки. Например, на рис.3 стр.1 также ссылается на стр. 3. В этом случае, имеет смысл присвоить стр.3 максимальное значение показателя доверия, в данном случае β, или среднее значение, в данном случае: (β+β*β)/2
Ведущим семинара был John Herren – один из сотрудников компании Zend, независимый консультант по вопросам построения веб-приложений, автор множества учебных материалов по PHP, Linux и т.п. Начав с эволюции PHP и показав его логичное развитие в сторону ООП и использования Web-сервисов (привожу часть слайда на эту тему), ведущий продемонстрировал примеры работы с XML на PHP с помощью различных инструментов, таких как DOM, SimpleXML.