Работаем с 2009 года Более 450 успешных проектов Санкт-Петербург
8 (999) 849-91-09

Обнаружение кликового спама с помощью алгоритма пропагации, реализованного на двудольном графе

Синь Ли, Мин Чжанг, Ицюнь Лью, Шаопин Мэй, Юйцзянь Цзинь и Лиюн Ру Факультет информационных технологий университета Цзинхуа, Пекин, Китай.

Поиск необходимой информации с использованием систем информационного поиска стал неотъемлемой частью нашей повседневной жизни. Для подавляющего большинства поисковых машин, информация, поступающая от кликов, совершаемых пользователями на страницах органической выдачи, является важным фактором ранжирования цифровых документов. Как следствие этого, некоторые веб-сайты прибегают к мошенническим практикам с целью получения более высокого рейтинга, которые заключаются в увеличении объема кликов, приходящихся на их страницы; подобного рода технологии получили название «кликового спама». Основываясь на анализе особенностей мошеннических кликов, в настоящей работе мы предлагаем новый подход по автоматическому вычислению кликового спама, который включает в себя: 1) моделирование пользовательской сессии с тройной последовательностью, которая впервые, насколько нам известно, учитывает не только пользовательские действия, но также преследуемую ими цель и временной интервал между действиями; 2) использование алгоритма пропагации на двудольном графе сеанса-пользователя для поиска мошенников и обнаружения большего объема мошеннических сессий; и 3) использование алгоритма пропагации на двудольном графе сеанса-паттерна в задачах достижения большей точности и полноты при идентификации кликового спама. Результаты экспериментов, проведенных на китайской коммерческой поисковой системе с использованием реальных кликовых данных, которые содержали порядка 80 млн. кликов, совершаемых пользователями поиска за день, продемонстрировали, что 2.6% всех кликов были идентифицированы как спам с показателем точности достигающим 97%.

1. Введение

Системы информационного поиска играют важную роль в текущей сетевой среде, за последние годы став одним из основных каналов доступа пользователей интернета к различного рода информации. В ответ на вопрос, который пользователи адресуют поисковой системе, последняя может возвращать множество релевантных страниц. Поисковая машина ранжирует данные результаты по ряду факторов, которые служат определением их релевантности при построении ранга, включающие текстовую информацию [18], ссылочную структуру [20] и так далее. Согласно задачам Yahoo! Labs Learning to Rank Challenge на текущем этапе развития систем информационного поиска, при ранжировании учитываются сотни характеристик. Среди них, за последнее время наибольшее внимание уделялось учету кликовой информации и характеристикам релевантности. Joachims в работе [13] полагает, что кликовая информация может быть использована как характеристика обратной связи для определения релевантности страниц в органической выдаче. Кликовая модель (такая, как каскадная модель [5], CCM [7], DBM [4] и т.п.) применявшаяся в смежных работах показала, что информация пользовательских кликов играет важную роль в ранжировании поисковых результатов. Согласно исследованиям поведения пользователей на поиске [17], большинство из них обращают внимание только на первые результаты возвращенных системой ответов. Таким образом, очевидно, что в том случае, если интернет-сайт сможет получить более высокий рейтинг по сравнению со всеми остальными ресурсами, пользователи будут совершать на него переходы с куда большей частотой и, таким образом, увеличат его поисковый трафик. Как следствие этого, продвижение сайтов в поиске посредством применения технологии мошеннических кликов стало основным каналом для недобросовестных веб-мастеров, стремящихся увеличить пользовательский трафик и, соответственно, получить больших экономических выгод [6, 15, 24, 3]. Исследования мошеннических кликов демонстрируют нам, что для подачи запросов в поисковые системы и совершения автоматических переходов по URL-адресам применяются различного вида боты, которые не только отнимают у поисковиков большой объем мощностей, но и оказывают воздействие на ранжирование результатов органического поиска.

Все большее число научных исследований фокусирует свое внимание на задачах противодействия поисковому спаму. В работе [8] Gyongyi и др. предложили алгоритм доверия TrustRank, который способен в полуавтоматическом режиме сепарировать авторитетные, хорошие страницы от некачественных соседей по сети. Они начинают с отбора небольшого исходного множества авторитетных страниц, а далее, следуя по исходящим с них гиперссылкам, отыскивают прочие документы, которые с определенной степенью вероятности также могут являться хорошими. Полученные ими результаты показывают, что используя авторитетное исходное множество, состоящее менее чем из 200 сайтов, можно эффективно отфильтровывать существенную долю спама в поиске. В работе [16] Krishnan и др. вводят алгоритм недоверия Anti-Trust Rank. Аналогично методологии Trust Rank, они отбирают помеченную в мануальном режиме исходную выборку веб-страниц; эксперименты, проведенные на наборе данных WebGraph, показывают, что текущий подход эффективен в части детекции спам-документов с использованием в качестве отправной точки небольшую исходную выборку. В настоящее время, в поисковых системах учитывается информация о поведении пользователей поиска [1, 17], а значит, машины корректируют результаты органической выдачи в соответствии с реакциями их пользователей. Как следствие этого процесса, возникают новые обманные технологии, называемые «кликовым спамом» (click spam), которые используют анализ пользовательского поведения. В качестве типичного примера кликового спама можно привести «Гуглбомбинг» (Google Bombing), явление при котором в поиске злонамеренно увеличивается ранг документа по какому-либо запросу. В Таблице 1 приведено еще два примера кликового спама представляющие собой пользовательские сессии, которые были извлечены из реальных логов пользовательских кликов популярной китайской коммерческой поисковой системы.

