基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简-孟慧丽.pdf

《基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简-孟慧丽.pdf》由会员分享，可在线阅读，更多相关《基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简-孟慧丽.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第43卷第2期 计算机科学 V0143 No22016年2月 Computer Science Feb 2016基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简孟慧丽马媛媛徐久成(河南师范大学计算机与信息工程学院 新乡453007)(河南省高校计算智能与数据挖掘工程技术研究中心 新乡453007)(智慧商务与物联网技术河南省工程实验室 新乡453007)摘要将下近似分布约简引入变精度悲观多粒度粗糙集，定义了变精度悲观多粒度粗糙集的下近似分布粒度熵，基于下近似分布粒度熵定义了变精度悲观多粒度粗糙集粒度的重要度，并设计了基于下近似分布粒度熵的悲观多粒度粗糙集启发式粒度约简算法，通过实例验证了算

2、法的有效性。关键词下近似分布约简，下近似分布粒度熵，变精度悲观多粒度粗糙集，粒度约简中图法分类号TPl82 文献标识码A DOI 1011896jissn1002137X20162018Granularity Reduction of Variable Precision Pessimistic Multi-granulation Rough SetBased oil Granularity Entropy of Lower Approximate DistributionMENG Huili MA Yuan-yuan XU Jiu-cheng(College of Computer&Info

3、rmation Engineering，Henan Normal University，Xinxiang 453007，China)(Engineering Technology Research Center for Computing Intelligence&Data Mining of Henan Province，Xinxiang 453007，China)(Engineering Lab of Intelligence Business&Internet of Things of Henan Province，Xinxiang 453007。China)Abstract The I

4、ower approximate distribution reduction was introduceel into the variable precmlon pessimistic multi-granulation rough setThe granularity entropy of the lower approximate distribution of the variable precision pessimisticmultigranulation rough set was definedThe importance of a granularity was also

5、defined based on the granularity entropy of the lower approximate distribution，and a heuristic granularity reduction algorithm of variable precision pessimistic multigranulation rough set was presentedThe experimental results show the validity of the algorithmKeywords Lower approximate distribution

6、reduction，Granularity entropy of lower approximate distribution，Variableprecision pessimistic multigranulation rough set，Granularity reduction粗糙集理论1是波兰数学家Pawlak提出的能有效处理信息系统中不精确、不确定信息的分析方法。粒计算2是人工智能领域中一个新的快速发展的领域，强调从不同层次和粒度分析问题，多粒度是粒计算的一个核心概念。从粒计算的角度来看，经典粗糙集理论主要基于等价关系对论域进行划分形成一个粒度空间，在单粒度空间下对目标概念进行近似逼

7、近。钱宇华等人分析了单一粒度空间下粗糙集的不足，认为应当从多个粒度空问对目标概念进行近似逼近，针对实际的决策问题，可获得更加合理、更加满意的求解L4J。文献35提出了多粒度粗糙集的概念，定义了悲观多粒度粗糙集和乐观多粒度粗糙集，多粒度粗糙集已成为粗糙集理论研究的一个新的热点，引起了许多学者的关注。文献6123分别对多粒度粗糙集的模型扩展及粒度约简算法进行了研究。Ziarko于1993年在经典粗糙集的基础上提出了变精度粗糙集模型13，文献10，11将变精度粗糙集的思想引入了多粒度粗糙集，定义了变精度多粒度粗糙集模型，但没有给出变精度多粒度粗糙集粒度约简的方法。文献12主要研究了基于容差关系的不完

8、备系统中变精度多粒度粗糙集的约简方法。目前对完备决策系统下变精度多粒度粗糙集的粒度约简的研究较少，对变精度多粒度楹糙集中的粒度进行约简，针对不同的精度，删除粒度集中不必要的粒度，有利于进一步从变精度多粒度粗糙集中提取简洁的决策规则。本文将下近似分布约简14的概念引入变精度悲观多粒度粗糙集，并定义了变精度悲观多粒度粗糙集的下近似分布粒度熵，基于下近似分布粒度熵定义了变精度悲观多粒度粗糙集粒度的重要度，设计了基于下近似分布粒度熵的变精度悲观多粒度粗糙集启发式粒度约简算法，该算法的时间复杂度为0(形I Ul 2)，为变精度多粒度粗糙集的应用提供了理论基础。1基本概念11粗糙集的基本概念定义”11 四

