加权朴素贝叶斯分类论文

2024-10-20

加权朴素贝叶斯分类论文（共7篇）

加权朴素贝叶斯分类论文篇1

0前言

分类是数据挖掘中一项重要的核心技术,其目的就是通过学习得到一个目标函数f,把每个属性集映射到一个预先定义的类标号y,因此可以将分类看作是从数据库到一组类别的映射。这些类别是被预先定义的,没有重合的。数据库里的每一个元组都可以准确地分配到某个类中。朴素贝叶斯分类器是一种最简单、有效、具有坚实的理论基础并在实际应用中得到广泛使用的分类器。朴素贝叶斯分类方法基于条件独立性假设,即假设一个属性对给定类的影响独立于其他属性,而这在现实问题中往往并不成立,为此,许多学者做了大量的工作来放松独立性假设。Harry Zhang等根据条件属性对决策所起的作用给予它们不同的权值,提出了加权朴素贝叶斯分类模型。Zhou Jiyi等根据粗糙集权重确定方法提出了一种基于区分矩阵的属性权重确定法。程克非、张聪提出了一种基于特征加权的朴素贝叶斯分类器。秦锋、任诗流提出一种通过用加权调整的先验概念来代替原朴素贝叶斯的先验概率。白似雪,梅君提出一种计算每个属性对每个类的相关概率和不相关概率,并以此进行加权。本文提出另一种加权方法,将信息论里互信息知识与属性之间的相关性相结合,给予不同的条件属性赋予不同的权值,实验证明,这种方法能有效提高分类效果。

1 朴素贝叶斯分类器

每个元组用一个n维属性向量X={x1,x2,…xn}表示,描述由n个属性A1,A2,…,An对元组的n个测量。假定有m个类C1,C 2...,Cm。这样,给定一个未知的元组X,其P(Ci|X)最大的类iC称为最大后验假定。根据贝叶斯定理:

由于P(X)对于所有类为常数,只需要P(X|Ci)P(Ci)最大即可。如果类的先验概率未知,则通常假定这些类是等概率的,即P(C 1)=P(C 2)=...P(Cm)。并据此对P(Ci|X)最大化。否则,最大化P(X|Ci)P(C i)。注意,类的先验概率可以用P(C i)=si/s计算其中is是类iC中的训练样本数,而s是训练样本总数。

给定具有许多属性的数据集,计算P(X|Ci)的开销可能非常大。为降低计算P(X|Ci)的开销,可以做类条件独立的朴素假定。给定元组的类标号,假定属性值有条件地相互独立,即在属性间不存在依赖关系。这样,

先验概率p(x1|Ci),p(x2|Ci),……,p(xn|Ci)可以从训练数据集求得。

根据此方法,对一个未知类别的样本X,可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci),然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为:

2 属性加权朴素贝叶斯分类算法

在现实实际应用中不同的条件属性与决策属性之间的相关程度是不同的,当条件属性与决策属性的相关程度高,它对分类的影响就要更大些,反之,如果条件属性与决策属性的相关程度较小,那么它对分类的影响就会很小。条件属性与决策属性的相关关系可以用相关系数的求解公式求得。设条件属性为Xi,决策属性为Y,其相关系数可以通过Xi与Y的协方差与Xi与Y的方差的几何平均数求商得到,它反映了Xi与Y属性的线性相关紧密的程度,值越大表明属性之间的联系越紧密,反之则联系较差。

属性间的相关系数为:

由于权值的范围介于0和1之间,则设定权值为:

信息论里的互信息概念是描述某个随机变量关于其他随机变量变化时的信息量的大小,它可以用来反映条件属性提供的关于决策属性的信息量的大小。而相关系数是通过代数方法里的协方差与方差来求得的,它侧重与属性间的偏离程度,能够有效的改进分类能力,但是它对属性间的变化不敏感。因此希望通过结合相关系数与互信息的知识,从而使属性获得更好的权重,提高分类效果。

设条件属性C和决策属性D的互信息,记为:

因此可以得出条件属性iC的权值为:

综合相关系数与互信息的权值公式,定义两者的平均值作为新的权值公式:

基于属性加权的AWI-AUC算法的实现关键在于求出各条件属性与决策属性之间的相关系数和他们的互信息。具体算法步骤如下:

步骤1数据预处理:将训练样本和待分类样本进行补齐和离散化;

步骤2分类器的建构。

步骤2.1读入并搅乱数据集,对数据集里的条件属性,决策属性,以及训练样例进行统计,生成统计表。再将数据集划分为新的训练集和测试集。

步骤2.2生成分类器网络结构,并对其进行参数学习。

步骤2.3计算所有的先验概率值,即在决策属性Dj下各个条件属性Ci取值的概率p(Ci|D)。

步骤3计算权值。

步骤3.1权值Wc的计算。扫描所有的训练集,求出各条件属性与决策属性的协方差Cov(Ci,D)和方差D(Ci)和D(D),通过公式计算得到相关系数ρCi D,则权重Wc=|ρCi D|。

步骤3.2权值Wi的计算。先求出条件属性和决策属性的互信息I(Ci,D),再计算权重Wi。

步骤3.3综合权值Wc和Wi,求得所需的权值Wci,并生成属性权值列表。

步骤4分类评估。通过对属性给予不同的权值,得出分类结果。

该算法的性能在各多项式时间内完成,并且算法可行。

3 实验结果及分析

为了验证算法的可行性和有效性,用数据集对算法进行了测试。实验数据集选自UCI(University of California in Irvine)数据库,下载网址是http://www.ics.uci.edu/~mlearn/MLRepository.html。所有数据集中数据的连续属性值均进行离散化处理。实验在MBNC(Bayesian Networks Classifier using Matlab)平台下完成。首先对数据集进行随机搅乱,打乱数据之间原先的排列顺序,并对数据集采取5叠交叉验证。每个数据集轮流实验5次,取5次实验的平均值作为实验的测试结果。表1为经过预处理后的数据集情况。

实验结果如表2所示。O-AUC表示的是没有使用加权方法时得出的AUC值,CC-AUC表示的是使用相关系数作为加权方法得到的AUC值,I-AUC表示的是使用信息论中的互信息知识作为权重后得到的AUC值,AWI-AUC表示的是本文提出的AWI-AUC算法得到的AUC值。

由表2可知:

(1)当O-AUC与CC-AUC,I-AUC比较时,可以看出CC-AUC,I-AUC在各个数据集下得到的AUC值均大于O-AUC,可见通过把条件属性与决策属性的相关系数和互信息作为条件属性的权重,可以提高分类器的分类性能,使得分类更加准确。

(2)当CC-AUC与I-AUC比较时,CC-AUC的值比I-AUC的值大的有6个数据集,比I-AUC值小的有4个数据集,并且这4个数据集中的训练集个数均偏大,可见I-AUC更适合对数据集大的进行分类,会获得更好的分类效果,只是原样本集里填充和离散的数据会对原样本产生影响。CC-AUC在这种情况下可以有效地提高贝叶斯分类能力。但CC-AUC采用的权重是通过相关系数得到,相关系数由代数的计算方法求得,结合实验对数据规模偏小的数据集更加适合,因此将上述两种方法综合求均值,得到新的AWI-AUC方法,通过实验证明AWI-AUC在总体上要好于其他方法,并证明了通过挖掘属性之间的潜在关系,对属性赋予不同程度的权重,可以获得更好的分类效果。

4 结束语

本文基于研究条件属性与决策属性之间的关系,并结合信息论中互信息的相关知识,提出一种加权的AWI-AUC方法,根据条件属性对决策分类的重要性不同给予其不同的权重系数来对AUC方法进行优化评估。在MBNC实验平台上实现该方法,并在数据集上通过实验比较,表明该方法的有效性和可行性。今后,将进一步研究改进条件属性与决策属性相关性的方法,以及分析条件属性与条件属性之间的关系,是否能够更好地提高分类器的分类能力。

参考文献

[1]秦锋,杨波,程泽凯.分类器性能评价标准研究[J].计算机技术与发展.2006.

[2]Harry Zhang,Shengli Sheng.Learning Weighted Na?ve Bayes with Accurate Ranking.[C]//The 4th IEEE International Conference on Data Mining.Chicago:IEEE Computer Society,2004.

