加权朴素贝叶斯

2024-06-21

加权朴素贝叶斯（精选七篇）

加权朴素贝叶斯篇1

关键词：朴素贝叶斯,成绩预测,信息熵

1 引言

目前, 各大高校由于在校生规模较以往扩大许多, 在教学过程中积累了大量的有关学生学习成绩的资源, 但传统的方法难以在这些海量的数据中寻找到有价值的信息, 教学管理者和决策者们都迫切需要通过更高层次的数据分析来揭示其教学中的规律, 从而更好的开展教学工作。于是许多学者开始使用数据挖掘技术去研究这些教育数据中潜藏的知识和信息, 为高校教学的提高和改革提供更科学有效地支持。本文建议使用朴素贝叶斯模型对学生成绩进行预测和分析, 找出对学生成绩影响较大的因素, 将这些处理的结果有效地用于完善教学系统的设计、控制和评价中, 从而及时改进和调整教学策略, 进而提高高校的教学质量。

2 加权朴素贝叶斯模型

朴素贝叶斯分类 (NBC) 是数据挖掘中最基础有效的分类算法之一, 它有着完整的数学基础和稳定的分类效率。如果有一个数据样本X和描述它的n个属性, 即X={x 1, x2, ..., xn}, 而类别变量Y有m个属性, 即Y={y 1, y2, ..., ym}, 在朴素贝叶斯分类时假设各个样本属性相对于类别条件是独立的, 满足公式:

其中概率P (x k|ym) 可以由收集得来的训练数据集中直接计算得到。

根据贝叶斯定理, 数据样本相对于类别变量的后验概率值为:

朴素贝叶斯分类法预测X应当属于具有最高后验概率的类, 也就是说, 朴素贝叶斯分类将未知样本分配给类别iy, 当且仅当:

朴素贝叶斯分类法与其他算法相比有着最小的误差率, 但其前提条件限制比较严格, 只有当对象的各个属性之间都相互独立时, 使用朴素贝叶斯模型可以得到最佳分类效果, 然而在学生成绩预测的几个研究属性之间很难满足这个条件, 例如:任课教师的资历很可能对学生的上课兴趣和教师评价有着一定的关联, 而学生平时所学习的专业也有可能影响学生对电脑的熟悉度等。为了弥补这个缺陷, 有学者提出了加权朴素贝叶斯分类模型 (WNBC) , 其主要思想是为每个属性赋予不同的权值, 从而使得朴素贝叶斯方法得以扩展, 降低算法对属性独立性的要求, 同时也有利于提高分类的效率。加权朴素贝叶斯分类模型被定义为:

其中iw代表属性ix的权值。显然如果权值越大, 该属性对分类的影响就越大, 因此加权朴素贝叶斯分类的关键问题就在于如何确定不同属性的权值。

3 确定属性权值

本文使用的是一种基于互信息量的分类模型, 它能根据信息论中的平均互信息量的值来计算条件属性的权重, 充分考虑各个条件属性对类别的影响, 从而大大提高分类算法的效率。

对于一个数据样本X={x 1, x2, ..., xn}和类别变量Y={y 1, y2, ..., ym}, ix与iy之间的互信息量, 也称为事件信息的概率计算公式为:

如果p (ix) =p (xi|yj) 时, 说明事件ix和yj相互独立, 互信息量I (x i;yi) 为0;如果p (xi|yj) >p (ix) , 那么说明当yj出现时, ix出现的几率随之增加, 此时互信息量I (x i;yi) 为正数;相反的, 如果p (xi|yj)

因此可以计算每个属性ix相对于类别变量的权重:

得到权重向量 (w1, w2, ..., wn) 。

在设计学生成绩分析预测模型时, 可以先计算这些属性的权重, 主要目的是能区分不同属性对决策的不同影响, 一般对分类有较大影响的属性, 我们赋予它较大的权重;相反地, 如果该属性对分类影响较小, 则权重值也应当越小, 从而可以增强对分类影响大的属性的学习, 也有利于提高分类学习的效率。

4 构建学生成绩预测模型

以目前各高校都必须要求学生参加的计算机等级考试为例, 我们采集了某高校大一新生的数据, 整理出可能影响学生计算机等级考试成绩的因素, 包括学生的高中的文理科计算机会考成绩、生源地, 入校后就读专业、任课教师的条件、学生对计算机的兴趣和了解等, 制成数据调查表, 要求学生如实填写信息。收集调查表后进行数据录入和预处理, 并根据算法需要对文本数据进行必要的转换, 例如将学生学习兴趣度归纳为三个等级, 分别是很感兴趣, 一般, 和没兴趣, 形成可适用于算法的数据表如下所示:

为了验证预测模型的效果, 我们将数据库中70%的数据做为训练集, 用于构建分类预测模型, 而将剩下的30%做为测试集, 用于测试模型的准确度。首先可以根据公式 (6) 计算出每个属性的权值如下:

为了验证方法的准确度和效率, 我们将本文所采用的加权朴素贝叶斯分类法和传统贝叶斯分类法做了比较试验, 分别在取数据测试集样本量为500、1000、1500、2500、3000时得到的准确度如下表所示:

通过两种分类法测试结果的比较, 可以看出加权朴素贝叶斯分类法比传统朴素贝叶斯分类法的准确度要略高些, 而如果训练集数据量越大, 那么加权朴素贝叶斯分类法的优势就更加明显。

5 总结

本文使用加权朴素贝叶斯分类法来对高校中学生的考试成绩做了预测分析, 各个属性的权值是由根据信息论观点下的平均互信息量计算得来的, 实验表明, 本文采用的加权朴素贝叶斯分类法在准确度上比传统朴素贝叶斯方法要更好, 特别是在取样的数据集量比较大时, 分类的效果越好, 可以做为预测和分析学生成绩的一种有效方法。

参考文献

[1]孔丽英, 数据挖掘在计算机等级考试中的应用[J], 计算机教育, 2010, 1, 38-41

[2]数据挖掘导论

[3] (Harry Z, Sheng S.Learning Weighted Na ve Bayes with Accurate Ranking[J].The Fourth IEEE International Conference on Data Minging, 2004, 341-356)

[4]李立萍, 张明友, 信息论导引[M], 成都:电子科技大学出版社, 2005, 32-70

[5]张龙飞, 基于互信息的朴素贝叶斯改进模型研究[D], 长春:吉林大学, 2010, 27-38

加权朴素贝叶斯篇2

随着网络信息量的不断增大以及网络服务规模的日益扩大,保障网络数据安全性的网络信息安全技术开始受到各界领域的关注与重视。入侵检测技术( IDT) 在网络环境中作为防火墙技术( FT) 的有效补充可被分为异常检测( AD) 和误用检测( MD) 两大类,它能够通过审计、检测、识别和响应的方式实时地对网络行为进行监控并过滤信息数据,形成一种内外呼应的智能保护体系[1]。

由于网络技术的不断更新,网络入侵行为也演变的更加复杂多变,海量数据情况下的网络环境也使得入侵检测技术不断面临着巨大的挑战。因此,将针对大数据环境的数据挖掘( DM) 算法如: KNN[2]、朴素贝叶斯( NB)[3]、支持向量机( SVM)[4]、K-means[5]等应用在入侵检测技术当中逐渐成为研究热点。其中,朴素贝叶斯( NB) 算法作为最优秀的分类模型之一被广泛应用于各信息领域。但由于NB的“独立性假设”要求,这样会忽略属性与属性之间的依赖关系,使得属性所具有的关系性得不到体现,这与网络环境中数据之间的复杂联系情况相违背,对于入侵检测技术中的网络行为分类就会表现出较低的准确率。因此,针对这一算法缺陷,研究人员运用各种方法技术对朴素贝叶斯( NB) 算法进行改进,以提升其分类的性能。

