Содержание к диссертации
Введение
Глава 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. Коллекция веб-страниц WebspamUK 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. Алгоритм Tгustrank 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-х годах стало активно развиваться направление информационного поиска, в частности стали возникать системы поиска научной информации, существенный вклад в развитие которых в это время внесли Г.Э. Влэдуц, Д.Г. Лахути, Э.Ф. Скороходько, Б. Викери, Д. Фоскет, Дж. Перри, А. Кент, Дж. Костелло.
Важными для развития информационно-поисковых систем стали работы Т. Митчела, В.Н. Вапника, А.Я. Червоненкиса, Р. Дуда, П. Харта по тео-
рип машинного обучения, благодаря этим работам появились современные поисковые системы, которые учитывают большое количество факторов при определении релевантности документов. Современные исследования в области машинного обучения для задач информационного поиска представлены в работах К.В. Воронцова, М.С. Агеева, М.И. Кумскова, М.И. Петровского, А. Нг, И. Фреунда, Р. Шапире, Р. Квинлена.
Одним из направлений, существенно повлиявших на методы обнаружения текстового спама, стало моделирование тематик естественных текстов. В 80-е годы лингвистическая теория тематик текстов была разработана в работах Т.А. ван Дейка и В. Кинча. Формальные модели тематик на основе тезаурусов и статистических методов обработки текстов были предложены в работах Н.В. Лукашевич, Т. Хоффмана, Д. Блея, Д. Вонга.
По мере развития сети Интернет стали возникать первые поисковые машины. Важной особенностью задач поиска по сети Интернет стало то, что поиск происходит по открытой коллекции документов, в которую могут попадать документы, содержащие недостоверную информацию. Впервые поисковые системы столкнулись с проблемой поискового спама в середине 90-х годов, что послужило толчком к нучным исследованиям в данной области. В основе многих методов обнаружения поискового спама лежат статистические подходы, разработанные для обнаружения спама в электронной почте. Методы обнаружения спама в электронной почте были исследованы в работах А.Н. Розинкина, И.В. Машечкина, Г. Робинсона, X. Карераса. С 2000-х годов ведутся активные исследования в области систем обнаружения поискового спама, новые методы борьбы с поисковым спамом предложены в работах К.В. Николаева, Р.В. Шарапова, Л. Бечетти, А. Бенцзура, Д. Феттерли. Непосредственно методы обнаружения текстового спама описаны в работах A.M. Райгородского, И. Биро, А. Нтуласа.
Текстовый спам существенно затрудняет решение задачи поиска необхо-
димой информации, так как пользователю приходится просматривать множество страниц, не содержащих полезной информации. Это приводит к тому, что либо пользователь поисковой системы вообще не находит интересующую информацию, либо тратит на ее поиск слишком много времени. В связи с этим текстовый спам является серьезной угрозой для развития поисковых машин.
Особенность рассматриваемой задачи заключается в том, что для ее эффективного решения необходимо анализировать большое количество характеристик текстов, которые трудно учесть в явном виде. Актуальным является применение методов машинного обучения, так как они позволяют строить эффективные программные системы, учитывающие такие неявные закономерности.
Для рассматриваемых задач важно обрабатывать поступающие документы максимально быстро, так как должно проходить минимальное время между появлением документа и его попаданием на выдачу поисковой системы. Разрабатываемая система должна работать в потоковом режиме, когда документы обрабатываются по мере их попадания в поисковую систему в течение нескольких секунд. Также разрабатываемые алгоритмы должны быть применимы для различных естественных языков.
Цель диссертационной работы
Целью диссертационной работы является разработка методов и программных средств обнаружения текстового спама. Разрабатываемые программные средства должны удовлетворять следующим требованиям: низкий уровень ошибок первого и второго рода при обнаружения текстового спама; обработка документов в потоковом режиме; применимость к различным естественным языкам.
Для достижения этой цели были поставлены следующие задачи:
разработка и исследование модели массово порожденных неестественных текстов;
разработка и исследование алгоритмов обнаружения текстового спама на основе машинного обучения;
разработка эффективного программного модуля классификации текстового спама на основе предложенных методов.
Научная новизна
Новизна настоящей диссертационной работы заключается в том, что предложен новый метод обнаружения текстового спама на основе оценки разнообразия тематик текстов. Применимость метода обоснована теоретически на основе разработанной модели массово-порождаемых неестественных текстов и численно, для чего были проведены эксперименты. Разработанный метод может применяться в системах, где требуется потоковая обработка документов.
Практическая значимость
На основе разработанных методов спроектирован и реализован программный модуль классификации текстового спама. Разработанный модуль может применяться в задачах обнаружения поискового спама, модерации Интернет-ресурсов, фильтрации спама в электронной почте. Разработанные методы и подходы определения текстового спама могут также применяться для определения авторства документа и автоматической классификации документов по жанрам и стилям. Разработанный модуль был апробирован в системе обнаружения поискового спама в поисковой системе Яндекс.
Апробация работы
Основные результаты диссертации докладывались на следующих конференциях и семинарах:
на одиннадцатой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции" (2009 г.);
на международной конференции "Диалог 2010"(2010 г.);
на седьмом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2011 г.);
на тринадцатой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции". Выступление автора удостоено диплома за лучший доклад, представленный на конференции (2011 г.);
Кроме того, результаты обсуждались на семинаре Лаборатории анализа информационных ресурсов НИВЦ МГУ и на аспирантском семинаре кафедры АСВК факультета вычислительной математики и кибернетики МГУ
Публикации
Результаты работы опубликованы в 6 печатных работах, в том числе в 2 статьях в журналах из списка ВАК РФ [2,3] и в 5 статьях в других изданиях [4-8]. Также результаты работы содержатся в статье в журнале из списка ВАК [1], которая находится в печати.
Личный вклад автора
Метод на основе анализа тематик текста, моделируемых с помощью скрытого распределения Дирихле
К поисковому спаму зачастую прибегают в случае, если легальная реклама некоторой продукции или сайта запрещена законом. Из-за этого поисковому спаму свойственны некоторые специфические тематики и эту информацию можно использовать для его обнаружения.
В работах [27, 28] предлагается алгоритм обнаружения поискового спама на основе анализа тематик текстов. Данный алгоритм основывается на статистическом методе Скрытое Распределение Дирихле (СРД, Latent Dirichlet Allocation), впервые описанном в работе [29].
Метод СРД представляет собой теоретическую модель того, как формируются тематики естественного текста. В рамках описания данной модели будем придерживаться следующих обозначений:
Слова - это базовые элементы, из которых состоят тексты. Каждое слово w представляет собой единичный вектор в некотором конечномерном пространстве. Размерность V пространства слов соответствует размеру словаря всех возможных слов. Элементы векторов будем обозначать верхними индексами, то есть v-ое слово это вектор в У-мерном пространстве, для которого WV = lHWU = 0,Uy V.
Документ й - это последовательность из Nj слов: d = (w\ w d).
Корпус документов D - это множество документов: D = {di ім} Тематика t - это вектор на симплексе в пространстве слов: : = (t1 tv), Y t1 = 1. Вероятность порождения слова w в тематике равна скалярному произведению этих двух векторов: p(w\t) = (w,t))
Т - это конечное множество всех возможных тематик: Т — \t\- #}. Множеству Т соответствует матрица /3 размерности KxV:U = /ЗІ.
В основе порождающей модели лежат следующие предположения:
Тематика определяет, в какой пропорции порождаются различные слова из словаря;
Каждое слово порождается одной тематикой;
Каждый документ принадлежит смеси нескольких тематик с разными весами;
Каждое слово порождается независимо от других слов в документе;
В рамках данной модели предлагается следующий алгоритм порождения произвольного документа d:
1. Выбирается длина порождаемого документа А ;
2. На основе if-мерного распределения Дирихле выбирается смесь тематик для документа d: 0d irichlet{a);
3. Для каждого из Л/d слов wn:
а. На основе мультиномиального распределения выбирается номер тематики, которая порождает слово: zn Mult(9d);
б. На основе мультиномиального распределения выбирается порождаемое слово с учетом тематики: wn Mult((3Zn)
Описанный алгоритм позволяет вычислять вероятность порождения произвольного документа или произвольного корпуса документов, если заданы параметры распределения Дирихле по тематикам а и матрица тематик /3. Пусть для документа d задана смесь тематик в и номера тематик для каждого слова Z = (z\ ZNd), тогда аожно оосчитать ьероятность ьорождения этого документа:
Используя формулу (1.14), перемножая по всем возможным Z и интегрируя по всем возможным в, можно также вычислить вероятность порождения корпуса документов:
Вектор параметров а - это фиксированный параметр модели. Он определяет смесь тематик, из которых порождаются документы, например, если а = (1 ), тт оаспределение Дирихле еудет торождать ьавномерныы емеси тематик. На практике применяются значения элементов О щ 1, так как в этом случае распределение Дирихле будет чаще порождать распределения, в которых присутствует одна главная тематика и несколько второстепенных с меньшими весами. Такой выбор параметров соответствует интуитивным представлениям о тематиках документов.
Модель СРД применяют для того чтобы восстановить по корпусу документов D тематики, которые наилучшим образом удовлетворяют порождающей модели, в предположении, что корпус был порожден согласно СРД. Для этого необходимо получить матрицу (3, которая яы максимизиирвалл аероятность порождения корпуса документов;
Посчитанные таким образом тематики могут использоваться для того чтобы восстановить смесь тематик, которая лучше всего соответствует произвольному документу d:
Для вычисления матрицы тематик по корпусу документов и смеси тематик для произвольного документа используются итерационные алгоритмы, вычисляющие приближенные решения уравнений (1.16,1.17). Наиболее распространенным методом является семплирование Гиббса [34].
Смесь тематик 9 для документа d позволяет оценить, насколько та или иная тематика представлена в тексте, поэтому СРД применяется для тематической классификации текстов [29]. В том числе СРД может применяться для тематической классификации веб-документов при обнаружении поискового спама.
На рис. 1.4 приведен Пример тематической структуры текста, полученной с помощью модели СРД. Вначале модель была обучена на наборе из 10000 документов из коллекции ROMIP.ВуWeb. Затем для одного из документов с помощью модели все слова были размечены по тематикам СРД. В приведен Ученые выяснили, какие отделы мозга активируются при чтении и письме - навыках, которые человечество приобрело совсем недавно по эволюционным меркам, и которые не могли привесги к физическиш изменениям в организации коры, Работы сгщщалжтов стгхбликщаны в журнале Science, а ее краткое содержание Доступно на портале ScienceNow.
ОМ тексте есть одна основная тематика, и две второстепенных, остальные слова распределяются по другим тематикам с меньшим весом.
В работе [27] было построено две модели СРД, отдельно по корпусу спам-документов и отдельно по корпусу неспам документов. Таким образом было получено два набора весов тематик: один описывает наиболее распространенные тематики для спама (0арат), другой для неепама (/3hom). При илассификации документа d вычислялись наиболее вероятные смеси тематик по каждой модели 9spam(d), 6ham{d). Элементы векторор 6apam(d)( 6ham{d) использовалисЛ как признаки в классификации спама и неспама. В качестве алгоритма классификации использовался метод опорных векторов.
В работе [28] данная модель была расширена с использование информации о ссылках. Для этого в порождающую модель СРД были внесены изменения, согласно которым каждое слово порождается не только тематиками текущего документа, но и тематиками всех документов, которые ссылались на него.
Данные алгоритмы были апробированы на коллекции WebspamUК-2007. Базовый алгоритм, предложенный в работе [27] показал AUG = 0,796, а улучшенный алгоритм с учетом ссылок показал AUG = О, 854.
К достоинствам данного подхода следует отнести высокое качество обнаружения спама. В то же время учет ссылок между документами существенно замедляет работу алгоритма и делает невозможной локальную обработку отдельных документов. Также данный подход не подходит для обнаружения поискового спама, порожденного на основе документов-образцов, так как исходные документы и спам-документы, порожденные на их основе, содержат сходный набор тематик. Также для задач обнаружения текстового спама применимы и другие методы тематической классификации документов, например, метод предложенный в работе [11].
Обобщенная модель генератора текстов на основе образцов
Чтобы выработать общий алгоритм обнаружения текстов, порожденных генераторами на основе образцов, важно выделить их общие черты. В данном разделе предлагается обобщенная модель генератора текстов на основе образцов.
Пусть Dtempl " набор текстов-образцов. Рассмотрим множество троек (t) документ (d), номер словопозиции (ш), слово, стоящее в данной позиции (v):
Любой из перечисленных алгоритмов порождения текстов на основе образцов можно представить в виде однородной цепи Маркова с пространством состояний Т, у которой переходная матрица определяется разновидностью алгоритма.
Пусть U = (di,mi,Vi), tj = {dj,mhVj) - два элемента из пространства состояний. Обозначим Ptutj - вероятность перехода между двумя этими состояниями, где Р - матрица переходов для данной цепи. Выпишем Рщ для алгоритмов порождения текстов, описанных выше.
Модель "мешок слов". Так как в данной мюдели вероятность порождения любого слова на любом шаге пропорциональна количеству словопозиций, содержащих это слово, то матрица переходов будет иметь простейший вид
Для того чтобы отразить "закольцованность"документа с точки зрения генератора текстов, в формуле (2.4) допускаются нулевые или отрицательные номера словопозиций в документе, и такие номера словопозиций отсчитыва-ются в обратном порядке с конца документа.
Генераторы на основе фрагментов текстов. Для генераторов на основе фрагментов текстов введем дополнительные обозначения. Пусть В -множество состояний, в которых фрагменты начинаются, а Е - множество состояний, в которых фрагменты заканчиваются, тогда элемент матрицы переходов можно выписать в следующем виде
Рассмотрим построение обобщенных цепей на примере, приведенном в разделе 2.1.1.2. Воспользуемся формулами (2.4, 2.5) и построим графы переходов между состояниями обобщенных цепей для различных вариантов генераторов. На рис. 2.2 приведен граф переходов для генератора на основе цепей Маркова длины 1, обученного на документах dx = {vuv2, v3}, dx = {УЪУЪ г}. На рис. 2.3 - для генератора на основе фрагментов, обученного на тех же документах. Все ребра, выходящие из одной вершины, имеют одинаковые веса (соответствующие вероятностям перехода) и в сумме дают единицу.
Опишем процесс порождения текста на основе обобщенной модели. На первом шаге произвольным образом выбирается начальное состояние цепи 0 = {do,77io,uo). Затем на каждом последующем шаге, исходя из матрицы вероятностей Р, выбирается следующее состояние. Нри переходе в состояние t = {d, v, m) ) корождаемому уокументу уобавляется ялово о. Процесс сакан чивается, когда порожденный текст достигает определенной длины.
Рассмотрим некоторые свойства цепей Маркова для обобщенных генераторов текстов:
1. Невозвратные состояния. Цепь Маркова для обобщенного генератора не может содержать невозвратных состояний по построению.
2. Однородность. Очевидно, по построению матрица переходов цепи Маркова для обобщенного генератора не зависит от времени, то есть цепь однородная.
3. Неразложимые классы. Если цепь Маркова содержит несколько нераз ложимых классов, то будем рассматривать каждый из них по-отдельно-сти, так как каждый искусственный документ будет порожден одним из классов. При этом каждый неразложимый класс будет состоять из отдельного набора документов-образцов. Во всех дальнейших рассуждениях будем рассматривать только неразложимые цепи Маркова и множества документов-образцов, соответствующих им.
Таким образом, можно считать, что при порождении текстов на основе документов-образцов используются однородные неразложимые цепи Марко ва.
Проведем аналогичные рассуждения для матрицы переходов, построенной по cbooMvrre (2 5) ПУСТь на шаге ті распределение вероятностей состояний равно 7г = /—,.., —-— ). Рассмотрим множество состояний Т , из которых можно попасть в состояние t.
Рассмотрим два случая. Пусть t не принадлежит множеству состояний Б, которое соответствует множеству начал фрагментов, тогда Т состоит ровно из одного состояния г, вероятность которого на шаге п равна —, следовательно вероятность состояния t на шаге п + 1 также будет равна Тт.
Рассмотрим второй случай, когда t принадлежит множеству состояний начал фрагментов В. В этом случае множество Т совпадает с множеством состояний концов фрагментов Е. Очевидно, что \В\ = \Е\, следовательно
Таким образом, для цепи Маркова, построенной в соответствии с формулой (2.5), также выполняется утверждение леммы.
Лемма 2. При порождении текстов с помощью обобщенной цепи Map кова до/ія слов попо игдепныт и? любо?п гпстпятія t гтпдитгя пп врппятности к т=т.
Доказательство. Рассмотрим два случая - апериодическую цепь Маркова и цепь Маркова с периодом q.
Пусть цепь Маркова апериодична. Тогда согласно лемме 1 для любого изначального состояния г верно
Пусть цепь Маркова периодична с периодом д. Рассмотрим цепь Маркова с тем же пространством состояний, но с матрицей переходов Pq. Этт цепь Маркова будет апериодична и разложима на д неразложимых классов, \Т\ при этом по построению каждый из классов будет состоять ровно из — состояний. Для каждого из неразложимых классов утверждение леммы будет справедливо.
Порождение текста исходной цепью Маркова можно рассматривать как поочередное порождение слов из каждого неразложимого класса. Таким образом, доля слов, порожденных из состояния 1, будет выражаться через долю слов, порожденных неразложимым классом, содержащим это состояние (1/д), и долю таких слов в этом классе (сходится по вероятности к д/\T\), то есть будет сходиться по вероятности к —-, что и требовалось доказать.
Основные модули системы
Модули разработанной системы решают основные задачи классификации HTML-документов, начиная с предобработки, заканчивая вынесением вердикта. Далее приводятся описания основных модулей системы классификации спама.
Модуль предобработки документа. Данный модуль является общим во всех сценариях использования системы. Его основная задача обработать поступающий на вход HTML-документ и выделить из него текст документа. В данном модуле производится анализ дерева HTML-тегов и выделяются части документа, которые образуют видимый текст, также в данном модуле кодировка документа приводится к UTF-8 и определяется язык документа. Текст документа, выделенный на данном этапе, поступает на вход различным модулям выделения признаков и также модулю обучения модели СРД.
Модуль обучения модели СРД. Основная задача данного модуля -обучение модели СРД на основе коллекции текстов, поступивших на вход. Вначале поступающие тексты приводятся к нижнему регистру и разбиваются на слова, затемполученные последовательности слов используются как обучающий набор для алгоритма обучения СРД. Данный модуль реализует алгоритм обучения СРД на основе итерационного процесса известного как семплирование Гиббса [47]. Данный процесс позволяет приближенно вычислить параметры модели СРД, которые затем сохраняются для дальнейшего использования.
Модуль анализа тематического разнообразия. Данный модуль сходен по строению с модулем обучения модели СРД. Он также представляет документы в виде последовательности слов, а затем применяет семплирование Гиббса чтобы по известной модели СРД восстановить веса тематик для нового документа.
При обучении использовались следующие параметры модели СРД:
Количество тематик К — 100;
Параметр распределения тематик в рамках одного документа: а= (0.5 0.5);
В работе [47] показано, что для большинства документов, существующих в сети Интернет, достаточно всего 20 итераций, чтобы достичь сходимости семплирования Гиббса. В связи с этим, вместо того чтобы проверять условия сходимости на каждой итерации, предлагается использовать фиксированное количество итераций для всех документов. В данном модуле также вычисляются признаки, описанные в разделе 3.1.4.
Модуль выделения глобальных характеристик. Данный модуль вычисляет частоту встречаемости всех слов в документе и на основе этих частот оценивает параметры закона Ципфа для документа. В данном модуле также вычисляется степень сжатия документа алгоритмами gzip и bz2. В данном модуле вычисляются признаки, описанные в разделе 3.1.3.
Модуль выделения характеристик читаемости. Данный модуль производит разбиение текста документа на слова и предложения. На основе разбиения в нем вычисляются признаки, описанные в разделе 3.1.1.
Модуль выделение стилистических характеристик. Данный модуль получает на вход текст документа и вычисляет по нему признаки авторства и стиля. Для анализа частот употребления частей речи требуется провести морфологический анализ слов в тексте в зависимости от языка документа. Для морфологического анализа применялись существующие реализации морфологических анализаторов:
Парсер mystem для русского языка [60];
Анализатор частей речи Stanford Part of Speech Tagger для английского языка [61].
При этом система поддерживает добавление других морфологических анализаторов для других языков. После этапа морфологического анализа в данном модуле происходит подсчет признаков, описанных в разделе 3.1.2.
Модуль обучения классификатора. Данный модуль работает с документами в виде векторов признаков, которые он получает из модулей выделения характеристик. В этом модуле реализуется алгоритм построения ансамбля деревьев решений, описанный в разделе 3.2. Данный модуль на выходе формирует дерево решений, обученное для классификации поискового спама. Одной из особенностей задач, решаемых разработанной системой, является большой размер обучающего набора, порядка десятков тысяч документов. Эта особенность приводит к тому, что этап обучения системы может занимать часы или даже дни, что негативно сказывается на скорости обновления классификатора, и, следовательно, препятствует быстрому обнаружению новых видов поискового спама.
Для ускорения работы алгоритма машинного обучения этот модуль был оптимизирован для работы на многоядерных процессорах. На этапе построения базового классификатора был реализован параллельный перебор всех возможных разбиений по различным признакам. Это позволяет существенно ускорить построение базовых классификаторов. На практике при размере обучающего набора в 100000 документов и использовании 75 признаков, описанных в главе 3, при запуске на 8-ядерной системе общее время обучения сокращается с 16 часов до 4 часов.
Модуль классификации. Этот модуль также работает с документами в виде векторов признаков. Он загружает ранее сформированное дерево решений и использует его для классификации документов, поступающих к нему из модулей выделения характеристик. На выходе выдается вещественное число в интервале от -1 до 1, которое характеризует спамность документа с точки зрения системы.
Система спроектирована с учетом возможности добавления поддержки других языков и морфологических анализаторов, а также с учетом возможности добавления новых модулей выделения признаков. Наиболее ресурсоемкие модули (модуль обучения классификатора, модуль анализа тематического разнообразия, модуль предобработки документа) реализованы на языке программирования С + + для максимальной эффективности, остальные модули реализованы на языке программирования Python.
Сравнение эффективности предложенного решения с существующими аналогами
Результаты, приведенные в разделе 4.2.3.2 показывают, что предложенный алгоритм превосходит существующие аналоги по качеству обнаружения поискового спама. В то же время одним из важных свойств классификаторов поискового спама является их эффективность. Данный раздел посвящен сравнению эффективности предложенного метода с существующими аналогами.
Наиболее важным сценарием с точки зрения эффективности является сценарий классификации набора веб-документов, так как от скорости работы системы в данном сценарии зависит, как быстро документы могут быть проиндексированы поисковой системой. Пусть на вход системе подается М документов, максимальная длина документа в словах iV, пусть также каждый документ связан ссылками не более чем с К другими. Для сравнения различных алгоритмов проанализируем их временную и пространственную сложность в зависимости от М, N я К. Сравнение будем производить для предложенного алгоритма, а также для двух наилучших на данный момент алгоритмов: Linked LDA [28] и CASIA [43].
Алгоритм CASIA использует набор признаков па основе алгоритмов ссылочного ранжирования PageRank [56] и HITS [52], а также набор характеристик текста документа, предложенных в работе [55] и подробно описанных в разделе 1.2.3.1. Для вычисления PageRank и HITS применялся итерационный алгоритм, предложенный в работе [56]. Каждая итерация алгоритма PageR.ank имеет сложность порядка О(МК), при этом использовалось фиксированное количество итераций. Вычисление эвристик, описанных в разделе 1.2.3.1, требует вычисления сжимаемости документов и пословной обработки документа. Сложность большинства алгоритмов сжатия равна O(N), следовательно, временная сложность алгоритма CASIA равна 0{МК + N). Объем памяти, необходимый для вычисления PageRank, пропорционален О(МК), так как необходимо хранить матрицу связности документов между собой. Также для вычисления признаков по текстам документа необходимо хранить тексты документов. В итоге пространственная сложность алгоритма CASIA равна 0{M{N + К)).
Алгоритм Linked LDA использует модифицированную модель СРД для вычисления весов тематик документа. Для вычисления весов тематик в Linked LDA используется семплирование Риббса. Временная сложность одной итерации этого алгоритма на наборе из М документов длины N равна O(MN), используется фиксированное количество итераций. Так как при вычислении весов тематик в алгоритме Linked LDA учитываются документы, связанные ссылками, то данный алгоритм также требует хранения матрицы связности документов между собой. Пространственная сложность Linked LDA также равна 0(M{N + K)).
Алгоритм, предлагаемый в данной работе, использует модель СРД. Для оценки параметров модели СРД применяется семплирование Гиббса с фиксированным количеством итераций, поэтому временная сложность вычисления характеристик тематического разнообразия равна 0{MN). Для вычисления некоторых других характеристик, таких как параметров закона Ципфа, необходимо отсортировать все слова в документе, поэтому итоговая временная сложность предлагаемого алгоритма равна 0(MNlog{N)). Память, необходимая для обработки документов предлагаемым алгоритмом, пропорциональна размеру входных данных. Пространственная сложность предлагаемого алгоритма равна O(MN). В таблице 4.8 приведены оценки наихудшей временной и пространственной сложности для сравниваемых алгоритмов.
Важным преимуществом предлагаемого алгоритма является возможность обрабатывать документы в потоковом режиме. Из-за того что алгоритмы Linked LDA и CASIA используют ссылочный граф, их качество сильно зависит от количества документов, обрабатываемых одновременно. Как следствие, эти алгоритмы не могут обрабатывать документы в потоком режиме. в то же время предлагаемый алгоритм на основе тематического разнообразия позволяет обрабатывать документы независимо друг от друга. Таким образом, разработанная система легко масштабируется на многомашинных комплексах.
