计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 242-251.doi: 10.11896/jsjkx.180901781
于天佑1,2, 张楠1,2, 岳晓冬3, 童向荣1,2, 孔贺庆1,2
YU Tian-you1,2, ZHANG Nan1,2, YUE Xiao-dong3, TONG Xiang-rong1,2, KONG He-qing1,2
摘要: 属性约简是粗糙集理论研究的重要内容之一,通过属性约简可以获取给定信息系统的最小特征子集。经典的序决策表属性约简是关于决策属性中的所有决策类的约简,但在实际应用中,由于决策者的偏好或者部分决策类数据的缺失,往往仅需要获得特定决策类的属性约简。基于这种考虑,文中回顾了序决策表的优势关系与下近似约简,定义了基于序决策表的单特定类与多特定类下近似约简,构造了相应的差别矩阵,提出了基于多特定类的序决策表下近似属性约简算法。基于多特定类的序决策表下近似约简可以较好地退化为基于单特定类的序决策表下近似约简或基于经典全决策类的序决策表下近似约简,是一种更加广泛的约简框架。实验采用了6组UCI数据集,分别在每个数据集上计算了3个单特定类和3组多特定类的约简,并将约简结果和约简效率与经典全类下近似约简、上近似约简及最大分布约简3个算法的约简结果和约简效率进行了比较。实验结果表明,在选定的特定类的数量相对全部决策类的数量较少时,约简的结果可能会更短,约简的效率也会有不同程度的提升。
中图分类号:
[1]PAWLAK Z.Rough sets [J].International Journal of Computer and Information Sciences,1982,11(5):341-356. [2]PAWLAK Z.Rough sets:Theoretical aspects of reasoning about data [M].Dordrecht:Kluwer Academic Publishers,1992. [3]WANG G Y,YAO Y Y,YU H.A survey on rough set theory and applications [J].Chinese Journal of Computers,2009,32(7):1229-1246.(in Chinese) 王国胤,姚一豫,于洪.粗糙集理论与应用研究综述[J].计算机学报,2009,32(7):1229-1246. [4]SKOWRON A,RAUSZER C.The discernibility matrices and functions in information systems [J].Theory and Decision Library,1992,11:331-362. [5]LI W T,XU W H,Multigranulation decision-theoretic rough set in ordered information system [J].Fundamenta Informaticae,2015,139(1):67-89. [6]SAI Y,YAO Y Y,ZHONG N.Data analysis and mining in ordered information tables [C]//Proceedings of 2001 IEEE International Conference on Data Mining.Washington DC:IEEE Computer Society Press,2001:497-504. [7]DEMBCZYNSKI K,PINDUR R,SUSMAGA R.Generation of exhaustive set of rules within dominance-based rough set approach [J].Electronic Notes Theory Computer Science,2003,82(4):96-107. [8]GRECO S,MATARAZZO B,SLOWINSKI R.Rough approxi-mation by dominance relations [J].International Journal of Intelligent Systems,2002,17(2):153-171. [9]GEDIGA G,RUNTSCH I.Rough approximation quality revisited [J].Artificial Intelligence,2001,132(2):219-234. [10]GRECO S,MATARAZZO B,SLOWINSKI R.Rough approximation of a preference relation by dominance relation [J].Europe Journal of Operation Research,1999,117(1):63-83. [11]ZHANG Q G,ZHANG P,WANG G Y.Research on approximation set of rough set based on fuzzy similarity [J].Journal of Intelligent and Fuzzy System,2017,32(3):2549-2562. [12]ZHANG H Y,LEUNG Y,ZHOU L.Variable-precision-dominance-based rough set approach to interval-valued information systems [J].Information Sciences,2013,244:75-91. [13]GU S M,HU C,WU W Z,et al.Uncertainty measures in multi-label ordered information systems [J].Journal of Nanjing University,2015,51(2):377-383.(in Chinese) 顾沈明,胡超,吴伟志,等.多标记序信息系统的不确定性研究[J].南京大学学报(自然科学),2015,51(2):377-383. [14]ZHANG X Y,XU W H.Lower Approximation reduction in ordered information system with fuzzy decision [J].Applied Mathmatics,2011,2(7):918-921. [15]SUSMAGA R.Reducts and constructs in classic and dominance-based rough sets approach [J].Information Sciences,2014,271:45-64. [16]CHEN H M,LI T R,CAI Y,et al.Parallel attribute reduction in dominance-based neighborhood rough set [J].InformationScie-nces,2016,373:351-368. [17]ZHANG X Y,XU W H,ZHANG W X.A novel algorithm of matrix computation for lower approximation reduction in IOIS [C]//2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery.Washington DC:IEEE Computer Society Press,2010,8:1876-1880. [18]WANG F,QIAN Y H,LIANG J Y.Heuristic attribute reduction algorithm to ordered information systems [J].Computer Science,2010,37(1):258-260.(in Chinese) 王锋,钱宇华,梁吉业.序信息系统的启发式属性约简算法[J].计算机科学,2010,37(1):258-260. [19]SHI D R,XU W H.Distribution reduction in interval-valued fuzzy decision ordered information systems [J].Journal of Frontiers of Computer Science and Technology,2017,11(4):652-658.(in Chinese) 史德容,徐伟华.区间值模糊决策序信息系统的分布约简[J].计算机科学与探索,2017,11(4):652-658. [20]HUANG Q,WEI L.Attribute reduction approach to an ordered information system based on boolean matrix [J].Journal of Chinese Mini-Micro Computer Systems,2016,37(8):1717-1720.(in Chinese) 黄琴,魏玲.基于布尔矩阵的序信息系统属性约简方法[J].小型微型计算机系统,2016,37(8):1717-1720. [21]YAN Y J,DAI J H.Unsupervised feature selection for interval ordered information systems [J].Pattern Recognition and Artificial Intelligence,2017,30(10):928-936.(in Chinese) 闫岳君,代建华.区间序信息系统的无监督特征选择[J].模式识别与人工智能,2017,30(10):928-936. [22]XU W H,ZHANG X Y,ZHANG W X.Upper Approximation Reduction in Inconsistent Target Information System Based on Dominance Relations [J].Computer Engineering,2009,2010(16):1012-1013.(in Chinese) 徐伟华,张晓燕,张文修.优势关系下不协调目标信息系统的上近似约简[J].计算机工程,2009,2010(16):1012-1013. [23]XU W H,ZHANG W X.Methods for knowledge reduction in inconsistent ordered information systems [J].Journal of Applied Mathematics and Computing,2008,26(1/2):313-323. [24]XU W H,LI Y,LIAO X W.Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems [J].Knowledge-Based Systems,2012,27:78-91. [25]XU W H,ZHANG W X.Uncertainty measures of roughness of knowledge and rough sets in ordered information systems [J].Lecture Notes in Artificial Intelligence,2007,4682:759-769. [26]QIAN Y H,LIANG J Y,DANG C Y.Interval ordered information systems [J].Computers and Mathematics with Applications,2008,56(8):1994-2009. [27]QIAN Y H,LIANG J Y,DANG C Y,et al.Set-valued ordered information systems [J].Information Sciences,2009,179(16):2809-2832. [28]LIU G L,HUA Z,ZOU J Y.Local attribute reductions for decision tables [J].Information Sciences,2017,422:204-217. [29]QIAN Y H,LIANG X Y,WANG Q,et al.Local rough set:a solution to rough data analysis in big data [J].International Journal of Approximate Reasoning,2018,97:38-63. [30]YAO Y Y,ZHANG X Y.Class-specific attribute reducts in rough set theory [J].Information Sciences,2017,418:601-618. [31]BAGGENSTOSS P M.Class-specific feature sets in classification [J].IEEE Trans.on Signal Processing,1999,47(12):3428-3432. [32]PINEDA-BAUTISTA B B,CARRASCO-OCHOA J A,MAR-TíNEZ-TRINIDAD J F.General framework for class-specific feature selection [J].Expert Systems with Applications,2011,38(8):10018-10024. [33]CHEN D G,ZHAO S Y.Local reduction of decision system with fuzzy rough sets [J].Fuzzy Sets and Systems,2010,161(13):1871-1883. [34]YANG X B,QI Y,YU D J,et al.α-Dominance relation and rough sets in interval-valued information systems [J].Information Sciences,2015,294:334-347. |
[1] | 程富豪, 徐泰华, 陈建军, 宋晶晶, 杨习贝. 基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法 Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory 计算机科学, 2022, 49(8): 97-107. https://doi.org/10.11896/jsjkx.210700202 |
[2] | 许思雨, 秦克云. 基于剩余格的模糊粗糙集的拓扑性质 Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices 计算机科学, 2022, 49(6A): 140-143. https://doi.org/10.11896/jsjkx.210200123 |
[3] | 方连花, 林玉梅, 吴伟志. 随机多尺度序决策系统的最优尺度选择 Optimal Scale Selection in Random Multi-scale Ordered Decision Systems 计算机科学, 2022, 49(6): 172-179. https://doi.org/10.11896/jsjkx.220200067 |
[4] | 陈于思, 艾志华, 张清华. 基于三角不等式判定和局部策略的高效邻域覆盖模型 Efficient Neighborhood Covering Model Based on Triangle Inequality Checkand Local Strategy 计算机科学, 2022, 49(5): 152-158. https://doi.org/10.11896/jsjkx.210300302 |
[5] | 孙林, 黄苗苗, 徐久成. 基于邻域粗糙集和Relief的弱标记特征选择方法 Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief 计算机科学, 2022, 49(4): 152-160. https://doi.org/10.11896/jsjkx.210300094 |
[6] | 王子茵, 李磊军, 米据生, 李美争, 解滨. 基于误分代价的变精度模糊粗糙集属性约简 Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost 计算机科学, 2022, 49(4): 161-167. https://doi.org/10.11896/jsjkx.210500211 |
[7] | 王志成, 高灿, 邢金明. 一种基于正域的三支近似约简 Three-way Approximate Reduction Based on Positive Region 计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067 |
[8] | 薛占熬, 侯昊东, 孙冰心, 姚守倩. 带标记的不完备双论域模糊概率粗糙集中近似集动态更新方法 Label-based Approach for Dynamic Updating Approximations in Incomplete Fuzzy Probabilistic Rough Sets over Two Universes 计算机科学, 2022, 49(3): 255-262. https://doi.org/10.11896/jsjkx.201200042 |
[9] | 李艳, 范斌, 郭劼, 林梓源, 赵曌. 基于k-原型聚类和粗糙集的属性约简方法 Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets 计算机科学, 2021, 48(6A): 342-348. https://doi.org/10.11896/jsjkx.201000053 |
[10] | 薛占熬, 孙冰心, 侯昊东, 荆萌萌. 基于多粒度粗糙直觉犹豫模糊集的最优粒度选择方法 Optimal Granulation Selection Method Based on Multi-granulation Rough Intuitionistic Hesitant Fuzzy Sets 计算机科学, 2021, 48(10): 98-106. https://doi.org/10.11896/jsjkx.200800074 |
[11] | 曾惠坤, 米据生, 李仲玲. 形式背景中概念及约简的动态更新方法 Dynamic Updating Method of Concepts and Reduction in Formal Context 计算机科学, 2021, 48(1): 131-135. https://doi.org/10.11896/jsjkx.200800018 |
[12] | 薛占熬, 张敏, 赵丽平, 李永祥. 集对优势关系下多粒度决策粗糙集的可变三支决策模型 Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation 计算机科学, 2021, 48(1): 157-166. https://doi.org/10.11896/jsjkx.191200175 |
[13] | 桑彬彬, 杨留中, 陈红梅, 王生武. 优势关系粗糙集增量属性约简算法 Incremental Attribute Reduction Algorithm in Dominance-based Rough Set 计算机科学, 2020, 47(8): 137-143. https://doi.org/10.11896/jsjkx.190700188 |
[14] | 陈玉金, 徐吉辉, 史佳辉, 刘宇. 基于直觉犹豫模糊集的三支决策模型及其应用 Three-way Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications 计算机科学, 2020, 47(8): 144-150. https://doi.org/10.11896/jsjkx.190800041 |
[15] | 岳晓威, 彭莎, 秦克云. 基于面向对象(属性)概念格的形式背景属性约简方法 Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice 计算机科学, 2020, 47(6A): 436-439. https://doi.org/10.11896/JsJkx.191100011 |
|