算法课程作业_python

第五次作业

一、文章分类

重写了部分代码，原代码利用各类文章中词语的次数进行条件概率计算，我改为利用各类文章中词语出现的文章篇数进行条件概率计算，下面是改动过的代码

def LoadData():
    i =0
    files = os.listdir(TrainingDataFile)
    for filename in files:
        infile = open(os.path.join(TrainingDataFile, filename), 'r')
        sline = infile.read().strip()
        while len(sline) > 0:
            pos = sline.find("#")
            if pos > 0:
                sline = sline[:pos].strip()
            words = sline.split(' ')
            if len(words) < 1:
                print("Format error!")
                break
            # 类别号，分类标签:每条样本的第一列
            classid = int(words[0])
            if classid not in ClassFeaDic:
                # 记录每个类中的每个token的出现篇数
                ClassFeaDic[classid] = {}
                # 记录每个token在各自类中的概率
                ClassFeaProb[classid] = {}
                # 记录每个类的文章个数
                ClassFreq[classid] = 0
            ClassFreq[classid] += 1
            # 记录每篇文章的正文文本特征
            words = words[1:]
            #remove duplicate words, binary distribution
            #words = Dedup(words)
            for word in set(words): #对文章中重复出现的词语进行删除
                if len(word) < 1:
                    continue
                wid = int(word)
                if wid not in ClassFeaDic[classid]:
                    ClassFeaDic[classid][wid] = 1
                else:
                    ClassFeaDic[classid][wid] += 1
        i += 1
        infile.close()
        if i % 100 == 0:
            print(i, "instances loaded!")
    print(i, "instances loaded!")

def ComputeModel():
    sum = 0.0
    for freq in ClassFreq.values():
        sum += freq
    for classid in ClassFreq.keys():
        # p(yi)：先验概率：每个类的文章个数/总文章数
        ClassProb[classid] = (float)(ClassFreq[classid])/(float)(sum)
    # p(xj|yi)
    # 遍历每个类，针对每一个类，重构ClassFeaProb为概率值
    for classid in ClassFeaDic.keys():
        #Multinomial Distribution
        sum = ClassFreq[classid] #每类文章总数
        #newsum = (float)(sum+len(WordDic)*DefaultFreq)
        newsum = (float)(sum + 1)
        #Binary Distribution
        #newsum = (float)(ClassFreq[classid]+2*DefaultFreq)
        for wid in ClassFeaDic[classid].keys():
            ClassFeaProb[classid][wid] = (float)(ClassFeaDic[classid][wid]+DefaultFreq)/newsum
        ClassDefaultProb[classid] = (float)(DefaultFreq) / newsum
    return

二、面试题

1、朴素贝叶斯算法，对缺失值、异常值是否敏感？

朴素贝叶斯是一种对缺失值不敏感的分类器，朴素贝叶斯算法能够处理缺失的数据，在算法的建模时和预测时数据的属性都是单独处理的。因此如果一个数据实例缺失了一个属性的数值，在建模时将被忽略，不影响类条件概率的计算，在预测时，计算数据实例是否属于某类的概率时也将忽略缺失属性，不影响最终结果。

朴素贝叶斯是一种对异常值不敏感的分类器，保留数据中的异常值，常常可以保持贝叶斯算法的整体精度，如果对原始数据进行降噪训练，分类器可能会因为失去部分异常值的信息而导致泛化能力下降。

2、朴素贝叶斯为什么适合增量计算？

因为朴素贝叶斯在训练过程中实际只需要计算出各个类别的概率和各个特征的类条件概率，这些概率值可以快速的根据增量数据进行更新，无需重新全量训练，所以其十分适合增量计算，该特性可以使用在超出内存的大量数据计算和按小时级等获取的数据计算中。

3、朴素贝叶斯的优缺点？

优点：

1.对小规模的数据表现很好，能处理多分类任务，适合增量式训练，尤其是数据量超出内存时，我们可以一批批的去增量训练。

2.对缺失数据不太敏感，算法也比较简单，常用于文本分类。

缺点：

1.理论上，朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为朴素贝叶斯模型给定输出类别的情况下,假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。