基于rrf的信息数据集的特征选择-刘潇.pdf

《基于rrf的信息数据集的特征选择-刘潇.pdf》由会员分享，可在线阅读，更多相关《基于rrf的信息数据集的特征选择-刘潇.pdf（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2016年第21期 Sc跹d积摊糯罨ment R恍眦hdoi：lO3969jissn10007695201621034基于RRF的信息数据集的特征选择刘 潇，王效俐(同济大学经济与管理学院，上海200092)摘要：信息数据集中存在的冗余、不相关甚至是噪音特征会严重影响管理决策的质量和效率。整合Rs理论和Relie腰算法，提出一种“二次过滤”的RRF组合决策方法。首先采用ReliefF算法计算出各个特征权重，过滤掉噪音特征；之后再用启发式的Rs方法对原有特征集进行特征约简，过滤掉冗余特征。RRF组合决策方法集合了两个算法的优点，能够有效减少计算的工作量和复杂度，避免RS约简过多以及约简中存在噪音

2、特征等问题，从而起到提高决策质量和效率的作用。最后，用一个真实的医疗信息数据集对算法进行测试，并与两个常见的特征选择算法进行对比，证明本算法在辅助临床决策中的作用。关键词：信息数据集；决策；特征选择；RelieF；RS中图分类号：C931 文献标志码：A 文章编号：10007695(2016)2l一019805Feature Sel廿on of hfoma石on Data Sets Based on lU灌UU)【iaoWANG Xiaoli(School of Economics蚰d M粕agement，T0n百i UniVersify，Sh锄ghai 200092，China)AbstI邯

3、t： Redundant，in-elevant and even noise features mav severelv iIlfluence classification accuracv of data sets A novel secondary filtration RRF gmup decision a190ritllm combining RS with ReliefF is proposed in this paperRRF algoritImtakes advanta丹e of the two al印rithms and can remove redundant attribu

4、tes effIectively，so the number of reducts is reducedand qualit)r of reducts is impmvedAt laLst，the Rf谭algorithm is tested by one real medical data set and two common fea-ture selection methods are used to compare with itThe experimemal results show tle efIectiveness of RItF algorithm inclinical deci

5、sionKey words：data sets；group decision；feature selection；Relie俘；RS1问题的提出随着信息技术的迅猛发展以及知识经济的到来，人类每天面l临的知识量越来越多、知识复杂度越来越高。对于一些大的信息数据集来说，描述对象的特征数量众多，但是同时也存在着以下一些问题：最初的数据集中往往存在着与分类不相关的特征、冗余特征，甚至是噪音特征；众多特征提供的信息量少并且不够精确；计算成本偏高等1。J。这些因素都可能造成数据集最后的分类精度不高、结果不可靠等，从而给管理决策带来了一定的困难p“1。粗集(Rs)理论由波兰华沙理工大学zPawlak教授bm

6、l。356等一批科学家于1982年提出，是用于研究不精确知识、不完整数据的表达、学习、归纳等有效方法。特征重要度是RS理论当中的一个重要概念，根据组织以往积累的数据建立决策表，继而可以求得特征的重要度。而当一个特征的重要度为。时，我们认为其为冗余特征，可以被约简掉。由于RS能够有效去除数据集中的冗余特征，近年来RS越来越多地应用在了特征选择问题上刈1。RS约简问题已经被证明是NPHard问题，常用启发式算法来求解，得到的约简数量也很多，特别是当条件特征数目比较大时，约简的数量更多。这就产生了两个问题：一是RS方法根据不可分辨关系可以有效去除决策系统中有相同功能的冗余特征，但是无法完全去除噪音特

7、征，当特征数目较多时，一些约简中仍会不可避免地存在噪音特征。二是如何评价数量众多的约简，选择最佳约筒。虽然有论文中采用数目最小的约简作为最佳约简，但这样的选择是不合理的，最小约简不一定是最佳约简，而且有的数据集中最小约简不只一个。如果我们能预先在数据集中对特征进行过滤，去除掉噪音特征，之后再对数据收稿日期：2016一02一17，修回日期：20160530基金项目：国家自然科学基金重点项目“面向全生命周期的医疗质量安全管理与资源优化配置”(71432007)万方数据刘潇等：基于RRF的信息数据集的特征选择 199集进行约简，理论上会减少约简的数量，提高约简的质量，从而提高决策的质量和效率。特征选