9、元组s一(U，AT，V，)称为信息系统，其中U表示对象的非空有限集合，称为论域；AT表示属性的非空有限集合；u表示属性a的值域，V表示全部对象在各个属到稿El期：20150511 返修日期：20150629 本文受国家自然科学基金项目(60873104。61370169)，河南省科技攻关重点项目(112102210194)，河南省教育厅自然科学研究项目(2011A520054)资助。孟慧丽(1978)，女，硕士，讲师，主要研究方向为粗糙集理论、数据挖掘，E-mail：menghuili93163corn；马媛媛(1982一)，女，硕士，主要研究方向为粗糙集理论、数据挖掘；徐久成(1963一)，

10、男，博士，教授，主要研究方向为数据挖掘、粒计算理论、生物信息等。83万方数据性上的取值构成的集合；f表示UATV的一个信息函数，V12AT，工U，f(x，n)V：。定义2E13 设S一(U，AT，V，)为信息系统，VAA丁，定义属性集A的不可区分关系IND(A)为：JND(A)一(z，y)EUXUl VaEA，f(x，丑)一，(j，)，UIND(A)表示不可区分关系IND(A)在U上导出的划分，简记为叫A。对VxEU，IxA=YIf(Y，口)一，(z，n)，VaEA)称为72在属性集A下的等价类。定义311 设s一(U，AT，V，)为信息系统，VAAT，XU，X关于属性集A的下近似集和上近似集

