автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка методов построения программных средств обнаружения текстового спама

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

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

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

спама

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 2 ЯНВ 2012

Москва - 2012

005006974

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

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

МГУ имени М.В. Ломоносова Добров Борис Викторович

Официальные оппоненты: д. ф.-м. н., с.н.с. Вычислительного цен-

тра РАН

Воронцов Константин Вячеславович

к. т. н., с.н.с. Института математики и компьютерных наук УрФУ Браславский Павел Исаакович

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

РАН

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

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

Автореферат разослан «22» ^ufisf,^ 2011_ г.

Ученый секретарь

диссертационного совета ^ic^f^] Трифонов Н.П.

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

Актуальность работы

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

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

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

Важными для развития информационно-поисковых систем стали работы Т. Митчела, В.Н. Вапника, А.Я. Червоненкиса, Р. Дуда, П. Харта по тео-

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

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

По мере развития сети Интернет стали возникать первые поисковые машины. Важной особенностью задач поиска по сети Интернет стало то, что поиск происходит по открытой коллекции документов, в которую могут попадать документы, содержащие недостоверную информацию. Впервые поисковые системы столкнулись с проблемой поискового спама в середине 90-х годов, что послужило толчком к нучным исследованиям в данной области. В основе многих методов обнаружения поискового спама лежат статистические подходы, разработанные для обнаружения спама в электронной почте. Методы обнаружения спама в электронной почте были исследованы в работах А.Н. Розинкина, И.В. Машечкина, Г. Робинсона, X. Карераса. С 2000-х годов ведутся активные исследования в области систем обнаружения поискового спама, новые методы борьбы с поисковым спамом предложены в работах К.В. Николаева, Р.В. Шарапова, JI. Бечетти, А. Бенцзура, Д. Феттерли. Непосредственно методы обнаружения текстового спама описаны в работах A.M. Райгородского, И. Биро, А. Нтуласа.

Текстовый спам существенно затрудняет решение задачи поиска необхо-

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

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

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

Цель диссертационной работы

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

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

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

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

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

Научная новизна

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

Практическая значимость

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

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

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

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

• на седьмом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (ЗУБ-СоБВ) (2011 г,);

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

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

Публикации

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

Личный вклад автора

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

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и библиографии. Общий объем диссертации 133 страницы. Библиография включает 62 наиме-

нований на 8 страницах.

Содержание работы

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

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

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

Второй раздел посвящен обзору методов обнаружения поискового спама

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

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

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

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

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

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

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

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

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

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

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

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

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

}d_ \{w : w Е d,w Е ©¿}|

И

(1)

EdsDiempl И

(2)

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

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

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

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

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

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

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

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

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

Еще один эксперимент проводился на стандартном наборе веб-страниц

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

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

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

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

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

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

Публикации в изданиях из списка ВАК

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

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

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

Прочие публикации

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

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

6. Павлов A.C. Добров Б.В. Метод определения массово порождаемых неестественных текстов // Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной Международной конференции «Диалог». 2010. Т. 9(16). С. 368-374.

7. Павлов А.С. . Методы обнаружения массово порождаемых неестественных текстов на основе анализа тематической структуры текстов // Тр. XIII Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции". 2011. Т. 1. С. 179-184.

8. Pavlov A.S., Dobrov B.V. Detecting Content Spam on the Web through Text Diversity Analysis // Proceedings of The Seventh Spring Researchers Colloquium on Databases and Information Systems, SYRCoDIS. 2011. Pp. 11-18.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия HAN 00510 от 01.12.99 г. Подписано к печати 23.12.2011 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 581. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.

61 12-1/450

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

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

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

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

спама

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

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель к. ф.-м. н.

Добров Борис Викторович

Москва - 2011

Содержание

Введение ......................................................................6

Глава 1. Анализ предметной области................11

1.1. Разновидности поискового спама .................11

1.1.1. Текстовый спам.......................12

1.1.1.1. Генераторы текстов на основе цепей Маркова 14

1.1.2. Ссылочный спам......................16

1.1.3. Техники маскировки поискового спама..........18

1.2. Методы обнаружения поискового спама..............20

1.2.1. Критерии оценки качества алгоритмов обнаружения поискового спама.......................21

1.2.1.1. Коллекция веб-страниц ШеЬвратиК.....24

1.2.2. Алгоритмы классификации................25

