朴素贝叶斯分类-盘古文库

朴素贝叶斯分类

来源：火烈鸟

作者：开心麻花

2025-09-19

朴素贝叶斯分类（精选7篇）

朴素贝叶斯分类第1篇

对称性使人们在观察自然和认识自然过程中产生的一种观念, 自然界千变万化的运动, 从一个侧面来说, 往往显示出各式各样的对称样, 同时又通过这些对称性的演化和残缺来反映出运动演化的特点。对称性的描述定义有很多种, 从物理学出发, 对称性可以概括为:如果某一现象 (或系统) 在某一变换下不改变, 则说该现象 (或系统) 具有该变换所对应的对称性。

每一种对称性都和某种特定的变换相联系, 对称性的千差万别也就集中在与之相联系的各种变换上, 因此可以根据变换所涉及的对象以及变换的性质对对称性进行研究与分类。对于对称性的描述与研究最有效的数学工具是群论与群表示论。物理学中对称性研究相当多的部分运用群论来分析, 概括和研究物理学的规律。例如, 晶体中的对称性, 根据对称性的结构对晶体进行分类, 以及利用群论结果确定晶体中电子的波函数。另外一方面, 根据群论的抽象机制对宇宙中粒子的运动行为作出预测。

统计学家运用对称性对数据进行分析, 并且专门开发了一个研究方向:数据分析的对称性研究。对称性研究主要运用统计与代数分析复杂的结构性数据, 例如DNA分子结构, Sloan字体等具有对称性的数据。这些数据 (x) 由一个有限集合V作为索引或者标注, 有限集合V具有可以有群刻画的对称性, 或者V可以构成一个群。简而言之, 对称性研究利用具有对称性的数据索引方便的对数据{x (s) , s∈V}进行分类, 解释, 统计性分析。目前对称性研究主要用于短核苷酸序列索引的数据分析, 由Sloan字体的对称性索引的对比敏感度与熵的分析, 地质成分熵的分解, 初等平面图像对称索引的数据的分类与统计分析等。

既然物理学家与统计学家能够运用群论认识自然界数据的规律, 那么我们从数据分析的角度看, 利用数据中的对称性, 结合机器学习方法, 对数据进行分析, 其目的就是揭示这些数据具有的规律, 从而帮助用户提供解释的依据。对于具有复杂结构的某些数据, 我们采用李群, 李群结构是对学习问题很有用的一套理论工具, 李群之所以受人们关注, 一方面是李群有好的数学结构, 另一方面受到物理学家和化学家广泛使用李群方法来处理物理学中的晶体数据、有机物和无机物的数据、药物分子结构数据等这些复杂数据的启发。如何把李群运用到机器学习中, 以下文献提供了一个参考作用。

对于构成李群的数据, 我们采用李群学习范式分析数据的维数, 紧致性, 连通性, 子群, 陪集。但仍有一个问题必须解决:如何确保计算复杂度问题。李群存在着复杂的代数结构, 代数结构对于数据的分析有着至关重要的作用, 但与统计对比, 机器学习的代数方面的研究涉及的很少, 只保留在理论层面上, 原因之一是由于对象的巨大数量, 很难计算。

2 基于群的朴素贝叶斯学习基本框架

设想学习问题定义如下, 学习器L工作在实例空间X和假设空间H上, H上假设X上定义的某种实数值函数 (即H中每一个h为一函数:h, XR其中R代表实数集) , L面临的问题从H中抽取的目标函数h。如果实例空间X是一个可以用群G刻画的对称空间, 或者实例X是一个群, 则可以利用群作用于实例空间, 产生实例空间X的商空间X/G, 则假设空间H的h变换为h:X/GR。本文学习算法的基本框架见图2.1。

一般来说, 给定的样本数据具有隐藏的对称性, 无法直接作为实例空间X, 如DNA分子序列, 实例空间X的每个实例都相当于该样本数据提取的一个特征, 所以构造一个有序的实例空间 (特征空间) , 能够极大程度的反映不同DNA分子的差异。

2.1 构造实例空间X:

由于我们的算法主要针对分子序列分类, 所以直接从样本数据出发。

任何一个长度为的分子序列可以有一个函数s:PA表示, 其中P={1, 2, , }是字母表A的每个字母所处的有序位置的集合。典型的字母表比如:DNA分子序列的字母:A={A, G, T, C}, RNA分子的字母表:A={A, G, T, U}, 或者简单的二元字母表A={U, Y}, 嘌呤 (U=A或者U=G) 与嘧啶 (Y=C或者Y=T) 。Doi (1991) 提出有效的局部序列长度为2, 3, 4, 5, 6。│A│表示字母表中字母的个数。X表示长度为L的所有│A│-序列构成的空间。实例空间X有│A│个实例。

2.2 构造X的商空间

已知实例空间X具有│A│个实例 (特征) , 当较大时, 则会出维数灾难问题, 为了解决这个问题, 可以根据实例空间X的规律, 构造感兴趣的群对X进行划分, 不同的群将会对实例空间X产生不同的划分, 要结合具体问题构造不同的群。例如对于DNA分子序列构造的实例空间, 我们感兴趣的是序列中符号的构成关系, 所以一般选择n阶置换群Sn (n=2, 3, 4) 。

定义: (群作用) 群在一个集合V的作用是一个映射:φ:GVV, 且φ满足以下条件:对所有的s∈V, φ (1, s) =s, 对于所有的τ, δ∈G, s∈V, φ (σ, φ (τ, s) ) =φ (δτ, s) 。

根据φ, 对于s∈X, 群G作用在实例空间上产生的轨道为o={φτ (s) ;τ∈G}, 轨道空间中的任两个实例都是等价的, 在某一个群G作用下, X的所有轨道集合构成了一个X的另一个空间:商空间X/G, 即X=o1∪o2∪∪oλ, λ表示轨道的个数, oi (i=1, , λ) 表示第i个轨道空间, 则每一个轨道空间的实例 (特征) 都是等价的。如何确定轨道的个数λ, 我们引用Burnside引理:

Burns ide引理:若一个有限群作用实例空间X上, 则X中轨道的个数:

其中fix (τ) ={s∈X;φτ (s) =s}, 表示具有对称性τ的X中实例集合, │fix (τ) │表示具有对称性τ的X中实例的个数, │G│表示群G中元素的个数。

由于轨道oi的每个实例 (特征) 都是等价的, 则每个轨道就可以作为DNA分子序列的一个特征 (属性) , 使用字母ai表示。X的商空间的维数为λ, DNA分子序列的属性为 (a1, a2, , aλ) 。

2.3 构造假设空间H

由于H中的假设为X上定义的某种实数值函数h, 学习器L学习的空间X已经变成商空间X/G, 则h变化为:h:X/GR;X商空间的每个轨道oi作为一个函数h的一个变量xi (i=1, 2, , λ) , H的变量数为λ。由于我们采用群的划分方法, 轨道之间相互独立, 则变量之间相互独立。假设每个变量xi服从均值为μi, 方差为δi的高斯分布, 空间的H的个假设h的表达式为:

本文采用一般的统计学方法计算每个变量xi的均值μi与δi值, 举一个简单的例子说明:对于每个核苷酸, 统计每个实例空间中每个实例在DNA分子中出现的频数, 比如, 已知DNA分子序列,

则每个实例的频数为

构造的实例空间X为:X={s:QA}, 其中Q={1, 2, 3}, A={a, g, c, t}, 构造的实例空间共有64个实例, 构造的群为S3={1, (12) , (13) , (23) , (123) , (132) }, 则由Burnside引理计算出λ=35, 轨道划分如下:同一个轨道内的实例的频数相加。则可以计算出变量xi (i=1, 2, , λ) 的样本值, 然后使用统计的方法估计出每个变量的均值与方差。

2.4 朴素贝叶斯分类