文献[6]中首次引入了隐朴素贝叶斯( HNB) 模型的概念,该算法在NB模型的基础上通过为每个属性节点增加一个隐藏父节点来记录该节点与其他节点间的依赖关系,弱化了属性间的独立性条件,从而提高了分类精度,但该模型对于多重属性的关系网络却显得效率较低。在文献[7]中,针对HNB算法改进的双隐朴素贝叶斯( DHNB) 模型被提出。该模型通过再度为每个属性节点增加一个新的隐藏父节点,该节点用来记录每个属性依赖关系的加权总和,从而更加充分地表示每个节点之间的关系情况,通过权重( Weight) 属性进一步提升了NB算法的性能。文献[8]介绍了一种随机选择朴素贝叶斯( RSNB) ,该算法是在包装器( Wrapper) 属性特征子集选择方法( FSS) 的基础之上,在整个属性空间中装载随机搜索,使得NB算法的预测性和分辨性增强,但在一定程度上也增加了算法本身的时间和空间复杂度O( n) 。Flores等人[9]采用了在连续和离散域AODE( Aggregating One-dependence Estimators) 模型中自动建立基于复杂属性值的半朴素贝叶斯( SNB) ,该算法能够将依赖性较强的基本属性特征组合成集合,因此SNB在某种程度上简化了属性集的复杂度,去除冗余属性,从而避免了分类干扰因素。在文献[10]中,一种动态完全朴素贝叶斯( DCNB) 分类模型被建立,该算法通过使用多元高斯核函数估计属性条件联合密度与平滑参数优化的方法,有效地利用了属性之间的条件依赖信息,从而提升了NB算法的分类准确性,但该改进算法针对大数据环境却显得效率有所降低。文献[11,12]分别引入属性加权的思想对NB算法进行了改进,通过对不同的条件属性赋予不同的权值来降低分类干扰,提高检测精度。

本文在前人的研究基础之上,针对上述改进方法的优缺点,提出了一种改进的NB算法———树加权朴素贝叶斯( TW-NB) 算法,并将该算法引入到入侵检测技术当中。该算法通过使用决策树归纳法( DTI) 过滤出重要的属性子集,首先通过决策树估计出被选择的属性权重,然后只有这些由决策树根据它们相关权重所选择出的最重要的属性才能被用于“类条件独立性假设”的计算。本文将结合使用KDD’99 入侵检测数据集测试并验证TW-NB算法在入侵检测技术中的性能,并与NB算法进行分类准确度的比较。实验结果证明,TW-NB算法在网络入侵行为的检测率与误检率方面较NB算法都有显著的改善,针对复杂多级的集合环境也能表现出较高的分类效率。

1 改进算法相关研究

1. 1 NB分类算法

给定一个N维训练样本集T = { D1,D2,…,Dn} ,其中Di={ d1,d2,…,dn} 表示集合中每个数据记录。训练集T包含属性集合A = { A1,A2,…,An} ,而每个属性Ai拥有属性值集合{ a1,a2,…,an} ,属性值可以是离散值或者连续值。训练数据集T还包含类集合C = { C1,C2,…,Cm| ( m ≤ n) } ,每个训练样本实例D( D∈ T) 均拥有一个特定的类别标记Cj。对于一个测试样本集E ={ e1,e2,…,en} ,测试实例ei可根据贝叶斯定理计算的后验概率P( Cj| Ai) 得出其所属类别。先验概率P( Cj) 可由拉普拉斯校正方程统计每个类别Cj( j ≤ m) 在训练集T中所出现的频率估算所得,条件概率P( Ai| Cj) 可相应地根据属性值ai( i ≤ n) 在训练集T中对应的所属类别Cj中出现的频率计算得出。因此,朴素贝叶斯( NB) 算法可通过先验概率和条件概率进行预测,从而得出待分类样本实例的所属类别,达到不同数据归类的目的。

根据式( 1) 可分别计算出测试样本属性ei所属类别的后验概率,NB分类算法找出最大后验概率MAP最终划分属性的归属类别,根据式( 2) 计算所得,即在训练集中仅当P( Ci| ei) >P( Cj| ei) ( i ≠ j,1 ≤ j ≤ m) ,则ei的类别标签为Ci,概率P( Ci| ei) 即为最大后验假设。

朴素贝叶斯分类器( NBC) 是一个基于概率的算法,可以预测样本所属类成员的概率。该算法有以下优点: ( 1) 算法构造简单,时间复杂度低; ( 2) 概率生成仅需单次遍历训练集合;( 3) 模型结构清晰严谨,具备较好的鲁棒性和可扩展性。NBC需要条件独立性假设的前提,即属性在给定类的影响独立于其他属性。

1. 2 决策树归纳法

决策树归纳法( DTI) 是一组规则集合,使用递归的方式将训练样本集( TS) 划分成更小的子集合( Sub-TS) ,直到每一个子集合拥有独有的所属类别标签。DTI算法通常采用信息论( IT)作为属性选择方法,根节点TS的选择是基于计算出的所具有最高信息增益的属性。给定一个N维训练样本集T = { t1,t2,…,tn} ,pj表示样本实例ti( i ≤ n) 属于类别Cj( j ≤ m) 的先验概率,可根据式( 3) 得出对给定的样本实例进行分类所需要的期望信息Info( T) 。

相应地,训练样本集T根据属性A = { a1,a2,…,an} 迭代地被划分成N个不同的子集合{ T1,T2,…,Tn} ,其中Ti为样本集合T中属性A = ai时的样本子集合。可根据权重值| Ti| / | T |计算出属性A划分T的期望信息,从而根据原始信息要求Info( T) 和新的信息要求的偏移量计算得出信息增益Info Gain( A) 。根据样本集T中的属性值,逐一地计算出每个属性值对T进行划分的信息增益,从中选择出具有最高信息增益的属性Am作为最佳属性来划分子集合,递归整个过程直到所有集合都被正确归类。

DTI用于分析构建模型的可行性与可信度,相应地根据观察推出其逻辑表达式及结构,通过其简单清晰的逻辑推理和分割信息值,能够快捷地对大数据集进行高效的数据划分。但针对连续型数据和多类别集合,划分效率就会随复杂度的升高而降低。

1. 3 TW-NB算法

树加权朴素贝叶斯( TW-NB) 算法是通过引入决策树归纳法( DTI) 来增强朴素贝叶斯( NB) 算法的预测性与可行性,增加权重参数使样本属性之间的独立性得到弱化,运用信息增益比迭代地将集合逐步精确细分,从而使得每个样本实例都能正确的被归类。

在一个给定的N维训练样本集合U中,其每一个训练样本实例Si( Si∈ U) 都拥有一组属性{ A1,A2,…,An} ,且每个属性都有不同的取值{ a1,a2,…,an} 。同时,样本集中的类集合C ={ C1,C2,…,Cm} 用于标记样本实例Si( i ≤ n) 。首先,根据决策树归纳法则,将训练集U构建成未修剪的决策树Tr,集合中每个样本拥有属性值,Tr作为属性选择及计算影响样本属性Ai归类的权重值 φ 的决策方法。构建完Tr后,使用决策树分类器从集合中分出最影响分类的子集合,为训练集U中每一个属性Ai初始化权重值 φ( i ≤ n,φ ≥0) 。如果Ai∈U但Ai Tr,则设初值 φ = 0。计算出Tr中测试属性Ai∈ Tr的最小深度D,并将属性的权重值初始化为1 /D。根据式( 5) ,将选择属性的权重值设为朴素贝叶斯( NB) 后验概率计算定理的指数时,能够影响分类的条件概率估算。最终,通过Laplace定理估计出Tr中类先验概率P( Cj) ( j ≤ m) 和属性条件概率P( Ai|Cj) ,属性通过 φ ≠ 0 而被选择出作为影响样本的最终归类,从而计算出后验概率而得出正确分类,而 φ = 0 的属性样本将不会出现在分类集合中。

其中,权重值 φ 是属性值类条件概率计算及样本之间关系的影响因子,得出样本属性的所属类别需要根据决策树Tr确定其影响最终分类的属性关系。并根据先验概率和条件概率估计出最大后验概率MAP,通过递归的原则逐步重复划分子集合的过程,将错分的子集合再次重组继续划分归类,最终确定每个样本的分类集合。TW-NB算法的具体实现过程如下:

输入训练样本集U = { S1,S2,…,Sn} 。

1) 在集合U中去除冗余样本数据,选择出最佳分裂属性并逐步地建立未修剪的决策树Tr 。

2) for ( 确定Tr中的每个节点Ni和分割路径Path ) 。

3) if ( 该条Path终止) ,将该子集合Ue确定为叶节点Ne并将其合理的分类。

4) else将子集合根据Path继续划分,建立决策子树Tr-s并为每个节点添加标记Li( i ≤ n) ) 。

5) for ( 遍历每个属性Ai( Ai∈ U) ) 。

6) if ( Ai∈ U但) ,设初权重值 φ = 0 。

7) else作为Tr中属性Ai( i ≤ n) 的最小深度D,初始化权重值 φ = 1 /D 。

8) for ( 分别遍历U中的类别标记Cj( j ≤ m) 和属性Ai( φ≠ 0) ) 。