8、择算法很多，一般分为过滤式算法(filters)和封装式算法(wrappers)两类p o。Relief算法属于过滤式算法，最早由鼬ra等叫提出，但是它受限于只能解决分类特征为两类的问题；1994年Kononenk01将Relief算法进行扩展，提出了能解决多类别问题的Relie爪算法；之后，Robnik Sikonja等引又提出了可用于回归的RRelie何算法。Relief系列算法是特征选择算法中的常见算法，是公认的效果较好的特征评估算法131348。1356，它不受特征之间关系的影响，对具有强依赖关系的特征集依然能够进行正确评估4|。综合上述，本文提出结合Relie仃和Rs算法的RRF“二

9、次过滤”组合算法，先用Relie俘算法过滤掉噪音特征，之后再用启发式的RS方法对原有特征集进行特征约简。该算法的好处是：在约简前首先去除部分噪音特征，之后进行第二次过滤，可以有效减少计算的工作量和复杂度，减少约简数目，提高约简质量，从而提高决策的质量和效率。2理论概述21 Rough Set理论简介RS的基本思想是建立相关信息系统(an information system)，然后用所建知识库中的知识来近似地刻画所解问题的不精确或不确定的知识。以下是RS的一些基本理论5341。56【651：定义l：设u是对象组成的非空有限集合，称为论域；对于任何子集xU，称为U中的一个概念或范畴。定义2：假设

10、给定知识库K=(U，尺)，对于每个子集xU和一个等价关系Rind(K)有以下两个子集分别称它们为x的尺下近似和尺上近似：R一(x)=戈E u：戈。cX (1)尺一(x)=戈E U：戈。n空集 (2)定义3：知识表达系统。知识表达系统的基本成分是研究对象的集合，关于这些对象的知识是通过制定对象的基本特征和它们的特征值来描述的。一个知识表达系统s可以表达为：S= (3)这里U是对象的集合，CuD=4是特征集合，C和D分别称为条件特征和决策特征；y是特征值的集合；F是一个信息函数，它指定u中每一对象x的特征值。定义4：若PcR，则nP(P中全部等价关系的交集)是一等价关系，称为P上的不可分辨关系，即

11、为涮(P)。定义5：在知识表达系统里面，令P和Q为C中的特征集，Q的P正域记为胛，(Q)，其中，xWi以(Q)。p。(Q)=u尺一(X) (4)定义6：令K=(U，只)为知识库，P和Q为C中的特征集，且P，Q尺r。(Q)=c口耐(p，(Q)耐() (5)其中：c口rd()表示集合的基数；K介于0和1之间。定义7：特征集P导出的分类的特征子集口i的重要度为：(口i)=rP(Q)一rP一。i(Q) (6)定义8：C、P和Q是u中的特征集，C、P、QA，一个约简被定义为，对于任意的CP，有：r。(Q)=L(Q) (7)22 Rehe但算法Relie母算法是一种特征权重算法(attributeweig

12、hting a190Iithms)，根据各个特征和类别的相关性赋予特征不同的权重，其权重大小取决于该特征值区分近邻的同类与不同类样本距离的能力m嗍1356。算法步骤具体如表1所示。表1 Relie佰算法ReUe伊A蛳tI”岫t：a decision龇S=(U，P，Q)，whP andQ帅di蛳sets 0fco础aIld deci8i缸Lt吣，豫pe商VelyJp=ol，d2，D。，Q=西，如，厶，ou咖t：Get tIIe删雄we蛳0f subset甲=旧，既m：妇谪0le岬is酬hm诋k：妇曲dI删舭s锄出set all weiglltswA=oEofi=l t0 mRandly sele

13、ct apleRiFor eh cIaC=d(R)doFmd k n朗r鸭t lIils(j=l吣k)凰(J=l协矗)F0r each claCcks(墨)doFind k ne岫lnissJ，i(c)E0r A=l to n do啦=睨Ai黝A碍)J琅+c墓喊)T淼叁坝A鼻彤(D)赢End3 RRF特征选择算法的提出31基于RRF特征选择流程对于一个信息数据集S来说，选择合理的特征选择算法至关重要。一个完整的特征选择流程包括：通过前期的数据预处理步骤，整理成符合特征选择算法格式的数据；通过算法进行特征选择，输出关键特征集D；之后用分类器对特征集D进行评估，测试算法的合理性。基于RRF的特征选