朴素贝叶斯分类器应用到学习任务中, 每个样本数据由属性值的合取描述, 而目标函数h从商空间X/G中取值, 学习器L被提供一系列关于目标函数的训练样例以及新实例 (描述为属性值的元组) , 然后对新实例分类。贝叶斯方法的分类目标在给定描述实例 (DNA分子序列) 的属性值, 得到做可能的目标值hMAP。

使用贝叶斯公式重写为:

朴素贝叶斯分类器基于一个简单的假设:在跟定目标值时属性值之间相互条件独立。换言之, 该假定在给定实例的目标值情况下, 观察到联合的a1, a2, , aλ的概率等于每个单独属性的概率乘机:

将其代入式 (2.2) , 可以得到朴素贝叶斯所使用的方法:

其中hNB表示朴素贝叶斯分类器输出的目标值。

将2.1式代入式2.4得到:

基于群的朴素贝叶斯算法如下:

Exam ple s是不同的DNA分子序列的集合以及类别名。H是所有可能假设的集合此函数作用提取DNA分子的属性, 构造假设空间H, 计算属性分布的高斯参数。变量n表示每种类别的DNA分子序列。

1.依据Exam le s构造实例空间X= (w1, w2, , wn) ;

2.构造群G

3. 计算假设空间H的每个hj的每个变量xi的均值ui, 方差δi

对于H中每个假设hj:

对于类别为hj的每个example:

统计实例空间X每个实例wi的频数;

根据群G与wi计算轨道数λ;

划分实例空间X=o1∪o2∪∪oλ;

计算每个轨道oi的频数;

变量xi=oi (i=1, 2, , λ) ;

计算假设hj的每个变量的均值ui, 方差δi

对于DNA分子, 返回其估计的类别。

计算变量xi的值;

朴素贝叶斯分类第2篇

关键词：朴素贝叶斯,维规约,条件信息熵,主成分分析,独立成分分析

0 引言

在众多分类方法和理论中, 朴素贝叶斯NB (Naïve Bayes) 由于计算高效、精度高和具有坚实的理论基础而得到了广泛应用[1]。它基于一个简单的假定:在给定分类特征条件下属性之间相互独立。在现实世界中, 这种独立性假设经常是不满足的。因此, 许多学者研究学习贝叶斯网络 (Bayes Network) 来改进其分类性能, 然而要学习得到一个最优贝叶斯网络是个NP-hard问题[2]。如何能既保持朴素贝叶斯计算的简单性, 又可以提高其分类性能, 成为改进朴素贝叶斯学习的重要研究方向。

高维度数据中的信息往往主要包含在一个或几个低维结构中[3], 因此维规约技术是处理高维数据的一个重要手段。其形式分为属性选择和维变换[4]两种。对于属性选择, 文献[5]提出了基于条件信息熵的选择朴素贝叶斯算法。对于维变换, 主要有主成分分析 (PCA) 和独立成分分析 (ICA) 方法[6]。显然, 并不是这些方法对任何数据集 (或实际问题) 都有很好的效果。本文从避免 (或减弱) 朴素贝叶斯条件独立性假设出发, 从维规约的两个方向, 分别就基于条件信息熵的选择朴素贝叶斯 (CIESNB) 、基于主成分分析的朴素贝叶斯 (PCANB) 和基于独立成分分析的朴素贝叶斯 (ICANB) 的维规约效果和分类性能进行了研究。并通过在UCI数据集上的仿真实验, 详尽地分析、比较了几种维规约方法的降维效果和对朴素贝叶斯分类性能的影响。以利于根据数据本身特点, 采用不同的维规约方法提高朴素贝叶斯的分类性能。

1 朴素贝叶斯的相关模型

1.1 朴素贝叶斯模型

贝叶斯分类是基于贝叶斯公式, 即:

$Ρ (C | X) = \frac{Ρ (X | C) Ρ (C)}{Ρ (X)}$

其中, P (C|X) 为条件X下C的后验概率, P (C) 为C的先验概率, P (X|C) 为条件C下X的后验概率, P (X) 表示X的先验概率。

为叙述方便, 对符号作如下约定:用大写字母表示变量, C表示类别变量, A表示属性变量, 假定共有m个属性变量, A=<A1, A2, , Am>;用小写字母表示变量取值, Val (C) ={c1, c2, , cl}, Val (A) ={ai1, ai2, , aik}分别表示类别变量和属性变量的值域;用X表示待分类样本集, x=<a1, a2, , am>表示待分类样本;用T表示训练样本集, ti=<a1, a2, , am, cl>表示训练实例。在朴素贝叶斯中假设各属性相对于类别条件独立, 则有:

P (x $c_{l}) = \prod_{i = 1}^{m} Ρ (a_{i}$ cl) (1)

在实践中, 由于经常会对数值型变量进行分析, 则假设在m维空间中, ai对于x的似然函数呈多元正态分布, 则[7]:

P (x $c_{l}) = \frac{\exp (- \frac{1}{2} (x - μ_{l})^{Τ} \sum_{l}^{- 1} (x - μ_{l}))}{(2 π)^{m / 2} | \sum_{l} |^{1 / 2}} (2)$

其中, μl=E[x]是cl类的均值, ∑l是mm维协方差矩阵, 定义为∑l=E[ (x-μl) (x-μl) T]。

根据后验概率公式, 测试样本E被分在后验概率最大的类中, 则朴素贝叶斯分类模型为[1]:

$V_{n b} (E) = \underset{c}{\arg} \max Ρ (c) \prod_{i = 1}^{m} Ρ (a_{i}$ c) (3)

1.2 基于维规约的朴素贝叶斯模型

对高维度数据, 维度之间的条件独立性假设往往不成立, 同时由于维度高会给分类带来很大困难。然而, 高维度数据中的信息往往主要包括在一个或几个低维结构中[3], 因此从高维数据中提取有效信息的维规约技术是处理高维数据的一个重要手段。维规约技术, 从数学角度讲就是对于给定m维的数据向量x={x1, x2, , xm}, 在某种条件下, 寻找一个能反映原始数据信息的较低维的表示, 即s={s1, s2, , sp}, 使得pm (理想情况p<<m) , s的向量有时又被称为潜隐向量。基于维规约的朴素贝叶斯模型就是先对高维数据进行维规约, 再进行朴素贝叶斯分类, 其问题的关键就在于选择合适的维规约算法。

2 维规约算法

2.1 基于条件信息熵的属性选择算法

选择朴素贝叶斯的关键就在于如何选择属性, 即如何进行属性约简。文献[5]中提出了一种基于条件信息熵的决策表约简算法, 核心思想是根据决策表决策属性相对于条件属性的条件熵的确定性 (不变性) 进行约简。先求决策表的属性核, 而后根据其他条件属性相对于决策属性的条件熵从小到大逐个加入, 直到所选条件属性集相对于决策属性的条件熵与所有条件属性对决策属性的条件熵相等为止。

2.2 基于主成分分析的维变换算法

因此, 基于主成分分析方法是对原始数据进行预处理, 可以从原始观测数据的m元数据中抽取出互不相关的p元特征, 即原始数据的主成分[7]。具体步骤如下:

Step1 原始数据的标准化处理, 使每个属性均值为0, 方差为1;

Step2 计算Step1中得到的数据集X的相关系数矩阵R;

Step3 计算R的特征值λi及其对应的特征向量μi, i=1, 2, , m, 并将特征值按由大到小的顺序排列, 即λ1>λ2>>λm;

Step4 计算主成分的方差贡献率和累计方差贡献率, 主成分p值的选取一般为累计方差贡献率>85%的前p个特征值;

Step5 利用前p个特征值对应的特征向量u1= (u11, u12, , u1m) T, u2= (u21, u22, , u2m) T, , up= (up1, up2, , upm) T, 按Y=UX计算原始数据的主成分y1, y2, , yp。

2.3 基于独立成分分析的维变换算法

