Категоризация текста с помощью анализа настроений с помощью Go

Недавно я читал Мастер-алгоритм Педро Домингоса. Это увлекательное чтение, с некоторыми интересными мыслями. В книге Домингос предложил отнести алгоритмы машинного обучения к одному из 5 племен — символистов, коннекционистов, эволюционистов, байесовцев и аналогизаторов. У каждого из этих племен есть собственный мастер-алгоритм. Символисты — это обратная дедукция (дерево решений), коннекционисты — это обратное распространение (нейронная сеть), эволюционисты — это генетическое программирование (генетические алгоритмы), байесовцы — это теорема Байеса, а аналогизаторы — это машина опорных векторов (SVM). ).

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

Я хотел сделать несколько вещей. Во-первых, я перепишу его на Go. Код Ruby работает отлично, но всегда приятно вернуться к старому коду и посмотреть, как я могу его улучшить. Во-вторых, я буду использовать его для довольно популярной цели — для анализа настроений (об этом я расскажу позже). Наконец, я буду тренировать и тестировать его с помощью надлежащего набора данных для обучения и тестирования (в моем предыдущем посте в блоге этого не было).

Теорема Байеса

Прежде чем мы начнем с теоремы Байеса, давайте вернемся к основам и поговорим о вероятностях. вероятность — это вероятность того, что что-то произойдет. В математике мы представляем ее как число от 0 до 1, где 0 означает, что это никогда не произойдет, а 1 означает, что это произойдет всегда.

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

Чтобы представить это математически, предположим, что вероятность того, что вы выйдете на улицу, независимо от того, что произойдет, равна A, а вероятность плохой погоды равна B, тогда условная вероятность того, что вы выйдете на улицу, в зависимости от погоды, равна p(A|B) или если прочитать вслух, это «вероятность». А при заданном В'.

Совместная вероятность – это вероятность того, что оба события сбудутся. В нашем примере выше вероятность того, что вы выйдете на улицу в плохую погоду, равна p(A and B). Возможно, вы узнали (или сохранили смутные воспоминания из школьной математики), что если обе вероятности независимы друг от друга, то p(A and B) = p(A)p(B), то есть вероятность A и B, кратна независимой вероятности A и независимой вероятности B.

Однако мы только что узнали, что A на самом деле не является независимым от B, поэтому p(A) на самом деле является частным случаем p(A|B). Если идет дождь, это снижает вероятность того, что вы выйдете на улицу, поэтому p(A|B) < p(A). Другими словами, более общее математическое описание:

p(A and B) = p(A|B)p(B)

Поскольку A и B могут быть любым событием путем обобщения, вероятность соединения A и B коммутативна:

p(A and B) = p(B and A)

Если подставить уравнения:

p(A|B)p(B) = p(B|A)p(A)

Затем, чтобы получить условную вероятность p(A|B):

Это то, что известно как теорема Байеса (или закон Байеса, или правило Байеса).

Анализ настроений

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

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

Классификация документов с помощью теоремы Байеса

Классификатор — это просто то, что классифицирует другие вещи. Классификатор — это функция, которая принимает набор данных и сообщает нам, к какой категории или классификации принадлежат данные. Чтобы классифицировать текстовый документ, мы спрашиваем: для конкретного документа какова вероятность того, что он принадлежит к этой категории? Когда мы находим вероятности данного документа во всех категориях, классификатор выбирает категорию с наибольшей вероятностью и объявляет ее победителем, то есть документ, скорее всего, принадлежит к этой категории.

Давайте преобразуем нашу более раннюю математическую формулу в ту, которую мы можем использовать для классификации документов:

В приведенной выше формуле p(category|document) — это то, что мы хотим найти: для данного документа какова вероятность того, что он принадлежит к этой категории?

Точно так же p(document|category) — это вероятность того, что документ существует в этой категории, p(category) — это вероятность категории независимо от каких-либо документов, а p(document) — это вероятность документа независимо от каких-либо категорий.

На самом деле нам нужны только p(document|category) и p(category). Мы можем отбросить p(document), потому что он одинаков для каждой категории.