[3]ZHOU Jiyi,LV Yuejin.A New Method of Ascertaining Attribute Weight Based on Discernibility Matrix.CSIST.2010.

[4]程克非,张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真.2006.

[5]秦锋,任诗流等.基于属性加权的朴素贝叶斯分类算法[J].计算机工程与应用.2008.

[6]白似雪,梅君,吴穹.一种基于概率加权的朴素贝叶斯分类.2009.

[7]林士敏,王双成,陆玉昌.Bayesian方法的计算学习机制和问题求解[J].清华大学学报.2000.

[8]张明卫,王波,张斌.基于相关系数的加权朴素贝叶斯分类算法[J].东北大学学报(自然科学版).2008.

[9]C.Blake and C.Merz,UCI Repository of Machine Learning Databases.http://www.ics.uci.edu/~mlearn/MLRepository.html.1998.

[10]程泽凯,林士敏,陆玉昌.基于Matlab的贝叶斯分类器平台MBNC[J].复旦学报.2004.

加权朴素贝叶斯分类论文篇2

在数据挖掘领域中,分类是一个非常重要的问题,是当前研究的热门。针对分类的问题,国内外都有比较深入的研究。其中成熟的分类算法有如决策树、基于向量空间模型的K-近邻分类、关联规则分类、神经网络、遗传算法、朴素贝叶斯等。在众多的分类算法中,朴素贝叶斯算法由于有着深厚的数学理论研究基础,以及其计算高效简单、有效而在众多应用中所运用。朴素贝叶斯算法是基于这样一个简单的假定:即分类特征属性之间都是条件独立的。用权值的概念表示就是各个属性之间的权值都是相等的,不存在差异。但是在应用环境中,特征类属性之间的关系很少是独立的,不满足实际的需求。针对这种情况,国际上很多学者都对此提出了各自的解决方案,比如,学者Zhang Harry提出了根据属性的重要性给不同属性赋不同权值的加权贝叶斯WNB(Weighted Native Bayesian),他给出了爬山算法和Monte Carlo技术确定权值的加权朴素贝叶斯算法,这些算法确实有了很大的改进,但是对于大数据集,朴素贝叶斯在整个训练集上,分类性能并不能得到很大的提高。我们期望能在局部的数据集上得到一定的释放。

本文通过对K-近邻法的深度研究,综合考察了朴素贝叶斯的分类算法的特点,通过K-近邻法先对测试样本分类,然后在测试的实例领域内构建贝叶斯分类器。提出了基于K-近邻法的局部加权朴素贝叶斯分类算法,并通过实验数据证明了该算法的合理性、可靠性,最终提高了分类的准确率。

1 K-近邻法的相关概念

K-近邻法是一种常用的基于距离的度量方法。训练样本是n维的数值属性描述。每个样本是n维数值空间中的一个点。所有的训练样本都存放在n维模式空间中。当给定一个未知样本时,K-近邻法搜索整个模式空间,找出最近接近未知样本空间的k个训练样本。这k个训练样本就是未知样本的k个“近邻”。“近邻”之间的定义是用欧几里德距离定义,欧几里德距离定义是这样定义如下:若空间中存在两个点x={x1,x2,…,xn},y={y1,y2,…,yn},那么这两个点的距离是:

$d (x, y) = \sqrt{\sum_{i = 1}^{n} (x_{i} - y_{i})^{2}} (1)$

在比较距离时,我们不必计算平方根,直接使用平方和来比较就可以。在使用该欧几里德距离函数来判断训练集中的哪个实例与一个未知的测试实例最靠近时,我们一旦找到最靠近的训练实例时,那么最靠近实例所属的类就被预测为测试实例的类,未知样本被分配到k个最邻近者中的最公共的类。当k=1时,未知样本被指定到模式空间中与之最邻近的训练样本类。

2 朴素贝叶斯分类器

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

P(HX)=P(XH)P(H)/P(X) (2)

其中P(XH)代表假设H成立的情况下,观察到X条件概率。P(H)是先验概率,或称H的先验概率,表示在任何数据样本出现证明之前假设H的概率。P(HX)是后验概率,或称条件下H的后验概率。朴素贝叶斯的分类说明步骤如下:

(1) 把每个数据样本数值化,用一个n维特征向量X={x1,x2,…,xn}表示样本属性的n个度量。

(2) 假定有m个类C1,C2,…,Cm。给定一个待分类的样本X,根据贝叶斯定理可得样本X的概率为:

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

(3) 由于P(X)对所有类都是常数,即只需P(XCi)P(Ci)最大。如果类的先验概率未知,则通常这些类是等概率的。即P(C1)=P(C2)=…=P(Cm)所以只需P(XCi)为最大。

(4) 为了计算P(XCi),我们通常做类条件独立的朴素假定。给定类的标号,假定属性值条件相互独立,则:

P(X $C_{i}) = \prod_{k = 1}^{n} Ρ (X_{k}$ Ci) (4)

即概率P(X1Ci),P(X2Ci),…,P(XnCi)由训练样本估计,其中:

a) 如果Ak是分类属性,则:

P(XkCi)=Sik/Si (5)

其中Sik是在属性Ak上具有值Xk的类Ci的训练样本数,而Si是Ci中的训练样本数;

b) 如果是连续属性,则通常假定该属性服从高斯分布。因而:

P(Xk $C_{i}) = g (x_{k}, u_{c i}, σ_{c i}) = \frac{1}{\sqrt{2 π} σ_{c i}} e^{\frac{(x - u_{c i})^{2}}{2 σ_{c i}^{2}}} (6)$

其中给定类样本的Ci的训练样本属性值Ak的值,g(xk,uci,σci)是属性Ak的高斯密度函数,而uci,σci分别为平均值和密度差。

(5) 对未知样本X分类,计算P(XCi)P(Ci),比较P(XCi)P(Ci)与P(XCj)P(Cj),如果P(XCi)P(Ci)>P(XCj)P(Cj),则X被分到Ci类中,反之则分到Cj类中。

3 K-近邻局部加权朴素贝叶斯分类算法

K-近邻局部加权的朴素贝叶斯K-LWNB(K-Locally Weighted Naive Bayes)。它首先应用k-近邻算法找到测试实例的k个邻居,然后应用线性方法来给每个邻居加权,最后在加权后的邻域内构建朴素贝叶斯分类器。K-LWNB算法于K-近邻算法一样是一种k相关的学习算法,要求用户在使用的时候自己认为地输入学习参数k,并且k的取值在一定程度上影响了它的分类性能。所以对于k的选择是相当重要的。本文提出了一种选择邻域大小的朴素贝叶斯模型,该模型为每一个测试实例在具有不同大小k值的数值邻域上学习一组朴素贝叶斯分类器,然后在其中选择一个最高分类准确度的朴素贝叶斯器来分类测试实例。在设计具体算法的时候,我们输入的数据包括有:领域的最大值Kmax、领域最小值Kmin以及训练实例集T;算法输出的数据就是Kbest;

具体算法伪代码描述如下:

4 实验结果

为了验证该算法的有效性,对该算法进行了实例的有效测试,实验中所选用的所有数据都来自于UCI公共数据库。本实验从UCI公共数据库中挑选了十个数据集作为测试数据。这些数据集的基本信息如表1所示,在这些数据中,为了达到更为准确的结果,使用的所有数据的连续属性值都进行了离散化处理,并且实验采用的十次交叉验证法。实验所采用的软件平台是:Windows XP操作系统,weka3.5.8版本数据挖掘工具,硬件平台是:双核T2060 1.6G Hz CPU,2GB内存。

在本实验所用的数据实例中,实验结果表明K-LWNB算法的分类准确率要优于NB算法,在十个实例中,八个实例运行后的精度都要高于NB算法。算法通过计算每个数据集的不同属性值与类别之间的相关性,然后使用K-近邻法得出K个最优邻居,最后用线性的方法给这些邻居加权,即各个相关属性获得了加权系数。最后分类的时候对后验概率计算公式中的每个概率项进行加权修正并最终得出分类结果。从实验结果可以看出,使用K-LWNB算法对属性进行加权分类,更加有效地利用了样本数据信息和属性与类别间的关联性。但值得注意的是在十个实例数据分类中,有两个实例数据分类的准确率小于NB算法,分析发现,这两例实例数据条件属性比较多,K-LWNB算法分类能力与NB算法相比略有下降。可能是因为属性值过多,导致每个属性值所得的加权系数都比较小,而不能真正发挥出自己的作用,但这与理论分析是一致的,在一定的误差范围之内。另一方面就是在算法的运行时间上,K-LWNB算法由于要计算找K个领域,因此要高于NB算法,但不影响分类结果。综上所述,K-LWNB算法是有效的。

