У меня есть сайт со статьями схожей тематики. На сайте было две проблемы: спамерские сообщения и дубликаты статей, причём дубликаты часто являлись не точными копиями.
Данный пост повествует о том, как я решил эти проблемы.
Дано:
- общее количество статей 140 000;
- количество спама: примерно 5%;
- количество не чётких дубликатов: примерно 75%;
Задача: избавиться от спама и дубликатов, а так же не допустить их дальнейшего появления.
Часть 1. Классификация на спам/не спам
Все статьи на моём сайте относятся к одной и той же тематике и, как правило, спамерсие/рекламные сообщения прилично отличаются по содержанию. Я решил вручную отсортировать некоторое количество статей. И на их основе построить классификатор. Для классификации будем считать косинусное расстояние между вектором проверяемой статьи и векторами двух групп (спам/не спам). К какой группе проверяемая статья ближе, к той и будем относить статью.
Сначала надо вручную классифицировать статьи. Набросал для этого форму с чекбоксами и собрал за несколько часов 650 статей спама и 2000 не спама.
Все посты очищаются от мусора – шумовых слов, которые не несут полезной нагрузки (причастия, междометия и пр). Для этого я собрал из разных словарей, которые нашёл в интернете, свой словарь шумовых слов.
Чтобы минимизировать количество различных форм одного слова, можно использовать стеммиг Портера. Я взял готовую реализацию на Java отсюда. Спасибо, Edunov
Из слов классифицированных статей, очищенных от шумовых слов и прогнанных через стемминг надо собрать словарь.
Из словаря удалим слова, которые встречаются только в одной статье.
Для каждой классифицированной вручную статьи считаем количество вхождений каждого слова из словаря. Получатся векторы, похожие на следующие:
Усиливаем в каждом векторе веса слов, считая для них TF-IDF. TF-IDF считается отдельно для каждой группы спам/не спам.
Сначала считаем TF (term frequency — частота слова) для каждой статьи. Это отношение количества вхождений конкретного слова к общему числу слов в статье:
где ni есть число вхождений слова в документ, а в знаменателе — общее число слов в данном документе.
Дальше считаем IDF (inverse document frequency — обратная частота документа). Инверсия частоты, с которой некоторое слово встречается в документах группы (спам/не спам). IDF уменьшает вес слов, которые часто употребляются в группе. Считается для каждой группы.
где
- |D| — количество документов в группе;
- di⊃ti — количество документов, в которых встречается ti (когда ni≠0).
Считаем TF-IDF:
Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.
Для каждой группы формируем по одному вектору, считая среднее арифметическое каждого параметра внутри группы:
Чтобы проверить статью на спам, надо получить для нее количество вхождений слов их словаря. Посчитать для этих слов TF-IDF для спама и не спама. Получится два вектора (на изображении TF-IDF не спам и TF-IDF спам). IDF для расчётов, берём тот, который считали для классифицирующей выборки.
Для каждого вектора считаем косинусное расстояние с векторами для спама и не спама, соответственно. Косинусное расстояние – это мера похожести двух векторов. Скалярное произведение векторов и косинус угла θ между ними связаны следующим соотношением:
Имея два вектора A и B, получаем косинусное расстояние – cos(θ)
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:
на спам – 0.62:
Следовательно, считаем, что статья – не спам.
Для тестирования я вручную отобрал ещё 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% выводил эмпирически. Оно позволяет находить достаточно изменённые версии одной и той же статьи.
Чизкейк со сгущенкой (без выпечки)
Ингредиенты:
* 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
