avatar

lightcaster

карма
96,2
125 голосов
рейтинг
0,0
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
16491
119

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

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).
0
fingoldo #
«Если я вам скажу “темно как у негра в …”, вы сразу поймете о каком месте чем идет речь, даже если я не закончу фразу. Так происходит потому что в натуральном языке вероятность появления слова сильно зависит от контекста. Байесовский же классификатор представляет документ как набор слов вероятности которых условно не зависят друг от друга.»
отлично расписано!!! )))

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