Московский государственный университет имени М. В. Ломоносова

На правах рукописи

Павлов Антон Сергеевич

Исследование и разработка методов построения

программных средств обнаружения текстового

спама

05.13.11 – математическое и программное обеспечение вычислительных

машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

Москва – 2012

Работа выполнена на кафедре автоматизации систем вычислительных ком­ плексов факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: к. ф.-м. н., зав. лабораторией НИВЦ МГУ имени М.В. Ломоносова Добров Борис Викторович

Официальные оппоненты: д. ф.-м. н., с.н.с. Вычислительного цен­ тра РАН Воронцов Константин Вячеславович к. т. н., с.н.с. Института математики и компьютерных наук УрФУ Браславский Павел Исаакович

Ведущая организация: Институт системного программирования РАН

Защита состоится «17» февраля 2012 г. в 11 часов на заседании диссертаци­ онного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет вычислительной математики и кибер­ нетики, аудитория 685. Желающие присутствовать на заседании диссертаци­ онного совета должны сообщить об этом за 2 дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факульте­ та ВМК МГУ http://cs.msu.ru/ в разделе «Наука» – «Работа диссертацион­ ных советов» – «Д 501.001.44».

Автореферат разослан « » 201 г.

Ученый секретарь диссертационного совета Трифонов Н.П.

Общая характеристика работы

Актуальность работы В настоящее время поисковые машины стали одним из основных источ­ ников информации в сети Интернет. Задача поисковой машины – по каждому пользовательскому запросу отранжировать страницы, находящиеся в ее ин­ дексе по релевантности. Релевантность – это мера соответствия страницы запросу. Манипуляции, направленные на незаслуженное повышение оценки релевантности страницы в поисковой системе, называются поисковым спа­ мом. Текстовый спам – это разновидность поискового спама, связанная с ма­ нипуляциями с текстами страниц.

Настоящая работа посвящена исследованию и разработке методов по­ строения программных средств обнаружения текстового спама. Под тексто­ вым спамом в данной задаче понимается массовое порождение неестествен­ ных текстов с помощью специализированных программ. Задача обнаружения такого спама заключается в определении, был ли текст написан человеком, или порожден автоматически с помощью программы.

С момента своего возникновения вычислительные комплексы использо­ вались для автоматической обработки текстов. В частности, известны рабо­ ты А.А.Ляпунова, С.Н.Разумовского, Л.Н. Королева, Н П.Трифонова по со­ зданию систем машинного перевода в середине 50-х годов прошлого века. В 60-х и 70-х годах стало активно развиваться направление информационного поиска, в частности стали возникать системы поиска научной информации, существенный вклад в развитие которых в это время внесли Г.Э. Влэдуц, Д.Г. Лахути, Э.Ф. Скороходько, Б. Викери, Д. Фоскет, Дж. Перри, А. Кент, Дж. Костелло.

Важными для развития информационно-поисковых систем стали рабо­ ты Т. Митчела, В.Н. Вапника, А.Я. Червоненкиса, Р. Дуда, П. Харта по тео­ рии машинного обучения, благодаря этим работам появились современные поисковые системы, которые учитывают большое количество факторов при определении релевантности документов. Современные исследования в обла­ сти машинного обучения для задач информационного поиска представлены в работах К.В. Воронцова, М.С. Агеева, М.И. Кумскова, М.И. Петровского, А. Нг, И. Фреунда, Р. Шапире, Р. Квинлена.

Одним из направлений, существенно повлиявших на методы обнаруже­ ния текстового спама, стало моделирование тематик естественных текстов.

В 80-е годы лингвистическая теория тематик текстов была разработана в ра­ ботах Т.А. ван Дейка и В. Кинча. Формальные модели тематик на основе тезаурусов и статистических методов обработки текстов были предложены в работах Н.В. Лукашевич, Т. Хоффмана, Д. Блея, Д. Вонга.

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

В основе многих методов обнаружения поискового спама лежат статистиче­ ские подходы, разработанные для обнаружения спама в электронной почте.

Методы обнаружения спама в электронной почте были исследованы в рабо­ тах А.Н. Розинкина, И.В. Машечкина, Г. Робинсона, Х. Карераса. С 2000-х годов ведутся активные исследования в области систем обнаружения поиско­ вого спама, новые методы борьбы с поисковым спамом предложены в рабо­ тах К.В. Николаева, Р.В. Шарапова, Л. Бечетти, А. Бенцзура, Д. Феттерли.

