В поисках аномалии: одноклассовая классификация текстов с помощью расхождения Кульбака—Лейблера
Привет, Хабр! На связи участница профессионального сообщества 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 resultDKL (P‖Q) — безразмерная величина. Чему она может быть равна? Если два распределения в разрезе слов полностью совпадают, то получим DKL (P‖Q)=0. Если слово редкое, то получим отрицательное значение. Оба эти случая мне неинтересны: либо потому, что это низкочастотное слово, либо потому, что в обоих корпусах слово одинаково распределено. Поэтому их отсекаю, принимая отсечку по DKL (P‖Q) на уровне 0,0001:
# рассчитаем расхождение Кульбака—Лейблера для лемм малого набора
outliers = top_KLD_outliers(investigate, reference, 0.0001, False)В итоге получаем список специфичных слов с соответствующими значениями DKL (P‖Q). Таким образом получилось 781 слово (а точнее 781 лемма), самые специфичные из которых — «говорить» и «государь».
Нужно помнить, что расхождение Кульбака—Лейблера является несимметричной мерой, то есть может быть DKL (P‖Q) ≠ DKL (Q‖P). Поэтому всегда важно правильно определять эталонный и референсный корпуса.
Поиск
Следующий этап — поиск текстов Лескова в наборе с текстами Бажова. Для каждого слова из текстов большого набора, проверяю есть ли оно среди специфичных слов, и если есть, то беру его DKL (P‖Q). Далее, суммирую все DKL (P‖Q), а затем, для учёта размера текста, умножаю эту сумму на количество специфичных слов и делю на общее количество слов текста после чистки.
После сортировки по убыванию по ΣDKL (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 — тексты Бажова. Проверка контрольной колонки подтверждает это.
График топ-50 текстов большого набора в разрезе специфичности.
А вот между точками со специфичностью 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))
Поиск осечки аномалий по точке перегиба кривой специфичности текстов: синяя линия — изначальный (зашумленный) график специфичности; оранжевая линия — сглаженный график специфичности; зеленая линия — график второй производной функции специфичности (масштабированный). При х = 26 вторая производная меняет свой знак. Так мы находим точку перегиба функции специфичности (26; 0,74).
И затем сохраняю результат:
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)
Матрица несоответствий для метода One-class SVM Classification: Actual label — фактическая метка, Predicted label — предсказанная метка; 12 — количество текстов Лескова, определённых как тексты Бажова, 18 — количество правильно определённых текстов Лескова, 99 — количество текстов Бажова, определённых как тексты Лескова, 2406 — количество правильно определённых текстов Бажова.
Заключение
Итак, в посте описана возможность использования метода Кульбака—Лейблера для поиска текстовых аномалий при наличии размеченного набора с образцами исключительно аномального класса. Разобран пример с несбалансированными по размеру наборами (2535 строк vs. 213 строк).
Метод Кульбака—Лейблера показал хорошие результаты, в отличие от метода одноклассовой классификации на основе SVM: с нулевыми потерями по текстам Бажова в противовес 4% для SVM и с четырьмя оставленными в наборе текстами Лескова против 12 для SVM. Точно так же можно искать необычные события в логах, письма от мошенников, аномальные заявки, ошибочно попавшие не в свою очередь.
Полный код, список стоп-слов и наборы для обучения можно найти по ссылке.