14、择流程如图l所示。万方数据刘潇等：基于RRF的信息数据集的特征选择原数据集s数据预处理一妒一ReIIc心算_；去过滤模块图1基于RRF的特征选择流程32 RRF主要计算子模块的实现RRF特征选择流程中的主要计算模块是RRF算法的3个模块：Relie仃算法过滤模块、阈值设置模块和RS特征约简模块。(1)Relie伊算法过滤模块。Relie伍算法过滤模块在MATLAB2014a中实现，参数设置具体如表2所示。表2 Relie腰算法特征权重求解模块参数设置其中，m和J|的大小取决于数据集中记录的数量以及分类特征的种类及其大小。当数据集中记录数较少时，m可以适当设置较小；当分类特征的种类较少，比如只有

15、两种时，_|可适当取大。(2)阈值设置模块。通过设置一个合理的阈值6，对ReliefF算法中求出的特征权重进行筛选，选出符合阈值范围的特征。阈值设置的方法很多，一些文献甚至是主观设置为005，或者01。RRF算法针对不同的数据集得出的权重往往相差很大，所以不能简单地设为一个固定值。在文献15中，作者将特征权重的均值设置为阈值，权重高于均值的指标将被挑选出来；平均值能充分利用数据所提供的信息，将其设为阈值比较常见，但容易受到极端值的影响；在文献16和17，作者将四分位数用于阈值的计算。综合上述，本文将第1个四分位数(Q1)设为阈值6，首先将权重集合中元素按照从小到大进行排序，求出其Q1，赋给阈值

16、6。(3)启发式RS特征约简模块。在RS特征约简模块，本文采用前向搜索的启发式算法来求解特征的约简集合。知识约简是RS理论的一个重要应用，通过对信息系统进行知识约简，可以去除系统中无用的信息，达到简化系统、提高知识精度的目的。RS约简是一个组合优化问题，需要测试2“一1个特征子集，为条件特征的个数，故寻找约简的过程一般采用启发式的搜索过程。本文采用向前搜索的算法求约简，算法步骤如下：输入：知识表达系统S=。输出：最小约简集合尺。，恐，尺。，n1。步骤1：数据离散化；步骤2：将约简集置空；步骤3：计算约简集之外的剩余属性的上下近似集、正域、依赖度和重要度；步骤4：按照特征重要度大小依次将一个条件

17、特征加入到约简集中；步骤5：循环步骤3和4，出现所有剩余特征的重要度都为0时，输出一个约简；当步骤4中全部条件特征添加完毕时，算法结束。33分类器测试我们选用几个常见的分类器对RRF特征选择模型进行效果测试。常用的分类器很多，BP神经网络(BPANN)、决策树c45、朴素贝叶斯(N批eBayes)、Libsvm、Lo舀stic回归(LR)等都是常见的分类算法模型【l引，本文选择BP神经网络(BPANN)、朴素贝叶斯(Nane Bayes)和决策树C45这3个分类器来测试RRF算法。为了评估分类器的性能，本文将原数据分为80一20(80训练，20测试)和7030(70训练，30测试)两种情况，测

18、试在MATLAB2014a中实现。4实验测试和结果本文用一个真实的信息数据集来验证文章提出的RRF算法，数据集从uCI机器学习数据库获得。41 Post叩emtiVe Patient Data数据集“Postoperative Patient Data”(PPD)包括9个特征(8个条件特征，1个决策特征)和87条记录，其决策特征是关于病人做完手术后下一步的计划。特征信息具体见表3所示。表3 PPD特征信息万方数据刘潇等：基于RRF的信息数据集的特征选择 201计算开始前先将数据集中进行离散化，再进行下列算法的计算，过程不再赘述。RRF算法对PPD特征选择的详细步骤如下：(1)ReliefF算法

19、过滤模块。ReliefF算法过滤模块在MATLAB2014a中执行，将数据录人，ReliefF算法运行20次，计算20次的平均结果，每个特征的平均权重的具体值如表4所示。表4 PPD数据集特征权重计算结果堑堡 ! ! ! ! 竺 竺 ! !权重 0104 3 0256 6 0088 9 0119 6 0099 9 o025 5 0196 l 0109 1(2)阈值计算模块。对表4中的权重阈值进行计算，特征口，和特征口。被去掉，特征n。、o：、吼、05、口7、口8被选择。(3)启发式RS特征约简模块。对选择后的特征重新建立新的知识表达系统，条件特征由原来的8个变为经过过滤后的6个特征，将数据录入