Непосредственно методы обнаружения текстового спама описаны в работах А.М. Райгородского, И. Биро, А. Нтуласа.

Текстовый спам существенно затрудняет решение задачи поиска необхо­ димой информации, так как пользователю приходится просматривать множе­ ство страниц, не содержащих полезной информации. Это приводит к тому, что либо пользователь поисковой системы вообще не находит интересующую информацию, либо тратит на ее поиск слишком много времени. В связи с этим текстовый спам является серьезной угрозой для развития поисковых машин.

Особенность рассматриваемой задачи заключается в том, что для ее эф­ фективного решения необходимо анализировать большое количество характе­ ристик текстов, которые трудно учесть в явном виде. Актуальным является применение методов машинного обучения, так как они позволяют строить эффективные программные системы, учитывающие такие неявные законо­ мерности.

Для рассматриваемых задач важно обрабатывать поступающие докумен­ ты максимально быстро, так как должно проходить минимальное время меж­ ду появлением документа и его попаданием на выдачу поисковой системы.

Разрабатываемая система должна работать в потоковом режиме, когда доку­ менты обрабатываются по мере их попадания в поисковую систему в течение нескольких секунд. Также разрабатываемые алгоритмы должны быть при­ менимы для различных естественных языков.

Цель диссертационной работы Целью диссертационной работы является разработка методов и программ­ ных средств обнаружения текстового спама. Разрабатываемые программные средства должны удовлетворять следующим требованиям: низкий уровень ошибок первого и второго рода при обнаружения текстового спама; обработка документов в потоковом режиме; применимость к различным естественным языкам.

Для достижения этой цели были поставлены следующие задачи:

1. разработка и исследование модели массово порожденных неестествен­ ных текстов;

2. разработка и исследование алгоритмов обнаружения текстового спама на основе машинного обучения;

3. разработка эффективного программного модуля классификации тексто­ вого спама на основе предложенных методов.

Научная новизна Новизна настоящей диссертационной работы заключается в том, что предложен новый метод обнаружения текстового спама на основе оценки раз­ нообразия тематик текстов. Применимость метода обоснована теоретически на основе разработанной модели массово-порождаемых неестественных тек­ стов и численно, для чего были проведены эксперименты. Разработанный метод может применяться в системах, где требуется потоковая обработка до­ кументов.

Практическая значимость На основе разработанных методов спроектирован и реализован программ­ ный модуль классификации текстового спама. Разработанный модуль может применяться в задачах обнаружения поискового спама, модерации Интернет­ ресурсов, фильтрации спама в электронной почте. Разработанные методы и подходы определения текстового спама могут также применяться для опре­ деления авторства документа и автоматической классификации документов по жанрам и стилям. Разработанный модуль был апробирован в системе об­ наружения поискового спама в поисковой системе Яндекс.

Апробация работы Основные результаты диссертации докладывались на следующих конфе­ ренциях и семинарах:

на одиннадцатой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллек­ ции"(2009 г.);

на международной конференции "Диалог 2010"(2010 г.);

на седьмом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2011 г.);

на тринадцатой Всероссийской научной конференции "Электронные биб­ лиотеки: перспективные методы и технологии, электронные коллекции".

Выступление автора удостоено диплома за лучший доклад, представ­ ленный на конференции (2011 г.);

Кроме того, результаты обсуждались на семинаре Лаборатории анализа информационных ресурсов НИВЦ МГУ и на аспирантском семинаре кафед­ ры АСВК факультета вычислительной математики и кибернетики МГУ.

Публикации Результаты работы опубликованы в 6 печатных работах, в том числе в статьях в журналах из списка ВАК РФ [2,3] и в 5 статьях в других изданиях [4-8]. Также результаты работы содержатся в статье в журнале из списка ВАК [1], которая находится в печати.

Личный вклад автора Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Большин­ ство теоретических и все практические результаты, представленные в публи­ кациях, получены лично автором.

Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения и библиографии.

Общий объем диссертации 133 страницы. Библиография включает 62 наиме­ нований на 8 страницах.

Содержание работы Во Введении обоснована актуальность диссертационной работы, сфор­ мулирована цель и аргументирована научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту научные положения.

Первая глава посвящена обзору разновидностей текстового спама. Так­ же в первой главе приводится обзор основных методов обнаружения тексто­ вого спама и методов машинного обучения, применяющихся в них. Целью данной главы является анализ достоинств и недостатков существующих ме­ тодов обнаружения текстового спама.