9) 运用Laplace方程,根据类别Cj( Cj∈ U) 在训练集U中所出现的频率估算出先验类概率P( Cj) ≥0 和带有影响指数的条件概率P( Ai| Cj) ≥ 0 。

10) for ( 遍历每一个求出的后验概率P( Cj| Ai) ) 。

11) 训练集U中比较每一个后验概率的值,当且仅当P( Cx| Ai) > P( Cj| Ai) ( x ≠ j ≤ m) ,即P( Cx| Ai) 为最大后验概率MAP,选取Cx作为Ai的所属类别,直到所有的子集合Us分类完毕。

输出训练集中所有样本均正确归类的分类集合UC,其中映射函数f: Cj→ Ai( j ≤ i ≤ n) 。

2 入侵检测实验与分析

2. 1 KDD’99 入侵检测数据集

入侵检测技术即为一种概率性预测及网络数据分类技术,将TW-NB分类器运用在该技术中来检测网络异常行为及事件数据归类达到预警功能是合理有效的。

本文实验使用KDD Cup 1999 ( KDD’99) 入侵检测数据集,通过实验数据来验证基于TW-NB算法的入侵检测技术的检测效率。在KDD’99 数据集中,每个样本表示网络数据流中类Class的属性值A: { A1A2,…,An} ,每个类Class都被标记着正常Normal或攻击Attack。这些类在数据集中可被分为{ Normal,DOS,U2R,R2L,Probe} 五大类,其中四大入侵类又可被细分成22 种攻击类型如表1 所示。

KDD’99 数据集是由DARPA98 数据集转化来的,它是对DARPA98 数据进一步过滤处理后产生的。由于原始数据集的庞大以及包含过多的冗余和缺失数据,因此KDD’99 数据集提供了一个500 万条数据记录其中的10% 的样本数据作为子集来方便数据的实验。通过实验数据的需求,本文选取了这个10% KDD’99 数据子集中的样本分别作训练集Train和测试集Test数据如表2 所示,同时数据集中为每次的网络连接使用的41 种输入属性特征如表3 所示。

2. 2 影响因素的分析与预处理

在实际的网络环境中,海量的网络访问数据由于类型和结构的不同会造成普遍的数据冗余以及一定程度的数据缺失,这些现实因素会直接影响到TW-NB算法的分类性能和预测效果。因此,数据的预处理为解决干扰问题对于验证算法的性能和健壮性是非常必要的。所关注并处理的实际影响因素主要有以下几项:

( 1) 冗余数据

实际环境中数据的冗余现象是必然存在的,它直接影响着数据的质量。因此,增加数据的独立性和剔除冗余数据是测试大规模数据系统成功的前提条件。

( 2) 缺失数据

数据的缺失造成了系统丢失了大量的有用信息,使系统表现出更加显著的不确定性,包含空值的数据会使分类过程陷入混乱并导致不可靠地输出。

处理以上影响TW-NB算法的分类预测因素,本文采用基于特征相似度的属性选择方法。主要步骤如下:

1) 根据式( 6) ,在数据集合U中计算与属性Aj之间的相似度 ρij。其中1 ≤ j ≤ n,且Aj∈ U 。

2 ) 选择相似度 ρij最大的完整属性Ai( 1 ≤ i ≤ n) 作为缺失数据的弥补对象,用于填补数据的完整性。

3) 计算数据集合U中属性之间的方差值COV( i,j) ,选择方差小的属性值,方差相同的属性任选其一,从而剔除了不必要的冗余数据,提高了数据质量。

4) 输出一个完整的、低冗余度的属性集合D 。

2. 3 实验结果分析

实验仿真环境采用Windows 7 操作系统、2. 8 GHz双核CPU、4 GB DDR3 内存以及Weka智能分析环境,实验数据使用KDD’99 入侵检测数据集中10% 训练及测试样本数据。根据入侵检测仿真实验结果,基于TW-NB算法的入侵检测技术的检测效率分析以及改进前后算法性能的比较结果分别如图1 所示。

从图1 和图2 中的实验结果可以看出,TW-NB算法在检测不同入侵数据时较NB算法在DR和FR方面都有了明显的性能提升,尤其对于DOS攻击和R2L攻击在检测率和误检率上分别有大幅度改善。由图3 所示,在设置了阈值( θ = 98. 5% ) 的情况下,TW-NB算法对入侵检测数据集中的攻击数据的检测准确度Accuracy的连续值较NB算法有了普遍的提高,整体连续属性取值均高于阈值 θ,最高准确值Am可达99. 76% 。而NB算法的检测准确度值趋于或低于阈值,最低取值降到98. 12% ,远远低于阈值。当准确度取值A < θ 时,则值A为不期望值。

结合实验结果与数据分析,本文将TW-NB算法分别与网络入侵检测领域中的其他流行的数据挖掘算法( C4. 5、SVM、Kmeans) 以及改进的NB算法( HNB、RSNB、AODE) 进行检测性能的比较,比较结果分别如表4 和表5 所示。

根据表4、表5 的数据比较结果,本文的改进算法TW-NB在检测率( DR) 和分类准确度( Accuracy) 方面较其他流行的数据挖掘算法以及改进算法均有明显的提升和改善。从其他实验结果可分析,TW-NB算法的平均入侵检测率可达99. 49% ,平均准确度较其他算法可提升到99. 162% ,平均错误分类率较其他算法可降到0. 838% ,检测性能具有比较显著的改进。

3 结语

针对现代网络环境中复杂多变的网络入侵行为,本文借鉴朴素贝叶斯理论,提出了改进的NB算法———TW-NB算法,并运用在入侵检测技术当中,将攻击数据从海量数据中划分出来并进行攻击预测。TW-NB算法通过引入决策归纳法( DTI) ,设计权重参数 φ 以及决策准则来进一步控制朴素贝叶斯( NB) 的分类,从而更加提高了NB算法的分类准确度。实验中,首先运用Weka智能分析环境和KDD’99 入侵检测数据集中的大量数据验证了算法的可行性,并分析实验结果得到不同效果的实验图和表。在今后的研究工作中,将进一步深入优化并提升TW-NB算法的分类性能。由于该算法对冗余数据复杂度及计算资源状况较为敏感,因此在下一步的计划当中,将引入数据预处理的相关方法再度提高TW-NB算法的鲁棒性和适用性。

参考文献

[1]史志才,夏永祥.高速网络环境下的入侵检测技术研究综述[J].计算机应用研究,2010,27(5):1606-1610.

[2]Yang Li,Li Guo.An active learning based TCM-KNN algorithm for supervised network intrusion detection[J].Computers&Security,2007,26(7):459-467.

[3]Levent Koc,Thomas A Mazzuchi,Shahram Sarkani.A network intrusion detection system based on a Hidden Nave Bayes multiclass classifier[J].Expert Systems with Applications,2012,39(18):13492-13500.

[4]谭爱平,陈浩,吴伯桥.基于SVM的网络入侵检测集成学习算法[J].计算机科学,2014,41(2):197-200.

[5]Reda M Elbasiony,Elsayed A Sallam.A hybrid network intrusion detection framework based on random forests and weighted k-means[J].Ain Shams Engineering Journal,2013,4(4):753-762.