IP-адрес пользователя Запрос Клик Кликнутый URL
211.143.91.98 9999pp.com 0  
211.143.91.98 9999pp.com 1 369ii.com
211.143.91.98 9999pp.com 1 369ii.com
211.143.91.98 9999pp.com 1 369ii.com
211.143.91.98 9999pp.com 1 369ii.com
211.143.91.98 9999pp.com 1 369ii.com
IP-адрес пользователя Запрос Клик Кликнутый URL
219.135.43.71 Китай 0  
219.135.43.71 Китай 1 zzyzzy.cn/html/322.html
219.135.43.71 Шанхай 0  
219.135.43.71 Шанхай 1 zzyzzy.cn/html/151.html
219.135.43.71 программное обеспечение 0  
219.135.43.71 программное обеспечение 1 zzyzzy.cn/html/188.html
219.135.43.71 саммит 0  
219.135.43.71 саммит 1 zzyzzy.cn/html/56.html
219.135.43.71 промышленность 0  
219.135.43.71 промышленность 1 zzyzzy.cn/html/220.html

Таблица 1. Два примера кликового спама (а) и (б)

В сессии, представленной в Таблице (а), после подачи поискового запроса, пользователь неоднократно кликает по определенному URL-адресу. В сессии, представленной в Таблице (б), пользователь отправляет различные поисковые запросы и неоднократно кликает по ряду интернет-страниц, относящихся к одному домену. Обе сессии способны увеличить рейтинг тех страниц, участвующих в поиске, по которым кликают пользователи, что улучшает видимость заданных сайтов, а, следовательно, манипулирует вероятностью того, что и другие пользователи совершат клики с поиска. Очевидно, кликовый спам не только подрывает основы справедливого ранжирования сайтов, но также и ухудшает взаимодействие с пользователем поиска. По этой причине, системы информационного поиска срочно нуждаются в технологиях определения кликового мошенничества. Кликовый спам является новым инструментом манипулирования алгоритмами ранжирования, использующим поведение пользователей таким образом, что становится трудно отличить нормальную пользовательскую реакцию от ненормальной. В настоящей работе мы предлагаем новый, автоматический подход по обнаружению кликового спама; текущая работа, насколько нам известно, на сегодняшней день является первым научным исследованием, в котором задействуются цель пользовательских действий, а также интервал между действиями в моделировании пользовательских сессий в задачах детекции кликового мошенничества. Предложенная методология демонстрирует не только результативность, но и эффективность при обнаружении кликового спама на реальной коммерческой системе информационного поиска. В указанном подходе используется следующая процедура: 1. Моделируется пользовательская сессия с тройной последовательностью; 2. Создается двудольный граф сеанса-пользователя и двудольный граф сеанса-паттерна в задачах описания взаимосвязи между пользователями и сессиями, а также между сессиями и паттернами; 3. На основании образцов режимов мошеннических сессий, вычисляется подавляющий объем кликового спама с использованием алгоритма пропагации меток на двудольном графе.

Оставшаяся часть работы организована следующим образом. После обсуждения смежных работ в следующем Разделе, в Разделе 3 мы рассказываем о детекции мошенничества на примере записи отдельного клика. Моделирование пользовательских сессий описывается в Разделе 4. Раздел 5 описывает распознание кликового спама на уровне сессий. В Разделе 6 дается оценка и описание нашего подхода и, наконец, в Разделе 7 подводятся итоги текущей работы.

2. Смежные работы

За последнее десятилетие наблюдается все возрастающий интерес к вычислению кликфрода. В работе [11] Jansen знакомит нас с преднамеренными кликами, совершаемыми по контекстным объявлениям с целью увеличения доходности рекламной площадки или скликивания рекламного объявления конкурента, которые получили название «кликфрод» (click fraud). Он также предлагает ряд контрмер, таких как усиление мониторинга за кликфродом, улучшение автоматических фильтров для идентификации и предотвращению данной мошеннической практики, а также переход от рекламной модели оплаты за клик (pay-per-click) на модель оплаты за действие (pay-per-action). В работе[3] Metwally и др. представляют три формы кликфрода, а также методы борьбы с ним. Они обнаружили, что некоторые веб-сайты могут кооперироваться с прочими ресурсами в задачах реализации технологии мошеннических кликов и, таким образом, для продвижения своих коммерческих интересов. Авторы работы разработали алгоритм, названный правило-стримингом, для сообщения ассоциативных правил со строгой гарантией на ошибки, используя ограниченную обработку каждого элемента и минимальное пространство, с целью идентификации кликфрода в системах показа контекстных объявлений. Приведенная выше работа напрямую связанна с детекцией кликфорда. Однако существует множество отличий между кликовым спамом в органическом поиске и практикой кликфорда, манипулирующего контекстной рекламой. Последний ставит своей целью увеличение количества кликов по демонстрируемым объявлениям таким образом, чтобы, например, увеличить доходность рекламной площадки, в то время как кликовый спам ориентирован на получение за счет большего числа кликов, приходящихся на веб-сайт, более высокого рейтинга в результатах поисковой выдачи. И в то время как детекция кликфорда требует от нас только изучение IP-адресов пользователей, с которых совершаются переходы по объявлениям, то идентификация кликового спама требует детального анализа логов пользовательских кликов системы информационного поиска. Следовательно, методологии, упомянутые нами выше, не могут напрямую применяться в нашей работе.

Radlinski [22] анализирует кликовый спам с точки зрения его полезности. Он обнаруживает, что кликовый спам играет значительную роль в ранжировании поисковых результатов, нанося вред системам информационного поиска. Он ищет вредоносный шум, разделяя популяцию пользователей на сегменты, и выдвигает предположение о том, что персонализация поисковых результатов может повысить устойчивость к кликовому спаму при использовании простого алгоритма ранжирования. Kang и др. [14] предлагают полуконтролируемый алгоритм обучения для разграничения программно-генерируемого веб-трафика (ботов) и истинных пользователей поиска. Для начала они используют технологию CAPTCHA для извлечения из данных пользовательских логов большого набора объектов-образцов, которые формируют обучающую выборку, а затем разрабатывают полуконтролируемый алгоритм обучения, использующего неразмеченные данные для улучшения производительности классификации. По их оценке, предложенная ими полуконтролируемая методология обучения значительно превосходит алгоритмы обучения с учителем.