Так как же нам найти p(document|category)? Документ состоит из набора слов, поэтому вероятность документа равна объединенной вероятности всех слов в документе. Вероятность документа с заданной категорией — это объединенная вероятность всех слов в документе внутри категории.

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

Вероятность p(category) относительно проста, это просто количество документов в категории по отношению к общему количеству документов во всех категориях.

Это достаточно просто. Давайте перейдем к коду.

Наивный байесовский классификатор в Go

Создать классификатор

Мы начнем с создания универсального наивного байесовского текстового классификатора в файле с именем classifier.go.

Сначала мы создаем структуру Classifier.

// Classifier is what we use to classify documents
type Classifier struct {
	words               map[string]map[string]int
	totalWords          int
	categoriesDocuments map[string]int
	totalDocuments      int
	categoriesWords     map[string]int
	threshold           float64
}

// create and initialize the classifier
func createClassifier(categories []string, threshold float64) (c Classifier) {
	c = Classifier{
		words:               make(map[string]map[string]int),
		totalWords:          0,
		categoriesDocuments: make(map[string]int),
		totalDocuments:      0,
		categoriesWords:     make(map[string]int),
		threshold:           threshold,
	}

	for _, category := range categories {
		c.words[category] = make(map[string]int)
		c.categoriesDocuments[category] = 0
		c.categoriesWords[category] = 0
	}
	return
}

В структуре words — это карта карт, которые представляют слова, обученные классификатором. Выглядит примерно так (не совсем так):

{
    "1": {
        "good": 10,
        "wonderful": 5,
        "amazing": 7,
    },
    "0": {
        "awful": 6,
        "loud": 4,
    }
}

Поле totalWords — это общее количество слов в классификаторе, а поле totalDocuments — это общее количество документов в классификаторе.

Поле categoriesDocuments представляет собой карту, на которой указано количество документов в каждой категории:

{
    "1": 13,
    "0": 16,
}

Поле categoriesWords представляет собой карту, на которой указано количество слов в каждой категории:

{
    "1": 35,
    "0": 44,
}

Я опишу threshold позже.

Подсчет слов

Сердце классификатора действительно заключается в подсчете слов, так что давайте посмотрим на это дальше. Для этого у нас есть функция countWords, которая передает документ и возвращает карту количества появлений каждого слова.

var cleaner = regexp.MustCompile(`[^\w\s]`)
// truncated list
var stopWords = map[string]bool{"a": true, "able": true, "about": true, ..., "you've": true, "z": true, "zero": true}

// clean up and split words in document, then stem each word and count the occurrence
func countWords(document string) (wordCount map[string]int) {
	cleaned := cleaner.ReplaceAllString(document, "")
	words := strings.Split(cleaned, " ")
	wordCount = make(map[string]int)
	for _, word := range words {
		if !stopWords[word] {
			key := stem(strings.ToLower(word))
			wordCount[key]++
		}
	}
	return
}

// stem a word using the Snowball algorithm
func stem(word string) string {
	stemmed, err := snowball.Stem(word, "english", true)
	if err == nil {
		return stemmed
	}
	fmt.Println("Cannot stem word:", word)
	return word
}

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

Нам не нужны все слова в документе, нам нужны только ключевые слова, поэтому мы удаляем из документа все часто встречающиеся слова, например, мы будем игнорировать слова статьи, такие как a , the, такие местоимения, как он, она и т. д. Поэтому мы используем список стоп-слов и отфильтровываем эти общие слова. Остальные будут переведены в нижний регистр, чтобы сделать ключ согласованным.

Многие слова имеют разные вариации, например, существительные могут стоять во множественном числе ( cat и cats нужно считать вместе), глаголы могут иметь времена ( eat, еда и съела должны учитываться вместе) и так далее. Чтобы не пересчитывать вариации слов дважды, мы используем технику, называемую стемминг. В нашем классификаторе я использовал библиотеку стеммеров Snowball на основе алгоритма Snowball.

Наконец количество слов суммируется и возвращается.

Обучение классификатора

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

