基于冲突域的测试成本独立决策系统属性约简

2015-12-14向恒月杨思春王小林

安徽工业大学学报（自然科学版） 2015年4期

关键词：约简权重冲突

向恒月，杨思春，王小林，王雷

（安徽工业大学计算机科学与技术学院，安徽马鞍山243032）

基于冲突域的测试成本独立决策系统属性约简

向恒月，杨思春，王小林，王雷

（安徽工业大学计算机科学与技术学院，安徽马鞍山243032）

针对决策系统存在冲突对象的情况，提出一个基于冲突域的λ-权重约简的启发式算法来降低属性约简的测试成本。首先对决策系统进行简化，将不一致对象的决策属性值异类化，进而删除重复对象，然后对简化后的决策系统根据冲突强弱计算出核属性和属性重要性,在此基础上，利用启发式函数来求解测试成本较低的属性约简，其中启发式函数由属性重要性和权重共同组成，权重由测试成本和非正参数λ决定。实验结果表明该方法在保证降低测试成本的同时加快处理效率。

决策系统；测试成本独立；冲突域；属性约简

在模式识别、数据挖掘中，属性约简是粗糙集领域特殊类型的特征选择问题[1]。属性约简的目的是保留必要属性，删除冗余属性，将隐含在数据中的知识用最简决策规则表示出来，其核心步骤是分类。分类通常有两个目标：降低测试成本；提高分类的准确性。在很多应用中，数据库中的数据免费可用，故目前有很多文献研究分类准确性这个问题，较有效的方法有：人工神经网络[2]，贝叶斯网络[3]，决策树[4-5]，支持向量机[6]。另外一些应用中的数据不免费提供，每个数据项均有测试成本，因此需要用较低的测试成本获得正确分类。然而现有对降低成本的研究较少，文献[7]提出了一种以信息增益为基础的λ-权重约简算法，由测试成本和非正参数λ决定权重，研究结果表明利用竞争方法选择一个合适的λ参数能显著提高结果的质量，但该研究没有找到对任何数据库均有效最优的λ值。

在数据收集过程中，数据不一致（冲突）是常见现象。文献[8]针对决策表中对象冲突的情况，设计基于冲突域的高效属性约简算法。文献[9]针对非完全不一致决策表将原决策表中不一致对象的决策属性值异类化，再消除重复对象得到简化决策表，再利用冲突域求解属性约简以提高属性约简算法的效率。文献[7]设计了基于信息增益的λ-权重约简算法，求出测试成本独立决策系统的一个相对测试成本较低的属性约简，算法的时间复杂度为O(|U|2|C|3)，空间复杂度为O(|U||C|)[7]。为进一步提高测试成本独立决策系统求属性约简的效率，本文对基于信息增益的λ-权重约简方法进行改进，提出了基于冲突域的λ-权重约简方法。

1 测试成本独立决策系统

1.1 基本概念

定义1[10]一个决策系统S是一个5元组

其中，U为论域，是对象的集合，U={x1,x2,…,xn}；C为条件属性集，D为决策属性集；Va是属性α∈C⋃D的值域；Ia为信息函数 Ia∶U→Va,∀α∈C⋃D,x∈U有Ia(x)∈Va不失一般性，也为了便于操作，假设D仅有一个决策属性值。决策系统S中，若∃xi,xj∈U(i≠j)，有IC(xi)=IC(xj)∧ID(xi)≠ID(xj)，则称S为不一致决策系统，xi与xj称为不一致对象（或称冲突对象），否则称S为一致决策系统。

定义2[10]一个测试成本独立决策系统是一个6元组

其中c∶C→R+⋃{0}是属性的成本函数。

通常测试成本是非负的(R+⋃{0})，条件属性集的所有属性的测试成本可以用一个向量表示c=[c(a1),c(a2),……,c(a|C|)]。由于λ-权重函数要求测试成本是非负值，不能取零，故文中规定：若有个别属性的获得不需要测试成本，仍然以一个很小的正值表示其测试成本。

性质1[10]设c*表示属性子集的成本函数，一个测试成本独立决策系统有如下性质：(1)c*(∅)=0；(2)c*({a})=c(a)∀a∈C；(3)