Все эти исследования показывают, что анализ особенностей записей отдельных кликов способствует детекции кликового мошенничества. Прочие исследования фокусировались на распознании кликового спама на уровне сессий. В работе [23] Sadagopan и Li утверждают, что такое рассмотрение крайне важно для идентификации типичных и атипичных пользовательских сессий в потоке кликов. Они моделируют пользовательскую сессию с учетом последовательности совершаемых ими действий. Они классифицируют пользовательские действия по 5 категориям: запрос страницы, веб-клик, клик по рекламе, следующий клик и прочий клик. Далее они используют модель Марковской цепи для отображения пользовательских сессий и рассчитывают вероятности перехода как её оценки похожести. Низкая сессионная оценка указывает на большую вероятность того, что сессия является атипичной. Их результаты показывают, что предложенный подход может идентифицировать типичные и атипичные сессии с точностью, достигающей порядка 89%, а также то, что фильтрация атипичных сессий уменьшает неопределённость среднего значения CTR примерно на 40%.

Подводя итоги Раздела, связанного со смежными работами, можно отметить, что в области детекции кликового спама, подавляющее большинство исследований фокусировалось на обнаружении кликового мошенничества в записях отдельных пользовательских кликов, в то время как несколько работ было сосредоточено на распознании кликовых манипуляций на уровне сессий. Однако кликовый спам – это поведение на уровне пользователей. Например, в том случае, если пользовательская сессия определена как мошенническая, все действия данного пользователя, которые он совершил в рамках заданной сессии, должны также рассматриваться мошенническими. Следовательно, такое предположение является более существенным в деле идентификации кликового спама на уровне сессий. Наш подход фокусируется на распознании кликового мошенничества на уровне сессий и в этом схож с работой, проделанной Sadagopan и Li. Вместе с тем, при моделировании пользовательских сессий мы также принимаем во внимание информацию, касающуюся цели действия и временного интервала между самими действиями, а для дальнейшего обнаружения мошеннических сессий мы используем алгоритм пропагации на двудольном графе.

3. Детекция записей отдельных спам-кликов

Данные, использованные в нашей работе, состоят из реальных логов пользовательских кликов, извлеченных из популярной китайской коммерческой системы информационного поиска. В ежедневных логах пользовательских кликов содержатся порядка 80 млн. рандомно выбранных образцов записей с анонимными ID и временной информацией; поисковыми
запросами, типом клика, а также данными по тем URL-адресам, по которым был выполнен переход с поиска. Для нашего эксперимента мы выбрали логи пользовательских кликов за декабрь 2011 года, которые в общей сложности включали в себя 2.4 млрд. записей. В логе пользовательских кликов, тэг представляет тип клика. Например, тэг «изображение» указывает на то, что пользователь совершил клик на поиске по изображениям. Для нормальных пользователей, тэг клика должен согласовываться с его истинным действием. В случае обнаружения несоответствия, возможна идентификация кликового спама. Еще один пример: если тэгом является «видео», однако URL-адрес, по которому был совершен клик, следует из основных поисковых результатов, а не из результатов поиска по видео, это указывает на спам. В общей сложности наличествует 40130 различных тэгов из выборки логов за 1 день (2011.12.7), которые могут быть разбиты на 53 категории в соответствии с префиксом тэгов. Для 20 из имеющихся категорий тэгов, URL-адреса, по которым был совершен клик, имеют общие характеристики. Исходя из приведенного выше анализа, касающегося записей кликов, в том случае, если тэг отсутствует или URL-адрес, по которому был совершен клик, не совпадает с тэгом, мы полагаем, что данная кликовая запись относится к мошенничеству. С помощью указанной методологии, были выполнены эксперименты, результаты которых представлены в Таблице 2.

Тип клика #мошеннические клики #всего кликов Доля спама
— (отсутсвует тег) 285,449 285,449 100%
поисковые подсказки 32,348 3,330,407 0.97%
следующая страница 3,105 2,209,056 0.14%
определенная страница 21,909 2,068,008 1.06%
контекстная реклама 12,092 2,200,346 0.55%
Снапшот 22,514 520,956 4.32%
Видео 5,051 342,363 1.48%
Изображение 4,844 246,900 1.96%
левая колонка 9,957 122,421 8.13%
Музыка 4,841 113,434 4.27%
Новости 5,028 49,622 10.1%
Карты 9,737 33,917 28.7%
знания 7,128 33,440 21.3%
предыдущая страница 106 25,604 0.41%
форма поиска 2,452 11,075 22.1%
помощь 2,521 5,285 47.7%
Прочее 14,333 118,483 12.1%
Всего 443,415 11,716,766 3.78%

Таблица 2. Результаты обнаружения спама в записи отдельного клика

Как демонстрирует таблица, таким способом было обнаружено в общей сложности 443415 записей мошеннических кликов из 82113889 кликовых записей, что составляет 0.54% от всех записей кликов (за исключением перечисленных выше 11716766 записей, для которых данный метод оказался неприменим). Мы также повторили эксперимент еще для двух дней, и доля спама в 0.55% и 0.52% для второго и третьего дня соответственно, подтвердила стабильность нашего метода обнаружения. Детекция отдельных спам кликов отличается достаточной аккуратностью (со 100% показателем точности), однако таким способом можно обработать простейшие технологии спама. По этой причине он не может быть применим для выборки, позволяющей обнаруживать более сложные мошеннические клики в нашей модели (детали приведены в Разделе 5).

4. Моделирование пользовательских сессий

Основная идея нашей работы заключается в моделировании пользовательских сессий с последовательностью действий таким образом, чтобы мы могли идентифицировать спам на основании суждения о возможном соответствии пользовательской сессии аномальным режимам последовательностей. В предшествующих работах, в основном дается буквенное определение отдельного действия (например, в исследовании [23]) не принимающее во внимание временной интервал между действиями или семантические их значения (например, действием является обращение на поиск с запросом, аналогичным предыдущему, или с новым пользовательским запросом). Новшество нашей работы как раз и состоит в этих двух моментах. Следовательно, ключевыми моментами моделирования пользовательской сессии являются (1) определение действий с семантическими значениями и (2) использование в нашей модели времени в качестве одного из факторов.