11、分别定义为：A(x)=zU：zAx)，A(x)一TU：zANxD)。定义4”1 设S一(U，AT，V，)是一个信息系统，XU，定义P(zA IX)：蜡其中，I表示集合的基数，P(x3一lX)表示集合zA中的元素包含在集合X中的比例。性质1M oP(A Ix)1。定义5c” 设S一(U，AT，V，力为信息系统，VA至A丁，XCU，对口(o，1，定义X关于A的可变精度下近似：山(x)一xEU：P(-xA x)脚性质210设S一(U，AT，V，jO为信息系统，VAAT，xEu，对阻，胆(o，1，皿团，则鱼(x)鱼(x)。12变精度悲观多粒度粗糙集的基本概念在多粒度粗糙集中，四元组S一(U，AT，V，

12、)是一个完备信息系统，其中A。，A。，A。AT，每个属性集Al称为一个粒度，可以对U基于等价关系jND(A)划分得到一个粒度空间，A一A，A：，A。称为一个粒度集。定义6” 设S一(U，AT，V，)是一个信息系统，其中Al，A2，A。AT，A=A1，A2，A。，V XEU，fie(0，1，X的变精度悲观多粒度下近似、上近似分别定义为：A0(x)一xEU：_P(zA1 Ix)pP(z岛l x)!三! 。9AP(XAm Ix)雕A(x)一A(x)i一1” 兰!：性质3103设S=(【，AT，V，)是一个信息系统，其中Al，A2，A。AT，A一Al，A2，A。)，VXU，则A!：(X)一NA：。(X

13、)。2基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简定义7设S=(U，ATU D，V，)是一个完备决策信息系统，A。，A。，A。AT，D为决策属性，A一A，A2，A。，p(o，1，BA，UD=Y1，Yz，K，则变精度悲观多粒度粗糙集下近似分布定义为：以9(【，D)=善A；(y)，蚤A；(y2)，善A0(L)若岛8(【，D)一懿9(U，D)，则称B为A的p变精度悲观多粒度下近似分布一致集。定义8设S一(U，ATUD，V，)是一个完备决策信息系统，A1，A2，A。EA丁，A一Al，A2，A。)，口(0，13，BA，UD=y。，y2，L)，若B为A的口变精度悲观多粒度下近似分布一致集，且对VB

14、IGB，都有如。4(U，D)848A9(U，D)，则称B为A的口变精度悲观多粒度下近似分布约简。定义9设S=(U，ATU D，V，)是一个完备决策信息系统，A1，A2，A。A11，A一Al，Az，A。，UD=Y1，y2，匕，p(o，1，YA：EA，如果颤口(U，D)一文9(U，D)，则称A在粒度集A中是不必要的，否则称A在粒度集A中是必要的。定理1设S=(U，ATU D，V，)是一个完备决策信息系统，A1，A2，A。AT，A一Al，Az，A。)，UD=Y1，y2，L)，口(o，1，则变精度悲观多粒度粗糙集下近似分布文9(u，D)一A嗵(y)，A9丝尘(y2)，A里2堕(L)。 一 A_上 A_

15、上 A证明：因为如9(u，D)=A0(y1)，A(Y2)，i=1 P i一1 rHZA,e，o(L)，由性质3可知对V匕ffUD，KY_,Ae，n(E)2 jQ垒巨(匕)一。N。A。i(Yj)，则以9(u，D)一AQ0。证明：当SGF(A，A)o时，即G(A一Al D)一G(AID)o，G(A一AI D)G(AD)，从而由定理4可知献一Ap(U，D)以9(U，D)，所以AA在粒度集A中是必要的。反之，若AlA在粒度集A中是必要的，则必有敞一A，p(U，D)文9(u，D)，从而唏(AA。)J D)唏(AD)，由定理2可知q(A D)q(A一A：)l D)，则q(A一(A：)ID)一G口(AlD)

16、O，即SGF(A。，A)0。定义12 粒度集A的核定义为CD卯(A)一AASGF(A；，A)0。定理5设S一(U，ATU D，V，)是一个完备决策信息系统，A1，A2，A。AT，A一A1，A2，A。)，UD一Y1，y2，L，BA，若唏(B D)一q(A D)且对VA。B，SGF(A。，B)O，则B为A的一个变精度悲观下近似分布粒度约简。证明：由定理4可知当G(B D)一G(AD)时，有如9(U，D)一以9(U，D)，即B为A的变精度悲观多粒度下近似分布一致集，而对VA。B，SGF(Ai，B)0，即G(B一A；D)一G(BlD)o，Q(B一A，)JD)G(BlD)，从而如fA)p(U，D)如9(

17、U，D)，因此B为A的变精度悲观多粒度下近似分布粒度约简。3基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简算法本节基于粒度集的下近似分布粒度熵设计了变精度悲观多粒度粗糙集的下近似分布粒度约简算法，将粒度集中不影响对象决策分类的不重要的粒度约简掉，基本思路是首先计算粒度集的核心粒度，并逐个选择粒度重要度最大的粒度加入到核中，最终得到粒度集的一个约简。算法1 基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简算法输入：决策信息系统S一(U，ATUDv，f)，A1，Az，。A。AT，A一A1，A2，A。输出：决策信息系统的一个变精度悲观下近似分布粒度约简CStepl：对每一个A，A，计算UA

18、和UO。Step2：对每一个基于单粒度的粒度空间UA和VYUD，求出UAi中各等价类包含在Yj中的比例，即PCxA：l Yj)，针对给定的p，将P(I-xA；I Yj)p的X加入到Ai8(Yi)，对VAiA，V YjUD，计算出A，B(Yj)。Step3：令BD，对VA，A，计算SGF(Ai，A)，将使SGF(Ai，A)O的Ai增加到粒度集B。Step4：如果G8(BID)=GB(AID)，则C=B，转Step5；否则令Bl=A-B，对VAiB1，计算唏(BID)一Go(BUAilD)，将使下近似分布粒度熵减少最多的粒度增加到属性集B中，B1=B1一Ai，转Step4。Step5：输出粒度约简

