加权朴素贝叶斯算法及其weka程序分析20151216A.pdf

《加权朴素贝叶斯算法及其weka程序分析20151216A.pdf》由会员分享，可在线阅读，更多相关《加权朴素贝叶斯算法及其weka程序分析20151216A.pdf（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析1 1局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka 程序分析程序分析1 1张伟(北京交通大学计算机与信息技术学院，北京，100044)摘要：摘要：局部加权朴素贝叶斯是一种改进朴素贝叶斯算法独立性假设缺陷的算法通过实验证明加权朴素贝叶斯算法具有很好的效果，比朴素贝叶斯和 K 最近邻方法的效果都要好。关键字关键字：局部加权，朴素贝叶斯在机器学习中直接使用贝叶斯定理是不现实的，因为训练集不足以获得全概率分布的准确估计。朴素贝叶斯分类算法是一种优秀的分类算法，但由于其必须满足属性独立性假设，

2、使得该算法具有了一定的局限性。局部加权朴素贝叶斯算法为了从该算法的弱点独立性假设入手，对朴素贝叶斯算法进行改进，提出了一种基于 K 近邻法的局部加权朴素贝叶斯分类算法。实验表明该算法提高了分类的可靠性与准确率。1 1局部加权朴学习局部加权朴学习局部加权学习（locally weighted learning，简称 LWL），既可用于回归问题（如局部加权线性回归），又可用于分类问题（如局部加权朴素贝叶斯）。局部加权分类是一种比较新的方式，在一些实验中表现出更高的准确率。分类过程需要对训练实例根据它们离测试实例的距离进行加权。在传统的加权学习算法中通常使用欧几里德距离来度量实例间的距离。局部加权学

3、习是方法是懒惰学习（lazy learning）和基于记忆学习（memory-basedlearning）的一种形式，它需要存储数据集，当需要对一个新实例进行处理，通过距离函数计算训练实例和测试实例的距离以确定和测试实例相关的训练实例的加权集合构，然后用该集合构造一个新的模型来处理新实例。1本文是多年来经过无数次修正的版本，其中融入了许多学生的建议而且也是时时更新的特别地，本文仅供学生学习使用，并不适合于发表在任何公开媒体上，也不允许任何学生将之存放到互联网上另外，与一般学术论文不同，本文许多地方采用第 1 人称进行讲述2 2局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWek

4、a程序分析程序分析1.11.1 局部加权朴素贝叶斯局部加权朴素贝叶斯原则上，贝叶斯定理保证了对一个给定属性值向量的新实例的类标的最优预测。不幸的是，直接将贝叶斯定理用于机器学习是不现实的，因为不可避免训练数据不足以获得全概率分布的精确估计。为了使推理可行必须先满足一些独立性假设。朴素贝叶斯方法把独立性假设发挥到了极致，假定属性对于给定的类标值是统计上独立的。虽然这个假设在实际中并不成立，朴素贝叶斯在许多分类问题上表现的非常好。此外，朴素贝叶斯计算效率训练在实例个数和属性个数上都是线性的且易于执行。机器学习相关文章开始关注朴素贝叶斯学习算法归功于Clark 和 Niblett 的有关 CN2 规

5、则学习的文章。在这篇文章中他们在实验评估中使用了一个简单的贝叶斯分类器（朴素贝叶斯）作为对比，朴素贝叶斯分类器比其他更成熟的学习算法表现更好。虽然已经对朴素贝叶斯在一些违反属性独立假设的情况下具有良好表现进行了解释，但一个基本事实没有改变，那就是当独立性假设不成立时，概率估计精度和效果都会下降。很多用于提高朴素贝叶斯效果的方法被提出，其中许多方法在保持原算法的简单性和计算高效性的同时降低算法的“朴素性”。Zheng 和 Webb 在这个领域的工作进行了很好的总结。最有效的方法包括：贝叶斯网络的限制子类、结合了属性选择的朴素贝叶斯或者将朴素贝叶斯模型结合到其他分类器（例如决策树）。事实证明局部加

