Документы и слова

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

Создайте новый файл docclass.py и включите в него функцию getwords, которая будет извлекать признаки из текста:

import re

import math def getwords(doc):

splitter=re.compile(‘\\W*’)

#    Разбить на слова по небуквенным символам words=[s.lower( ) for s in splitter.split(doc)

if len(s)>2 and len(s)<20]

#    Вернуть набор уникальных слов return dict([(w,1) for w in words])

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

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

Еще один фактор, который нужно принимать во внимание, когда выбирается набор признаков, – насколько хорошо они смогут распределить документы по категориям. Например, приведенная выше функция getwords сокращает число признаков, приводя все слова к нижнему регистру. Это означает, что написанное заглавными буквами слово, встречающееся в начале предложения, ничем не отличается от такого же слова, написанного строчными буквами, в середине предложения. Но тем самым мы полностью игнорируем КРИКЛИВЫЙ стиль, характерный для многих спамных сообщений, а это мог бы быть важный классифицирующий признак спама. Альтернативной могло быть стать объявление признаком такой характеристики: более половины слов написаны заглавными буквами.

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

Обучение классификатора

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

тем лучше он классифицирует последующие документы. Кроме того, в начальный момент классификатор намеренно делают очень «робким», так чтобы его «уверенность в себе» повышалась по мере того, как он узнает, какие признаки важны для проведения различий. Прежде всего нам понадобится класс для представления классификатора. Он инкапсулирует те факты, которым классификатор успел обучиться. У такой структуры есть важное достоинство – можно создавать разные экземпляры классификаторов, ориентированные на различных пользователей, группы или запросы, и обучать их в соответствии с потребностями конкретной группы. Создайте в файле docclass.py следующий класс classifier: class classifier: def __init__(self,getfeatures,filename=None):

#       Счетчики комбинаций признак/категория self.fc={}

#       Счетчики документов в каждой категории self.cc={}

self.getfeatures=getfeatures

В этом классе есть три переменных экземпляра: fc, cc и getfeatures. В переменной fc хранятся счетчики признаков при различных классификациях: например:

{‘python’: {‘bad’: 0, ‘good’: 6}, ‘the’: {‘bad’: 3, ‘good’: 3}}

Это означает, что слово the трижды появлялось в документах, классифицированных как плохие, и трижды – в документах, классифицированных как хорошие. Слово Python появлялось только в хороших документах.

Переменная cc – это словарь, в котором отражено, сколько раз применялась каждая классификация. Это необходимо для вычисления вероятности, о чем чуть позже. И последняя переменная экземпляра, getfeatu res, – это функция, с помощью которой из классифицируемых образцов выделяются признаки. В нашем примере это функция getwords.

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

#       Увеличить счетчик пар признак/категория def incf(self,f,cat):

self.fc.setdefault(f,{})

self.fc[f].setdefault(cat,0)

self.fc[f][cat]+=1

#       Увеличить счетчик применений категории def incc(self,cat):

self.cc.setdefault(cat,0) self.cc[cat]+=1

#       Сколько раз признак появлялся в данной категории def fcount(self,f,cat):

if f in self.fc and cat in self.fc[f]:

return float(self.fc[f][cat]) return 0.0

#       Сколько образцов отнесено к данной категории def catcount(self,cat):

if cat in self.cc:

return float(self.cc[cat]) return 0

#       Общее число образцов def totalcount(self):

return sum(self.cc.values( ))

#       Список всех категорий def categories(self):

return self.cc.keys( )

Метод train принимает образец (в данном случае документ) и классификацию. С помощью функции getfeatures он выделяет из образца признаки. Затем он вызывает метод incf, чтобы увеличить счетчики для каждого признака в данной классификации. И наконец он увеличивает счетчик применений этой классификации:

def train(self,item,cat):

features=self.getfeatures(item)

# Увеличить счетчики для каждого признака в данной классификации for f in features: self.incf(f,cat)

# Увеличить счетчик применений этой классификации self.incc(cat)

Убедиться в том, что класс работает правильно, можно, запустив интерпретатор Python и импортировав этот модуль:

$ python

>>> import docclass

>>> cl=docclass.classifier(docclass.getwords)

>>> cl.train(‘the quick brown fox jumps over the lazy dog’,’good’)

