过滤垃圾信息 #
基于规则的分类器（rule-based classifier），使用时会有人事先设计好一组规则，用以指明某条信息是否属于垃圾信息。
存在的问题是
- 垃圾信息制造者知道规则后，就可以绕开过滤器
- 是否被当作垃圾信息很大程度上因其所面对的读者和张贴位置的不同而不同。
解决：程序在开始阶段逐渐收到更多消息之后，根据人们提供给它的有关哪些是垃圾邮件，哪些不是垃圾邮件的信息，不断地进行学习。通过这样的方式，我们可以分别为不同的用户、群组或网站建立起各自的应用实例和数据集，它们对垃圾信息的界定将逐步形成自己的观点。
提取文本中的单词
def getwords(doc):
splitter=re.compile('\\W*')
print doc
# 非字母进行首字母切分
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])
分类器 #
- 首先定义一个分类器
class classifier:
def __init__(self,getfeatures,filename=None):
self.fc={}
self.cc={}
self.getfeatures=getfeatures
fc 的数据格式如下
{'python': {'bad': 0, 'good': 6}, 'the': {'bad': 3, 'good': 3}}
代表了， the 在 bad 中出现了 3 次，而 python 在 bad 中出现了 0 次。
cc 记录了各分类被使用次数的字典
基础函数 #
然后我们定义了基础的函数，用于分类器的更新
# 增加 FC（特征/分类）中的值
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
# 一个特征(feature)出现于某个分类(category)的次数
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( )
然后就可以定义我们的训练函数了
def train(self,item,cat):
# 找到所有特征
features=self.getfeatures(item)
# 计算特征好坏
for f in features:
self.incf(f,cat)
# 增加分类的引用次数
self.incc(cat)
此时执行如下
>>> 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')
1.0
>>> cl.fcount('quick','bad')
1.0
计算概率 #
上面我们将好坏的分类进行分类，就像之前其他算法一样，我们需要将其转为 0 - 1 之间的数字
def fprob(self,f,cat):
if self.catcount(cat)==0: return 0
# 特征在分类中出现的次数，除以这个分类一共的内容项总数
return self.fcount(f,cat)/self.catcount(cat)
这个时候，我们执行
>>> reload(docclass)
<module 'docclass' from 'docclass.py'>
>>> cl=docclass.classifier(docclass.getwords)
>>> docclass.sampletrain(cl)
>>> cl.fprob('quick','good')
0.66666666666666663
就会得到一个值。代表了 quick 在 good 中的概率是 0.66
但是现在的算法有个致命的问题，其在训练的初期阶段，对那些极少出现的单词变得异常敏感。为解决上述问题，在我们手头掌握的有关当前特征的信息极为有限时，我们还需要根据一个假设的概率来作出判断。一个推荐的初始值是0.5.我们还要为假设的概率赋以多大的权重——权重为1代表假设概率的权重与一个单词相当。经过加权的概率值返回的是一个有 getprobability 与假设概率组成的加权平均。
主要是为了弱化只出现很少的词对系统的影响。
def weightedprob(self,f,cat,prf,weight=1.0,ap=0.5):
# 计算当前的概率值，这里的 prf 在当前就是 fprob
basicprob=prf(f,cat)
# 统计特征在所有分类中出现的次数
totals=sum([self.fcount(f,c) for c in self.categories()])
# 计算平均权重
bp=((weight*ap)+(totals*basicprob))/(weight+totals)
return bp
朴素过滤器 #
当我们有一个分类器的模型的时候，我们就需要将一个文档各个单词的概率进行组合，然后得到文档属于分类的概率。
朴素贝叶斯分类器：朴素指的是它假设将要被组合的各个概率是彼此独立的。即，一个单词在属于某个指定分类的文档中出现的概率，与其他单词出现于该分类的概率是不相关的。
事实上文章中的各个单词并不是独立的，这意味着我们无法采用朴素贝叶斯分类器所求得的结果实际用作一篇文档属于某个分类的概率。不过，我们还是可以对各个分类的计算结果进行比较，然后在看哪个分类的概率最大。在现实中，若不考虑假设的潜在缺陷，朴素贝叶斯分类器将被证明是一种非常有效的文档分类方法。
举个例子
20% 的 Bad 类的文档中提及了 Python 那么 Pr(Python|Bad) = 0.2 ，同时 80% 的 Bad 类的文档中提及了 casino 那么 Pr(casino|Bad) = 0.8。那么同时出现两者的文档的 Bad 概率是 0.2 * 0.8 = 0.16。
那么这个算法就呼之而来了。
def docprob(self,item,cat):
features=self.getfeatures(item)
# 将所有的特征概率相乘
p=1
for f in features: p*=self.weightedprob(f,cat,self.fprob)
return p
这个时候计算出来的是 Pr(Document | Category) 也就是这个文档在这个分类的概念，而我们需要得到的是 Pr(Category|Document) 也就是这个文档属于这个分类的概率。这里就需要使用 贝叶斯定理
换言之就是如下
\(\operatorname{Pr}(\text { Category } \mid \text { Document })=\operatorname{Pr}(\text { Document } \mid \text { Category }) \times \operatorname{Pr}(\text { Category }) / \operatorname{Pr}(\text { Document })\)对于 Pr(Category) 中的计算是随机选择一篇属于该分类的概率，Pr(Document) 就是随机一个类型属于这个文档的概率，在这里没有意义就忽略了
那么计算公式如下
def prob(self,item,cat):
catprob=self.catcount(cat)/self.totalcount()
docprob=self.docprob(item,cat)
return docprob*catprob
当我们计算出概率之后，就是要得到这个文档属于某个分类的结果，构造朴素贝叶斯分类器的最后一个步骤是实际判定某个内容项所属的分类。 此处最简单的方法是计算被考查内容在每个不同分类中的概率，然后选择概率最大的分类。 在许多问题中无法将各个分类同等看待，如与将正常邮件归为垃圾邮件相比，偶尔收到几封垃圾邮件还是可以容忍的。在另一些应用中承认不知道答案，要好过判断答案就是概率值稍大一些的分类。
为解决这一问题，我们可以为每个分类定义一个最小阈值。 以垃圾邮件过滤为例，假如过滤到“bad”分类的阈值为3，则针对“bad”分类的概率就必须至少3倍于针对“good”分类的概率才行。假如针对“good”分类的阈值为1，则对于任何邮件，只要概率确实大于针对“bad“分类的概率，它就是属于”good“分类的。任何有可能属于”bad“分类，但概率并没有超过3倍以上的邮件，都将被划归到”未知“分类中。
这样代码如下
def classify(self,item,default=None):
probs={}
# 找到最大概率的分类
max=0.0
# 遍历所有的分类
for cat in self.categories():
# 每个分类的概率
probs[cat]=self.prob(item,cat)
if probs[cat]>max:
max=probs[cat]
best=cat
# 确保分类的概率大于（ 阈值 * 第二高的概率）
for cat in probs:
if cat==best: continue
if probs[cat]*self.getthreshold(best)>probs[best]: return default
return best
The Fisher Method 费舍尔方法 #
贝叶斯过滤器中，我们通过 Pr(Featrue|Category) 组合的结果得到了文档的隶属概率，在本章我们换一个角度计算在文档中出现某个特征时候，该文档属于某个分类的概率 Pr(Category | Featrue)。
这里准备3个变量
- 属于某个分类的概率
clf = Pr(Featrue | Category) - 属于所有分类的概率合
freqsum = Pr(Featrue | Category) - cprob = clf / (clf+nclf)
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
费舍尔方案是将所有的概率相乘，然后取自然对数，再 / -2
def fisherprob(self,item,cat):
# 计算所有的概率乘合
p=1
features=self.getfeatures(item)
for f in features:
# weightedprob 和 上一章相似
p*=(self.weightedprob(f,cat,self.cprob))
# 自然对数 / -2
fscore=-2*math.log(p)
# 倒置对数获得概率，也就是转换 0 - 1
return self.invchi2(fscore,len(features)*2)
在 贝叶斯 上面我们控制阈值来决定输出结果，在费舍尔上指定下限来减少错误
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
但是书上没有说明为什么这里采用 下界 限制的办法。
持久化 #
这里主要用 SQL 把之前的逻辑重写了，直接参考源码 docclass.py
替代函数 #
因为上面那个方法都需要在训练的时候，传入 Good Bad 本质上是一个监督学习的过程 supervised learningmethods