贝叶斯分类范文-盘古文库

贝叶斯分类范文（精选7篇）

贝叶斯分类第1篇

上世纪九十年代以来, 计算机和信息技术发展迅速, 各类信息以级数倍的速度在Internet上广泛传播, 尤其是种类繁多的文本信息。因此如何在众多文本中掌握最有效的信息始终是信息处理的目标。基于人工智能技术的文本分类系统能依据文本的语义将大量的文本自动分门别类, 从而帮助人们更好地把握文本信息。近年来, 文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合, 有效地提高了信息服务的质量。

贝叶斯分类器是基于贝叶斯学习方法的分类器, 其原理虽然较简单, 但是其在实际应用中很成功。贝叶斯模型中的朴素贝叶斯算法有一个很重要的假设, 即属性间的条件独立。

(二) 贝叶斯相关理论

1. 条件概率

条件概率定义为:设A, B是两个事件, 且P (A) >0称为在条件A下发生的条件事件B发生的条件概率。

乘法公式:设P (A) >0则有P (AB) =P (B|A) P (A) 。

2. 全概率公式和贝叶斯公式

设S为试验E的样本空间, 为E的一组事件, 若则称为样本空间的一个划分。

全概率公式定义为:设试验E的样本空间为A, A为E的事件, B1, B 2, ....Bn为A的一个划分, 且, 则。

贝叶斯公式定义为:设试验E的样本空间为A, A为E的事件, 为A的一个划分, 则。

其中i, j均为下标, 求和均是1到n。

(三) 贝叶斯分类器设计

贝叶斯文本分类模型是一种典型的基于统计方法的分类模型, 它利用先验信息和样本数据信息来确定事件的后验概率。

1. 贝叶斯分类描述

根据贝叶斯公式:

可知贝叶斯文本分类的任务是将表示成为向量的待分类文本归类到与其关联最为紧密的类别中去。其中为待分类文本Xq的特征向量, 为给定的类别体系。求解向量属于给定类别的概率值, 其中pj为属于Cj的概率, 则max所对应的类别为文本X所属的类别, 因此分类问题被描述为求解方程 (2) 式的最大值。

其中训练文本集中, 文本属于类别cj的概率;如果待分类文本属于类别cj, 则类别cj中包含向量的概率;给定的所有类别的联合概率。

显然, 对于给定的所有类别, 分母是一个常数, 所以求解 (2) 式的最大值转化为求解下式的最大值, 即

又根据贝叶斯假设, 文本特征向量属性x1, x2, ......xn独立同分布, 其联合概率分布等于各个属性特征概率分布的乘积, 即

所以 (3) 式变为:

即为所求解的用以分类的分类函数。

尽管推导出了分类函数, 但是分类函数中的概率值还是未知的, 因此, 为了计算分类函数的最大值, (5) 式中的先验概率值分别估算如下。

其中, 训练文本中属于cj类别的文本数量;N训练文本集总数量。

其中, 类别cj中包含属性xi的训练文本数量;N (C=cj) 类别中的训练文本数量;M训练文本集合中经过踢出无用词去除文本预处理之后关键字的数量。

2. 朴素贝叶斯分类器算法

朴素贝叶斯分类器算法假定各待分类文本特征向量相互独立。相互独立表明所有特征向量之间的表述没有关联, 有利于计算。以下为朴素贝叶斯分类器算法步骤。

(1) 待分类文本利用分词工具形成待分类文本特征向量, 利用常用词向量净化待分类文本特征向量, 使其消除冗余和常用词, 形成新的待分类文本特征向量。

(2) 通过对属性在C1类训练文本集中进行查找, 计算出属性在C1类训练文本集中出现的次数集属性分别除以C1类训练集总文本数和训练文本集中经过踢出无用词去除文本预处理之后关键字的数量之和, 得到在C1类训练文本中出现的概率集。把中的属性相乘得到在C1类训练文本集中出现的先验概率P (x|c1) 。

(3) C1类训练文本集中的文件数量除以整个训练文本集的总数得到先验概率得到在C1类训练文本集中的后验概率。

(4) 重复2、3步骤计算出所有类别的后验概率。

(5) 根据步骤4得出的结果比较出最大的后验概率P (cj|x) , Cj类就是所属类别。

3. 朴素贝叶斯分类器

根据朴素贝叶斯分类器算法使用Java为开发语言, Tomcat为服务器, 采用B/S模型进行实现。以下是得到待分类文本向量后验概率的主要实现代码。

(四) 测试数据和实验结果

作为测试, 本文选用Sogou实验室的文本分类数据, 并使用了mini版本。迷你版本有10个类别, 共计100篇文章, 总大小244KB。

使用的测试文本:

东方网10月8日消息:华盛顿时报6日报道称, 中国最近秘密进行了一次远程导弹飞行试验。据中国军事专家称, 9月25日的试验再次凸显北京远程和近程弹道导弹、巡航导弹及新式导弹防御拦截弹所能够造成的威胁越来越大。

报道称, 一名美国官员证实, 中国军方从北京西南方约320英里处的太原导弹中心向西部约1800英里处的库尔勒市试射了一枚导弹。中国官方未提供详细信息, 称试验数据属于机密。

亚洲和美国的中国观察者于9月23日意识到了此次试射活动, 当时中国政府发布了“飞行通告”, 警告飞机在9月25日前远离从太原到库尔勒的空域通道。

使用mini版本的测试结果:

结果显示, 军事类别的后验概率为2.532662E-2, 是所有类别中最大的, 所以测试文章属于军事类别。最后经过400篇不同文章测试, 分类器分类结果正确率达到83%以上, 实现文本分类作用。