ICA最早是由文献[8]提出, 其目的是为非高斯分布数据找到一种线性变换, 使成分之间尽可能统计独立。统计上相互独立是一种比不相关更强的条件。独立肯定意味着不相关, 但反之不然。只有当f (x1, x2, , xm) 服从高阶正态分布, 两者才等价。对于高斯分布主成分分析就是独立成分分析。

ICA的一般线性模型 (不考虑噪声) 为X=AS, 其中X=[x1, x2, , xm]T为观测信号, S=[s1, s2, , sm]T为独立的源信号且各分量服从非高斯分布, A是nm混合矩阵。ICA的目的就是在仅知道X的情况下, 寻找nm混合矩阵A或mn解混矩阵 (又称为分离矩阵) W, 使Y=WX, 其中Y= (y1, y2, , ym) T且Y的各分量尽可能相互独立, 而Y逼近S, 从而得到源信号[8]。

问题的关键是如何度量分离结果的独立性, 鉴于ICA理论的基本出发点, 信号的独立性度量是通过它的非高斯性度量来实现的, 本文采用其中的负熵度量准则。我们采用一种快速ICA算法FastICA[9]对训练样本集进行独立分量提取。具体算法参见文献[9]。

3 仿真实验

为了对比分析前述几种维规约算法对朴素贝叶斯分类性能的影响, 选用了UCI机器学习数据库 (http://www.ics.uci.edu/～mlearn/MLRepository) 中的14个数据集作为测试数据, 这些数据集的基本信息如表1所示。

测试步骤:

Step1 对数据的预处理: (1) 用重庆邮电大学计算科学技术研究所研发的“基于Rough Set 的智能数据分析系统 (RIDAS) ”对数据集进行预处理 (用“条件组合补齐算法”进行补齐, 对基于条件信息熵的属性选择算法中用“基于属性重要性”的方法进行离散化, 其它两种算法无需离散化) ; (2) 如果某个属性的取值个数与样本数相等时, 它对分类的作用很小, 于是先将这样的属性去掉。

Step2 为了研究属性间相关系数的大小对维规约及分类性能的影响, 计算属性间的绝对平均相关系数 $| \bar{R} |$ 。

Step3 维规约:分别按第2节介绍的算法进行维规约, 其维规约后的属性数见表2。

Step4 将约规约后的数据集采用5重交叉验证 (5-fold cross-validation) 测试方法, 取5次测试精度的平均值作为这个数据集的测试结果, 详见表2。

注:1) NB, CIESNB, PCANB, ICANB分别表示朴素贝叶斯、基于条件信息熵的选择朴素贝叶斯、基于主成分分析和独立成分分析的朴素贝叶斯方法; $2) | \bar{R} |$ 表示属性间的绝对平均Pearson相关系数。

对几种算法的维规约效果和分类精度进行比较, 结果如表3、表4和图1所示。在表3和表4中w-t-l分别表示当前行所在方法比当前列所在方法性能优、相当和劣的数据集个数, 如表上中的“11-3-0”表示CIESNB算法比NB算法在11个数据集上能简化属性个数, 3个数据集上与NB算法相当的属性数目, 比NB属性数多的为0个数据集。

通过对几种算法测试结果的比较分析, 可以得出以下结论:

(1) CIESNB、PCANB和ICANB均能较大程度降低决策表中条件属性数的同时, 提高其分类精度;

(2) 在降维效果上, 基于主成分分析方法的作用最明显, 平均维数只占原来维数的37.5%, 独立成分分析方法其次;

(3) 在分类精度上, ICANB比PCANB和CIESNB方法都高, 其次是PCANB;

(4) 属性间相关性的大小对PCANB和ICANB分类性能影响较大, 当相关系数较大时, PCANB和ICANB改善分析性能的效果较显著;

(5) 在处理具有连续值属性时, 由于CIESNB需先对属性进行离散化, 这会导致部分信息的丢失, 反而会影响其分类性能。

4 结论及展望

本文从三种主要的维规约方法入手, 对基于条件信息熵的属性选择算法、基于主成分分析的维规约算法和基于独立成分分析的维规约算法对朴素贝叶斯分类性能的影响作了研究。并以UCI中的14个数据集为测试数据, 通过实验比较了几种维规约算法对朴素贝叶斯分类的降维效果和分类精度的影响。实验表明:几种方法均能在较大程度降低属性维数的同时提高其分类精度;在降维效果上主成分分析方法最明显, 在分类精度上独立成分分析方法最优。本文的另一重大发现是属性间相关性大小对基于主成分和独立成分算法的降维和分类性能有较大影响, 相关性越大效果越显著。最后, 在处理具有连续属性的数据集时, 如果对其进行离散化, 可能会导致部分信息丢失, 反而影响其分类性能。

由于改进朴素贝叶斯模型还很多, 如树增强型朴素贝叶斯、加权朴素贝叶斯等, 本文只研究了降维对贝朴素贝叶斯的影响, 是否可在降维的基础上再应用到其它改进模型上;此外, 由于本文所选用的数据集只有14个, 在其它数据集上的性能如何还需进一步研究;最后, 如何根据实际问题数据集的自身特点选择合适的维规约算法也是我们下一步努力的方向。

参考文献

[1]史忠植.知识发现[M].北京:清华大学出版社, 2002:169-220.

[2]Chickering D M.Learning Bayesian networks is NP-complete[M].NewYork:Springer.1996:121-130.

[3]李国英.关于高维、相依的不完全数据的统计分析[J].数学进展, 2002, 31 (3) :193-199.

[4]Ye J P, Li Q, Xiong H, et al.IDR/QR:An Incremental Dimension Re-duction Algorithm via QR Decomposition[J].IEEE Transactions onKnowledge and Data Engineering, 2005, 17 (9) :1208-1222.

[5]邓维斌, 黄蜀江, 周玉敏.基于条件信息熵的自主式朴素贝叶斯分类算法[J].计算机应用, 2007, 26 (4) :888-891.

[6]Bura E.Dimension Reduction Techniques:ARewies[EB/OL].2006.ht-tp://srccs.snu.ac.kr/Work-shop/04Statistics/7.pdf.

[7]Sergios Theodoridis, Konstantinos Koutroumbas.模式识别[M].3版.北京:电子工业出版社, 2006:7-44.

[8]Jutten C, Herault J.Independent component analysis versus PCA[C]//Proc of European Symposium on Signal Processing.1988:287-314.

朴素贝叶斯在文本分类中的应用第3篇

文本分类是指在给定分类体系下, 根据文本内容确定文本类别的过程。目前, 文本分类的研究工作主要是研究如何运用统计学和机器学习的方法利用计算机对文本进行自动分类。文本分类是一个有指导的学习过程, 它根据一个已经被标注的训练文本集合, 找到文本属性 (特征) 和文本类别之间的关系模型 (分类器) , 然后利用这种学习得到的关系模型对新的文本进行类别判定。文本分类一般包括两个步骤:第一步, 通过样本训练, 利用样本和类别之间的联系, 建立一个样本分类函数;第二步, 通过样本分类函数, 对新文本进行分类。

贝叶斯理论被用于机器学习中, 是一种基于统计的机器学习技术, 由于其简单高效, 在很多领域都有广泛运用。在文本分类中, 根据贝叶斯公式, 分别计算文本属于不同类别的概率, 将文本归类于概率值最大的那一个类别。

1 贝叶斯理论

贝叶斯定理设样本空间为S, A为一个事件, B1, B2, , Bn为S的一个划分, 且P (A) >0, P (Bi) >0 (I=1, 2, , n) , 则

P (Bi) 是先验概率, P (Bi|A) 是后验概率, 是在事件A发生情况下Bi的概率, 公式 (1) 是贝叶分类算法的数学基础。贝叶斯分类就是利用已经观察到的样本信息, 根据贝叶斯公式来计算后验概率, 并以计算结果作为选择依据把样本归属到某个类别。

2 朴素贝叶斯文本分类器