// Train the classifier
func (c *Classifier) Train(category string, document string) {
	for word, count := range countWords(document) {
		c.words[category][word] += count
		c.categoriesWords[category] += count
		c.totalWords += count
	}
	c.categoriesDocuments[category]++
	c.totalDocuments++
}

Классификация документов

Здесь начинается настоящее действие. Прежде чем перейти к методу Classify, давайте еще раз посмотрим на уравнение:

p(category|document) = p(document|category)p(category)

Мы создадим метод для расчета каждой из вероятностей. Начнем с p(category).

// p (category)
func (c *Classifier) pCategory(category string) float64 {
	return float64(c.categoriesDocuments[category]) / float64(c.totalDocuments)
}

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

Далее мы смотрим на p(document|category).

// p (document | category)
func (c *Classifier) pDocumentCategory(category string, document string) (p float64) {
	p = 1.0
	for word := range countWords(document) {
		p = p * c.pWordCategory(category, word)
	}
	return p
}

func (c *Classifier) pWordCategory(category string, word string) float64 {
	return float64(c.words[category][stem(word)]+1) / float64(c.categoriesWords[category])
}

Во-первых, мы используем countWords, чтобы получить количество слов в документе. На самом деле нас здесь не волнует количество слов, нам просто нужен список ключевых слов в документе. Для каждого ключевого слова мы находим его вероятность в категории. Это просто количество вхождений этого ключевого слова в категории, деленное на общее количество слов в категории. Например, после обучения классификатора, скажем, для категории 1 (что является положительным), у нас есть 10 вхождений слова «хорошо». в то время как у нас есть в общей сложности 100 слов в категории 1. Это означает, что вероятность слова в категории равна 0.1.

Мы делаем это для каждого ключевого слова в документе, затем умножаем все эти вероятности, и это будет p(document|category).

Наконец мы находим p(category|document), что довольно тривиально.

// p (category | document)
func (c *Classifier) pCategoryDocument(category string, document string) float64 {
	return c.pDocumentCategory(category, document) * c.pCategory(category)
}

Теперь, когда у нас есть условные вероятности каждой категории, мы объединим их в одну карту.

// Probabilities of each category
func (c *Classifier) Probabilities(document string) (p map[string]float64) {
	p = make(map[string]float64)
	for category := range c.words {
		p[category] = c.pCategoryDocument(category, document)
	}
	return
}

Это будет использоваться нашим методом Classify.

// Classify a document
func (c *Classifier) Classify(document string) (category string) {
	// get all the probabilities of each category
	prob := c.Probabilities(document)

	// sort the categories according to probabilities
	var sp []sorted
	for c, p := range prob {
		sp = append(sp, sorted{c, p})
	}
	sort.Slice(sp, func(i, j int) bool {
		return sp[i].probability > sp[j].probability
	})

	// if the highest probability is above threshold select that
	if sp[0].probability/sp[1].probability > c.threshold {
		category = sp[0].category
	} else {
		category = "unknown"
	}

	return
}

Наш метод Classify сортирует категории по вероятности и определяет верхнюю категорию. Но это не конец. Может быть шанс, что разница между высшей и второй категориями очень мала. Например, возьмем в качестве примера классификацию электронных писем как спам и не спам и предположим, что вероятности таковы: спам составляет 51%, а не спам — 49%. Должен ли документ классифицироваться как спам? Это зависит от того, насколько строгим должен быть классификатор.

Это причина для поля threshold, которое является пороговым соотношением для разделения категорий. Например, если threshold равно 1.5, это означает, что категория с наибольшей вероятностью должна быть в 1,5 раза выше, чем вторая по величине вероятность. Если высшая категория не достигает порогового значения, мы классифицируем ее как unknown.

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

Анализ настроений с использованием наивного байесовского классификатора

Для этого сообщения в блоге я использую Набор данных Sentiment Labeled Sentences Data Set, созданный Димитриосом Котзиасом для статьи От групповых к индивидуальным меткам с использованием глубоких функций, Kotzias et. аль,. KDD 2015. Этот набор данных содержит 1000 комментариев с каждого из веб-сайтов Amazon, IMDB и Yelp, помеченных либо 1 для положительных комментариев, либо 0 для отрицательных комментариев. Комментарии извлекаются из обзоров продуктов, фильмов и ресторанов соответственно.