19、C，算法结束。算法时间复杂度分析：计算各个粒度对论域划分的时间复杂度为O(研JUl 2)，计算一个粒度划分下的各等价类包含在决策分类K中的比例的时间复杂度为O(IUl 2)，则计算不同粒度划分下的等价类包含在决策分类yi中的比例的时间复杂度为O(rnlUI 2)，知道各对象在不同粒度下的等价类包含在决策分类y!中的比例后，计算A。(Yi)的时间复杂度为0(1UI)，则计算n A。(K)时，需计算m似i。()的交集，A。A其时间复杂度为0(mlUI 2)，则计算SGF(A：，A)、G(BD)、G(A1D)的时间复杂度为0(mIUI 2)，从而对m个粒度，计算SGF(A，A)、G(A一(AiID)

20、的时间复杂度为O(m2 lUI 2)，所以算法总的时间复杂度为O(m2 lUI 2)。4实例分析表1是一个决策信息系统，A=A-，Az，As)表示3种独立的评价指标，U一z。，zz，z。，z。，工s，ze)表示6个待评价的对象，D表示决策属性。UD一y，y2)，Y。=zz，2Cs，zs，ze)，Yz一z。，z。)。根据每个评价指标，对对象的评价分为3类1，2，3，分别表示差，一般，好，如表1所列。对象在不同评价指标下的等价类如表2所列。表2不同评价指标下对象xi的等价类x1 1l，x3 01，x4 ol，x3，x5x2 x2，x4 x2，】c5，】(6 x2，、x3 11，x3 x3 X1x3

21、x5x4 x2， 11，x4 x2，x4)【5 )【5，x6 x2，x5，x6 01，x3，x5当UD=y1，y2，Yl一T2，2C3，z5，“，Yz一2C1，z4)时，各对象在不同评价指标下的等价类包含在K中的比例如表3所列。当口=1z时，文8(U，D)一z2，z。，X5，ze，zt)，根据算法1计算可得纽(y1)一U，A堑(y1)一z2，X3，X5，2C6，A堑(Y1)=U，A1口(Y2)=zl，2C2，z3，z4，A2日(y2)一z1，z4)，A拍(Yz)一z2，zt，由于SGF(A2，A)O，SGF(A，A)O，因此B=Az，A3)，此时(U，D)=“勋，X3，X5，蕊)，X4)一(下

22、转第104页)85万方数据for discovering clusters in large spatial databases with noiseCProceedings of the 2th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining1996，22623163 Sun Hao-jun，Wang Sheng-rui，Jiang Qing-sham FCM-basedmodel selection algorithms for determining the number of clust

23、ersJPattern Recognition，2004，37(10)：20272037ETBai LiangLiang Jiye，Dang Chuang-yim An initialization me-thod to simultaneously find initial cluster centers and the Rumber of clusters for clustering categorical dataJKnowledge-Based Systems，2011，24(6)：785-79583 Liang Jiye，Zhao Xing-wang，Li De-yu，et a1D

24、etermining thenumber of clusters using information entropy for mixed dataJPattern Recognition，2012，45：225122659Tou J，GonzalesRPatternRecognitionPrinciplesMMA：Addison-WesleyReading，1974103 Pal N R，Bazdek J C On clustering validity for the fuzzy c-meansmodelJIEEE Transactions on Fuzzy Systems，1995，3(3

25、)：37037911Xiao Yu，Yu JianSemiSupervised Clustering Based on AffinityPropagation AlgorithmJJJournal of Software，2008，19(11)：28032813(in Chinese)肖宇，于剑基于近邻传播算法的半监督聚类I-j软件学报，2008，19(11)：28032813123 Bilenko M，Basu S，Mooney R JIntegrating constraints andmetric learning in semisupervised clusteringcRuss G，

26、Dale S，edsProcof the 21st Int1 Confon Machine Learning(ICMI，2004)Banff：ACM Press，2004：81-8813Basu S，Banerjee A，Mooney R JSemisupervised clustering byseeding,CClaude S，Achim GH，edsProcof 19th Int1Confon Machine Learning(ICML 2002)Sydney：MorganKaufmann Publishers，2002：273414Kamvar S D，Klein D，Manning

27、C n Spectral learningcProcof the 1 8th Intl Joint Confon Artificial Intelligence(UCAI 2003)Acapulco。Mexico：Morgan Kaufmann Publishers，2003：56卜566(上接第85页)文4(【，D)，G(BID)一G日(AD)，所以B=A2，A3为p一12时粒度集A的一个粒度约简；同理可计算出当卢一1时，文9(U，D)=“如)，D，当B=A3)时，甜(u，D)=“x6，O=懿9(U，D)，Gp(BlD)一Gp(AfD)，所以B=As)为p一1时粒度集A的一个粒度约简。实例表

