何华平， 陈光建

(四川理工学院 计算机学院 四川 自贡 643000)



一种最小测试代价约简的改进算法

何华平， 陈光建

(四川理工学院 计算机学院 四川 自贡 643000)

传统属性约简的目标是在决策表中的所有条件属性中，选择一组分类代价最小的约简，算法构建了测试代价最小的约简.以往的测试代价约简算法查找成功率不够理想，性能不稳定，提出了一种改进的测试代价约简算法.通过运行2个UCI数据集实验，证明算法是有效的，并为提高测试代价约简算法性能提供了新途径.

代价敏感学习； 属性约简； 最小测试代价

0 引言

在数据挖掘中，要删除冗余数据是十分困难的，属性约简是目前最广泛采用的方法之一[1-3].以前的一些约简算法在大多数情况下是可以找到最小约简的，但性能和稳定性不够好[4].文[5]解释了测试代价敏感约简，定义并实现了该算法.测试代价敏感约简算法与传统约简算法相比具有更强的通用性，该算法关心测试代价，而不再像传统算法只关注分类的精度.测试代价在很多应用场合是很重要的，不同的约简产生相同的分类精度，而测试代价各不相同.文[6]提出了算法框架用于解决该问题.测试代价敏感约简算法的性能总是不能令人满意.本文提出了一种算法：首先利用条件信息熵找出核，再把除核之外的属性添加到核集中，形成(N-L)个集合(N代表决策属性数，L代表决策属性中除核之外的属性数)，然后对每个集合使用文[6]的框架算法求最小代价约简，最后把(N-L)个可能的最小代价约简进行比较，找出测试代价最小的约简作为本次约简的结果.通过2个UCI数据集实验，把改进的算法和文[6]的算法进行比较，结果表明不管是在查找成功率、最大超出率和平均超出率上均有大幅的提高，稳定性大大增强.

1 问题定义

1.1 测试代价独立决策系统

文[7]定义了一个测试代价独立决策系统(TCI-DS)S，它是一个6元组，

(1)

其中，U是一个有穷对象集，称为域，C是条件属性集合，D是决策属性集合，Va是a∈C∪D的所有值的集合，Ia：U→Va，a∈C∪D的一个信息功能，c：C→R+∪ {0}是测试代价功能.

任何的φ⊂A⊆C，可以使用公式

(2)

式(2)表明所有属性测试代价之间是相互独立的.例如，如果医生给病人做测体温和量血压两项测试，假设测试代价相应为5.00元和10.00元，那么总的测试代价为5.00+10.00=15.00元.

1.2 最小测试代价约简

本文只考虑最基本的概念,例如基于正区域的约简算法[8].为了提出定义，需要明白粗糙集理论的一些基本概念.任何的φ≠B⊆C∪D决定了在域U上的一个关系I(B).一个被B决定的分割记为U/I(B)，或者简写为U/B.把B(X)记为X的下近似，则把B⊆C，D的正区域定义为：POSB(D) = ∪X∈U/DB(X).

定义1任何B⊆C是S的一个决策关系约简，当且仅当：

1)POSB(D)=POSC(D)；

2) ∀a∈B,POSB{a}(D)⊂POSC(D).

定义1的条件表明，该约简是充分的，必须维持决策系统的特有特性[5].S上所有可能的约简记为Red(S).约简的核是所有约简的共有属性集合，即Core(S)=∩Red(S)[8].

2 算法描述

文[6]提出了一种通用的测试代价感知约简算法代码框架，该算法主要分为3个主要步骤：1)通过计算各条件信息熵的办法，找出约简的核；2)以核为基础再把其余的属性添加进去，计算各属性的加权信息增益，把最大的添加进去，直到POSB(D) ≠POSC(D)；3)把冗余的属性去掉，剩下的就是此次查找成功的最小代价约简.该算发是启发式算法，查找到的约简可能是最终最小代价约简，也可能失败.通过分析文[8]中的实例，发现：第1)步骤都是成功的，第3)步骤总是能剔出候选约简中的冗余属性，查找失败总是发生在第2)步骤.在通过加权的信息增益添加属性到候选约简中，算法基于这样一种假设：前一轮添加的是信息增益大属性，那么后面一定添加信息增益大的属性，则一定得到的约简是最小代价约简.当所有属性测试代价相等时，这种假设是成立的，但测试代价是随机产生的，它的大小影响了属性代价函数，使前面的假设不成立，所以可能产生失败.

基于前面的分析，本文把算法框架的第2)步骤，即在核上直接开始执行根据信息增益的约简，直到该约简具有原决策系统的完备性，修改为在核上直接添加一个其余的非核属性，得到多个集合.例如：有8个决策属性{a,b,c,d,e,f,g,h}，其中核属性有2个Core={a,c},则可以得到{a,b,c},{a,c,d},{a,c,e},{a,c,f},{a,c,g},{a,c,h}.然后分别基于每个集合进行约简及去冗余属性，再分别计算最小代价.最后再选择代价最小的作为最终的结果.