5 结语

条件独立性假设在很大程度上影响了朴素贝叶斯的分类性能,实际上,在现实的生产环境中,对于属性之间条件独立是很少的。但是,由于朴素贝叶斯对于条件独立性的属性分类又是极其优秀的。所以,针对这种情况,本文进行了算法的改进。从局部来释放这种条件独立性的假设,最后从实验得出的数据可以看出,该算法确实提高了分类性能。但是,由于无关属性在多数机器学习方案中存在负面影响,通常在学习之前先进行属性选择,只保留一些最为相关的属性,而将其他属性都去掉,选择相关属性最好的方法是人工选择,通过去除不适当的属性以降低数据的维数,能改善学习算法的性能。还能提高速度,即使属性选择可能会带来很多计算。更重要的是,维数降低形成一个更为紧凑、更易理解的目标概念表达式,使用户的注意力集中在最为相关的变量上。在这个算法中,前期实验准备也进行了人工属性选择,这样对整个算法的执行效率就更为准确有效。最后,论文中用UCI数据库中的10数据集作为测试数据,通过实验比较了朴素贝叶斯分类算法与K-近邻局部加权的朴素贝叶斯分类算法的分类性能,实验结果表明,使用K-近邻局部加权的朴素贝叶斯算法在一定的条件下,分类性能有了明显的提高。

参考文献

[1]Hall M.A decision tree-based attribute weighting filter for Nave Bayes[J].Knowledge-Based Systems,2007,20(1):120-126.

[2]Zheng Z,Webb G I.Lazy learning of Bayesian rules[J].MachineLearning,2000,41(1):53-84.

[3]Kelly D,Tangney 13.Adapting to Intelligence Profile in an AdaptiveEducational Aystem[J].Interacting with Computers,2006,18(3):385-409.

[4]Harry Z,Sheng S.Learning Weighted Naive Bayes with Accurate Rank-ing[C]//Fourth IEEE International Conference on Data Mining(IC-DM’04),2004:567-570.

[5]Chickering DM.Learning Bayes networks is NP-complete[M]//Learn-ing from Data:AI and Statistics V.New York:Springer,1996:121-130.

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

[7]蒋良孝.朴素贝叶斯分类器及其改进算法研究[D].中国地质大学,2009.

[8]秦锋,任诗流,罗慧.基于属性加权的朴素贝叶斯分类算法[J].计算机工程与应用,2008,44(6):107-110.

[9]邓维斌,王国胤,王燕.基于Rough Set的加权朴素贝叶斯分类算法[J].计算机科学,2007(2):204-206.

[10]程克非,张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真,2006,23(10):92-94.

[11]王双成,苑森淼.具有丢失数据的贝叶斯网络结构学习研究[J].软件学报,2004,15(7):1042-1048.

一种朴素贝叶斯分类增量学习算法篇3

朴素贝叶斯算法是基于贝叶斯全概率公式的一种分类算法[1,2]。它以贝叶斯定理为理论基础,是一种在已知先验概率和条件概率的情况下计算后验概率的模式识别方法。朴素贝叶斯分类算法有一个基本限制:在给定特征条件下的属性值之间必须相互条件独立,即特征项独立性假设。尽管在现实世界中,这种独立性假设经常是不能满足的,但目前许多研究和应用都表明,即使违背这种假定,NB也表现出很强的健壮性[3],所以越来越受到机器学习研究人员的重视[4,5]。但是由于贝叶斯分类分类算法本身的特点,它不可避免地存在一些其他的限制和不足,如训练集永远没有变化或者更新训练集后需要重新学习分类器从而耗费大量时间等,增量学习方法能够弥补这些方面的不足。

增量学习(Incremental Learning)是一种得到广泛研究与应用的智能化数据挖掘与知识发现技术[1,6,7,8]。在这个信息不断增长的时代,一种机器学习方法是否具有良好的增量学习能力已经成为评价学习性能优劣的重要参考之一。但是传统的贝叶斯分类算法只是在分类时使用到先验概率与样本信息,很少涉及到对分类器进行增量学习,文章[6,8]中提到的增量学习都是基于文档型计算公式的朴素贝叶斯分类算法。这种使用文档型计算公式计算属性的类条件概率存在特征项对文本贡献不明显的弊端。Harry Zhang在文献[9]中提出了根据属性的重要性给不同属性赋不同权值的加权朴素贝叶斯(Weighted Naïve Bayes,简称WNB)模型并实验得出较理想的效果。但是Zhang的文章未涉及到增量学习修正分类器。

本文结合上述两种思想的优势,提出加权朴素贝叶斯分类增量学习算法。文章对加权贝叶斯分类增量学习算法思想以及实现过程进行了详细描述并对算法进行证明。通过算法分析,得到其相比无增量学习的贝叶斯分类,额外的空间复杂度与时间复杂度都在可接受范围。

2 朴素贝叶斯分类算法

2.1 朴素贝叶斯分类算法简述

朴素贝叶斯分类方法中,每个数据样本用一个m维向量:d=d(W1,…,Wi,…,Wm)表示,其中Wi表示文本特征项;训练集D={d1,d2,…,dN}中的每个文本属于类集C={c1,…,ck}中的一个类。利用贝叶斯公式通过类别ci的先验概率和文本的类条件概率P(d|ci)来计算未知文本d属于ci类的概率,并取后验概率最大的类为文本的类别。计算公式如下:

undefined

undefined

其中P(wj|ci)即特征项wj在类ci中出现的概率,也叫属性的类条件概率。

2.2 贝叶斯分类算法的缺陷

朴素贝叶斯分类算法具有简洁,高效和稳定等优势,但是也存在一定的弊端。其要求在给定特征条件下的属性值之间必须相互条件独立在现实文本中就难以满足。但目前许多研究和应用都表明,即使违背这种假定,朴素贝叶斯也能取得较好效果。除了这个独立性假设,目前研究的朴素贝叶斯分类算法还是存在一个比较明显的缺陷。

朴素贝叶斯分类算法就是根据训练样本的类先验概率和特征项的类条件概率(都从训练集D中得到)来预测后验概率,得出测试文档的类别标签。有限的训练文本集的文本分布很难完全代表总体文本的分布,所以计算得到的先验概率的可信度有待修正。如果训练集D没有良好的数据完备性,那么预测的测试文档类别标签就可能不准确。而真实的情况是,有限大小的训练集D不可能具有完备的数据,一些领域的分类文本也是一批一批得到。不学习新的文本的分类器的分类效果必然没有多学习新的文本的分类器的分类效果好。传统的贝叶斯分类要想学习新的文本所包含的信息,就需要重新学习全部文本,每这样学习一次,都需要耗费大量时间代价。

3 贝叶斯分类增量学习算法

3.1 增量学习思想

在原始条件下,训练集D是保持不变的。而有限的训练集要完全表示文本的分布情况是不现实的。为此需要通过一种方法来不断更新训练集,以期达到完备训练集从而使其分类效果更精确的目的。增量学习思想[3]就是将测试集Dt中没有类别标签的实例经过分类器分类后,经过一个严格判断过程,将判断确认正确分类的文本追加到训练集D中;以及将专家给出正确分类的文本和其他途径得到的批量已分类文本追加到训练文本集,使得训练文本信息能够得到扩充,信息量更加丰富。在分类器已有知识的基础上,结合新加入文本,再次训练分类器,利用新文本中含有的有用信息来修正当前的分类器,能够使得各类别的先验概率以及各特征项的类条件概率能够更加精确,从而使得分类器分类效果更好。

对于贝叶斯文本分类,增量学习的任务实质上是如何根据先验信息和新加入样本的信息来确定新的先验概率P(ci)和各个属性类条件概率P(wk|ci)。

