В поисках аномалии: одноклассовая классификация текстов с помощью расхождения Кульбака – Лейблера

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

Представьте ситуацию – вам нужно найти текстовые аномалии в определенном датасете. У вас есть размеченный датасет с образцами только аномального класса. При этом различия сразу в глаза не бросаются: не то чтобы аномальные тексты написаны на английском, а нормальные – на русском.

Что это может быть за задача? В общем случае, это может быть выявление любых небольших отрывков текста, которые попали в общий датасет как сор. К примеру, это могут быть заявки, ошибочно попавшие не в ту очередь. Также это могут быть необычные события в логах или письма от мошенников. В этом посте, для примера, рассмотрю задачу отсеивания отрывков произведений Н.С. Лескова из датасета с текстами П.П. Бажова. Почему выбрана эта пара писателей? Оба писали сказы, оба использовали разговорно-бытовой стиль и с ходу не у всякого их текста угадывается автор.

Для решения таких задач часто используют метод одноклассовой классификации на основе опорных векторов – One-class SVM Classification. Одноклассовая классификация (еще ее называют унарной классификацией) помогает идентифицировать объекты определённого класса среди всех объектов через обучение на наборе, содержащем только объекты этого класса. Однако в моём случае этот метод дал неудовлетворительные результаты. Тогда было решено опробовать метод Кульбака-Лейблера. О нём и написан пост.

Датасеты были подготовлены самостоятельно (их можно найти по ссылке). В них вошли части произведений из «Малахитовой шкатулки» Бажова и из сборника повестей и рассказов Лескова (например, «Левша»). Датасет с текстами Бажова и вкраплениями текстов Лескова назову для простоты «большим», а датасет исключительно с текстами Лескова – «малым». В большой датасет вошло 2505 текста Бажова и 30 текстов Лескова, в среднем по 196 символов каждый. То есть в большом датасете 1,2% аномалий. В малый датасет вошло 213 текстов Лескова по 208 символов в среднем. Загружаем датасеты:

Примеры текстов:

Далее, поэтапно, рассмотрю процесс подготовки текстов и поиска в них аномалий.

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

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

Вместо лемматизации можно использовать стемминг Операция стемминга возвращает основу слова, тогда как операция лемматизации возвращает словарную форму слова. Пример стемминга: «скажите» à «скаж». Пример лемматизации: «скажите» à «сказать». Лемматизация лучше, но в моём случае, из-за технических ограничений, использовала стемминг via Snowball Stemmer NLTK. Стемминг хуже тем, что основы разных слов могут быть одинаковы и при подсчете частот это даст дополнительную ошибку.

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

Сравнение двух корпусов проводится с использованием расхождения Кульбака – Лейблера. Расхождение Кульбака – Лейблера – это мера того, насколько одно распределение вероятностей отличается от второго, эталонного, распределения вероятностей. В моём случае это вероятность встретить слово в корпусе. Рассчитывается оно так:

где µ – любая мера на X, для которой существуют абсолютно непрерывные относительно µ функции p = dP/dµ и q = dQ/dµ (а это как раз относительные частоты лемм в корпусах). Основание логарифма в этой формуле существенной роли не играет. Его выбор позволяет зафиксировать конкретный вид функции из семейства эквивалентных функций и равносилен выбору единицы измерения расхождения Кульбака-Лейблера, поэтому возможно применение логарифма с любым основанием, большим единицы. Я использовала двоичный логарифм. Код для этого этапа следующий:

DKL(P‖Q) – безразмерная величина. Чему она может быть равна? Если два распределения в разрезе слов полностью совпадают, то получим DKL(P‖Q)=0. Если слово редкое, то получим отрицательное значение. Оба эти случая мне неинтересны: либо потому что это низкочастотное слово, либо потому что в обоих корпусах слово одинаково распределено. Поэтому их отсекаю, принимая отсечку по DKL(P‖Q) на уровне 0,0001:

В итоге получаем список специфичных слов с соответствующими значениями DKL(P‖Q). Таким образом получилось 781 слово (а точнее 781 лемма), самые специфичные из которых – ‘говорить’ и ‘государь’.

