30 мая 2011 в 00:33

Наивный Байесовский классификатор в 25 строк кода

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

И так, для примера возьму задачу определения пола по имени. Конечно, чтобы определить пол можно создать большой список имен с метками пола. Но этот список в любом случае будет неполон. Для того чтобы решить эту проблему, можно «натренировать» модель по маркированным именам.
Если интересует, прошу .

Немного теории


Пусть у нас есть строка текста O. Кроме того, имеются классы С, к одному из которых мы должны отнести строку. Нам необходимо найти такой класс с, при котором его вероятность для данной строки была бы максимальна. Математически это записывается так:

image

Вычислить P(C|O) сложно. Но можно воспользоваться теоремой Байеса и перейти к косвенным вероятностям:

image

Так как мы ищем максимум от функции, то знаменатель нас не интересует (он в данном случае константа). Кроме того, нужно взглянуть на строку O. Обычно, нет смысла работать со всей строкой. Намного эффективней выделить из нее определенные признаки (features). Таким образом формула примет вид:

image

Знаменатель нас не интересует. Числитель же можно переписать так.

image

Но это опять сложно. Здесь включаем «наивное» предположение о том, что переменные O зависят только от класса C, и не зависят друг от друга. Это сильно упрощение, но зачастую это работает. Числитель примет вид:

image

Финальная формула примет вид:

image (1)

Т.е. все что нужно сделать, это вычислить вероятности P( C ) и P(O|C). Вычисление этих параметров и называется тренировкой классификатора.

Код


Ниже — код на питоне. Содержит всего две функции: одна для тренировки (подсчета параметров формулы), другая для классификации (непосредственный расчет формулы).

from __future__ import division
from collections import defaultdict
from math import log

def train(samples):
    classes, freq = defaultdict(lambda:0), defaultdict(lambda:0)
    for feats, label in samples:
        classes[label] += 1                 # count classes frequencies
        for feat in feats:
            freq[label, feat] += 1          # count features frequencies

    for label, feat in freq:                # normalize features frequencies
        freq[label, feat] /= classes[label]
    for c in classes:                       # normalize classes frequencies
        classes[c] /= len(samples)

    return classes, freq                    # return P(C) and P(O|C)

def classify(classifier, feats):
    classes, prob = classifier
    return min(classes.keys(),              # calculate argmin(-log(C|O))
        key = lambda cl: -log(classes[cl]) + \
            sum(-log(prob.get((cl,feat), 10**(-7))) for feat in feats))


В функции train первые пять строк производят подсчет количества классов C, а также частоту появления фич O и С в одном семпле. Вторая часть метода просто нормирует эти частоты. Таким образом на выходе получаются вероятности P© и P(O|C).

В функции classify происходит поиск наиболее вероятного класса. Единственное отличие от формулы (1) в том, что я заменяю произведение вероятностей на сумму логарифмов, взятых с отрицательным знаком, и вычисляю не argmax, а argmin. Переход к логарифмам — распространненный прием чтобы избежать слишком маленьких чисел, которые могли бы получится при произведении вероятностей.
Число 10(^-7), которое подставляется в логарифм, это способ избежать нуля в аргументе логарифма (т.к. он будет иначе он будет неопределен).

Чтобы натренировать классификатор возьмем размеченный список мужских и женских имен и воспользуемся этим кодом:

def get_features(sample): return (sample[-1],) # get last letter

samples = (line.decode('utf-8').split() for line in open('names.txt'))
features = [(get_features(feat), label) for feat, label in samples]
classifier = train(features)

print 'gender: ', classify(classifier, get_features(u'Аглафья'))


Файл 'names.txt' можно скачать здесь.

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

def get_features(sample): return (
        'll: %s' % sample[-1],          # get last letter
        'fl: %s' % sample[0],           # get first letter
        'sl: %s' % sample[1],           # get second letter
        )


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

Тесты


Я протестировал классификатор на части исходного корпуса с именами. Точность составила 96%. Это не блестящий результат, но для многих задач вполне достаточно.
+37
12569
110

Комментарии (21)