[6]Jiang Liangxiao,Zhang H,Cai Zhihua.A novel Bayes model:hidden naive Bayes[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1361-1371.

[7]李晶辉,张小刚.一种改进隐朴素贝叶斯算法的研究[J].小型微型计算机系统,2013,34(7):1654-1658.

[8]Liangxiao Jiang,Zhihua Cai,Harry Zhang.Not so greedy:Randomly Selected Naive Bayes[J].Expert Systems with Applications,2012,39(12):11022-11028.

[9]M Julia Flores,JoséA Gámez,Ana M Martínez.Domains of competence of the semi-naive Bayesian network classifiers[J].2014,260(1):120-148.

[10]王双成,杜瑞杰,刘颖.连续属性完全贝叶斯分类器的学习与优化[J].计算机学报,2012,35(10):2129-2138.

[11]李方,刘琼荪.基于改进属性加权的朴素贝叶斯分类模型[J].计算机工程与应用,2010,46(4):132-141.

朴素贝叶斯分类法的应用篇3

一、朴素贝叶斯分类法的工作过程

1. 设D是训练元组。每个元组用一个属性向量X={x1, x2, ..., xn}表示。

2. 假设m有个类C1, C2, ..., Cm, 给定元组X, 分类法将预测出X属于具有最高后验概率的那个类。也就是说, 朴素贝叶斯分类方法预测X属于Ci类, 即

这样就可最大化P (Ci|X) 。其中P (Ci|X) , 最大的类Ci就称为最大后验假设。可得:

3. 给定具有许多属性的数据集时, 计算P (X|Ci) 的开销可能会非常大。

为了降低计算P (X|Ci) 的开销, 需要做类条件独立的朴素假定。给定了元组的类标号, 假定属性值之间有条件地相互独立, 可得:

二、朴素贝叶斯分类实例

根据天气情况来判断某天是否去春游。给定如表所式的10个训练元组, 其中每天由属性天气情况, 温度, 风力和AQI来描述, 类属性春游。

现在有一测试样本X:

<天气:晴, 温度:凉爽, 风力:大, AQI:157>

问这一天是否适合春游。

首先, 最大化P (X|Ci) P (Ci) , i=, 12。P (春游=是) =6/10=0.600P (春游=否) =4/10=0.400

为了计算P (X|Ci) , i=, 12, 需计算以下条件概率:

类似的, P (X|春游=否) =0.500*0.250*0.600*0.800=0.060

为了发现最大化的的类, 计算

P (X|春游=是) *P (春游=是) =0.030*0.600=0.018

P (X|春游=否) *P (春游=否) =0.060*0.400=0.024

因此对于元组X, 应用朴素贝叶斯分类器可预测出元组的X类为春游=否。

三、总结

本文对朴素贝叶斯分类方法进行了详细介绍, 并给出了实例证实了朴素贝叶斯分类法的优势。通过将该分类法与决策树、神经网络的分类法进行的各种比较试验证明, 在许多领域中, 贝叶斯分类法可以与它们相媲美。从理论上讲, 与其他所有的分类法算法相比, 贝叶斯分类具有最小错误率。

摘要：朴素贝叶斯分类器是一种简单且高效的分类算法, 在数据挖掘、模式识别等领域中应用广泛, 以其独特的不确定性的知识表达形式、丰富的概率表达的能力、以及综合的先验知识增量学习的特性等成为众多分类方法中较为流行的方法之一。

关键词：数据挖掘,朴素贝叶斯,分类

参考文献

[1]韩家炜著.数据挖掘概念与技术.机械工业出版社.2011.

[2]王国才.朴素贝叶斯分类器的研究与应用.重庆交通大学硕士学位论文, 2010.

[3]李艳美.基于贝叶斯网络的数据挖掘应用研究.西安电子科技大学硕士学位论文, 2008.

一种新的朴素贝叶斯属性选择算法篇4

贝叶斯学派是现代统计学中与经典频率学派并列的两大学派之一, 贝叶斯数据分析就是先验分布在经过了数据所提供的证据修订之后所形成的经验分布[1]。英国牧师ThomasBayes在1763年提出了后来以他的名字命名的贝叶斯理论。随着统计决策理论、信息论和经验贝叶斯方法等理论和方法的创立和应用, 贝叶斯方法很快显示出他的优点, 成为十分活跃的一个方向。

Duda和Hart于1937年提出了基于贝叶斯公式的朴素贝叶斯分类器NBC (NaiveBayesianClassification) [2]。NBC是一个简单有效而且在实际使用中比较成功的分类器。朴素贝叶斯分类器假设一个指定类别中各属性的取值是相互独立的。这一假设也被称为:类别条件独立。即每个属性变量都以类变量作为唯一的父节点。它可以帮助有效减少在构造贝叶斯分类器时所需要进行的计算量。后来, 人们又提出了许多方法和技术, 包括半朴素贝叶斯分类器 (semi-NB) [3]、相关属性删除[4]、概率值调节[5]、贝叶斯网络 (Bayesiannetworks) [6]、贝叶斯树 (NBTree) [7]以及懒惰贝叶斯规则方法[8]。这些算法是对朴素贝叶斯算法的改进和推广。

朴素贝叶斯学习有很多优点, 首先它在很宽范围的应用中都有出人意料的好效果。其次, 朴素贝叶斯学习可以很好地扩展到超大规模的问题, 并且不需要通过搜索来寻找最大后验概率的朴素贝叶斯假设。最后, 朴素贝叶斯学习可以轻松地应付有噪声的训练数据, 并在适当的时候给出概率预测。然而, 虽然朴素贝叶斯分类器算法比较简单, 不需要进行结构学习, 但在实际的应用领域中, 各个属性相互独立的假设很难成立, 是进一步提高其精度的主要障碍之一。

本文介绍朴素贝叶斯分类器, 然后提出一种新的朴素贝叶斯分类算法, 最后给出结论。

1 朴素贝叶斯分类器

给定一个类别c∈C, 样本集有n个属性A1, A2, A3, …, An, 测试样本x= (a1, a2, …, an) ∈X, 根据给定包含多个属性的样本集, 直接计算P (x c) 的运算量是非常大的。为实现对P (x c) 的有效估算, 朴素贝叶斯分类器通常都假设各类别是相互独立的, 即各属性的取值是相互独立的。对于特定的类别且其各属性相互独立, 就会有:

结合贝叶斯定理中, 可得

在公式 (2) 中对于所有的类别P (x) 相同。因此NaiveBayes分类器可以用下列公式表示:

当属性Ai为连续变量或是离散变量时, P (ai c) 会有不同的计算方法:

(1) 当属性Ai为连续变量时, 可以假定它们满足一定形式的分布 (如高斯正态分布, 核函数分布等) , 通常假定属性服从高斯正态分布, 并把类条件概率密度函数f (x) 作为P (ai c) , f (x) 定义如下:

(4) 式中:g (x, u, σ) 为属性Ai的高斯规范密度函数;μ和σ为训练样本中类别为c的属性Ai取值的平均值和方差。

(2) 当属性Ai为离散变量时, P (ai c) 等于类别为c的样本中属性Ai等于ai的比例。

图1显示了朴素贝叶斯分类算法的训练流程和分类流程。

朴素贝叶斯分类器算法比较简单, 不需要进行结构学习。然而, 在朴素贝叶斯分类器算法中, 各个属性相互独立的假设很难成立, 因而进一步提高其精度相当因难。

2 一种新的朴素贝叶斯属性选择算法

朴素贝叶斯分类器由于类别条件独立的假设, 影响了它在现实分类中的性能, 而属性冗余是影响类别条件独立假设成立的一个因素。而在搜索空间添加属性时与属性的顺序无关, 这样会导致在添加几个相关的属性时留下的属性未能具有最优的分类性能。因此, 我们决定利用信息增益方法对属性集合S中的属性进行排序, 即按照信息增益值的大小对属性进行排序。

2.1 一种新的朴素贝叶斯属性选择算法

按照信息增益值对属性排序, 我们提出一种新的选择性朴素贝叶斯算法, 其步骤描述如下:

输入变量:S为所有属性的集合;待分类的数据集合。

输出变量:S′为属性选择集合;最大准确率Accuracymax。

(1) 初始化属性选择集合S′为空集合;S为所有属性的集合;S为根据属性的信息增益高低排序的属性集合;S″为未选择的属性集合, S″=S;最大准确率AAccuracymax=0;当前准确率AAccuracycurrent=0。

(2) 如果S″为空跳到步骤5;

(3) 选取S″中的第一个属性ai, S′=S′∪ai, 根据SNB算法的分类公式进行分类, 并计算当前AAccuracycurrent;

(4) 如果AAccuracycurrent≥AAccuracymax:AAccuracymax=

如果Accuracycurrent<Accuracymax:S′=S′-ai,

跳到步骤 (2) 。

(5) 保存此时的S′和AAccuracymax, 算法终止;

2.2 例子

例1设有4个属性的集合{v1, v2, v3, v4}, 属性v4和属性v1完全相关 (冗余) 。假设按照属性的原始顺序进行初始化并分类选择, S′会不断地加入属性v1、v2和v3, 当加入属性v4时, 会出现属性v1与属性v4相关而导致的准确率下降, 因此S′={v1, v2, v3}

例2在例1的条件下 (除了属性v1和v4属性完全相关, 只是属性v1和v4属性相关) , 假设按照属性原始顺序的逆顺序进行初始化并分类选择, S′会不断地加入属性v4、v3和v2, 当加入属性v1时, 会出现属性v1与属性v4相关而导致准确率下降, 因此S′

从例1和例2中可以看出, 属性集合中的属性顺序会导致不同的属性选择集合S′。在例1中S′={v1, v2, v3}不一定能出现最好的分类性能, 同理在例2中S′={v2, v3, v4}也不一定能出现最好的分类性能。

我们提出的算法使得最原始的属性集合S中的属性应该按照一定的顺序进行排序, 并且按照这种顺序排序的属性集合所选取的S′能使分类器的性能达到最优。

4 结论

本文研究朴素贝叶斯属性选择算法。首先介绍了朴素贝叶斯分类器NBC原量, 紧接着分析了此种方法的不足;然后提出了一种新的选择性贝叶斯分类算法。新算法按照属性信息增益值的大小进行排序后再进行属性选择这一策略, 能够取得好的分类效果。

摘要：贝叶斯分类算法存在一个不足之处, 即在搜索空间添加属性时与属性的顺序无关, 导致在添加几个相关的属性时留下的属性不能具有最优的分类性能。提出的一种选择性朴素贝叶斯算法, 先按照属性信息增益值的大小对属性进行排序, 然后再对属性进行选择, 从而能够提高分类的准确率。

参考文献

[1] Jia Weihan, Kamber M.数据挖掘概念与技术.范明, 译.北京:机械工业出版社, 2001:99—101

[2] Langley P, Iba W, Thompson K.An analysis of Bayesian classifiers.In:Proc of the l0th National Conf.on Artificial Intelligence.MenloP-ark:AAAI Press, 1992:223—228

[3] Kononenko I.Seminaive Bayesian classifier.In:Proc of the 6th Eu-ropean Working Session on Learning.NewYork:Springer-Verlag, 1991:206—219

[4] Langley P, Sage S.Induction of selective Bayesian classifiers.In:Uncertainty in Artificial Intelligence.SanFrancisco:Morgan Kauf-mann Publishers, 1994:399—406

[5] Webb G I, Pazzani M J.Adjusted probability naive Bayesian induc-tion.In:Proc of the l1th Australian Joint Conf on Artificial Intelli-gence.Berlin:Springer-Verlag, 1998:285—295

[6] Friedman N, Geiger D, Goldszmidt M.Bayesian network classifiers.Machine Learning, 1997;29 (2—3) :131—163

[7] Geiger D.An entropy-based learning algorithm of Bayesian condition-al trees.In:Proc of the 8th Annual Conference on Uncertainty in Arti-ficial Intelligence.California:Stanford, 1992:92—97

加权朴素贝叶斯篇5

性能预测根据其目的、对象和时间的不同通常有两种含义。第一种是指软件开发过程中,通过对架构的分析,预测软件完成后的性能表现,目的在于寻找最优化的软件架构方法以保证软件质量[1];另一种是指软件使用过程中,通过对参数、环境的分析,预测任务的响应时间等性能表现,使用户或系统可以根据预测结果对工作安排作出更好的决策。后者在大型报表、网格计算等运算量大、运行时间长的系统中具有深远的意义[2],这也是本文的研究方向。

1 相关工作

当前,软件使用过程中的性能预测方法主要有两类:一类是通过硬编码,将计算工作时间的代码直接写入相关功能模块。这也是很多现有软件的做法。但是这种方法灵活性差,难以适应不同的环境配置,且对于结构复杂的遗留系统,修改代码的代价大、风险高;另一类是通过对历史数据的分析,为当前应用系统做出性能预测。如文献[3]提出了基于多元线形回归的性能预测方法;文献[4]等提出了基于相似操作确认的性能预测方法;文献[5]等提出了基于累积分布函数和概率密度函数的性能预测方法。这些方法可以成功解决环境配置变化问题,同时实现预测模块的松耦合。但是在高维情况下有些算法会出现效率问题,且对噪音数据和不完整数据的适应性较差。

鉴于此,本文提出了一种基于朴素贝叶斯分类的性能预测方法。该方法使用性能测试的结果集作为训练集,利用朴素贝叶斯分类算法进行学习训练,最后将分类器包装为预测模块,嵌入到已有系统中对未来操作进行性能预测。该方法既实现了系统的松耦合,又具有构建简单、计算快速的特点,还可以很好地适用于高维情况及不完整数据[6],同时也具有较强的抗噪能力。

2 朴素贝叶斯分类算法

分类是机器学习和数据挖掘的一种重要方法。在分类中,训练的目的是通过带有类标号的一组训练样本构建分类器[7]。贝叶斯分类是一种基于概率统计知识的分类算法。根据实现方式不同可分为朴素贝叶斯分类和贝叶斯信念网络[8]等。朴素贝叶斯分类算法是在假设属性之间相互独立的前提下,设计的一种简单高效的分类方法,常被应用于文本处理、医疗诊断、系统性能管理等诸多领域[9,10,11]。

2.1 贝叶斯定理

假设数据样本X类标号未知,H为某种假定,P(H|X)则为条件X下H成立的后验概率。贝叶斯法则根据假设的先验概率和给定假设下观测到不同数据的条件概率,提供了一种计算后验概率的方法:

$Ρ (Η / X) = \frac{Ρ (X | Η) Ρ (Η)}{Ρ (X)} (1)$

其中P(X|H)为H成立时X的条件概率,P(H)为先验概率。

2.2 朴素贝叶斯分类

如果把每个数据样本X用一个n维向量{x1,x2,…,xn}表示,假定有m个类标号C1,C2,…,Cm。那分类问题可以转化为寻找使P(Ci|X)最大的类标号Ci的过程。即确定类标号Ci,使得:

P(Ci|X)>P(Cj|X) 1≤j≤m i≠j (2)

在任何情况下成立。

根据贝叶斯定理有:

$Ρ (C_{i} | X) = \frac{Ρ (X | C_{i}) Ρ (C_{i})}{Ρ (X)} (3)$

P(X)对于所有类是常量,故而要想最大化P(Ci|X),只需最大化P(X|Ci)P(Ci)。

先验概率P(Ci)由训练样本可以直接得出:

$Ρ (C_{i}) = \frac{S_{C_{i}}}{S} (4)$

其中SCi表示类标号为Ci的训练样本个数,S为训练样本总数。

关于条件概率P(X|Ci),朴素贝叶斯算法假设样本X的n个属性对分类结果的影响是独立的,不存在依赖关系,因此有:

$Ρ (X | C_{i}) = \prod_{k = 1}^{n} Ρ (x_{k} | C_{i}) (5)$

其中P(xk|Ci)表示类标号为Ci的样本中,X的第k个属性取值为xk的概率。如果此属性为分类型属性,则:

$Ρ (x_{k} | C_{i}) = \frac{S_{i k}}{S_{i}} (6)$

其中Sik表示在类标号为Ci的训练样本中,第k个属性取值为xk的样本个数,Si表示类标号为Ci的训练样本数。

如果此属性为连续型属性,则通常假设该属性服从高斯分布,利用高斯函数计算如下:

$Ρ (x_{k} | C_{i}) = \frac{1}{\sqrt{2 π σ_{C_{i}}}} e^{\frac{(x_{k} - μ_{C_{i}})^{2}}{2 σ_{C_{i}}^{2}}} (7)$

另外也可以将连续型属性转换为分类型属性,统一使用式(6)进行计算。

至此可求出各个类的先验概率P(Ci)和条件概率P(X|Ci)。

朴素贝叶斯算法通过独立性假设,将高维问题转换成多个一维问题,降低了计算复杂度。是目前公认的一种简单而有效的概率分类方法。其性能可与基于规则的分类、决策树和神经网络等方法相媲美[8]。

3 构建性能预测模块

建立性能预测模块的过程可以分为三个阶段:

(1) 通过性能测试获取训练数据集;

(2) 使用朴素贝叶斯算法通过训练集生成分类器;

(3) 使用分类器进行性能预测。

数据采集工作作为分类器训练的前提,具有重要地位。为了得到准确的预测结果,真实的训练数据必不可少。本文通过一种集成化的性能测试过程,在实现传统性能测试功能的同时,得到性能预测模块所需的训练数据。

3.1 环境变量及性能因子

在性能测试开始之前,首先要模拟一个真实稳定的测试环境,确定必须的环境变量。如网络通信协议、CPU频率、内存分配情况等。接着确定预测模块涉及的影响性能表现的样本属性(影响因子)有哪些,如访问方式、并发数、计算量、数据量等,这里用n维向量X(x1,x2,…,xn)来表示。最后确定性能测试关注的结果属性(表现因子)有哪些,如平均响应时间、系统吞吐量、CPU利用率等,用q维向量Y(y1, y2, … , yq)来表示。这样,性能测试便可以抽象为寻求向量X到向量Y映射关系的过程。

3.2 测试用例

创建测试用例最重要的是确定X向量各属性的取值规律。由于性能预测模块是基于贝叶斯分类算法进行训练的,为了达到更高的预测准确度,算法本身要求训练数据的先验概率及条件概率应尽量真实准确。也就是说为了确保向量Y中表现因子的概率分布符合实际情况,创建测试用例的时候必须保证X各属性的取值规律贴近于真实。

为了达到上述要求,在创建测试用例的时候,性能影响因子的分布情况应尽量在当前系统或类似系统中抽样获得,再生成同比例的性能测试用例。对于新系统以及无法在实际环境中采样的系统,则应根据领域知识确定性能影响因子所服从的概率分布情况。然后编写脚本以各属性概率分布情况为依据随机组合生成测试用例。

3.3 测试过程

当测试用例创建完成之后,通过自动化测试脚本,完成各个用例的测试,并记录测试结果。

在这个过程中通常需要以下几方面的工作:

(1) 使用测试工具实现用户并发访问、脚本录制等功能。

(2) 编写控制脚本实现数据量、计算量等专业领域方面的参数变化。

(3) 实现测试过程自动化。

(4) 使用系统监控工具记录向量Y中各属性的反馈情况。

3.4 分类器训练

测试结束之后,得到N组由向量X到向量Y的映射:

X1(x11,x21,…,xn1) → Y1(y11, y21, … , yq1)

X2(x12,x22,…,xn2) → Y2(y12, y22, … , yq2)

……

XN(x1N,x2N,…,xnN) → YN(y1N, y2N, … , yqN)

训练之前,要对测试结果做一些转化与处理。具体如下:

对于X中的连续型属性,鉴于其条件概率分布不服从高斯分布,本文采用类型转换的方式来处理。即将向量X中的连续型性能影响因子全部转化为分级类型。以属性xj(1<=j<=n)为例,假设xj为取值范围1-100的连续型数据,转换为分级类型后,则成为以100/r为长度的r个区间,区间标号分别为 aj1,aj2,…,ajr。

对于向量Y,鉴于其类标号无法直接划分,训练时要先将向量Y拆分成q个标量,对每个标量属性分别训练分类器,预测时先根据各自的分类器独立预测,再将各因子的预测结果综合为最终结果Y。

将向量Y拆分后,需要确定各个表现因子的分类粒度。粒度越小,计算复杂度越高。鉴于各表现因子训练过程及预测方法大致相同且相互独立,下文就以yp(1<=p<=q)为例展开阐述。设属性yp分为m类C1,C2,…Cm。

数据处理完成,先根据朴素贝叶斯算法中的公式(4),计算出yp所有类标号的先验概率P(Ci),如表1所示。

再根据式(5)和式(6) 计算各类标号条件下,X的每个属性各种取值的概率P(xj=ajk|Ci),如表2所示。

Ci表示表现因子yp的第i个类标号,xj表示样本X的第j个属性,ajk表示属性xj的第k种取值,P(xj=ajk|Ci)表示类标号为Ci的样本中,X的第j个属性取值为ajk的概率。

最后,将两张表中的所有信息记录于数据库中作为分类依据,供预测算法查询。

3.5 预测算法

分类器训练结束,封装分类器,将预测接口提供给应用程序,这样用户发出请求之后,将首先调用性能预测模块获取预测值,然后再执行请求的任务。

性能预测模块工作过程如下:

(1) 收集样本X(x1,x2,…,xn)中各影响因子的取值;

(2) 根据式(3)和式(5),计算样本X对于各个类标号Ci的条件概率与先验概率之积;

(3) 根据式(2),将拥有最大后验概率的类标号Ci作为性能预测的结果返回给用户。

预测过程的算法如下:

预测算法对每个类标号Ci首先从数据库中取出先验概率P(Ci),随后从数据库中取出所有属性对Ci的条件概率并求积得到P(X|Ci),最后在所有类标号中找到P(Ci)与P(X|Ci)乘积最大的作为输出。算法的时间复杂度为O(|C|*|X|),在分类数|C|不变的情况下,随着维数|X|的增大,算法的开销以|C|为单位线性增加,可见该算法在处理高维问题上具有优势。

yp预测结束后,以同样的方法,预测出所有表现因子的类标号,组合得到的向量Y即为最终预测结果。

3.6 自动更新

系统添加了性能预测模块之后,模块本身会持续记录用户使用过程中的性能表现作为下一阶段的训练数据,并定期使用新的训练集生成分类器。这样,性能预测模块通过保持训练数据的时效性,保证了性能预测的准确性。

4 实验

本文使用某投资银行的税务辅助决策系统进行实验,首先使用本文方法对测试集进行预测,然后使用SPSS[13]中的多元线性回归方法进行预测。最后将两组结果进行对比,以验证本文方法在准确性和效率上的优势。

实验使用一个真实的金融服务系统,可以帮助基金管理人储存和查询基金交易及持有状况,并根据税法相关规定,通过计算税务数据,辅助管理人做出交易决策。该系统数据量大,每月生成报表时的附加计算量也非常大,响应时间通常在半小时以上。本文正是针对这一功能,进行预测模块的对比实验。

4.1 环境准备

鉴于该系统使用PL/SQL在数据库层面实现主要业务逻辑,性能主要受数据库环境配置影响,故而测试环境应重点保证数据库服务器环境参数与真实环境接近。配置具体如下:

(1) CPU频率:7 * 1.5GHz;

(2) 数据库共享内存池: 369M;

(3) 数据库缓存: 5200M。

4.2 属性确定及用例准备

性能测试准备阶段的主要任务是确定要研究的性能影响因子和它们所服从的概率分布情况,并根据分布生成测试用例。

对于实验系统,所关注的性能影响因子主要有以下几项:

(1) 当前数据量描述主要涉及的数据库表中当前数据量的总和,该参数将直接影响查询效率。

(2) 并发用户数同时访问数据库的用户数,该参数通过对数据库造成的并发查询压力影响性能表现。

(3) 数据密度描述查询时间段内每日交易次数的多少,直接决定了计算复杂度,影响性能。

(4) 报表时段长短描述用户要生成的报表的时间区间,在同等数据密度下,时间越长,数据越多,计算也就越复杂,响应时间越长。

接着需要确定预测的对象,即性能表现因子。由于本文方法中各性能表现因子之间的训练和预测是独立进行的,为了便于分析,本实验只选取响应时间这一项属性作为表现因子。

确定研究的属性之后,通过对系统一段时间内的抽样情况,确定各个属性所服从的概率分布,之后将连续型属性转换为分级属性,如表3所示。

最后,将四个属性在符合各自概率分布的前提下,通过随机组合生成100组测试用例。

4.3 性能测试

通过编写PL/SQL脚本,实现当前数据量和数据密度的变化;通过使用自动化测试工具录制脚本实现多用户的并发;通过改变输入参数控制报表时段长短,最后编写测试代码完成这100组样本的测试过程,记录每组用例的响应时间如表4所示。

4.4 分类器训练

随机抽取其中的80组作为训练集,剩余20组作为测试集。将响应时间从0开始以10分钟为粒度分作12类。根据3.4节的方法用训练集中的80组数据进行分类器训练,得到先验概率表和条件概率表作为结果,完成训练。与SPSS中的多元线形回归方法相比,朴素贝叶斯算法在训练过程的效率上体现出明显的优势。

4.5 预测结果及对比

训练结束后,使用剩余20组实验数据检验训练效果。利用3.5节所述的算法对20组样本进行响应时间预测。并将预测结果与多元线性回归法预测结果及实际结果进行对比,如表5所示。

由实验结果得知,在分类粒度为10分钟的情况下,本文方法得到的预测区间包含实际结果的占65%,预测区间在实际结果临近区间的占25%,预测区间偏离较远的占10%。多元线性回归法的预测结果误差在10分钟之内的占60%,10-15分钟的占20%,偏离较大的占20%。将两组结果进行对比,可以发现本文方法在准确率上优于回归算法。主要原因有两点:一是系统在大负载情况下的性能变化很难用线性变化来拟合;二是朴素贝叶斯算法的抗噪能力要优于多元线性回归方法。

5 结论

本文将机器学习的理论应用于软件性能预测,提出了一种基于朴素贝叶斯分类的性能预测方法,与传统预测方法相比,具有构建方便、计算快速、鲁棒性强、松耦合、抗噪能力强等优势。在以后的工作中,将继续加强对预测算法的优化,进一步探索更好的分类模型。

摘要：基于朴素贝叶斯分类提出了一种复杂应用系统的性能预测方法。利用应用系统性能测试的结果作为训练集,引入朴素贝叶斯分类方法训练分类器,再将该分类器包装成预测模块嵌入应用系统,对响应时间等多种性能属性进行预测。与传统方法相比,该方法具有准确度高、构造简单、效率高、鲁棒性强、松耦合等优势。在针对金融报表系统的对比实验中准确率达到65%以上,训练过程的时间开销也明显少于传统方法。

加权朴素贝叶斯篇6

信息检索被认为是Web文本挖掘的前身,但是位于Internet上的信息,一方面规模巨大,并且缺乏结构化,对于这些非结构化或半结构化的复杂的Web数据,在做文本分类之前,还需要对获取的文本进行特征提取和表示,然后再使用文本分类技术进行快速、自动的分类。

本文主要分析和讨论了基于朴素贝叶斯(Naïve Bayesian)方法的Web文本分类的相关理论,并使用中文自然语言理解平台[1]上的文本分类语料库,进行具体的实验分析。

1 Web文本分类方法

1.1 Web文本分类概述

文本分类是在预定义的分类体系下,根据文本的特征,将给定文本归类的过程,而文本的特征涉及对文本的理解,因此涉及众多的学科领域。Sebastiani用下面的数学模型描述文本分类。

定义函数Φ:D×C→{T,F},其中D={d1,d1,⋯,d|D|}表示待分类的文本文档,C={c1,c1,⋯,c|C|}为预定义分类体系下的指标集。设T和F值表示为二元组<dj,ci>,分别表示文本dj属于类ci和文本dj不属于类ci。在文本分类中涉及两个最重要的问题:文本表示与分类器设计。那么对于来自网络的Web文本分类系统可以简单地表示为图1。

1.2 Web文本表示

Web文本和其他文本类似,由文字、词语和标点符号组成,要使用计算机来表示文本,首先需要选择一种好的表示方式,并且要求该表示方法能尽可能准确地反映文本的主题、内容和结构等。

当前比较常见的表示方法是由G.Salton等人于60年代末提出的向量空间模型(VSM)。在VSM中,用由特征二元组组成的特征向量表示文本dj,记为dj={(t1,ω1j),(t2,ω2j),…,(ts,ωsj)},其中(tk,ωkj),1≤k≤s表示特征tk的二元组,ωkj表示文本dj中特征tk的权重,s为特征集合的大小。那么对文本的比较、分类等操作就可以转换成特征向量组间的操作,使问题变得简单且易于实现。

1.3 Web文本特征选择及特征权重计算方法

使用VSM模型对Web文本进行文本表示,得到的特征向量维数一般会非常高,为提高性能,需要对特征向量进行特征选择以降维,那么面临的问题是,应该选择哪些特征,以及应该赋予这些特征多大的权重,以希望经约简的特征向量更好地体现文本的内容、主题等?当前比较常见的方法有:信息增益(IG)、卡方、文档频度(DF)、互信息(MI)、特征强度(TS)等。本文主要使用文档频度的方法进行讨论,该方法是最基本且最简单的一种方法,统计在多个文档中出现特征tk的次数,次数越多的特征被认为越关键,故被保留。

文本特征权重的计算方法常见的有布尔权值、绝对词频(TF)、倒排文档频度(IDF)、TF.IDF权值、熵权值等,本文使用绝对词频tfij衡量文本特征权重。

对于Web文本,在文本表示之前,需要对文本进行分词。分词之后的文本词表中包含很多对文本特征表示无意义的词,还需要对其进行约简,去除虚词、数量词等不能体现文本特征的词。而对于重复出现的词,会有两种情况:一种是通用的名词、动词,不具特征性,应去掉;第二种是恰好能反映文本的特征的词,应该保留,并且统计记录其频数,用VSM模型进行表示。然后再使用文本特征选择及特征权重计算方法对建立的VSM模型进行优化,得到结构化的数据,为下一步分类做好准备。

2 贝叶斯分类算法基本理论

贝叶斯分类算法是基于统计学的方法,可以预测类成员关系的可能性。实践表明贝叶斯分类算法有非常高的准确率并且计算速度较快。贝叶斯分类算法基于概率论中的著名的贝叶斯定理[2]。

定理1设样本空间S,n个互斥事件成为S的一个划分:S={A1,A2,…,An},AiAj=0,i≠j,X是S中任意一个事件,则有:

设D是训练元组集(包含类标号),其中的元组用n维向量X=(x1,x2,…,xn)表示,属性集记为DA={A1,A2,…,An}。设有J个类C1,C2,…,CJ,根据贝叶斯定理,分类算法将预测给定元组X属于的类。分别计算后验概率P(Ci|X),找到最大值,其中先验概率P(Ci)通过学习训练元组得到,考虑到P(X|Ci)的计算是复杂并且开销非常大的,故做了类条件独立的朴素假设,即是

该分类算法被称为朴素贝叶斯分类[3](NBC)。

2.1 Web文本分类数据的预处理

为实验的方便,使用中文自然语言理解平台[1]由复旦大学提供的文本分类语料库,包含有财经、科技、教育、电脑、房产、人才、汽车、体育、卫生、娱乐10个类别共951个文本。对所有的951个文本的每个文本分词,分别生成相应的文本词表,如图2所示。

然后进行去词约简,去除虚词、数量词等不能体现特征的词,去除那些不具有特征性但却重复出现的通用的名词、动词,记录反映文本特征的词及词频,每个文本可以表示成一条VSM模型元组,最终所有的文本处理完成后生成一个矩阵,称为词频矩阵,最后一列加上类属性,本实验词频矩阵是951×13353,如表1所示。再进行降维处理,最终的词频矩阵部分如表2所示。

3 应用实验

3.1 Web文本分类

为使用贝叶斯算法对文本分类,首先对词频矩阵进行离散化处理,离散化规则如表3所示。

最后,对表2的词频矩阵D951×252进行数据离散化处理的结果如表4所示。

实验的硬件平台:Pentium E2160 1.8GHz处理器,1G内存;开发环境:Visual Studio 2005,使用盘古分词[4]的C#开源代码。使用朴素贝叶斯算法进行学习、分类,实验结果如表5所示。实验表明,对非训练数据的分类准确性不高,这说明该数据集的高稀疏性会使所构建的分类器的泛化能力还不够好,还有待提高。

4 结论

针对来自网络的Web本文,使用基于朴素贝叶斯的分类算法对其进行自动分类,本文做了如下工作:1)概述了Web文本分类的相关方法以及贝叶斯分类理论;2)通过具体的实验,给出了Web文本分类的详细过程,包括分词、约简、降维、训练、分类等,实验结果较好;3)针对高维稀疏数据的非训练数据分类效果还不够理想,还有待进一步研究。