Первый раздел посвящен обзору разновидностей поискового спама. В настоящее время существуют следующие разновидности поискового спама:

текстовый спам, ссылочный спам, техники скрытия поискового спама. Ал­ горитмы текстового ранжирования опираются на предположение, что если слова запроса встречаются в тексте, то страница релевантна данному запро­ су. Техники текстового спама позволяют спамерам создавать страницы, реле­ вантные сразу множеству запросов, добавляя большое количество различных слов. Поисковые системы также используют информацию о ссылках меж­ ду страницами, чтобы выбрать наиболее релевантный результат. Ссылочный спам заключается в создании таких ссылочных структур, которые искажают метрики, посчитанные с помощью алгоритмов PageRank, HITS и им подоб­ ных. Техники скрытия поискового спама нацелены на активное противодей­ ствие системам обнаружения поискового спама, применяемым в поисковых системах.

Второй раздел посвящен обзору методов обнаружения поискового спама и методов машинного обучения, наиболее часто применяющихся в задачах классификации поискового спама. В начале раздела приводятся критерии сравнения качества алгоритмов. Существующие методы обнаружения тексто­ вого спама основываются на двух основных подходах: на обнаружении спама с помощью эвристик и обнаружение спама с помощью анализа тематики тек­ стов. Также в разделе проанализированы методы обнаружения ссылочного спама и комбинированные методы обнаружения поискового спама.

Анализ показывает, что ни один из опубликованных на данный момент алгоритмов не позволяет достаточно эффективно обнаруживать документы, порожденные с помощью генераторов неестественных текстов на основе об­ разцов. Алгоритмы на основе учета ссылочной структуры также непримени­ мы в случае, когда документы поступают в поисковую машину, в потоковом режиме, так как такие документы обычно не обладают входящими ссылками.

Таким образом, актуальным представляется разработка алгоритма и про­ граммной системы обнаружения поискового спама, удовлетворяющих следу­ ющим условиям:

Обнаружение поискового спама по содержимому документа;

Общее высокое качество обнаружения поискового спама различных ви­ дов спама, в том числе порожденных генераторами на основе докумен­ тов-образцов;

Высокая скорость проверки документов.

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

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

Определение. Пусть = {1,.., } - множество всех тематик, тогда вектор = (1,.., ) называется тематической структурой документа, если доля словопозиций принадлежащих тематике равно :

На основе свойств обобщенной модели генератора текстов доказывается теорема:

Теорема 1. Пусть - набор документов-образцов для генератора текстов, и задана тематическая структура каждого документа. Пусть на их основе обучен смешивающий генератор текстов, и с помощью него порождается документ длины. Тогда с ростом тематическая струк­ тура порожденного документа сходится по вероятности к усредненной тематической структуре документов-образцов:

Во втором разделе предлагается метод определения текстового спама на основе разработанной обобщенной модели генераторов текстов. Для модели­ рования тематической структуры предлагается использовать метод скрыто­ го распределения Дирихле (Latent Dirichlet Allocation), который позволяет эффективно оценивать тематическую структуру для произвольного текста.

Также на основании Теоремы 1 предлагается две характеристики примени­ мые для обнаружения текстового спама. Для каждой характеристики дока­ зывается, что для порожденного текста с ростом его длины и количества документов-образцов она стремится к нулю.

В третьей главе исследуются трудноконтролируемые автором текста особенности, которые могут применяться для обнаружения неестественных текстов, с целью построения эффективного классификатора неестественных текстов на основе этих характеристик. А также предлагается алгоритм ма­ шинного обучения для задачи обнаружения текстового спама.

Первый раздел посвящен характеристикам, применимым для обнаруже­ ния текстового спама. В основе разработанного подхода лежит наблюдение, что на настоящий момент не существует метода, который бы успешно воспро­ изводил все свойства естественных текстов. В данном разделе предлагаются характеристики текстов, которые трудно контролировать автору текста, и предположительно плохо воспроизводятся генераторами текстов. Предлага­ емые признаки относятся к четырем основным категориям: метрики читае­ мости текстов; характеристики жанра и стиля; глобальные статистические закономерности. Также используются характеристики тематического разно­ образия, предложенные во второй главе.

Второй раздел посвящен разработанному алгоритму машинного обуче­ ния. Данный метод является модификацией алгоритма построения деревьев решений C4.5. В разработанном алгоритме, чтобы минимизировать влияние переобучения, с помощью голосования классификаторов (bagging) и адаптив­ ной коррекции ошибок (boosting) строится ансамбль деревьев решений, каж­ дое их которых построено с помощью алгоритма C4.5.