(五) 结语

通过贝叶斯算法实现文本分类, 是一种简单而有效的方法。根据测试的结果, 已基本实现简单文本分类。但是, 通过对大容量的文章测试, 会得到大量的分词单元, 严重的影响系统的处理能力, 使系统效率严重低下。

参考文献

[1]Tom M Mitchell.机器学习[M].曾华军, 等译.北京:机械工业出版社, 2003.

[2]梅馨, 刑桂芬.文本挖掘技术综述[J].河北大学学报, 2003, 24 (5) .

[3]韩家炜, 等.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.

[4]王灏, 黄厚宽, 田盛丰.文本分类实现技术[J].广西师范大学学报, 2003, 21 (s1) :173-179.

基于群的朴素贝叶斯分类第2篇

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

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

统计学家运用对称性对数据进行分析, 并且专门开发了一个研究方向:数据分析的对称性研究。对称性研究主要运用统计与代数分析复杂的结构性数据, 例如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的值;

基于贝叶斯分类的毒蘑菇识别第3篇

毒蘑菇也称毒覃、毒菌等,是指大型真菌的子实体被食用后对人类或动物产生中毒反应的种类[1]。我国各省市几乎每年都有毒蘑菇中毒致死的报告,所以研究毒蘑菇的中毒机理、识别方法以及预防和治疗毒蘑菇中毒等具有重大意义[2]。毒蘑菇的毒性有强有弱,有的虽然毒性比较弱,但是如果长时间食用,仍然会发生中毒[3]。毒性较强的一旦出现临床症状就为时已晚。对毒蘑菇的识别,人们在长期采集大型真菌的过程中积累了很多经验和方法[4]。随着真菌研究的兴起,对毒蘑菇的识别方法取得了较大成果。主要有以民间经验为基础的形态识别、化学分析、动物检验和分类学上认识毒蘑菇等方法。但是这些方法在实际应用中存在着准确度不高,对未知毒素检测不够理想,所需实验设备多,实验周期长等问题。基于传统毒蘑菇识别方法存在的不足,本文提出一种基于贝叶斯分类模型的毒蘑菇识别方法。通过对毒蘑菇历史数据特征的学习,可以较为准确地识别未知有毒蘑菇。通过实验证明准确率达到98%以上。

1传统毒蘑菇识别方法

1.1民间经验识别

长期以来,人们在采摘蘑菇中总结了大量经验,总结了很多鉴别毒蘑菇的方法。一般分为通过观察蘑菇的外形特征,如菌盖上的刺菌柄菌环。如但是有些蘑菇没有上述特征却是有毒的,如裂丝盖伞并没有上述特征,但是毒性很强。还有通过对蘑菇颜色的识别来判断蘑菇的毒性。如有的蘑菇颜色鲜艳,特别是紫色常有剧毒,如毒红菇,但也有例外,如白毒伞颜色为纯白色,形状也不奇特,但确实是有毒的。这些方法虽然在识别比较简单,但准确率较低,每年中毒事件就说明了这个问题,所以不能作为鉴别毒蘑菇的可靠方法[5]。

1.2化学检测

化学检测一般包括汁液显色法、简单层析法、液相色谱法,文献[6]提出了利用浓盐酸处理蘑菇汁液可识别出含有毒伞肽或色胺类毒素的毒蘑菇。文献[7]提出利用不同毒素在层析液中有不同的Rf值,经层析分开后与显色剂反应,显示不同的颜色。文献[8]提出利用液相色谱法检测毒蘑菇所含毒素,根据波峰面积计算各种毒素的含量。但是液相色谱法需要相关的设备,同时一种蘑菇可能含有多种毒素成份,增加了检测难度。所以化学检测一般只局限于专业人员采用,并且化学检测在对未知毒素检测中,存在一定的局限。

1.3动物实验检测法

动物急性毒理实验,一次性给供试动物食用待测蘑菇,观察动物反应,根据食后症状判断有毒无毒[9]。动物实验法虽然比较安全可靠,但是耗费时间长所需材料较多,很难推广。

1.4真菌分类鉴定法

根据毒菌的生物学特性从分类学上认识毒蘑菇的种类,了解它的形态特征、生态习性,结合动物毒性试验加以鉴别,但是由于总结过程复杂,专业性强,推广难度很大。

在毒蘑菇识别中,传统的民间经验识别主要依据采集者的经验,事实证明这种方法准确度不高。化学检测对未知毒素的检测有一定的局限性,动物检测虽然可靠,但是耗费时间长,所需材料多,还受剂量和环境的限制。

2贝叶斯分类原理

贝叶斯分类算法具有构造简单,模型参数不需要任何复杂的迭代,可以适用于规模较大的数据集。此外,它容易解释,即便不是本专业的读者,也能够理解该方法,分类效果好[10]。

贝叶斯判别分类的基础是对分类历史特征的学习,历史数据常用先验概率的形式给出,当取得待测样本后,就可以用样本来修正已有的先验概率分布,得出后验概率分布,通过后验概率分布进行类别的分类[11]。

可以这样阐述贝叶斯原理,首先给出一些属性的定义:P(i|x)表示一个向量为X = (x1,…xn)的对象属于类别i的概率;f(x|i)表示x关于类别i的条件分布;P(i)为不清楚对象自身任何信息的时候该对象属于类别i的概率即类别i的先验概率f(x)为两个类别总的混合分布:f(x)=f(x)0)P(0)+f(x|1)P(1)。