1.2.2.1. Алгоритм построения деревьев решений С4.5 26

1.2.2.2. Метод опорных векторов............28

1.2.2.3. Методы построения ансамбля классификаторов ........................31

1.2.3. Методы обнаружения текстового спама .........32

1.2.3.1. Алгоритм обнаружения текстового спама на основе эвристик.................32

1.2.3.2. Метод на основе анализа тематик текста, моделируемых с помощью скрытого распределения Дирихле..................35

1.2.3.3. Алгоритм на основе обнаружения редких пар слов........................40

1.2.4. Методы обнаружения ссылочного спама.........42

1.2.4.1. Алгоритм Тп^гапк...............42

1.2.4.2. Алгоритм обнаружения ссылочных ферм . . 43

1.2.4.3. Алгоритм на основе комбинации ссылочных признаков ....................45

1.2.5. Методы обнаружения дубликатов.............47

1.2.6. Комбинированные методы обнаружения поискового спа-

ма...............................49

1.2.6.1. Методы на основе объединения текстовых и ссылочных признаков..............49

1.2.6.2. Алгоритм обнаружения продажных ссылок . 50 1.3. Выводы к первой главе.......................52

Глава 2. Алгоритм обнаружения текстового спама на основе оценки разнообразия тематик документа.............54

2.1. Модель массово порождаемых неестественных текстов.....54

2.1.1. Обзор методов порождения неестественных текстов . . 56

2.1.1.1. Модель мешок слов...............56

2.1.1.2. Генераторы на основе цепей Маркова.....56

2.1.1.3. Метод на основе фрагментов текстов.....58

2.1.1.4. Обобщенная модель генератора текстов на основе образцов.................59

2.1.2. Тематическая структура текстов.............66

2.1.3. Свойства тематической структуры порожденных текстов 67

2.2. Метод обнаружения неестественных текстов...........68

2.2.1. Моделирование тематик с помощью модели скрытое распределение Дирихле (СРД) ..............68

2.2.2. Критерии обнаружения неестественных текстов.....69

2.2.2.1. Нарушение тематической структуры текстов 69

2.2.2.2, Критерий Пирсона...............71

2.2.2.3. Закон Ципфа для тематической структуры . 73 2.3. Выводы ко второй главе ......................74

Глава 3. Комбинированный алгоритм обнаружения тексотвого спама....................................76

3.1. Метод на основе трудноконтролируемых характеристик текстов 76

3.1.1. Характеристики читаемости текста............78

3.1.2. Особенности жанра и авторского стиля .........79

3.1.3. Глобальные статистические характеристики текстов . . 82

3.1.4. Характеристики тематического разнообразия текстов . 85

3.2. Метод машинного обучения на основе деревьев решений .... 87

3.2.1. Построение базового классификатора ..........88

3.2.2. Построение ансамбля классификаторов .........89

3.3. Выводы к третьей главе.......................91

Глава 4. Программная система классификации поискового спама ......................................92

4.1. Архитектура системы обнаружения поискового спама......92

4.1.1. Сценарии использования системы.............93

4.1.2. Основные модули системы.................94

4.2. Экспериментальная оценка предложенного решения ......100

4.2.1. Численное подтверждение модели массово порождаемых неестественных текстов................100

4.2.1.1. Методология исследования...........101

4.2.1.2. Зависимость скорости сходимости от количества документов образцов............102

4.2.1.3. Зависимость скорости сходимости от количества слов в документе .............103

4.2.1.4. Применимость критериев для различных генераторов на основе цепей Маркова......104

4.2.2. Эксперименты на модельных данных...........108

4.2.2.1. Эксперимент по обнаружению текстов, порожденных различными генераторами дорвеев . . 109

4.2.2.2. Сравнение методов машинного обучения . . . 110

4.2.2.3. Анализ качества предлагаемых характеристик 113

4.2.2.4. Устойчивость алгоритма обнаружения поискового спама...................114

4.2.2.5. Применимость алгоритма для различных языков ........................116

4.2.3. Апробация предложенного решения на реальных данных 117

4.2.3.1. Эксперимент по обнаружению спама в блогах 118

4.2.3.2. Эксперимент по обнаружению поискового спама на коллекции WebspamUK-2007 ...... 120

4.2.3.3. Сравнение эффективности предложенного решения с существующими аналогами .....121

4.3. Выводы к четвертой главе.....................124

Заключение..................................125

Литература..................................126