4.1 Определения действия

Мы определяем пользовательскую сессию как взаимодействие между пользователем и поисковой системой в рамках 30 минут, начиная с первого пользовательского запроса, отправленного поисковой машине. Подобным методом в ежедневном логе пользовательских кликов может быть сгенерировано более чем 50 млн. пользовательских сессий. В ходе пользовательской сессии, после подачи пользователем своего вопроса, он может просматривать возвращенные страницы с результатами поиска, кликать по ссылкам на оригиналы веб-документов, переходить по вкладкам и так далее, или переформулировать свой вопрос и продолжить взаимодействие с системой информационного поиска. В нашей работе, мы определяем 6 видов пользовательских действий:

Следовательно, пользовательские действия можно разбить на 6 категорий. В отличие от более ранних исследовательских работ, мы назначаем различным запросам и кликам по различным гиперссылкам различные идентификаторы, которые способны разграничить цели пользовательских действий. Это представляется нам разумным постольку, поскольку действие можно рассмотреть с точки зрения нормального пользовательского поведения в том случае, если пользователь кликает по 10 различным веб-результатам после подачи какого-либо вопроса. Однако в том случае, если он кликает 10 раз по аналогичным результатам после подачи своего запроса, то это наводит на мысль о мошенничестве с его стороны. В более ранних исследовательских работах, 2 сессии моделировались по одинаковой последовательности действий. В тоже время, в нашей работе мы можем разграничить их в соответствии с идентификаторами действий.

4.2 Временной интервал

После того, как мы дали определения возможным действиям, совершаемых в ходе пользовательской сессии, давайте введем в нашу модель информацию о временном интервале между самими действиями. В пользовательской сессии должен наличествовать разумный временной интервал между действиями. Например, после того, как пользователь обратился на поиск со своим запросом, он затрачивает время на ознакомление со страницей поисковых результатов и только затем совершает прохождение по одной из предложенных ссылок, ведущих на оригинал веб-документа. Он также тратит свое время на ознакомление с посадочной страницей и только затем кликает по прочим результатам поиска. Как следствие этого, в том случае, если действия, совершаемые в ходе пользовательской сессии, отличаются чрезмерной частотой, то это, с большой долей вероятности, указывает нам исполнение пользовательской сессии ботом и пользователь оказывается под подозрением в мошенничестве. Следовательно, при моделировании пользовательских сессий крайне важно принять во внимание временной интервал между действиями. Однако в том случае, если мы используем значение временного интервала напрямую, данные окажутся слишком разрежёнными потому, что каждая секунда во временном интервале будет означать различное действие. Вместо этого, нам необходимо сегментировать временной интервал. Мы анализируем распределение временного интервала 6 действий (временной интервал действия является временным интервалом между текущим и предыдущим действием; в том случае, если это является первым действием пользовательской сессии, временной интервал равен 0), которое представлено на Рисунке 1.

Распределение временного интервала 6 действий

Рисунок 1. Распределение временного интервала 6 действий

Как продемонстрировано на Рисунке 1, распределения временного интервала 6 действий аналогичны, поэтому мы применяем схожую стратегию сегментации к указанным 6 действиям. Мы сегментируем временную шкалу на 4 части с нулевой точкой и двумя точками перегиба, соответствующих распределению временного интервала. Формально, пусть t будет значением временного интервала (в секундах), а T будет идентификатором сегмента, таким образом, когда:

Временной интервал

Опираясь на приведенный выше анализ, мы можем смоделировать пользовательские сессии со включением в них целей действия и временного интервала между действиями. Каждое событие в сессии мы представляем тройкой (S, i, T), где S ∈ {Q, W, O, N, T, A} представляет собой действие; i используется для разграничения различных целей действия; а T ∈ {0, 1, 2, 3} представляет собой временной интервал. Таким образом, каждая сессия может быть выражена тройной последовательностью, начинающейся с {Q0,0} постольку, поскольку каждая сессия начинается пользователем, адресующего вопрос системе информационного поиска без временного интервала. Ниже приведен пример смоделированной пользовательской сессии: (Q0,0), (T,1), (Q0,1), (Q0,0), (W2,1), (Q1,3), (Q1,1), (Q1,0), (W2,1), (T,2), (Q1,1), (Q1,0), (W2,1), (Q1,2), (Q1,0), (T,1). То есть, пользователь отправляется на поиск с запросом (Q0,0), вскоре прокручивает страницу (T,1), через некоторое время переподает тот же запрос (Q0,1), тотчас отправляет данный запрос снова (Q0,0) и, после небольшого временного интервала, кликает по третей ссылке из числа предложенных ему в органическом поиске (W2,1)…

5. Распознание кликового спама на уровне сессий

5.1 Детекция мошеннических сессий на основании вероятности перехода цепи Маркова

Для начала в качестве базисного эксперимента используем подход, предложенный в работе [23]. Основная идея, положенная в данный подход, заключается в том, что в рамках сессии, следующее событие в значительной степени зависит от предыдущего, что приводит к Модели Марковской Цепи пользовательских сессий. Пространство состояний Модели Марковской Цепи включает каждое действие, которое возникает в пользовательских сессиях. Вероятность перехода Pr(i,j) из состояния i в состояние j оценивается следующим образом:

Вероятность перехода состояний цепи Маркова

,где Qi,j является числом случаев, при которых за состоянием i следует состояние j, а Qi = ∑jQi,j. Тогда каждой пользовательской сессии можно присвоить вероятностную оценку путем перемножения вероятности отдельных состояний переходов в заданной сессии. Следовательно, сессия с высокой вероятностной оценкой может быть ассоциирована с нормальным поведением, в то время как сессия с низкой вероятностной оценкой может ассоциироваться с редким поведением. Поскольку вероятностная оценка получается путем перемножения вероятности отдельных переходов состояний, пользовательская сессия с более длинной последовательностью получит меньшую оценку. Во избежание подобного случая, они используют логарифм вероятностной оценки и нормализуют ее по длине сессионной последовательности с целью получения среднего Марковского Логарифмического Правдоподобия (Markovian LoglikeHood, MLHavg).Следовательно, низкая оценка MLHavg указывает на большую вероятность того, что сессия атипична. Таким образом, мошеннические сессии могут быть обнаружены по хвосту распределения оценок MLHavg. Мы используем подход Sadagopan и Li для тестирования смоделированных нами пользовательских сессий из лога кликовых данных за день (2011.12.7), которые включают более чем 50 млн. пользовательских сессий. Мы подсчитываем вероятность перехода между состояниями в пользовательских сессиях и вычисляем оценку MLHavg каждой сессии. Распределение оценок MLHavg продемонстрировано на Рисунке 2.

