• 数据库&大数据&数据科学 •

### 一种基于正域的三支近似约简

1. 深圳大学计算机与软件学院 广东 深圳 518060; 深圳大学智能信息处理重点实验室 广东 深圳 518060
• 收稿日期:2021-05-10 修回日期:2021-10-15 发布日期:2022-04-01
• 通讯作者: 高灿(2005gaocan@163.com)
• 作者简介:(wzc2802005420@163.com)
• 基金资助:
国家自然科学基金(61806127,62076164); 佛山市教育局项目(2019XJZZ05)

### Three-way Approximate Reduction Based on Positive Region

WANG Zhi-cheng, GAO Can, XING Jin-ming

1. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, ChinaKey Laboratory of Intelligent Information Processing, Shenzhen, Guangdong 518060, China
• Received:2021-05-10 Revised:2021-10-15 Published:2022-04-01
• About author:WANG Zhi-cheng,born in 1998,postgraduate.His main research interests include machine learning and granular computing.GAO Can,born in 1983,Ph.D,assistant professor,master supervisor.His main research interests include machine lear-ning and computer vision.
• Supported by:
This work was supported by the National Natural Science Foundation of China(61806127,62076164) and Bureau of Education of Foshan(2019XJZZ05).

Abstract: Attribute reduction is one of the most important research topics in the theory of three-way decision.However, the existing attribute reduction methods based on three-way decision are too strict, which limit the efficiency of attribute reduction.In this paper, a three-way approximate attribute reduction method based on the positive region is proposed.More specifically, attri-bute reduction is considered as the process of determining attributes as positive, boundary, or negative ones according to their correlation to the decision attribute.The negative attributes are first removed by retaining the measure of the positive region.Then, some of the boundary attributes are iteratively excluded by relaxing the positive region measure.Finally, an approximate reduction is formed by the remaining attributes.Extensive experiments on UCI data sets demonstrate that the proposed method can achieve much smaller reducts with the same or even better performance in comparison with other representative methods, showing the effectiveness in attribute reduction.

