Поиск текстов, не соответствующих тематике и нахождение похожих статей

в 19:49, , рубрики: java, Алгоритмы, детектор дубликатов, детектор спама, машинное обучение, Программирование, метки: , ,

У меня есть сайт со статьями схожей тематики. На сайте было две проблемы: спамерские сообщения и дубликаты статей, причём дубликаты часто являлись не точными копиями.

Данный пост повествует о том, как я решил эти проблемы.

Дано:

  • общее количество статей 140 000;
  • количество спама: примерно 5%;
  • количество не чётких дубликатов: примерно 75%;

Задача: избавиться от спама и дубликатов, а так же не допустить их дальнейшего появления.

Поиск текстов, не соответствующих тематике и нахождение похожих статей - 1

Часть 1. Классификация на спам/не спам

Все статьи на моём сайте относятся к одной и той же тематике и, как правило, спамерсие/рекламные сообщения прилично отличаются по содержанию. Я решил вручную отсортировать некоторое количество статей. И на их основе построить классификатор. Для классификации будем считать косинусное расстояние между вектором проверяемой статьи и векторами двух групп (спам/не спам). К какой группе проверяемая статья ближе, к той и будем относить статью.

Сначала надо вручную классифицировать статьи. Набросал для этого форму с чекбоксами и собрал за несколько часов 650 статей спама и 2000 не спама.

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

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

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

Из словаря удалим слова, которые встречаются только в одной статье.

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

Усиливаем в каждом векторе веса слов, считая для них TF-IDF. TF-IDF считается отдельно для каждой группы спам/не спам.

Сначала считаем TF (term frequency — частота слова) для каждой статьи. Это отношение количества вхождений конкретного слова к общему числу слов в статье:

Поиск текстов, не соответствующих тематике и нахождение похожих статей - 3

где ni есть число вхождений слова в документ, а в знаменателе — общее число слов в данном документе.
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 4

Дальше считаем IDF (inverse document frequency — обратная частота документа). Инверсия частоты, с которой некоторое слово встречается в документах группы (спам/не спам). IDF уменьшает вес слов, которые часто употребляются в группе. Считается для каждой группы.

Поиск текстов, не соответствующих тематике и нахождение похожих статей - 5

где

  • |D| — количество документов в группе;
  • di⊃ti — количество документов, в которых встречается ti (когда ni≠0).

Поиск текстов, не соответствующих тематике и нахождение похожих статей - 6

Считаем TF-IDF:

Поиск текстов, не соответствующих тематике и нахождение похожих статей - 7

Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 8

Для каждой группы формируем по одному вектору, считая среднее арифметическое каждого параметра внутри группы:
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 9

Чтобы проверить статью на спам, надо получить для нее количество вхождений слов их словаря. Посчитать для этих слов TF-IDF для спама и не спама. Получится два вектора (на изображении TF-IDF не спам и TF-IDF спам). IDF для расчётов, берём тот, который считали для классифицирующей выборки.
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 10

Для каждого вектора считаем косинусное расстояние с векторами для спама и не спама, соответственно. Косинусное расстояние – это мера похожести двух векторов. Скалярное произведение векторов и косинус угла θ между ними связаны следующим соотношением:
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 11

Имея два вектора A и B, получаем косинусное расстояние – cos(θ)
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 12

Код на Java

public static double cosine(double[] a, double[] b) {
    double dotProd = 0;
    double sqA = 0;
    double sqB = 0;
    for (int i = 0; i < a.length; i++) {
        dotProd += a[i] * b[i];
        sqA += a[i] * a[i];
        sqB += b[i] * b[i];
    }
    return dotProd/(Math.sqrt(sqA)*Math.sqrt(sqB));
}

В результате получается диапазон от -1 до 1. -1 означает, что вектора полностью противоположны, 1, что они одинаковы.

Какое из полученных значений (для спама и не спама) будет ближе к 1, к той группе и будем относить статью.

При проверке схожести на не спам получилось число 0.87:
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 13
на спам – 0.62:
Поиск текстов, не соответствующих тематике и нахождение похожих статей - 14
Следовательно, считаем, что статья – не спам.