>>> cl.train(‘make quick money in the online casino’,’bad’)

>>> cl.fcount(‘quick’,’good’)

>>> cl.fcount(‘quick’,’bad’)

1.0

Сейчас нам был бы полезен метод, который сохраняет в классификаторе некоторые данные, полученные в ходе обучения, чтобы не приходилось каждый раз проводить обучение заново. Добавьте такую функцию в файл docclass.py:

def sampletrain(cl):

cl.train(‘Nobody owns the water.’,’good’) cl.train(‘the quick rabbit jumps fences’,’good’)

cl.train(‘buy pharmaceuticals now’,’bad’) cl.train(‘make quick money at the online casino’,’bad’) cl.train(‘the quick brown fox jumps’,’good’)

Вычисление вероятностей

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

Добавьте в класс classifier метод fprob:

def fprob(self,f,cat):

if self.catcount(cat)==0: return 0

#    Общее число раз, когда данный признак появлялся в этой категории,

#    делим на количество образцов в той же категории return self.fcount(f,cat)/self.catcount(cat)

Эта величина называется условной вероятностью, обычно записывается в виде Pr(A | B) и произносится так: «Вероятность A при условии B». Мы только что вычислили значение Рг(Слово | Классификация); то есть вероятность того, что некоторое слово появится в данной классификации.

Протестируем эту функцию в интерактивном сеансе: >>> reload(docclass)

<module ‘docclass’ from ‘docclass.py’> >>> cl=docclass.classifier(docclass.getwords) >>> docclass.sampletrain(cl) >>> cl.fprob(‘quick’,’good’)

0.66666666666666663

Как видите, слово quick входит всего в три документа, из которых два классифицированы как хорошие. Следовательно, вероятность того, что хороший документ будет содержать это слово, равна Pr(Quick | Хороший) = 0,666 (2/3).

Начинаем с разумной гипотезы

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

это слово встретилось в одном плохом документе и не встречалось в хороших, то вероятность того, что оно может появиться в хороших документах, согласно функции fprob равна 0. Это, пожалуй, перебор, так как слово money вполне нейтральное, просто ему не повезло – угораздило первый раз встретиться в плохом документе. Было бы разумнее, если бы вероятность постепенно приближалась к нулю по мере того, как обрабатывается все больше и больше документов в той же категории. Чтобы справиться с этой проблемой, мы выберем некую предполагаемую вероятность, которой будем пользоваться, когда информации о рассматриваемом признаке слишком мало. Хорошей отправной точкой может послужить вероятность 0,5. Еще нужно решить, какой вес приписать предполагаемой вероятности, – 1 означает, что вес предполагаемой вероятности равен одному слову. Взвешенная вероятность – это средневзвешенное значение, возвращаемое функцией getprobability, и предполагаемая вероятность.

В рассмотренном выше примере взвешенная вероятность слова money первоначально равна 0,5 во всех категориях. После того как классификатору был предъявлен один плохой документ и он узнал, что слово money отнесено к категории плохих, вероятность, что оно окажется плохим, возросла до 0,75. Это значение дает следующее вычисление: (weight*assumedprob + count*fprob)/(count+weight) = (1*1.0+1*0.5)/(1.0 + 1.0) = 0.75

Добавьте метод weightedprob в класс classifier: def weightedprob(self,f,cat,prf,weight=1.0,ap=0.5):

#       Вычислить текущую вероятность basicprob=prf(f,cat)

#       Сколько раз этот признак встречался во всех категориях totals=sum([self.fcount(f,c) for c in self.categories( )])

#       Вычислить средневзвешенное значение bp=((weight*ap)+(totals*basicprob))/(weight+totals) return bp

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

>>> reload(docclass)

<module ‘docclass’ from ‘docclass.pyc’> >>> cl=docclass.classifier(docclass.getwords) >>> docclass.sampletrain(cl) >>> cl.weightedprob(‘money’,’good’,cl.fprob)

0.25

>>> docclass.sampletrain(cl) >>> cl.weightedprob(‘money’,’good’,cl.fprob)

0.16666666666666666

Как видите, после повторного запуска sampletrain классификатор еще сильнее утвердился во мнении относительно вероятностей различных слов – из-за вклада предполагаемой вероятности.

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

Вы можете следить за любыми ответами на эту запись через 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