7850人阅读
机器学习可以解决很多问题，其中最为重要的两个是 回归与分类。 这两个问题怎么解决， 它们之间又有什么区别呢？ 以下举几个简单的例子，以给大家一个概念
1. 线性回归
回归分析常用于分析两个变量X和Y 之间的关系。 比如 X＝房子大小 和 Y＝房价 之间的关系， X=(公园人流量，公园门票票价） 与 Y=(公园收入) 之间的关系等等。
那么你的数据点在图上可以这么看
现在你想找到 房子大小和房价的关系， 也就是一个函数f(x) = y. 能够很好的表示 这两个变量之间的关系。
于是你需要大概评估一下这个 房子大小和房价大概是一个什么关系.
是线性的关系吗? 还是非线性的关系?
当然在这个问题里面， 线性的关系更符合这两者的关系。于是我们 选择一个合适的 线性模型, 最常用的是 f(x) = ax+b.&
然后用这个线性的模型 去 匹配这些数据点。
1.1 怎么匹配?&
有了数据点 和 你臆想出来的线性模型，怎么进行匹配，也就是怎么用这根线最好地描述些数据点的关系?
需要最好地描述点, 我们又需要一个关于“好”的定义。你也可以想出很多关于“好”的定义。下面有两个,
这两个定义都是 将模型与数据点之间的距离差 之和做为 衡量匹配好坏的标准。 &误差越小, &匹配程度越大。
但是 总的来说， 我们想要找到的模型， 最后是想要使 f(x) 最大程度地 与y相似， 所以我们想要尽量地减少 f(x)与y之间的差值。 所以在这里 用第二个图的“好的定义” 来评估这根线的匹配程度是很合理的。于是我们有了误差公式!!!!!
这个公式，说的是，可以通过调整不同的a 和 b的值，就能使 误差不断变化，而当你找到这个公式的最小值时，你就能得到最好的a,b. 而这对(a,b)就是能最好描述你数据关系的模型参数。
1.1.1 沿导数下降法(Gradient Descent)
怎么找 cost(a,b)的最小? cost(a,b) 的图像其实像一个碗 一样，有一个最低点。 找这个最低点的办法就是，先随便找一个点(e.g. a=3, b = 2), 然后 沿着这个碗下降的方向找，最后就能找到碗的最低点。
cost(a,b) 的形状
怎么找(某一点)碗下降的方向?? 答案是，找那一点导数的反方向。拿参数a 举个例子, &a与cost 关系如下图,
只要将任意一个a, 沿着使cost 导数的反方向 慢慢移动，那么 最终有一天a值就会到达使 cost 最小的那一点. 于是你可以不断地移动a,b, 向着最低点前进。
当然在进行移动的时候也需要考虑，每次移动的速度，也就是\Alpha的值，这个值也叫做（学习率）. 学习率的增大可以加速参数逼近最优的情况， 但是如果在快要到达函数的底端的时候，需要减小学习率，以免出现cost 不断增大或者不停摆动的情况(如下图, J(a,b)就是cost(a,b) )。 所以说，当出现以上两种情况时候，我们应该果断选取一个较小的学习率，
以保证cost能减少到一个稳定的值(我们称为 收敛converge).&
1.1.2 直接求解最小点方法
这时候，有的人会问，为什么要让a不停地往下跑呢？ 而且还需要设定学习率， 多麻烦， 直接让找 导数为0点(最小极值)， 不就可以了吗? 嗯。。。也可以...但是各有优缺，
具体方法和优劣分析可见&的博客:&
总结一下： &回归问题的解决方法是:
& & &1. 假定一个模型 & 2. &定义什么叫做最好的匹配(构造误差函数) & 3. 用这个模型去匹配已有的数据点(训练集)
需要进一步讨论的问题:
如果参数(a,b)更多了该怎么办?如果最合适的匹配模型并不是线性的怎么办? & －－－ 选用一个 非线性模型 &比如 &y = ax^2 + bx + c.如果误差(cost)与a,b（模型参数）的关系不是像碗一样的, 而是凹凸不平的该怎么办? ------ & 这时候你就得注意你得到的cost的最低点(局部的最低)可能因初始点的不同而不同。 而这些最低点你需要进行比较，以确定是不是全局的最低
2.分类(Logistic regression)
分类问题也是一类很常见的问题。 比如说，怎么判定一个人是高富帅还是吊丝? 假如我是中央电视台的记者，采访了N个人, 拿到了第一手资料。资料如下
我们想要根据一个人的口袋钱数量，来预测一个人是(富帅) 还是 （吊丝）. &我们能不能用回归的方法做呢?
显然是可以的， 我们只要找到一个模型，然后再进行匹配就可以了。
但是因为分类问题的y值常常是一些离散的数字，(比如， 富帅为1, 吊丝为0)， 所以我们已经不能用一个简单的线性函数来拟合这些数据了。我们需要一个更逼真的模型。&
于是我们引入了一个更适合处理分类问题的函数--- 一个非线性函数， 阶跃函数。
这个函数的形状更像我们分类问题的数据分布，所以，用他来拟合分类问题的数据将更适合！
所以我们有了一个新的模型,&
通过调整a,b 的值，可以让模型不断改变以匹配数据点。 为了匹配数据点，我们又需要一个衡量匹配程度的函数，就像 回归问题一样的cost 函数. 于是同理我们可以得到cost
于是我们急切地想要把它用我们之前的gradient descent 的方法求解出使cost 最小的两个a,b值。 但是很遗憾的是， 这个cost函数关于a,b,是非凸(non-convex)的。 就像下面那张图那样坑坑洼洼。。。
所以你没有办法通过以上两种方法(1.1.1和1.1.2)求出这个cost函数的全局最小值。
所以你需要构造一个更好的cost函数， 在可以衡量拟合程度的同时 又是一个关于a,b 的凸函数(像回归问题的cost一样，和一个碗一样，只有一个极小值).&
这怎么构造啊....
幸好我们还有各种伟大的数学家，他们夜以继日，终于赶制出了一个形状和碗一样(convex)的cost函数. (Maximum&Likelihoods&Estimation 更具体的介绍请看&)
现在我们又可以用我们熟悉的 导数方向下降法(gradient descent) 移动a, b的值，使cost 降低到最小。
最后，分类的问题就这样被解决了。
当然，更复杂的问题可能有:
现在是分成两类，如果数据需要分成三类或者更多该怎么办? &---- 假如有A,B,C三类， 把其中A类做为1，BC做为0,然后做Logistic regression, 得到模型a, 同理将B类做为1,AC作为0,得到模型b, 再同理得到模型c. & &最后测试的时候， 对任意一个数据点x, 我们能够得到x分别属于A,B,C三类的概率值&
最后比较大小，哪个大，这个x就属于哪一类
& & & & & & &具体可看,&&(七)
3.总结(两个问题的区别)
这篇文章大概的意图是能想让大家了解， 机器学习中最基本的两类问题，线性回归和分类。 能让大家有个清晰的思想，对于这两类问题都有以下几个步骤,
如何选取一个&合理的模型(线性的，or 非线性的(e.g. 阶跃函数， 高斯函数)).制造一个&美好&的&误差函数&(可以评估拟合程度，而且还是convex函数)采取一切可能的技术(e.g. 导数下降法，解极值方程法) 求出最好的模型参数
谈谈回归和分类的区别：
总的来说两个问题本质上都是一致的，就是模型的拟合（匹配）。 但是分类问题的y值(也称为label), 更离散化一些. 而且， 同一个y值可能对应着一大批的x, &这些x是具有一定范围的。&
所以分类问题更多的是 (一定区域的一些x) 对应 着 (一个y). & 而回归问题的模型更倾向于 (很小区域内的x，或者一般是一个x) &对应着 &(一个y).
在把一个问题建模的时候一定要考虑好需求，让你的模型更好的与现实问题相对应。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：52052次
排名：千里之外
原创：16篇
评论：97条
(2)(2)(4)(3)(6)机器学习-分类简介
时间： 17:49:42
&&&& 阅读：45
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&一 分类概述
& & &分类在数据挖掘中是一项非常重要的任务。分类的目的是学会一个分类函数或分类模型（也常常称作为分类器),该模型能把数据库中的数据项映射到给定类别中的某一个类别。
& & & 分类属于一种有指导的学习，模型的学习是在被告知每个训练样本属于哪个类的“指导”下进行的，并随机的从样本群选取。每个训练样本还有一个特定的类标签与之对应，它不用于无指导的学习（聚类）。
&二 分类器
&& & &分类器的构造方法有统计方法、机器方法、神经网络方法等。
& & & &包括贝叶斯和非参数法。常见的临近学习或基于事例的学习属于非参数方法。对应的知识表示则为判别函数和原型事例。
机器学习方法
& & & 包括决策树法和规则归纳法。前者对应的表示为决策树或判别树，后者则有决策表和产生式规则等。
神经网络方法
& & & & 主要是BP算法，它的模型表示是前向反馈神经网络模型(由代表神经元的结点和代表联接权值的边组成的一种体系结构),BP算法本质上是一种非线性判别函数。
& & & &另外，许多技术，如粗糙集等，都可以用于分类器构造中。
& & & &分类方法归结为四种类型：基于距离的分类方法（最临近方法）、决策树分类方法（ID3和C4.5算法）、贝叶斯分类方法（朴素贝叶斯算法和EM算法）和规则归纳（AQ算法、CN2算法和FOIL算法）等。
& & & &要构造分类器，需要有一个训练样本数据作为输入。分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。
& & &一般地，数据分类分为两个步骤，建模和使用：
& & & & & &1. 建立一个模型，描述预定的数据集或概念集
& & & & & &2. 使用模型进行分类
注：使用模型前需要评估模型的预测准确率。保持(Holdout）方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立于训练样本。模型在给定的测试集上的准确率是被模型正确分类的测试样本的百分比。对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。如果模型的准确率根据训练数据集进行评估，评估可能是乐观的，因为学习模型倾向于过分拟合数据。因此，使用交叉验证来评估模型是比较合理的。
三 &朴素贝叶斯分类
& & & 贝叶斯分类是统计分类方法。基本思想：首先计算每个分类的先验概率，然后在每种分类上计算待分类样本的后验概率，在哪个分类上的后验概率大就属于哪个分类。
& & &&贝叶斯分类器的分类是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，所谓的后验概率也就是该对象属于某一类的概率，然后选择具有最大后验概率的类作为该对象所属的类，即在哪个分类上的后验概率大就属于哪个分类。
& & &&朴素贝叶斯分类器基于一个简单的假定：给定目标值时属性之间相互条件独立。
& & &每个数据样本用一个n维特征向量表示，分别描述对n个属性A1,A2,A3,......,An样本的n个度量。
& & & 假定有m个类C1,C2,......,Cm，给定一个不知类别的数据样本X，分类器将预测X属于具有最高后验概率(条件X下）的类。也就是说朴素贝叶斯分类将未知的样本分配给类Ci(1&=i&=m）当且仅当P(Ci | X) & P(Cj | X)，对任意的j=1,2,.....,m,j!=i.这样最大化的P(Ci|X)对应的类Ci称为最大后验假定，而P(Ci|X)可以根据下面的贝叶斯定理来确定:
& & & & & & & & & & & & & & & & & & & & & & & & & &&
& & & 由于P(X)对于所有类为常数，只需要P(X|Ci)P(Ci)最大即可。如果Ci类的先验概率未知，则通常假定这些类是等概率的，即P(C1)=P(C2)=.....=P(Cm),假设不是等概率，那么类的先验概率可以用P(Ci)=Si/S计算，其中Si是类Ci中的训练样本数，而S是训练样本总数。因此问题就转化为对P(X|Ci)的最大化。P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设。
& & &给定具有许多属性的数据集，计算P(X|Ci)的开销是可能非常大。为降低计算P(X|Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间不存在依赖关系。这样：
& & & & & & & & & & & & & & && & & & & & & &&
& 其中概率P(x1|Ci)、P(x2|C2)、P(x3|C3),.....,P(xn|Cn)可以由训练样本估值。
& & & &如果Ak是离散属性，则P(xk|Ci) = sik/si,其中sik是在属性Ak上具有值xk的类Ci的训练样本数，而si是Ci的训练样本数。
三 决策树分类
& & &&从数据中生成分类器的一个特别有效的方法是生成一个决策树（Decision Tree)，决策树表示方法是应用最广泛的逻辑方法之一，它从一组无序、无规则的事例中推理出决策树表示形式的分类规则。
& & & 决策树方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶节点得到结论。
& & &&决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。一棵典型的决策树如下图所示。内部结点用矩形表示，而树叶节点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。
& &&&&决策树从根到叶结点的一条路径就对应者一条合取规则，因此决策树容易转换成分类规则。
& & & &多叉树的内部结点是属性，边是该属性的所有取值，有几个取值，就有几条边。数据的叶子结点都是类别标记。
& & & &决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3、CN2、SQIQ、SPRINT等。大多数已开发的决策树是一种核心算法的变体。
& & &&ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使系统熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点的熵值为0，此时，每个叶子节点对应的实例属于同一类。
& & & &决策树分类算法通常分为两个步骤，决策树生成和决策树修剪。
&&在信息论中，熵被用来衡量一个随机变量出现的期望值，它是随机变量的期望，用来度量信息的不确定程度。熵是整个系统的平均消息量。
一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。处理信息就是为了把信息搞清楚，就是熵减少的过程。一个属性的熵越大，它蕴含的不确定信息越大，越有利于数据的分类。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并尽量确保找到一棵简单的树来刻画相关的信息。
& & &&&信息论中，事件ai的信息量（又叫信息本体）I(ai&)可如下度量：
& & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & &&&&其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量(又叫先验熵)可如下度量：
& & & & & & & & & & &
& & & 设S是s个数据样本的集合。假设类标号属性具有m个不同的值，定义m个不同类
Ci（i=1,2,....,m)。设si是Ci中样本的个数。对一个给定的样本分类所需的期望信息量有下面
& & & & & & & & & & & & &&&
& & &&&其中pi是任意样本属于Ci的概率，一般可用si/s来估计。
& & & 设属性A具有v个不同的值{a1,a2,...,av}。可以用属性A将S划分为v个子集{S1,S2,....Sv},其
中Sj包含S中这样的一些样本，它们在A上具有值aj。如果用A作为测试属性(即最好的分裂
属性),则这些子集对应于包含集合S的结点生长出来的分支。
& & & 设sij是集合Sj中类Ci的样本数。根据由属性A划分子集的熵由下式给出:
& & & & & & & & & & & & & & &
& & & & & & &&
&&充当第j个子集的权，并且等于字集(即A值为aj)中样本个数除以S中样本总数。熵值越小，子集划分的纯度越高，说明选择属性A作为决策节点的效果
& & & & & & &&
& & & &由期望信息和熵值可以得到对应的信息增益值。对于在A上分支将获得的信息增益可
以由下面的公式得到:
& & & & & & & & & & & &
& & & & & 信息增益就是这两个熵的差值。熵表示系统的不稳定程度，Gain（S，A）越大，系统熵减小的也就越快，表示条件A对于确定系统的贡献越大,说明选择测试属性A作为决策节点对分类提供的信息越多，系统趋于稳定的速度也更快。
& & &&ID3根据信息增益，运用自顶向下的贪心策略建立决策树。信息增益用于度量某个属性对样本集合分类的好坏程度。由于采用了信息增益，ID3算法建立的决策树规模比较小，查询速度快。
ID3算法缺点
&信息增益度度量存在一个内在偏置，它偏袒具有较多值的属性，举一个极端的例子，如果有一个属性为日期，那么将有大量的值，太多的属性值把训练样例分割成非成小的空间，单独的日期就可能完全预测训练数据的目标属性，因此，这个属性可能会有非常高的信息增益，该属性可能会被选为根结点的决策属性并形成一棵深度为一级但却非常宽的树，这棵树可以理想的分类训练数据。但是这个决策树对于测试数据的分类性能可能会非常差，因为它过分完美地分割了训练数据，它不是一个好的分类器。
& & & &除此之外，ID3算法增长树的每一个分支深度，指导恰好能对训练样例完美的分类。然而整个策略并非行得通。事实上，当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性采样时，这个策略便会遇到困难，导致过度拟合训练集。
& & &另外ID3算法只能处理离散类型的数据。
& & &&ID3算法在搜索的过程中不能进行回溯，每当在树的某一层次选择了一个属性进行测试，它不会再回溯重新考虑这个选择。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优的答案，而不是全局最优。
& & & ID3算法在搜索的每一步都使用当前的所有训练样例，以统计为基础决定怎样精化当前的假设。这与那些基于单独的训练样例递增作出决定的方法不同。使用所有样例的统计属性（例如：信息增益）的一个优点是大大降低了对个别训练样例错误的敏感性。因此，通过修改ID3算法的终止准则以接受不完全拟合训练数据的假设，是可以很容易的扩展到处理含有噪声的训练数据。
& & 有几种途径可被用来避免决策树学习中的过度拟合，它们分为两类:
& & & & &1.预先剪枝&及早停止树的增长，在ID3算法完美分类训练数据之前就停止树的增长。
& & & & &2.后剪枝&& & 即允许树过度拟合数据，然后对这个树进行后修剪。
& & &尽管第一种方法可能看起来更直接，但是对过度拟合的树进行后修剪的第二中方法在实践中更成功。这是因为在第一种方法中精确地估计何时停止树增长是很困难的。
C4.5算法概述
& & &C4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能。例如:
& & &&1.用信息增益比例的概念
& & & & & &
&&&& &这里属性A具有v个不同的值{a1,a2,...,av}。可以用属性A将S划分为v个子集{S1,S2,....Sv},其
中Sj包含S中这样的一些样本，它们在A上具有值aj。
&&&&&&2. 合并具有连续值的属性
&&&&&&&& ID3算法最初假定属性离散值，但在实际环境中，很多属性值是连续的。C4.5算法能够处理具有连续的属性值。
&&&&&3. 处理含有未知属性值的训练样本
& & & & &C4.5处理的样本可以含有未知属性值，其处理方法是用最常用的值替代或者将最常用的值分在同一类中。具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率依赖于该属性已知的值。
&&&&&4. 产生规则
& & & & 一旦树被简历，就可以把树转换成if-then规则。
& &&&&分类可用于预测，分类的目的是从历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预测。统计学中常用的预测方式是回归。数据挖掘中的分类和统计学中的回归方法是一对联系又有区别的概念。一般地，分类的输出是离散的类别值，而回归的输出则是连续数值。分类具有广泛的应用，例如垃圾邮件识别、信用卡系统的信用分级、图像的模式识别等。
标签：&&&&&&
&&&& &&&&&&
&& && && &&
版权所有 鲁ICP备号-4
打开技术之扣，分享程序人生！【机器学习实战】：C++实现基于概率论的分类方法--朴素贝叶斯分类（Naive Bayes Classifier） - 推酷
【机器学习实战】：C++实现基于概率论的分类方法--朴素贝叶斯分类（Naive Bayes Classifier）
朴素贝叶斯分类算法是机器学习中十分经典而且应用十分广泛的算法，下面将逐步学习和说明。
一、条件概率：
条件概率是概率论中的一个重要实用的概念。所考虑的是事件A已经发生的条件下事件B发生到概率。
（一）条件概率 定义
设A，B是两个事件，且P(A)&0，称：
P(B|A) = P(AB) / P(A)
为在事件A发生的条件下事件B发生的
（二）乘法定理
设P(A) & 0 ， 则有
P(AB) = P(B|A) * P(A)
&&&&& （三）全概率公式和贝叶斯公式
样本空间划分定义
：假设S为试验E的样本空间，B1,B2,B3..Bn为E的一组事件。若：
&&&&&&&& (i)&
&&&&&&&& (ii)
&&&&&&&& 则称B1,B2,B3...Bn为样本空间S的一个划分。若B1,B2,...,Bn是样本空间的一个划分，那么，对每次试验，事件B1,B2,B3...Bn中必有一个且仅有一个发生。
设试验E的样本空间为S，A为E的事件，B1,B2,...Bn为S的一个划分，且P(Bi)&0（i=1,2,...n），则：
&&&&&&&& P(A) = P(A|B1)*P(B1) + P(A|B2)*P(B2)+...+P(A|Bn)*P(Bn).& 此式成为
全概率公式
&&&&&&&& 在很多实际问题中P(A)不易直接求得，但是却容易找到S的一个划分B1,B2,...Bn，且P(Bi)和P(A|Bi)或为已知，或容易求得，那么就可以全概率公式求得P(A)。
设试验E的样本空间为S，A为E的事件，B1,B2,...,Bn为S的一个划分，且P(A)&0，P(Bi)&0 (i=1,2,...,n)，则
&&&&&&&&&&&&&
& & & & & &此式成为
贝叶斯公式
二、基于贝叶斯决策分类的分类方法：
在数据较少的情况下仍然有效，可以处理多类别问题；
对于输入数据的准备方式较为敏感；
使用数据类型：
标称性数据；
朴素贝叶斯是贝叶斯决策理论的一部分，所以讲述朴素贝叶斯分类之前有必要了解贝叶斯决策理论。我们之所以称之为“朴素”，是因为整个形式化过程只做最原始，最简单的假设。
假设我们有一个数据集，它由两类数据组成，数据分布：
1：两个参数已知的概率分布，参数决定分布形状。
我们现在用p1(x,y)表示数据点(x,y)属于类别1（图中用圆点表示的类别）的概率，用p2(x,y)表示数据点(x,y)属于类别2（图中用三角形表示的类别）的概率，那么对于一个新数据点(x,y)，可以用下面的规则来判断它的类别：
如果p1(x,y) & p2(x,y) ，那么类别为1。
如果p1(x,y) & p2(x,y) ，那么类别为2。
也就是说，我们也选择搞概率对应的类别。这就是贝叶斯决策理论的核心思想，即选择具有最高概率的决策。
三、朴素贝叶斯的一般过程：
（1）收集数据：可以使用任何方法。
（2）准备数据：需要数值型或者布尔型数据。
（3）分析数据：有大量特征时，绘制特征作用不大，此时使用直方图效果更好。
（4）训练算法：计算不同的独立特征的条件概率。
（5）测试算法：计算错误率。
（6）使用算法：一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使用朴素贝叶斯分类器，不一定非要是文本。
四、文本分类：
要从文本中获取特征，需要先拆分文本。具体如何做？这里的特征是来自文本的词条（token），一个词条是字符的任意组合。可以把词条想象为单词，也可以使用非单词词条，如URL、IP地址或者任意其他字符串。
以在线社区的留言板为例。为了不影响社区的发展，我们要屏蔽侮辱性的言论，所以要构建一个快速过滤器，如果某条留言使用了负面或者侮辱性的语言，那么就该留言标识为内容不当。过滤这类内容是一个很常见的需求。对此问题建立两个类别，侮辱性和非侮辱性，使用1和0分别表示。
来设计数据结构和算法。
4.1 准备数据：从文本中构建词向量
把文本看成单词向量或者词条向量，也就是说将句子转换为向量。考虑出现在所有文档中的所有单词，再决定将哪些词纳入词汇表或者说所要的词汇集合，然后必须要将每一篇文档转换为在词汇表上的向量，为什么要这么做，不着急，先往下看。
4-1：词表到向量的转换函数：
* code list 4-1 : transfer func from docs list to vocabulary list
#include&iostream&
#include&map&
#include&set&
#include&vector&
#include&algorithm&
#include&numeric&
#include&cstring&
#include&stdio.h&
#include&cstdlib&
string posting_list[6][10]={
{&my&,&dog&,&has&,&flea&,&problems&,&help&,&please&,&null&},
{&maybe&,&not&,&take&,&him&,&to&,&dog&,&park&,&stupid&,&null&},
{&my&,&dalmation&,&is&,&so&,&cute&,&I&,&love&,&him&,&null&},
{&stop&,&posting&,&stupid&,&worthless&,&garbage&,&null&},
{&mr&,&licks&,&ate&,&my&,&steak&,&how&,&to&,&stop&,&him&,&null&},
{&quit&,&buying&,&worthless&,&dog&,&food&,&stupid&,&null&}
int class_vec[6] = {0,1,0,1,0,1};
//1 is abusive ,0 not
class NaiveBayes
vector& vector&string& & list_of_
//词条向量
vector&int& list_
map&string,int&
//单词列表
int *return_
NaiveBayes()
//posting_list --& list_of_posts
vector&string&
for(int i=0;i&6;i++)
vec.clear();
for(int j=0;posting_list[i][j]!=&null&;j++)
vec.push_back( posting_list[i][j] );
list_of_posts.push_back( vec );
//class_vec --& list_classes
for(int i=0;i&sizeof(class_vec)/sizeof(class_vec[0]);i++)
list_classes.push_back( class_vec[i] );
void create_vocab_list()
vector& vector&string& & :: iterator it = list_of_posts.begin();
int index = 1;
while( it!=list_of_posts.end() )
vector&string& vec = *
vector&string& :: iterator tmp_it = vec.begin();
while( tmp_it!=vec.end() )
if( my_vocab_list[*tmp_it] == 0 )
my_vocab_list[*tmp_it] = index++; //index is the location of the vocabulary
map&string,int&::const_iterator itt = my_vocab_list.begin();
while( itt!=my_vocab_list.end() )
cout&&itt-&first&&& &&&itt-&second&&&
}//create_vocab_list
//set some one doc to vec with 0 and 1.
void set_of_words_to_vec(int idx)
cout&&&set of words to vec begin the document id is : &&&idx&&
int len = my_vocab_list.size()+1;
return_vec = new int[ len ](); //pay attention to the difference between &new int[len]&. initalize all the element to zero.
fill(return_vec,return_vec+len,0);
for(int i=0;i&i++)
cout&&return_vec[i]&&& &;
for( int i=0;posting_list[idx][i]!=&null&;i++ )
int pos = my_vocab_list[ posting_list[idx][i] ];
if( pos != 0 )
return_vec[pos] = 1;
}//set_of_words_to_vec
void print()
cout&&&print the return_vec begin :&&&
int len = my_vocab_list.size()+1;
cout&&&len = &&&len&&
for(int i=0;i&i++)
cout&&return_vec[i]&&& &;
delete [] return_
}//print()
int main()
nb.create_vocab_list();
nb.set_of_words_to_vec(5);
nb.print();
system(&pause&) ;
&NaiveBayes()
：构造函数做了两方面的工作，其一，初始化了词条切分后的文档集合list_of_posts，即将posting_list转换为list_of_posts，其中list_of_posts中的每一个分量就是一个文档，这些文档来自斑点犬爱好者留言板；其二，用class_vec去初始化类的私有成员变量list_classes，它是类别标签的集合，分为两类，侮辱性和非侮辱性。这些文本的类别由人工标注，这些标注信息用于训练程序以便自动检测侮辱性留言。
&create_vocab_list()
：创建一个包含在所有文档中出现的不重复词的列表。定义私有成员变量map&string,int& &my_vocab_ key是代表单词，value则代表单词在my_vocab_list中的位置（下标）。
&set_of_words_to_vec(int idx)
：该函数的输入参数为某个文档的下标值idx，得到了return_vec，即下标为idx的文档向量，向量的每个元素为1或者0，分别表示词汇表中的单词在输入文档中是否出现。首先根据词表长度获得文档向量长度，并用STL中的fill将其元素都设为0；遍历下标为idx的文档中所有单词，得到在词汇表my_vocab_list中的位置pos，然后根据pos将return_vec中对应的值设置为1。该函数使用词汇表或者想要检查的所有单词作为输入，一旦给定一篇文档（斑点犬网站上的一条留言），该文档就会被转换为词向量。
：打印得到的文档向量return_vec。
4.2：训练算法：从词向量计算概率：
前面介绍了如何将一组单词转换为一组数字，接下来看如何使用这些数字来计算概率。现在已经知道一个词是否出现在一篇文档中，也知道该文档所属的类别。那么我们将对某个文档转换成为文档向量W后进行分类，实际上就是计算在W的条件下，类别为Ci的概率。
p(Ci | W) = p( W | Ci ) / p( W&
：就是需要分类的词向量；
我们将使用上述公式，对于每个类计算该值，然后比较这两个概率值的大小。如何计算？
首先可以通过类别i（侮辱性留言或非侮辱性留言）中文档数除以总的文档数来计算概率p(Ci)。
这里就要用到朴素贝叶斯假设。如果将向量W展开为一个个独立特征，那么就可以将上述概率写作p(W0,W1,W2...Wn)。这里假设所有词都相互独立，该假设也称作条件独立性假设，它意味着可以用P(W0|Ci)
)来计算上述概率，这就极大地简化了计算的过程。
该函数的伪代码如下：
计算每个类别中的文档数目：
对每篇训练文档：
对每个类别：
如果词条出现文档中--&增加该词条的计数值
增加所有词条的计数值
对每个类别：
对每个词条：
将该词条的数目除以总词条数目得到条件概率
返回每个类别的条件概率
4-2：朴素贝叶斯分类器训练函数：
* code list 4-1 : transfer func from docs list to vocabulary list
* add code list 4-2 : training func on Naive Bayes Classifier
#include&iostream&
#include&map&
#include&set&
#include&vector&
#include&algorithm&
#include&numeric&
#include&cstring&
#include&stdio.h&
#include&cstdlib&
string posting_list[6][10]={
{&my&,&dog&,&has&,&flea&,&problems&,&help&,&please&,&null&},
{&maybe&,&not&,&take&,&him&,&to&,&dog&,&park&,&stupid&,&null&},
{&my&,&dalmation&,&is&,&so&,&cute&,&I&,&love&,&him&,&null&},
{&stop&,&posting&,&stupid&,&worthless&,&garbage&,&null&},
{&mr&,&licks&,&ate&,&my&,&steak&,&how&,&to&,&stop&,&him&,&null&},
{&quit&,&buying&,&worthless&,&dog&,&food&,&stupid&,&null&}
int class_vec[6] = {0,1,0,1,0,1};
//1 is abusive ,0 not
class NaiveBayes
vector& vector&string& & list_of_
vector&int& list_
map&string,int&
int *return_
vector& vector&int& & train_
NaiveBayes()
vector&string&
for(int i=0;i&6;i++)
vec.clear();
for(int j=0;posting_list[i][j]!=&null&;j++)
vec.push_back( posting_list[i][j] );
list_of_posts.push_back( vec );
for(int i=0;i&sizeof(class_vec)/sizeof(class_vec[0]);i++)
list_classes.push_back( class_vec[i] );
void create_vocab_list()
vector& vector&string& & :: iterator it = list_of_posts.begin();
int index = 1;
while( it!=list_of_posts.end() )
//vector&string& vec( *it.begin(),*it.end() );
vector&string& vec = *
vector&string& :: iterator tmp_it = vec.begin();
while( tmp_it!=vec.end() )
//cout&&*tmp_it&&& &;
if( my_vocab_list[*tmp_it] == 0 )
my_vocab_list[*tmp_it] = index++; //index is the location of the vovabulary
}//create_vocab_list
//set some one word to vec with 0 and 1.
void set_of_words_to_vec(int idx)
cout&&&set of words to vec begin the document id is : &&&idx&&
int len = my_vocab_list.size()+1;
return_vec = new int[ len ](); //pay attention to the difference between &new int[len]&. initalize all the element to zero.
fill(return_vec,return_vec+len,0);
for(int i=0;i&i++)
cout&&return_vec[i]&&& &;
for( int i=0;posting_list[idx][i]!=&null&;i++ )
//cout&&posting_list[idx][i]&&& &;
int pos = my_vocab_list[ posting_list[idx][i] ];
if( pos != 0 )
return_vec[pos] = 1;
}//set_of_words_to_vec
void get_train_matrix()
cout&&&get train matrix begin : &&&
train_mat.clear();
for(int i=0;i&6;i++)
set_of_words_to_vec(i);
vector&int& vec( return_vec , return_vec + my_vocab_list.size()+1 );
train_mat.push_back(vec);
delete []return_
}//get train matrix
void print()
cout&&&print the train matrix begin : &&&
vector& vector&int& & :: iterator it = train_mat.begin();
while(it!=train_mat.end())
vector&int& vec = *
vector&int& :: iterator itt = vec.begin();
while( itt!=vec.end())
cout&&*itt&&& &;
}//print()
void train_NB0()
int num_train_docs = train_mat.size();//sizeof(posting_lists)/sizeof(posting_lists[0]);
cout&&&num_train_docs = &&&num_train_docs&&
int num_words = train_mat[0].size() - 1 ;
/* calculatr the sum of the abusive classes */
int sum = accumulate(list_classes.begin(),list_classes.end(),0); //C++ STL accumulate()
cout&&&sum = &&&sum&&
float p_abusive = (float)sum/(float)num_train_
cout&&&p_abusive = &&&p_abusive&&
vector&float& p0vect(train_mat[0].size(),0); //the frequency of each word in non-absusive docs
vector&float& p1vect(train_mat[0].size(),0); //the frequency of each word in abusive docs
printf(&p0num.size() = %d , p1num.size() = %d\n&,p0vect.size(),p1vect.size());
float p0Denom = 0.0; //the total number of words in non-abusive docs
float p1Denom = 0.0; //the total number of words in abusive docs
/* calculate the p0num,p1num,p0Denom,p1Denom */
for(int i=0;i&list_classes.size();i++)
if(list_classes[i] == 1)
//abusive doc
for(int j=0;j&p1vect.size();j++)
p1vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p1Denom++;
//non-abusive doc
for(int j=0;j&p0vect.size();j++)
p0vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p0Denom++;
for(int i=0;i&p1vect.size();i++)
p0vect[i] = p0vect[i]/p0D
p1vect[i] = p1vect[i]/p1D
cout&&&print the p0vect values : &;
for(int i=0;i&p0vect.size();i++)
cout&&p0vect[i]&&& &;
cout&&&\nprint the p1vect values : &;
for(int i=0;i&p1vect.size();i++)
cout&&p1vect[i]&&& &;
int main()
nb.create_vocab_list();
nb.get_train_matrix();
nb.print();
nb.train_NB0();
system(&pause&) ;
代码中和4-1的代码相比，4-2增加了私有成员变量train_mat和公有成员函数train_NB0。其中：
train_mat：
文档矩阵。是由0,1组成的词向量矩阵，单个向量是一个文档转换成为和my_vocab_list等长的[0,1]数组。
朴素贝叶斯分类器训练函数。
首先，计算文档属于侮辱性文档（class=1）的概率：p_abusive，即P(1)。因为这是一个二类分类问题，所以可以通过1-P(1)得到P(0)。对于多于两类的分类问题，则需要对代码稍加修改。
计算P(Wi | C0)和
P(Wi | C1)，需要初始化程序中的分子变量
和分母变量p0Denom/p1Denom。在for循环中，要遍历训练集train_mat中的所有文档。每次某个词语（侮辱性或非侮辱性）在某一文档中出现，则该词在向量
p1vect对应的位置数值加一，而且在所有的文档中，该文档的总次数
也相应加1。对于两个类别都需要进行同样的计算处理。最后，对每个元素除以该类别中的总次数。
4.3：测试算法：根据现实情况修改分类器
利用贝叶斯分类器对文档进行分类时，要计算多个概率乘积以获得文档属于某个类别的概率，即计算
如果其中的一个概率值为0，那么最后的乘积也为0。为降低这种影响，可以将所有词的出现数初始化1，并将分母初始化为2.
p0vect.resize(train_mat[0].size(),1);//the frequency of each word in non-absusive docs
p1vect.resize(train_mat[0].size(),1);//the frequency of each word in abusive docs
float p0Denom = 2.0; //the total number of words in non-abusive docs
float p1Denom = 2.0; //the total number of words in abusive docs
下溢出。这是由于太多很小的数相乘造成的。当计算乘积
p(W1|Ci)p(W2|Ci)....p(Wn|Ci)时，由于大部分因子都非常小，所以程序会下溢出或者得到不正确答案。在代数中有ln(a*b) = ln(a) + ln(b)，于是通过对数可以避免下溢出或者浮点数舍入导致的错误。同时，采用自然对数进行处理不会有任何损失。自然ln不会影响函数的单调性。
p0vect[i] = log(p0vect[i]/p0Denom);
p1vect[i] = log(p1vect[i]/p1Denom);
万事俱备，已经可以开始构建完整的分类器了。
4-3：朴素贝叶斯分类函数：
* code list 4-1 : transfer func from docs list to vocabulary list
* code list 4-2 : training func on Naive Bayes Classifier
* add code list 4-3 : naive bayes classify function
#include&iostream&
#include&map&
#include&set&
#include&cmath&
#include&vector&
#include&algorithm&
#include&numeric&
#include&cstring&
#include&stdio.h&
#include&cstdlib&
string posting_list[6][10]={
{&my&,&dog&,&has&,&flea&,&problems&,&help&,&please&,&null&},
{&maybe&,&not&,&take&,&him&,&to&,&dog&,&park&,&stupid&,&null&},
{&my&,&dalmation&,&is&,&so&,&cute&,&I&,&love&,&him&,&null&},
{&stop&,&posting&,&stupid&,&worthless&,&garbage&,&null&},
{&mr&,&licks&,&ate&,&my&,&steak&,&how&,&to&,&stop&,&him&,&null&},
{&quit&,&buying&,&worthless&,&dog&,&food&,&stupid&,&null&}
int class_vec[6] = {0,1,0,1,0,1};
//1 is abusive ,0 not
class NaiveBayes
vector& vector&string& & list_of_
vector&int& list_
map&string,int&
int *return_
vector& vector&int& & train_
vector&float& p0
vector&float& p1
NaiveBayes()
vector&string&
for(int i=0;i&6;i++)
vec.clear();
for(int j=0;posting_list[i][j]!=&null&;j++)
vec.push_back( posting_list[i][j] );
list_of_posts.push_back( vec );
for(int i=0;i&sizeof(class_vec)/sizeof(class_vec[0]);i++)
list_classes.push_back( class_vec[i] );
void create_vocab_list()
vector& vector&string& & :: iterator it = list_of_posts.begin();
int index = 1;
while( it!=list_of_posts.end() )
//vector&string& vec( *it.begin(),*it.end() );
vector&string& vec = *
vector&string& :: iterator tmp_it = vec.begin();
while( tmp_it!=vec.end() )
//cout&&*tmp_it&&& &;
if( my_vocab_list[*tmp_it] == 0 )
my_vocab_list[*tmp_it] = index++; //index is the location of the vovabulary
}//create_vocab_list
//set some one word to vec with 0 and 1.
void set_of_words_to_vec(int idx)
cout&&&set of words to vec begin the document id is : &&&idx&&
int len = my_vocab_list.size()+1;
return_vec = new int[ len ](); //pay attention to the difference between &new int[len]&. initalize all the element to zero.
fill(return_vec,return_vec+len,0);
for(int i=0;i&i++)
cout&&return_vec[i]&&& &;
for( int i=0;posting_list[idx][i]!=&null&;i++ )
//cout&&posting_list[idx][i]&&& &;
int pos = my_vocab_list[ posting_list[idx][i] ];
if( pos != 0 )
return_vec[pos] = 1;
}//set_of_words_to_vec
void get_train_matrix()
cout&&&get train matrix begin : &&&
train_mat.clear();
for(int i=0;i&6;i++)
set_of_words_to_vec(i);
vector&int& vec( return_vec , return_vec + my_vocab_list.size()+1 );
train_mat.push_back(vec);
delete []return_
}//get train matrix
void print()
cout&&&print the train matrix begin : &&&
vector& vector&int& & :: iterator it = train_mat.begin();
while(it!=train_mat.end())
vector&int& vec = *
vector&int& :: iterator itt = vec.begin();
while( itt!=vec.end())
cout&&*itt&&& &;
}//print()
void train_NB0()
int num_train_docs = train_mat.size();//sizeof(posting_lists)/sizeof(posting_lists[0]);
cout&&&num_train_docs = &&&num_train_docs&&
int num_words = train_mat[0].size() - 1 ;
/* calculatr the sum of the abusive classes */
int sum = accumulate(list_classes.begin(),list_classes.end(),0);
cout&&&sum = &&&sum&&
//float p_abusive = (float)sum/(float)num_train_
p_abusive =
(float)sum/(float)num_train_
cout&&&p_abusive = &&&p_abusive&&
//vector&float& p0vect(train_mat[0].size(),1); //the frequency of each word in non-absusive docs
p0vect.resize(train_mat[0].size(),1);
//vector&float& p1vect(train_mat[0].size(),1); //the frequency of each word in abusive docs
p1vect.resize(train_mat[0].size(),1);
printf(&p0num.size() = %d , p1num.size() = %d\n&,p0vect.size(),p1vect.size());
float p0Denom = 2.0; //the total number of words in non-abusive docs
float p1Denom = 2.0; //the total number of words in abusive docs
/* calculate the p0num,p1num,p0Denom,p1Denom */
for(int i=0;i&list_classes.size();i++)
if(list_classes[i] == 1)
//abusive doc
for(int j=0;j&p1vect.size();j++)
p1vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p1Denom++;
//non-abusive doc
for(int j=0;j&p0vect.size();j++)
p0vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p0Denom++;
for(int i=0;i&p1vect.size();i++)
p0vect[i] = log(p0vect[i]/p0Denom);
p1vect[i] = log(p1vect[i]/p1Denom);
cout&&&print the p0vect values : &&&
for(int i=0;i&p0vect.size();i++)
cout&&p0vect[i]&&& &;
cout&&&\nprint the p1vect values : &&&
for(int i=0;i&p1vect.size();i++)
cout&&p1vect[i]&&& &;
int classify_NB( string *doc_to_classify )
return_vec = new int[ my_vocab_list.size()+1 ]();
for(int i=0;doc_to_classify[i]!=&null&;i++)
int pos = my_vocab_list[ doc_to_classify[i] ];
if( pos!=0 )
return_vec[ pos ] = 1;
for(int i=0;i&my_vocab_list.size()+1;i++)
cout&&return_vec[i]&&& &;
float p1 = inner_product( p1vect.begin()+1,p1vect.end(),return_vec+1,0 ) + log(p_abusive);
float p0 = inner_product( p0vect.begin()+1,p0vect.end(),return_vec+1,0 ) + log(1-p_abusive);
cout&&&p1 = &&&p1&&
cout&&&p0 = &&&p0&&
if( p1&p0 )
int main()
nb.create_vocab_list();
//nb.set_of_words_to_vec(5);
nb.get_train_matrix();
nb.print();
nb.train_NB0();
string doc1_to_classify[] = {&love&,&my&,&dalmation&,&null&};
string doc2_to_classify[] = {&stupid&,&garbage&,&null&};
cout&&&doc1 classified as : &&&nb.classify_NB( doc1_to_classify )&&
cout&&&doc2 classified as : &&&nb.classify_NB( doc2_to_classify )&&
可以看到doc1:{&love&,&my&,&dalmation&,&null&};被分为0类（not abusive）; doc2:{&stupid&,&garbage&,&null&}被分为1类（abusive）。分类正确！
五、示例：使用朴素贝叶斯过滤垃圾邮件：
在这个例子中，我们将了解朴素贝叶斯的一个最著名的应用：电子邮件垃圾过滤。首先看一下如何使用通用框架来解决问题：
（1）收集数据：提供文本文件；
（2）准备数据：将文本文件解析成词条向量；
（3）分析数据：检查词条确保解析的正确性；
（4）训练算法：使用我们之前建立的train_NB()函数；
（5）测试算法：使用classifyNB()，并且构建一个新的测试函数来计算文档集的错误率；
（6）使用算法：构建一个完整的程序对一组文档进行分类，将错分的文档输出到屏幕上。
5.1：切分文本：
首先我们将写一个python程序textParse.py来对所有的email文件进行解析，正常的邮件放在/email/ham/下，垃圾邮件放在/email/spam/下，将ham下每个文件解析完成后放在/email/hamParse/下，
将spam下每个文件解析完成后放在/email/spamParse/下，email共享文件链接：/Q4fXnTtGudGA9 。
代码textParse.py：
#!/usr/bin/env python
def textParse(bigString):
listOfTokens = re.split(r'\W*',bigString)
return [tok.lower() for tok in listOfTokens if len(tok) & 2 ]
def spamTest():
for i in range(1,26):
wordList = textParse( open('./email/ham/%d.txt' % i).read() )
fp = open( './email/hamParse/%d.dat' % i , 'w')
for item in wordList:
fp.write(item+' ')
wordList = textParse( open('./email/spam/%d.txt' % i).read() )
fp = open( './email/spamParse/%d.dat' % i , 'w')
for item in wordList:
fp.write(item+' ')
spamTest()
上面的python代码就是读入文本数据，然后切分，得到词向量，然后将词向量中的词都转换成小写，并把长度大于2的提取出来，写入文本文件中去。文本解析是一个相当复杂的过程，可以根据自己的情况自行修改。
5.2：测试算法：使用朴素贝叶斯进行交叉验证
完整代码NB3.cc：
* code list 4-1 : transfer func from docs list to vocabulary list
* code list 4-2 : training func on Naive Bayes Classifier
* code list 4-3 : naive bayes classify function
* add code list 4-4 : naive bayes bag-of-word model
* add code list 4-5 : text parse : textParse.py and spam email test function : get_error_rate()
#include&iostream&
#include&map&
#include&set&
#include&cmath&
#include&vector&
#include&algorithm&
#include&numeric&
#include&cstring&
#include&stdio.h&
#include&cstdlib&
#include&fstream&
#include&stdlib.h&
#include&unistd.h&
#include&string.h&
class NaiveBayes
vector& vector&string& & list_of_
vector&int& list_
map&string,int&
int *return_
vector& vector&int& & train_
vector&float& p0
vector&float& p1
int test_data_
NaiveBayes()
cout&&&please input the num of test data which should be less than 24 : &&&
cin&&test_data_
vector&string&
char buf[3];
string buf_
for(int i=test_data_num+1;i&=25;i++)
sprintf(buf,&%d&,i);
//convert digit to string
vec.clear();
filename = &./email/hamParse/&+buf_str+&.dat&;
//cout&&&filename : &&&filename&&
fin.open( filename.c_str() );
cerr&&&open the file &&&filename&&& error&&&
while(fin&&word)
vec.push_back(word);
list_of_docs.push_back( vec );
list_classes.push_back(0);
filename.clear();
fin.close();
for(int i=test_data_num+1;i&=25;i++)
sprintf(buf,&%d&,i);
vec.clear();
filename = &./email/spamParse/&+buf_str+&.dat&;
//cout&&&filename : &&&filename&&
fin.open( filename.c_str() );
cerr&&&open the file &&&filename&&& error&&&
while(fin&&word)
vec.push_back(word);
list_of_docs.push_back( vec );
list_classes.push_back(1);
filename.clear();
fin.close();
~NaiveBayes()
fin.close();
fout.close();
list_of_docs.clear();
list_classes.clear();
my_vocab_list.clear();
train_mat.clear();
//delete [] return_
p0vect.clear();
p1vect.clear();
void create_vocab_list()
vector& vector&string& & :: iterator it = list_of_docs.begin();
int index = 1;
while( it!=list_of_docs.end() )
//vector&string& vec( *it.begin(),*it.end() );
vector&string& vec = *
vector&string& :: iterator tmp_it = vec.begin();
while( tmp_it!=vec.end() )
//cout&&*tmp_it&&& &;
if( my_vocab_list[*tmp_it] == 0 )
my_vocab_list[*tmp_it] = index++; //index is the location of the vovabulary
}//create_vocab_list
//set some one word to vec with 0 and 1.
void beg_of_words_to_vec(int idx)
//cout&&&set of words to vec begin the document id is : &&&idx&&
int len = my_vocab_list.size()+1;
return_vec = new int[ len ](); //pay attention to the difference between &new int[len]&. initalize all the element to zero.
fill(return_vec,return_vec+len,0);
vector& vector&string& &:: iterator it = list_of_docs.begin() + idx - 1
vector&string& vec
vector&string& :: iterator itt = vec.begin();
int pos = 0 ;
while( itt!=vec.end() )
cout&&*itt&&& &;
pos = my_vocab_list[ *itt ];
if(pos!=0)
return_vec[pos] += 1;
}//beg_of_words_to_vec
void get_train_matrix()
cout&&&get train matrix begin : &&&
train_mat.clear();
for(int i=1;i&=list_of_docs.size();i++)
beg_of_words_to_vec(i);
vector&int& vec( return_vec , return_vec + my_vocab_list.size()+1 );
train_mat.push_back(vec);
delete []return_
}//get train matrix
void print()
cout&&&print the train matrix begin : &&&
vector& vector&int& & :: iterator it = train_mat.begin();
while(it!=train_mat.end())
vector&int& vec = *
vector&int& :: iterator itt = vec.begin();
while( itt!=vec.end())
cout&&*itt&&& &;
}//print()
void train_NB0()
int num_train_docs = train_mat.size();//sizeof(docs_lists)/sizeof(docs_lists[0]);
cout&&&num_train_docs = &&&num_train_docs&&
int num_words = train_mat[0].size() - 1 ;
/* calculatr the sum of the abusive classes */
int sum = accumulate(list_classes.begin(),list_classes.end(),0);
cout&&&sum = &&&sum&&
//float p_abusive = (float)sum/(float)num_train_
p_abusive =
(float)sum/(float)num_train_
cout&&&p_abusive = &&&p_abusive&&
//vector&float& p0vect(train_mat[0].size(),1); //the frequency of each word in non-absusive docs
p0vect.resize(train_mat[0].size(),1);
//vector&float& p1vect(train_mat[0].size(),1); //the frequency of each word in abusive docs
p1vect.resize(train_mat[0].size(),1);
printf(&p0num.size() = %d , p1num.size() = %d\n&,p0vect.size(),p1vect.size());
float p0Denom = 2.0; //the total number of words in non-abusive docs
float p1Denom = 2.0; //the total number of words in abusive docs
/* calculate the p0num,p1num,p0Denom,p1Denom */
for(int i=0;i&list_classes.size();i++)
if(list_classes[i] == 1)
//abusive doc
for(int j=0;j&p1vect.size();j++)
p1vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p1Denom++;
//non-abusive doc
for(int j=0;j&p0vect.size();j++)
p0vect[j] += train_mat[i][j];
if(train_mat[i][j]==1)
p0Denom++;
for(int i=0;i&p1vect.size();i++)
p0vect[i] = log(p0vect[i]/p0Denom);
p1vect[i] = log(p1vect[i]/p1Denom);
int classify_NB(const char
*filename )
return_vec = new int[ my_vocab_list.size()+1 ]();
fin.open(filename);
cerr&&&fail to open the file &&&filename&&
while(fin&&word)
int pos = my_vocab_list[ word ];
if( pos!=0 )
return_vec[ pos ] += 1;
fin.close();
float p1 = inner_product( p1vect.begin()+1,p1vect.end(),return_vec+1,0 ) + log(p_abusive);
float p0 = inner_product( p0vect.begin()+1,p0vect.end(),return_vec+1,0 ) + log(1-p_abusive);
cout&&&p1 = &&&p1&&&
&&&&p0 = &&&p0&&
if( p1&p0 )
void get_error_rate()
char buf[3];
string buf_
int error_count = 0;
for(int i=1;i&=test_data_i++)
sprintf(buf,&%d&,i);
filename = &./email/hamParse/&+buf_str+&.dat&;
if( classify_NB( filename.c_str() ) != 0 )
error_count++;
filename = &./email/spamParse/&+buf_str+&.dat&;
if( classify_NB( filename.c_str() ) != 1 )
error_count++;
cout&&&the error rate is : &&&(float)error_count/(float)(2*test_data_num)&&
int main()
nb.create_vocab_list();
//nb.beg_of_words_to_vec(5);
//nb.beg_of_words_to_vec(30);
nb.get_train_matrix();
//nb.print();
nb.train_NB0();
doc1_to_classify[] = &./email/hamParse/1.dat&;
doc2_to_classify[] = &./email/spamParse/1.dat&;
cout&&&doc1 classified as : &&&nb.classify_NB( doc1_to_classify )&&
cout&&&doc2 classified as : &&&nb.classify_NB( doc2_to_classify )&&
nb.get_error_rate();
makefile：
./textParse.py
g++ NB3.cc
rm ./email/spamParse/*
./email/hamParse/*
代码中增加了get_error_rate()函数测试分类函数的错误率。email中ham和spam下分别有25个文本文件，我们定义了成员变量test_data_num，那么我们就将ham/spam下第1~test_data_num的邮件当做
，第test_data_num+1~25的邮件当做
。这种随机选择数据的一部分作为训练集，而剩余部分作为测试集的过程称为
留存交叉验证
。那么在构造函数中就将第test_data_num+1~25的数据来初始化list_of_doc，进一步通过create_vocab_list()和get_train_matrix()得到train_mat，再通过训练函数train_NB0()得到p0vect和p1vect，通过classify_NB()对文本进行分类，get_error_rate()测试分类函数的错误率。
下面展示一个在test_data_num = 7情况下的结果：
错误率在7%左右。经过测试随着test_data_num的增加错误率会减小，知道test_data_num=12的时候降为4%。之后又会随着test_data_num的增加而上升。
如果还有问题可以留言进行交流，谢谢！
已发表评论数()
&&登&&&陆&&
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见