定义3Ri=Core∪ {ai},ai∈C,i=1,2,…，N-L.Ri为核属性再增加一个非核属性的关系，i为关系编号.

定义4Reducti=Reduction(Ri),i=1,2,…,N-L.Reducti为定义3中的用文[5]算法查找到的最小代价约简关系Ri.

定义5Mj=Reductj,j=minimal(c(Reducti)),i=1,2,…,N-L；c为式(2)定义的函数，Mj就是本文改进算法所得到的最小代价约简.算法的描述如下：

Output:Areductwithsub-minimaltest-cost

Method:tcs-reduction

1:B0←∅

3:if(POSC→{ai}(D)≠POSC(D))then

4:B0←B0∪{ai}//aiisacoreattribute

5:endif

6:endfor

8:Bj=B0∪{ak}//ak∉B0,andak∈C

9:while(POSBj(D) ≠POSC(D))do

10:a=anelementof(C-Bj)suchthatf(B,a,c,gc)ismaximal

11:Bj=Bj∪{a}

12:endwhile

14:if(ai∈Bj&&POSBj-{ai}(D)=POSBj(D))then

15:Bj=Bj- {ai}//removeredundantattributes

16:endif

17:endfor

18:endfor

20:returnB0.

3 实验

3.1 数据集

表1 属性集信息Tab.1 Information about attribute set

3.2 测试代价的设定和结果评价

本文把各属性的测试代价的值限定在[1, 100]范围的整数，通过一个随机发生器产生并把它们送给各属性作为测试代价.

图1 查找成功率(FOF)

图2 最大超出率(AEF)

图3 平均超出率(AEF)

4 结论

本文提出了一种最小测试代价约简的改进算法.实验结果表明，它比原算法有更高的性能和稳定性.从2个UCI数据集的实验结果证明，该改进算法具有更高的查找成功率，最大超出率和平均超出率均低于原算法.实验结果表明，实验数据的曲线更加平滑，算法的性能更加稳定.实际应用过程中可以进行多级构建来进一步提高性能，但同时算法的时间复杂度会大量增加，在构建算法过程中可以采用折中的办法来解决.

[1] 毛华，赵小娜，史田敏，等．多部图的最大匹配算法[J]．郑州大学学报：理学版，2013，45(1)：27-29．

[2] 王瑜．NMF方法在遮挡人耳识别中的应用[J]．郑州大学学报：理学版，2013，45(1)：61-64．

[3] 王长明，聂建军．基于遗传算法的二次曲面提取技术研究[J]．郑州大学学报：理学版，2013，45(1)：65-68．

[4] 申雪芬，谢珺，刘海峰，等．一种改进的基于相对正域的增量式属性约简算法[J]．广西师范大学学报：自然科学版，2013，31(3)：45-49．

[5] Yao J T, Yao Y Y.Information granulation for web based information retrieval support systems[C]// Proceedings of SPIE.Florida，2003:138-146.

[6] Min F，Liu Q. A hierarchical model for test-cost-sensitive decision systems[J]. Information Sciences, 2009, 179(14): 2442-2452.

[7] Pawlak Z. Rough sets[J].International Journal of Computer and Information Sciences, 1982, 11(2):341-356.

[8] 许长志，闵帆.带权约简及其在汉语词性标注自动校对中的应用[J].控制与决策，2007, 22(7): 740-744.

An Improved Algorithm of Minimal Test-cost Attributes Reduction in Decision Systems

HE Hua-ping, CHEN Guang-jian

(DepartmentofComputerScience,SichuanUniversityofScience&Engineering,Zigong643000,China)

The traditional attribute reduction problem was aimed at constructing a minimal reduct. As later on, it aimed at constructing a minimal test-cost reduct under the model. The current test-cost reduction algorithm could not ensure a satisfactory performance. And an enhanced algorithm was designed for better performance.The experimental results in two UCI datasets showed that this algorithm was efficient and effective. This algorithm was a new way to improve the performance.

cost-sensitive learning; attribute reduction; minimal test-cost

2014-09-06

国家自然科学基金资助项目，编号60873077;企业信息化与物联网测控技术四川省高校重点实验室项目，编号2013WZY02;四川理工学院培育项目，编号2013PY06;四川省教育厅科研项目，编号12ZB083.

何华平(1976-)，男，四川自贡人，副教授，主要从事代价敏感学习研究，E-mail:hehuaping_001@163.com.

TP181

A

1671-6841(2015)01-0074-04

10.3969/j.issn.1671-6841.2015.01.016