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

Привет, Хабр! На связи участница профессионального сообщества NTA Корсакова Елена.

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

Постановка задачи

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

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

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

Подготовка наборов данных

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

# загружаем малый набор import os fname = os.path.join('/kaggle/input/bazhov-leskov-dataset/Leskov.xlsx') with open(fname) as f:     target_corpus = pd.read_excel('/kaggle/input/bazhov-leskov-dataset/Leskov.xlsx')  # загружаем большой набор fname = os.path.join('/kaggle/input/bazhov-leskov-dataset/Bazhov.xlsx') with open(fname) as f:     reference_corpus = pd.read_excel('/kaggle/input/bazhov-leskov-dataset/Bazhov.xlsx')

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

Бажов:

Вот бы был наш Тимофеич дома, не то бы было. Спозаранок бы он разведал про незваных гостей и гостинцев бы им припас не столько. Напредки забыли бы дорогу к нашему городу! Дорогой человек по этому делу был. Зря его загубили!

Лесков:

«Ах, скажите, — говорю, — пожалуйста!» «Ну, Степан, — думаю, — Матвеич, отличную ж вы было со мной штуку подшутили! — и говорю, что, стало быть же, говорю, как я его теперь замечаю, он, однако, фортель!»

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

Подготовка текстов

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

# функция для очистки текстов def _remove_punct_num(sample):     import re     import string      remove = string.punctuation     remove = remove.replace('-', '') # don't remove hyphens     pattern = r'[{}]'.format(remove) # create the pattern     sample = re.sub(pattern, '', sample)     sample = re.sub('[«»]+', '', sample)     sample = re.sub('\\b\\d+(\\.\\d+)?%?', '', sample)     return sample  def text_to_lemmas_KLD(sample):     sample = _remove_punct_num(sample)     tokens = (str(sample)).split()     tokens = [morph.parse(tok.lower())[0].normal_form for tok in tokens if len(tok.lower())>3 and tok.lower() not in STOPLIST]     return tokens  # чистим тексты target_corpus['clean_text'] = target_corpus.text.apply(text_to_lemmas_KLD) reference_corpus['clean_text'] = reference_corpus.text.apply(text_to_lemmas_KLD)

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

«Ах, скажите, — говорю, — пожалуйста!» «Ну, Степан, — думаю, — Матвеич, отличную ж вы было со мной штуку подшутили!».

↓

[‘сказать’, ‘говорить’, ‘степан’, ‘думать’, ‘матвеевич’, ‘отличный’, ‘штука’, ‘подшутить’..]

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

Отбор слов: метод Кульбака—Лейблера

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

# проводим подсчет частот лемм в корпусах dictionary_to_investigate = sum((Counter(x) for x in target_corpus.clean_text), Counter()) dictionary_to_reference = sum((Counter(x) for x in reference_corpus.clean_text), Counter())  # функция подсчета относительных частот лемм в корпусах def count_freq(counter):     total = 0     for key in counter:         total += counter[key]     result = {}     for key in counter:         result[key] = counter[key] / total     return result  # считаем относительные частоты лемм в корпусах investigate = count_freq(dictionary_to_investigate) reference = count_freq(dictionary_to_reference)

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

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

# функция для расчета расхождения Кульбака-Лейблера def partial_KLD(px, qx):         if not all([px, qx]):             return 0         return px * log2(px/qx)     def top_KLD_outliers(p, q, threshold, include_new=True):     keys = set(p.keys()).union(q.keys())     result = {}     for key in keys:         if key in p and key not in q:             if include_new:                 result[key] = float('inf')         elif key in p and key in q:             pkld = partial_KLD(float(p[key]), float(q[key]))             if pkld > threshold:                 result[key] = pkld     return result

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

# рассчитаем расхождение Кульбака—Лейблера для лемм малого набора outliers = top_KLD_outliers(investigate, reference, 0.0001, False)

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

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

Поиск

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

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

# функция для расчета специфичности текстов  def find_specificity(cell):     total_specificity = 0     total_specific_words = 0     for key in cell:         total_clean_words = len(cell)         if key in outliers:             total_specificity += float(outliers[key])             total_specific_words += 1     return total_specificity*total_specific_words/total_clean_words  # строим рейтинг текстов большого набора по специфичности reference_corpus['specificity'] = reference_corpus['clean_text'].apply(find_specificity) reference_corpus = reference_corpus.sort_values(by='specificity', ascending=False)

Как правильно выбрать отсечку?

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

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

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

raw = reference_corpus.specificity.to_list() smooth = gaussian_filter1d(raw, 8) smooth_d2 = np.gradient(np.gradient(smooth)) inflection_points = np.where(np.diff(np.sign(smooth_d2)))[0]

А вот график:

# plot threshold results plt.plot(raw, label='Noisy Data') plt.plot(smooth, label='Smoothed Data') plt.plot(np.max(smooth)*(smooth_d2)/(np.max(smooth_d2)-np.min(smooth_d2)), label='Second Derivative (scaled)') for i, infl in enumerate(inflection_points, 1):     plt.axvline(x=infl, color='k', label=f'Inflection Point {i}') plt.legend(bbox_to_anchor=(1.55, 1.0))

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

reference_corpus[:inflection_points[0]].to_excel('KLD_result.xlsx', index=False)

Сравнение результатов с One-class SVM classification

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

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

# визуализируем матрицу несоответствий import numpy as np import matplotlib.pyplot as plt import seaborn as sns  class_names=[0,1] # name  of classes fig, ax = plt.subplots() tick_marks = np.arange(len(class_names)) plt.xticks(tick_marks, class_names) plt.yticks(tick_marks, class_names) # create heatmap sns.heatmap(pd.DataFrame(results), annot=True, cmap="YlGnBu",fmt='g', linewidths=1, linecolor='#dddddd', annot_kws={"size": 16}) ax.xaxis.set_label_position("top") plt.tight_layout() plt.title('Confusion matrix | One-class SVM classification', y=1.1) plt.ylabel('Actual label') plt.xlabel('Predicted label') for item in ([ax.title, ax.xaxis.label, ax.yaxis.label] +              ax.get_xticklabels() + ax.get_yticklabels()):     item.set_fontsize(16)

Заключение

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

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

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