<d,c>={Beijing joins the World Trade Organization, China}

对于这个只有一句话的文档，我们把它归类到 China，即打上china标签。

我们期望用某种训练算法，训练出一个函数γ，能够将文档映射到某一个类别：

γ:X→C

这种类型的学习方法叫做有监督学习，因为事先有一个监督者（我们事先给出了一堆打好标签的文档）像个老师一样监督着整个学习过程。

朴素贝叶斯分类器是一种有监督学习，常见有两种模型，多项式模型(multinomial model)和伯努利模型(Bernoulli model)。

多项式模型

在多项式模型中， 设某文档d=(t₁,t₂,…,t_k)，t_k是该文档中出现过的单词，允许重复，则

先验概率P(c)= 类c下单词总数/整个训练样本的单词总数

类条件概率P(t_k|c)=(类c下单词t_k在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|)

V是训练样本的单词表（即抽取单词集合，单词出现多次，只算一个），|V|则表示训练样本包含多少种单词。在这里，m=|V|, p=1/|V|。

P(t_k|c)可以看作是单词t_k在证明d属于类c上提供了多大的证据，而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。

#!/usr/bin/python
#  NaiveBayes classification
#  lming_08 2014.07.06
import math
import numpy as np
from sklearn import metrics

class NaiveBayes:
    def __init__(self, trainFile):
        self.trainingFile = trainFile
        self.trainingData = self.read_data(trainFile)

    # Read training or testing data
    def read_data(self, file):
        data = []
        fd = open(file)
        for line in fd:
            arr = line.rstrip().split(',')
            # Turn an instance's last column(y column) as integer
            arr[-1] = int(arr[-1])
            # Append the instance to trainingData
            data.append(tuple(arr))
        fd.close()
        return data

    def train_model_with_Bernoulli(self):
        self.sumPosInstance = 0.
        self.sumNegInstance = 0.
        self.termfreq = {}
        for instance in self.trainingData:
                if int(instance[-1]) == 1:
                    self.sumPosInstance += 1
                else:
                    self.sumNegInstance += 1

                for i in range(len(instance) - 1):
                    key = str()
                    if i < 55:                        
                        if float(instance[i]) > 0:
                            key = "freq" + "|" + str(i + 1) + "|" + "1"
                        else:
                            key = "freq" + "|" + str(i + 1) + "|" + "0"
                    else:
                        key = "length" + "|" + str(i + 1) + "|" + instance[i]

                    if key not in self.termfreq:
                        self.termfreq[key] = [0, 0]
                    
                    if int(instance[-1]) == 1:
                        self.termfreq[key][1] += 1
                    else:
                        self.termfreq[key][0] += 1
        # prior_prob = p(y = 1)
        self.prior_prob = self.sumPosInstance / (self.sumPosInstance + self.sumNegInstance)
        # prior_ratio = p(y=1) / p(y=0)
        self.prior_ratio = self.sumPosInstance / self.sumNegInstance

    # the function should be called before predict()
    def set_testfile(self, testFile):
        self.testing_data = self.read_data(testFile)

    def predict(self):
        self.testingY = []
        self.predict_result = []

        for instance in self.testing_data:
            self.predict_result.append(self.predict_instance_with_Bernoulli(instance))
            self.testingY.append(instance[-1])
    
    def get_statistics(self):
        true_classify_count = 0.
        false_classify_count = 0.
        for instance in self.testing_data:
            post_prob = self.predict_instance_with_Bernoulli(instance)
            if post_prob >= 0.5 and instance[-1] == 1:
                true_classify_count += 1
            elif post_prob >= 0.5 and instance[-1] == 0:
                false_classify_count += 1
            elif post_prob < 0.5 and instance[-1] == 1:
                false_classify_count += 1
            elif post_prob < 0.5 and instance[-1] == 0:
                true_classify_count += 1
        return true_classify_count, false_classify_count
	
    def predict_instance_with_Bernoulli(self, instance):
        f = 0.
        for i in range(len(instance) - 1):
            key = str()
            if i < 55:                        
                if float(instance[i]) > 0:
                    key = "freq" + "|" + str(i + 1) + "|" + "1"
                else:
                    key = "freq" + "|" + str(i + 1) + "|" + "0"
            else:
                key = "length" + "|" + str(i + 1) + "|" + instance[i]

            if key in self.termfreq:
                f += math.log( (self.termfreq[key][1] + 1) / ((self.termfreq[key][0] + 2) * self.prior_ratio) )

        
        posterior_ratio = self.prior_ratio * math.exp(f)
        # posterior probability
        prob = posterior_ratio / (1. + posterior_ratio)
        return prob

    def getAUC(self):
        y = np.array(self.testingY)
        pred = np.array(self.predict_result)
        fpr, tpr, thresholds = metrics.roc_curve(y, pred) # metrics.roc_curve(y, pred, pos_label=1)
        auc = metrics.auc(fpr, tpr)
        return auc

def main(trainFile, testFile):
    nb = NaiveBayes(trainFile)
    nb.train_model_with_Bernoulli()
    nb.set_testfile(testFile)
    nb.predict()
    print("the value of AUC: " % nb.getAUC())
    print("the value of priori probability:" % nb.priorProb)

if __name__ == "__main__":
    if len(argv) != 3:
        print "Usage: python %s trainFile(in) testFile(out)" % __file__
        sys.exit(0)

    main(argv[1], argv[2])

#!/usr/bin/python
#  Partitioning a file into training(80%) and testing file(20%)
#  lming_08 2014.07.06
from random import randint

def partition_file(file, train_file, test_file):
    ltest = []
    ltrain = []
    fd = open(file, "r")
    train_fd = open(train_file, "w")
    test_fd = open(test_file, "w")
    test_index = 0
    train_index = 0
    for line in fd:
        rnum = randint(1, 10)
        if rnum == 5 or rnum == 6:
            test_index += 1
            ltest.extend(line)
            if test_index == 100:
                test_fd.writelines(ltest)
                ltest = []
                test_index = 0
        else:
            train_index += 1
            ltrain.extend(line)
            if train_index == 100:
                train_fd.writelines(ltrain)
                ltrain = []
                train_index = 0
    if len(ltest) > 0:
        test_fd.writelines(ltest)
    if len(ltrain) > 0:
        train_fd.writelines(ltrain)
    train_fd.close()
    test_fd.close()
    fd.close()

#!/usr/bin/python%
#  main execute file
#  lming_08 2014.07.06
import sys
from sys import argv
from NaiveBayes import NaiveBayes
from PartitionFile import partition_file

def main(srcFile, trainFile, testFile):
    partition_file(srcFile, trainFile, testFile)
    nb = NaiveBayes(trainFile)
    nb.train_model_with_Bernoulli()
    nb.set_testfile(testFile)
    nb.predict()
    print("the value of AUC: %f" % nb.getAUC())
    print("the value of priori probability: %f" % nb.prior_prob)
    true_classify_count, false_classify_count = nb.get_statistics()
    error_rate = false_classify_count/(true_classify_count + false_classify_count)
    print("the error rate : %f" % error_rate)
	
if __name__ == "__main__":
    if len(argv) != 4:
        print "Usage: python %s srcFile(in) trainFile(out) testFile(out)" % __file__
        sys.exit(0)

    main(argv[1], argv[2], argv[3])