基于改进的加权贝叶斯分类算法在空间数据中的应用
作者 :  杨敏 等

  摘要: 朴素贝叶斯算法是一种简单而高效的分类算法,但它的属性独立性假设,影响了它的分类性能。针对这个问题,提出一种基于属性约简的PLS加权朴素贝叶斯分类算法。该算法首先分析属性之间的相关性,通过属性约简选择一组近似独立的属性约简子集,提出改进的偏最小二乘回归加权朴素贝叶斯分类算法,实验结果表明,改进算法具有较高的分类准确度。并将改进的算法应用于边坡识别问题中。
  Abstract: Naive bayesian algorithm is a simple and effective classification algorithm, but its attribute independence hypothesis, influence its classification performance. According to this problem, the paper proposes a kind of attribute reduction based on PLS weighted simple bayesian classification algorithm. This algorithm firstly analyzes the relationship between attribute, through attribute reduction choose a set of approximate independent attribute reduction subset, put forward the improvement of the partial least-squares regression weighted simple bayesian classification algorithm, experimental results show that the improved algorithm has higher classification accuracy. And the improved algorithm is applied to slop identification.
  关键词: 加权朴素贝叶斯分类;属性约简;偏最小二乘回归;边坡识别
  Key words: Weighted Naive Bayes;attribute reduction;partial least squares;slope identification
  中图分类号:TP391 文献标识码:A 文章编号:1006-4311(2012)36-0201-03
  0 引言
  朴素贝叶斯分类器(Naive Bayesian Classifier,NBC)是一种简单而有效的概率分类方法,由于其计算高效、精确度高,并具有坚定的理论基础得到了广泛应用。然而,朴素贝叶斯分类方法基于条件独立性假设,即假设一个属性对给定类的影响独立于其他属性,而这在现实问题中往往并不成立。
  文献[1]给出了基于偏最小二乘回归(PLS)的属性求解算法。该算法用回归系数度量了条件属性与决策属性之间的相关程度。但忽略了冗余属性对回归分析的影响,为此,本文在分析属性相关性度量的基础上,通过属性约简的方法找出一组最近似独立的属性约简子集,从而删除冗余属性和无关属性,弱化了朴素贝叶斯分类器的独立性假设条件的限制。在约简的数据集上,在条件属性与决策属性之间建立基于属性约简的偏最小二乘回归方程,以回归系数作为条件属性的权值,进一步改进朴素贝叶斯的分类测试能力。并通过实验与朴素贝叶斯分类器进行比较。
  1 朴素贝叶斯分类及加权贝叶斯分类模型
  1.1 朴素贝叶斯分类算法 贝叶斯分类是一种基于统计方法的分类模型,贝叶斯定理是贝叶斯学习方法的理论基础。朴素贝叶斯分类模型在贝叶斯定理的基础上,通过条件独立性假设,降低计算开销,预测未知数据样本属于最高后验概率的类。
  设每个数据样本用一个n维特征向量X={x1,x2,…,xn}表示,分别描述对n个属性A1,A2,…An样本的n个度量。假定有m个类C1,C2,…,Cm,给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类。即朴素贝叶斯分类将未知的样本分配给类Ci,当且仅当P(Ci│X)>P(Cj│X),1?燮j?燮m,j≠i,这样,最大化P(Ci│X)。其中P(Cj│X)最大的类Ci称为最大后验假定。根据贝叶斯定理得:P(Ci│X)=■。
  由于P(X)为常数,只需P(X│Ci)P(Ci)最大即可。给定具有许多属性的数据集,计算P(X│Ci)的开销可能非常大。为降低计算P(X│Ci)的开销,可以做类条件独立的朴素假设。给定样本的类标号,假设属性值相互条件独立,即在属性间,不存在依赖关系。这样,P(X│Ci)=■P(xk│Ci),概率P(x1│Ci),P(x2│Ci),…,P(xn│Ci)可以由训练样本估值。为对未知样本X分类,对每个类Ci,计算P(X│Ci)P(Ci)。样本X被指派到类Ci,当且仅当P(X│Ci)P(Ci)>P(X│Cj)P(Cj),1?燮j?燮m,j≠i
  朴素贝叶斯分类比较简单,可操作性比较强,分类准确性较好,与其他分类算法相比,具有最小的误分类率。
  1.2 加权朴素贝叶斯分类器 在实际应用中不同的条件属性与决策属性之间的相关程度是不同的,当条件属性与决策属性的相关程度高,它对分类的影响就要更大些,反之,如果条件属性与决策属性的相关程度较小,那么它对分类的影响就会很小。由于在实际中难于满足朴素贝叶斯条件独立性的假设,可给不同的属性赋不同的权值使朴素贝叶斯得以扩展,则加权朴素贝叶斯模型为:
  VMNB=argmaxP(c)■P(ai│c)■
  其中,wi代表属性Ai的权值,属性的权值越大,该属性对分类的影响就越大。加权朴素贝叶斯的关键问题就在于如何确定不同属性的权值。   2 改进的贝叶斯分类算法
  2.1 属性约简方法 属性约简是在保持分类能力不变的前提下,依次从数据表中删去属性,每删除一个属性即刻检查新的信息表,如果不出现新的不一致,则删除该属性,然后对新表重复前面的操作;否则该属性不能被删除,信息表要恢复到前一个,再继续对另一个属性重复操作;直到不再有冗余的属性,此时可以得到属性的约简集。
  设S为一个信息系统,S=(U,A,V,f)。其中:U为对象集,U={x1,x2,…,xn};A为属性集,A=C∪D,A={a1,a2,…,an},C为条件属性集,D为决策属性集,C∩D=?覫;V=∪Va(a∈A),Va为属性a的值域;f:U×A→V为一信息函数,f为一映射。
  给定信息系统S中包含一组条件属性C和决策属性D,要从C中找出最优约简,先计算所有条件属性和决策属性之间的属性相关度[2],并且根据将所有条件属性降序排列得到条件属性序列AttriSet,然后选择AttriSet中的第一个属性A1,依次计算该属性与其他属性的相关度,从AttriSet中删除A1的冗余属性,对于AttriSet中的其余属性,按照同理依次删除其它冗余属性,最后得到最优约简子集RedAttriSet。
  2.2 偏最小二乘回归方法 偏最小二乘回归[3](PLS)是一种多元统计数据分析方法,集多元回归分析、典型相关分析和主成分分析的基本功能于一体,将建模预测类型的数据分析方法与非模型式的数据认识性分析方法有机地结合起来,提供了一种多对多线性回归建模的方法,特别当变量个数很多,且都存在多重相关性时,用偏最小二乘回归建立的模型具有传统的经典回归分析等方法所没有的优点。
  在一种简化PLS算法基础上,研究了一种基于粗糙集改进偏最小二乘回归算法[4],以减少PLS建模的计算量,提高在线建模速度。
  改进的PLS算法步骤如下:
  (1)根据粗糙集理论,利用属性相关性的约简方法对数据进行约简,在经过知识约简后,进行数据标准化处理,得到标准化后的自变量矩阵E0和因变量矩阵F0,在此基础上对向量进行成分提取。从E0中抽取一个成分,t1=E0W1,其中W1=■;
  (2)实施E0和F0在t1上的回归■,E1和F1均为残差矩阵;p1和r1均为回归系数向量,即:
  p1=■,r1=■
  (3)检查收敛性,若Y对t1的回归方程已达到满意的精度,则进行下一步;否则,以E1取代E0,以F1取代F0实施与第(1)步基本相同的算法,对残差矩阵进行新一轮的成分提取和回归分析;
  (4)依此类推,在第h步(h=2,3,…,s),方程满足精度要求,则可得到s个成分t1,t2,…,ts实施F0在t1,t2,…,ts上的回归得F0=t1r1+t2r2+…+tsrs+Fs
  (5)按照标准化的逆过程,将F(y*)的回归方程还原为y对x的回归方程:y*=?琢1x1+?琢2x2+…+?琢sxs,?琢为xi的回归系数;
  (6)对权数归一化进行处理,即?棕i=■为第i个属性所占权重,且满足■?棕i=1。
  由于权数的实质是结构相对数,且线性变换并不影响权数的作用结果,所以当权数为负时,先通过平移使之归结为结构相对数,再对权数作归一化处理。
  2.3 算法实现 属性约简在不影响分类能力的前提下,对决策表中空值属性做了处理,去除了冗余的属性和完全依赖属性,又删选了部分依赖属性集。通过以上操作,降低干扰信息对PLS提取成分的影响,提高了回归建模精度。在约简的数据集上,建立偏最小二乘的加权朴素贝叶斯分类器(PLS-NBC),算法具体步骤如下:
  Step1:求最优约简子集RedAttriSet;
  Step2:在最优约简子集的基础上构建加权朴素贝叶斯分类器;
  Step3:分类器的构造:如果是分类任务,则转Step6,如果是训练任务,则转Step4:;
  Step4: 概率表学习:对所有训练样本,计算所有的先验概率p(xi│Cj),即在类别Cj下属性Ai的属性值xi出现的概率,及类别Cj出现的概率p(Cj);
  Step5:权重的学习:扫描所有训练样本,计算属性Ai的权值?棕i,生成加权朴素贝叶斯概率表及属性权值列表,即构造PLS加权朴素贝叶斯分类模型;
  Step6:分类:调用概率表及属性权值列表,得出分类结果。
  3 实验结果及分析
  为了验证算法的有效性,对算法进行测试。本实验数据集选自UCI机器学习数据库,从中选取了5个数据集分别为Car,heart,Tic-Tac-Toe,Zoo,Kr-vs-kp。实验在matlab7.10平台下完成。首先求出朴素贝叶斯器的分类正确率(NBC/%);其次对实验数据集进行属性的约简,约简结果如表1。计算每个属性的权重,在此基础上构建加权朴素贝叶斯分类器,并对每个数据集进行分类正确率测试(PLS-NBC/%);最后将两个分类器的分类结果进行比较如表1。
  基于属性约简的PLS加权朴素贝叶斯分类器与基本的朴素贝叶斯分类器相比,一方面通过属性约简改善条件属性间的依赖性,找到一组最近似独立的属性约简子集,另一方面基于PLS加权的贝叶斯分类,考虑条件属性和决策属性的相关关系,充分利用类之间的信息,放松了条件独立性假设。实验结果表明,基于属性约简的PLS加权朴素贝叶斯分类器具有较高的分类准确率。
  4 改进的算法在边坡稳定性识别中的应用
  山体滑坡和泥石流具有分布广、破坏性强、隐蔽性等特点,严重威胁着人民群众的生命财产安全。根据“预防为主,防治结合”的地质灾害防治方针,山体滑坡的预报问题成为山体滑坡防治的重要环节。加强偏坡的稳定性识别对山体滑坡的预报有着重要意义。对边坡稳定性进行分析,可以预测滑坡事故,采取防护措施,避免或者减少人员伤亡与经济损失。因此,提高偏坡稳定性识别率成为有效防灾的关键问题[5]。这里,将决策树分类算法(C4.5)、神经网络模型(BP)、朴素贝叶斯分类算法(NBC)和PLS-NBC算法分别用于偏坡的稳定性识别,比较各个分类算法的偏坡稳定性识别正确率。
  根据工程经验[6],边坡稳定的因素有岩石的容重、内聚力、内摩擦角、边坡角、边坡高度、孔隙压力等。从文献[6]收集得到一个含有82个实例的数据集。其中,有44个实例为破坏边坡,38个为稳定边坡。在matlab7.10平台上对数据集进行分类,分类结果比较如表2所示。
  由实验结果可知,C4.5算法和PLS-NBC具有较高的分类准确率,其中PLS-NBC分类准确率最好。在后续的研究中,考虑数据集的缺失值的处理,进一步提高分类准确率。
  参考文献:
  [1]李雪莲.基于PLS的加权朴素贝叶斯分类测试算法[J].电子质量,2010,(07):4-6.
  [2]张静,王建民,何华灿.基于属性相关性的属性约简新方法[J].计算机工程与应用,2005,28:55-57.
  [3]王惠文.偏最小二乘回归方法及应用[M].北京:国防工业出版社,1999:150-169.
  [4]张小海.基于粗糙集的偏最小二乘回归方法[J].上海交通大学学报,2010,44(12):1680-1681.
  [5]高岩.基于因子分析的NBC及其在边坡识别中的应用[J].计算机工程与设计,2011,32(11):3830.
  [6]冯夏庭.智能岩石力学导论[M].北京:科学出版社,2000.

文秘写作 期刊发表