对于属性类条件概率P(wk|ci),文献[6]与[8]中使用的是文档型计算公式:

undefined

其中P(Aj=aj|c=ci)为特征项aj属于类ci的概率,count(Aj=aj|c=ci)为在属于类ci的文本中出现了特征项aj的文本数, count(c=ci)为属于类ci为属于类的文本数。

此计算公式具体简洁易算的特点,能够使得分类方法在这个过程中计算速度很快。但是,依据此公式,多个对文本类别贡献不同的特征项,只要都同时在若干个文本中出现,其属性的类条件概率就相同。显然,这样的属性类条件概率公式完全不能凸显特征项在文本中的重要性。为克服此弊端,本文对属性的类概率P(wj|ci)计算采用能够体现特征项在文本中重要性的词频加权计算公式,公式如下:

undefined

式中|V|表示项表中总项数,TF(wj,ci)表示项wj在训练集中属于类ci的所有文本中出现的频次之和,即

undefined

式中fik为特征项wi在文本dk中的出现频率。为防止TF(wj,ci)为0从而引起P(wj|ci)为0的情况发生,可以在初始化时先给每个TF(wj,ci)赋初值0.01。赋小的初值能够解除前面的疑虑,同时又能避免淹没其他在类中少量出现但是分类能力强的特征项。

3.2 增量学习文本选择

并非所有测试文本都适合用来对系统进行增量学习,那些类别不太明确或者对类别表示贡献不大的文本,加入后可能反而使类别特征模糊化。所以对于哪些文本采取增量学习应有严格的限制。有两种情况的文本适合分类器增量学习,一种是有专家已经给予分类的文本,这在专题文本领域是很常见的;另一种是对未分类的文本,由分类系统自动判断其是否合适参与增量学习。本文主要论述第二种情况,第一种情况相比第二种情况少了判断过程,实际上是一个单纯的增量学习的过程。

对于没有类标签的文本dt,需要用现有的分类器为它分配类标签。为方便计算,本文定义给文本划分到某类的概率取一个名称为类置信度,用θ表示。依据上面的公式(4),文本dt属于类ci的类置信度为:

undefined

令θt=max{θi,1≤i≤k},则分类结果为,即dt属于类ct。

判断被分类文本dt是否满足加入训练集进行增量学习的条件是:如果θt满足:undefined,即θt不小于其他类置信度之和的某个系数倍,则系统相信文档dt属于类ci的划分确定可信。系数α设定越大,系统对于参与增量学习的文本要求越严格。根据经验得出α∈[1/2,1]系统都能得到比较好的效果。

3.3 算法描述

输入:训练集D={d1,d2,...,dN},测试集Dt={dN+1,dN+2,...,dK}

输出:分类器C,测试文档dt类别

Step1:利用训练集D,学习分类器C;

Step2:对于测试集Di中每个文本di,重复如下步骤:

Step3:利用分类器C,分类di,得到类标签〈di,ct〉;

Step4:依据式(6)判断类置信度θt,如果undefined,进行下一步,否则,转Step6;

Step5:undefined,修正分类器C,包括修正P(ci)、P(wk|ci)、D和|Dci|;

Step6:Dt=Dt-dt,判断Dt是否为空,为空,执行下一部,否则转Step2;

Step7:算法结束。

下面给出上述算法中的增量学习公式并在后文给出部分证明。

类先验概率修正公式:

undefined

属性的类条件概率修正公式:

undefined

文档数量修正公式:D=D+1;|Dci|=|Dci|+1,当ct=ci

其中:D表示文档总数;|Dct|表示属于ci类的文档数;|Wci|表示属于ci类的所有文本中的所有词频总和;fkt表示特征项wk在文dt中的频率;undefined表示文档dt中出现的所有词的词频总和。

对分类器进行修正的文本不仅仅限于系统判断保证准确分类的文本,还可以是专家分类结果文本和其他途径得到的批量带分类文本。对带分类的文本的增量学习,直接进行Step5。可以看出,依本算法得到的分类器除了拥有较好的自学习能力,还有良好的人机交互功能。其增量学习能力正是我们所期望的。

4 算法证明与分析

4.1 算法证明

下面对式(7)进行简单证明。为方便阅读,对新生成的变量P(ci),以P*(ci)表示以显示区别,其他变化变量同此。式(7)中ct=ci情况下对P(ci)增量学习公式证明如下:

undefined

证毕。

当ct≠ci时,P(ci)的增量学习公式undefined,可以看出它是ct=ci情况下对P(ci)增量学习公式的一部分,证明参照上式。

式(8)中当ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式证明如下:

undefined

证毕。

式(8)中当ct=ci并且wk∉dt情况下对P(wk|ci)增量公式证明如下:

undefined可以看出它是ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式的一部分,证明参照上式。

4.2 算法分析

对新加入一个文本到训练集,系统需要保存的内容包括:新文本的各特征项,各类的先验概率,各属性的类条件概率,为增量学习系统需额外保存与临时保存的内容有属于类ci的词频总和、|Wci|新加入文档dt中的词频总和undefined、新的类先验概率P(ci)以及新的属性的类条件概率P(wk|ci),不能分析得到,因增量学习而产生的额外空间开销为S(m),其中m为新文本中的特征项数;

在额外时间复杂度方面,对系统进行一个文本的增量学习,与不进行增量学习的差别主要在step4与step4,即需要对是否进行增量学习做判定以及需要重新计算被分类文档的词频总数、类先验概率、属性的类条件概率、文档总数与划入类的类文档总数。step4做判定的时间复杂度是O(k),计算总词频总数、文档总数与划入类的类文档总数是一个简单加法,复杂度为O(1),计算类先验概率的时间复杂度为O(k),计算属性的类条件概率的时间复杂度为O(km),不难得出额外时间开销为O(k)+O(1)+O(k)+O(km)=O(km),其中m为分类系统中所包含的总项数,k为文档类别总数。可以看出,贝叶斯分类增量学习算法在空间和时间复杂度上的额外开销都在可接受范围,所以该算法是可行的。

5 结束语

朴素贝叶斯分类方法以其高效率为广大研究人员接受,但是关于其增量学习方面得到的关注并不多,更多是关注到属性条件概率计算上面,以使特征项能更好的表现文本。本文研究属性类条件概率计算公式为TF加权法的加权朴素贝叶斯分类增量算法,对给出了算法思想,具体算法以及算法证明和分析。虽然采用TF加权比文档型计算公式对分类效果要好很多[9],但是采用的TF加权法,也存在如下弊端:一些在多种类型的文本中多次出现的词削弱了其他分类能力强的词的表现力。作者下一步目标是研究能够在时间复杂度可接受范围内进行的更理想的加权朴素贝叶斯分类增量学习算法。

参考文献

[1]史忠植.知识发现.北京:清华大学出版社,2002.169～220

[2]王玉玲.基于贝叶斯理论的分类模式挖掘方法研究.微计算机应用,2007,28(6):664～668

[3]Domingos P,Pazzani M.On the Optimality of the Simple Bayesian Classifier under Zero-One Loss.Machine Learning,1997,29(2-3):103～130

[4]Yager R.An extension of the naive Bayesian classifier.Information Sciences,2006,176:577～588

[5]Mc Callum A,Nigam K.A comparison of Event Models for Naive Bayes Text Classification.AAAI-98Workshop on Learning for Text Categorization,Madison,Wisconsim:AAAI Press,1998,509～5l6

[6]宫秀军,刘少辉,史忠植.一种增量贝叶斯分类模型.计算机学报,2002,25(6):645～650

[7]Nadeem Ahmed,Syed Huan.Incremental learning with support vector machines,IJCAI[c],Stockholm,Sweden,1999.

[8]姜卯生,王浩,姚宏亮.朴素贝叶斯分类器增量学习序列算法研究.计算机工程与应用,2004,14:57～59

加权朴素贝叶斯分类论文篇4