6、权的朴素贝叶斯算法具有很好的效果，比朴素贝叶斯和 K 最近邻方法的效果都要好。我们用来加权朴素贝叶斯的方法是从一项源于用来对非线性回归模型进行估计的技术中借鉴而来，线性回归模型适合基于加权函数的数据，这个加权函数用来处理要进行预测的实例。由于加权函数随着每个需要处理的实例改变，所以由此产生的估计是非线性的。本文我们研究了用于分类的局部加权学习，局部加权学习在机器学习中没有得到很多关注。Loader（1999）和 Hastie(2001)从统计学角度研究了所谓的“局部可能性”方法，包括局部加权线性逻辑回归和局部加权密度估计。朴素贝叶斯是用密度估计进行分类的例子。和逻辑回归相比它具有优势：在属性个

7、数上是线性的，这是这种方法在具有多属性的学习问题上具有更高的计算有效性。我们使用朴素贝叶斯的方式和在局部加权线性回归中使用线性回归的方式一样：一个局部朴素贝叶斯模型适合于用来预测类属性实例（我们称这个实例为测试实例）的领域中的数据集的子集。此领域中的训练实例是加权的，距离测试实例越远的例子具有的权重越小。然后一个分类器可以从朴素贝叶斯模型获得，朴素贝叶斯模型将测试实例的属性值作为输入。用来训练每个局部加权朴素贝叶斯模型的数据集的子集由最近邻算法决定。用户指定的参数 k 控制使用多少个实例。这通过使用具有紧支撑的加权函数和为 k 最近邻的距离设定宽度（或带宽）来实现。局部加权朴素贝叶斯算法及其局

8、部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析3 31.21.2属性处理属性处理令 di表示测试实例到第 i 个最近邻点 xi的欧几里德距离。我们假设所有属性在计算距离前都被标准化为 0 到 1 之间的数值，名称型属性都进行二值化处理。令 f 为一个加权函数对所有的 y 1 有 f（y）=0。接下来我们设每个实例xi的权重i为i fdi/dk这意味着实例 xk的权重为 0，所有距离测试实例很远的实例的权重都为 0，和测试实例相同的实例权重为 1。所有具有以上性质的单调递减函数都可以作为加权函数。在我们的实验中使用的如下线性加权函数 flinear，对于 y 0,1，有flinear

9、y1 y即，我们令权重随距离线性递减。更高的 k 值导致模型对数据中的波动变化很小，而较小的 k 值使得模型和数据保持一致。过小的 k 值可能导致模型和数据中的噪声匹配。我们的实验表明这种方法对于 k 值的选择在不是特别小的情况下是不敏感的。有一点需要说明。为了避免零频率的出现，我们在实现朴素贝叶斯的过程中使用Laplace 估计对名称型属性的条件概率进行估计，这与加权方案进行交互。我们的经验发现适当的划分权重可以使得用来生成朴素贝叶斯模型的实例的总权重逼近 k。假定有 r 个训练实例 xi满足 didk。那么重新调整的权重计算公式如下i 其中 n 是训练实例的总个数。irnq0q朴素贝叶斯计

10、算具有属性值 a1，a2，a3，am测试实例的类属性 cl的后验概率的公式如下：pcl|a1,a2,.,ampclmj1paj|clmoq1pcqj1paj|cq其中 o 是类属性的总数。等式右边的单个个体的概率根据加权后的数据进行估计，类属性cl的先验概率为1in0Iciclipcloin0i其中 ci是序号为 i 的训练实例的类属性值，当x=y 时指标函数 I（x=y）为 1，其他为 0。假设属性 j 是名称型的，aj（属性在测试实例中对应的值）的条件概率计算公式如下：paj|cl1in0Iaj aijIciclinjin0Iaj aiji4 4局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯

11、算法及其 WekaWeka程序分析程序分析其中 nj属性 j 取值的个数，aij是属性 j 在实例 i 中的值。如果数据中包含数值属性，我们用Fayyad 和 Irani 的基于 MDL 准则的离散化方案，将结果视作名称型属性，也可以做一个名称型假设，基于加权数据集对均值和方差进行估计。我们将给出两种方法的实证结果。2 2加权朴素贝叶斯的实现分析加权朴素贝叶斯的实现分析我们将详细分析 Weka-3-6-13平台下，LWL.java源代码之中的所有成员变量与方法。2.12.1成员变量成员变量在 Weka-3-6-13 平台下的 LWL.java 类共定义了 13 个成员变量，现逐一介绍所有成员变

12、量如下：（1）序列化 serialVersionUID简单来说，Java 的序列化机制是通过在运行时判断类的serialVersionUID来验证版本一致性的。在进行反序列化时，JVM 会把传来的字节流中的 serialVersionUID 与本地相应实体（类）的 serialVersionUID进行比较，如果相同就认为是一致的，可以进行反序列化，否则就会出现序列化版本不一致的异常。（2）训练实例集合 m_Train用于分类的训练实例的集合。（3）邻接点数目 m_kNN用来对核的带宽进行选择的邻接点数目。（4）加权核方法 m_WeightKernel目前选择使用的加权核方法。（5）布尔型变量

13、m_UseAllK用来决定是否对每个实例设置邻接点数目m_kNN。（6）抽象类对象 m_NNSearch用来设置使用的最近邻搜索算法。（7）五个静态最终变量 LINEAR、EPANECHNIKOV、TRICUBE、INVERSE、GAUSS、CONSTANT分别代表了五种不同可用的核权重方法。这五个静态最终变量代表了可使用核加权方法。（6）分类器 m_ZeroR以防当不能从数据集中建立分类器时有ZeroR 模型可用。ZeroR 指建立和使用 0-r 分类器类。可预测均值（数值型类）或模型（名称型类）。局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析5 52

14、.22.2辅助性的方法辅助性的方法在 Weka-3-6-13平台下的 LWL.java类共定义了 25 个方法，首先简单介绍这 25 个方法，然后对其中的 7 个方法我们做重点介绍。现逐一介绍所有方法如下：（1）类的说明信息 globalInfo()这个方法就是返回描述这个类的一串字符主要是对相应分类模型的说明。在浏览器（explorer）或 Weka 实验环境（experimenter）下，通过这串字符来显示这个类的功能。这个 方 法 的 实 现 机 制 依 赖 于 Weka.core 之 下 的 TechnicalInformation 类 与 TechnicalInformationHa

15、ndler 接口。这个方法主要用于：01:/*02:*Returns a string describing classifier.03:*return a description suitable for04:*displaying in the explorer/experimenter gui05:*/（2）列出参考文献所有著录项getTechnicalInformation()这个方法用于01:/*02:*Returns an instance of a TechnicalInformation object,containing03:*detailed information abo

16、ut the technical background of this class,04:*e.g.,paper reference or book this class is based on.05:*06:*return the technical information about this class07:*/（3）构造器 LWL()用来实例化一个决策树树桩分类器对象。（4）列出描述默认分类器的字符串defaultClassifierString()这个方法用于返回用于描述默认分类器的字符串。01:/*02:*String describing default classifier.0

17、3:*04:*return the default classifier classname05:*/（5）返回枚举对象 enumerateMeasures()这个方法用于返回其他测试名字的枚举对象01:/*02:*Returns an enumeration of the additional measure names03:*produced by the neighbour search algorithm.04:*return an enumeration of the measure names6 605:*/局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序