参考文献

[1]中文自然语言理解平台[DB/OL].http://www.nlp.org.cn/

[2]李贤平.概率论基础[M].北京:高等教育出版社,1997.

[3]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].范明,孟小峰译.北京:机械工业出版社,2007:201-206.

[4]盘古分词开源代码[CP/OL].http://pangusegment.codeplex.com。

[5]郑庆华,刘均,田锋,等.web知识挖掘:理论、方法与应用[M].2010:3-5.

[6]包小兵,翟素兰,程兰兰.基于信息熵加权的局部离群点检测算法[J].计算机技术与发展,2012(7).

加权朴素贝叶斯篇7

1.1 Android系统

Android一词的本义指“机器人”,也是一款基于Linux内核的开源手机操作系统,该系统由精简的Linux内核作底层管理、各种开源的功能库作中间件、基于Dalvik虚拟机的Java应用程序框架和一组基本的应用软件组成,是首个为移动终端打造的真正开放和完整的系统平台[1]。

Android系统自2007年首次发布以来,以其开源免费的优势,至今,经过多次系统升级,已经成为全球最流行的手机,占有率已超60%。与此同时,据网秦2012年第一季度的《全球手机安全报告》[2]指出“2012年第一季度查杀到的Android手机恶意软件3523款,直接感染手机412万部”,并且仍有上升趋势。所以,在Android移动设备迅速普及的今天,开展Android安全性研究势在必行,检测Android恶意软件研究具有重要意义。