二十世纪末到二十一世纪,全球的数据以爆炸式规模急剧增长。例如,到2005年底,已经有了82亿的网页收录到Googl中,中国的百度搜索引擎中的网页也增加到了10亿左右[1]。许多重要的知识内容规律就隐藏在这些数据的背后,人们可以利用这些重要的信息给决策者在进行科学分析时提供重要的依据。虽然,人们可以从这些信息中获取到了价值,带来方便,但是也产生了许多问题[2],如信息真假难辨,安全难以保证,信息过量,难以消化等问题。为了解决这些问题,必须找到一种有效的方法。数据挖掘技术能够从海量的数据中提取有价值的内容进行分析和理解学习,是一种有效的方法。

在现实生活中,数据基本上都是以二维表的形式存储在关系数据库中。每个数据表中都包含着各种对分类有影响的信息。因此,要想从多关系数据库中提取有价值的信息,就需要利用多关系数据挖掘技术对多关系表中的数据进行分析。多关系分类就是以多个相互联系的关系表为对象对其挖掘分类。根据前人已有的研究方法中,多关系分类可以总结为以下两种:一种是利用传统的分类方法Propositional Learning对多关系数据进行处理。但是传统的分类算法都是在单个表的基础上实现的,所以为了处理多关系数据,就需要将多关系数据转化成单个关系。然而,在转化过程中容易造成信息丢失[3],可能会丢失对分类影响比较重要的信息。另一种是结合多关系对传统的分类方法扩展更新,与传统的分类方法不同,这种方法不需要将多个关系表转化成单个关系,便能够直接处理多关系数据[4,5,6]。这种方法主要包含两个方面:一种是基于选择图的多关系分类,是从多关系数据挖掘的框架中得出ILP方法,并把表与表之间的关系转换成直观的选择图,如TILDE[7]、MRDTL[8];另外一方面是基于元组ID传播[4]的多关系分类,如Cross Mine[9]、GraphNB[10]、FAFS[11]等。

随着大型数据库的建立和机器学习的需要条件,新的问题开始出现了。特征选择作为机器学习的一个比较重要的预处理步骤,在分类任务中起着重要作用[12]。它根据某一个评价准则从原始特征集中选择出有效的子集,在之后的数据处理过程中能够提高处理性能,如分类聚类的性能[13]。在实际的应用中,多关系数据库的关系中有许多不相关的且冗余的属性,这些属性对分类任务的贡献很小,甚至没有贡献。因此,特征选择是多关系数据挖掘中一个必要的数据处理步骤。通过利用特征选择方法,我们能够提高分类的效果以及分类模型的可理解性。

1 多关系数据库知识

关系数据库描述了一组实体DB={E1,E2,…,En}以及实体之间的关系。这些实体是由一个目标表和若干个背景表或者非目标表,其定义如下:

定义1在一个关系表R中,若存在一个属性C,且对于C的每个分量ci都代表着一个实例的类标签,则把C称为R的类属性,由R.C表示。那么具有类属性的关系R就被称作目标关系,记为Rt,其余的则称为非目标表或背景表。

在关系数据库中,每两个表之间都能通过连接属性直接或者间接的相连。由于每一个关系表中都存在着一个主码,要想使得另一个表与该表直接相连,则在这个表中一定存在着相对应的外码。对于两个间接相连的关系表,它们之间是通过外码与外码的方式相连。以PKDD CUP99金融数据为例,图1是其数据库中各关系的连接结构。在此多关系数据库中,loan为目标表,其余的七个表则是背景表,背景表根据连接属性直接或者间接地与目标表相连。

不同于单表结构的简单性,多关系数据库的结构设计、关系模式等都是非常复杂的,尤其是关系数据库中各表之间复杂的关系对分类任务有很大的影响。根据图1可以看出,每条边可能会导致许多重复的连接操作,没有意义的语义关系。

为了能够简单明了地表示各关系表之间的关系,我们使用语义关系图来表示。

定义2语义关系图SGR是一种有向无环图SRG(V,E,W),其中,V是对应于数据库中关系表的顶点集合。E是有向边,并且每个边(v,w)代表通过直接连接这两个表把表w连接到v表上。W是关系表中所有属性的集合,其中每个属性连接两个表。我们把这种属性称为连接属性。

语义关系图以目标表为起点,表与表之间的连接路径有两种:一种是主码到外码的连接;另一种是外码到主码的连接。总的来说,语义关系图不仅描述了数据库中关系表之间的关系,而且使这种关系更加的简单明了。它的总体形状类似于数据库中的ER图。图2就是图1对应的语义关系图,促进了关系间虚拟连接的过程,就像整个算法的一个流程图。

2 特征选择

特征选择的研究始于20世纪60年代初,在对其研究的过程中,通常假设特征与特征之间是相互独立的。由于当初设计的特征数目比较少,很多操作都凭借人为的经验来进行的,这样不仅具有很大的盲目性和局限性,而且花费代价还比较高,所得出来的结果也很不理想。20世纪90年代以来,人们已经进入一个信息化社会化的时代,信息技术的快速发展使得数据规模变得非常庞大,数据的维数也非常大。这使得信息处理的要求越来越高,人为经验的评价方法已经不能适应大规模数据了。因此,需要找到能够适应大数据且能够保证准确率等综合性能较好的特征选择方法。为了获得更好的结果,许多学者基于传统算法并结合相关领域对特征选择方法进行了改造,但是由于特征选择方法本身的多样性以及处理问题的复杂性,至今还没有一个固定的选择模式和有效的方法。

在以往的对特征选择的研究中,Yang等人[14]通过利用线性最小方差匹配法LLSF,并根据各个特征的取值情况对样本空间进行学习划分,其实验结果验证了该方法只适用于特征分布平衡的时候,而对于特征分布和类属性分布不平衡时,分类结果很不理想。Q.H.Hu[15]在信息论的基础上提出了基于信息熵的混合数据简约方法。L.Yu等在2003年提出的Fast Correlation Based Filter(FCBF)[16],该算法结合选择最优子集和特征相关权重法,来降低特征集之间的冗余性。He Jun等人在2008年提出的Feature and Relation Selection(FARS)[11]是通过关系表的不确定性评价(TSU)评估的。它同时采用特征选择和关系选择,有效的选择了一组小的相关特征集。

以上所描述的各种特征选择方法考虑到了特征与类标签的相关度,但忽略了特征之间的冗余度,这样不仅会降低分类的时间性能,精确度也有可能会降低。因此,本文提出了基于mRMR的多关系朴素贝叶斯分类算法MNB-mRMR。该算法通过利用基于互信息的最大相关最小冗余mRMR[17]的特征选择算法对多关系数据库中的多关系表进行特征选择,在每个关系表中都选择出对分类帮助最大的特征子集。在如何选择出最佳特征子集问题上,本文通过计算最大相关度与最小冗余度之间的信息差算子,并根据给定阈值对训练集进行训练,训练出最优子集,最后利用多关系朴素贝叶斯分类算法对选择后的多关系数据库进行分类验证。

3 基于mRMR的多关系朴素贝叶斯分类

3.1 相关知识

由于最大相关最小冗余的特征选择算法是在互信息的基础上提出的方法,本节将介绍互信息的相关知识。首先介绍信息熵的概念。熵这个术语源于热力学领域,而香农把熵这个概念引入信息理论中,故又被称为香农熵[18]。它是衡量信息的一种度量,在信息论的发展历程中起着非常重大的意义。

定义3如果一个离散随机变量ζ的概率分布为p=(p1,p2,…,pa),则它的熵H(ζ)定义为:

定义4如果(ζ,η)~p(x,y),那么η关于ζ的条件熵定义为:

互信息源于信息论,是衡量两个特征之间关联度的一个重要标准,其定义如下:

定义5设p(x),q(x)是X上的两个概率分布,那么它们的互熵定义为,实际上,互信息就是一种特殊的互熵它的定义如下:

对于两个随机变量ζ与η,它们的联合分布为p(x,y),边际分布分别为p(x)和p(y),那么ζ与η的互信息I(ζ,η)为:

且互信息与联合熵、条件熵的关系有:

3.2 最大相关与最小冗余

在机器学习与模式识别中,特征选择的目的是为了寻找最具有代表的特征集以使得分类的错误最小化。要得到最小误差通常需要通过计算类标签c与子空间Rm的最大统计相关量,就是所谓的最大相关。由于是基于互信息的特征选择算法,所以首先要解决的问题就是互信息计算,根据3.1节的介绍,对于两个随机变量X和Y:

根据式(1)、式(2)、式(4)就可以得到特征xi与类标签c的互信息I(xi,c),即特征与类标签的相关度。最大相关则是选出满足下面等式的特征的方法:

依据式(4)和式(5)便可以实现最大相关。最大相关最小冗余算法就是对于给定的原始特征集,依据最大相关最小冗余准则对原始特征集X中的特征与类标签之间的互信息大小进行排序并把结果放入目标集R。

但是部分好的特征组合却不一定能得到好的分类效果。因为,影响分类效果的因素不仅仅表现在特征与类标签的相关度上,还要表现在特征与特征之间的冗余度。所以选择相互排斥的特征时,下面的最小冗余条件也可以添加进去:minR(S),R息=|的S1方|2式∑xi,来xj∈实SI(现xi。,xj),最小冗余则可以通过式(4)最小化互信

将最大相关与最小冗余结合起来就是所谓的“最大最小冗余准则”,于是便产生如下算子maxΦ(D,R),Φ=D-R,即信息差(MID)算子▽MID。其中Φ(D,R)用来表示D和R的联合关系。现在把最大相关最小冗余准则问题转化为了最大化信息差算子▽MID的问题,假设S中已经包含了m-1个特征,那么S的第m个特征就是那个能使下面算子最大的那个特征:

即mRMR特征选择问题转化为了计算信息差算子▽MID的问题。因此,利用mRMR算法进行特征选择的过程就是依据▽MID的大小来对各个特征进行排序然后进行筛选的过程。

由于在多关系数据库中,只有目标表有类标签,而非目标表中没有类标签,要想计算非目标表中特征的互信息以及信息差算子▽MID,必须利用元组ID传播技术[9]。通过这种虚拟连接技术,元组IDs以及类标签才能从目标表传递到非目标表中。在计算出每个关系表中特征的最大相关最小冗余的信息差算子▽MID之后,根据信息差算子对每个关系表的特征进行选择,选择出最终用于分类的最优特征集。这些选择出来的特征集被用于多关系朴素贝叶斯分类。

3.3 多关系朴素贝叶斯分类

朴素贝叶斯是利用统计学中的贝叶斯定理来对样本进行分类的一种简单概率的分类方法。它的原理简单,易于理解。其思想基础是对于一个待分类的样本,通过计算它属于各个类别的概率值来确定概率值最大的那个类别就是该样本的最终类别。贝叶斯分类应用非常广泛,可应用到各种领域,如对垃圾邮件的过滤[19]、人脸识别[20]等。起初,朴素贝叶斯分类只应用于单表数据,后来被扩展到直接处理多个关系表。

对于多关系的朴素贝叶斯,假设t是目标表,s则是与其相连的另外一个关系表,对于表t中的一个元组x:X=(x1,x2,…,xn),s中有p个元组能够与x相连接。这些p个元组是(yk1,yk2,…,ykp),其中每个元组ykl由r个值表示:ykl=(ykl1,ykl2,…,yklr),然后,元组x的类标签的计算如下:

3.4 MNB-mRMR算法描述

本节将对基于最大相关最小冗余的多关系朴素贝叶斯分类算法MNB-mRMR进行详细的描述。首先给出该算法中所涉及的一些符号和函数的意义及功能:D表示的是关系数据库;Rt表示目标表,Ri表示其他关系表即非目标表;集合S是空集,用来存放所选的最优特征集;μ表示的是给定的有关信息差算子▽MID的阈值;CreateRelation Graph(G)函数的功能是根据多关系数据库的连接关系构建语义关系图,该语义关系图使得这些多关系表之间的关系更加清楚明了。Propagate(Ri,Rt)函数表示将目标表中的类标签和ID传递到非目标表中以便对非目标表中的特征进行评估。SRi表示关系表Ri最终所选的特征集。

MNB-mRMR算法的具体描述如下:

算法:MNB-mRMR

输入:目标表Rt,其它关系表Ri(i=1,2,…,n),集合S,阈值μ

输出:SRi,每个关系表所选的特征集

step1:CreateRelation Graph(G);

step 2:Propagate(Ri,Rt);

step3:

a)对于每个关系表Ri,根据式(4)计算每个特征与类标签的互信;

b)将具有最大互信息值的特征加入S中;

c)根据式(4)和式(6)计算其余特征的信息差算子▽MID;

d)根据每个特征的▽MID值与给定阈值μ删除小于μ的特征,得到SRi;

step 4:利用多关系朴素贝叶斯分类算法对最终进行特征选择后的关系表进行分类验证。

本文利用mRMR进行特征选择的过程转化成了根据特征信息差算子的大小进行筛选的过程。在step3中,首先计算各个特征与类标签之间的互信息,代表了各个特征与类标签之间的相关度。而我们的目标是为了得到相关度高且冗余性小的特征集,因此,首先将关系表中与类标签互信息最大的那个特征加入空集S中,在计算加入其余特征时计算该特征的信息差算子,之后根据最大相关与最小冗余的信息差算子的大小与给定阈值大小,删除小于给定阈值的特征,将大于阈值的特征加入集合S中。最后利用多关系朴素贝叶斯分类算法进行测试验证。

4 实验结果与分析

为了验证MNB-mRMR算法的有效性,实验是在windows XP操作系统完成的,CPU是Intel(R)Core(TM)2 Duo E75000 2.93 GHz,内存是1.96 GB。开发环境为Java平台,编译运行环境是jdk1.6。数据存储工具使用的是Mysql数据库。数据集使用的是PKDD CUP 99金融数据集,该金融数据库是多关系挖掘中常使用的数据集,能够有效地对算法进行实验验证。数据集共有几百万条记录,共包含8个关系表,一个目标表loan,具有是否贷款的类标签,另外7个表示辅助表,与目标表直接或者间接相连。

4.1 阈值设定

在本节中,主要讨论实验室中所涉及的参数设置问题。本节中所要讨论的参数是特征的最大相关与最小冗余的信息差算子μ,因为在MNB-mRMR算法中,需要根据最大相关与最小冗余的信息差算子的大小与给定阈值μ的大小,删除小于给定阈值的特征。为了选出最优特征集以得到高的分类精确度,本文通过手动设定不同阈值,选择那些信息差算子▽MID大于给定阈值的特征集。对于不同的阈值,整个算法的分类准确率和时间性能也会有不同。图3表示了在信息差算子μ取不同的值时,该算法的分类精确度的变化。该分类精确度基本上处于一个先上升后下降的趋势,并在μ=-0.01左右,分类精确度最高。因此,在本文的实验中,我们选取-0.01作为信息差算子的阈值,根据各个特征的信息差算子的值选出大于-0.01的特征集。

4.2 分类性能比较

为了验证MNB-mRMR算法的有效性,本文将该算法与TILDE算法、Graph-NB算法进行了比较,实验结果如表1所示。在表1中,可以看出MNB-mRMR算法相较于TILDE算法、Graph-NB算法以及FARS算法,分类准确率都要高。MNB-mRMR算法既考虑到特征与类标签的相关度,又考虑到特征与特征之间的冗余度,将这两者结合起来能更充分、更准确地评估特征。因此,MNB-mRMR算法在分类准确度上会高于另外三种分类算法。

5 结语

加权朴素贝叶斯分类论文篇5

许多人把数据挖掘视为另一个常用的术语:数据中的知识发现。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的, 但又是潜在的、有用的信息和知识的过程。

本文利用数据挖掘中的朴素贝叶斯分类技术来研究鸢尾花数据集中有关于鸢尾花分类问题。以鸢尾花数据集为对象, 尝试通过数据挖掘中的朴素贝叶斯分类技术对数据进行分析, 实现对鸢尾花所属分类进行预测, 发现鸢尾花所属分类与鸢尾花各项数据之间的联系, 有助于对鸢尾花的培养进行管理。

2朴素贝叶斯分类算法

假设每个数据样本用一个n维特征向量来描述n个属性的值, 即X={x1, x2, ..., xn}, 假设有m个类, 分别用C1, C2, ..., Cm表示。给定的一个未知的数据样本X (没有标明属于哪个类) , 根据贝叶斯定理得:

undefined

P (xn|Ci) 都可以从训练数据集求得。

