摘要
差别矩阵是很多学者用来计算粗糙集属性约简的一种方法,该方法因其简单、直观、易于理解而得到广泛应用,但是包含在差别矩阵中的冗余元素不仅对属性约简不起作用反而增加存储空间,为消除这些冗余元素提出了一种新的存储结构:二进制链表,通过位运算将差别矩阵中所有的重复元素和父集元素删除,降低差别信息的存储空间。为验证二进制链表的有效性,提出了一种新的属性约简算法。通过UCI数据库中多组数据集对该方法进行测试,并将实验结果与其他算法进行比较,提出的算法可以更快地得到属性约简集并且能够有效地降低存储空间。
The difference matrix is a method used by many scholars to calculate the attribute reduction of rough sets. This method is widely used because it is simple, intuitive and easy to understand, but the redundant elements contained in the difference matrix are not only take no effect on attribute reduction, but also have the problem of high cost of spatial storage.In order to eliminate these redundant elements, a new storage structure is proposed: a binary linked list. All repetitive elements and parent set elements in the discernibility matrix are deleted by bit operation to reduce the storage space of discernibility information. In order to verify the validity of the binary linked list, a new attribute reduction algorithm is proposed. The method is tested by multiple sets of data sets in the UCI database, and the experimental results are compared with other algorithms. The proposed algorithm can get the attribute reduction set faster and can effectively reduce the storage space.
引文
[1] Pawlak Z.Rough Sets[J].International Journal of Computer and In-formation Sciences,1982,11:341-356.
[2] Slowinski R.Intelligent decision support-handbook of applications and advances of the rough sets theory[M].London:Kluwer Academic Publishers,1992.
[3] Yunge Jing,Tianrui Li,Hamido Fujita,et al.An incremental attribute reduction method for dynamic data mining[J].Information Sciences,2018,465:202-218.
[4] Yunge Jing,Tianrui Li,Junfu Huang,et al.A Group Incremental Reduction Algorithm with Varying Data Values[J].International Journal of Intelligent Systems,2017,32(9):900-925.
[5] Yunge Jing,Tianrui Li,Hamido Fujita,et al.An incremental attribute reduction approach based on knowledge granularity with a multi-granulation view[J].Information Sciences,2017,411:23-38.
[6] Yunge Jing,Tianrui Li,Junfu Huang,et al.An incremental attribute reduction approach based on knowledge granularity under the attribute generalization[J].International Journal of Approximate Reasoning,2016,76:80-95.
[7] Hongmei Chen,Tianrui Li,Yong Cai,et al.Parallel attribute reduction in dominance-based neighborhood rough set[J].Information Sciences,2016,373:351-368.
[8] Wen S D,Bao Q H.A fast heuristic attribute reduction approach to ordered decision systems[J].European Journal of Operational Research,2018,264:440-452.
[9] Skowron A,Rauszer C.The discernibility matrices and functions in information systems[C].Intelligent Decision Support,Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht,1991:331-362.
[10] 徐章艳,杨炳儒,宋威.基于简化差别矩阵的完备属性约简算法[J].计算机工程与应用,2006,26(3):167-169.
[11] 周建华,徐章艳,章晨光.改进的差别矩阵的快速属性约简算法[J].小型微型计算机系统,2014,35(4):831-834.
[12] Felix R,Ushio T.Rough sets-based machine learning using a binary discernibility matrix[C].Proceeding of 2nd International Conference on Intelligent Processing and Manufacturing of Materials,Ha-waii,1999:299-305.
[13] 蒙祖强,史忠植.一种新的基于简化二进制可辨矩阵的相对约简算法[J].控制与决策,2008,23(9):976-978.
[14] 王亚琦,范年柏.改进的基于简化二进制分辨矩阵的属性约简方法[J].计算机科学,2015,42(6):210-215.
[15] Yang M,Yang P.A novel condensing tree structure for rough set feature selection[J].Neurocomputing,2008,71(4):1092-1100.
[16] 蒋瑜.基于差别信息树的rough set属性约简算法[J].控制与决策,2015,30(8):1531-1536.
[17] 张文阳,蒋瑜.基于键树的粗糙集属性约简算法[J].成都信息工程大学学报,2017,32(6):618-622.
[18] 唐坤剑,容强.基于加权浓缩树的粗糙集属性约简算法[J].计算机工程与应用,2018,54(2):76-81.
[19] 梅红岩,刘井莲,刘海霞.基于区分链表的属性约简改进算法[J].计算机与信息技术,2008,(Z1):55-56.
[20] 陈炼,吴灵芝.基于链表的不完备决策表属性约简算法[J].科学技术与工程,2015,15(3):250.
