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

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Привет, Хабр! На связи участница профессионального сообщества 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)

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

 D_{KL}(P\parallel Q)=\int_{X}^{}p\textrm{log}\frac{p}{q}d\mu

где µ — любая мера на 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

DKL(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), а затем, для учёта размера текста, умножаю эту сумму на количество специфичных слов и делю на общее количество слов текста после чистки.

Specificity_{text}=\frac{\sum DKL(P\parallel Q)\times N_{specific words}}{N_{clean words}}

После сортировки по убыванию по Σ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 текстов большого набора в разрезе специфичности.
График топ-50 текстов большого набора в разрезе специфичности.

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

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

Если важно оставить все целевые тексты, — а это тексты Бажова, — то можно отсечь по порогу 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).
Поиск осечки аномалий по точке перегиба кривой специфичности текстов: синяя линия — изначальный (зашумленный) график специфичности; оранжевая линия — сглаженный график специфичности; зеленая линия — график второй производной функции специфичности (масштабированный). При х = 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 — количество правильно определённых текстов Бажова.
Матрица несоответствий для метода One-class SVM Classification: Actual label — фактическая метка, Predicted label — предсказанная метка; 12 — количество текстов Лескова, определённых как тексты Бажова, 18 — количество правильно определённых текстов Лескова, 99 — количество текстов Бажова, определённых как тексты Лескова, 2406 — количество правильно определённых текстов Бажова.

Заключение

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

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

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

Источник: https://habr.com/ru/companies/sberbank/articles/783428/


Интересные статьи

Интересные статьи

Это третья часть из серии статей про компонентный подход. В предыдущей статье мы рассмотрели, как реализовать сложный экран, разбив его на набор простых компонентов. Применим эту же идею, чтобы органи...
Среди всего прочего в Leaseweb мы предлагаем нашим пользователям сервис Private Network, который позволяет им создать свою собственную частную сеть между другими продуктами Leaseweb.Для решения задачи...
Штош. Скорее всего, у многих в папке загрузок собиралась куча разных инсталляторов, архивов и прочих файлов. И вот наступает момент, когда из этой кучи экскрементов нужно...
Почему с помощью обычного полнотекстового поиска сложно искать очень короткие документы и как быть, если хочется это сделать. Читать дальше →
В первой части статьи мы рассмотрели основы работы с утилитой SIP, предназначенной для создания Python-обвязок (Python bindings) для библиотек, написанных на языках C и C++. Мы рассмотрели основн...