根据此方法, 对于类别未知的样本X, 可以先分别计算X属于每一个类别ci的概率。

P (X|ci) *P (ci) , 然后选择概率最大的类别作为其类别。

若朴素贝叶斯分类算法将未知数的数据样本X分配给Ci, 则需要满足:

P (|X) > P (|X) , P (ci| X) >P (cj|X) , 1≤j≤m, i≠j

从理论上来讲, 朴素贝叶斯分类算法与其他算法相比有着最小的错误率, 在实践中朴素贝叶斯分类算法还可以和神经网络算法和判定树等分类算法相媲美, 并且它的适应性也很强, 执行效率高, 在给定的N个属性的M个训练集, 学习时间的复杂度为O (N*M) , 这使得它在现实中有着广泛的应用。

3实例

鸢尾花数据集中数据属性分为花萼长、花萼宽、花瓣长、花瓣宽和所属分类5项。为了编程方便, 使用calyx_length表示花萼长、calyx_width表示花萼宽、petal_length表示花瓣长、petal_width表示花瓣宽、category表示所属分类如表1所示。

鸢尾花的类别分为3种:Iris-setosa、Iris-versicolor、Iris-virginica, 我们从鸢尾花数据集中选取60个数据样本作为训练数据集 (可随机选取, 这里为了实验计算方便, 每种类别均选取了20个样本) , 预测一个未知的数据所在分类。

若从预测数据集中读出如下数据 (5.4, 3.7, 1.5, 0.2) , 其中对应的4个属性类别分别为花萼长 (calyx_length) 、花萼宽 (calyx_width) 、花瓣长 (petal_length) 、花瓣宽 (petal_width) 。3个分类类别分别为setosa (用C1表示) , versicolor (用C2表示) , virginica (用C3表示) 。

朴素贝叶斯分类算法的步骤如下:

(1) 计算训练数据集中每个种类所占的比例。

因为60个训练数据集中每个种类均选取了20个样本, 所以在训练数据集中对于鸢尾花的3个种类出现的概率为:

P (setosa) =P (versicolor) =P (virginica) =1/3。

(2) 计算每个属性在训练数据集中的条件概率P (X|ci) , (i=1, 2, 3)

从每个预测属性值可以得到如下数据:

(3) 求最大后验概率P (Ci|X) 。

根据贝叶斯定理后验概率可以通过求先验概率来得到, 即P (X|ci) *P (ci) , 这里可以得到如下数据:

(4) 判断P1, P2, P3的大小:Max (P1, P2, P3) 。

在这里Max (P1, P2, P3) =P1, 所以我们把预测数据分类在P1类, 即Iris-setosa类别。实际上预测数据的类别就是Iris-setosa。如果Max (P1, P2, P3) =P2, 那么分在versicolor类, 如果Max (P1, P2, P3) =P3那么分在virginical类。我们通过这个过程说明如何使用朴素贝叶斯分类算法对未知数据进行分类, 达到了数据挖掘的目的。

4结束语

随着计算机技术的发展, 数据挖掘越来越受到研究人员的关注, 而分类算法中的朴素贝叶斯分类算法以其简单的算法思想、较高的精确度等优点成为挖掘领域热门的研究方向。朴素贝叶斯分类算法是建立在各个属性之间的相互独立性假设的前提下进行的, 这种假设在现实中是很少出现的。朴素贝叶斯分类算法在属性之间没有那么严格的条件下也能发挥比较好的性能, 所以朴素贝叶斯分类算法在证券、消费、教育、银行等行业中占有一席之地。

参考文献

[1]李志刚, 马刚.数据仓库与数据挖掘的原理及应用[M].北京:高等教育出版社, 2008.

[2][美]PANG-NING TAN, MICHAEL STEINBACH, VIPIN KU-MAR.Introduction to Data Mining[M]北京:人民邮电出版社, 2006.

[3][美]WALTER SAVITCH, Absolute Java[M], 北京:清华大学出版社, 2008.

[4]李艳, 刘信杰, 胡学刚.数据挖掘中朴素贝叶斯分类的应用[J].潍坊学院学报, 2007 (4) .

加权朴素贝叶斯分类论文篇6

1 中文文本预处理

1.1 分词预处理

在文本的组织上, 中文与以英语为代表的欧美语言有着很大的不同, 在西方语言中, 词与词是使用空格隔开的, 因此不需要进行分词处理, 而在中文文本中, 字、词是连在一起的。因此, 分词的难度较大。中文分词技术面临的两个最大问题是歧义切分和未登录词识别[1]。本文采用中科院的汉语词法分析系统ICTCLAS完成这项工作。该系统采用统计方法和规则方法相结合的方式, 基于N- 最短路径的方法对中文文本进行无歧义文本初切分, 然后通过多层隐马尔可夫模型算法进行未登陆词识别, 取得了非常好的分词效果。系统分词正确率高达97% 以上, 未登陆词识别召回率高达90%。

1.2 数据清洗

经过分词处理的文本, 并不是所有的特征都对构造向量空间模型和分类有帮助, 相反, 将对文本分类没有帮助的词作为特征项, 会对分类的精度造成很大的影响。另外, 去停用词可以很大程度上减小特征项的数量, 对文本降维具有很大帮助, 所以在构造向量空间模型前, 要对分类无帮助的词进行尽可能彻底的清理。本系统是在词性标注的基础上进行数据清洗的。经过分词处理后, 对于标点w、助词u、连词c、介词p和量词q等进行清洗。

1.3 去停用词

停用词主要是指文本中存在的助词、副词、连词、代词、介词、叹词、量词和数词等。例如:助词中的“的, 得, 地, 吧, 呢”;副词中的“非常, 很, 十分, 都”。

去停用词在技术上实现并不复杂, 只需建立一个停用词词典, 将在分词后每个词与停用词词典内的词条进行匹配, 如果匹配成功, 则将该词去掉。

2 文本特征选择

特征选择是为了提高文本分类的效率, 减少计算复杂度。文本特征选择通常通过判断特征词进行。常用的方法有:文档频率、信息增益、互信息、统计量和期望交叉熵等[3]。本文采用信息增益和文档频率方法进行特征词判断。

2.1 信息增益

信息增益是一个基于熵的评估方法, 定义为某特征项在文本中出现的前后信息熵之差。对于特征项w和文档类别c, IG考虑c中出现和不出现w的文档频率来衡量w对于c的信息增益。w对于c的信息增益越大, 说明特征项w对于类别c越重要, 贡献越大。信息增益评估函数定义如式 (1) 所示。

式 (1) 中, m表示类别数, P (ci) 表示ci类文档在语料中出现的概率, P (w ) 表示语料中包含特征项w的文档频率, P (ci|w) 表示文档包含特征项w时属于ci类的条件概率, P () 表示语料中不包含特征项w的文档频率, 率P (。ci|) 表示文档不包含特征项w时属于ci类的条件概

2.2 文档频率

文档频率 (document frequency, DF) 是含特征项的文本数目。其思想是:DF值低于某个阈值的词条是低频词, 它们不含或含有较少的类别信息。并从特征空间中去掉这些低频词, 从而降低空间维数提高分类的精度。

3 文本分类

文本分类用一个已标记类别的文本数据集来训练分类器, 这个文本数据集称为训练集, 然后用训练好的分类器对未标记类别的文本进行分类。比较常用的文本分类算法有, KNN算法、SVM算法和贝叶斯算法等。

在许多场合, 朴素贝叶斯 (Naïve Bayes, NB) 分类算法可以与决策树和神经网络分类算法相媲美, 该算法能运用到大型数据库中, 且方法简单、分类准确率高、速度快。从理论上讲, 与其他所有的分类算法相比, 贝叶斯分类具有最小的出错率, 在其类条件独立的假定成立的前提下, 它是最佳的分类算法。然而在很多情况下, 其类条件独立的朴素假定并不能成立, 但实践证明, 即便如此, 它在很多领域中仍然能够获得较好的分类结果。

朴素贝叶斯方法 (Naïve Bayesian) 将训练文档分解成特征向量和决策类别变量, 假定特征向量的各分量间相对于决策变量是相对独立的, 也就是说各个分量独立地作用于决策变量。朴素贝叶斯的属性间条件独立假设使得对联合概率的计算大大简化, 公式如 (2) 所示。