构成文本的有意义的单元是词语, 文本的类别和文本出现的词语是有关联性的。假定文本可以用一组能表示文本类别的特征词来表示, 可以把这组特征词定义成文本的特征向量T (t1, t2, , tn) 。假设训练样本集中有m个不同的类别, C1, C2, , Cm, 要确定特征向量T属于哪个类别, 只需要计算每个类别的条件概率P (Ci|T) , 选取概率值最大的类别作为文本的类别。根据贝叶斯定理可得文本分类函数:

由全概率公式可知, 公式 (2) 可以写成:

朴素贝叶斯理论有一个重大假设, 即向量T是独立不相关的, 因此:

对于任意类别Ci的条件概率P (Ci|T) 都有相同的因子P (T) , 而确定文本类别的过程中关心的是P (Ci|T) 中哪个值最大, 而并不关心其具体值。为简化计算, 公式 (3) 可以写成:

公式 (5) 就是文本分类函数, 在分类函数中要先训练样本, 根据训练结果估算P (Ci) 和P (tj|Ci) 。朴素贝叶斯分类算法有两种模型:一种是贝努力事件模型, 一种是多变量事件模型。两种模型对P (Ci) 和P (tj|Ci) 估算方式不一样, 本文采用贝努力事件模型。

从公式 (5) 中可见, 贝叶斯分类中所有的特征词都对分类有贡献作用, 并不是一个或几个特征词决定分类, 因此特征词选取关系到分类准确性。术语停用词专指那些从文本分割出来的对分类不起作用的词语。对于停用词必须剔除掉, 一方面可以减少对分类的干扰, 另一方面可以降低特征向量的维数以减少计算量。

2.1 样本训练

分析训练集, 统计类别个数、类别名称等信息。利用分词工具将训练集S中每一篇样本切割成词语串, 去掉无意义的停用词, 形成文本的特征向量Ti (ti1, ti2, , tin) 。统计每个类别Ci中出现的特征词t以及t出现的次数;统计每个类别Ci的样本数量ni和训练集S中的样本总量N;统计每个类别Ci的特征词总数。样本训练的算法步骤如下:

S1:分析训练集, 统计类别信息;

S2:进入子类别;

S3:统计子类中的样本数量;

S4:读取样本, 文本切分, 形成特征向量;

S5:分析特征向量, 记录特征词t, 更新特征词t出现的次数, 记录样本特征词数量;

S6:重复S4, 对子类中所有的样本遍历一次, 统计子类中的特征词总量;

S7:重复S2, 对训练集中所有子类遍历一次, 统计训练集合中的样本总量。

2.2 分类计算

首先对测试文本进行文本切分, 去掉那些对文本归类不起作用的停用词, 形成文本的特征向量T (t1, t2, , tn) , 利用样本训练的结果, 对每个类别Ci计算条件概率P (Ci|T) 。

在计算条件概率P (Ci|T) 过程中需要计算类别Ci的先验概率P (Ci) , 利用公式 (6) 计算先验概率P (Ci) 。

其中, Ci表示类别i, ni表示类别Ci中的样本数量, N表示训练集中的样本总数。

对于每个特征词tj, 需要计算在类别Ci的条件概率P (tj|Ci) , 利用公式 (7) 可以计算条件概率P (tj|Ci) 。

其中, nji表示类别Ci中含特征词tj的样本数量, ni表示类别Ci中的单词数量, r为常量。

根据公式 (6) 、 (7) 的计算结果, 利用公式 (5) 计算出测试文本的特征向量T (ti, ti, , ti) 在每个类别Ci的条件概率P (Ci|T) , 比较每个类别的概率值, 取概率值最大的那一个类别作为测试文档归属的类别。算法步骤如下:

S1:分割测试文本, 形成特征向量T;

S2:计算类别Ci的先验概率P (Ci) ;

S3:计算特征词tj的条件概率P (tj|Ci) ;

S4:重复S3, 直至所有的特征词计算完毕;

S5:利用公式 (5) 计算出条件概率P (Ci|T) , 保存计算值;

S6:重复S2, 直至所有的类别都被计算一次;

S7:利用S5的计算值, 选择概率值最大的类别作为文档的类别。

2.3 具体实现

以Java作为开发语言实现了一个朴素贝叶斯文本分类器, 文本分类器由两个模块组成, 为训练模块和分类计算模块。图1是文本分类器的结构示意图。

样本训练模块完成对样本集的训练, 模块的输入是训练样本集, 模块的输出是训练结果, 作为分类计算模块的输入数据。在样本训练模块中, 设计了TrainedResult类作为保存训练结果的数据结构。在训练过程中需要对文本切分, 形成特征向量, 为此设计了DocmentSeperator类和StopWordsHandler类。每个类的功能如下:

StopWordsHandler类。停用词处理类, 剔除对分类不起作用的停用词。停用词包括单个汉字, 单个汉字容易被识别剔除掉, 对于词语只能编制停用词表, 通过词表判断是否属于停用词语。

DocmentSeperator类。文本切分类, 完成文本切分, 形成词语串。在这个类中使用了第三方的分词工具, 即中科院的汉语分词开源系统ICTCLAS。

TrainedResult类。训练结果类, 用于保存训练的结果。需要保存的样本信息包括每个类别C中出现的特征词t以及t出现的次数、每个类别C的样本数量、训练集S中的样本总量、每个类别C的特征词总数。

Trainer类。样本训练类, 完成对样本集的分析, 统计样本类别、样本数量。通过调用TrainedResult类和StopWordsHandler类提供的功能, 生成样本的特征向量, 分析特征向量, 统计特征词和特征词出现的次数, 形成训练结果。

分类计算模块完成对测试文本的分类计算, 模块的输入是测试文本和训练结果, 输出是类别的后验概率。分类计算模块只设计了ClassCalculate类, 该类对外提供类别Ci的后验概率P (Ci|T) 。内部实现包括计算类别Ci的先验概率、特征词tj的后验概率P (tj|Ci) , 并利用公式 (5) 计算P (Ci|T) 。

在分类计算模块中可以对测试文本的后验概率的计算做一定优化, 对于分类贡献大的特征词提高其权重。TF-IDF (term frequency-inverse document frequency) 是一种常用的加权技术, 其思想是:特征词在某一特定文件内是高频词, 而在整个文件集合中是低频词, 这个特征词对分类贡献大, 应该取得大的权重。TF-IDF倾向于过滤掉常见词语, 保留重要词语。文档频率TF (term frequency) 是指在某篇文档中, 某特征词出现的频率, 特征词t在TF中的计算公式TFt=|Dit|/|Di|, 其中|Dit|表示特征词t在文档Di出现的次数, |Di|表示文档Di中出现的词语总数。逆文档频率IDF (inverse document frequency) 是用来度量特征词的普遍重要性, 特征词t的IDF计算公式IDFt=log ( (|D|) /1+|Dt|) , 其中|D|表示文档总数, |Dt|表示包含特征词t的文档数量。TF-IDF表示TFt和IDFt的乘积, 能够体现特征词t对文本分类的贡献, 可以提高分类的性能。在实现过程引入了TF-IDF作为权重, 对公式 (5) 作了修正。

文本分类器由NaiveBayesClassifier类实现, 完成样本集的训练和测试文本的分类计算, 数据的输入是训练样本集和测试集。

3 试验结果

试验语料采用搜狗实验室免费共享的语料库, 语料库中的文档分为9个类别, 共计17 910篇文档, 从每个类别中抽取一部分作为训练样本, 余下的作为测试样本。试验测试数据显示, 平均分类正确率到达74.2%以上。在分类器的实现中还可以作进一步的改进, 为了节省训练时间, 训练模块可以把训练结果用中间文件保存起来, 在训练之前对中间文件做一个判断, 如果存在中间文件, 直接加载中间文件, 否则按提供的样本集训练。

4 结语