• TP391
 [1] LI Y,LI T,LIU H.Recent advances in feature selection and its applications[J].Knowledge and Information Systems,2017,53(3):551-577.[2] BISHOP C M.Pattern recognition and machine learning[M].New York:Springer,2006.[3] ARMANFARD N,REILLY J P,KOMEILI M.Local feature selection for data classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2015,38(6):1217-1227.[4] MIAO D Q,ZHAO Y,YAO Y Y,et al.Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model[J].Information Sciences,2009,179(24):4140-4150.[5] LI F,MIAO D Q,PEDRYCZ W.Granular multi-label feature selection based on mutual information[J].Pattern Recognition,2017,67:410-423.[6] YAO Y Y,ZHAO Y.Discernibility matrix simplification forconstructing attribute reducts[J].Information Sciences,2009,179(7):867-882.[7] LAI Z H,YONG X,JIAN Y,et al.Rotational invariant dimensionality reduction algorithms[J].IEEE Transactions on Cybernetics,2016,47(11):3733-3746.[8] WANG X,PENG Z H,LI J Y,et al.Method of Concept Reduction Based on Concept Discernibility Matrix[J].Computer Science,2021,48(1):125-130.[9] ZENG H K,MI J S,LI Z L.Dynamic Updating Method of Concepts and Reduction in Formal Context[J].Computer Science,2021,48(1):131-135.[10] PAWLAK Z.Rough sets[J].International Journal of Computer &Information Sciences,1982,11(5):341-356.[11] YAO Y Y.Three-way decisions with probabilistic rough sets[J].Information Sciences,2010,180(3):341-353.[12] YAO Y Y.Three-way decision and granular computing[J].International Journal of Approximate Reasoning,2018,103:107-123.[13] YAO Y Y.Three-way granular computing,rough sets,and formal concept analysis[J].International Journal of Approximate Reasoning,2020,116:106-125.[14] YAO Y Y,ZHAO Y.Attribute reduction in decision-theoreticrough set models[J].Information Sciences,2008,178(17):3356-3373.[15] YAO Y Y.Three-way conflict analysis:Reformulations and extensions of the Pawlak model[J].Knowledge-Based Systems,2019,180:26-37.[16] YAO Y Y.Three-way decisions and cognitive computing[J].Cognitive Computation,2016,8(4):543-554.[17] ZHAO Y,WONG S K M,YAO Y Y.A note on attribute reduction in the decision-theoretic rough set model[C]//Transactions on Rough Sets XIII.Berlin:Springer,2011:260-275.[18] LI H X,ZHOU X Z,ZHAO J B,et al.Non-monotonic attribute reduction in decision-theoretic rough sets[J].Fundamenta Informaticae,2013,126(4):415-432.[19] MA X A,WANG G Y,YU H.Heuristic method to attribute reduction for decision region distribution preservation[J].Ruan Jian Xue Bao/Journal of Software,2014,25(8):1761-1780.[20] MA X A,WANG G Y,YU H,et al.Decision region distribution preservation reduction in decision-theoretic rough set model[J].Information Sciences,2014,278:614-640.[21] GAO C,LAI Z H,ZHOU J,et al.Maximum decision entropy-based attribute reduction in decision-theoretic rough set model[J].Knowledge-Based Systems,2018,143:179-191.[22] ZHANG X Y,MIAO D Q.Region-based quantitative and hierarchical attribute reduction in the two-category decision theoretic rough set model[J].Knowledge-Based Systems,2014,71:146-161.[23] ZHANG X Y,MIAO D Q.Reduction target structure-based hie-rarchical attribute reduction for two-category decision-theoretic rough sets[J].Information Sciences,2014,277:755-776.[24] JIA X Y,LIAO W H,TANG Z M,et al.Minimum cost attribute reduction in decision-theoretic rough set models[J].Information Sciences,2013,219:151-167.[25] JIA X Y,TANG Z M,LIAO W H,et al.On an optimization representation of decision-theoretic rough set model[J].International Journal of Approximate Reasoning,2014,55(1):156-166.[26] LIAO S J,ZHU Q X,FAN M.Cost-sensitive attribute reduction in decision-theoretic rough set models[J].Mathematical Problems in Engineering,2014,35(1):1-9.[27] SLEZAK D.Approximate reducts in decision tables[C]//Proceedings of IPMU’ 96.Granada:Spain,1996:1159-1164.[28] SLEZAK D.Approximate entropy reducts[J].FundamentalInformaticae,2002,53(3/4):365-390.[29] YANG M.Approximate reduction based on conditional information entropy in decision tables[J].Acta Electronica Sinica,2007,35(11):2156-2160.[30] YANG X,LI T R,LIU D,et al.A unified framework of dynamic three-way probabilistic rough sets[J].Information Sciences,2017,420:126-147.[31] ZHANG Q H,XIE Q,WANG G Y.A survey on rough set theory and its applications[J].CAAI Transactions on Intelligence Technology,2016,1(4):323-333.[32] YAO Y Y,WONG S K M.A decision theoretic framework for approximating concepts[J].International Journal of Man-machine Studies,1992,37(6):793-809.[33] LICHMAN M.UCI machine learning repository [DB/OL].University of California,Irvine,CA,USA,2013.http://archive.ics.uci.edu/ml.[34] PEDREGOSA F,VAROQUAUX G,GRAMFORT A,et al.Scikit-learn:Machine learning in Python[J].Journal of Machine Learning Research,2011,12:2825-2830.
 [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] 薛占熬, 侯昊东, 孙冰心, 姚守倩. 带标记的不完备双论域模糊概率粗糙集中近似集动态更新方法 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 [8] 张师鹏, 李永忠. 基于降噪自编码器和三支决策的入侵检测方法 Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions 计算机科学, 2021, 48(9): 345-351. https://doi.org/10.11896/jsjkx.200500059 [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] 王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023 [11] 辛现伟, 史春雷, 韩雨琦, 薛占熬, 宋继华. 基于三支决策的增量标签传播算法 Incremental Tag Propagation Algorithm Based on Three-way Decision 计算机科学, 2021, 48(11A): 102-105. https://doi.org/10.11896/jsjkx.210300065 [12] 薛占熬, 孙冰心, 侯昊东, 荆萌萌. 基于多粒度粗糙直觉犹豫模糊集的最优粒度选择方法 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 [13] 曾惠坤, 米据生, 李仲玲. 形式背景中概念及约简的动态更新方法 Dynamic Updating Method of Concepts and Reduction in Formal Context 计算机科学, 2021, 48(1): 131-135. https://doi.org/10.11896/jsjkx.200800018 [14] 梁伟, 段晓东, 徐健锋. 基于差异性度量的基础聚类三支过滤算法 Three-way Filtering Algorithm of Basic Clustering Based on Differential Measurement 计算机科学, 2021, 48(1): 136-144. https://doi.org/10.11896/jsjkx.200700213 [15] 薛占熬, 张敏, 赵丽平, 李永祥. 集对优势关系下多粒度决策粗糙集的可变三支决策模型 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
Viewed
Full text

Abstract

Cited

Shared
Discussed