朴素贝叶斯算法

我们来约定一下：

S： 邮件为垃圾邮件的概率

V: 邮件含有’viagra’词的概率

贝叶斯会告诉我们已知这个邮件含有viagra词，判断为垃圾邮件的概率：

假设垃圾邮件和非垃圾邮件的概率都是0.5，即：

则通过上面的公式得到：

假设50%的垃圾邮件中有‘vargra’，只有1%的非垃圾邮件中含有这个单词，问这个邮件是垃圾邮件的概率：

可见，含有这个单词一般都是垃圾邮件。

更加精致的邮件分类器

想象一下我们有一堆字母，，我们使用Xi表示一封信中含有此词的概率。同样，表示垃圾邮件中含有单词的概率，，非垃圾邮件中含有单词的概率。贝叶斯估计最大的假设就是单词存在之间没有关系，也就是单词都是独立的，从数学的角度出发，也就是，这是一个非常大胆的假设，虽然这是一种假设，但这种算法却体现了很好的分类性能。接下来使用贝叶斯理论，则，这时我们需要计算大量的概率乘积，不过我们可以用log函数来简化，。 
但有时候会存在除0的状况，我们会使用一个因子k，得到

实现

说完了理论，是不是感觉很空洞，那我们来实现一下吧。首先定义一个方法来得到不同的单词作为集合。

def tokenize(message):
    message = message.lower()
    all_words = re.findall('[a-z0-9]+',message)
    return set(all_words)

我们第二个方法是统计训练集中单词的个数。返回一个字典，key为单词，value为二元组(垃圾邮件的统计，非垃圾邮件的统计)，来查看某单词在垃圾和非垃圾邮件中的个数。

def count_words(training_set):
    counts = defaultdict(lambda:[0, 0])
    for message,is_spam in training_set:
        for word in tokenize(message):
            counts[word][0 if is_spam else 1] += 1
    return counts

我们下面一步就是计算概率了，返回三元组，包含了每个单词，在垃圾邮件中的概率和非垃圾邮件中的概率。

def word_probabilities(counts, total_spams, total_non_spams,k=0.5):
    return [(w,(spam+k)/(2*k+total_spams),(non_spam+k)/(total_non_spams+2*k)) for w,(spam,non_spam) in counts.iteritems()]

最后，我们通过这些单词的概率和贝叶斯理论来计算是垃圾邮件的概率：

def spam_probability(word_probs,message):
    message_words = tokenize(message)
    log_prob_if_spam = log_prob_if_not_spam = 0.0
    for word,prob_if_spam,prob_if_not_spam in word_probs:
        if word in message_words:
            log_prob_if_spam += math.log(prob_if_spam)
            log_prob_if_not_spam += math.log(prob_if_not_spam)
        else:
            log_prob_if_spam += math.log(1.0 - prob_if_spam)
            log_prob_if_not_spam += math.log(1.0 - prob_if_not_spam)
    prob_if_spam = math.exp(log_prob_if_spam)
    prob_if_not_spam = math.exp(log_prob_if_not_spam)
    return prob_if_spam/(prob_if_spam+prob_if_not_spam)

最后，我们写成一个类：

class NaiveBayesClassifier:
    def __init__(self, k=0.5):
        self.k = k
        self.word_probs = []
    def train(self,training_set):
        num_spams = len([is_spam for message,is_spam in training_set if is_spam])
        num_non_spams = len(training_set) - num_spams
        word_counts = count_words(training_set)
        self.word_probs = word_probabilities(word_counts,num_spams,num_non_spams,self.k)
    def classify(self,message):
        return spam_probability(self.word_probs,message)

我们来测试一下我们的分类性能。

在这个网址上提供了垃圾邮件数据集，我们测试了2002年的版本，对了，这里三个2002年的压缩文件都要下载下来，并放在一个文件夹下面，如这样的： 

下面我们就来测试一下：

import glob

path = 'spam\*\*'

data = []

for fn in glob.glob(path):
    is_spam = 'ham' not in fn
    #print is_spam

    with open(fn,'r') as file:
        for line in file:
            if![](http://i.imgur.com/8e6mWGM.png) line.startswith('Subject:'):
                subject = re.sub(r'^Subject: ','',line).strip()
                data.append((subject,is_spam))

这段代码的含义就是将文件夹下面的数据集放在一个data中。

random.seed(0)
train_data,test_data = split_data(data,0.75)
classifier = NaiveBayesClassifier()
classifier.train(train_data)

分割成测试集和训练集。

classified = [(subject,is_spam,classifier.classify(subject)) for subject,is_spam in test_data]
counts = Counter((is_spam,spam_probability>0.5) for _,is_spam ,spam_probability in classified)

首先分类测试集中的数据，然后检查准确率。在我的机器上，运行结果如下： 

精度为709/(709+28)=0.96,召回率为709/(709+40)=0/95,看起来还是蛮高的。我们有兴趣看看哪些容易被误分类。

classified.sort(key=lambda row:row[2]) #从小到大排序

spammiest_hams = filter(lambda row:not row[1],classified)[-5:]
hammiset_spams = filter(lambda row:row[1], classified)[:5]

最容易被判断为垃圾邮件的非垃圾邮件和垃圾邮件最不容易被判断的邮件。当然了，我们还最想看看垃圾邮件中的单词。

def p_spam_given_word(word_prob):
word, prob_if_spam, prob_if_not_spam = word_prob
return prob_if_spam / (prob_if_spam + prob_if_not_spam)

words = sorted(classifier.word_probs, key=p_spam_given_word)
spammiest_words = words[-5:]
hammiest_words = words[:5]

我们打印出来单词，如图：

这些关于含有钱，工作等单词的邮件很可能为垃圾邮件，而其他关于razor，等单词却不是，让我们感到很吃惊。