на главную ] 

Автоматизированная обработка
текстов на естественном языке,
с использованием инструментов
языка Python

Евгений Борисов

вторник, 24 января 2017 г.

В этой статье мы поговорим о методах классификации и кластеризации текстов на естественном (русском) языке, а так же рассмотрим примеры реализаций решений этих задач на языке 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 групп по темам.

from sklearn.datasets import fetch_20newsgroups # загрузка набора twenty = fetch_20newsgroups(data_home='data/',subset=subset, categories=categories, shuffle=True, random_state=42) print("размер:",len(twenty.data)) print("метки классов: ",twenty.target_names) print("пример:") print("\n".join(twenty.data[0].split("\n")[:3]) )
Листинг 1: пример использования набора 20newsgroups

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

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

from Stemmer import Stemmer stemmer = Stemmer('russian') text = ' '.join( stemmer.stemWords( text.split() ) )
Листинг 2: пример использования Stemmer

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

from sklearn.feature_extraction.text import CountVectorizer from sklearn.feature_extraction.text import TfidfTransformer from sklearn.linear_model import SGDClassifier from sklearn.pipeline import Pipeline from sklearn.metrics import accuracy_score text_clf = Pipeline([ ('countvect', CountVectorizer() ), ('tfidf', TfidfTransformer(use_idf=False)), ('clf', SGDClassifier(loss='hinge')), ]) text_clf.fit(x, y) predicted = text_clf.predict( x ) print( accuracy_score( y , predicted) )
Листинг 3: пример использования инструментов частотного анализа текстов в Scikit-learn

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

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

ПОЛИТИКА: По Киеву ходит пугач Соланы... протестуют в Киеве против вступления Украины в НАТО.Они собрались на Майдане Независимости возле памятника Независимости, сообщает УНИАН.Протестующие держат в руках флаги ... ... народа Украины - быть с Россией и Беларусью!".По словам агентства, "сейчас приверженцы Витренко проводят митинг, на котором выступают лидеры ПСПУ".Последние высказывают ... КУЛЬТУРА: Вчера вечером в Японии состоялась премьера голливудского фильма о гейшах, вызвавшая негодование в связи с тем, что эти девушки представлены проститутками, а играющие их актрисы - китаянки. Мало того, что главные роли фильма "Мемуары гейши" исполнили китайские актрисы, он еще и снят ...
Листинг 4: примеры из учебного набора текстов

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

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


Рис 1: скриншот утилиты управления БД текстов

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

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

метод извлечения признаков результат (accuracy )
TF0.864788732394
TF + хеширование0.872300469484
TF-IDF0.893114241002
TF-IDF + стеминг 0.890610328638
TF-IDF + стеминг + n-grams 0.840219092332
Таблица 1: результаты экспериментов

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

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

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

КЛАСТЕР 1: Около 18 тысяч человек покинули подконтрольные боевикам районы Алеппо За минувшие сутки из подконтрольных боевикам районов сирийского города Алеппо было выведено около 17,971 тысячи жителей, в их числе 7,542 тысячи детей. Об этом в субботу, 10 декабря, сообщает ТАСС со ссылкой на российский Центр примирения враждующих сторон в Арабской Республике. Битва за Алеппо: повстанцы просят дать им вывезти раненых Сирийские повстанцы просят о пятидневном перемирии, чтобы эвакуировать раненых из районов в восточной части Алеппо, после того как они вывели все свои отряды из исторического центра — Старого города. КЛАСТЕР 2: Лидер Радикальной партии Олег Ляшко раскритиковал депутата Верховной рады Украины от партии «Батькивщина» Надежду Савченко за встречу с главами самопровозглашенных Донецкой и Луганской народных республик (ДНР и ЛНР) Александром Захарченко и Игорем Плотницким. Лидер Радикальной партии Украины Олег Ляшко назвал Надежду Савченко госизменницей. Политик призвал лишить наводчицу мандата народного депутата "То, что сейчас чудит Савченко, — это государственная измена. За подобные действия ей надо немедленно запретить доступ к государственной тайне, отозвать из ПАСЕ и лишить мандата народного депутата Украины", — написал Ляшко на странице в Facebook. Лидер украинской "Радикальной партии" Олег Ляшко назвал переговоры депутата Верховной рады от партии "Батькивщина" Надежды Савченко, ранее осужденной в России по делу об убийстве журналистов в Донбассе и помилованной президентом РФ, с главами самопровозглашенных Луганской и Донецкой народных республик государственной изменой. КЛАСТЕР 3: Финальная распродажа! Chery Tiggo от 19990 руб (199,9 млн) «Китайские автомобили» объявляют финальную распродажу популярных кроссоверов Chery Tiggo FL! На автомобили в максимальной комплектации установлена специальная цена 19 990 рублей (199,9 млн). Количество автомобилей ограничено! "Черная суббота" Не успели купить новый автомобиль в «черную пятницу»? Не нашли ничего подходящего в дилерских автосалонах? Не беда: автосалон «Китайские автомобили» объявляет «черные субботы»! «Черная суббота» — это не шестой трудовой день в советской стране, а желанный праздник для покупателей новеньких авто!
Листинг 5: примеры похожих текстов объединённых системой в один кластер

Текст программы на 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
Яндекс.Метрика
TOP.zp.ua PR-CY.ru
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.