Android系统采用软件堆层(Software Stack,又名软件叠层)的架构,主要分为三部分。底层以Linux内核工作为基础,提供核心系统服务,比如安全,内存管理,进程管理,网络协议栈和驱动模块;中间层包括各种开源函数库Library和虚拟机Virtual Machine。第三层是各种应用基本框架,主要是由各种组件管理器级成,提供Android程序开发的基础功能,使组件重用变得简单,加快了程序开发的速度。最上面一层是常用的必要的应用程序,包括通话程序,短信程序等,应用软件可由第三方开发。每个Android应用都运行在它自己的进程里,并依附在一个单独的Dalvik虚拟机实例上[3],一个设备可以高效地运行多个Dalvik虚拟机。

1.2 Android的安全机制

Android安全机制的一个重要的设计出发点就是:应用程序在默认的情况下不可以执行任何对其他应用程序、系统或者用户带来负面影响的操作。除了Linux在系统内核级来做保障,在外围用户空间android也设计了独特的安全机制来保障程序的安全性[4]。

1)Android系统充分利用了Linux系统的安全特点,一个程序分配一个用户ID,每个程序运行在自己的沙箱环境,之间不能相互影响。

每个程序在安装时,系统会为它分配一个属于自己的用户,为它创建一个“沙箱”环境,防止其它程序影响。用户在程序安装到手机中时被分配,并且在这个设备中保持它的永久性。另外如果该程序创建任何文件都会被赋予程序的用户标识,并且正常情况下不能被其它进程访问。