Распределение оценок MLHavg

Рисунок 2. Распределение оценок MLHavg

Из рисунка видно, что для 99.6% пользовательских сессий MLHavg ∈ (−4, 0] – мы можем рассматривать их как нормальные сессии. Обнаруженные пользовательские сессии с оценкой ниже чем -4 мы рассматриваем в качестве мошеннических. Оценка точности данного подхода и сравнение с нашими методологиями даются в Разделе 6.

5.2 Обнаружение образцов режимов мошеннических сессий

Основная идея нашей работы заключается в обнаружении небольшого набора образцов мошеннических сессий, и далее в распознании пользователей-мошенников и паттернов последовательностей с использованием алгоритма пропагации меток на двудольном графе сеанса-пользователя и двудольном графе сеанса-паттерна, который поможет нам вычислить большее число мошеннических сессий и улучшить значения точности и полноты нашего исследования. Для обнаружения образцов мошеннических сессий мы отыскиваем режимы, используемые этими сессиями в записях отдельных кликовых махинаций, описанных выше. Мы анализируем сессии, которые содержат подобные записи по той простой причине, что данные сессии с большей вероятностью могут являться мошенническими. Мы моделируем эти сессии с использованием методологии, описанной в Разделе 4, и отыскиваем общие для многих из них режимы. В общей сложности мы обнаружили 5 режимов мошеннических сессий и представили их регулярными выражениями; их характеристики описаны ниже:

Мы используем данные кликов, полученные за 1 день (2011.12.7), для оценки точности указанных режимов сессий. Мы моделируем пользовательские сессии и получаем сессии, которые соответствуют таким 5 режимам, как: в том случае, если длина сессионной последовательности, совпадающей с режимом, превышает 50% длины сессии (рассматриваются только те действия, временной интервал которых составляет 0 или 1), мы определяем заданную сессию как соответствующую мошенническому режиму. Здесь мы не учитываем действия, временной интервал которых составляет 2 или 3 по той простой причине, что мы полагаем, что действия в мошеннической сессии обычно совершаются с более коротким временным интервалом таким образом, что пользователь смог выполнить больше манипулятивных сессий на протяжении одинакового периода времени. Для каждого из 5 режимов, мы рандомно извлекли 100 сессий, соответствующих заданному режиму, в задачах мануального аннотирования и оценки точности. Количество и точность сессий продемонстрировано в Таблице 3.

Режим #сессия #клик %кликов Точность
(QAi)0−1* 11,981 143,214 0.226% 100.0%
(QiT)0−1* 3,964 36,964 0.058% 98.0%
(Qi)0−1* 17,258 14,956 0.024% 95.0%
Q(Wi)0−1* 2,069 36,097 0.057% 100.0%
Q(Ai)0−1* 4,079 82,843 0.130% 100.0%
всего 39,351 314,074 0.495% 98.6%

Таблица 3. Точность и соотношение кликов 5 образцов мошеннических режимов

В Таблице 3, первый столбец содержит мошеннические режимы, второй столбец — количество сессий, совпадающих с соответствующим режимом, третий столбец демонстрирует количество действий (запросов и кликов) в сессии; четвертый столбец — соотношение между действиями в сессиях и всеми действиями в логе кликов, собранных за 1 день; наконец, последний столбец отображает точность соответствующего режима. Глядя на таблицу, можно увидеть, что точность 5 мошеннических режимов достаточно высока (98.6%), поэтому обнаруженные 39351 сессии могут быть использованы в качестве образцов мошеннических сессий.

5.3 Алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя

Алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя (user-session bipartite graph), основывается на том предположении, что в случае, если некоторое число пользовательских сессий оказываются мошенническими, тогда все прочие сессии данного пользователя с большой долей вероятности должны считаться также манипулятивными. В соответствии с этим предположением, мы начинаем с образцов мошеннических сессий и, полагаясь на обманные сессии, отыскиваем пользователей-мошенников, а затем, на основании уже этих обнаруженных пользователей, отыскиваем большее число мошеннических сессий. Для того чтобы идентифицировать большое число мошеннических сессий, что позволит улучшить показатели точности и полноты нашей работы, мы повторяем указанную процедуру несколько раз. Для завершения данного процесса мы создаем отношения между пользователями и сессионными последовательностями. В системах информационного поиска пользователь может инициировать сессии с различными последовательностями, а различные пользователи могут создавать схожую сессионную последовательность. Их отношения формируют двудольный граф сеанса-пользователя, аналогичный представленному на Рисунке 3.

Двудольный граф сеанса-пользователя

Рисунок 3. Двудольный граф сеанса-пользователя

В данных логах пользовательских кликов одного дня наличествует порядка 40 млн. пользователей и 1 млн. сессионных последовательностей. Основываясь на указанном выше предположении и анализе, мы предлагаем алгоритм пропагации на двудольном графе сеанса-пользователя. Сперва, мы назначаем оценку каждой сессии. В частности, для сессий, совпадающих с мошенническими режимами, которые были идентифицированы ранее, мы присваиваем начальную оценку равную 1, а всем прочим сессиям присваиваем нулевую оценку. Далее мы обновляем оценку каждого пользователя с учетом средневзвешенных оценок сессий, которые он создает. Затем, мы обновляем оценку каждой сессии с учетом средневзвешенных оценок пользователей, создающих сессии, для завершения первой итерации нашего алгоритма. Этот процесс повторяется до тех пор, пока оценки сессий между двумя итерациями не начнут изменяться несущественно. Описание алгоритма продемонстрировано на изображении «Алгоритм 1», где wij является частотной характеристикой пользователя i, создающего сессию j.

Алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя

Алгоритм 1. Алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя

5.4 Алгоритм пропагации, реализованный на двудольном графе сеанса-паттерна

С помощью алгоритма пропагации, реализованного на двудольном графе сеанса-пользователя, мы получаем список пользователей, уличенных в манипуляции с кликами, а также мошеннические сессионные последовательности. Однако нашей целью является обнаружение всех мошеннических паттернов последовательностей таким образом, чтобы мы могли выявлять мошеннические сессии, совпадающие с указанными паттернами. Алгоритм пропагации, реализованный на двудольном графе сеанса-паттерна (pattern-session bipartite graph) основывается на том предположении, что в случае, если некоторое число пользовательских сессий, совпадающих с паттерном последовательности, оказываются мошенническими, тогда все прочие сессии, совпадающие с паттерном последовательности с большой долей вероятности должны считаться также манипулятивными. Основная идея алгоритма пропагации, реализованного на двудольном графе сеанса-пользователя, заключается в обнаружении частовстречающихся паттернов последовательностей, следующих из смоделированных пользовательских сессий, и в распространении мошеннической оценки сессионных образцов на двудольном графе сеанса-паттерна в соответствии с полученным списком мошеннических паттернов последовательностей.

Для начала, введем определение частовстречающихся паттернов последовательностей, данное в работе [2]. Набор элементов I = {i1, i2, …, ik} является множеством всех элементов. Последовательность α (ti ⊆ I) представляет собой упорядоченный перечень подмножеств элементов. Последовательность содержится в другой последовательности тогда, когда существуют такие целые числа i1 < i2 < … < in, что a1 ⊆ bi1, a2 ⊆ bi2, …, an ⊆ bin. С учетом базы данных последовательностей D = {s1, s2, …, sn}, саппортизация последовательности α определяется как число последовательности в D, содержащих α. В том случае, если саппортизация α оказывается большей, чем θ|D| (θ – предельно-допустимое пороговое значение), α называется частовстречающимся паттерном последовательности (frequent sequential pattern).

На протяжении многих лет было разработано достаточно широкое разнообразие алгоритмов обнаружения частовстречающихся паттернов последовательностей в очень крупных базах данных последовательностей, например FreeSpan [9], PrefixSpan [10, 21], CloSpan [25] и так далее. Мы используем подход PrefixSpan, предложенный в работе [10, 21] для майнинга частовстречающихся паттернов последовательностей из смоделированных пользовательских сессий. PrefixSpan работает по принципу «разделяй и властвуй». Полное множество паттернов последовательности разбивается на различные подмножества в соответствии с различными префиксами; создаются соответствующие прогнозируемые базы данных и рекурсивно майнятся частовстречающиеся паттерны последовательностей. На основании добытых частовстречающихся паттернов последовательностей мы создаем двудольный граф сеанса-паттерна. Поскольку каждый паттерн последовательности может соответствовать различным сессионным последовательностям, а каждая сессионная последовательность может соответствовать различным паттернам последовательности, их взаимосвязь формирует двудольный граф сеанса-паттерна. Здесь мы используем тот же алгоритм, что и на двудольном графе сеанса-пользователя, чтобы распространить мошеннические оценки образцов сессий и получить мошеннические паттерны последовательностей, как продемонстрировано на изображении «Алгоритм 2». В частовстречающихся паттернах последовательностей не требуется того, чтобы действия в сессии были непрерывными, что эффективно снижает воздействие шума. Высокая надежность алгоритма повышает показатели полноты детекции кликового спама.

Алгоритм пропагации, реализованный на двудольном графе сеанса-паттерна

Алгоритм 2. Алгоритм пропагации, реализованный на двудольном графе сеанса-паттерна

6. Оценки и обсуждения

6.1 Производительность алгоритма пропагации, реализованного на двудольном графе сеанса-пользователя

В наших экспериментах, выполненных на недельной выборке логов пользовательских кликов, содержащей порядка 80 млн. ежедневных записей кликов, мы используем алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя. Для начала мы оценим производительность алгоритма на логах пользовательских кликов за 2011.12.7. Каждая сессионная последовательность получает оценку после завершения итерации нашего алгоритма. Очевидно, что оценка каждой сессионной последовательности находится в диапазоне от 0 до 1. Мы подсчитываем количество и соотношение кликов по сессиям для различных оценочных диапазонов. Здесь, соотношение кликов в сессии определено как соотношение между количеством действий (запросов и кликов) за сессию на определенном оценочном диапазоне и количеством действий во всех сессиях. Соотношение кликов для различных оценочных диапазонов представлено на Рисунке 4.

 Соотношение кликов для различных оценочных диапазонов на один день с использованием алгоритма пропагации на двудольном графе сеанса-пользователя

Рисунок 4. Соотношение кликов для различных оценочных диапазонов на один день с использованием алгоритма пропагации на двудольном графе сеанса-пользователя

Из нашей методологии нам известно, что высокая оценка свидетельствует о высокой вероятности того, что сессия является мошеннической. Таким образом, для сессий с оценкой, оказывающейся больше, чем 0.5, мы случайным образом выбрали 200 сессий для их мануального аннотирования с целью оценки точности нашего алгоритма; результаты представлены в Таблице 4.

Диапазон #сессия #корректно Точность
(0.9,1] 59 57 0.966102
(0.8,0.9] 15 13 0.866667
(0.7,0.8] 22 19 0.863636
(0.6,0.7] 28 22 0.785714
(0.5,0.6] 76 55 0.723684
всего 200 166 0.83

Таблица 4. Точность для различных диапазонов оценок

