[ на главную ] 

В этой статье мы поговорим о методах классификации и кластеризации текстов на естественном (русском) языке, а так же рассмотрим примеры реализаций решений этих задач на языке Python с помощью библиотеки Scikit-learn.

1. Введение

Интернет содержит гигантское количество различных текстов, человек давно перестал самостоятельно справляться с этим потоком информации, чтобы найти что-то в этом океане слов мы пользуемся специальными техническими средствами - поисковыми роботами, агрегаторами новостей, спам-фильтрами и т.п. Актуальность задач эффективной автоматизированной обработки текстов на естественных языках (NLP) не спадает. В этой статье мы рассмотрим следующие часто встречающиеся практические задачи: сортировка текстов по темам и поиск похожих текстов.

2. Формализация задачи

Для решения, упомянутых выше задач, будем применять методы машинного обучения. Чтобы их использовать нам понадобится размеченный набор текстов $T$ для обучения системы, т.е. каждому учебному тексту присваивается метка определённого класса. Также необходимо выбрать способ формализации этих данных, т.е. некоторым способом построить отображение $f$ из множества текстов $T$ в пространство признаков $X$ \begin{equation} f:T\rightarrow X \end{equation}

Функцию $f$ называют процедурой излечения признаков или feature extraction.

После того как мы определим $f$ и пространство признаков $X$ будет построено, каждому тексту из $T$ поставлена в соответствие точка из $Х$, мы получаем возможность применять весь арсенал математических методов для разделения всех точек $Х$ на подмножества.

Так задача поиска похожих текстов это есть задача кластеризации точек из $X$, задача сортировки текстов по темам сводиться к задаче классификации точек из $X$.

Формально говоря, нам необходимо построить отображение $g$ из множества вектор-признаков $X$ во множество меток $L$. \begin{equation} g:X\rightarrow L \end{equation}

Таким образом наша задача обработки текста разделяется на два основных этапа.

1. построение пространства признаков (извлечение признаков)
2. разделение пространства признаков на части

Далее мы поговорим о методах извлечения признаков из текста.

3. Извлечение признаков из текста

В этом разделе опишем метод извлечения признаков из текста под называнием частотный анализ (другое название - мешок слов) [1] и его модификации.

Для формирования вектора признаков текста, частотный анализ считает количество повторов каждого слова в тексте.

Если более детально, то схема частотного анализа выглядит следующим образом.

1. построить словарь $V$ из всех слов, используемых в исходных текстах $T$
2. для каждого текста $t_i \in T$
   и для каждого слова из словаря $v_j \in V$,
   посчитать число вхождений $x_{ij}$ слова $v_j$ в текст $t_i$

Таким образом для каждого текста $t_i \in T$ мы получаем вектор целых неотрицательных чисел $x_i$, длинна которого равна количеству слов в словаре $V$.
Это базовый вид метода частотного анализа текстов.

Для текстов разного размера величина значений частоты $x$ может сильно отличаться, т.е. чем больше текст тем больше может быть повторов слов. Для уменьшения этого эффекта применяется метод нормализованного частотного анализа или TF (term frequency) [2], значения частоты $x$ делятся на общее число слов в тексте $t$. \begin{equation} TF(t,V) = \frac{x(t,V)}{size(t)} \end{equation}

4. О словаре для частотного анализа

Формирование словаря - важная часть работы системы обработки текстов. От того какие слова там окажутся, зависит информативность вектор-признаков и соответственно качество работы системы. Словарь формируется из всего набора текстов исходя из задачи.

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

Однако, для задачи определения авторства текста частота употребления предлогов может оказаться очень даже полезными признаками.

Удалять часто употребляемые слова или нет? Существует компромиссный вариант формирования вектор-признаков. Имя ему TF-IDF [2], этот метод не выбрасывает часто употребляемые слова из словаря но уменьшает их вес в вектор-признаке. Для этого для всех слов словаря вычисляется коэффициент обратной частоты IDF (inverse document frequency), выглядит это следующим образом. \begin{equation} IDF(v_i) = \log \frac{ size(T) }{ size(T(v_i)) } \end{equation} т.е. логарифм дроби, у которой в числителе общее количество текстов, а в знаменателе количество текстов содержащих слово $v_i$, т.е. чем чаще встречается слово тем меньше значение его IDF.

Итоговая частотная характеристика выглядит как произведение частотной характеристики TF на коэффициент обратной частоты IDF. \begin{equation} TFIDF(t,T,v) = TF(t,v) \cdot IDF(t,T,v) \end{equation}

Здесь нужно упомянуть ещё один способ составления словарей - использования N-грамм[3] (N-grams). В словарь частотного анализа мы можем включать не только отдельные слова но и словосочетания (упорядоченные цепочки слов) длинны не более N слов. Это увеличит размер нашего словаря (снижая производительность), но в некоторых случаях может повысить качество работы.

Далее мы поговорим об предварительной очистке текста.

5. Предварительная обработка текстов

Мы разобрались с тем как строить частотные характеристики для текстов, однако тут существует ещё одно затруднение. В сложных естественных языках (таких как русский язык) одно и то же слово может принимать разные формы (падежи), и в словарь частотного анализа могут попадать все словоформы, отличающиеся предлогами и/или окончаниями. Из-за этого может сильно увеличиваться размер словаря и соответственно размер набора данных для обучения, что может вызывать падение производительности системы и ухудшать обобщающие способности классификатора (переобучение).

Существует несколько способов решения этой задачи.