贝叶斯方法的核心是对f(x|i)f的估计,贝叶斯方法假设x的每个分量都是相互独立的,所以有f(x|i)=∏Pj=1f(xj|i)。

举例说明叶斯工作原理。表1是一组蘑菇毒性和其特性的分类表(其中E表示可食用,P表示有毒)

取一个形状为Bell、颜色为Gray、生长地为Grasses的未知毒性蘑菇,根据贝叶斯分类原理可以用如下公式计算该蘑菇有毒和无毒的概率:

蘑菇有毒的概率:

蘑菇无毒的概率:

由上可知蘑菇有毒的概率大于无毒的概率,则判断该未知毒性蘑菇为有毒蘑菇。

3实验

3.1实验环境和实验数据

实验平台采用Cpu i3 2120主频3.3GHz,内存4GB,数据集采用UCI数据库中Mushroom Database,数据集包括8 124条大型真菌的23个特征属性。选取其中7 000条数据5个特征属性作为学习数据集,1 124条作为测试数据集。

注:第23个属性为有毒无毒

特征值选择为:

3.2检验算法有效性

检验算法的有效性分为两步

第一步:计算全部1 124条测试数据集的正确率,经计算得出准确率为98.48%

为了更准确地说明算法的准确率进行第二步实验。

第二步:对1124条测试数据随机抽样20次每次抽取250条数据,画出折线图,验证算法的正确率。

4结语

贝叶斯分类第4篇

随着因特网的迅猛发展,电子邮件正成为一种最快捷、最经济的通信手段。但电子邮件在成为一种信息交流工具的同时,也正在成为大量商业广告等无用信息的载体,这就需要用户花费大量时间和精力来处理这些所谓的“垃圾”邮件。如何对邮件中的拉圾邮件进行过滤是用户关心的一大问题,因此“反垃圾邮件”方法的研究是电子邮件处理中的重要课题。目前一些电子邮件系统已采取了一定的技术手段进行反垃圾邮件处理,但这些技术都存在一定的不足或技术上的不完善。因此,研究一种有效的反垃圾邮件系统具有十分重要的意义。

1 反垃圾邮件的形式

当前,反垃圾邮件的方法有服务器端和客户端两种。一般情况下,比较理想的方法是,在邮件服务器端直接将垃圾邮件屏蔽掉,这样不仅用户不会受到垃圾邮件的骚扰,而且服务器可以减少邮件的处理量,节约处理器资源和带宽流量。但是,相当多的电子邮件服务提供商特别是一些不够规范的免费电子邮件提供商并没有把这件事做好(有些免费的电子邮件服务提供商甚至向别的厂商和公司收取费用直接往自己的免费用户邮箱里投放广告邮件)。因此,在客户端进行垃圾邮件的过滤和处理就成为反垃圾邮件的唯一途径。防线上去抵挡垃圾邮件的进攻了。由于客户端对邮件的接收是被动的,不像服务器端,可以把一些邮件在没有投放到用户的邮箱目录之前就拒收掉。所以客户端对邮件必须全面接收。但是可以在邮件接收完成后进行邮件的识别和过滤,这也是守好最后一道防线的关键。一封电子邮件,从邮件分析的角度可以大致分为以下五部分:邮件头、发件人、收件人、邮件主题、邮件内容。客户端是一个被动接收的角色,还没有足够的权利去做其它的事情。因此只能采用过滤技术来摆脱垃圾邮件,通过对电子邮件在五个部分比较明显的标志位可以基本上确认这封邮件是不是垃圾邮件。

2 改进的贝叶斯过滤算法

不管是对什么内容进行过滤,都要有相应的技术支持。目前对垃圾邮件的过滤主要有黑名单、白名单、基于规则的过滤技术、Bayesian 过滤技术和神经网络技术等五种技术,这里主要对Bayesian过滤算法进行讨论,通过对传统的Bayesian过滤算法进行改进以期达到较好的筛选效果。

2.1 贝叶斯过滤算法

贝叶斯过滤技术是基于贝叶斯定理,贝叶斯过滤技术似乎与基于规则的过滤技术相似,但是贝叶斯过滤器不必预先设定规则,不需要分析邮件句法或内容含义。贝叶斯过滤器是用户根据自己所接受的垃圾邮件和非垃圾邮件的统计数据来创建的,这意味着垃圾邮件发送者无法猜测出过滤器是如何配置的,从而有效阻止垃圾邮件。贝叶斯过滤器能够学习分辨垃圾邮件与非邮件之间的差别,差别是用概率来表示的,并且自动应用到以后的检测中。在收到几百封信件后,一个好的贝叶斯过滤器就可以自动识别各种垃圾邮件。

贝叶斯定理:设X是类标号未知的数据样本。设H为某种假定,如数据样本X属于某特定的类C。对于分类问题,希望确定P(HX)给定观测数据样本X,假定H成立的概率。P(HX)称为后验概率或条件X下H 的后验概率。例如,假定数据样本域由水果组成,用它们的颜色和形状描述。假定X表示红色和圆的,H表示假定X是苹果,则P(HX)反映当看到X是红色并是圆的时候对X是苹果的确信程度。作为对比,P(H)是先验概率或H的先验概率。对于我们的例子,它是任意给定的数据样本为苹果的概率,而不管数据样本看上去如何。后验概率P(HX)比先验概率P(H)基于更多的信息(如背景知识)。P(H)是独立于X的。类似地,P(HX)是条件H下X的后验概率。即是说,已知X是苹果,那么X是红色的、圆的概率。P(X)是X的先验概率。使用本文的例子,它是由水果集取出的一个数据样本是红的和圆的概率。计算这些概率可以用贝叶斯定理来实现。贝叶斯定理是:undefined它提供了一种由P(X)、F(H)和P(XH)来计算后验概率P(XH)的方法并成为贝叶斯分类方法的基石。