Четвертая глава посвящена описанию программной реализации мето­ да обнаружения текстового спама, разработанного в главах 2 и 3. В первом разделе описывается архитектура разработанной системы. Система построе­ на по модульному принципу и поддерживает подключение дополнительных модулей выделения признаков в документах. В рамках системы был реализо­ ван модуль оценки разнообразия тематической структуры с помощью метода скрытого распределения Дирихле. Данный модуль позволяет оценивать тема­ тическое разнообразие документов со сложностью порядка длины документа, что особенно важно для обработки документов в режиме близком к реально­ му времени.

Также был реализован модуль обучения и классификации с использова­ нием метода, предложенного в главе 3. В целях ускорения процесса обучения была разработана специализированная версия этого алгоритма, поддержива­ ющая распараллеливание процесса обучения на многоядерных процессорах.

Второй раздел посвящен апробации разработанной системы на различ­ ных модельных и реальных данных. В первую очередь была показана приме­ нимость предложенного алгоритма для обнаружения генераторов спама на основе цепей Маркова. В ходе экспериментов система обнаруживала такие документы с низким уровнем ошибок. В ходе экспериментов было также по­ казано, что применение характеристик тематического разнообразия, предло­ женных во второй главе сокращает уровень ошибок первого и второго рода в два раза по сравнению с вариантом алгоритма только на основе трудно­ контролируемых характеристик. Были исследованы наиболее полезные для классификации текстового спама признаки.

Также в данном разделе поставлены новые эксперименты на реальных данных. В первом эксперименте была собрана коллекция из 2189 докумен­ тов с сайта livejournal.com, 587 из которых были определены экспертами как спам. Тестирование системы на данном наборе производилось по методике скользящего контроля, в результате чего система показала уровень ошибок первого рода 5,8% и уровень ошибок второго рода 1,5%.

Еще один эксперимент проводился на стандартном наборе веб-страниц WebspamUK-2007. Данный набор представляет собой слепок сайтов из домен­ ной зоны.uk (Великобритания), собранный за март 2007 года. Он состоит из 100 тысяч сайтов со всеми внутренними страницами. Результаты экспери­ мента на данном наборе показывают, что по качеству обнаружения спама разработанная система превосходит существующие решения и допускает на 11% меньше ошибок, чем ближайший существующий аналог.

В Заключении диссертационной работы перечисляются ее основные результаты:

1. Для решения задачи построения программных средств определения тек­ стового спама разработан новый алгоритм обнаружения текстового спа­ ма на основе оценки разнообразия тематик документа.

2. Теоретически и численно обоснована применимость разработанного ал­ горитма и программной системы для обнаружения текстового спама, порожденного генераторами текстов на основе цепей Маркова, широко используемыми для создания поискового спама.

3. Разработан комбинированный алгоритм классификации текстового спа­ ма на основе анализа большого числа факторов, моделирующих связ­ ность, стиль, читаемость текстов, а также учета результатов алгоритма оценки разнообразия тематик документа.

4. Реализована программная система определения поискового спама. По­ лучены более высокие характеристики классификации поискового спа­ ма на стандартном наборе данных, по сравнению с известными метода­ ми. Разработанная система позволяет обрабатывать документы в пото­ ковом режиме.

Публикации в изданиях из списка ВАК 1. Павлов А.С., Программная система обнаружения текстового спама // Вест­ ник ВГУ. Серия системный анализ и информационные технологии. (В пе­ чати).

2. Павлов А.С., Добров Б.В. Метод обнаружения массово порожденных неестественных текстов на основе анализа тематической структуры // Вы­ числительные методы и программирование: новые вычислительные тех­ нологии. 2011. Т. 12. С. 58–72.

3. Павлов А.С., Добров Б.В. Обнаружение поискового спама в Вебе на основе анализа разнообразия текстов // Труды Института системного программирования РАН. 2011. Том 21. С. 277–296.

Прочие публикации 4. Павлов А.С. Добров Б.В. Методы обнаружения поискового спама, по­ рожденного с помощью цепей Маркова // Тр. XI Всероссийской науч­ ной конференции “Электронные библиотеки: перспективные методы и технологии, электронные коллекции”. 2009. Т. 1. С. 311–317.

5. Павлов А.С. Исследование устойчивости метода обнаружения поиско­ вого спама на основе статистических характеристик // Программные системы и инструменты. Тематический сборник. 2009. Т. 10. С. 108–119.