关联规则的朴素贝叶斯分类结构优化仿真

王正杰+姚道洪

摘要：朴素贝叶斯分类器要求属性变量间相互独立，此时的分类准确率和效率是很高的，但是不满足该条件时分类性能就会受很大影响。针对属性变量间不相互独立造成分类性能低这一问题，借助于关联规则挖掘，提出一种优化朴素贝叶斯网络结构的方法。首先，预置合适的支持度和置信度挖掘强关联规则，找到属性变量、分类变量间的共现关系；然后，根据关联规则对属性变量进行约减，在朴素贝叶斯分类结构基础上做节点和边的增减；最后，分别通过增边、约简和混合优化得到三种结构模型。对比仿真实验表明，增边可以有效提高分类准确率，节点和边的约减可以有效提高分类效率。

关键词： 关联规则；朴素贝叶斯分类器；贝叶斯网络；网络结构；数据挖掘

中图分类号：TP391.9 文献标识码：A 文章编号：1009-3044（2017）27-0241-05

Abstract：The naive bayes classifier requires that the attributes are independent of each other， the classification accuracy and efficiency is high at this time， but when the condition is not satisfied， the classification performance will be greatly affected. Aiming at the problem that the attribute variables are not independent of each other， the classification performance is low， this paper puts forward a method of optimizing the network structure Based on association rule mining. First of all， set the appropriate support and confidence， mining association rules， find the attribute variables， classification of co-occurrence between relations；Then， according to the association rules to subtract attribute variables do increase or decrease of nodes and edges Based on naive bayesian classifier network structure；Finally， by adding edges， reduce the nodes and edges， hybrid optimization， this paper get the structure model of three kinds of optimization.The simulation experiments show that the increase side can effectively improve the classification accuracy of nodes and edges of subtract， can effectively improve the efficiency of classification.

Key words：association rule mining； naive bayes classifier； bayesian networks； network structure； data mining

1 概述

在眾多分类技术中，朴素贝叶斯分类器在很多领域中因有很好的分类能力而受青睐，它的结构模型简单而有代表性，基本数学理论源出贝叶斯公式，分类预测模型泛化能力强，准确率和效率高。可是，属性变量间独立假设的条件决定了该分类器并不能放之四海皆准，勉强应用，其分类结果可能会违背数据反映的内在固有信息，当然也影响到分类准确率。因此，在朴素贝叶斯分类结构的基础上进行结构的优化对有效提高准确率或效率是一个突破。

为获得具有更高分类准确率和效率的网络结构，很多专家学者在朴素贝叶斯分类结构的基础上做了很多改进工作。文献[1]在朴素贝叶斯分类结构的属性节点间加入能够减缓朴素贝叶斯的强独立性假设的增强弧，建立了双层贝叶斯模型（DLBAN），大大提高了查全率和查准率；文献[2]提出一种特征加权朴素贝叶斯分类器（FWNB），分类的正确率与树扩展朴素贝叶斯（TAN）和朴素贝叶斯树（NBTree）的相当，但分类的效率有所提高；文献[3]提出了一种基于先验节点序学习网络结构的优化方法，定义优化目标函数和可行域空间，将网络结构学习的问题转化成解目标函数极值的数学规划问题，令人耳目一新；文献[4]在训练集上选取若干属性子集，以这些子集来构建贝叶斯分类器，利用遗传算法进行优选，比朴素贝叶斯方法有更高的分类精度。也有学者利用关联规则优化网络结构：文献[5]提出一种基于关联规则属性约减的贝叶斯方法AD-TAN，在逐层删除冗余节点时，计算较为繁琐；文献[6]提出一种基于关联规则的贝叶斯网络分类算法，先利用关联规则挖掘候选网络边集，再通过贪心算法学习网络结构，算法复杂不易操作。

关联规则挖掘可以把看似互不相关的项归在不同的项集里，挖掘出项间潜在的共现关系。比如在很多资料中都提到沃尔玛超市利用关联规则挖掘找到了“啤酒”和“尿布”的关联关系，这也是关联规则应用当中最神奇和最成功的案例之一。

本文将挖掘的关联规则作为优化分类结构的依据，通过增边提高分类准确率，通过节点和边的约减提高分类效率，通过设置不同的关联规则支持度和置信度阈值控制结构优化的程度。下面先介绍朴素贝叶斯分类器和关联规则挖掘技术，再阐述结构优化的三种模型，最后做仿真实验与其他分类算法做效果对比，以此说明优化算法的优越性。endprint

