基于朴素贝叶斯算法的垃圾邮件分类(Python实现).

Presentation基于朴素贝叶斯算法的垃圾邮件分类(Python实现)EastChinaNormalUniversity2020年1月3日CONTENTS目录0简介1回顾：基本方法2算法3拉普拉斯平滑4实例：邮件分类5流行学习2020年1月3日EastChinaNormalUniversity简介朴素贝叶斯法：是基于贝叶斯定理和特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型对于给定的输入x，利用贝叶斯定理求出后验概率最大的输出y.朴素贝叶斯法实现简单，学习和预测的效率都很高，是业界常用的一种方法。2020年1月3日EastChinaNormalUniversity在从数学角度来说，分类问题可做如下定义：设输入空间𝒳⊆𝑅𝑛为n维向量的集合，输出空间为类标记集合𝒴={𝑐1,𝑐2,𝑐3,……,𝑐𝑘}。输入为特征向量𝓍∈𝒳，确定映射规𝓎=𝑓(𝓍),则输出为类标记𝓎∈𝒴。不考虑模糊数学里的模糊集情况。例如，医生对病人进行诊断就是一个典型的分类过程，任何一个医生都无法直接看到病人的病情，只能观察病人表现出的症状Review1:分类问题综述12020年1月3日EastChinaNormalUniversity垃圾邮件非垃圾邮件……各种化验检测数据来推断病情，这时医生就好比一个分类器，而这个医生诊断的准确率，与他当初受到的教育方式（构造方法）、病人的症状是否突出（待分类数据的特性）以及医生的经验多少（训练样本数量）都有密切关系。回顾算法拉普拉斯平滑邮件分类流行学习小结朴素贝叶斯法通过训练数据集学习联合概率分布P(X,Y)。具体地学习先验概率分布和条件概率分布。先验概率分布:P(Y=𝑐𝑘),k=1,2,…,K条件概率分布（假设𝓍(𝑗)可取值𝑆𝑗个，𝑗=1,2…,𝑛,𝑌可取值有𝑘个，本project中即邮件第j个特征可取值S个值，S=2）：P(X=𝓍|Y=𝑐𝑘)=P(𝑋(1)=𝓍(1),…,𝑋(𝑛)=𝓍(𝑛)|Y=𝑐𝑘),k=1,2,…,K朴素贝叶斯法对条件概率做了条件独立性的假设，P(X=𝓍|Y=𝑐𝑘)=P(𝑋(1)=𝓍(1),…,𝑋(𝑛)=𝓍(𝑛)|Y=𝑐𝑘)=P(𝑋(𝑗)=𝓍(𝑗)|Y=𝑐𝑘)𝑛𝑗朴素贝叶斯分类器可以表示为：𝓎=𝑓(𝓍)=argmaxP(Y=𝑐𝑘)P(𝑋(𝑗)=𝓍(𝑗)𝑗|Y=𝑐𝑘)P(Y=𝑐𝑘)𝑘P(𝑋(𝑗)=𝓍(𝑗)𝑗|Y=𝑐𝑘)注意到分母对所有的𝑐𝑘都是相同的，所以𝓎=𝑓(𝓍)=argmaxP(Y=𝑐𝑘)P(𝑋(𝑗)=𝓍(𝑗)𝑗|Y=𝑐𝑘)Review2:贝叶斯定理2020年1月3日EastChinaNormalUniversity回顾算法拉普拉斯平滑邮件分类流行学习小结算法：2020年1月3日EastChinaNormalUniversityRIDageincomestudentcredit_ratingclass_buy_pc1youthhighnofairno2youthhighnoexcellentno3midhighnofairyes4seniormediumnofairyes5seniorlowyesfairyes6seniorlowyesexcellentno7midlowyesexcellentyes8youthmediumnofairno9youthlowyesfairyes10seniormediumyesfairyes11youthmediumyesexcellentyes12midmediumnoexcellentyes13midhighyesfairyes14seniormediumnoexcellentnoTrain_dataset(表格来源：数据挖掘:概念与技术第3版)回顾算法拉普拉斯平滑邮件分类流行学习小结2020年1月3日EastChinaNormalUniversitytest:X=(age=youth,income=mediu,student=yes,credit_rating=fair)(1)计算先验概率P(buy_pc=yes)=9/14=0.643P(buy_pc=no)=5/14=0.357条件概率：P(age=youth|buy_pc=yes)=2/9=0.22P(age=youth|buy_pc=no)=2/5=0.600P(income=medium|buy_pc=yes)=4/9=0.444P(income=medium|buy_pc=no)=2/5=0.400P(student=yes|buy_pc)=1/5=0.200P(credit_rating=fair|buy_pc=yes)=6/9=0.667P(credit_rating=fair|buy_pc=no)=2/5=0.400回顾算法拉普拉斯平滑邮件分类流行学习小结2020年1月3日EastChinaNormalUniversitytest:X=(age=youth,income=mediu,student=yes,credit_rating=fair)(2)对于给定的实例test:X，计算Y=𝑐𝑘P(𝑋(𝑗)=𝓍(𝑗)𝑗|Y=𝑐𝑘)，k=1,2,…,KP(X|buy=yes)=P(age=youth|buy_pc=yes)*P(income=medim|buy_pc=yes)*P(student=yes|buy_pc=yes)*P(credit_rating=fair|buy_pc=yes)=0.222*0.444*0.667*0.667=0.044同理：P(X|buy=no)=0.600*0.400*0.200*0.400=0.019找出最大化的P(X|Y=𝑐𝑘)P(Y=𝑐𝑘)的类计算P(X|buy=yes)P(buy=yes)=0.044*0.463=0.228P(X|buy=no)P(buy=no)=0.019*0.357=0.007(3)确定实例x的类0.04440.019,朴素贝叶斯分类预测test:X的类为buy_pc=yes.回顾算法拉普拉斯平滑邮件分类流行学习小结如果遇到零概率值怎么办？拉普拉斯平滑。EastChinaNormalUniversity如果得到某个P(𝑋(𝑗)=𝓍(𝑗)|Y=𝑐𝑘)的零概率值，将其代入P(X=𝓍|Y=𝑐𝑘)=P(𝑋(𝑗)=𝓍(𝑗)|Y=𝑐𝑘)𝑛𝑗将返回P(X=𝓍|Y=𝑐𝑘)的概率为零！一个零概率将消除乘积中设计的所有其他（后验）概率的影响。怎么避免这样的问题呢？条件概率的贝叶斯估计：𝑝𝜆(𝑋(𝑗)=𝑎𝑗𝑙|Y=𝑐𝑘)=𝐼𝑥𝑖(𝑗)=𝑎𝑗𝑙,𝑦𝑖=𝑐𝑘+𝜆𝑁𝑖=1𝐼𝑦𝑖=𝑐𝑘+𝑆𝑗𝜆𝑁𝑖=1其中𝜆≥0等价于在随机变量各个取值的频数赋予一个正数𝜆。当𝜆=0时，最大似然估计，𝜆=1时成为拉普拉斯平滑。同样先验概率的贝叶斯估计为：𝑝𝜆(Y=𝑐𝑘)=𝐼𝑦𝑖=𝑐𝑘+𝜆𝑁𝑖=1𝑁+𝐾𝜆其中𝑥𝑖(𝑗)表示第i个样本的第j个特征，𝑎𝑗𝑙表示第个特征可能去第𝑙个值,I为指示函数。2020年1月3日回顾算法拉普拉斯平滑邮件分类流行学习小结流程图：EastChinaNormalUniversity获取训练样本确定特征属性对每个类计算P(𝑦𝑖)对每个特征属性就按所有划分的条件概率对每个类别计算P(x|𝑦𝑖)以P(x|𝑦𝑖)P(Y=𝑐𝑘)最大项作为x的所属类别准备阶段分类器训练阶段应用阶段2020年1月3日回顾算法拉普拉斯平滑邮件分类流行学习小结准备数据从文本中构建词向量（贝努利模型）EastChinaNormalUniversity从文本中构建邮件向量（words2vec）：通常有两种实现方式：一种是基于贝努利模型，一种是基于多项式模型实现。我们采用前一种实现方式，将每个词的出现与否作为一个特征（词集模型，相对应的是词袋模型），不考虑单词在文档中出现的次数，因此在这个意义上相当于每个假设词是等权重的。具体如下：(1）遍历所有邮件,创建一个包含所有文档中出现的不重复的单词集合（即特征）。(2)对于每一封邮件创建一个与单词集合等长的0向量。接着遍历邮件中所有单词，如果出现在单词集合中则把对应的值设为1。2020年1月3日回顾算法拉普拉斯平滑邮件分类流行学习小结训练模型（技巧小结）EastChinaNormalUniversity遍历所有训练集，计算所需要的先验概率和条件概率，构建分类器模型。根据前面的分析，如果一个概率值为0,那么最后的乘积都为0,为降低这种影响，可以将所有的词的出现频率初试话为1，并将分母初始化为2。另外由于数据维度过高，当计算P(X=𝓍|Y=𝑐𝑘)=P(𝑋(𝑗)=𝓍(𝑗)|Y=𝑐𝑘)𝑛𝑗时，多个很小的数相乘可能会出现下溢或者浮点数舍入导致错误，我们可以对乘积取自然对数。即ln（a*b）=ln(a)+ln(b)。2020年1月3日回顾算法拉普拉斯平滑邮件分类流行学习小结交叉验证（1000）EastChinaNormalUniversity[百分比][百分比]测试结果错误正确正确错误64936准确率：0.936%2020年1月3日回顾算法拉普拉斯平滑邮件分类流行学习小结流形学习2020年1月3日EastChinaNormalUniversity本质上，流形学习就是给数据降维的过程。这里假设数据是一个随机样本，采样自一个高维欧氏空间中的流形（manifold），流形学习的任务就是把这个高维流形映射到一个低维（例如2维）的空间里。流形学习可以分为线性算法和非线性算法，前者包括主成分分析（PCA）和线性判别分析（LDA），后者包括等距映射（Isomap），拉普拉斯特征映射（LE）等。流形学习可以用于特征的降维和提取，为后续的基于特征的分析，如聚类和分类，做铺垫，也可以直接应用于数据可视化等。回顾算法拉普拉斯平滑邮件分类流行学习小结流形学习2020年1月3日EastChinaNormalUniversity回顾算法拉普拉斯平滑邮件分类流行学习小结流形学习2020年1月3日EastChinaNormalUniversity回顾算法拉普拉斯平滑邮件分类流行学习小结流形学习2020年1月3日EastChinaNormalUniversity回顾算法拉普拉斯平滑邮件分类流行学习小结流形学习(DIM)2020年1月3日EastChinaNormalUniversity算法的输入是所有数据在高维情况下两两之间的距离（记i与j的距离为Dij）。现在以降到2维为例说明这个算法。首先我们把所有数据点随机绘制在一张二维图像上，然后计算它们两两之间的距离dij，然后我们计算出它与高维距离Dij的误差，根据这些误差，我们将每对数据点按比例移近或移远，然后重新计算所有dij，不断重复到我们没法减少误差为止。假设有n个点:(1)输入每一对点之间的距离Dij。(2)随机在2维平面生成n个点，点i坐标记为x[i]、y[i]，计算它们两之间的距离，记为dij.(3)对所有i和j计算：eij=(dij-Dij)/Dij，每个点用一个二维的值grad[k]来表示它要移动的距离的比例因子(初始为0，0)。在计算出每个eij后，计算((x[i]-x[j])/dij)*eij，然后把它加到grad[i][x]上，同样把((y[i]-y[j])/dij)*eij加到grad[i][y]上。(4)把所有eij的绝对值相加，为总误差，与前一次的总误差比较(初始化为无穷大)，大于前一次的话就停止。否则把它作为上一次总误差，继续。对每个点，新的坐标为x[i]-=rate*grad[i][x]y[i]-=rate*grad[i][y]，其中r