Байесовский классификатор

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

Хотя все примеры были связаны с документами, описанный байесовский классификатор применим к любому набору данных, который можно представить в виде списков признаков. Признаком считается любое свойство, которое может присутствовать или отсутствовать в образце. Для документов признаками служат слова, но это могут быть характеристики неидентифицированного объекта, симптомы заболевания и вообще все, о чем можно сказать, имеется оно или нет.

Обучение

Как и все алгоритмы обучения с учителем, байесовский классификатор обучается на примерах. Пример – это список признаков образца и его классификация. Предположим, что вы хотите научить классификатор распознавать, относится ли документ, содержащий слово python к языку программирования или к змеям. В табл. 12.1 приведен пример обучающего набора для этой цели.

Таблица 12.1. Признаки и классификация набора документов

Признаки

Классификация

Питоны – это констрикторы, которые питаются

Змея

птицами и млекопитающими

Python с самого начала разрабатывался как язык

Язык

сценариев

В Индонезии нашли питона длиной 49 футов

Змея

В Python реализована динамическая система типов

Язык

Питон с яркими чешуйками

Змея

Проект с открытыми исходными текстами

Язык

Классификатор запоминает все встретившиеся признаки, а также вероятности того, что признак ассоциирован с конкретной классификацией. Примеры предъявляются классификатору по одному. После каждого примера классификатор обновляет свои данные, вычисляя вероятность того, что документ из указанной категории содержит то или иное слово. Например, после обучения на показанном выше примере может получиться набор вероятностей, представленный в табл. 12.2.

Таблица 12.2. Вероятности принадлежности слов категориям

Признак

Язык

Змея

Динамический

0,6

0,1

Констриктор

0,0

0,6

Длина

0,1

0,2

Исходный

0,3

0,1

И

0,95

0,95

Из этой таблицы видно, что после обучения ассоциации признаков с различными категориями становятся сильнее или слабее. Слово «констриктор» имеет большую вероятность для змей, а слово «динамический» – для языка программирования. Неоднозначные признаки, например союз «и», имеют близкие вероятности для обеих категорий (слово «и» встречается почти в любом документе вне зависимости от его тематики). Обученный классификатор – это всего лишь список признаков вместе с ассоциированными вероятностями. В отличие от некоторых других методов классификации, здесь не нужно хранить исходные данные, на которых проводилось обучение.

Классификация

После обучения байесовский классификатор можно применять для автоматической классификации новых образцов. Предположим, что имеется документ, содержащий слова «длина», «динамический» и «исходный». В табл. 12.2 имеются вероятности для каждого слова, но они вычислены лишь для отдельных слов. Если бы все слова с высокой вероятностью попадали в одну и ту же категорию, то ответ был бы ясен. Однако для слова «динамический» выше вероятность попадания в категорию «Язык», а для слова «длина» – в категорию «Змея». Чтобы классифицировать новый документ, необходимо по вероятностям признаков вычислить вероятность всего образца.

Ранее был описан один из методов решения этой задачи – наивный байесовский классификатор. Он вычисляет совокупную вероятность по следующей формуле:

Рг(Категория | Документ) = Рг(Документ | Категория) x Рг(Категория) где

Рг(Документ | Категория) = Рг(Слово1 | Категория) x

x Рг(Слово2 | Категория) x … Величины Рг(Слово | Категория) – значения, взятые из таблицы, например Рг(Динамический | Язык) = 0,6. Величина Рг(Категория) равна полной частоте встречаемости данной категории. Поскольку категория «Язык» встречалась в половине случаев, то Рг(Язык) = 0,5. Результатом считается та категория, для которой Рг(Категория | Документ) принимает максимальное значение.

Использование ранее написанного кода

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

>>> docclass.getwords(‘python is a dynamic language’)

{‘python’: 1, ‘dynamic’: 1, ‘language’: 1}

Этой функцией можно воспользоваться для создания нового классификатора, обучения его на примерах строк: >>> cl=docclass.naivebayes(docclass.getwords) >>> cl.setdb(‘test.db’)

>>> cl.train(‘pythons are constrictors’,’snake’)

>>> cl.train(‘python has dynamic types’,’language’)

>>> cl.train(‘python was developed as a scripting language’,’language’)

и последующей классификации:

>>> cl.classify(‘dynamic programming’)

u’language’

>>> cl.classify(‘boa constrictors’)

u’snake’

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

Сильные и слабые стороны

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

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

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

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

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100