18、分析程序分析（6）返回命名的测试的值getMeasure(String additionalMeasureName)01:/*02:*Returns the value of the named measure from the03:*neighbour search algorithm.04:*paramadditionalMeasureName the name of the measure to query for05:*its value06:*return the value of the named measure07:*throws IllegalArgumentExceptio

19、n if the named measure is not08:*supported09:*/（7）返回枚举对象 listOptions()这个方法用于返回一个描述可使用选项的枚举类。01:/*02:*Returns an enumeration describing the available options.03:*04:*return an enumeration of all the available options.05:*/（8）解析一个选项列表 setOptions(String options)throws Exception这个方法用于：01:/*02:*Parses a

20、given list of options.03:*04:05:*Valid options are:06:*07:*-A08:*The nearest neighbour search algorithm to use(default:09:*weka.core.neighboursearch.LinearNNSearch).10:*11:*12:*-K<number of neighbours>13:*Set the number of neighbours used to set the kernel bandwidth.14:*(default all)15:*16:*-U

21、<number of weighting method>17:*Set the weighting kernel shape to use.0=Linear,1=Epanechnikov,18:*2=Tricube,3=Inverse,4=Gaussian.19:*(default 0=Linear)20:*21:*-D22:*If set,classifier is run in debug mode and局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析23:*may output additional info to the consol

22、e24:*25:*-W26:*Full name of base classifier.27:*(default:weka.classifiers.trees.DecisionStump)28:*29:*30:*Options specific to classifier31:*weka.classifiers.trees.DecisionStump:32:*33:*34:*-D35:*If set,classifier is run in debug mode and36:*may output additional info to the console37:*38:39:*40:*par

23、am options the list of options as an array of strings41:*throws Exception if an option is not supported42:*/7 7（9）返回字符串数组存放分类器的当前设置getOptions()这个方法用于获得分类器的当前设置。01:/*02:*Gets the current settings of the classifier.03:*04:*return an array of strings suitable for passing to setOptions05:*/（10）返回这些性质的简要

24、说明KNNTipText()这个方法用于：01:/*02:*Returns the tip text for this property.03:*return tip text for this property suitable for04:*displaying in the explorer/experimenter gui05:*/（11）设置的邻接点的数目setKNN(intknn)这个方法用于设置用于核带宽的邻接点数目。01:/*02:*Sets the number of neighbours used for kernel bandwidth setting.03:*The b

25、andwidth is taken as the distance to the kthneighbour.04:*05:*paramknn the number of neighbours included inside the kernel06:*bandwidth,or 0 to specify using all neighbors.8 807:*/局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析（12）返回邻接点数目 getKNN()这个方法返回用于核带宽设置的邻接点数目。（13）返回这些性质的简要说明weightingKernelTipText

26、()01:/*02:*Returns the tip text for this property.03:*return tip text for this property suitable for04:*displaying in the explorer/experimenter gui05:*/（14）setWeightingKernel(int kernel)这个方法用于设定将要使用的核加权方法，只能是六个方法（线性、抛物线、三立方体、逆、高斯、常数）之一。01:/*02:*Sets the kernel weighting method to use.Must be one of

27、LINEAR,03:*EPANECHNIKOV,TRICUBE,INVERSE,GAUSS or CONSTANT,other values04:*are ignored.05:*06:*param kernel the new kernel method to use.Must be one of LINEAR,07:*EPANECHNIKOV,TRICUBE,INVERSE,GAUSS or CONSTANT.08:*/（15）获得将要使用的核加权方法的整型值getWeightingKernel()（16）返回最近邻搜索算法的说明nearestNeighbourSearchAlgorith

28、mTipText()（17）返回正在使用的最近邻搜索算法getNearestNeighbourSearchAlgorithm()（18）设定用于寻找最近邻的最近邻搜索算setNearestNeighbourSearchAlgorithm(NearestNeighbourSearchnearestNeighbourSearchAlgorithm)（19）返回分类器的默认功能getCapabilities()（20）生成分类器 buildClassifier(Instances instances)（21）将提供的实例加入训练集updateClassifier(Instance instance)