Первый это лематизация [4] - все слова в тексте приводятся к нормальной форме (единственное число, именительного падежа). Лематизация требует словарей языков, на которых написан текст, она выполняет поиск для всех слов текста их нормальной формы по словарям и это может существенно снижать производительность.

Второй метод это стеминг [5] - выделение основы слов путём отбрасывания приставок и окончаний. Этот способ нормализации текста работает гораздо быстрее чем лематизация. Он менее качественный но для частотного анализа его вполне достаточно.

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

6. Общая схема системы

В предыдущих разделах мы рассмотрели задачу извлечения признаков и предварительной обработки данных, далее представим схему работы системы обработки текстов.

1. собрать и разметить учебные тексты $T$
2. удалить из текстов лишние слова (исходя из задачи)
3. выполнить стеминг (нормализация слов)
4. построить словарь $V$ из очищенного набора текстов $T$
5. с помощью словаря $V$ выполнить частотный анализ текстов
6. построить матрицу учебных примеров $X$ из векторов частотных характеристик и списка меток текстов $L$
7. случайным образом перемешать набор $X$ (переставить строки матрицы)
8. разделить набор $X$ на две части - учебный набор $X_l$, тестовый набор $X_t$
9. обучить классификатор (или кластеризатор) $g$ на наборе $X_l$ и сохранить его параметры $W$
10. протестировать качество работы системы на наборе $X_t$

Далее мы рассмотрим реализацию описанной выше схемы средствами языка Python.

7. Реализация на Python

И так, мы описали все части системы, теперь можно приступать к реализации, для этого воспользуемся языком Python и библиотекой Scikit-learn (http://scikit-learn.org). Последняя представляет собой большой набор реализаций разных методов машинного обучения и связанных с этим функций.

Начнём с данных, Scikit-learn содержит в себе различные наборы данных для тестирования программ, среди них набор 20newsgroups из репозитория UCI (https://archive.ics.uci.edu/ml/datasets/Twenty+Newsgroups). Этот набор содержит 20 тысяч новостных сообщений на английском языке разбитых на 20 групп по темам.

Как уже говорилось - тексты на английском языке, тексты на русском языке придётся добывать самостоятельно.

Второй инструмент, который мы рассмотрим, это Stemmer (http://snowball.tartarus.org) для выполнения стеминга (выделения основы слов), этот пакет имеет поддержку русского языка. Stemmer не является частью Scikit-learn и устанавливается отдельно (например с помощью утилиты pip).

Для выполнения частотного анализа в Scikit-learn есть следующие инструменты.

• CountVectorizer - составляет словарь и заменяет слова в тексте номерами в словаре.
• HashingVectorizer - аналогичная функциональность CountVectorizer но с предварительным хешированием слов в тексте
• TfidfTransformer - частотный анализатор TF-IDF
• TfidfVectorizer - CountVectorizer и TfidfTransformer в одной упаковке

8. Тесты и результаты

Тесты будем проводить на наборе из 3196 текстов на русском языке, разбитых на 13 групп по темам. Ниже приведены примеры текстов из набора.

Сами тексты в формате sqlite можно скачать [здесь].

Для удобства пользования БД текстов, [здесь] можно скачать специальную утилиту - вебинтерфейс к этой БД, основанный на Flask (http://flask.pocoo.org/).

8.1 Сортировка текстов по темам

Первым протестируем работу классификатора, т.е. решение задачи сортировки текста по темам. В качестве классификатора использовалась логистическая регрессия [6] из пакета Scikit-learn. Ниже представлены результаты для различных характеристических функций (частотный анализ с предобработкой), для каждого выполнялось тестирование на 10 случайных разбиениях набора (учебный и тестовый), в таблице 1 приведены средняя точность (accuracy) классификатора на тестовых наборах. Наилучший результат показал TF-IDF без предварительной очистки текстов.

Текст программы на Python можно скачать [здесь].

8.2 Поиск похожих текстов

Далее рассмотрим работу кластеризатора, т.е. решение задачи поиска похожих текстов. Поиск похожих текстов выполняется аналогичным классификации образом, только вместо логистической регрессии выполняется кластеризация - KMeans [7] из пакета Scikit-learn. Ниже представлены результаты работы системы кластеризации.

Текст программы на Python можно скачать [здесь].

9. Заключение

Описанный в этой статье метод частотного анализа текстов - не универсален. Например, метод может не достаточно хорошо работать на больших текстах, где частотная характеристика может размываться большим количеством разных слов. На очень маленьких текстах тоже могут быть не лучшие результаты, потому как мало информации для частотного анализа. Этот метод может давать сбои на задачах где важен порядок слов в тексте. В остальных случаях частотный анализ текстов можно успешно применять для автоматической сортировки массива текстов.

Литература

1. Е.С.Борисов Классификатор текстов на естественном языке.
   - http://mechanoid.kiev.ua/neural-net-classifier-text.html
2. Wikipedia: TF-IDF - https://en.wikipedia.org/wiki/Tf-idf
3. Wikipedia: N-gram - https://en.wikipedia.org/wiki/N-gram
4. Wikipedia: Lemmatisation - https://en.wikipedia.org/wiki/Lemmatisation
5. Wikipedia: Stemming - https://en.wikipedia.org/wiki/Stemming
6. Е.С.Борисов Классификатор на основе логистической регрессии.
   - http://mechanoid.kiev.ua/ml-regression-class.html
7. Е.С.Борисов Кластеризатор на основе алгоритма k-means.
   - http://mechanoid.kiev.ua/ml-k-means.html