Данная работа посвящена разработке методов и средств обнаружения массово порождаемых неестественных текстов. В работе предлагается теоретическая обобщенная модель текстов, порожденных по образцам. На основе теоретической модели предлагается алгоритм обнаружения неестественных текстов. Данный алгоритм анализирует тематическую структуру текстов, и определяется по ней неестественные тексты. Предложенный алгоритм проверяется на задаче обнаружения поискового спама.
1. Введение
В связи с ростом объема информации в сети Интернет поисковые машины стали основным средством для эффективного доступа к ней. Задача поисковой машины – на каждый поисковый запрос выдавать ранжированный набор страниц, наиболее соответствующих запросу. Мера соответствия страницы запросу, называемая релевантностью, вычисляется на основе характеристик страниц и запросов.
Появление сайта в первой десятке выдачи
популярных поисковых систем по коммерческим
запросам обеспечивает большой приток
посетителей на сайт. В связи с этим возникает
конкуренция между создателями сайтов за
попадание на верхние позиции выдачи поисковых
систем. Она приводит к тому, что создатели сайтов
пытаются повлиять на работу алгоритмов,
применяемых в поисковых системах, чтобы
незаслуженно повысить оценку релевантности
страниц. Это явление получило название
поискового спама [
Поисковый спам ухудшает качество поиска и
увеличивает нагрузку на поисковую систему. Он
был признан одной из основных угроз для
современных поисковых систем [
Поисковые системы используют различную информацию для ранжирования страниц: содержимое страницы и сайта, на которой она расположена; ссылки между страницами и сайтами и пр. В настоящее время существует несколько разновидностей поискового спама, нацеленных на различные алгоритмы, применяемые внутри поисковых систем. Например, ссылочный спам нацелен на алгоритмы ссылочного ранжирования, такие как PageRank.
Одной из разновидностей поискового спама является массовое порождение неестественных текстов. При использовании такого спама целью спамеров является попадание в выдачу по запросам с малым количеством релевантных страниц. Это позволяет странице с большой вероятностью показаться по этому запросу. Чтобы максимизировать количество переходов пользователей по таким запросам спамерам приходится создавать тысячи страниц, каждая из которых должна показываться по одному или нескольким низкочастотным запросам. Такой спам особенно опасен для поисковых систем, так как спамерские страницы непосредственно показываются в выдаче.
Так как создание большого количества страниц с текстом вручную не представляется возможным, спамеры применяют автоматические алгоритмы массового порождения текстов. При этом им необходимо максимально затруднить обнаружение таких текстов со стороны поисковой системы. Существует два основных подхода к массовому порождению текстов: • Копирование существующих естественных текстов; • Синтез текстов на основе естественных документов-образцов.
В настоящее время существует целый ряд
эффективных методов обнаружения дубликатов,
которые позволяют обнаруживать скопированные
тексты в масштабах сети Интернет [
Данная работа посвящена алгоритмам обнаружения массово порождаемых неестественных текстов. 1.1 Обзор существующих решений
В основе многих методов обнаружения
неестественных текстов лежит подход,
предложенный в работе [
Развитием данного подхода является работа [
В работе [
Одной из целей исследования является изучение теоретических основ обнаружения неестественных текстов, порожденных на основе документовобразцов.
Автоматическая генерация текстов в настоящее время является нерешенной задачей. Естественным текстам свойственно большое количество закономерностей, которые сложно воспроизвести автоматическими методами: • Локальная связность; • Единство стиля и жанра; • Синтаксическая структура предложений; • Глобальная тематическая связность текста; • Структура изложения;
• И т.п.
При порождении поискового спама используются различные алгоритмы порождения текстов. Рассмотрим алгоритмы, которые используют выборку естественных текстов для обучения генераторов текстов.
В данной работе был рассмотрен ряд алгоритмов порождения текстов, зачастую применяемых для порождения неестественных текстов: • Алгоритм на основе модели «мешок слов»; • Алгоритм на основе цепей Маркова порядка k; • Алгоритм на основе копирования фрагментов документов-образцов.
Чтобы выработать общий алгоритм обнаружения текстов, порожденных генераторами на основе образцов, важно выделить их общие черты. В данном разделе предлагается обобщенная модель генератора текстов, на основе образцов.
Пусть Dобразцы – набор текстов-образцов. Рассмотрим множество троек (t): документ (d), номер слова (m), слово, стоящее в данной позиции (v):
T = {t} = {(d , m, v)}; | T |=
∑ | d |; d∈Dобразцы Опишем процесс порождения текста на основе обобщенной модели. На первом шаге произвольным образом выбирается начальное состояние цепи. Затем на каждом последующем шаге, исходя из матрицы вероятностей, выбирается следующее состояние, при переходе в состояние t = (d , m, v) к порождаемому документу добавляется слово v. Процесс заканчивается, когда порожденный текст достигает определенной длины.
Все вышеперечисленные алгоритмы порождения текстов на основе образцов можно представить в виде однородной цепи Маркова с пространством состояний T, у которой переходная матрица P определяется разновидностью алгоритма. 2.1 «Мешок слов»
Так как в данной модели вероятность порождения любого слова на любом шаге пропорциональна частоте этого слова в наборе, матрица переходов будет иметь простейший вид: 1 Ptit j = P( X n+1 = t j | X n = ti ) = (1) | T | ; 2.2 Алгоритм на основе цепей Маркова
Пусть k – порядок цепи Маркова, тогда элемент матрицы переходов для этого алгоритма не равен нулю, только если предыдущие k слов для двух состояний совпадают. Введем сходства на множестве состояний. Два состояния схожи по k предыдущим, если предыдущие k слов для этих двух состояний совпадают.
Очевидно, отношение сходства по k предыдущим состояниям является отношением эквивалентности и множество состояний разделяется на классы эквивалентности T1k ,..,TNkk . Обозначим P(T ) - множество состояний, непосредственно предшествующих состояниям из множества T. Тогда вероятность перехода между состояниями может быть выражена через их классы эквивалентности: ⎧ 1 ⎪ Ptit j = ⎨| Tlk | ⎪ ⎩ , t j ∈Tlk , ti ∈ P(Tlk ); 0, иначе; (2) 2.3 Алгоритм на основе фрагментов текстов Для генераторов на основе фрагментов текстов введем дополнительные обозначения. Пусть B – множество состояний, в которых фрагменты начинаются, а E – множество состояний, в которых фрагменты заканчиваются, тогда элемент матрицы переходов можно выписать в следующем виде: ⎧ 1 ⎪ | B | , ti ∈ E, t j ∈ B; ⎪ Ptit j = ⎨1, d i = d j , m j = mi + 1, ti ∉ E; (3) ⎪ 0, иначе; ⎪ ⎩ 3. Модель тематической структуры текстов
Одной из важных характеристик естественных текстов является глобальная тематическая связность текстов. У текстов чаще всего есть одна основная тема, и несколько второстепенных. Изучение неестественных текстов показывает, что они зачастую бессмысленны и лишены единой тематики. При этом в тексте встречаются слова из различных документов-образцов, посвященных разным тематикам. Таким образом, на интуитивном уровне тематика синтетических текстов более разнообразна и расплывчата. Чтобы использовать это наблюдение для обнаружения неестественных текстов, вначале формализуем понятие тематики.
Предлагаемый подход к формализации понятия тематики аналогичен лингвистической теории, сформулированной авторами [6]. В рамках данной теории утверждается, что любой осмысленный документ – это некоторое высказывание над несколькими макроконцептами. При этом разные концепты в разной степени участвуют в формировании текста, что соответствует основным и второстепенным тематикам в документе.
Также в модели предполагается, что тематик конечное множество число.
Пусть всех тематик, Θ = {Θ1,.., ΘK } тогда вектор (4) Теоретические исследования методов порождения неестественных текстов позволяют формально доказать нарушение тематической структуры в порожденных текстах.
Теорема 1. Пусть Dобразцы – набор документовобразцов для генератора текстов, и задана тематическая структура каждого документа. Пусть с помощью генератора порождается документ dпорожд длины l. Тогда с ростом l тематическая структура порожденного документа ипорожд сходится по вероятности к усредненной тематической структуре документов-образцов: ∑| d |θ d
∑| d | θ порожд ⎯⎯Ρ → d∈Dобразцы ;
(5) d∈Dобразцы Важным следствием данной теоремы является то, что распределение тематик более разнообразно в порожденных текстах, чем в документах-образцах. Если в естественных текстах зачастую присутствует одна ярко выраженная тематика, то в порожденных документах тематика более расплывчатая. 4. Предлагаемый алгоритм обнаружения 4.1 Моделирование тематик с помощью модели СРД
В настоящее время существует несколько
подходов к моделированию тематик текстов. В
данной работе использовалась статистическая
модель для текстов скрытое распределение Дирихле
(СРД), также известная как Latent Dirichlet
Allocation (LDA) [
В модели СРД считается, что тематика определяется вероятностью порождения слов из словаря. Считается, что существует ограниченное число тематик N. При этом одно и то же слово имеет ненулевую вероятность порождения в разных тематиках. В данной модели каждому документу ставится в соответствие вектор вероятностей тематик и, порожденный из распределения Дирихле с вектором параметров б. При этом считается, что каждое слово в документе порождено строго одной тематикой.
Модель СРД также позволяет по имеющемуся набору документов восстановить вероятности слов в тематиках и веса тематик и для каждого документа. Тематики в модели СРД, восстановленные по коллекции текстов, обладают рядом свойств, которые делают их похожими на тематики в интуитивном представлении: • Слова, которые часто встречаются вместе в одних и тех же текстах, получают высокий вес в одних и тех же тематиках; • Любое слово может порождаться разными тематиками с разной вероятностью; • Часто употребляемые слова, такие как предлоги и союзы, будут иметь высокую вероятность порождения в любой тематике.
Описанные свойства позволяют рассматривать
веса тематик для документов, полученные в модели
СРД, как некоторую модель интуитивного понятия
о тематиках документа. В данной работе тематики
текстов моделировались с помощью модели СРД,
обученной на 10000 документах из коллекции
Romip.ByWeb [
Из теоремы 1 следует, что с ростом длины порожденного документа его тематическая структура будет стремиться к усредненной тематической структуре набора документовобразцов. 4.2.1 Оценка разнообразия тематической структуры на основе критерия Пирсона Для того чтобы оценить естественность тематической структуры можно применить критерий согласия Пирсона. Будем использовать критерий Пирсона, чтобы проверить гипотезу, что наблюдаемые веса тематик подчиняются усредненному распределению тематик.
В реальности усредненные веса тематик документов-образцов могут быть не известны. Чтобы обойти эту проблему воспользуемся особенностью модели СРД. В модели считается, что веса тематик документов подчиняются распределению Дирихле с однородными r параметрами α . Математическое ожидание такой ⎛ 1 случайной величины равно ⎜ ⎝ K ,.., 1 ⎞
⎟ . Таким K ⎠ образом, в качестве усредненного веса тематик в документах-образцах можно взять математическое ожидание весов тематик в модели СРД:
K ⎛ 1 2 χ 2 (d ) = K 2 ∑ ⎜ −θ i d ⎟⎞ ; (6) i=1 ⎝ K ⎠ 4.2.2 Оценка разнообразия тематической структуры на основе закона Ципфа
Естественным текстам свойственен ряд
статистических закономерностей, таких как закон
Ципфа [
Предлагаемый подход опирается на гипотезу, что для весов тематик справедлива аналогичная закономерность – если упорядочить тематики по весу в документе, то вес тематики будет обратно пропорционален ее порядковому номеру. Вес тематики иk с порядковым номером k подчиняется следующему соотношению: θ k (s, c) ≈ c ;
(7) k s где s – параметр, характеризующий разнообразие тематик в тексте, c – константа. Чем больше параметр s тем больший вес будет у основных тематик, чем меньше s, тем более разнообразны тематики в документе.
Для оценки разнообразия тематик в тексте можно по частотам тематик в тексте оценить параметры s и c. Для вычисления значения s формулу (15) удобно привести к логарифмической шкале: log(θ k (s, c)) ≈ log(c) − s log(k ); (8) Чтобы из этого уравнения получить приближенное значение s для текста, воспользуемся (9) методом наименьших квадратов: f k = log(θ k (s, c)); rk = log( k ); s = −
K ∑ rk f k − ∑ rk ∑ f k k k k
⎞ K ∑ (rk )2 − ⎜⎛ ∑ rk ⎟
k ⎝ k ⎠ Характеристика разнообразия тематик в тексте, вычисленная по формуле (9) может также использоваться как один из факторов для оценки разнообразия тематик текстов. Чем больше значение параметра Ципфа для текста, тем с менее разнообразна тематическая структура документа. 4.2.3 Алгоритм машинного обучения для обнаружения неестественных текстов
Предлагаемый алгоритм машинного обучения для обнаружения неестественных текстов состоит из двух основных частей: • Модель СРД, применяющаяся для автоматического построения тематической структуры текстов; • Алгоритм машинного обучения на основе деревьев решений; При обучении данного алгоритма вначале строится модель СРД по обучающей выборке документов. По этой модели с помощью формул (6) и (9) можно оценить тематическое разнообразие естественных и неестественных документов, содержащихся в обучающей выборке.
Характеристики тематического разнообразия
используются как факторы при построении
автоматического классификатора. Наряду с
факторами тематического разнообразия
применяются многочисленные статистические
характеристики, предложенные в работе [
В результате обучение происходит дважды: вначале на выборке качественных документов Таблица 1. Характеристики классификации неестественных текстов различными вариантами алгоритма Точность Полнота
F-мера БМазеошваояквселросви.я 98,41% 98,50% 98,45% БазоЦваМя -в2е.рсия 96,19% 96,11% 96,15% БазоЦваМя -в3е.рсия 94,08% 92,29% 93,18% БПарзеодвлаяожвеернсиияя. 92,69% 91,87% 92,28% УлуМчше шенонкасялвоевр.сия 99,70% 99,25% 99,47% УлучшЦенМна-2я.версия 98,37% 97,93% 98,15% УлучшЦенМна-3я.версия 97,72% 97,09% 97,40% УлПучршеделнонжаяенвиеря.сия 96,23% 97,03% 96,63% обучается модель СРД, затем по обучающему набору обучается классификатор спама.
В данной работе используется алгоритм классификации, основанный на деревьях решений C4.5 с добавлением процедуры объединения нескольких деревьев путем голосования.
При классификации текстов, с помощью
предварительно обученной модели СРД,
вычисляется разнообразие тематической структуры
текстов, затем вычисляются характеристики,
предложенные в работе [
Важной частью работы является экспериментальное подтверждение применимости предлагаемого алгоритма обнаружения неестественных текстов.
В рамках первого эксперимента проверялась способность предложенного алгоритма решать модельную задачу – обнаруживать документы, порожденные каждым из рассмотренных алгоритмов генерации неестественных текстов.
Измерялась точность полнота и F-мера обнаружения неестественных текстов при использовании классификатора, обученного на выборке естественных текстов из коллекции ROMIP.ByWeb и наборе текстов, порожденных различными генераторами текстов: • Генератор на основе модели «мешок слов» (мешок слов); • Генератор на основе цепей Маркова порядка 2 (ЦМ-2); • Генератор на основе цепей Маркова порядка 3 (ЦМ-3); • Генератор на основе копирования предложений (предложения); Обучающие выборки составлялись из 10000 документов из коллекции ROMIP.ByWeb в качестве примеров естественных текстов, и 10000 документов, порожденных одним из генераторов, обученных на текстах из той же коллекции. Тестовые выборки составлялись аналогичным образом и не содержали пересечения с обучающими.
В ходе эксперимента было построено два
классификатора для каждой тренировочной
выборки. В качестве базового был взят
классификатор с использованием характеристик,
предложенных в работе [
Разница в точности и полноте классификаторов позволяет оценить выигрыш при использовании характеристик тематического разнообразия. Результаты эксперимента приведены в таблице 1.
Чтобы сравнить предлагаемые алгоритмы
обнаружения поискового спама с существующими
аналогами был проведен ряд экспериментов на
наборе данных WebspamUK-2007 [
В рамках эксперимента на обучающей выборке
обучались две версии алгоритма – базовая без
характеристик тематической структуры и
улучшенная, содержащая характеристики,
предложенные в разделе 4. Версии алгоритма
сравнивались между собой, а также с лучшими
результатами других исследователей на данном
наборе. В частности сравнение проводилось с
алгоритмом победителя соревнований по
обнаружению поискового спама Web Spam
Challenge 2008 [
Общепринятой метрикой для измерения качества классификаторов поискового спама на данном наборе является площадь под ROC-кривой (Area Under ROC-Curve, AUC). ROC-кривая – это кривая, которую описывает алгоритм классификации на графике, осями которого являются верно-положительные и ложноположительные срабатывания. Чем больше площадь под ROC-кривой, тем в среднем больше полнота алгоритма при фиксированной точности.
Результаты эксперимента и сравнение с существующими аналогами приведено в таблице 2. Как видно, улучшенный алгоритм превосходит, как базовую версию, так и лучшие на текущий момент алгоритмы классификации поискового спама. Базовый алгоритм Улучшенный алгоритм
Linked LDA [
Для решения задачи определения автоматически порожденных неестественных текстов разработан новый алгоритм машинного обучения на основе оценки разнообразия тематик документа.
Теоретически и численно обоснована применимость разработанного алгоритма для обнаружения неестественных текстов, порожденных генераторами текстов на основе цепей Маркова, широко используемых для создания веб-спама.
Разработанный алгоритм апробирован на стандартном наборе данных реальных сайтов WebspamUK-2007. Получены более высокие характеристики классификации веб-спама, по сравнению с известными методами. Литература
© A.S. Pavlov
This work is dedicated to development of methods and tools for detecting mass-generated unnatural texts. A generalized model of unnatural texts generated using natural samples is proposed. An algorithm for unnatural texts detection is also proposed. The algorithm is based on theoretical properties of unnatural texts and uses topical diversity analysis to distinguish natural and unnatural texts. The proposed algorithm is evaluated on web spam detection task.