定义3在一个测试成本独立决策系统 S=(U,C,D,{Va|α∈C⋃D}，{Ia|α∈C⋃D},c)中，新的决策系统S'=(U,C,D,{V'a|α∈C⋃D}，{I'a|α∈C⋃D},c)，满足：

其中Vξ表示不同于S中任何决策属性的值。

由定义3可知，决策系统S’是将原决策系统S中不一致对象的决策属性值均异类化为Vξ。

定义4在测试成本独立决策系统 S’=(U,C,D,{V’a|α∈C⋃D}，{I'a|α∈C⋃D},c)中，设U/C={[x1]C,[x2]C,…,[xn]C}，令U’={x1,x2,…,xn}；则称S*=(U’,C,D,{V’a|α∈C⋃D}，{I’a|α∈C⋃D},c)为简化决策系统。

由定义4可知，S*是将S’中重复对象删除后得到的决策系统。

1.2 测试成本的设定

帕雷托分布(Pareto distribution)产生的一组随机数中包含许多小数值和少量大数值[11]，所以用帕雷托分布来随机产生测试成本更符合实际要求。

为了使实验结果与文献[7]具有可比性，本文将变量的取值设定与文献[7]相同，变量∂取2，p(M,N,x)的取值区间是(M,N+1)，cp(N,N,x)的取值区间是[M,N]，并设M=1,N=100。

1.3 评估标准

处理较低测试成本的属性约简问题有很多不同的算法，因此需要一个评估标准来比较不同算法的表现，本文用找到最优约简的概率来作为评估标准。设总实验次数记为K，找到最优约简的次数记为k，找到最优约简的概率记为f=k/K。

在实验部分，对同一个决策系统会产生不同的测试成本，也并非每次得到的约简都是最优约简，因此用找到最优约简的概率既能定性又能定量的衡量一个算法的性能。

2 基于冲突域的λ-权重约简

文献[7]中是基于信息熵来获得信息增益，在此基础上给测试成本一个权重，共同构成λ-权重函数，在文献[7]中的时间复杂度为O(|U|2|C|3)，空间复杂度为O(|U||C|)，显然这个时间复杂度比较高,且基于信息熵设计属性约简算法通常只要求H(D|R)=H(D|C),并不要求∀r∈R均有H(D|R－{r})≠H(D|C),只有要求这一点而设计的属性约简算法才通常称为完备的属性约简[12]。为了保证算法的完备性，文献[7]中的算法在最后加上了消除冗余属性的检查，这样无疑增加了算法的执行时间。

2.1 启发式函数的设计

文献[7]当中核属性的计算采用正区域方法，对象之间频繁的比较运算难以避免，但是利用冲突域的方法求核属性，既可以避免这个问题，同时也避免了采用可分辨矩阵所需的大量空间和时间开销。

属性集R关于决策属性D的冲突域ConSet(R)的定义见文献[8-9]，这里不再详细介绍。

定义7[8]属性a的重要性sig(a,R,D)=|ConSet(R)|－|ConSet(R∪{a})|。

为了求出测试成本独立决策系统的一个较低测试成本的属性约简，给测试成本一个权重，启发式函数离不开属性重要性和测试成本这两方面，因此本文的启发式函数定义如下：

定义8基于冲突域的λ-权重约简的启发式函数f(R,ai,ci)=(|ConSet(R)|－|ConSet(R∪{ai})|)ciλ。

2.2 约简过程

求测试成本独立决策系统的属性约简，其思路是先根据定义3和定义4将原决策系统进行简化，然后求出核属性，再根据启发式函数依次加入函数值大的属性，直到得到较低测试成本的属性约简为止，最后对非核属性进行反向消除，以确保约简的完备性。图1是针对测试成本独立决策系统求解测试成本较低的属性约简的流程图。

3 实验比较

采用本文算法和UCI数据库中4个数据集为实验数据，对文献[7]中的约简算法和本文的约简算法进行测试（实验环境为T6600 2.2 GHz，内存2 GB，eclipse3.6.1），通过f(R,ai,ci)=(|ConSet(R)|－|ConSet(R∪{ai})|)ciλ可知，当λ=0时，本文算法就是基于冲突域渐减的属性约简算法，没有考虑测试成本。Patient数据集有8个条件属性，表1是帕雷托分布(Pareto distribution)产生的10组测试成本，其他数据集测试成本就不一一例举。测试均是每个数据集设定100个不同的测试成本，也就是每个数据集都是试验900次。文献[7]中的约简算法和本文的约简算法的比较结果见表2。

表1 Pareto分布产生的测试成本Tab.1 Test cost settings of Pareto distribution

表2 两个约简算法的比较Tab.2 Comparison between the two reduction algorithms

由表2可知，本文算法的执行时间要低于文献[7]中的算法，虽然两种算法采用的启发式算法都是先求解核属性，但是文献[7]在计算核属性的时候用的是正区域的方法，对象之间频繁的比较运算会增加算法执行的时间。

本文设计的启发式函数，其中λ是唯一可由用户设定的参数，为了提高算法的性能，希望设置一个λ值，可以使得找到最优约简的概率最大。图2是根据不同λ和找到最优约简的概率所画出的折线图。λ取0就是没有权重函数，没有考虑测试成本，因为Patient数据集仅有一个属性约简，所以不管λ取多少，这个仅有的约简就是最优约简，所以找到最优约简的概率都是1.0，其他3个数据集会随着λ的减小，找到最优约简的概率先上升后趋于平稳。从图2中可以看出当λ取-1.25时，这四个数据集的找到最优约简的概率最大。

4 结语

降低测试成本是属性约简的一个新的研究趋势，也有其潜在的应用领域。已有的求测试成本较低的属性约简问题因为使用正区域方法计算核属性，使得算法的时间复杂度较高。为了降低时间复杂度，提高效率，本文对测试成本独立决策系统的属性约简问题进行了研究，针对决策系统存在冲突对象这一情况，先对决策表进行简化，然后提出一个基于冲突域的λ-权重约简算法，根据冲突强弱计算核属性和属性重要性,避免正区域方法求核属性时的频繁比较运算。最后，通过实验验证本文算法相对应同类算法，有一定的优越性。

[1]Min F,Hu Q,Zhu W.Feature selection with test cost constraint[J].International Journal of Approximate Reasoning,2014,55(1): 167-179.

[2]Hornik K,Stinchcombe M,White H.Multilayer feedforward networks are universal approximators[J].Neural Networks,1989, 2(5):359-366.

[3]Domingos P,Pazzani M.On the optimality of the simple Bayesian classifier under zero-one loss[J].Machine Learning,1997, 29(2):103-130.

[4]Quinlan J R.C4.5 Programs for Machine Learning[M].San Mateo,California:Morgan Kaufmann Publisher,1993:235-240.

[5]Yi W,Lu M,Liu Z.Multi-valued attribute and multi-labeled data decision tree algorithm[J].International Journal of Machine Learning and Cybernetics,2011,2(2):67-74.

[6]Vapnik V,Chervonenkis A.On the uniform convergence of relative frequencies of events to their probabilities[J].Theory of Probability and ItsApplication,1971,16(2):264-280.

[7]Min F,He H,Qian Y,et al.Test-cost-sensitive attribute reduction[J].Information Sciences,2011,181(2):4928-4942.

[8]葛浩，李龙澍，杨传健.基于冲突域的高效属性约简算法[J].计算机学报,2012,35(2):342-350.

[9]葛浩，李龙澍，杨传健.基于冲突域渐减的属性约简算法[J].系统工程理论与实践,2013,33(9):2371-2380.

10]Yao Y.Apartition model of granular computing[M]//Transactions on Rough Sets I.Springer Berlin Heidelberg,2004:232-253.

[11]帕累托分布[Z/OL].(2013-03-09)[2014-09-20].http://site.douban.com/182577/widget/notes/10567181/note/265696846/.

[12]徐章艳，侯伟，宋威，等.一个有效的基于信息熵的启发式属性约简算法[J].小型微型计算机系统,2009,30(9):1805-1810.

责任编辑：丁吉海

Attribute Reduction in Test-cost-independent Decision System Based on Conflict Region

XIANG Hengyue,YANG Sichun,WANG Xiaolin,WANG Lei
(School of Computer Science and Technology,Anhui University of Technology,Ma'anshan 243032,China)

With pertinence to the conflict object existing in decision system,a heuristic algorithm based on conflict region λ-weighted reduction was proposed for the purpose of decreasing attribute reduction’s test cost.Firstly,decision system was simplified,decision attribute value of inconsistent object was paganized,and the duplicate objects were deleted.Then core attribute and attribution importance were calculated according to the conflict intensity on the simplified decision system,and based on these,using the heuristic function a lower test cost attribute reduction was solved,where the heuristic function was composed of attribution importance and weights,and weights were decided by test cost and a non-positive exponentλ.The experimental result shows that the method can reduce test cost and speed up processing efficiency.

decision system;test-cost-independent;conflict region;attribute reduction

TP391

10.3969/j.issn.1671-7872.2015.04.015

2015-02-28

安徽省高校自然科学研究重点项目(KJ2011A048)；安徽工业大学研究生创新研究基金项目(2013080)

向恒月(1990-)，女，安徽合肥人，硕士生，主要研究方向为粗糙集。

杨思春(1970-)，男，安徽六安人，博士，教授，主要研究方向为自然语言处理、粗糙集、信息检索和概念格。

1671-7872(2015)-04-0378-05