Глядя на таблицу, можно заметить, что сессии в диапазоне с высокой оценкой оказываются мошенническими с более высокой точностью, что отвечает ожиданиям нашего эксперимента. Поскольку идентификация кликового спама требует высокой точности, мы рассматриваем сессии, попадающие в оценочный диапазон (0.9, 1], как мошеннические, что составляет 2.1% от всего числа запросов и кликов наблюдаемых во всех сессиях. Мы определяем соотношение кликов в сессиях, подпадающих в оценочный диапазон (0.9, 1], как соотношение спам-кликов. Мы также запустили аналогичный эксперимент на выборке данных, которая содержала 550 млн. записей кликов, собранных за неделю (2011.12.1 — 2011.12.7). Соотношения кликов для различных оценочных диапазонов с разбиением по дням продемонстрированы на Рисунке 5.

Соотношения кликов для различных оценочных 
	диапазонов с разбиением по дням с использованием алгоритма пропагации на двудольном графе сеанса-пользователя

Рисунок 5. Соотношения кликов для различных оценочных диапазонов с разбиением по дням с использованием алгоритма пропагации на двудольном графе сеанса-пользователя

Как показано на Рисунке 5, количество обнаруженных мошеннических сессий приходится в своем большинстве с понедельника по среду, нежели чем с Четверга по воскресенье. Возможно, это связано с тем, что пользователи-мошенники или компании по продвижению сайтов более активны в начале недели. Таким образом, мы предполагаем, что детекция кликового спама должна в большей степени концентрироваться на начале каждой недели.

6.2 Производительность алгоритма пропагации, реализованного на двудольном графе сеанса-паттерна

Для выбора конкретного предельно-допустимого порогового значения саппортизации θ в задачах майнинга частоповторяющихся паттернов последовательностей, мы используем интервал от 0.005 до 0.01, а также проверяем выборку данных пользовательских логов за один день, используя алгоритм пропагации на двудольном графе сеанса-паттерна, и рассчитаем соотношение спам-кликов. По результатам, полученным для каждого θ, мы случайным образом извлекаем 100 сессий, которые содержатся внутри оценочного диапазона (0.9, 1], с целью их мануального аннотирования для оценки точности нашего алгоритма. Соотношение спам-кликов и точность для каждого θ продемонстрированы в Таблице 5.

Пороговое значение саппортизации θ Соотношение спам-кликов Точность
0.01 0.026172068 97%
0.009 0.026976257 92%
0.008 0.027539188 93%
0.007 0.028182539 92%
0.006 0.028665052 91%
0.005 0.028986728 91%

Таблица 5. Соотношение спам-кликов и показатель точности для каждого θ

Результаты свидетельствуют о том, что с уменьшением θ соотношение спам-кликов возрастает, а показатель точности уменьшается. Для обеспечения точности детекции кликового спама, мы установим пороговое значение θ на 0.01. Соотношение кликов в различных диапазонах оценки представлено на Рисунке 6.

Соотношение кликов в различных оценочных диапазонах с использованием алгоритма пропагации на двудольном графе сеанса-паттерна

Рисунок 6. Соотношение кликов в различных оценочных диапазонах с использованием алгоритма пропагации на двудольном графе сеанса-паттерна

Рисунок демонстрирует нам, что соотношение спам-кликов достигает 2.6%, что несколько выше, чем 2.1% в случае применения алгоритма пропагации только на двудольном графе сеанса-пользователя, тем самым подтверждая высокую надежность методологии пропагации, реализованной на двудольном графе сеанса-паттерна.

6.3 Сравнение трех методологий

Мы сравниваем производительность нашего алгоритма с традиционным подходом по вычислению кликового спама, предложенного в [23]. В случае базисного подхода мы рассматриваем потенциально мошеннические сессии с показателями ниже, чем -4, а также случайным образом выбираем 100 сессий для оценки показателя точности. Соотношение спам-кликов и точность всех трех методологий представлены в Таблице 6.

Методология Соотношение спам-кликов Точность
Базисный подход [23] 1.7% 90%
Алгоритм пропагации, реализованный на двудольном графе сеанса-пользователя 2.1% 97%
Алгоритм пропагации, реализованный на двудольном графе сеанса-паттерна 2.6% 97%

Таблица 6. Сравнение трех подходов

Данные таблицы показывают, что наши подходы превосходят базисную методологию как по показателю точности, так и полноты. Сохраняя высокий показатель точности, алгоритм пропагации, реализованной на двудольном графе сеанса-паттерна, позволяет идентифицировать больший объем мошеннических сессий, чем алгоритм пропагации, реализованной на двудольном графе сеанса-пользователя.

6.4 Воздействие кликового спама на результаты органического поиска

NDCG (normalized discounted cumulative gain, [12]) является важной метрикой для оценки релевантности результатов алгоритмического поиска. NDCG в точке p(NDCG@p) рассчитывается как:

NDCG

,где reli является мануальной меткой i-го документа, а IDCG@p представляет собой идеальное значением DCG, полученное при сортировке документов по релевантности. Формула указывает на то, что релевантность высокоранжируемых результатов более важна, нежели чем низкоранжируемых. Например, в том случае, если низкорелевантный результат ранжируется высоко, значение NDCG станет относительно небольшим, а результаты ранжирования менее удовлетворительными. Мы отфильтровываем идентифицированные мошеннические сессии и используем метрику NDCG для оценки изменений. Мы извлекли из однодневной выборки логов пользовательские запросы для которых количество кликов составляла более чем 1000, а соотношение спам-кликов превышало 10%. Эти запросы содержат большое число записей спам-кликов, и мы бы хотели проверить, действительно ли наш подход по вычислению кликового спама поможет поисковым системам улучшить качество их поиска. Для каждого запроса мы отранжировали URL-адреса по CTR до и после фильтрации мошеннических сессий. Здесь CTR рассчитывается следующим образом:

CTR

Поскольку обнаруженные мошеннических сессий содержат большое количество кликов, приходящиеся на определенные результаты, они будут ранжироваться ниже после соответствующей фильтрации манипулятивных сессий. Мы помечаем ТОП 20 URL-адресов для каждого поискового запроса в соответствии с их релевантностью и рассчитываем значение NDCG. Мы сравниваем средние nDCG@5, nDCG@10 и nDCG@20 запросов, представляя полученные результаты на Рисунке 7.