构造分类器模块是训练过程的关键模块, 应用贝叶斯分类算法, 构造具体的分类器。训练过程一般比较耗时, 系统将所有文本训练一次后, 把特征项的相关信息等存入文件中。在训练一次后, 测试时直接从配置文件中读入相关信息而不需要再次训练。从而节省时间。

假设训练语料包含N个文本D={D1, D2, Dn}, 这些文本分属于M个文本类别C={C1, C2, Cm}, 训练语料集共有L个文本特征词W={W1, W2, WL}。

当文本Di属于类别Cj时, 则有P (Cj|Di) =1, 否则P (Cj|Di) =0。如果给定文本类别变量, 则文本类别Cj的先验概率估计按公式 (3) 计算。

若用F (Wk, Di) 表示特征词Wk在文本Di中出现的次数, 则特征词Wk在类别Cj中的概率估计按公式 (4) 计算。

任何文本都可视为一系列有序排列的特征词的集合, 在朴素贝叶斯模型中假定特征向量的各分量间相对于决策变量是相对独立的, 则类别Cj中产生文本Di的概率按公式 (5) 计算。

根据测试文本特征数据计算测试文本属于每个类别的概率, 然后按照最大概率给测试文本分类。测试文本Di属于类别Cj的概率按公式 (6) 计算。

摘要：本文针对中文文本分类的特点, 采用中科院汉语词法分析系统ICTCLAS对文档进行分词, 并进行数据清洗和过滤停用词, 运用信息增益和文档频率特征选择算法对文档进行特征选取。

关键词：中文分词,本文分类,信息增益,朴素贝叶斯算法

参考文献

[1]陈平.基于SVM的中文文本分类相关算法的研究与实现[D].西安:西北大学, 2008

[2]余芳.一个基于朴素贝叶斯方法的Web文本分类系统:web CAT[J].计算机工程与应用, 2004 (7) .

加权朴素贝叶斯分类论文篇7

关键词：朴素贝叶斯分类器,k-均值聚类,数据挖掘

1 引言

数据挖掘[1]是从大型数据集中将隐含在其中的、人们事先不知道的、对决策有用的知识获取的完整过程。分类是数据挖掘和机器学习中一个重要的研究课题, 它旨在生成一个分类函数或分类模型, 由该模型把数据库中的数据项映射到某一给定类别中, 从而实现对数据的分类。朴素贝叶斯分类器[2] (naive Bayesian classifiers) 是以概率密度函数为基础, 描述分类系统中条件属性和分类属性之间的映射关系。贝叶斯分类器的优点是出错率较小, 但实际上在使用过程中主要存在两个方面的限制:一是先验概率定义困难;二是类别条件独立问题:即独立性假设经常是不满足的。并且独立性假设在一定程度上限制了朴素贝叶斯分类器的适用性, 当处理的数据维数较多, 且数据量较大时, 朴素贝叶斯分类器的效率是偏低的, 且其准确率也有待提高。

针对上述限制, 提出结合k-均值聚类与贝叶斯方法进行分类知识挖掘的解决方案和实现方法。该方法先在数据预处理过程中采用k-均值算法, 得到相互独立的核心属性, 后进行贝叶斯方法的分类知识挖掘。由于k-均值聚类理论的引入, 改善了贝叶斯方法中属性独立性的限制, 提高了分类的准确率。并且由于k-均值算法的引入, 扩大了朴素贝叶斯分类器的应用领域。

2 k-均值聚类算法

2.1 聚类分析

聚类是一个将数据集划分为若干组或类的过程, 并使得同一个组内的数据对象具有较高的相似度;而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。为了实现属性聚类, 通常将一块数据区域A描述成一张表, 在表中有n个对象, 主要是用来存放所有n个对象彼此之间所形成的差异。有矩阵

其中d (i, j) 表示对象i和j对象之间的差异 (或不相似程度) 。通常d (i, j) 为一个非负数;当对象i和j对象非常相似或彼此“接近”时, 该数值接近0;该数值越大, 就表示对象i和对象j越不相似。由于d (i, j) =d (j, i) 且d (i, i) =0, 因此就有上式所示矩阵。

2.2 k-均值算法

k-均值算法以要生成的簇的数目k为输入参数, 把n个对象划分成k个组 (k≤n) , 每个组表示一个簇。首先, 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类;然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数, 具体定义如下:

其中E为数据库中所有对象的均方差之和;p为代表对象的空间中的一个点;mi为聚类Ci的均值。

k-均值算法试图找到使平方误差准则函数最小的簇。当潜在的簇形状是凸面的, 簇与簇之间区别较明显, 且簇大小相近时, 其聚类结果较理想。该算法复杂度为O (nkt) , 其中n为所有对象的数目, k为簇数, t是迭代的次数, 通常k<<n, t<<n。因此, 对处理大数据集合, 该算法非常高效, 伸缩性好。

3 朴素贝叶斯分类器

每个数据样本均是由为一个n维特征向量, X={x1, x2, …, xn}来描述其n个属性 (A1, A2, …, An) 的具体取值;假设共有m个不同类别, C1, C2, …, Cm。给定一个未知类别的数据样本X, 分类器在已知X情况下, 预测X属于事后概率最大的那个类别。也就是说, 朴素贝叶斯分类器将未知类别的样本X归属到类别Ci, 当且仅当:P (Ci|X) >P (Cj|X) , 对于1≤j≤m, j≠i。根据贝叶斯定理:

根据此方法, 对一个未知类别的样本X, 可以先分别计算出X属于每一个类别Ci的概率P (X|Ci) P (Ci) , 然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为

4 基于均值的朴素贝叶斯分类算法

基于k-均值算法的朴素贝叶斯分类技术就是利用k-均值算法来研究各列属性之间存在的隐含的依赖关系, 将列属性值进行融合, 达到数据预处理目的, 最后再基于朴素贝叶斯方法进行分类。其处理步骤如下:

1.数据预处理:

(1) 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类

(2) 再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;

(3) 不断重复 (1) 、 (2) 直到标准测度函数

通过满足方差最小标准的k个聚类, 将其中相关系数较大的属性合并成一个综合属性。这样随后进行的贝叶斯分类中的各个属性间就能尽可能达到属性独立。

2.基于朴素贝叶斯分类算法进行分类挖掘

通过k-均值算法, 改善了条件属性独立性的限制, 符合朴素贝叶斯分类器的要求。由此可得到改进后的基于k-均值的朴素贝叶斯分类算法:先根据互不相关的核心属性集, 求取类的先验概率P (Ci) ;再由类条件独立的假定, 计算;最后通过上述分类器计算式, 得出分类结果。

5 实验结果及分析

本文中使用NBC表示朴素贝叶斯分类器, KMBC表示基于k-均值算法的朴素贝叶斯分类器。为了测试算法KMBC的效果, 选用了UCI机器学习数据库中的7个典型数据库实例, 数据集的基本信息见表1。实验在WINDOWS XP, J2SDK的平台下完成, 首先补齐决策表, 离散化处理, 在测试过程中同样采用交叉验证法;最后将得到的两种结果进行比较, 结果见表1.

由实验过程及实验结果分析发现, 实验所用的数据实例中, KMBC的分类准确率优于NBC。在算法运行时间上, KMBC略高于NBC, 两者之间运行时间的差别并不明显。

6 结束语

针对朴素贝叶斯分类器的条件独立性假设的限制, 本文提出了一种基于k-均值的朴素贝叶斯算法, 先利用k-均值算法对数据进行预处理, 通过属性合并改善条件属性间的依赖性, 找到一组最近似独立的属性结果, 以符合朴素分类器的算法要求。实验结果表明, 改进后的算法可以达到更精确的分类效果。并且当数据量很大, 而各维属性之间又存在隐含关系是, 改进后的算法是处理这些问题行之有效的方法。

参考文献

[1]han j w.数据挖掘概念与技术[M].北京:机械工业出版社, 2001

【加权朴素贝叶斯分类论文】推荐阅读：

朴素的美丽06-01

关联加权05-28

模糊加权06-10

指数加权10-01

小学中秋节活动方案:让月饼的外衣朴素起来09-08