贝叶斯定理更常用的表述为:设(Ω,ε,P)为概率空间,Ai∈ε(i=1,2,,n)为Ω的一个有穷部分且P(Ai)>0(i=1,2,,n),则对任意B∈ε且P(B)>0,有:

undefined

2.2 贝叶斯分类器的工作原理

贝叶斯分类器的工作包括设计和实现两个部分,设计是指用一定数量的样本(也称为训练集或学习集)进行分类器的设计;实现是指用所设计的分类器对待识别的样本进行分类。

贝叶斯分类器首先从训练集中学习得知给定类Ci下各属性(w1,w2,,wn)的条件概率值,然后用贝叶斯定理计算给定待识别样木d在各个类Ci的条件概率的值P(Cid),最后用最高后验概率值作出预测。贝叶斯分类器有两种不同的模型。下面详细地介绍这两种贝叶斯分类模型的工作原理。

2.2.1 一般贝叶斯模型

一般贝叶斯模型结构如图1所示,它包含一个表示类变量的结点C和表示类特征项的结点wi(i=1,2,,n),两个结点间有连线表示这两个变量不独立,否则表示两个结点间相对独立,即对于给定类变量C,若wi,wj相对读立,有P(wiC,wj)=P(wiC)。

给定一特征项为wi(i=1,2,,n)的样本d,它属于类Ck的贝叶斯公式为:

P(Ckd)=P(Ck)*P(dCk)/P(d) (2)

其中:

undefined

根据公式(2)可知,要判断待识别样本d属于哪个类别,可以计算概率P(Ckd)来完成。计算出P(Ckd)值后可以通过比较各个类的条件概率值,把d分到具有最大后验概率值P(Ckd)的类中去,得到最佳的分类结果。

对于给定的类集合,公式(2)中的概率值P(d)是一定的,对于分类没有什么作用,在分类过程中可以忽略,因此只需要计算出先验概率P(Ck)和条件概率P(dCk)这两个值,就可以比较各个类的条件概率值的大小,对d 进行分类。先验概率P(Ck)的值可以通过训练集容易得知,而条件概率P(dCk)的计算相对比较复杂,因为,从一般贝叶斯网络结构图可以看出,特征项之间可能相互依赖,这种依赖关系的存在使得特征属性的数量很多,从而使得条件概率P(dCk)的计算相对比较复杂。

2.2.2 改进贝叶斯模型

贝叶斯定理给出了最小化误差的最优解决方法,可用于分类和预测,理论上它看起来很完美,但在实际中它并不能被直接利用,因为它需要知道证据的确切分布概率,而实际上并不能确切地给出证据的分布概率。为了使用贝叶斯定理来分类,在很多分类方法中都作出某种假设以逼近贝叶斯定理的要求,改进贝叶斯分类方法就是其中的一种。其结构图如图2所示。

改进贝叶斯分类假定一个属性值对给定类的影响独立于其他属性的值。这一假设称作类条件独立。做此假定是为了简化所需的计算,并在此意义下称为“改进的”。这种假设大大降低了计算的复杂度,且具有较高的精确度,使用改进贝叶斯模型进行分类的做法是通过概率计算,从待分类的实例的属性值a1,a2,,an求出最可能的分类目标值,其工作过程如下:

①每个数据样本用一个n维特征向量X={x1,x2,x3,,xn}表示,分别描述对n个属性A1,A2,A3,,An样本的n个度量。

②假定有m个类C1,C2,,Cm。给定一个未知的数据样本X(即没有类标号),分类法将预测X属于具有最高后验概率(条件X下)的类。即是说,改进贝叶斯分类将未知的样本分配给类Ci,当且仅当P(CiX)>P(CjX),1jm,j≠i,P(CiX)最大的类Ci称为最大后验假定。根据贝叶斯定理,undefined,由于P(x)对于所有类为常数,要最大化P(CiX)只要P(XCi)P(Ci)最大化即可。如果类的先验概率未知,则通常假定这些类是等概率的,即P(C1)=P(C2)==P(Cm),并据此只对P(XCi)最大化,否则对P(XCi)P(Ci)最大化,P(Ci)可用P(Ci)=si/s来计算,其中,si是类Ci中的训练样本数,s是训练样本总数。

③给定的样本具有许多属性时,计算P(XCi)的开销可能很大。为降低计算P(XCi)的开销,可以做类条件独立的朴素假定。给定样本的类标号,假定属性值相互条件独立,即在属性间,不存在依赖关系。这样就有:undefined概率P(x1Ci),P(x2Ci),,P(xnCi)可由训练样本估值,其中:如果Ak是分类属性,则P(xkCi)= sik/si,其中sik是在属性Ak上具有值xk的类Ci的训练样本数,而si是Ci中的训练样本数;如果Ak是连续属性,则通常假定该属性服从高斯分布。

④对未知样本X分类,对每个类Ci,计算P(XCi)P(Ci)。样本被指派到类Ci,当且仅当P(XCi)P(Ci)>P(Cjx)P(Cj),1jm,j≠i,也就是说X被指派到其P(XCi)P(Ci)最大的类Ci。

3 结束语

利用贝叶斯分类方法对邮件进行分类的主要工作是从邮件取出标识并计算标识在垃圾邮件和有用邮件中出现的概率,其方法简单、可计算能力强、运算速度快。另外,不必像基于规则的方法那样预先设定规则、分析邮件句法或内容含义,且贝叶斯分类方法是用户根据自己所接收的垃圾邮件和非垃圾邮件的统计数据来创建的,这意味着垃圾邮件发送者无法猜测出过滤器是如何配置的,从而有效阻止垃圾邮件。