2)另外,Android系统设计了另一个安全特性,即权限控制[5,6]。每个程序要想使用系统的资源,必须在在程序的声明文件中明确的声明,在安装时向用户提示。如果有敏感权限用户可拒绝安装。

一个程序在安装时,需要声明自己需要的权限给用户提示,包括如访问联系人、访问网络、访问电电子邮件、收发送信息、读写存储卡,调用Android其他组件等。如果有恶意权限会被细心的用户发现,并且程序在实际运行期间,不可能有超出安装时声明的权限。权限是Android为保障安全而设计的安全标识,同时也是程序实现某些操作的前提。

存在的问题是,用户选择安装了某个程序,就不得不接受该程序的所有权限,而一般的普通用户却不熟悉,这些权限可能给自己带来的危害。另外,用户往往更关心程序带来的功能,而忽视了程序所具有权限带来的潜在威胁。在安装了这样的恶意程序后,在运行过程中便可访问用户的隐私数据或执行非法的动作,而用户不会知晓,从中给用户带来威胁。

1.3 相关研究

文献[7]使用自动测试工具,测试了1310个关键Android API,创建了较为完整的Android权限集合(permission map),包括了contend Providers,Disallowed Broadcasts,receving Broadcasts,sending Broadcast,startin-g Activities,starting Services几乎所有种类的权限。