20、特征约简模块，根据前向搜索的启发式算法得到特征约简结果女口：RI 口l，n2，口5，口7，08，R2 口2，04，口5，口7，口8，尺3 ol，口2，04，05，07，本模块在MATIAB2014a中实现。42测试结果分析为测试RRF算法的有效性，我们对原数据集取80一20(80数据作为训练集，20数据作为测试集)和70一30(70数据作为训练集，30数据作为测试集)两种情况进行分析。使用BP神经网络(BPANN)、朴素贝叶斯(Nal、re Bayes)和决策树(C45)3个分类器，计算运行10次，3个约简得到的测试集最高分类准确率具体见表5所示。表5 PPD数据集测试集分类准确率约简测试集分

21、类准确率8020 70一30e Bayes c457647 82357647 76478824 8235BPANN Nave Bayes c4568 76 7660 76 7668 80 84Rl 7059R2 7059马 647l从表5中可以看出，R，相比R，、尺：具有更高的测试集分类准确率。为测试本算法的有效性，选择信息增益(infonation gain)和Lasso这两个常见的特征选择方法得到的特征组合与本文得到的R，做对比。采用信息增益方法对PPD数据集进行特征选择，得到了口：，口3，o，口。，o，口8特征组合；采用Lasso方法进行特征选择，得到了，。，口。，口，的特征组合。这3种

22、方法的对比结果具体见表6和图2所示。表6 3种特征方法得出的测试集分类准确率对比特征选择方法测试集分类准确率BPANN Nane Baye8 c45 BPANN NaHe Bayes c458235 68 80 847647 56 72 766 47 76 80 76647l5882矾718824823576 47*尝器图2 3种方法得出的测试集分类准确率对比从表6和图2中可以看出，RRF方法除了在BPANN分类器上(7030)分类准确率略低于L鹬so方法外，在其他分类器上均有明显优势。RRF方法从最初的特征集中提取相对重要的特征，去除冗余特征和噪音特征，能够有效精简数据集和提高决策的质量和效

23、率。在临床上，医生判断某种疾病需要根据一定的临床症状和检测指标，有时候指标个数会很多，如果我们能够从这些指标中筛选出更有效的指标，精简指标集，可以提高临床的诊断质量和效率，起到辅助临床决策的作用。5结论信息数据集中冗余、不相关甚至是噪音特征的存在会严重影响决策质量和效率，本文结合RS理论和ReliefF算法提出了一种新的RRF组合特征选择算法。该算法能够有效去除特征集中冗余特征和噪音特征，精简数据集的同时提高决策的质量和效率；采用一个真实的数据集对算法进行了测试并进行了结果分析，结果表明RRF算法在一定程度上可以起到辅助决策的作用。但是该算法也有一定的局限性，ReliefF算法在进行特征选择时

24、需要设置一个阈值，带有一定的主观性，未来我们还会就此做进一步深人研究，探讨合理阈值的设置，以确保将主观影响降到最低。参考文献：1PRIGOGINE I7rhe networked societyJ Joumal of worldsystems research，2015，6(3)：8928982PRATT G AIs a carnbrian elplosion coming for IDbotics?JTheJoumal ofEconornic Perspectives，2015，29(3)：5l一603cHEN H L，YANG B，uu J，eI a1A support vector ma

25、chine classifier with rough Setbased feature selection for breast carIcer diagrIosisJExpert systellls wilh Applications，201l，38(7)：901490224BERETTA L，sANTANIE【D AImplementing ReliefF filIers to ex昀ct meaI】jn加l fealures f而m genetjc】jfeljme dalaselsJJoumal ofbiomedical i山matics，20ll，44(2)：36l一3695PAwL