摘要：邮件过滤技术是反垃圾邮件的重要手段,目前对垃圾邮件的过滤主要有基于内容、基于IP地址和基于信头、信封等方法,这些方法对垃圾邮件的过滤起到了一定作用。但是由于信体是垃圾邮件的最终载体,而仅依据IP地址、信头、信封中的特征容易造成错误判断。在贝叶斯分类器的工作原理的基础上,提出了基于贝叶斯分类器的反垃圾邮件模型的原理与实现方法,将反映垃圾邮件的特征综合在一起统称为“属性”,避免了单纯基于IP、信头、信封过滤的规则性太强的缺点,降低将正常邮件判断为垃圾邮件的风险。

关键词：电子邮件,垃圾邮件,邮件过滤

参考文献

[1]陈华辉,薛春阳.一种基于贝叶斯网的“垃圾”邮件过滤器[J].微机发展,2000(4):53-55.

贝叶斯分类第5篇

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

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.

贝叶斯分类第6篇

1 基于分布估计算法的朴素贝叶斯分类器

1.1 分布估计算法

随着基础理论研究所取得的一系列进展,分布估计算法(estimation of distribution algorithms)以其较强的理论基础逐渐成为进化计算研究领域的一个新的研究方向,并成为当今国际进化算法研究的新热点。分布估计算法的基本思想就是使用概率的方法描述和表示每一代群体,并从个体中学习基因之间关系以及个体的适应度信息,利用学习到的信息生成性能更好的下一代群体[1,2]。

分布估计算法是遗传算法和统计学习的结合,通过统计学习的手段建立解空间内个体分布的概率模型,然后对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化。分布估计算法中没有传统的交叉、变异等遗传操作,是一种全新的进化模式。这种优化技术能够通过概率图模型对变量之间的关系进行建模,从而能有效的解决多变量相关的优化问题[3]。周树德等全面系统的介绍分布估计算法这一新技术[4],并总结该算法的研究现状和未来的研究方向。文献[5]提出了一种自适应实值分布估计算法,借鉴遗传算法中关于种群多样性的性能指标,并根据该指标相应改变采样时方差的值,从而扩大搜索空间,提高种群多样性。文献[6]提出一种新的基于最大熵的分布估计算法,主要用基于最大熵估计种群中的模式概率分布,取代贝叶斯网络分布估计算法中的贝叶斯概率图模型。该算法无需进行贝叶斯网络学习,大大减少了计算量,而且还能获取更准确的概率分布估计。

分布估计算法在算法设计、理论研究和实际应用方面仍需要做很多工作。作为一种新型的优化技术,分布估计算法的核心是解空间的概率模型。针对特定的优化问题,综合考虑搜索空间的结构、概率模型的学习算法、样本产生算法等。选择合适的概率模型,是发挥分布估计算法性能的关键所在。分布估计算法的本质是统计学习与进化算法的结合,通过统计学习手段对群体中的数据进行分析和建模,以挖掘搜索空间结构的相关知识。采用机器学习的方法分析数据、指导搜索已经成为设计新算法的趋势。

1.2 基尼指数

基尼指数是一种非纯度的属性分裂方法,适用于类别、二进制、连续数值等类型的字段,是Breiman等人于1984年提出的,被广泛应用在CART算法、SLIQ算法、SPRINT算法和Intelligent Miner的决策树算法中。Gini指数度量数据划分或训练数据集的不纯度。尚文倩在[7]中提到改进的基尼指数算法,采用测量属性对于分类来说的“纯度”的形式,即数值越大,“纯度”越大,信息量越丰富,属性越好.并提出了一种新型的文本分类模型(IGIC),取得了良好的分类效果。

1.3 贝叶斯分类器

近年来,数据挖掘成为一个新的研究热点。分类作为一种重要的数据分析形式,由于其具有大量的应用,也引起了研究者越来越多的关注。用于大型数据库,贝叶斯分类已表现出高准确率和高速度。贝叶斯分类法是一种统计学分类方法,是机器学习和数据挖掘中最有效地学习方法之一[8]。通过分类算法的比较研究发现,一种称作朴素贝叶斯分类法(Na觙ve Bayesian classifier)的简单贝叶斯分类算法可以与决策树和经过挑选的神经网络分类算法相媲美[9]。朴素贝叶斯分类法的“朴素”是指它的条件独立性假设,而实际的问题中这种朴素假设往往不能够成立,虽然在某些不满足独立性假设的情况下它仍然可能获得较好的分类性能,但是,仍然需要通过各种方法来提高朴素贝叶斯分类器的性能[4,9,10]。