28、明，在计算变精度悲观多粒度租糙集的粒度约简时，针对给定的精度口，首先计算粒度集的核心粒度，然后以下近似分布粒度熵的变化作为启发式信息，逐个选择粒度重要度最大的粒度加入到核中，最终求得的粒度约简与原始多粒度空间在相同精度下具有同样的决策能力。在本例中，当口一12时，B=Az，A。)为粒度集A的一个约简，评价指标At可忽略，当口=1时，B一A。)为粒度集A的一个约简，评价指标A-、Az可忽略。结束语本文针对变精度悲观多粒度粗糙集模型的粒度约简进行了研究，设计了变精度悲观多粒度粗糙集粒度约简算法，并通过实例验证了该算法的有效性，针对不同的精度，计算粒度集的约简，有利于进一步从变精度悲观多粒度粗糙集中

29、提取更加简洁的决策规则，这为变精度多粒度粗糙集的应用提供了理论基础。参考文献1Pawlak zRough setEJInternational Journal of Computer andInformation Seience，1982，11：341-3562Lin T YGranular computing on binary relations II：Rough setrepresentations and belief functionsMRough Sets andKnowledge Discovery1998：1221403Qian Yu-hua，Liang JiyeRough s

30、et method based on multigranulationsCProceeding of the Fifth IEEE InternationalCOMerence on Cognitive InformaticsBeijing，China，July 2006：2973044Qian Yuhua，LiangJiye，Yao Yiyu，et a1MGRS：A muhigranulation rough setJInformation Sciences，2010，180：9499705Qian Yuhua，Liang Jiye，Wei WeiPessimistic rough deci

31、sioncSecond International Workshop on Rough Sets Theory2010：440-44963 Yang Xibei，Dou Huili，Yang Jing-yuHybird MuhigranulationRough Sots Based on Equivalence RelationsJComputer Sei一104ence，2012，30(11)：165169(in Chinese)杨习贝，窦慧莉，杨静宇基于等价关系的混合多粒度粗糙集J计算机科学，2012，30(11)：1651697Zhang Ming，Tang Zhen-min，Xu We

32、iyan，et a1Variable Multigranulation Rough Set ModelJPattern Recognition and Artificial Intelligence，2012，25(4)：709720(in Chinese)张明，唐振民，徐维艳，等可变多粒度粗糙集模型J模式识别与人工智能，2012，25(4)：7097208Sang Yanli，Qian YuhuaA Granular Space Reduction A矿proach to Pessimistic MultiGranulation Rough SetsJPatternRecognition a

33、nd Artificial Intelligence，2012，25(3)：361366(inChinese)桑妍丽，钱宇华一种悲观多粒度粗糙集中的粒度约简算法J模式识别与人工智能，2012，25(3)：3613669Liu CaihuiCovering-based Multigranulation Rough Set ModelBased on Maximal Description of ElementsJComputer Science，2013，40(12)：6467(in Chinese)刘财辉一种元素最大描述下的多粒度覆盖粗糙集模型J计算机科学，2013，40(12)：6467i0

34、3 Qian Yuhua，Zhang Hu，Sang Yan-li，et a1Multigranulation decisiontheoretic rough sets-JInternational Journal of Approximate Reasoning，2014，55(1)：225237113 Dou Huili，Wu Chen，Yang Xibei，et a1Variable PrecisionMultigranulation Rough Sets,JJournal of Jiangsu Universityof Science and Technology，2012，26(1)

35、：6569(in Chinese)窦慧莉，吴陈，杨习贝，等可变精度多粒度粗糙集模型J江苏科技大学学报，2012，26(1)：656912Zhai Yong-jian，Zhang Hong。Reduction of Variable PrecisionMultigranulation Rough SetsJJournal of Jinling Institute ofTechnology，2013，29(4)：1-8(in Chinese)翟永健，张宏变精度多粒度粗糙集的约简研究J金陵科技学院学报，2013，29(4)：1-813Ziarko wVariable precision rough set modelJJournal ofComputer and System Sciences，1993，46(1)：395914Zhang Wen-xiu，Mi Jusheng，Wu Wei-zhiKnowledge Reduc-tions in Inconsistent Information SystemsJChinese Journal ofComputers，2003，26(1)：1218(in Chinese)张文修，米据生，吴伟志不协调目标信息系统的知识约简J计算机学报，2003，26(1)：1218万方数据