Наивный Байесовский классификатор в 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%. Это не блестящий результат, но для многих задач вполне достаточно.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 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
                  Мне кажется, статью стоило вынести из-под замка. Очень интересная, на мой взгляд. Хотя, конечно, это личное право автора. Да и хомячки бы вряд ли оценили.
                • –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)

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