文献[11]提出一种改进的朴素贝叶斯模型,它对样本空间中那些可能有助于提高分类准确率的子集给予更多的关注,从而达到提高模型分类准确率的目的。文献[12]介绍了一种使用贝叶斯假设选择子集概率的方法。文献[12]提出了一种提高朴素贝叶斯分类器准确率的新算法BoostFSNB,并与相关算法进行了对比,结果表明该算法的应用能够提高分类器的准确率。文献[14]通过分析比较得出10折交叉验证能够获得更好的无偏性。董立岩等为了降低朴素贝叶斯分类模型的独立性假设约束,提出一种混合式朴素贝叶斯分类模型[15]。通过分析贝叶斯定理,该模型把条件属性集合划分成若干个独立的属性子集,然后用树增广朴素贝叶斯分类对属性子集分别进行分类学习,最后通过公式进行整合。张明卫等提出了一种基于相关系数的加权朴素贝叶斯分类模型[16],通过计算条件属性和决策属性之间的相关系数,对不同的条件属性赋予不同的权重,从而在保持简单性的基础上有效地提高了朴素贝叶斯算法的分类性能。文献[17]提出了一种属性加权朴素贝叶斯算法,该算法通过属性加权来提高朴素贝叶斯分类器性能,从训练数据中直接学习得到加权参数。权值可以看作是计算某个类的后验概率时某属性取值对该类别的影响程度。对各属性的每个取值采取不同的加权值,从而体现出各个属性的不同取值对分类的影响。文献[18]对分类方法的新发展进行了较详细的归纳,并总结了分类方法发展的趋势。

文献[19]提出学习近似模糊规则的混合遗传算法来生成模糊分类器。它使用一种新的方法来促进种群间的共同进化,即通过个体运行的混合进化机制来发现多个规则。为了提高学习规则的质量,它提出一种通过每一代的遗传操作产生性能优良的后代的局部搜索方法,最后从最后一代生成的种群中抽取规则集形成模糊分类器。文献[20]对8种离散化方法进行了对比研究,并将其分别应用到NB/FNB,LBR和AODE三种分类器上进行对比实验。文献[21]归纳总结了现有的改进贝叶斯算法,并提出了一个新的贝叶斯模型即隐式朴素贝叶斯。它由每个属性产生的父母来使其与其他属性结合在一起产生权重,并通过大量实验以不同的评价方法分别验证了该算法的有效性。文献[22]介绍了利用ROC曲线评价分类器性能的方法。文献[23]介绍了一种比分类精度更能准确反应分类器性能的新方法AUC评价。

1.4 贝叶斯与进化算法的结合

文献[24]首次将分布估计算法引入到分类器系统中,并与遗传算法进行了对比,结果显示分布估计算法要优于遗传算法。文献[25]提出了一个在基于概率的优化问题中使用贝叶斯推理技术的框架。基于这个框架,描述了一个简单的连续贝叶斯分布估计算法。文献[26]介绍了一个基于贝叶斯分类器在每一代进化中进行学习和模拟的新的进化计算方法。朱允刚提出了用遗传算法简化搜索空间然后进行贝叶斯结构学习算法[27],该算法的搜索空间小于目前多数算法的搜索空间。金哲提出了一种基于遗传算法的BAN分类器算法[28]。该算法对TAN分类器的结构进行了扩展,得到了一种受限制的BAN分类器。针对这种分类器的结构学习,设计了结合对数似然的适应度函数,并给出了网络结构的编码方案,设计了相应的遗传算子,使得该算法能够收敛到全局最优。文献[29]提出一种新的算法,该算法为避免数据预处理时,训练集的噪声及数据规模使属性约简的效果不太理想,并进而影响分类效果,在训练集上通过随机属性选取生成若干属性子集,并以这些子集构建相应的贝叶斯分类器,然后采用遗传算法进行优选。

2 结论

贝叶斯分类第7篇

关键词：Android恶意软件,动态检测,机器学习,朴素贝叶斯,卡方检验

0 引言

Android是一个开放源系统, 这意味着不法分子也能够掌握此系统的基本结构和源代码, 所以Android手机恶意软件检测技术成为了当今热点问题。目前, 手机恶意软件检测主要采取基于签名或行为的传统电脑病毒检测算法, 其中基于行为的算法更适用于手机恶意代码检测。

Zhou等发现恶意代码往往通过重打包方式伪装自己欺骗用户, 提出Fuzzy Hashing方法实现重打包检测, 结果显示第三方电子市场存在5%~13%的重打包程序[1], 但并未进一步探寻具体的检测方案。Borja等根据Android软件的权限, 采取多种分类算法检测恶意软件, 虽部分算法准确度较高, 但仅考虑权限不足以反映Android软件特性[2]。Burguera等使用k-means聚类处理相同Android软件在不同用户使用下的行为数据, 但该方法需要使用者参与, 涉及到隐私泄露问题[3]。Shabtai通过监视特征值和事件开发一个基于行为的HIDS检测系统[4,5], 由于在早期研究中缺乏样本, 研究者们通常都自己编写恶意软件来证实他们的观点[6]。

本文使用机器学习算法分析应用软件行为, 收集大量广为应用的Android应用软件并将其中部分作为训练集, 提取出主要行为特征。由于朴素贝叶斯模型默认各特征值相对独立, 为了提高该分类算法的效率, 提出一种新的改进方法, 即在分类前使用卡方检验函数对样本应用程序进行选择, 然后再应用朴素贝叶斯模型将应用程序分类。

1 基于卡方检验的贝叶斯分类

为了完成恶意表现, 移动终端的恶意软件需要采取与之相关的行为。比如, 非法获取使用者的通讯录, 那么首先就需要在读取已存在终端设备上的通讯录, 自动连接网络, 并将非法读取到的联系人信息上传至网络。在监控到行为集合后, 使用朴素贝叶斯分类 (NBC) 算法, 它拥有可靠的数学依据、稳定的分类效率和相对较低的报错率。但是, NBC算法要求被获取并分析的特征值相对彼此独立, 如果属性特征存在相互依存关系, 朴素贝叶斯分类算法的效率就会大大降低, 此时就需要应用卡方检验来提高朴素贝叶斯分类算法的效率。

1.1 恶意行为描述

首先为了得到可以用于贝叶斯选择依据的恶意代码特征, 需要分析Android恶意软件的行为, 主要的恶意行为包括:

