基于压缩决策表的乐观多粒度粗糙集粒度约简算法
|
摘要
粒度约简是多粒度粗糙集研究的一个关键问题。为了从乐观多粒度粗糙集的角度研究粒度约简问题,消除冗余数据,提高粒度约简的效率,提出基于压缩决策表的乐观多粒度粗糙集粒度约简算法。针对乐观多粒度粗糙集模型,引入下近似分布粒度约简的概念;利用线性时间排序算法进行等价类划分,为决策表的压缩和下近似集的计算打下基础;以冗余的决策表为研究对象,以核粒度为初始粒度约简集,以粒度重要性为启发式信息,运用粒度约简算法进行粒度约简,并通过实例分析和实验验证了该算法的有效性。结果表明,算法降低了计算下近似集的时间复杂度,具有较高的粒度约简效率。
Granular space reduction is a key issue in the research of multi-granulation rough sets. In order to eliminate redundant data and speed up the granular space reduction from perspective of optimistic multi-granulation rough sets,a granular space reduction algorithm to optimistic multi-granulation rough sets based on compressed decision table is presented.Firstly,a concept of distribution granular space reduction is introduced. Secondly,equivalence classes are divided using linear time sort algorithm for computing compressed decision table and lower approximation. On this basis,granular space reduction is conducted using the proposed granular space reduction algorithm. Finally,the example and experiments are given to demonstrate the validity of the algorithm. The results show that the proposed algorithm can greatly reduce the time complexity for computing lower approximation and has higher granular space reduction efficiency.
Granular space reduction is a key issue in the research of multi-granulation rough sets. In order to eliminate redundant data and speed up the granular space reduction from perspective of optimistic multi-granulation rough sets,a granular space reduction algorithm to optimistic multi-granulation rough sets based on compressed decision table is presented.Firstly,a concept of distribution granular space reduction is introduced. Secondly,equivalence classes are divided using linear time sort algorithm for computing compressed decision table and lower approximation. On this basis,granular space reduction is conducted using the proposed granular space reduction algorithm. Finally,the example and experiments are given to demonstrate the validity of the algorithm. The results show that the proposed algorithm can greatly reduce the time complexity for computing lower approximation and has higher granular space reduction efficiency.
引文
[1]PAWLAK Z.Rough set[J].International Journal of Computer and Information Science,1982,11(5):341-356.
[2]胡峰,周耀,王蕾.基于邻域粗糙集的主动学习方法[J].重庆邮电大学学报:自然科学版,2017,29(6):776-784.HU Feng,ZHOU Yao,WANG Lei.Algorithm for active learning based on neighbor rough set theory[J].Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition,2017,29(6):776-784.
[3]王宇,杨志荣,杨习贝.决策粗糙集属性约简:一种局部视角方法[J].南京理工大学学报,2016,40(4):444-449.WANG Yu,YANG Zhirong,YANG Xibei.Local attribute reduction approach based on decision-theoretic rough set[J].Journal of Nanjing University of Science and Technology,2016,40(4):444-449.
[4]张超,李德玉,翟岩慧.双论域上的犹豫模糊语言多粒度粗糙集及其应用[J].控制与决策,2017,32(1):105-110.ZHANG Chao,LI Deyu,ZHAI Yanhui.Hesitant fuzzy linguistic multigranulation rough set over two universes and its application[J].Control and Decision,2017,32(1):105-110.
[5]张云雷,吴斌,刘宇.一种新的基于粗糙集K-均值的社区发现方法[J].电子与信息学报,2017,39(4):770-777.ZHANG Yunlei,WU Bin,LIU Yu.A novel community detection method based on rough set K-means[J].Journal of Electronics&Information Technology,2017,39(4):770-777.
[6]QIAN Yuhua,LIANG Jiye,YAO Yiyu,et al.MGRS:Amulti-granulation rough set[J].Information Sciences,2010,180(6):949-970.
[7]桑妍丽,钱宇华.一种悲观多粒度粗糙集中的粒度约简算法[J].模式识别与人工智能,2012,25(3):361-366.SANG Yanli,QIAN Yuhua.A granular space reduction approach to pessimistic multi-granulation rough sets[J].Pattern Recognition and Artificial Intelligence,2012,25(3):361-366.
[8]汪小燕,申元霞.基于粒度矩阵的程度多粒度粗糙集粒度约简[J].系统工程与电子技术,2016,38(12):2889-2893.WANG Xiaoyan,SHEN Yuanxia.Granulation reduction of graded multi-granulation rough set based on granulation matrix[J].Systems Engineering and Electronics,2016,38(12):2889-2893.
[9]孟慧丽,马媛媛,徐久成.基于信息量的悲观多粒度粗糙集粒度约简[J].南京大学学报:自然科学版,2015,51(2):343-348.MENG Huili,MA Yuanyuan,XU Jiucheng.The granularity reduction of pessimistic multi-granulation rough set based on the information quantity[J].Journal of Nanjing University:Natural Sciences Edition,2015,51(2):343-348.
[10]张艳芹.模糊多粒度粗糙集约简方法研究[J].武汉理工大学学报,2014,36(8):133-137.ZHANG Yanqin.Researching on reduct of fuzzy multigranulation rough set[J].Journal of Wuhan University of Technology,2014,36(8):133-137.
[11]张明,程科,杨习贝,等.基于加权粒度的多粒度粗糙集[J].控制与决策,2015,30(2):222-228.ZHANG Ming,CHENG Ke,YANG Xibei,et al.Multigranulation rough set based on weighted granulations[J].Control and Decision,2015,30(2):222-228.
[12]张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18.ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge Reduction in Inconsistent Information Systems[J].Chinese Journal of Computers,2003,26(1):12-18.
[13]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.WANG Guoyin.Rough set theory and knowledge acquisition[M].Xi’an:Xi’an Jiaotong University Press,2001.
[14]刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展,2003,40(5):637-642.LIU Shaohui,SHENG Qiujian,SHI Zhongzhi.A new method for fast computing positive region[J].Journal of Computer Research and Development,2003,40(5):637-642.
[15]杨红颖,王向阳.一种新的按位块分段快速排序算法[J].微电子学与计算机,2006,23(8):136-139.YANG Hongying,WANG Xiangyang.Fast sorting method of separating segment according bit field[J].Microelectronics&Computer,2006,23(8):136-139.
[16]徐章艳,杨炳儒,宋威.基于简化的二进制差别矩阵的快速属性约简算法[J].计算机科学,2006,33(4):1711-1714.XU Zhangyan,YANG Bingru,SONG Wei.Quick attribution reduction algorithm based on simple binary discernibility matrix[J].Computer Science,2006,33(4):1711-1714.
[17]YANG X B,QI Y S,SONG X N,et al.Test cost sensitive multigranulation rough set:model and minimal cost selection[J].Information Sciences,2013,250(11):184-199.
[2]胡峰,周耀,王蕾.基于邻域粗糙集的主动学习方法[J].重庆邮电大学学报:自然科学版,2017,29(6):776-784.HU Feng,ZHOU Yao,WANG Lei.Algorithm for active learning based on neighbor rough set theory[J].Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition,2017,29(6):776-784.
[3]王宇,杨志荣,杨习贝.决策粗糙集属性约简:一种局部视角方法[J].南京理工大学学报,2016,40(4):444-449.WANG Yu,YANG Zhirong,YANG Xibei.Local attribute reduction approach based on decision-theoretic rough set[J].Journal of Nanjing University of Science and Technology,2016,40(4):444-449.
[4]张超,李德玉,翟岩慧.双论域上的犹豫模糊语言多粒度粗糙集及其应用[J].控制与决策,2017,32(1):105-110.ZHANG Chao,LI Deyu,ZHAI Yanhui.Hesitant fuzzy linguistic multigranulation rough set over two universes and its application[J].Control and Decision,2017,32(1):105-110.
[5]张云雷,吴斌,刘宇.一种新的基于粗糙集K-均值的社区发现方法[J].电子与信息学报,2017,39(4):770-777.ZHANG Yunlei,WU Bin,LIU Yu.A novel community detection method based on rough set K-means[J].Journal of Electronics&Information Technology,2017,39(4):770-777.
[6]QIAN Yuhua,LIANG Jiye,YAO Yiyu,et al.MGRS:Amulti-granulation rough set[J].Information Sciences,2010,180(6):949-970.
[7]桑妍丽,钱宇华.一种悲观多粒度粗糙集中的粒度约简算法[J].模式识别与人工智能,2012,25(3):361-366.SANG Yanli,QIAN Yuhua.A granular space reduction approach to pessimistic multi-granulation rough sets[J].Pattern Recognition and Artificial Intelligence,2012,25(3):361-366.
[8]汪小燕,申元霞.基于粒度矩阵的程度多粒度粗糙集粒度约简[J].系统工程与电子技术,2016,38(12):2889-2893.WANG Xiaoyan,SHEN Yuanxia.Granulation reduction of graded multi-granulation rough set based on granulation matrix[J].Systems Engineering and Electronics,2016,38(12):2889-2893.
[9]孟慧丽,马媛媛,徐久成.基于信息量的悲观多粒度粗糙集粒度约简[J].南京大学学报:自然科学版,2015,51(2):343-348.MENG Huili,MA Yuanyuan,XU Jiucheng.The granularity reduction of pessimistic multi-granulation rough set based on the information quantity[J].Journal of Nanjing University:Natural Sciences Edition,2015,51(2):343-348.
[10]张艳芹.模糊多粒度粗糙集约简方法研究[J].武汉理工大学学报,2014,36(8):133-137.ZHANG Yanqin.Researching on reduct of fuzzy multigranulation rough set[J].Journal of Wuhan University of Technology,2014,36(8):133-137.
[11]张明,程科,杨习贝,等.基于加权粒度的多粒度粗糙集[J].控制与决策,2015,30(2):222-228.ZHANG Ming,CHENG Ke,YANG Xibei,et al.Multigranulation rough set based on weighted granulations[J].Control and Decision,2015,30(2):222-228.
[12]张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18.ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge Reduction in Inconsistent Information Systems[J].Chinese Journal of Computers,2003,26(1):12-18.
[13]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.WANG Guoyin.Rough set theory and knowledge acquisition[M].Xi’an:Xi’an Jiaotong University Press,2001.
[14]刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展,2003,40(5):637-642.LIU Shaohui,SHENG Qiujian,SHI Zhongzhi.A new method for fast computing positive region[J].Journal of Computer Research and Development,2003,40(5):637-642.
[15]杨红颖,王向阳.一种新的按位块分段快速排序算法[J].微电子学与计算机,2006,23(8):136-139.YANG Hongying,WANG Xiangyang.Fast sorting method of separating segment according bit field[J].Microelectronics&Computer,2006,23(8):136-139.
[16]徐章艳,杨炳儒,宋威.基于简化的二进制差别矩阵的快速属性约简算法[J].计算机科学,2006,33(4):1711-1714.XU Zhangyan,YANG Bingru,SONG Wei.Quick attribution reduction algorithm based on simple binary discernibility matrix[J].Computer Science,2006,33(4):1711-1714.
[17]YANG X B,QI Y S,SONG X N,et al.Test cost sensitive multigranulation rough set:model and minimal cost selection[J].Information Sciences,2013,250(11):184-199.