Сравнение nDCG до и после фильтрации мошеннических сессий

Рисунок 7. Сравнение nDCG до и после фильтрации мошеннических сессий

Рисунок демонстрирует нам, что после выполнения процедуры фильтрации мошеннических сессий, наблюдается большее увеличение nDCG@5, чем nDCG@10 и nDCG@20. Подобный результат свидетельствует о том, что идентифицированные спамеры, занимавшиеся накруткой кликов, стремились продвинуть свои веб-сайты на максимально высокие позиции (≤5) в органической выдаче.

7. Выводы

Предыдущие исследования показали, что кликовый спам оказывает большое воздействие на производительность систем информационного поиска. В текущем исследовании мы предложили новый автоматический подход по обнаружению кликового спама на уровне сессий. В начале, мы смоделировали пользовательскую сессию с тройной последовательностью, учитывающей цели действия и временной интервал между действиями. Затем, мы сконструировали двудольный граф сеанса-пользователя и двудольный граф сеанса-паттерна в задачах описания их взаимосвязей. Наконец, на основании обнаруженных образцов мошеннических сессий, мы распространили мошеннические оценки на двудольном графе и улучшили точность и полноту нашей работы. Методологии, которые мы предложили, имеют лучшую производительность, чем традиционные методы детекции кликового спама на уровне сессий; наш алгоритм может идентифицировать в качестве спама 2.6% всех запросов и кликов при показателе точности в 97%. После фильтрации обнаруженных мошеннических сессий, значение nDCG результатов алгоритмической выдачи увеличилось, что свидетельствует об улучшении качества поиска.

Ссылки

[1] E. Agichtein, E. Brill, and S. Dumais. Improving web search ranking by incorporating user behavior information. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 19–26. ACM, 2006.

[2] R. Agrawal and R. Srikant. Mining sequential patterns. In Data Engineering, 1995. Proceedings of the Eleventh International Conference on, pages 3–14. IEEE, 1995.

[3] L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. A. Baeza-Yates. Link-based characterization and detection of web spam. In AIRWeb, pages 1–8, 2006.

[4] O. Chapelle and Y. Zhang. A dynamic bayesian network click model for web search ranking. In Proceedings of the 18th international conference on World wide web, pages 1–10. ACM, 2009.

[5] N. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position-bias models. In Proceedings of the 2008 International Conference on Web Search and Data Mining, pages 87–94. ACM, 2008.

[6] G. Gu, R. Perdisci, J. Zhang, W. Lee, et al. Botminer: Clustering analysis of network traffic for protocol-and structure-independent botnet detection. In USENIX Security Symposium, pages 139–154, 2008.

[7] F. Guo, C. Liu, A. Kannan, T. Minka, M. Taylor, Y.-M. Wang, and C. Faloutsos. Click chain model in web search. In Proceedings of the 18th international conference on World wide web, pages 11–20. ACM, 2009.

[8] Z. Gyongyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pages 576–587. VLDB Endowment, 2004.

[9] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.-C. Hsu. Freespan: frequent pattern-projected sequential pattern mining. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 355–359. ACM, 2000.

[10] J. Han, J. Pei, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In proceedings of the 17th international conference on data engineering, pages 215–224, 2001.

[11] B. J. Jansen. Click fraud. Computer, 40(7):85–86, 2007.

[12] K. Jarvelin and J. Kekalainen. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4):422–446, 2002.

[13] T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 133–142. ACM, 2002.

[14] H. Kang, K. Wang, D. Soukal, F. Behr, and Z. Zheng. Large-scale bot detection for search engines. In Proceedings of the 19th international conference on World wide web, pages 501–510. ACM, 2010.

[15] A. Karasaridis, B. Rexroad, and D. Hoeflin. Wide-scale botnet detection and characterization. In Proceedings of the first conference on First Workshop on Hot Topics in Understanding Botnets, volume 7. Cambridge, MA, 2007.

[16] V. Krishnan and R. Raj. Web spam detection with anti-trust rank. In AIRWeb, volume 6, pages 37–40, 2006.

[17] Y. Liu, F. Chen, W. Kong, H. Yu, M. Zhang, S. Ma, L. Ru. Identifying Web Spam with the Wisdom of the Crowds. ACM Transaction on the Web. Volume 6, Issue 1, Article No. 2, 30 pages. March 2012.

[18] M. Marchiori. The quest for correct information on the web: Hyper search engines. Computer Networks and ISDN Systems, 29(8):1225–1235, 1997.

[19] A. Metwally, D. Agrawal, and A. E. Abbadi. Using association rules for fraud detection in web advertising networks. In Proceedings of the 31st international conference on Very large data bases, pages 169–180. VLDB Endowment, 2005.

[20] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: bringing order to the web. 1999.

[21] J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. Mining sequential patterns by pattern-growth: The prefixspan approach. Knowledge and Data Engineering, IEEE Transactions on, 16(11):1424–1440, 2004.

[22] F. Radlinski. Addressing malicious noise in clickthrough data. In Learning to Rank for Information Retrieval Workshop at SIGIR, volume 2007, 2007.

[23] N. Sadagopan and J. Li. Characterizing typical and atypical user sessions in clickstreams. In Proceedings of the 17th international conference on World Wide Web, pages 885–894. ACM, 2008.

[24] T. Schluessler, S. Goglin, and E. Johnson. Is a bot at the controls?: Detecting input data attacks. In Proceedings of the 6th ACM SIGCOMM workshop on Network and system support for games, pages 1–6. ACM, 2007.

[25] X. Yan, J. Han, and R. Afshar. Clospan: Mining closed sequential patterns in large datasets. In Proc. 2003 SIAM Intarl Conf. Data Mining (SDMar03), pages 166–177, 2003.

Перевод материала «Search Engine Click Spam Detection Based on Bipartite Graph Propagation» выполнил Константин Скоморохов

Полезная информация по продвижению сайтов:

Перейти ко всей информации