0
lightcaster #
Похоже, я перестарался с теорией :). Длинные формулы режут глаза.
+2
burdakovd #
По мне так нормальное количество формул.
Хотя я только вчера сдал экзамен по основам теории прогнозирования (кстати в том числе и про байесовский классификатор спрашивали), так что по сравнению с теми ужасами — у Вас формулы вовсе, а так, формулки=)
+1
lightcaster #
Да, сами формулы несложные. Просто хабр — не математический журнал, и здесь больше популярны практичные статьи.
0
xni #
Зря Вы так: формулы простые, хорошо оформленные и понятные. Я никогда не интересовался классификаторами, но все понял. Одного кода было бы недостаточно.
Спасибо!
+1
multik #
А чем это сильно отличается от алгоритма описанного в книге «Программируем коллективный разум»? — там кстати тоже на питоне код.
+1
lightcaster #
Не знаю. Я не читал. Там похожий код?

Знаю хорошую реализацию в nltk. Но там посложнее. Я же хотел написать максимально просто и коротко.
0
multik #
немного, хотя я на питоне не пишу, поэтому утверждать не могу
0
multik #
Но если не читали эту книгу то рекомендую — тем более — там все примеры на питоне.
0
lightcaster #
Да, хорошая книжка. Кое где поверхностно на мой взгляд, но довольно просто все объясняет.
Спасибо, почитаю.
0
burdakovd #
> Я протестировал классификатор на части исходного корпуса с именами.

Исходный корпус — это names.txt, то есть обучающая выборка? Если так, то результат завышен.
Лучше хотя бы случайным образом разбить исходный names.txt на две части train.txt и test.txt, обучать на одной части, тестировать на другой.
0
lightcaster #
Так и сделал :). Разбил на два корпуса. Стандартная, вобщем, практика. names.txt — файлик создавался шафлом по списку женских и мужских имен.

А в чем результат завышен?

Ниже — код для тестирования.

def test(classifier, test_set):
    hits = 0
    for feats, label in test_set:
        if label == classify(classifier, feats):
            hits += 1
    return hits/len(test_set)

def get_features(sample): return (
        'll: %s' % sample[-1],          # get last letter
        'fl: %s' % sample[1],           # get first letter
        'sl: %s' % sample[0],           # get second letter
        )

if __name__ == '__main__':
    samples = (line.decode('utf-8').split() for line in open('names.txt'))
    features = [(get_features(feat), label) for feat, label in samples]
    train_set, test_set = features[:-100], features[-100:]

    classifier = train(train_set)
    print 'Accuracy: ', test(classifier, test_set)
0
burdakovd #
Глядя на этот код, понимаю что всё ОК.

Просто в тексте статьи приведен пример обучения классификатора — там для обучения используется весь names.txt а не его часть, и ниже сказано «Я протестировал классификатор на части исходного корпуса с именами». Выглядит, как будто вы тестировали классификатор на обучающих данных.
0
lightcaster #
Понятно. Просто если бы включил код для тестирования, это было бы больше чем 25 строк :).
+1
iv1 #
В некоторых источниках встречал название этого алгоритма не как «наивный», а «упрощенный» и кажется, что последнее наименование больше подходит.
0
sourcerer #
Мне кажется, статью стоило вынести из-под замка. Очень интересная, на мой взгляд. Хотя, конечно, это личное право автора. Да и хомячки бы вряд ли оценили.
0
lightcaster #
Можно и опубликовать. Только куда? :)

0
kastaneda #
в алгоритмы!
–1
rdolgov #
«В функции train первые пять строк производят подсчет количества классов C»
1ая мысль: «а С то тут при чем ?» 2ая:«вот пельмень, это же из формулы» ;)
0
lightcaster #
Да, в коде все очень прямолинейно.
0
FuN_ViT #
в функции классификаторе (classify) не хватает проверки — есть ли пересечения тестируемого набора фич с фичами классификатора (prob).

т.к. иначе в тесте можно получить неверный результат, если проверять сбойный вариант (для приведенного теста — «ЫЫЫЫЫ»).
0
denis_bazhenov #
Хорошая статья, спасибо. Я у себя в блоге тоже описал байесовский классификатор, но с большим упором на теорию. В частности более подробно написал про проблему неизвестных слов (additive smoothing, то зачем вы использовали 10^-7).

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