Метод Фишера

, названный по имени Р. А. Фишера (R. A. Fisher), – это альтернативный метод классификации, который дает очень точные результаты, особенно применительно к фильтрации спама. Он используется в подключаемом к программе Outlook фильтре SpamBayes, который написан на языке Python. В отличие от наивной байесовской фильтрации, когда для вычисления вероятности всего документа перемножаются вероятности отдельных признаков, по методу Фишера вычисляется вероятность отнесения к той или иной категории для каждого признака документа, после чего эти вероятности комбинируются и проверяется, насколько получившееся множество похоже на случайное. Хотя этот метод более сложен, с ним стоит ознакомиться, так как он обеспечивает большую гибкость при настройке параметров классификации.

Вероятности отнесения признаков к категориям

В наивном байесовском фильтре, который обсуждался выше, мы комбинировали вероятности Pr (Признак| Категория) для получения полной вероятности документа, а затем сравнивали их. В этом разделе мы начнем с вычисления вероятности попадания документа в некоторую категорию при условии наличия у этого документа конкретного признака, то есть с вычисления величины Pr(Категория | Признак). Если слово casino встречается в 500 документах, из которых 499 плохие, то оценка casino относительно категории «Плохой» будет очень близка к 1.

Обычно значение Рг(Категория | Признак) вычисляется так:

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

Чтобы выполнить такую нормализацию, в методе Фишера вычисляются три величины:

•       clf = Рг(Признак | Категория) для этой категории

•       freqsum = сумма Рг(Признак | Категория) для всех категорий

•       cprob = clf / (clf + nclf)

Создайте в файле docclass.py новый подкласс fisherclassifier класса classifier и включите в него такой метод:

class fisherclassifier(classifier): def cprob(self,f,cat):

#       Частота появления данного признака в данной категории clf=self.fprob(f,cat)

if clf==0: return 0

#       Частота появления данного признака во всех категориях freqsum=sum([self.fprob(f,c) for c in self.categories( )])

#       Вероятность равна частоте появления в данной категории, поделенной на

#       частоту появления во всех категориях p=clf/(freqsum)

return p

Эта функция возвращает вероятность того, что образец с указанным признаком принадлежит указанной категории, в предположении, что в каждой категории будет одинаковое число образцов. Можете посмотреть в интерактивном сеансе, какие получаются цифры: >>> reload(docclass)

>>> cl=docclass.fisherclassifier(docclass.getwords) >>> docclass.sampletrain(cl) >>> cl.cprob(‘quick’,’good’)

0.57142857142857151 >>> cl.cprob(‘money’,’bad’)

1.0

Как видите, документы, содержащие слово casino с вероятностью 0,9, классифицируются как спам. Это соответствует данным обучения, но

остается все та же проблема – недостоверность для редко встречающихся слов, когда вероятность может оказаться сильно завышенной. Поэтому, как и раньше, лучше пользоваться взвешенной вероятностью, начав со значения 0,5 и постепенно улучшая точность по мере обучения класса:

>>> cl.weightedprob(‘money’,’bad’,cl.cprob)

0.75

Комбинирование вероятностей

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

По методу Фишера все вероятности перемножаются, затем берется натуральный логарифм (math.log в Python) и результат умножается на -2. Добавьте следующий метод в класс fisherclassifier:

def fisherprob(self,item,cat):

#    Переменожить все вероятности p=1

features=self.getfeatures(item) for f in features:

p*=(self.weightedprob(f,cat,self.cprob))

#    Взять натуральный логарифм и умножить на -2 fscore=-2*math.log(p)

#    Для получения вероятности пользуемся обратной функцией хи-квадрат return self.invchi2(fscore,len(features)*2)

Фишер доказал, что если бы вероятности были независимы и случайны, то результат этого вычисления подчинялся бы распределению хи- квадрат. Следует ожидать, что образец, не принадлежащий некоторой категории, будет содержать слова с различными вероятностями признаков для данной категории (их распределение было бы случайным), а в образце, принадлежащем категории, будет много признаков с высокими вероятностями. Подав результат вычисления по формуле Фишера на вход обратной функции хи-квадрат, мы получаем вероятность того, что случайный набор вероятностей вернет такое большое число. Добавьте обратную функцию хи-квадрат в класс fisherclassifier: def invchi2(self,chi,df): m = chi / 2.0 sum = term = math.exp(-m)

for i in range(1, df//2): term *= m / i sum += term return min(sum, 1.0)

Протестируйте метод Фишера и посмотрите, как он оценивает различные строки:

>>> reload(docclass)

>>> cl=docclass.fisherclassifier(docclass.getwords) >>> docclass.sampletrain(cl) >>> cl.cprob(‘quick’,’good’)

0.57142857142857151

>>> cl.fisherprob(‘quick rabbit’,’good’)

0.78013986588957995

>>> cl.fisherprob(‘quick rabbit’,’bad’)

0.35633596283335256

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

Классификация образцов

Значения, возвращенные функцией fisherprob, можно использовать для классификации. Вместо того чтобы задавать мультипликативные пороги, как в байесовском фильтре, можно определить нижние границы для каждой классификации. Тогда классификатор вернет максимальное значение, укладывающееся в эти границы. Для антиспамного фильтра минимальную границу для категории «Плохой» можно задать достаточно высокой, например 0,6. А для категории «Хороший» можно задать гораздо меньшую границу, скажем 0,2. Это уменьшает шансы попадания в эту категорию хороших сообщений, но допускает «просачивание» небольшого числа спамных сообщений в ящик для входящей почты. Любое сообщение, для которого оценка для категории «Хороший» меньше 0,2, а для категории «Плохой» меньше 0,6, классифицируется как «Неизвестный».

Создайте в классе fisherclassifier метод init, инициализирующий еще одну переменную экземпляра для хранения отсечек:

def __init__(self,getfeatures):

classifier._____ init_ (self,getfeatures)

self.minimums={}

Добавьте методы получения и установки значений, считая, что по умолчанию принимается значение 0:

def setminimum(self,cat,min): self.minimums[cat]=min

def getminimum(self,cat):

if cat not in self.minimums: return 0 return self.minimums[cat]

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

def classify(self,item,default=None): # Цикл для поиска наилучшего результата best=default max=0.0

for c in self.categories( ): p=self.fisherprob(item,c) # Проверяем, что значение больше минимума if p>self.getminimum(c) and p>max: best=c max=p return best

Испытаем классификатор по методу Фишера на тестовых данных. Введите в интерактивном сеансе следующие команды:

>>> reload(docclass)

<module ‘docclass’ from ‘docclass.py’> >>> docclass.sampletrain(cl) >>> cl.classify(‘quick rabbit’)

‘good’

>>> cl.classify(‘quick money’)

‘bad’

>>> cl.setminimum(‘bad’,0.8) >>> cl.classify(‘quick money’)

‘good’

>>> cl.setminimum(‘good’,0.4) >>> cl.classify(‘quick money’)

Результаты аналогичны полученным от наивного байесовского классификатора. Но считается, что на практике классификатор Фишера фильтрует спам лучше; правда, убедиться в этом на небольшом обучающем наборе вряд ли получится. Какой классификатор использовать – зависит от приложения. Заранее не скажешь, что будет работать лучше и какие выбирать отсечки. Впрочем, приведенный код позволяет поэкспериментировать с обоими алгоритмами, задавая разные параметры.

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

1 комментарий »

 
  • Дмитрий says:

    Взято из книги Тоби Сегарана “Программируем коллективный разум” начиная со страницы 157.

 

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

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