26、AK zRough setsJ Intemational Joumal of computer卸dInfomatjon Sciences，1982，1l(5)三-l万方数据202 刘潇等：基于RRF的信息数据集的特征选择6曾黄麟粗集理论及其应用M重庆：重庆大学出版社，19967s0N c s，l(IM Y N，KIM H s，et a1Decisionmal【ing model f打哪ly dia印osis of congestive hean硒lureing mll曲跎t柚d disiontpee appmachesJJoumal of Biomedical I砥姗atics，2012，45

27、(5)：999一10088S聊NIARSl(I R W，SKOWRON ARou曲set mthods in hn嘴se1ection锄d reco印itionJPattem Reco弘iti仰ktters，2003，24(6)：8338499YANG J，0LA飓soN s0pliIlliz撕彻一based融岫嘴跎lection w油adaptive instance锄plingJ compute璐0pe眦ions R档鲍Ich，2006，33(11)：3088310610KIRA K，RENDELL LA praclical apprnach to细t啪selectj鲫cProceedin

28、萨0f tlle Nintll confe陀nce in Machine l哪ingSan Fr虮cisco：Mo骤n Kaufmann Pllblishe惜hc，1992：24925611KONONENK0 IEsdHlatiIlg a蚵butes：al蟛and嘲emi0f枷efCProoeedin零0f the溉tII EIIrope明c0血舢lce in蚴neI舶llliIlgBedin Heiddberg：S曲nger Vedag，1994：17118212ROBNIKSIKONJA M，KONONENKO IAn ad印tation of Relieffor attribute es

29、timation in regre鹪i伽cMachine k锄ing：P肛ceedin铲0f tlIe Fourteentll Int锄撕onal Con胁nce(ICML97)S蛐Fr蛆cisco：Mo骤n K眦fmalln，1997：29630413HuANG Y，MccuLLAGH P J，BIAcK N DAn 01)timizadofReliefF for cl鹊s访cation in large datatsJD8taKnowledgeEn西neering，2009，68(11)(上接第197页)9王小鲁中国经济增长的可持续性与制度变革J经济研究，2000(7)：3一1510uNG

30、HuI TANG，PETER E KOVEoSEmbodied蚰d di驼mbodiedRD spiUove璐to devel叩ed趴d deVeloping cntri鹤JInten城-lional Business Review2008(5)：54655811杨宇，郑垂勇企业家精神对经济增长作用的实证研究J生产力研究，2008(18)：ll1312 BuRT R s stmcture hol髂：tlle social smJctu陀of com咖ti帅M1B08ton：Harvard Unive玛ily Pre鸥，1992：3613于明洁，郭鹏，张果区域创新网络结构对区域刨新效率的影141

31、51617】819ROBN一SIKONJA MKONONENKO 1Theoretical and empirical柚alysis of ReliefF锄d RRelie珂JMachine l龃rnjIIg，2003，53(12)：2369POLAT KGUNE S SA new feature selection m砒od仰cla鸽击ca-tion ofmedical data跎ts：Kemel Fscorefe咖re selectionJExpen system witll APplic砒ions，2009，36(7)：10367一10373KAPUSrA J，MINl(M，SvEC P

32、，et aI姗n堍tim wi曲wtlll幽0ld to identi如user se鹊ions of stakehdde玛0f a c0硼m咀eial b弧kponalJProoedia c响puter sci朋ce，2014，29：1779179IDMONrEIR0 P，BENIES L，0I、，EIRA F，et a1 EUT叮IS habitat童tll髓holds f撕tlle w器t锄ost 0f tIle Iberian Peni珊llla-一a晰I蜩lesec咖咖dyJJ眦mal 0fs睫R嗍rch，2015，100：笠一3l高学东，尹阿东，张健，等利用上凸函数对决策树算法的改

33、进J中国管理科学，2004，12(4)：144一148BLAKE CMEI也C，YAMADA KUnive玛ity of Cal渤mia 1wineRepository 0f nmchine I姗iIlg databas，technical陀ponRh-vine，CA：r11le Universily 0f Cal怕mia，D。p缸ment 0f Inf0Hn撕onalld Cmputer science，1998作者简介：刘潇(1988一)，女，河南安阳入，博士，主要研究方向为服务科学与服务工程、知识管理。王效俐(1960一)，男，山西万荣人。教授，博士研究生导师，主要研究方向为服务科学与服务工程。响研究J科学学与科学技术管理，2013(8)：566314刘新民，于文成，王垒企业家集群、产业集群与经济增长的关系研究J山东科技大学学报(社会科学版)，2016(3)：6267作者简介：王垒(1986一)，男，山东淄博人，讲师，在站博士后。主要研究方向为创业与创新管理、区域经济发展。刘新民(1965一)，男，山东莒南人，教授，博士研究生导师，主要研究方向为组织治理与系统决策。董啸(1990一)，男，山东青岛人，硕士研究生，主要研究方向为企业家创新理论。万方数据