Нужно помнить, что расхождение Кульбака-Лейблера является несимметричной мерой, т.е. может быть DKL(P‖Q) ≠ DKL(Q‖P). Поэтому всегда важно правильно определять эталонный и референсный корпуса.

Следующий этап – поиск текстов Лескова в датасете с текстами Бажова. Для каждого слова из текстов большого датасета, проверяю есть ли оно среди специфичных слов, и если есть, то беру его DKL(P‖Q). Далее, суммирую все DKL(P‖Q), а затем, для учета размера текста, умножаю эту сумму на количество специфичных слов и делю на общее число слов текста после чистки.

После сортировки по убыванию по ΣDKL(P‖Q) и выбора отсечки, получаю датасет текстов, похожих на тексты Лескова

Для того, чтобы это понять, построим график специфичности для топ-50 исследуемых текстов. Те тексты, которые имеют специфичность выше 0,74 – это гарантированно тексты Лескова. Их получилось 26 штук. И действительно, контрольная колонка с авторами для этих текстов содержит только значение ‘Лесков’. Те тексты, которые имеют специфичность ниже 0,21 – тексты Бажова. Проверка контрольной колонки подтверждает это.

А вот между точками со специфичностью 0,74 и 0,21 находится пограничная зона, в которой специфичность текстов резко снижается. И тут хорошо бы иметь под рукой эксперта, который сможет вручную обработать тексты этой области. Однако можно поступить проще. В том случае, если важно исключить аномалии по максимуму, можно отсечь тексты по порогу 0,21. Отбросим 32 текста, из которых 30 текстов Лескова и 2 текста Бажова. Неплохой результат!

Матрица несоответствий для метода Кульбака-Лейблера (отсечка 0,21): Actual label – фактическая метка, Predicted label – предсказанная метка; 0 – число текстов Лескова, определенных как тексты Бажова, 30 – число правильно определенных текстов Лескова, 2 – число текстов Бажова, определенных как тексты Лескова, 2503 – число правильно определенных текстов Бажова

Если важно оставить все целевые тексты, а это тексты Бажова, то можно отсечь тексты по порогу 0,74. Так, будут сохранены все тексты Бажова, но среди 2505 текстов Бажова останется 4 текста Лескова. Для этого нужно найти первую точку перегиба на кривой специфичности. Ищу её как вторую производную от слегка сглаженных данных по специфичности.

Вот код:

А вот график:

Поиск осечки аномалий по точке перегиба кривой специфичности текстов: синяя линия – изначальный (зашумленный) график специфичности; оранжевая линия – сглаженный график специфичности; зеленая линия – график второй производной функции специфичности (масштабированный). При х = 26 вторая производная меняет свой знак. Так мы находим точку перегиба функции специфичности (26; 0,74).

И затем сохраняем результат:

Подготовку датасетов проводила так же, как для метода Кульбака-Лейблера. Для векторизации использовался TfidfVectorizer. Метод One-class SVM взят в библиотеке Scikit learn.

Что оказалось? Оказалось, что с One-class SVM classification не всё так хорошо, как с методом Кульбака-Лейблера, что видно из матрицы несоответствий: 18 аномальных текстов было правильно распознано, тогда как 12 аномальных текстов было причислено к классу нормальных. Но что хуже всего – 99 текстов Бажова было отнесено к текстам Лескова, а это почти 4% всех нормальных текстов!

Матрица несоответствий для метода One-class SVM Classification: Actual label – фактическая метка, Predicted label – предсказанная метка; 12 – число текстов Лескова, определенных как тексты Бажова, 18 – число правильно определенных текстов Лескова, 99 – число текстов Бажова, определенных как тексты Лескова, 2406 – число правильно определенных текстов Бажова

Итак, в посте описана возможность использования метода Кульбака-Лейблера для поиска текстовых аномалий при наличии размеченного датасета с образцами исключительно аномального класса. Разобран пример с несбалансированными по размеру датасетами (2535 строк vs. 213 строк).

Метод Кульбака-Лейблера показал хорошие результаты, в отличие от метода одноклассовой классификации на основе SVM: с нулевыми потерями по текстам Бажова в противовес 4% для SVM и с 4-мя оставленными в датасете текстами Лескова против 12 для SVM.

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

Полный код, список стоп-слов и датасеты для тренировки можно найти по ссылке.