Пользователь
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%. Это не блестящий результат, но для многих задач вполне достаточно.
@lightcaster
карма
96,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

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

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

    Исходный корпус — это names.txt, то есть обучающая выборка? Если так, то результат завышен.
    Лучше хотя бы случайным образом разбить исходный names.txt на две части train.txt и test.txt, обучать на одной части, тестировать на другой.
    • 0
      Так и сделал :). Разбил на два корпуса. Стандартная, вобщем, практика. 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
        Глядя на этот код, понимаю что всё ОК.

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

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

    т.к. иначе в тесте можно получить неверный результат, если проверять сбойный вариант (для приведенного теста — «ЫЫЫЫЫ»).
  • 0
    Хорошая статья, спасибо. Я у себя в блоге тоже описал байесовский классификатор, но с большим упором на теорию. В частности более подробно написал про проблему неизвестных слов (additive smoothing, то зачем вы использовали 10^-7).
    • 0
      «Если я вам скажу “темно как у негра в …”, вы сразу поймете о каком месте чем идет речь, даже если я не закончу фразу. Так происходит потому что в натуральном языке вероятность появления слова сильно зависит от контекста. Байесовский же классификатор представляет документ как набор слов вероятности которых условно не зависят друг от друга.»
      отлично расписано!!! )))
  • 0
    Спасибо за статью!
    Я только начал изучать машинное обучение немного удивлён тому, что NBC классификатор реализуется достаточно просто.

    Кстати, если будет интересно, я на основе твоего кода и выборки обучил решающее дерево (DecisionTreeClassifier из scikit-learn), которое показало точность 97%:

    from sklearn.tree import DecisionTreeClassifier
    
    # ...
    
    def get_features(sample): return (
        ord(sample[-1]),  # get last letter
        ord(sample[0]),  # get first letter
        ord(sample[1]),  # get second letter
    )
    
    # ...
    
    clf = DecisionTreeClassifier()
    clf.fit(
        [i[0] for i in train_set],
        [i[1] for i in train_set]
    )
    
    hits = 0
    for feats, label in test_set:
        if label == clf.predict([feats]):
            hits += 1
    print 'Accurancy DecisionTreeClassifier: ', hits/len(test_set)
    
    
    • 0
      Сюда ещё оценка точности, полноты:
      Accuracy, Precision, Recall NBC: (0.96, 0.9821428571428571, 0.9482758620689655)
      Accuracy, Precision, Recall CDT: (0.97, 0.9824561403508771, 0.9655172413793104)

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