Для тестирования я вручную отобрал ещё 700 записей. Точность результатов была 98%. При этом то, что классифицировалось ошибочно даже мне было сложно отнести к той или иной категории.


Часть 2. Поиск нечётких дубликатов

После очистки от спама осталось 118 000 статей.

Для поиска дубликатов я решил использовать инвертированный индекс (Inverted index). Индекс представляет собой структуру данных, где для каждого слова указывается, в каких документах оно содержится. Соответственно, если у нас есть набор слов, можно легко сделать запрос документов, содержащих эти слова.

Пример с Вики. Допустим, у нас есть следующие документы:

T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"

Для этих документов построим индекс, указав, в каком документе содержится слово:

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

Все слова «what», «is» и «it» находятся в документах 0 и 1:

{0,1} ∩ {0,1,2} ∩ {0,1,2} = {0,1}

Индекс я сохранял в БД MySQL. Индексирование заняло около 2-х дней.

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

Чтобы отсеять то, что дубликатом не является, надо посчитать косинусное расстояние между исходной и найденными. То, что совпадает больше, чем на 75% считаю дубликатом. Число в 75% выводил эмпирически. Оно позволяет находить достаточно изменённые версии одной и той же статьи.

Пример найденных дубликатов:

Вариант 1:
Чизкейк со сгущенкой (без выпечки)

Ингредиенты:
* 450 гр Сметана от 20 % жирности
* 300 гр печенья

* 100 гр растопленного сливочного масла
* 300 гр хорошего сгущенного молока
* 10 гр быстрорастворимого желатина
* 3/4 стакана холодной кипяченой воды

Приготовление:
Разборную форму выстелить пергаментной бумагой.
Размельченное в мелкую крошку печенье смешать с растопленным маслом. Смесь должна быть не жирной, но и не сухой. Выложить смесь в форму и хорошо уплотнить. Убрать в холодильник на 30 минут.
Сметану смешать со сгущенным молоком.
Желатин залить 3/4 стакана воды и поставить на 10 минут набухать. Затем растопить его на водяной бане так, чтобы он весь растворился.
В смесь сгущенки и сметаны осторожно влить желатин, тщательно помешивая. Перелить затем в форму. И убрать в холодильник до полного застывания примерно на 2-3 часа.
При застывании можно добавить ягоды свежей клюквы или посыпать тертым шоколадом или орехами.

Приятного аппетита!

Вариант 2:
«Чизкейк» без выпечки со сгущенкой

Ингредиенты:

-Сметана от 20 % жирности 450 гр

-300 гр печенья ( я брала овсяные)
-100 гр растопленного сливочного масла
-300 гр качественного сгущенного молока
-10 гр быстрорастворимого желатина
-3/4 стакана холодной кипяченой воды

Приготовление:

1). Форму (лучше разъёмную) застелить пергаментной бумагой.
2). Печенье измельчить в мелкую крошку и смешать с растопленным маслом. Масса не должна быть жирной, но и не слишком сухой. Уложить массу в форму и хорошо утрамбовать. Поставить в холодильник на полчаса.
3). Сметану смешать со сгущенным молоком (можно добавить больше или меньше сгущенки, это уже дело вкуса).
4) Желатин залить 3/4 стакана воды и оставить на 10 мин. набухать. Затем растопить его на водяной бане так, чтобы он полностью растворился.
5) В сметано-сгущенную массу потихоньку ввести желатин, хорошо помешивая. Перелить затем в форму. И отправить в холодильник до полного застывания. У меня застыл быстро. Где-то 2 часа.
Я при застывании добавила еще ягоды свежей клюквы — это придало пикантность и кислинку. Можно посыпать тертым шоколадом или орехами.

Полная чистка заняла около 5 часов.

Чтобы обновлять индекс для поиска дубликатов, не надо перестраивать уже существующие данные. Индекс достраивается инкрементально.

Из-за ограниченного количества оперативки на сервере у меня нет возможности держать индекс в памяти, поэтому я и держу его MySQL-е, где хранятся сами статьи. Проверка одной статьи, если не грузить всё в память, занимает у программы около 9 сек. Это долго, но т.к. новых статей в сутки появляется лишь несколько десятков, решил не заморачиваться со скоростью, пока этого не потребуется.

Автор: shurik2533

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js