4gophers

Классификация текста

Перевод статьи "Text classification"

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

supervised

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

Обработка входных данных

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

Разбивка текста на отдельные слова называется токенизацией. Но для повышения точности нужно выполнить еще ряд шагов. Один из самых важных шагов - это удаление стоп слов. Нам необходимо удалить слишком часто встречающиеся слова и слова без значительного семантического смысла. В английском языке это at, which, and, so, a, an и еще много такого. Еще нужно провести нормализацию всех слов, выполнить стемминг и привести все слова к их нормальной форме. Это позволит объединить разные формы слова, например слова "работать", "работал", "работали" будет приведено к "работа". Тут нужно учесть, что для классификации все эти слова объединяться, и частота будет считаться как для одного слова. Кстати, основа слова не всегда совпадает с морфологическим корнем слова. Можно использовать леммизацию. С ее помощью можно находить правильные морфологические основы, что позволит сохранить смысл слова. Но для леммизации нужно использовать словари. И это значительно более затратный процесс, чем стемминг. И последнее - не забудьте про приведение всех слов к одному регистру.

Наивная Байесовская Классификация

Наивная Байесовская классификация это вероятностная классификация, которая предсказывает распределение по списку определенных классов. Она основана на теореме Байеса, которая позволяет рассчитать вероятность некоторого события на основании факта что произошло некоторое другое событие. Формула для решения задачи классификации формулируется следующим уравнением:

Bayes theorem

в которой C это класс, а D это сам документ. С помощью этой теоремы вычисляется вероятность присвоения класса C документу D, при условии, что мы знаем вероятность отношения документа D к классу С и независимые вероятности для C и для D. Вероятность для документа это единица, поэтому мы не будем ее учитывать в наших расчетах. Вероятность для класса равна количеству документов в обучающем наборе, принадлежащих этому классу, разделенная на количество всех документов. Осталось разобраться с вероятностью отношения документа D к классу C. Под словом "наивная" скрывается допущение что все слова в документе не зависят друг от друга, в таком случае, мы можем вычислить вероятность как сумму вероятностей для каждого отдельного слова.

Существует много различных Байесовских классификаторов. Они делают разные допущения о распределении вероятностей для различных классов. Например, для Бернули классификатора учитывается только количество вхождений определенного слова. Мультиномиальная классификация учитывает еще и частоту вхождения. Вероятность присвоения класса для конкретного слова в мультиномиальном классификаторе можно выразить как:

где:

  • count(w, C) - количество сколько раз слово w было отнесено к классу C на обучающих данных.
  • count(C) - количество всех слов отнесенных к классу C.
  • V - количество уникальных слов в тренировочных данных.
  • α - параметр для сглаживания, предотвращает 0 вероятности(α=1 используется для сглаживания Лапласа).

Давайте теперь немного поэкспериментируем.

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

type Classifier struct {
    classPerWordCount map[string]int
    classPerDocument  map[string]int
    wordClassCount    map[string]map[string]int
    documentsCount    int
}

// Train the classifier with text and its class.
func (c *Classifier) Train(words []string, class string) {
    c.documentsCount++
    c.incrementDocumentPerClass(class)

    for _, word := range words {
        c.incrementWordClass(word, class)
        c.incrementClassPerWord(class)
    }
}

После стадии обучения наш классификатор готов для расчета предсказаний классов новых документов. Мы будем присваивать документу класс, который предсказан с наибольшей вероятностью.


func (c *Classifier) Classify(words []string) (string, float64) { var score float64 var prediction string for _, class := range c.classes() { var probability = c.probability(words, class) if score < probability { score = probability prediction = class } } return prediction, score }

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

Mar 8, 2017
comments powered by Disqus