文献[8]分析了2011年10月前1260个良性程序的权限使用情况,同时与他们收集的恶意程序库中恶意程序所申请的权限的情况,进行了对比发现:访问网络、读手机状态、访问网络状态、写SD卡等权限在恶意程序和良性程序中都广泛使用,但恶意程序倾向于使用(:)短信有关的权限(62.7%)、开机自启动权限(54.6%)、更改WIFI状态的权限(31.6%),而良性程序很少使用这些程序。另外,恶意程序比良性程序倾向于请求更多的权限,在他们收集的样本中,恶意程序平均需要11个,而良性程度需要4个。在前20名的权限中,恶意程序平均需要9个,而良性程序平均仅需要3个。

由上,可以推断出,恶意程序与良性程序在需要的请求的权限集合与组合上,有比较明显的不同。

2 朴素贝叶斯算法与恶意软件检测模型

根据前文所述及相关研究,笔者认为可以运用机器学习方法以权限组合为特征对Android恶意软件进行检测。在机器学习方法中,朴素贝叶斯方法(Naive Bayes,NB),是一种性能较好的分类方法,常用在文本分类上[9],研究对比后发现其模型特征上与Android程序的权限上有一定相似性。

2.1 算法描述

NB利用贝叶斯公式的特性,将先验概率转换成后验概率,并为了简化问题处理,采取了“朴素的假设”。它分类新实例的方法是在给定描述实例时,通过计算概率得到最可能的分类目标值。

2.1.1 定义极大后验假设(maximum a posteriori,MAP)

vMAP——最可能的分类,V——目标属性取值集合(此处为{0,1}),vj——目标属性(j)的取值,a1,a2,……an——样例的特征属性

2.1.2 算法描述

1)在(1)式中,估计P(vj)只需要计算每个目标值出现在训练样例中的频率即可,

2)P(a1,a2...an|vj)必须要一个非常大的样例空间才可以,但这不现实。基于一个简单的假定:若在给定目标值时属性间相互独立,有P(a1,a2...an|vj)=∏iP(ai|vj)(文献[10]从数学上说明了NB假设的合理性以及NB能取得不错分类结果的原因)。P(ai|vj)项也可根据训练数据上出现的频率得出。代入上式:

3)估计——类别vj的样例数,nc(ai,vj)——类别vj的样例中属性ai取某一值的样例数目。但当在样例中,某个属性的属性值没有出现时,便会出现问题,即估计的概率为0,会使之后的类别概率变为0,影响判别。改进为:p——要确定概率的先验估计,m——等效样本大小的常量,确定对观察到的数据如何衡量p的作用[11]。一般取m为k(ai可能属性值的个数)即假设每个属性值在类别vi中都出现了一次。

2.2 建模

主要的问题是,把一定数量的良性程序与恶意程序的权限扫描统计出来,计算其概率。以[7]中总结出的所有权限作为权限字典D,作为特征属性。

1)从官方的Android市场[12]下载的一定数量程序(官方审核相对比较严格,假设全为良性程序),得到各程序权限,集合到一起,并对各权限计数,记作B={,……}。

2)笔者收集了一批恶意程序样本,得到各程序权限,集合到一起,同(1)一样,对各权限计数。

3)记T=B+M T={,……}

4)对应到该分类的具体问题中,2.1.2中的“样例”应为具体权限。

1——代表是良性程序B0——代表是恶意程序M

nc(vj=1)——B样本数量中各权限总数nc(vj=0)——M样本数量中各权限总数

n——T总样本数量各权限总数

nc(ai,vj)——在vj类样本中,出现ai权限的次数,可由(1)(2)中得到。

|D|——权限字典中的权限数量

5)在以上概率全部计算出来之后就可以预测新样本:

vMAP=argvj∈mVaxP(vj)∏iP(ai|vj),得到最可能的分类预测。

3 模拟实验

1)样本取得:从Google官方的Android市场下载200个程序(官方审核相对比较严格,假设全为良性程序)。包括了游戏娱乐类、工具类、系统管理类等程序。恶意样本,来自笔者的收集,取200个,包括了一些主流恶意的程序,如:Droid Kung Fu,AnverseBot,Base Bridge,Root Expoit等。

2)权限提取:基于开源项目androgurad[13],编写了一个自动读取一个目录下所有程序权限并统计每个权限数量的工具,会将统计信息写出保存到文件。

3)用python语言实现了NB算法,按前文中的计算方式,计算相应的概率项。

4)先随机选取参与训练的良性程序和恶意程序各50个进行分类实验,再选择未参与训练的新样本进行检测,进行五轮实验。实验结果如下:

其中,

TP——true positive真阳性,即检测正确到恶意样本数量

FN——false negative假阴性,即检测错误的恶意样本数量

TPR——真阳率表征了一种命中率(检测率)

FP——false positive假阳性,即检测错误的良性样本数量

TN——true negative真阴性,即检测正确的良性样本数量

FPR——假阳率表征了一种错误命中率(误报率)

ACC——准确率

实验结果分析,由以上模拟实验可以看出,训练样本的分类效果相对较好,对新样本具有一定的检测能力,但不是特别理想。原因是样本数量偏少,检测方式单一,另外如果能按软件的分类如游戏娱乐、工具、系统管理等来进行检测效果会更好,因为不同类型的软件所需要的权限集合与组合也有不同。

4 总结

本文介绍了Android系统的架构,分析了Android系统的安全机机制。针对Android特有的安全机制,提出一种利用机器学习算法检测恶意软件的方法,并进行了模拟实验和分析,效果较好。今后,笔者将继续对Android系统的恶意软件检测进行研究,具体涉及如增加样本数量的训练;将检测模型移植到Android平台上;研究恶意的软件的除权限外的其他静态特征;研究恶意软件的运行时特征,hook Android的敏感API,建立恶意软件的行为模式;寻找合适的机器学习算法,使模型具有更好的学习并检测新样本的能力。

摘要：在今天开源的android手机越来越流行的同时,也有越来越多的木马、广告、隐私偷窥、扣费等恶意软件的出现困扰着用户。该文首先介绍了Android系统的构成,分析了android系统的安全机制和存在的安全隐患,并就关键的权限机制的相关研究进行了综述。文章提出利用机器学习中的朴素贝叶斯分类算法,对程序的权限进行建模分类检测,并进行了模拟实验。

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【加权朴素贝叶斯】相关文章：

朴素的爱情观04-07

朴素的爱作文05-11