Во-первых, давайте посмотрим, как настраиваются данные.

Настройка данных

Я разделяю каждый набор данных на обучающие и тестовые наборы данных и использую обучающий набор данных для обучения классификатора, а тестовый набор данных — для проверки классификатора. Это делается с помощью функции setupData.

// datasets
type document struct {
	sentiment string
	text      string
}

var train []document
var test []document

// set up data for training and testing
func setupData(file string) {
	rand.Seed(time.Now().UTC().UnixNano())
	data, err := readLines(file)
	if err != nil {
		fmt.Println("Cannot read file", err)
		os.Exit(1)
	}
	for _, line := range data {
		s := strings.Split(line, "|")
		doc, sentiment := s[0], s[1]

		if rand.Float64() > testPercentage {
			train = append(train, document{sentiment, doc})
		} else {
			test = append(test, document{sentiment, doc})
		}
	}
}

// read the file line by line
func readLines(path string) ([]string, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	var lines []string
	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}
	return lines, scanner.Err()
}

Я использую переменную testPercentage, чтобы получить процент всего набора данных, который будет тестовым набором данных. Это, в свою очередь, используется для случайного выбора количества записей, которые должны быть в тестовом наборе данных.

Создайте классификатор документов

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

// parameters
var (
	testPercentage = 0.1
	datafile       = "amazon.txt"
	threshold      = 1.1
)

var categories = []string{"1", "0"}

func main() {
	setupData(datafile)
	fmt.Println("Data file used:", datafile)
	fmt.Println("no of docs in TRAIN dataset:", len(train))
	fmt.Println("no of docs in TEST dataset:", len(test))

	c := createClassifier(categories, threshold)

...

Обучите классификатор с набором данных поезда

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

...
	// train on train dataset
	for _, doc := range train {
		c.Train(doc.sentiment, doc.text)
    }
...

Тестовый классификатор на тестовом наборе данных

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

...
	// validate on test dataset
	count, accurates, unknowns := 0, 0, 0
	for _, doc := range test {
		count++
		sentiment := c.Classify(doc.text)
		if sentiment == doc.sentiment {
			accurates++
		}
		if sentiment == "unknown" {
			unknowns++
		}
	}
	fmt.Printf("Accuracy on TEST dataset is %2.1f%% with %2.1f%% unknowns", float64(accurates)*100/float64(count), float64(unknowns)*100/float64(count))
...

Мы подсчитываем количество точных классификаций, а также неизвестных классификаций.

Тестовый классификатор на обучающем наборе данных

Мы также тестируем некоторые обучающие наборы данных для проверки работоспособности.

..
	// validate on the first 100 docs in the train dataset
	count, accurates, unknowns = 0, 0, 0
	for _, doc := range train[0:100] {
		count++
		sentiment := c.Classify(doc.text)
		if sentiment == doc.sentiment {
			accurates++
		}
		if sentiment == "unknown" {
			unknowns++
		}
	}
	fmt.Printf("\nAccuracy on TRAIN dataset is %2.1f%% with %2.1f%% unknowns", float64(accurates)*100/float64(count), float64(unknowns)*100/float64(count))
...

Посмотрим на результаты.

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

Вывод

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

Исходный код

Вы можете найти этот код в Github по адресу https://github.com/sausheong/gonb.

Ссылка

  1. В моем первоначальном посте в блоге много ссылок на книгу Тоби Сегарана Программирование коллективного разума.
  2. Увлекательная книга Педроса Домингоса Мастер-алгоритм вызвала этот пост и заслуживает второго упоминания.
  3. Книга Аллена Дауни Think Bayes превосходно описывает, что такое закон Байеса, и я взял некоторые советы из книги, когда описывал его в этом сообщении в блоге.
  4. Я использовал набор данных из статьи «От группы к отдельным меткам с использованием глубоких функций», Kotzias et. аль,. КДД 2015