29、将实例作为参数传给方法，然后这个方法将该实例加入训练集。01:/*02:*Adds the supplied instance to the training set.03:*04:*param instance the instance to add05:*throws Exception if instance could not be incorporated06:*successfully07:*/（22）计算测试实例类的概率distributionForInstance(Instance instance)这个方法用于计算给定的测试实例的类成员概率。01:/*局部加权朴素贝叶斯算法及

30、其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析9 902:*Calculates the class membership probabilities for the given testinstance.03:*04:*param instance the instance to be classified05:*return preedicted class probability distribution06:*throws Exception if distribution cant be computed successfully07:*/（23）返回分类器的描述to

31、String()这个方法将对字符串的描述作为字符串返回。01:/*02:*Returns a description of this classifier.03:*04:*return a description of this classifier as a string.05:*/（24）返回修订的字符串getRevision()（25）主方法用于测试这个类。01:/*02:*Main method for testing this class.03:*04:*paramargv the options05:*/2.32.3主要方法主要方法下面我们来详细介绍算法中的几个主要方法及：（1）p

32、ublic Enumeration listOptions()这个方法用于返回一个描述可使用选项的枚举类。01:public Enumeration listOptions()02:/实例化Vector对象，Vector类封装了一个动态的、允许再分派的Object数组03:Vector newVector=new Vector(3);04:/*Option:类型安全的方法：addElement（对象）属于原型载体，用来向对象尾部添加05:*元素。对泛型类型向量的引用要进行参数化。06:*/07:newVector.addElement(new Option(tThe nearest neigh

33、bour search +08:algorithm to use +(default:09:weka.core.neighboursearch.LinearNNSearch).n,10:A,0,-A);11:newVector.addElement(new Option(tSet the number of neighbours used12:to set13:+the kernel bandwidth.n1010局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析14:+t(default all),15:K,1,-K);16:newVector.addEl

34、ement(new Option(tSet the weighting kernel shape to17:use.18:+0=Linear,1=Epanechnikov,n19:+t2=Tricube,3=Inverse,4=Gaussian.n20:+t(default 0=Linear),21:U,1,-U);22:/23:Enumeration enu=super.listOptions();24:while(enu.hasMoreElements()25:newVector.addElement(enu.nextElement();26:27:/返回向量的所有组成元素的枚举28:re

35、turn newVector.elements();29:（2）public void setOptions(String options)这个方法主要用于分析一个给定的选项列表01:public void setOptions(String options)throws Exception 02:03:String knnString=Utils.getOption(K,options);04:if(knnString.length()!=0)05:setKNN(Integer.parseInt(knnString);06:else 07:setKNN(-1);08:09:10:String

36、 weightString=Utils.getOption(U,options);11:if(weightString.length()!=0)12:setWeightingKernel(Integer.parseInt(weightString);13:else 14:setWeightingKernel(LINEAR);15:16:17:String nnSearchClass=Utils.getOption(A,options);18:if(nnSearchClass.length()!=0)19:String nnSearchClassSpec=Utils.splitOptions(n

37、nSearchClass);20:if(nnSearchClassSpec.length=0)21:throw new Exception(Invalid NearestNeighbourSearch algorithm +22:specification string.);23:24:String className=nnSearchClassSpec0;25:nnSearchClassSpec0=;局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析26:27:setNearestNeighbourSearchAlgorithm(NearestNeighb

38、ourSearch)28:Utils.forName(NearestNeighbourSearch.class,29:className,30:nnSearchClassSpec)31:);32:33:else34:this.setNearestNeighbourSearchAlgorithm(new LinearNNSearch();35:36:super.setOptions(options);37:（3）public String getOptions()这个方法用来返回分类器的当前设置数组。01:public String getOptions()02:03:String superO

39、ptions=super.getOptions();04:String options=new String superOptions.length+6;05:int current=0;06:optionscurrent+=-U;optionscurrent+=+07:getWeightingKernel();08:if(getKNN()=0)&m_UseAllK)09:optionscurrent+=-K;optionscurrent+=-1;10:11:else 12:optionscurrent+=-K;optionscurrent+=+getKNN();13:14:optionscu

40、rrent+=-A;15:optionscurrent+=m_NNSearch.getClass().getName()+16:+Utils.joinOptions(m_NNSearch.getOptions();17:System.arraycopy(superOptions,0,options,current,18:superOptions.length);19:return options;20:（4）public String getOptions()这个方法返回分类器的默认的功能。01:public String getOptions()02:03:String superOptio

41、ns=super.getOptions();04:String options=new String superOptions.length+6;05:06:int current=0;07:11111212局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析08:optionscurrent+=-U;optionscurrent+=+09:getWeightingKernel();10:if(getKNN()=0)&m_UseAllK)11:optionscurrent+=-K;optionscurrent+=-1;12:13:else 14:options

42、current+=-K;optionscurrent+=+getKNN();15:16:optionscurrent+=-A;17:optionscurrent+=m_NNSearch.getClass().getName()+18:+Utils.joinOptions(m_NNSearch.getOptions();19:System.arraycopy(superOptions,0,options,current,20:superOptions.length);21:22:return options;23:（5）public void buildClassifier(Instances

43、instances)这个方法用来生成构造器01:public void buildClassifier(Instances instances)throws Exception 02:03:if(!(m_ClassifierinstanceofWeightedInstancesHandler)04:throw new IllegalArgumentException(Classifier must be a 05:+WeightedInstancesHandler!);06:07:08:/can classifier handle the data?09:getCapabilities().t

44、estWithFail(instances);10:11:/remove instances with missing class12:instances=new Instances(instances);13:instances.deleteWithMissingClass();14:15:/only class?-build ZeroR model16:if(instances.numAttributes()=1)17:System.err.println(18:Cannot build model(only class attribute present in data!),19:+us

45、ing ZeroR model instead!);20:m_ZeroR=new weka.classifiers.rules.ZeroR();21:m_ZeroR.buildClassifier(instances);22:return;23:24:else 25:m_ZeroR=null;局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析26:27:28:m_Train=new Instances(instances,0,instances.numInstances();29:30:m_NNSearch.setInstances(m_Train);31:

46、（6）public void updateClassifier(Instance instance)这个方法主要用于将实例作为参数传给方法，然后这个方法将该实例加入训练集。01:public void updateClassifier(Instance instance)throws Exception 02:03:if(m_Train=null)04:throw new Exception(No training instance structure set!);05:06:else if(m_Train.equalHeaders(instance.dataset()=false)07:th

47、row new Exception(Incompatible instance types);08:09:if(!instance.classIsMissing()10:m_NNSearch.update(instance);11:m_Train.add(instance);12:13:（7）public double distributionForInstance(Instance instance)这个方法用于计算给定的测试实例类成员的概率。01:public double distributionForInstance(Instance instance)throws02:Excepti

48、on 03:/default model?默认模型04:/*如果m_ZeroR不为空，则用其调用distributionForInstance（）方法求实例类05:*成员的概率，并作为返回值返回06:*/07:if(m_ZeroR!=null)08:return m_ZeroR.distributionForInstance(instance);09:10:11:if(m_Train.numInstances()=0)12:throw new Exception(No training instances!);13:14:15:m_NNSearch.addInstanceInfo(instan

49、ce);16:17:int k=m_Train.numInstances();18:if(!m_UseAllK&(m_kNN k)&19:!(m_WeightKernel=INVERSE|20:m_WeightKernel=GAUSS)1313141421:k=m_kNN;22:23:局部加权朴素贝叶斯算法及其局部加权朴素贝叶斯算法及其 WekaWeka程序分析程序分析24:Instances neighbours=m_NNSearch.kNearestNeighbours(instance,k);25:double distances=m_NNSearch.getDistances();26

50、:27:if(m_Debug)28:System.out.println(Test Instance:+instance);29:System.out.println(For+k+kept +neighbours.numInstances()+30:out of +31:m_Train.numInstances()+instances.);32:33:34:/IF LinearNN has skipped so much that distances.length)36:k=distances.length;37:38:if(m_Debug)39:System.out.println(Inst