(1) 未经机主准许发送或删除短信, 通过发送收费短信定制特殊服务或删除回执信息;

(2) 截取短信通知, 机主因此不会意识到已被恶意扣取话费;

(3) 未经机主授权下载、安装或卸载应用程序;

(4) 非法获取机主SD卡内容;

(5) 非法获取手机基本信息, 如版本、ICCID、IMEI、IMSI或MSISDN;

(6) 非法获取机主隐私, 如通讯录、通话记录、短信、电子邮件和定位;

(7) 非法自动连接网络或改变当前联网方式以下载恶意应用或上传机主私人信息。

我们需要过滤出恶意行为的特征表现, Android应用程序由activity、broadcast receiver、service和content provider等组件组成。显然, broadcast receiver可以自定义这一点使得检测过程变得更加困难。此时需要将与恶意代码行为息息相关的activity和broadcast receiver行为进行全面的总结分析。另外, 应用程序必须得到相应的权限, 然后抄送它到Android Manifest.xml。典型的恶意代码行为与相应所需权限如下:

(1) 接收短消息, 权限为android.permission.RE-CEIVE_MMS, android.permission.RECEIVE_SMS, 该行为允许应用程序接收并篡改短消息内容, 接收后能够非法删除短消息;

(2) 读取通讯录, 权限为android.permission.READ_CONTACTS, 该行为允许应用程序读取通讯录信息, 非法联络通讯录成员;

(3) 拨打电话, 权限为android.permission.CALL_PHONE, 该行为允许应用程序在无机主参与情况下非法拨打电话;

(4) 获取GPS信息, 权限为android.permission.ACCESS_FINE_LOCATION, 该行为允许应用程序获取机主的精确位置;

(5) 改变网络设置, 权限为android.permission.CHANGE_NETWORK_STATE, 该行为允许应用程序改变网络连接方式;

(6) 安装程序包, 权限为android.permission.IN-STALL_PACKAGES, 该行为允许应用程序非法下载并安装程序包。

实验所用的应用软件包含的恶意代码行为只含有上面所述行为的6种。假设已知确定的应用软件行为, 将它命名为XS, 特征集合包括表现集合 (v1, v2, …, vn) 和行为集合 (c1, c2, …, cm) , 就得到我们所需要的机器学习集合, 如表1所示。aij代表了表1中横排i与纵列j的值, 表明了特征值vi的值归类到类别cj。

1.2 用卡方检验预处理

卡方检验算法在本文中起到了滤波器的作用, 这里使用它得到一个相互之间更加独立的恶意代码特征值的集合[7]。卡方检验公式表示如下:

式 (1) 描述了如何计算行为值xs的卡方值。在这个公式中, cij= (Tc1*Tcj) /T, 并且已经得知Tc1代表了类别ci的总数值, 而Tv2代表了特征vj的总数值。在计算了每个行为的卡方值之后, 将所得到的卡方值降序排列。如果xs的值越低, 就能够得知该行为与所需的特征值不相关, 将之从行为集中删除。

使用 (c1, c2) 来代表被测应用程序的所有恶意和非恶意行为, 其中, c1代表恶意行为, c2代表非恶意行为。下载的用于测量的所有Android应用软件的特征集合拥有n个元素, 这些元素包含行为优先值 (比如获取移动终端使用者地址的优先值) 和以确定会发生的功能值 (比如实现短消息接收的功能) 。然后设应用程序集合T (T1, T2, …, Tk) 总共包含k个事件。在测量过行为值xs的卡方值之后, 将卡方值比较低的行为从集合中删除。通过这种方式, 就可以得到上文中所需的更加相对独立的行为, 然后使用朴素贝叶斯分类方法来更有效地判定行为是恶意的还是非恶意的。用公式表述如下:

1.3 基于贝叶斯的分类算法

朴素贝叶斯分类算法是基于贝叶斯原理得出的一种分类方法, 并且拥有更高的计算性能[8]。假设一个样本拥有n个属性 (A1, A2, …, An) , 并且每个未知分类样本在n维空间中表示为X= (x1, x2, …, xn) 。设这里有m个类别 (c1, c2, …, cm) 。朴素贝叶斯分类算法假设X属于最高可能性的那个分类, 这也就意味着倘若对任意j (j!=i) , 都存在一个i满足p (ci|x) >P (cj|x) , 那么就可以下结论:X属于分类c1[9]。

这里使用Tr代表所测的Android应用软件是恶意软件, 而使用Ni代表这个应用软件具有第i个特征。那么如果这个应用软件是恶意的, 拥有第i个行为的未知数就可以被表示成为P (Ni|Tr) , 且P (Ni|Tr) =Si/m。BN用来代表被测应用软件是普通的, 如果普通应用软件拥有第i个等为特征, 那么未知数就是, 且P (Ni|BN) =Li/n。从训练集合之中可以得到P (Tr) =m/ (m+n) , P (BN) =n/ (m+n) 。

如果被测应用软件拥有K行为集合之中的a行为特征值, 那么可以设bi和分别用来表示被测样本有或者没有第i个行为特征值。B的组成可以用表示。定义P (Tr|B) 代表样本具有α个行为特征值, 而不具有K-α个行为特征值。而P (BN|B) 代表拥有以上行为特征值的被测样本均为普通非恶意样本, 得出式 (3) 。

接着, 再定义β=P (Tr|B) /P (BN|B) , 那么如果β>1, 就可以得出结论:这个应用软件样本是恶意的, 反之亦然。β的求解方法如式 (4) 所示:

P (Tr) 和P (BN) 也是已知的, 接下来需要应用式 (5) 来求得P (B|Tr) 和P (B|BN) 。

在上述公式中, 如果ai=bi或者, 此时的β可以由式 (6) 来表示。

2 实验仿真

使用实验的方式来检验之前讨论的算法, 首先获取477个Android应用程序, 其中的246个具有表1所包含的6种恶意代码行为。为了证明将以往简单的朴素贝叶斯分类模型与卡方检验理论结合起来的高有效性, 首先将这477个样本程序单独使用朴素贝叶斯分类进行检测, 称为实验一;将样本程序通过用卡方检验滤波器过滤后再使用朴素贝叶斯分类, 称为实验二。表2为实验一与实验二中对6种恶意代码行为的检测结果展示。从实验结果可以看出, 经过卡方检测预处理后, 朴素贝叶斯分类算法检测对采样的6种恶意行为敏感度分别都有提高。

为分析与表述的方便, 使用FPR (False Positive Rate) 来代表误报率, 使用FNR (False Negative Rate) 来代表漏报率[11]。实验结果表示在表3中, 表3包含了被测样本的总数 (总数) , 实际的恶意软件数量 (实际数) , 使用检测理论检测出来的恶意软件数量 (检测数) , 以及被检测理论检测出来的软件中确实是恶意软件的数量, 并随之计算出这两个实验结果的测试精度 (检测数占实际数的比例) 。从实验结果可以看出, 将卡方检验滤波器与朴素贝叶斯分类理论相结合的算法 (实验二) 拥有较低的误报率、漏报率和较高的精度[12]。

3 结束语

从实验仿真结果中, 可以发现将朴素贝叶斯理论与卡方检验相结合的改进算法应用在Android恶意软件动态检测技术上, 会使检测具有更高的效率。即使与以前的理论比起来效率确实提高, 但还是不能令人满意, 接下来的研究将着重研究恶意行为的隐性特征值, 以使得恶意和非恶意的软件的判决标准更完善。还可以将其他的分类标准, 比如K-nearest算法, 应用到动态行为检测中来, 已达到进一步提高效率和检测精度的目的。

参考文献

[1]ZHOU W, ZHOU Y, JIANG X, et al.Detecting repackaged smartphone applications in third-party Android marketplaces[C]∥Proceedings of the Second ACM Conference on Data and Application Security and Privacy.New York, USA:ACM, 2012:317-326.

[2]BORJA S, IGOR S, CARLOS L, et al.PUMA:Permission Usage to Detect Malware in Android[C]∥International Jiont Conference CISIS’12-ICEUTE’12-SOCO’12 Special Sessions.Berlin, Germany:Springer, 2012:289-298.

[3]BURGUERA I, ZURUTUZA U, NADJM-TEHRA-NI S.Crowdroid:Behavior-based Malware Detection System for Andoird[C]∥Proceedings of the 1st ACM Workshop on Security and Privacy in Smartphones and Mobile Devices.New York, USA:ACM, 2011:15-26.

[4]SHABTAI A, ELOVICI Y.Applying Behavioral Detection on Android-based Devices[C]∥Mobile Wireless Middleware, Operating Systems, and Applications.Springer Berlin Heidelberg, 2010:235-249.

[5]SHABTAI A, KANONOV U, ELOVICI Y, et al.'Andromaly':a Behavioral Malware Detection Framework for Android Devices[J].Journal of Intelligent Information Systems, 2012, 38 (1) :161-190.

[6]WU Dong-Jie, MAO Ching-hao, WEI Te-en, et al.DroidMat:Android Malware Detection through Manifest and API Calls Tracing[C]∥2012 Seventh Asia joint conference on information security, 2012:62-69.

[7]LANCASTER H O, SENETA E.Chi-Square Distribution[M].USA:John Wiley&Sons, Ltd, 1969.

[8]张立民, 刘峰, 张瑞峰.一种构造系数的自相关函数特征提取算法[J].无线电通信技术, 2012, 38 (5) :56-59.

[9]周继宇, 张雅奇, 徐伯庆.一种采用非均匀量化的近似Log-MAP算法[J].无线电通信技术, 2012, 38 (1) :29-31.

[10]柴伟杰, 付志兵, 王志芳.决策树算法在应急预案评估中的应用分析[J].无线电工程, 2011, 41 (7) :58-61.

[11]魏亮, 刘琳琳, 刘洋, 等.基于G-S算法的GPS接收机抗干扰技术研究[J].无线电工程, 2013, 43 (4) :35-36, 47.

贝叶斯分类范文

贝叶斯分类第1篇

基于群的朴素贝叶斯分类第2篇

基于贝叶斯分类的毒蘑菇识别第3篇

贝叶斯分类第4篇

贝叶斯分类第5篇

贝叶斯分类第6篇

贝叶斯分类第7篇

贝叶斯分类范文

猜你喜欢

栏目

最近更新

热门标签

贝叶斯分类范文

贝叶斯分类 第1篇

基于群的朴素贝叶斯分类 第2篇

基于贝叶斯分类的毒蘑菇识别 第3篇

贝叶斯分类 第4篇

贝叶斯分类 第5篇

贝叶斯分类 第6篇

贝叶斯分类 第7篇

贝叶斯分类范文

猜你喜欢

栏目

最近更新

热门标签

贝叶斯分类第1篇

基于群的朴素贝叶斯分类第2篇

基于贝叶斯分类的毒蘑菇识别第3篇

贝叶斯分类第4篇

贝叶斯分类第5篇

贝叶斯分类第6篇

贝叶斯分类第7篇