2 朴素贝叶斯分类原理

2.1 贝叶斯网络

贝叶斯网络（Bayesian Networks， BN）是一种推理工具，基本理论基于概率论和图论。对于变量集[V={X1，X2，...，Xn}]对应了一个二元组[（G，P）]，[G]表示一个有向无环图，也称为贝叶斯网络结构，[P]表示一个条件概率表（CPT），也称为贝叶斯网络参数。在图[G]中，一个节点[A]的所有前驱节点称为[A]的父节点集，用[Pa（A）]表示。

3.1.2 Apriori 算法

在挖掘频繁项集的关联规则算法当中，Apriori 算法是最早和最经典的算法之一。Apriori 算法通过反复迭代来计算数据库中的频繁项集，第i次迭代计算出的项集[Li]称为频繁i-项集，每一次迭代过程中都要经历确定候选集[Ci]和根据最小支持度minsup选择候选集[Li]两个步骤，分别称为连接（join）和剪枝（prune）。算法的输入是数据事务集，预设支持度和置信度阈值，最终输出频繁项目集。

另外，由于Apriori算法频繁地扫描数据集，所以算法效率并不高，为此很多专家学者提出了一些改进算法，如AprioriTid算法、DHP算法、Partition算法、FP-growth算法、DLG算法等[5]。

3.2 结构优化算法

3.2.1 属性变量间结构扩展算法ESBA

所谓朴素贝叶斯分类器属性变量间结构扩展（Extended structure between attributes， ESBA），是指在朴素贝叶斯网络的基础上添加属性变量节点间的边，使得新结构更能适应样本数据，目的是使网络分类能力更强，能弥补NBC的网络结构适应性差的缺点。利用关联规则对NBC结构扩展的流程如图2。

具体步骤是：

（1） 确定最小支持度，先对关联规则进行试挖掘。如果最小支持度比较小，挖掘出的关联规则数量会很大，结构扩展时加边数量会增多，不利于简化结构；如果最小支持度比较大，挖掘出的关联规则数量较少，需扩展的边数量也会较少甚至没有，达不到结构扩展的目的。所以，最小支持度的确定要考虑以上两因素，有必要多次尝试后确定最终的最小支持度。

（2） 从关联规则中选出前项和后项都是属性变量节点的高置信度和高提升度的规则，在已有NBC结构上按照从先决条件节点到结果节点指向添加有向边，完成一次结构扩展。

（3） 依照扩展后的结构计算分类准确率，把握网络分类能力。如果分类性能没有得到明显改善，则终止结构扩展，结束。如果分类性能好，说明上一次加边扩展的新结构更优，有必要继续加边，转到第4步。

（4） 找到次高置信度的规则，重复第2、3步，直至不能再添加有效的有向边。

在NBC结构的基础上增加属性变量节点间的边，结构要比NBC的复杂，这在分类的准确率上可能有所提高，但结构的复杂化使属性变量节点较多时分类效率降低。

3.2.2 属性变量间结构约简算法RS

在有的大型事务中，项目集[I]=[i1，][i2，][...] [，in]的项目数比较多，利用NBC进行结构建模时冗余的属性变量节点也会很多，这时可以考慮利用关联规则挖掘出对分类起关键作用的属性，利用这些关键属性做NBC结构建模，这样能大大提高运算效率，在分类准确率上还不会有太大影响。这一做法可称为结构约简（Reduction structure，RS），具体做法是：

（1） 挖掘那些属性变量节点为前项，分类属性节点为后项的关联规则，规则[R]要满足基本条件，见（4）式。

（2） 关联规则中没有出现的属性变量为冗余变量，在NBC的结构中将相应的节点删除。

需要注意的是，如此构造的NBC扩展结构可能会在分类准确率上有损失，但以准确率的略微损失换取结构精减带来的高效分类，这对高维实例集分类是值得的。

3.2.3 混合结构优化算法EHS

NBC的混合结构扩展（ Expansion of the hybrid structure，EHS）是指将前述ESBA和RS技术相结合，根据挖掘的关联规则，在属性变量节点间即考虑增加边，又考虑对属性变量节点进行约简，混合结构扩展EHS力求在NBC结构基础上进一步优化，目的是调整分类准确率和效率，使优化后的分类器有更好的分类能力。另外，在混合结构扩展过程中可能会遇到的情况和处理办法如下：

（1） 关联规则后项结果全是属性变量而没有分类变量，此时不再做属性约简，只考虑在属性变量节点间加边，此时的网络结构应该比NBC结构复杂，此种网络分类能力较强，但效率比NBC应该差。