用朴素贝叶斯进行文本分类有较好的分类效果, 但这种文本分类方法还有很大的改进余地, 可以进一步提高分类的效率和精度。分类函数要能体现每个特征词对分类的贡献程度, 形成非线性的加权公式。特征词提取要尽可能去掉对分类无意义的词语, 降低特征向量的维度。朴素贝叶斯理论假设特征词是相互独立的, 即一个词语的出现与其它词语的出现无关, 这在实际情况中往往不成立。

摘要：朴素贝叶斯理论是一种典型机器学习技术, 能够应用于文本分类中。运用朴素贝叶斯理论阐述了贝叶斯分类器的样本训练和分类计算的过程, 构造了一个文本分类器。试验表明, 朴素贝叶斯理论在文本分类中有较好的分类效果。

关键词：中文信息处理,文本分类,机器学习,朴素贝叶斯

参考文献

[1]张征杰, 王自强.文本分类及算法综述[J].电脑知识与技术, 2012, (4) .

[2]刘颖.贝叶斯方法在文本分类预处理中的应用[J].电脑与信息技术, 2010 (6) .

[3]杨凯峰, 张毅坤, 李燕.基于文档频率的特征选择方法[J].计算工程, 2010 (17) .

[4]搜狗实验室语料库[DB/OL].http://www.sogou.com/labs/dl/c.html.

[5]陈叶旺, 余金山.一种改进的朴素贝叶斯文本分类方法[J].华侨大学学报:自然科学版, 2011 (4) .

朴素贝叶斯分类第4篇

文本分类技术是信息检索与数据挖掘领域的核心技术，主要的算法包括朴素贝叶斯、K最近邻、神经网络和支持向量机等[1]。其中朴素贝叶斯算法在进行文本分类时，假定特征独立于类别，简化了训练和分类过程的计算，具有运行快速、易于实现的特点，因此成为文本分类中广为使用的一种方法，吸引了众多学者的关注。文献[2]提出了一种基于期望最大化（EM）的朴素贝叶斯文本分类算法，提高了对未标注语料的利用率。文献[3]提出了一种基于局部加权的朴素贝叶斯文本分类算法，弱化了特征项间独立性假设。文献[4]将支持朴素贝叶斯文本分类算法同支持向量机算法相结合，提高了分类的准确率。文献[5]提出了一种基于辅助特征词的朴素贝叶斯文本分类算法，提高了类条件概率的精确度。文献[6]提出了一种对特征词权重进行高阶投票的方法，改善了当训练语料不足时分类器的性能。但是，以上研究存在一定的局限性。一方面，在单机上运行的传统朴素贝叶斯文本分类算法，由于其自身扩展性和计算能力的限制，在当前大数据[7]环境下，难以保证数据处理的高效性；另一方面，在文本分类过程中，语言中的大部分词都属于低频词，难以有一个足够大的训练语料能够包含所有的词语，因而会造成数据稀疏问题。对于该问题，很少有学者进行研究。

因此，针对数据稀疏问题，本文借鉴统计语言建模技术[8]中的数据平滑方法，提出一种Dirichlet朴素贝叶斯文本分类算法，同时采用MapReduce编程模型[9]，在Hadoop[10]云计算平台上实现该算法的并行化。

1 算法的原理及改进

1.1 朴素贝叶斯文本分类算法

