O código deste exemplo se baseia no exemplo de Segaran 2007: "Programming Collective Intelligence"
Ao classificar documentos -- precisaremos de algumas coisas:
i) features i.e. qualquer coisa que você pode determinar como presente ou ausente no documento, ou que você possa contar nos documentos;
ii) classes; se não estivermos fazendo Topic Modeling as classes que queremos usar, muitas vezes, são dadas (e.g. fraudulento vs. normal; CV desejável vs. não; SPAM vs HAM; etc)
iii) bem ...mais documentos. A maioria dos modelos de classificação são supervisionados (todo mundo sabe a diferença? -- senão estará na próxima aula!), logo é preciso treinar o classificador.
Bem, ao considerar documentos para classificação, um bom candidato para features são as palavras do documento. Outros incluem: as entidades nomeadas (named-entities); os meta-dados associados ou qualquer coisa que sirva como feature
mas para este exemplo, vamos com as palavras:
Criamos uma função em python que extrai as palavras de um documento:
In [42]:
# coding: utf-8
import re
def getwords(doc):
splitter = re.compile('\\W*')
# Split the words by non-alpha characters
words = [s.lower() for s in splitter.split(doc) if len(s) > 2 and len(s) < 20]
#print words # usamos isso para checar o split depois
# retorno o set de palavras ÚNICAS!
res = dict([(w, 1) for w in words])
# print 'res:',res # veja
return res
Esta função divide um string partindo em cada coisa que não é uma letra e convertendo para minúsculo.
A escolha das features é muito importante. E difícil. Os documentos precisam ter algumas features em comum, mas uma feature que ocorre em todo documento é inútil para a classificação.
Em tese o texto inteiro de cada documento poderia ser uma feature. Mas aí teriamos um classificador que coloca cada um documento em uma classe separada (a não ser que haja documentos exatamente iguais). Do outro lado do espectro, podemos usar as letras como features, mas aí como todos os documentos de um corpus em geral tendem a ter o mesmo alfabeto, elas não seriam uma forma efetiva de separar documentos.
até quais palavras utilizar pode ser problemático, usamos pontuação ou não? quais as melhores regras para dividir palavras? Usamos o título (em caso de artigos ou notícias)? Colocar em minúsculo perde a informação de nomes próprios, inícios de frase, acrônimos.
Por exemplo -- para um detector de SPAM ...o estilo 'GRITADO' DE DIGITAR É CRUCIAL PARA DISTIGUIR MENSAGENS, E O NÚMERO DE EXCLAMAÇÕES TAMBÉM!!!!!
Com isso em mente, vamos programar e treinar o nosso classificador. Classificadores supervisionados melhoram à medida que vêem mais e mais documentos (tomando cuidado com overfitting/overtraining).
Vamos escrever uma classe genérica que descreve um classificador:
In [43]:
class classifier:
""" um classificador genérico que serve para trinar um Naïve Bayes """
def __init__(self, getfeatures, filename=None):
# contagem de combinações: feature/categoria
# ex: {'python': {'bad': 0, 'good': 6}, 'the': {'bad': 3, 'good': 3}}
self.featCatCombinations = {}
# contagem de documentos em cada cat.
# ex: {'good': 385, 'bad':266}
self.docCountPerCat = {}
# fn. de extração de features (recebida como input)
# no nosso caso é a getWords
self.getfeatures = getfeatures
# veremos mais em baixo para que isso serve!
self.thresholds = {}
# #################################################################
# estes são helper methods para que nossa classe permaneça genérica
# #################################################################
def incrFeatCount(self, f, cat):
"""Incrementa a contagem da feature f na categoria cat"""
self.featCatCombinations.setdefault(f, {})
self.featCatCombinations[f].setdefault(cat, 0)
self.featCatCombinations[f][cat] += 1
def incrCatCount(self, cat):
"""Incr. a contagem de uma cat"""
self.docCountPerCat.setdefault(cat, 0)
self.docCountPerCat[cat] += 1
def fcount(self, f, cat):
"""num. de vezes uma feature aparece em uma cat"""
if f in self.featCatCombinations and cat in self.featCatCombinations[f]:
return float(self.featCatCombinations[f][cat])
return 0.0
def catcount(self, cat):
"""num. de itens em uma cat."""
if cat in self.docCountPerCat:
return float(self.docCountPerCat[cat])
return 0
def totalcount(self):
"""num. total de itens"""
return sum(self.docCountPerCat.values())
def categories(self):
"""lista de categorias"""
return self.docCountPerCat.keys()
# #################################################################
def train(self, item, cat):
"""pego um documento classificado, parto ele em features e
adiciono as contagens deste doc. ao todo"""
features = self.getfeatures(item)
# incr. a contagem para cada feature na cat.
for f in features:
self.incrFeatCount(f, cat)
# incr. a contagem na cat.
self.incrCatCount(cat)
# #################################################################
def fprob(self, f, cat):
"""probabilidade de uma feature >F< ocorrer na categoria >C<:
i.e: num. de vezes F aparece em C sobre o num de itens em C
"""
if self.catcount(cat) == 0: return 0 # se vazio, retorna 0
return self.fcount(f, cat)/self.catcount(cat)
def weightedprob(self, f, cat, prf, weight=1.0, ap=0.5):
"""probabilidade ponderada (veja abaixo)
weight é o peso (em qtd de palavras) que a prob assumida tem
ap é a probabilidade assumida (assumed probability - ap)
"""
# calcular a probabilidade basica
basicprob = prf(f, cat)
# contar o numero de vezes que a feature aparece em TODAS as categorias
totalOcc = sum([self.fcount(f, c) for c in self.categories()])
# calcular a probabilidade ponderada
bp = ((weight * ap) + (totalOcc * basicprob)) / (weight + totalOcc)
# = ( 1 * 0.5) + ( soma * prAssumida) / ( 1 + soma )
return bp
# #################################################################
# setter e getter para as thesholds de cada categoria, veremos abaixo
# #################################################################
def setthreshold(self, cat, t):
self.thresholds[cat] = t
def getthreshold(self, cat):
if cat not in self.thresholds: return 1.0
return self.thresholds[cat]
# #################################################################
# aqui finalmente
def classify(self, item, default=None):
probs = {}
# Encontra a classe com a maior probabilidade
max = 0.0
for cat in self.categories():
probs[cat] = self.prob(item, cat)
if probs[cat] > max:
max = probs[cat]
best = cat
# garante que a probabilidade excede threshold*next best
for cat in probs:
if cat == best: continue
if probs[cat] * self.getthreshold(best) > probs[best]: return default
return best
Vamos checar os helpers?
In [44]:
cl=classifier(getwords)
cl.train('the quick brown quick fox jumps over the lazy dog','good')
cl.train('make quick money in the online casino','bad')
Veja que a palavra 'the' só aparece uma vez, em um documento bom
In [45]:
cl.fcount('the','good')
Out[45]:
igualmente, 'quick' só aparece uma vez em um documento classificado como mau:
In [46]:
cl.fcount('quick','bad')
Out[46]:
Agora podemos criar uma função place-holder para um corpus de e-mails; e vamos tentar achar SPAM.
In [47]:
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('Mike is quick to store his money in bonds','good')
Adicionamos à nossa classe funções de contagem, agora vamos extrair probabilidades: A função fprob faz exatamente isso, veja lá.
Zeramos o classificador e treinamos no corpus anotado (já classificado).
In [48]:
cl=classifier(getwords)
sampletrain(cl)
cl.fprob('quick','good')
Out[48]:
Isso se chama probabilidade condicional: Pr(A | B).
Neste exemplo temos a probabilidade Pr(palavra | classe), isto é, para uma dada classificação, calculamos a probabilidade de uma dada palavra aparecer.
fprob tem um leve problema, que é usar a informação que foi vista até um dado momento torna o modelo sensível durante o início do treino e a palavras que ocorrem raramente. 'Money' aparece somente uma vez e é classificada como ruim pois aparece em um anúncio de casino, mas 'money' pode ser (e provavelmente é) uma palavra neutra em um corpo de e-mails genérico.
Com isso, a probabilidade de 'money' aparecer em 'good' agora é zero. Seria muito mais realistico se o valor gradualmente se aproximasse de zero à medida que mais e mais documentos fossem vistos.
Assim, vamos partir de uma probabilidade assumida (0.5, por exemplo) e um peso para esta probabilidade: um peso de 1 significa que ela vale uma palavra, assim a nossa probabilidade com pesos (weighedprob lá em cima) será uma média ponderada entre a palavra (get) e a probabilidade assumida).
Uma vez que temo as probabilidades de cada categoria conter uma certa palavra, podemos combinar as probabilidades de palavras individuais para ter a probabilidade de um documento pertencer a uma dada classe.
Este método se chama 'naïve' (ingênuo) pois parte da premissa que as probabilidades sendo combinadas são independentes (por isso multiplicamos) – isto é – assumimos que a probabilidade de uma palavra de um documento ocorrer em uma categoria é independente de todas as outras palavras serem ou não daquela categoria
A palavra 'cassino' deve ocorrer junto com 'ganhar' muito mais que com 'alumínio' ou 'feijoada' (pelo menos eu espero).
Para um classificador Naive Bayes, precisamos da probabilidade de um documento inteiro ser dado uma classificação. Por assumir independência, podemos somente multiplicar as probabilidades individuais das palavras para obter a do documento. Veja docprob abaixo.
Agora sabemos calcular $Pr(Documento | Classe)$, mas isso não serve de muito.
Para classificar documentos precisamos de $Pr(Classe | Documento)$, ou seja, dado o documento qual a probabilidade de ele pertencer a uma classe específica.
Entra o Teorema de Bayes:
ou seja: $$Pr(Classe | Documento) = \frac{Pr(Documento | Classe) \cdot Pr(Classe)}{Pr(Documento)}$$
Assim, $Pr(Classe)$ é a probabilidade que um documento aleatório será desta classe, então é só o número de documentos na classe divido pelo número total de documentos.
$Pr(Documento)$ é desnecessário pois os resultados não serão usados em uma probabilidade, e sim apenas comparativamente entre classes (e todas terão o mesmo denominador), então podemos ignorá-lo!
O método prob calcula a probabilidade da categoria e retorna o produto de $Pr(Document|Category)$ e $Pr(Category)$. Vamos adicionar isto à classe NaiveBayes:
In [49]:
class NaiveBayes(classifier):
def docprob(self, item, cat):
"""pega a probabilidade multiplicada de cada feature (palavra) do documento"""
# pegar as feature
features = self.getfeatures(item)
# Mutiplico as probabilidades de cada feature
p = 1
for f in features:
p *= self.weightedprob(f, cat, self.fprob)
return p
def prob(self, item, cat):
# calculando Pr(Classe)
catprob = self.catcount(cat) / self.totalcount()
# calculando Pr(Doc | Classe)
docprob = self.docprob(item, cat)
# retornando Pr( Classe | Doc) = Pr(Doc | Classe) * Pr(Classe)
return docprob*catprob
O ultimo passo é escolher uma classe para o documento. A forma mais simples seria calcular as probabilidades de cada classe e escolher a maior.
Se estivermos apenas tentando descobrir a classe mais apropriada para um item esta é uma estratégia que se aplica, mas em muitas aplicações é melhor o classificador admitir que não sabe a resposta do que decidir que a resposta é uma categoria com uma probabilidade marginalmente maior.
No nosso exemplo de SPAM, é muito mais importante evitar que um email bom seja classificado como spam do que pegar absolutamente todos os spams. Uma mensagem de spam na inbox de vez em quando pode ser tolerada, mas um email importante que é jogado na caixa de spam pode ser negligenciado completamente. Se você precisa olhar no seu folder de spam procurando e-mails importantes, não há razão para ter um folder de spam.
Para lidar com isso, podemos colocar um threshold, isto é, um valor mínimo para cada categoria. Para que um novo documento caia em uma categoria, ela precisa ser >x< mais provável que qualquer outra, digamos 3.
Assim, qualquer mensagem cuja probabilidade é alta ..mas não 3 vezes mais alta de ser spam é classificada como 'unknown'
vamos ver no código... lé em cima!
In [50]:
if __name__ == '__main__':
cl = classifier(getwords)
sampletrain(cl)
print 'fprob for "money" being good', cl.fprob('money', 'good')
print 'fprob for "money" being bad', cl.fprob('money', 'bad')
print '\nweightedprob for "money" being good', cl.weightedprob('money', 'good', cl.fprob)
print 'weightedprob for "money" being bad', cl.weightedprob('money', 'bad', cl.fprob)
In [51]:
s = "money, that's what I want"
print '\nretraining on new text:\t\t','"'+s+'"\n'
cl.train(s, "bad")
print 'weightedprob for "money" being good', cl.weightedprob('money', 'good', cl.fprob)
print 'weightedprob for "money" being bad', cl.weightedprob('money', 'bad', cl.fprob)
In [64]:
nbClassifier = NaiveBayes(getwords)
sampletrain(nbClassifier)
print "\nis 'quick' good?", nbClassifier.prob('quick', 'good')
print "is 'quick' bad?",nbClassifier.prob('quick', 'bad')
print "it is classified as:",nbClassifier.classify('quick', default='unknown')
s2 = "Take this other quick quiz and make money!"
s3 = "click here quick! Woman want to talk to you!"
print '\nretrainting on two new texts...'
print '\t\t"'+s2+'"'
print '\t\t"'+s3+'"'
nbClassifier.train(s2, "bad")
nbClassifier.train(s3, "bad")
print "\nis 'quick' good?", nbClassifier.prob('quick', 'good')
print "is 'quick' bad?",nbClassifier.prob('quick', 'bad')
print 'now it is:',nbClassifier.classify('quick', default='unknown')
print '\n\n'
sNew = 'my dog, while quick, cannot jump'
#sNew = 'my rabbit, while quick, cannot jump'
print 'agora vamos classificar o um novo texto que recebemos:'
print '\t\t"'+sNew+'"\n'
print nbClassifier.classify(sNew, default='unknown')
print 'e com threshold:',
nbClassifier.setthreshold('bad', 3)
print nbClassifier.classify(sNew, default='unknown')
Uma razão que classificadores Bayesianos são usados para classificação é pois eles requerem muito menos computação que outros métodos. Um texto ou mensagem pode ser enorme, contendo até milhares de palavras, e simplesmente atualizar contagens toma muit menos memória e ciclos de processador que, por exemplo, treinar uma rede neural do tamanho necessário.
Uma rede neural, neste caso, também tem a desvantagem de não ser interpretável. Neste exemplo podemos olhar as probabilidades individuais e como elas contribuem ao todo, enquanto os pesos de conexão em uma rede neural não permitem interpretação direta.
Por outro lado, redes neurais e classificadores como SVMs pode capturar relações mais complexas entre as features. Em uma ANN a probabilidade de uma feature pode mudar em resposta à presença ou ausência de outras features. Por exemplo, podemos querer filtrar a palavra "cassino" a não ser que apareça junto com a palavra "filme"