SEOgramota.Ru блог о SEO, продвижении, заработке в интернете

Краткое изложение содержания Создатели страниц, в которых содержится спам, прибегают к различным технологиям для достижения высоких результатов в выдаче. Есть специальные эксперты, которые умеют идентифицировать спам, но данный процесс достаточно трудоемкий и дорогостоящий. В связи с этим предлагается полуавтоматическая технология выявления спама. Сначала отбирается несколько случайных страниц, которые будут оценены экспертом. Идентифицировав вручную несколько случайно выбранных страниц, в дальнейшем используется ссылочная структура Интернета для определения других страниц, которые, скорее всего, окажутся «хорошими» и правильными страницами. В данной работе обсуждаются возможные способы случайного отбора и обнаружения «хороших» страниц. Представляются результаты экспериментов, проводимых в Интернете и оценка эффективности работы технологии. Результаты показали, что существуют эффективные способы фильтрации спама.

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, в данном разделе предлагается его короткий обзор. PageRank страницы будет достаточно высоким, если необходимое количество важных страниц указывают на эту страницу. PageRank основывается на взаимном влиянии страниц. Страница не только сама оказывает влияние на другую страницу, но и испытывает влияние на себе. Показатели PageRank r(p) страницы p определяются так: где α – коэффициент распада1. Равносильно матричное уравнение: Таким образом, оценка некоторой страницы p представляет сумму двух компонентов. Одна часть оценки относится к страницам, которые указывают на страницу p. Другая (статическая) часть оценки подходит для всех веб-страниц. PageRank может вычисляться итерационно, например, с помощью метода Jacobi. В строго математическом смысле итерация должна переходить в конвергенцию. На практике принято использовать четко зафиксированное число итераций. Стандартный алгоритм PageRank присваивает статическую оценку каждой странице, версия PageRank со смещением функционирует по-другому. В матричном уравнении вектор 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 X
00; 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 определяется так:  

Таблица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 Рис.3 Trust dampening Рис.4 Trust splitting Второй способ для снижения показателя доверия, который называется trust splitting (разделение доверия) основан на следующем наблюдении: осторожность, с которой пользователи добавляют ссылки на свои страницы, обратно пропорциональна количеству ссылок на странице. Другими словами, если «хорошая» страница содержит всего несколько исходящих ссылок, то, скорее всего, страницы, на которые ведут эти ссылки, «хорошие».

Однако если «хорошая» страница содержит сотни исходящих ссылок, то велика вероятность того, что страницы, на которые ведут эти ссылки, окажутся «плохими». Данное наблюдение приводит нас к «разделению доверия», так как данное наблюдение распространяется и на другие страницы: если страница р имеет показатель доверия Т(р) и указывает на!(р) страниц, то оценка для каждой из!(р) страниц будет равна отношению T(p)/!(p). В этом случае, реальная оценка страницы будет представлять собой сумму оценок, рассчитанных с помощью входящих ссылок. Наглядно, чем больше доверия получает страница с других страниц, тем больше вероятность того, что данная страница «хорошая». Рис.4 схематично представляет метод trust splitting. «Хорошая» случайная страница 1 содержит 2 исходящие ссылки, таким образом, она распределяет половину оценки, равной 1, между страницами, на которые она указывает. Точно так же, «хорошая» случайная страница 2 содержит три исходящих ссылки, соответственно, каждая страница, на которую указывает страница 2, получает одну треть от ее оценки. Тогда оценка страницы 3 будет складываться следующим образом: 1/2 + 1/3 = 5/6. Необходимо отметить, что возможно совмещение двух способов снижения показателя доверия. На рис.4, например, стр.3 может быть присвоена оценка, которая рассчитывается следующим образом: β*(1/2 + 1/3) . В дальнейшем будет доказано, что при вычислении оценки доверия целесообразно полагаться на алгоритм Page Rank. 4.3 Алгоритм TrustRank Функция TrustRank, изображенная на рис. 5, необходима при подсчете оценки доверия для интернет-графа. Алгоритм работы объясняется с помощью рис.2. Алгоритм TrustRank представляет собой граф (переходная матрица Т и N интернет-страниц). Используются параметры, которые контролируют работу алгоритма (L, MB, αB см. ниже). Рис.5 Алгоритм TrustRank Шаг 1: алгоритм вызывает функцию SelectSeed, которая возвращает вектор s. Составляющие вектора s(p) определяют «предпочтение» страницы p как случайной страницы (подробности можно найти в разделе 5). Как показано в разделе 5.1, одна версия SelectSeed возвращает следующий вектор к примеру на Рис.2: s = [0,08, 0,13, 0,08, 0,10, 0,09, 0,06. 0,02]. Шаг 2: функция Rank(x, s) осуществляет преобразования вектора х в х’, с элементами х’(i) в порядке убывания значения s(x’(i)). Например, σ = [2, 4, 5, 1, 3, 6, 7]. В соответствии с приведенным примером, страница 2 самая предпочтительная случайно выбранная страница, следующая 4 и т. д. Шаг 3: активизируется функция Oracle для L, наиболее предпочтительных страниц. Составляющие статического вектора распределения d, соответствующие хорошим страницам, устанавливаются равными 1. Шаг 4: нормализуется вектор d, так, чтобы сумма его составляющих ровнялась 1. Допуская, что L=3, множество случайных страниц {2, 4, 5}. 2 и 4 являются хорошими случайно выбранными страницами, мы получаем следующий вектор распределения статических оценок для нашего примера, d = [0, ½, 0, ½, 0, 0, 0]. Шаг 5: заключительный этап, подсчитывается TrustRank с использованием смещенных вычислений PageRank, где d заменяет равномерное распределение. Заметьте, что шаг 5 представляет определенную модель, когда доверие снижается и разделяется: в каждой итерации показатель доверия вершины распределяется между соседствующими и снижается по причине коэффициента затухания αВ. Допуская, что αВ = 0,85, МВ = 20, алгоритм показывает следующий результат: t* = [0, 0,18, 0,12, 0,15, 0,13, 0.,05, 0,05] Обратите внимание, что способ итерационного определения показателя доверия влияет на то, что хорошие, случайно выбранные страницы (2 и 4), не имеют больше показателя, равного 1.Однако, у них по-прежнему самые высокие показатели. Также следует отметить, что страница 4 имеет более низкий показатель, чем страница 2. Это связанно со структурой ссылок в данном примере: ссылки на страницу 2 сделаны со страницы с высоким показателем (страница 3), а на страницу 4 нет. Таким образом, алгоритм TrustRank «корректирует» первоначальные показатели, представленные функцией прогнозирования Oracle, представляя больше доказательств того, что по сравнению со страницей 4, страница 2 – хорошая. Если получится, можно нормализовать суммарный вектор, разделив все показатели на самый высокий (делая показатель страницы 2 равным 1), то данное действие не привнесет кардинальных изменений в порядок страниц. Из данного примера видно, что алгоритм TrustRank присваивает хорошим страницам более высокий показатель. В частности, три из четырех хороших страниц (2, 3 и 4) получили высокий показатель, а две из трех плохих страниц (страницы 6 и 7) получили низкий показатель. Однако, показатели страниц 1 и 5 были определены алгоритмом н