朴素贝叶斯文本分类算法NB(Naive Bayes）是一种基于概率统计的学习方法。常用的模型包括多变量贝努利模型和多项式模型，二者的计算粒度不一样，伯努利模型以文件为粒度，多项式模型以单词为粒度。本文采用多项式模型[11]。假设文档d可由其所包含的特征词表示，即d=(w1,w2,⋯,w|v|)，wk为特征词，k=1,2,⋯,|v|，v是特征词的集合，|v|为特征词的个数。同时，目标类别集合数目确定，c={c1,c2,⋯,cm}，ci是类标签，i=1,2,⋯,m。由贝叶斯公式可计算文档d属于类别ci的概率为：

因式（1）中分母与类别无关，可将此表达式重写：

式（2）中的类先验概率p(ci)和类条件概率p(d|ci)通过从训练集中学习得到，通常取它们的最大似然估计作为它们的估计值。

类先验概率p(ci)可以由下式估计：

式中：Ni为类ci中的特征词总数；N为训练集的特征词总数。

由于文档d可由其所包含的特征词表示，可将类条件概率p(d|ci)重写如下：

朴素贝叶斯假设特征词wi和wj之间对类别的影响相互独立，根据概率的乘法定理，可将式（4）重写为：

将式（5）代入式（2），得到表达式如下：

在式（5）中，基于朴素贝叶斯独立性假设，将文档的类条件概率转换为求特征词的类条件概率，特征词的类条件概率p(wk|ci)可以由下式估计：

式中：Nik为训练集中特征词wk在类别ci中的权重；为类别ci中所有特征词的权重的总和。

本文特征词的权重采用TF-IDF算法[12]进行计算。

朴素贝叶斯文本分类的目标就是确定极大后验假设MAP(Maximum a Posteriori），即求出文档d最可能的类别值cMAP，表达式如下：

1.2 Dirichlet朴素贝叶斯文本分类算法

Zipf定律[13]是计量语言学中最早提出的统计规律之一。在自然语言的语料库中，特征词出现的频率Pr与其在频率表中的排名r之间有下列关系：

式中：K和γ都是常数，K的值通常取1，γ的值通常取0.1。

如果词表包含数十万个词，由式（9）可计算出其中排名前1 000个最常用的词占各种文章中全部出现的词的80%。计算过程如下：

这个事实表明，对于自然语言中的大多数词，它们在语料库中出现的频率都是稀疏的；而且，无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。因此，在式（8）中，由于存在数据稀疏问题，特征词wk在类别ci中出现的次数可能为零，导致零概率问题。常用的方法是采用Laplace平滑方法进行估计：

但是，Laplace平滑方法由于将所有没有出现的词的概率视为相等，会导致未出现的词的概率过高，降低了分类的准确率。实际上，在统计语言建模技术领域，数据稀疏问题已经得到了广泛的研究，而Laplace平滑方法并不在其中几种首选的平滑方法之列。因此，不妨考虑能否将统计语言建模技术中的平滑方法应用到朴素贝叶斯文本分类之中。在统计语言建模技术中，对于任何一个句子S=(w1,w2,⋯,wk)，可以将其看作是具有以下概率值的马尔科夫过程：

式中n代表了马尔科夫过程的阶数。当n=1时，称之为一元语言模型，此时单词序列w1,w2,⋯,wn在文档中出现的概率P(w1,w2,⋯,wn)=P(w1)⋅P(w2)⋯P(wn)，这种情况和朴素贝叶斯文本分类算法的独立假设完全相同。所以，统计语言建模技术中的平滑方法也适用于朴素贝叶斯文本分类算法。因此，本文提出了一种Dirichlit朴素贝叶斯文本分类算法DNB(Dirichlet Naive Bayes），即引入了统计语言建模技术中广泛应用的Dirichlet平滑方法代替Laplace平滑方法，改进后特征词的类条件概率p(wk|ci)由下式估计：

式中：μ是调节分类性能的参数；p(wk|C)表示wk在ci中出现的预估概率。

2 算法的MapReduce并行化

2.1 文本预处理Job

文本预处理Job的工作流程：

(1）解析输入语料的相对路径Path，将其存放的目录名作为类名Label。

(2）采用中文分词工具对文档内容进行处理。

(3）处理成贝叶斯模型要求的输入格式：每行一篇文档，每篇文档的格式为<Path,(Feature＿1,Feature＿2，…，Feature＿n）>，键Key为Path，值Value为一篇文档分词后的特征词Feature组成的集合，生成TD(tokenized documents）文件。

文本预处理Job的输出文件File及其键值对的表述如表1所示。

2.2 文本向量化Job

文本向量化Job的工作流程如下：

(1）读取TD文件。

(2）统计所有特征词的数目，生成WC(word count）文件。

(3）读取上一步生成的WC文件，为每个特征词分配惟一的ID，生成Dictionary文件。

(4）统计每个文档中每个特征词的词频TF，得到向量Vector＿TF，形式如下：（Feature＿1＿ID:Feature＿1＿TF,Feature＿2＿ID:Feature＿2＿TF，…，Feature＿n＿ID:Feature＿n＿TF），生成TFVectors文件。

(5）统计在所有文档中每个特征词出现的文档频率DF，生成DFCount文件。

(6）计算出每个特征词的权重TFIDF，得到向量Vector＿TFIDF，形式如下：（Feature＿1＿ID:Feature＿1＿TFIDF,Feature＿2＿ID:Feature＿2＿TFIDF，…，Feature＿n＿ID:Feature＿n＿TFIDF），生成TFIDFVectors文件。JobFile

文本向量化Job的输出文件File及其键值对的表述如表2所示。

2.3 训练分类器Job

训练分类器Job的工作流程为：

(1）为类别建立索引，每个类别有对应的ID，生成LabelIndex文件。

(2）读取TFIDFVectors文件，叠加相同类别的文档的向量Vector＿TFIDF，可计算出相同类别的特征词的权重之和LFW，得到向量Vector＿LFW，形式如下：（Fea ture＿1＿ID:Feature＿1＿LFW,Feature＿2＿ID:Feature＿2＿LFW，…，Feature＿n＿ID:Feature＿n＿LFW），生成LFW Vectors文件。

(3）读取上一步得到的LFWVectors文件，叠加所有类别的向量Vector＿LFW，可计算出每个特征词在所有类中的权重之和FW，生成FWCount文件；叠加每个类别的所有特征词的向量Vector＿LFW，可计算出每个类中所有特征词的权重之和LW，生成LWCount文件。

(4）读取之前得到的LFWVectors文件、FWCount文件、LWCount文件，新建一个二维矩阵，行由所有类别构成，列由所有特征词构成，用LFW填充这个矩阵，然后在此矩阵的最后一行增加一行，填充FW，在此矩阵的走后一列添加一列，填充LW，即可构造一个贝叶斯分类模型，生成NaiveBayesModel文件。

训练分类器Job的输出文件File及其键值对的表述如表3所示。

2.4 测试分类器Job

测试分类器Job的工作流程为：

(1）读取NaiveBayesModel文件，建立NaiveBayes Model对象。

(2）在NaiveBayesModel中取出相关参数，根据式（12），计算特征词的类条件概率，根据式（3），计算类先验概率，根据式（6）计算文档对于所有类的后验概率PP(posterior probability），得到向量Vector＿PP，形式如下：（Label＿1＿ID:Label＿1＿PP,Label＿2＿ID:Label＿2＿PP，…，Label＿n＿ID:Label＿n＿PP）。生成Result文件。

(3）读取第（2）步得到的Result文件，取最大的后验概率对应的类别作为该输入文档的类别cMAP。

测试分类器Job的输出文件File及其键值对的表述如表4所示。

3 仿真实验

3.1 实验环境

仿真实验平台是由5个节点组成的Hadoop集群，其中1台为主节点，其余为从节点。每个节点的具体配置如下：4×1.80 GHz CPU,16 GB内存，300 GB硬盘，操作系统为CentOS 6.5,Hadoop版本选用1.2.1。实验数据来源于搜狗实验室提供的文本分类语料库SogouC[14]。数据集包含10个类别，每个类别有8 000篇文档，数据集大小约为277 MB。中文分词工具采用mmseg4j中文分词器。

3.2 实验结果

实验采用准确率P(Precision）和召回率R(Recall）来评估分类算法的性能[15]，计算公式如下：

其中：TPi表示测试文档集中正确分类到类别ci的文档数；FPi表示测试文档集中错误分类到类别ci的文档数；FNi表示测试文档集中属于类别ci但被错误分类到别的类别的文档数。

3.2.1 DNB算法的参数选择

取数据集的60%作为训练集，其余的40%作为测试集，选择5个节点进行实验。参数μ的取值是任意的非负整数，当取0时相当于不采用平滑方法。为了获得参数μ的最佳取值，对μ的取值从0开始逐渐递增，间隔1 000，进行实验。实验结果如图1所示。

从图1可以看出，当参数μ的取值从0递增到3 000的过程中，准确率和召回率都在大幅增加，而参数μ的取值在3 000之后的递增过程中，准确率和召回率或增或减，幅度都较平缓且趋于稳定。因此选择参数μ的取值为3 000。

3.2.2 DNB算法与NB算法的性能对比

取数据集的60%作为训练集，其余的40%作为测试集，选择5个节点进行实验。实验结果如图2、图3所示。

从图2、图3可以看出，除个别类外，改进后的DNB算法的准确率和召回率都优于NB算法，说明了改进后的DNB算法提高了分类性能。

3.2.3 不同数据集对加速比的影响

对数据集进行有返还抽样（sampling with replacement），分别构造100 MB,200 MB,400 MB,800 MB,1 600 MB五个不同大小的新数据集，然后分别从5个新数据集中取60%作为训练集，其余的40%作为测试集，依次选择1个和5个节点进行实验。

实验结果如表5所示。

从表5可以看出，当数据集较小时，加速比[16]并不理想。这是因为当数据集较小时，处理数据的时间较少，节点之间通信消耗的时间相对较多。但是，随着数据集的不断增大，处理数据的时间远远大于节点之间通信消耗的时间，因此加速比有了显著提升，同时说明了本文算法适用于大数据的处理。

3.2.4 不同节点数对运行时间的影响

从1 600 MB的数据集中取60%作为训练集，其余的40%作为测试集，依次选择1～5个节点进行实验。实验结果如图4所示。

从图4可以看出，运行时间随节点数的增加而显著减小，说明了本文算法具有良好的扩展性和高效性。

4 结语

本文提出了一种基于Hadoop的Dirichlet朴素贝叶斯文本分类算法，通过引入统计语言建模技术中的数据平滑方法，降低了数据稀疏问题对分类性能的影响，同时，由于采用并行计算，提高了对海量数据的处理能力，并具有良好的扩展性。实验结果表明，本文算法可以显著提高传统朴素贝叶斯文本分类算法的性能和效率，适用于海量文本数据的处理。

摘要：针对当前大数据环境下朴素贝叶斯文本分类算法在处理文本分类任务时存在的数据稀疏以及效率低的问题,提出了一种基于Hadoop的Dirichlet朴素贝叶斯文本分类算法。该算法引入统计语言建模技术中的Dirichlet数据平滑方法,采用Map Reduce编程模型,在Hadoop云计算平台上实现了算法的并行化。通过实验对比分析了该算法与传统朴素贝叶斯文本分类算法对大规模文本数据的分类效果。结果表明,该算法显著提高了传统朴素贝叶斯文本分类算法的准确率、召回率,且具有高效性和易扩展性。

朴素贝叶斯分类第5篇

随着知识社会的到来及“互联网+”行动计划的制定, 互联网上的海量数据逐渐被有效地收集和整合。国内的一些互联网企业在针对用户的个性化服务上进行了探索, 如豆瓣网提供了推荐书籍、音乐等服务, 百度旅游在假期提供推荐旅游路线, 自动匹配低价机票和酒店等服务。这些创新取得了很好的效果, 大大提高了企业的竞争力。目前的智能个人助理软件都没有针对特定群体进行优化, 而是面向所有用户进行开发。这样的软件涉及的信息过于分散, 缺乏解决实际问题的能力。此外, 由于朴素贝叶斯方法在预测和分类中被广泛应用, 如在预测项目交付率[1]、互联网流量分类[2]、云检测和估计算法[3]等。因此本文提出了针对校园实时信息进行推荐的基于朴素贝叶斯方法的智能推荐算法研究。

2 朴素贝叶斯分类器 (Naive Bayes classifier)

2.1 朴素贝叶斯分类器概述

贝叶斯学习方法中的朴素贝叶斯学习器, 常被称为朴素贝叶斯分类器。在某些领域其性能可与神经网络和决策树学习能力相当[4]。分类问题一直是机器学习、模式分类和数据挖掘的核心问题[5]。

贝叶斯方法的新实例分类目标是在给定描述实例的属性值<a1, a2, ..., an>下, 得到最可能的目标值vmap。朴素贝叶斯分类器所使用的方法:

其中, VNB表示朴素贝叶斯分类器输出的目标值。

2.2 朴素贝叶斯分类器分析

假设给定了如下表1所示的训练样本数据, 学习的目标是根据给定天气的结果判断是否打网球。

样本数据集提供了14个训练样本, 使用此表的数据, 并以朴素贝叶斯分类器来分类下面的新实例: (Outlook=sunny, Temperature=cool, Humidity=high, Wind=strong) 对于新实例预测目Play Tennis的目标值 (Yes或No) , 由上面的公式可以得到:

其他数据同理代入后得到:

故应分类到no中。

3 校园信息智能推荐算法 (Campus recommendation algorithm)

3.1 算法说明

与上述例子有所区别, 在校园信息智能推荐算法中, 所面对情况中的新实例的属性值范围不是仅限于数据库中记录, 而是所有可能的输入值。在新实例中可能存在记录中没有涉及到的属性值。算法需要根据新实例与数据记录的匹配程度推测新实例的目标值, 将其所对应关键字返回, 将新实例记录于数据库中, 以此来达到对新实例学习的目的。

给定了如表2所示的训练样本数据, 学习的目标是以当前的时间节点为条件, 根据用户历史查询记录, 推测客户当前可能最需要获取的信息, 即返回通过算法计算得出的概率值最大的记录所对应的关键字 (时间仅以上下午进行分类) 。

根据表2训练样本 (二) , 当在case1 (Day=Sun, Time=10) 时发出请求。以如下方法计算。

得到的每组数据概率值将都为0, 无法用于比较, 故对以上公式进行修改, 定义如下公式。

其中, k为请求发出时的时间条件与数据库匹配数为0的数量 (如上述样本数据, 数据记录中没有符合Day=Sun条件的记录, 则k值为1) 。则首条记录的概率值为

当在case2 (Day=Mon, Time=10) 时发出请求。

其他数据同理可得, 训练样本计算结果如表3所示。

返回Rate值最大的关键字, 作为查询的输入、输出用户可能需要的数据。

3.2 算法的过程

如图1程序框图所示, 通过二层循环依次计算每条记录与其他记录匹配程度的概率值并保存概率最高的一组记录。最后, 将保存的记录关键字返回。算法包含二层循环, 时间复杂度为O (n2) 。

3.3 算法测试

算法测试所采用的数据库为My SQL, 通过Android客户端在特定时间进行相应内容的查询, 由Java Web端的Servle将数据记录在服务器中, 即生成如图2所示的数据表。

当数据库完成对基础数据的收集后, 用户再通过客户端要求推荐信息时, 算法会根据以上信息进行计算, 分析数据表记录。将得出关键字返回, 查询相应关键字, 得到所需信息, 结果和表2计算结果一致, 如图3所示。

4 结论 (Conclusion)

本文阐述了原始朴素贝叶斯分类器的基本原理, 给出了对其进行变换后的形式化定义。在此基础上, 进一步对基于此理论的校园信息智能推荐算法进行描述, 给出了算法的过程、时间复杂度, 并将算法实际应用于基于Java Web服务器的项目中, 得到测试结果。测试结果与计算结果一致, 达到了预期目的, 能够返回所期望数据。

摘要：本文结合对原始朴素贝叶斯分类器原理的分析, 论述智能助理软件的设计过程中, 所需推荐算法与其之间存在的差异性。并针对在校园收集和整合信息的特点和所需推荐方式, 对原始朴素贝叶斯文本分类器算法加以修改。将得到的校园信息智能推荐算法实现在智能助理软件中。经测试, 算法具有较好的准确性。

关键词：朴素贝叶斯分类器,校园信息提示,智能推荐算法

参考文献

[1]Stewart, B.Predicting Project Delivery Rates Using the NaiveBayes Classifier[J].Journal of Software Maintenance and Evolution Research and Practice, 2002, 14 (3) :161-79.

[2]Jun Zhang, Chao Chen.Internet Traffic Classification by Aggregating Correlated Naive Bayes Predictions[J].IEEE Transactions on Information Forensics and Security, 2013, 8 (1) :5-15.

[3]Islam, T.CLOUDET:a Cloud Detection and Estimation Algorithm for Passive Microwave Imagers and Sounders Aided by Naive Bayes Classifier and Multilayer Perceptron[J].IEEE Journal of Selected Topics In Applied Earth Observations And Remote Sensing, 2015, 8 (9) :296-301.

[4]Tom M.Mitchell.Machine Learning[M].The Mc Graw-Hill Companies, Inc.1997.

[5]LI Xu-Sheng, GU0 Yao-Huang.Extended Tree Augmented Naive Bayesian Classifier[J].Pattern Recognition and Artificial Intelligence, 2006, 19 (4) :470-474.

[6]Zhong Hong-rui, Zhang Yong, Yu Jing-wen.Data Classification On Naive Bayes In Cloud Computing Environment[J].Computer Applications and Software, 2005, 32 (3) :28-30.

[7]Yazdami, M.Artificial intelligence:Principles and Applications[M].Chapman and Hall, Ltd., New York, NY, 1995 (1) :1.

[8]Langley P, Iba W, Thompson K.An Analysis of Bayesian Classifiers[J].In:Proc of the 10th National Conference on Artificial Intelligence.San Jose, USA;AAAI Press, 1992:223-228.

[9]Thomas G.Dietterieh.Ensemble Methods in Machine Learning[C].Lecture Notes in Computer Science, 2000.

朴素贝叶斯分类第6篇

自点对点传输技术出现以来, Peer-to-Peer (P2P) 技术迅速发展, 如今已经成为了网络带宽的最大占有者。有关数据显示, P2P流量已经占据了互联网总流量的60%80%, 而在高校的校园网中, P2P流量更是达到了网络总流量的80%以上。P2P技术的出现, 带来了网络带宽资源匮乏等问题, 致使网络非常拥挤, 严重影响了其他用户对网络的正常使用。因此, 对P2P流量的识别和监管成为企业、高校、运营商等单位必须解决的问题。

早期的P2P应用软件都是通过固定的端口来实现通信的, 所以可以通过端口号来对P2P流量进行识别。不过随着互联网的发展, 只有ppgou等极少数P2P软件仍采用固定的端口和IP, 大多数P2P软件实现了用动态端口进行通信。这就使得通过端口来识别P2P流量的方法已经濒临淘汰。而从网络数据包的内容中提取出应用层数据特征的识别技术得到广泛推广, 也是目前各大设备厂商应用最多的识别技术。然而, 随着以采用数据加密的手段来模糊化协议特征的第四代P2P技术的出现, P2P识别技术面临瓶颈。同时对未加密的P2P流量和加密的P2P流量进行识别, 成为P2P识别技术发展的趋势。

本文重点讲述通过明文特征和朴素贝叶斯[1,2]相结合的方式, 既可以精确地识别出未加密的P2P流量, 又能识别出加密的P2P流量。

1 明文特征识别方式

这是一种基于应用层静态特征的识别方法[3], 各种应用软件通常依赖于不同的协议, 而不同的协议都有其各自的应用层特征。基于明文特征的识别技术需要多次提取P2P应用软件通信过程中各个数据包的应用层信息, 挖掘出其中能代表这个软件的明文特征。所谓明文, 意思是指其应用层数据中的特征字节, 这些字节在数据传输过程中一定会出现。基于明文特征的识别方法是目前比较成熟的技术, 也是大多数网络设备厂商主要使用的技术。

常用的P2P应用的明文特征如表1所示。这些P2P应用在传输层都是用了TCP和UDP两种协议来进行传输, 所以其明文特征也分为两类, 分别对应TCP和UDP两种协议。这些明文特征可以为字符串, 特征字节, 行首字节等。

基于明文特征的P2P流量识别有精确度高, 使用范围广等优点, 不过其缺乏对加密数据分析的功能, 对加密P2P应用的检测能力非常有限。

2 朴素贝叶斯识别方式

随着互联网的进一步发展, 第四代P2P技术成为了一个新的发展趋势, 这一代的P2P应用技术相对第三代技术而言, 主要特点是以采用数据加密的手段使协议流量特征模糊化[4], 用以规避监管。第四代P2P技术相关应用软件的出现, 使得如今主流的协议分析方法面临瓶颈, 明文特征识别方式已经无法有效地识别出采用数据加密使特征模糊化的P2P流量。现采用的朴素贝叶斯分类的方法, 就是用来针对加密的P2P流量进行识别的。

贝叶斯公式:设V1, V2, , Vn (n为正整数) 为样本空间V的一种划分, 如果以P (Vj) 表示事件Vj发生的概率, 且P (Vj) >0 (j=1, 2, , n) , 对于任一事件X, P (X) >0, 有:

朴素贝叶斯分类模型

设Vmap=argmaxP (Vj a1, a2, , am) , 其中Vmap是给定一个实例得到的最可能的目标值, 即后面计算得出的概率最大的一个;a1am (m为任意正整数) 是我们选取的特征集合。根据贝叶斯公式可得

当a1, a2, , am相互独立, P (a1, a2, , am) 的值不变, 为常数。所以 (1) 可化简为

又因为朴素贝叶斯分类器基于一个简单的假定:属性值之间相互条件独立。换句话说, 该假定说明在给定实例的目标值情况下, 观察到联合的a1, a2, , am的概率等于每个单独属性的概率乘积:

将式 (3) 带入式 (2) 可得

其中, VNB表示朴素贝叶斯分类器输出的目标值。所以要想得到目标值, 必须统计信息:

(1) P (Vj) ;

(2) P (ai Vj) , 即对V的每一个子集Vj统计出P (a1 Vj) , P (a2 Vj) , , P (am Vj) 。

选取的特征集合必须完备, 以免影响朴素贝叶斯分类的精确度, 但是如果特征选取过多, 会大大增加统计信息的计算量。所以, 选取的特征集合是一个关系到整个朴素贝叶斯识别方法可行性的关键问题。经过分析, 在选取特征时舍弃一些冗余的特征, 选取四个特征, 分别为数据包长度Length, 包间隔时间ΔT, 重传率RF, TCP初始序号SEQ。

3 系统模型

采用的P2P流量识别模型如图1所示。一条数据流先进入明文特征模块, 搜索是否有明文特征, 若有则打上相应标记, 表示已经识别。若明文特征无法识别, 则进入朴素贝叶斯模块, 根据海量的统计信息, 对其进行识别。

4 软件测试与实验仿真

本实验是基于苏州大学与网经科技联合实验室的融合通信网关OfficeTenA 0来进行的。将本文的明文特征模块和朴素贝叶斯模块加入到OfficeTenA 0系统中。在朴素贝叶斯模块中, 选取的统计特征信息为由数据包长度Length, 包间隔时间ΔT, 重传率RF, TCP初始序号SEQ构成的特征一元组〈Length, ΔT, RF, SEQ〉。被测试的P2P应用软件为thunder、bt、emule、qq旋风、网络快车, 其他的应用统一用others代替。

实验采用识别率和误匹配率两个参数作为指标[5]。假设X代表某P2P应用, m是识别出来的X的流量 (以一个数据包为单位) , n是实际X的流量, s是实际的其他应用的总流量, t是被误匹配为X的其他应用的流量, 则识别率为m/n, 误匹配率为t/s。

同时运行各个P2P应用15分钟, 统计出它们各自的识别率和误匹配率两个参数, 图2为实验测试结果。对列举出的5种P2P应用的识别率都达到了85%以上, 对网络快车的识别达到了95%。可见本文采用的模型对于主流P2P软件有着非常良好的识别率, 不过也都有少量的误匹配, 说明虽然对P2P流量有较强的识别能力, 不过对具体的P2P应用的识别精度还有待改进。

5 结论

本文采用了结合明文特征和朴素贝叶斯分类来识别P2P流量的方法, 分别介绍了这两个方法, 并设计出了识别模型。通过实验测试, 证明了该方法的可行性。该方法需要大量数据样本的统计信息, 不过它对加密的、不加密的P2P流量的识别率非常高, 因而耗费一些时间去统计信息是可以接受的。从测试的结果来看, 该方法可以准确地识别出P2P流量。不过测试结果也表明有少量的误匹配情况, 所以在具体协议识别精度上还需要提高, 这就需要提取更精确的明文特征以及收集数量更多的统计信息, 用以进一步减少误匹配。

摘要：明文特征是基于应用层静态特征的一种识别方法, 需要提取出应用层数据的特征信息;而朴素贝叶斯分类是基于大量统计信息的一种识别方法, 主要用来识别加密的Peer-to-Peer (P2P) 流量。着重介绍了采用明文特征和朴素贝叶斯分类相结合的方法, 对加密的以及未加密的P2P流量进行识别。测试结果表明, 这种方法可以较准确地识别出P2P流量。

关键词：P2P,识别,朴素贝叶斯,明文特征

参考文献

[1]韩家伟.数据挖掘概念与技术.北京:机械工业出版社, 2007:173—174

[2] Auld T, Moore A W.Bayesian neural networks for internet trafficclassification.IEEE Transactions on Neural Net-works, 2007;1 (18) :223—239

[3] Wang Pinghui, Guan Xiaohong.P2P traffic identification based on thesignatures of key packets.Computer Aided Modeling and Design ofCommunication Links and Net-works, 2009;6:1—5

[4]张春红, 裘晓峰, 纪阳, 等.P2P技术全面解析.北京:人民邮电出版社, 2010:214—222

实例讨论朴素贝叶斯模型及其缺陷第7篇

一、两种模型

想要知道一只羊是绵羊还是山羊,可以从判别模型的方法来分析,从数据中来判别,然后通过观察这只羊的特征来预测这只羊是哪一种羊的概率。也就是说我们可以根据山羊的特征来学习一个山羊模型,再根据绵羊特征学习一个绵羊模型。最后从这只羊的特征中进行提取,放到山羊模型中看概率是多少,再放绵羊模型中看概率是多少,谁的概率大就是谁.

常见的判别模型有线性回归、对数回归、线性判别分析等等.常见的生成模型有朴素贝叶斯模型,高斯混合模型等等.

接下来我们重点介绍朴素贝叶斯模型.

二、朴素贝叶斯模型

假设要分类正常邮件和垃圾邮件,分类邮件是文本分类的一种应用.

假设采用最简单的特征描述方法,首先找一部英语词典,将里面的单词全部列出来。然后将每封邮件表示成一个向量,向量中每一维都是字典中的一个词的0/1值,1表示该词在邮件中出现,0表示未出现.

比如一封邮件中出现了“a”和“b u y”,没有出现“aardvark”、“aardwolf”和“zygmurgy”,那么可以形式化表示为:

假设字典中总共有5000个词,那么x是5000维的。这时候如果要建立多项式分布模型(二项分布的扩展).

某随机实验中有k个可能结果A1,A2,…,AK,它们概率分布分别是k,,,ppp21(43),那么在N次采样的结果中,A1出现n1次,而A2出现n2次,……,AK出现nk次,这个事件出现的概率公式为:

我们看出朴素贝叶斯假设是约束性很强的假设,“buy”一般来讲与“price”有关系,而我们假设条件独立.

于是建立模型的形式来表示:

想要数据上概率的乘积能最大,求最大似然估计为:

联合概率分布乘积最大,说明朴素贝叶斯是生成模型.