（2） 关联规则后项结果全是分类变量而没有属性变量，此时只做属性约简，不在属性变量节点间增加边，此时的网络结构属性变量节点数量减少，是一个规模较小的NBC结构。此种网络分类能力比NBC稍差，但分类效率大大提升。

（3） 关联规则中前项和后项即有属性变量也有分类变量，是两类变量间的混杂规则，这时即考虑对属性变量节点进行约简，又考虑在属性变量节点间增加边。另外，关于关联规则还要注意：如果规则[R：A，B?C]满足基本条件（4）式，那么[R1：A?C]，[R2：B?C]也都满足基本条件，在扩展的结构中要做相应的结构优化。

（4） 如果[A，B]是两个属性变量，规则[R1：A?B]与[R2：B?A]同时出现时，取两者的置信度[conf]较高者，如果置信度都一样两规则中任选其一。

3.2.4 举例

为进一步说明结构模型扩展过程，下面以Weka 3.9 自带文件weather.nominal.arff的数据来源进行仿真。数据中有14个实例，五个变量，其中有四个属性变量（outlook， temperature， humidity， windy），一个分类变量（play），均为离散型变量，取值情况见表1。endprint

本例来看，ESBA模型和EHS模型与NBC的分类能力相当，可替代NBC进行分类。RS模型因删除了一个属性节点，分类正确率降低。weather数据集实例数量少，属性变量个数少，较难发现分类效率的差异，后文大型数据集的仿真结果就可反映这一点。

4 仿真及分析

下面将上述朴素贝叶斯分类器的几种结构优化技术应用到其他数据集，并做分类正确率的对比。另外，再将EHS与其他分类技术做分类性能对比，其他技术包括决策树、支持向量机、BP神经网络。如果数据集中属性变量为连续型，则用Weka.unsuperised.attribute.discretize过滤器进行等频离散化处理。首先对UCI数据集iris进行仿真。NBC、ESBA、RS、EHS分类正确率对比情况见表3，四个模型的结构见图4。

对比中可见，在大型数据集中，利用关联规则对属性变量进行约减可以很大程度提升分类效率，缩短建模时间，在正确率上可能会略有损失；利用关联规则增加共现属性变量间的边，有利于提高分类的正确率，但在分类效率上略有损失，建模时间通常会多一些；混合结构优化EHS模型在各数据集中正确率和效率有波动，是因为属性约减和增减边的规模各有不同。在后续研究中可以尝试通过控制关联规则挖掘的最小支持度和最小置信度有效改变强关联规则数量，以达到控制分类正确率和分类效率的目的。

5 结束语

朴素贝叶斯分类器因独立假设的条件在应用上受局限，分类准确率也受影响。为此，通过关联规则挖掘找到分类属性、类别间的共现关系，对朴素贝叶斯分类器的结构模型进行修缮优化。通过仿真实验，证实了新结构的分类器在分类准确率或效率上各有所长，将其应用到大型数据集中定能发挥优势，对于以后做进一步属性降维、提高准确率和效率的研究有一定作用。

参考文献：

[1] 郗海龙，张玉环. 恶意网络软件行为评估中的分类优化模型仿真[J]. 计算机仿真，2015，（10）：467-470.

[2] 程克非，张聪. 基于特征加权的朴素贝叶斯分类器[J]. 计算机仿真，2006，（10）：92-94+150.

[3] 朱明敏，刘三阳，汪春峰. 基于先验节点序学习贝叶斯网络结构的优化方法[J]. 自动化学报，2011，（12）：1514-1519.

[4] 胡为成，胡学钢. 基于遗传算法的朴素贝叶斯分类[J]. 計算机技术与发展，2007，（01）：30-32.

[5] 王晓龙. 基于关联规则属性约简的树增广朴素贝叶斯分类器及应用[D].吉林大学，2014.

[6] 张子义，王德亮. 基于关联规则的贝叶斯网络分类器[J]. 计算机应用，2009，（S1）：134-136.

[7] Agrawal R， Mannila H， Srikant R， et al. Fast Discovery of Association Rules[J]. Advances in knowledge discovery and data mining，1996，12（1）：307-328.

[8] 王晓海，吴志刚. 数据挖掘：概念、模型、方法和算法[M].北京：清华大学出版社，2013.

[9] 袁梅宇. 数据挖掘与机器学习WEKA应用技术与实践[M].北京：清华大学出版，2014.endprint