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

张　晶　毕佳佳　刘　炉

(合肥工业大学计算机与信息学院　安徽 合肥 230009)



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

张晶毕佳佳*刘炉

(合肥工业大学计算机与信息学院安徽 合肥 230009)

在分类任务中，特征选择是一种提高分类效果的重要方法。现实生活中的数据都是存储在多关系数据库中的。多关系数据库的数据中有许多不相关的且冗余的特征，这些特征对分类任务的贡献很小，甚至没有贡献。如何有效地将特征选择应用到多关系分类中是比较重要的。因此，将最大相关最小冗余的特征选择方法应用到多关系分类中，对关系数据库中的每个关系表进行特征选择，选择出对分类影响较好的特征集，再用多关系朴素贝叶斯分类算法对进行特征选择后的多关系数据库进行分类测试。实验结果表明了该算法的性能有了一定的提高。

多关系分类特征选择

0　引　言

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

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

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]。它是衡量信息的一种度量，在信息论的发展历程中起着非常重大的意义。

(1)

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

(2)

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

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

I(ζ,η)=H[p(x,y),p(x)q(y)]

(3)

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

I(ζ,η)=H(ζ)+H(η)-H(ζ,η)；

I(ζ,η)=H(ζ)+H(ζ|η)；

I(ζ,η)=H(η)+H(η|ζ)。

3.2最大相关与最小冗余

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

=H(Y)-H(Y|X)

(4)

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

(5)

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

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

(6)

即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的类标签的计算如下：

CMAP=argmaxci∈CP(ci|X)

=argmaxci∈Cp(ci)p(x1,…,xn,yk11,…,yk1r,…,ykp1,…,ykpr|ci)

(7)

3.4MNB-mRMR算法描述

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

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

算法: MNB-mRMR

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

输出：SRi，每个关系表所选的特征集

step1: CreateRelationGraph (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的特征集。

图3　不同μ值下的分类准确率的比较

4.2分类性能比较

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

表1　PKDD CUP 99的准确率

5　结　语

本文提出了基于mRMR的多关系朴素贝叶斯分类算法。特征选择一直是提高分类效果的有效方法，本文中将基于互信息的最大相关最小冗余的特征选择方法应用到多关系分类中，剔除了与类标签不相关且冗余度高的特征，选出了最优特征集。在选择最优特征集的过程中，根据特征的最大相关最小冗余的信息差算子的大小进行选择，该信息差算子综合了特征的最大相关度与最小冗余度，能够有效地表示该特征对分类效果的影响力。根据给定的信息差算子的阈值，反复实验训练，训练出分类效果最好的特征集。最后用多关系朴素贝叶斯分类算法进行了验证。该方法主要解决了不相关特征与冗余的特征对分类任务产生不好影响的问题。实验结果表明了该算法提高了分类精确度且加强了分类模型的可理解性。

[1] 邓彩凤.中文文本分类中的互信息特征选择方法研究[D]. 重庆:西南大学，2011.

[2] 刘海燕. 基于信息论的特征选择算法研究[D]. 上海:复旦大学，2012.

[3] Horvath T, Wrobel S, Bohnebeck U. Relational instance-based learning with lists and terms[J]. Machine Learning, 2001,43(1-2):53-80.

[4] Kramer S, Lavrac N, Flach P. Propositionalization approaches to relational data mining[M]. Germany: Springer-Verlag, 2001:262-291.

[5] Taskar B, Segal E, Koller D. Probabilistic classification and clustering in relational data[C]//Proceedings of 17th International Joint Conference on Artificial Intelligence, San Francisco, 2001:870-876.

[6] Neville J, Jensen D, Friedl, et al. Learning relational probability trees[C]//Proceedings of the ninth ACM STGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2002:625-630.

[7] Blockeel H, Raedt L De. Top-down induction of first logical decision trees[C]//Proceedings of 1998 International Conference of Machine Learning (ICML’98), Essex, 1998:285-297.

[8] Leiva H A, Gadia S. MRDTL: a multi-relational decision tree learning algorithm[C]//Proceedings of the 13th International Conference on Inductive Logic Programming, Springer, 2002:38-56.

[9] Yin Xiaoxin, Han Jiawei, Yang Jiong, et al. CrossMine: Efficient classification across multiple data relations[C]//Proceedings 2004 International Conference on Data Engineering (ICDE’04), Heidelberg, 2004:172-195.

[10] Liu Hongyan, Yin Xiaoxin, Han Jiawei. An efficient multi-relational naive Bayesian classifier based on semantic relationship graph[C]//Proceedings of the 4th International Workshop on Multi-Relational Data Mining, Chicago, 2005:68-76.

[11] He Jun, Liu Hongyan, Hu Bo, et al. Selecting effective features and relations for efficient multi-relational classification[J]. Computational Intelligence, 2010, 26(3):258-280.

[12] Ouardighi A, Akadi A, Aboutajdine D. Feature selection on supervised classification using Wilk’s Lambda statistic[C]//Proceedings of 2007 Computational Intelligence and Intelligent Informatics (ISCIII’07), Agadir, 2007:51-55.

[13] Sha C, Qiu X, Zhou A. Feature selection based on a new dependency measure[C]//Proceedings of 2008 International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’08), Shandong, 2008:266-270.

[14] Yang Y, Pedersen J O. A comparative study on feature selection in text categorization[C]//Proceedings of 14th International Conference on Machine Learning, Nashville, US, 1997,26(1):15-39.

[15] Hu Qinghua, Yu Daren, Xie Zongxia. Information-preserving hybrid data reduction based on fuzzy-rough techniques[J]. Pattern Recognition Letters, 2006,27(5):414-423.

[16] Yu L, Liu H. Feature selection for high-dimensional data: A fast correlation based filter solution[C]//Proceedings of 12th International Conference on Machine Learning (ICML-03), Washington, 2003:856-863.

[17] Peng H, Long F, Ding C. Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE transactions on pattern analysis and machine intelligence, 2005,27(8):1226-1238.

[18] 沈世镒, 陈鲁生. 信息论与编码理论[M]. 北京: 科学出版社, 2005:18-31.

[19] 惠孛, 吴跃. 基于全局的即时垃圾邮件过滤模型的研究[J]. 电子测量与仪器学报,2009, 23(5):46-51.

[20] Ouarda W, Trichili H. Combined Local Features Selection for Face Recognition Based on Naive Bayesian Classification[C]//Proceedings of 2013 International Conference on Hybrid Intelligent Systems (HIS’13), Gammarth, 2013:240-245.

MULTI-RELATIONAL NAIVE BAYESIAN CLASSIFICATION BASED ON MRMR

Zhang JingBi Jiajia*Liu Lu

(SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009，Anhui,China)

In classification task, feature selection is an important method to improve classification effect. In real life, data is stored in multiple relational databases. There are many irrelevant and redundant features in multiple relational database, and they have little or even no contribution to classification task. How to effectively apply the feature selection to multi-relational classification is rather important. Therefore, we applied the feature selection method of maximum relevance minimum redundancy to multi-relation classification, the feature selection is carried out on every relation table in database and to pick out the feature sets with better effect on classification. Then, we used the multi-relational naive Bayesian classification algorithm to classifying and testing the multi-relational database with the features selected. Experimental results also showed that the performance of the algorithm has been improved.

Multi-relationalClassificationFeature selection

2015-03-14。国家自然科学基金项目(61273292，6130 5063)。张晶，副教授，主研领域：数据挖掘，人工智能。毕佳佳，硕士生。刘炉，硕士生。

TP311

A

10.3969/j.issn.1000-386x.2016.08.013