Введение

Актуальность работы

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

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

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

Важными для развития информационно-поисковых систем стали работы Т. Митчела, В.Н. Вапника, А.Я. Червоненкиса, Р. Дуда, П. Харта по теории

машинного обучения, именно благодаря их работам появились современные поисковые системы, которые учитывают большое количество факторов при определении релевантности документов. Современные исследования в области машинного обучения представлены в работах К.В. Воронцова, М.С. Агеева, М.И. Кумскова, М.И. Петровского, А. Нг, И. Фреунда, Р. Шапире, Р. Квинлена.

По мере развития сети Интернет стали возникать первые поисковые машины. Важной особенностью задач поиска по сети Интернет стало то, что поиск происходит по открытой коллекции документов, в которую могут попадать документы, содержащие недостоверную информацию. Именно открытость сети Интернет привела к возникновению поискового спама. Впервые поисковые системы столкнулись с проблемой поискового спама в середине 90-х годов, в следствие чего началось развитие методов обнаружения поискового спама. В основе многих методов обнаружения поискового спама лежат статистические подходы, разработанные для обнаружения спама в электронной почте. Методы обнаружения спама в электронной почте были исследованы в работах А.Н. Розинкина, И.В. Машечкина, Г. Робинсона, X. Карераса. В 2000-х годах велись активные исследования в области систем обнаружения поискового спама, современные методы борьбы с поисковым спамом предложены в работах К.В.Николаева, Р.В. Шарапова, JI. Бечетти, А. Бенцзура, Д. Феттерли. Непосредственно методы обнаружения текстового спама описаны в работах A.M. Рай городского, И. Биро, А. Нтуласа.

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

машин.

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

Цель диссертационной работы

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

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

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

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

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

Научная новизна

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

Практическая значимость

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

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

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

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

• на седьмом весеннем коллоквиуме молодых исследователей в области

баз данных и информационных систем (ЗУКСоБШ) (2011 г.);

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

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

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

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

Глава 1

Анализ предметной области

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

1.1. Разновидности поискового спама

Поисковые машины - это один из основных источников информации в сети Интернет. Задача поисковой машины - по каждому пользовательскому запросу отранжировать страницы, находящиеся в ее индексе по релевантности. Релевантность - это мера соответствия страницы запросу.

Манипуляции, направленные на незаслуженное повышение оценки релевантности страницы в поисковой системе, называются поисковым спамом. Приблизительно 10 — 20% всего содержимого сети Интернет составляет поисковый спам [26], в некоторых доменных зонах этот уровень может достигать 70% [55].

В настоящее время во всех ведущих поисковых системах уровень спама в первой десятке результатов составляет около 5%, то есть в среднем каждый второй запрос содержит один спамерский документ. Поисковый спам признан одной из основных угроз для существующих поисковых систем [48] и существенно влияет на качество поиска [51].

Различные техники, применяемые в поисковом спаме, можно разделить

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

Существует несколько типов поискового спама. Текстовый спам (content spam) нацелен на повышение оценки релевантности страницы за счет манипуляции с ее текстом и содержимым. Ссылочный спам (link spam) нацелен на создание такой структуры ссылок вокруг страницы, при которой она ранжируется выше. Техники имитации поведения пользователей нацелены на дискредитацию алгоритмов ранжирования по пользовательским характеристикам. Также к поисковому спаму относят многочисленные техники, которые скрывают признаки поискового спама на странице и затрудняют его обнаружение.

1.1.1. Текстовый спам

Большинство алгоритмов ранжирования документов на основе их соответствия запросу опираются на предположение, что если слова запроса встречаются в тексте, то страница релевантна данному запросу. Примерами таких алгоритмов могут служить формулы на основе TF-IDF (от англ. term frequency, inverse document frequency). В основе TF-IDF положены следующие принципы: чем чаще слово из запроса встречается в тексте, тем с большей вероятностью текст релевантен запросу; чем чаще слово из запроса встречается во разных текстах, тем с меньшим весом это слово стоит учитывать при вычислении релевантности. Одним из наиболее распространенных вариантов TF-IDF является Okapi ВМ25 [59], широко применяемая в современных поисковых системах.

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

Существуют разнообразные техники порождения текстового спама [45]:

• Повторение слов запроса на странице. Повторяя одни и те же слова, спамеры увеличивают оценку релевантности данной страницы по запросу, содержащему эти слова,

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