属性集变化条件下集值决策信息系统的增量属性约简方法

doi:10.11772/j.issn.1001-9081.2021051024

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (2): 463-468.DOI: 10.11772/j.issn.1001-9081.2021051024

• 数据科学与技术 • 上一篇

属性集变化条件下集值决策信息系统的增量属性约简方法

刘超¹^,², 王磊¹^,²(), 杨文¹^,², 钟强强¹^,², 黎敏¹^,²

^1.南昌工程学院信息工程学院, 南昌 330099
^2.江西省水信息协同感知与智能处理重点实验室(南昌工程学院), 南昌 330099

收稿日期:2021-06-15 修回日期:2021-07-17 接受日期:2021-07-21 发布日期:2022-02-21 出版日期:2022-02-10
通讯作者: 王磊
作者简介:刘超（1997—），男，江苏靖江人，硕士研究生，CCF学生会员，主要研究方向：粗糙集、三支决策、粒计算；
王磊（1967—），男，湖北鄂州人，教授，博士，CCF会员，主要研究方向：粗糙集、数据挖掘、知识发现；
杨文（1996—），女，四川广安人，硕士研究生，CCF学生会员，主要研究方向：粒计算、粗糙集、数据挖掘；
钟强强（1994—），男，江西赣州人，硕士研究生，主要研究方向：粒计算、粗糙集、数据挖掘；
黎敏（1975—），男，江西南昌人，教授，博士，主要研究方向：机器学习、数据挖掘、粗糙集、粒计算。
基金资助:
国家自然科学基金资助项目(61562061);江西省教育厅科技项目(GJJ170995)

Incremental attribute reduction method for set-valued decision information system with variable attribute sets

Chao LIU¹^,², Lei WANG¹^,²(), Wen YANG¹^,², Qiangqiang ZHONG¹^,², Min LI¹^,²

^1.School of Information Engineering，Nanchang Institute of Technology，Nanchang 330099，China
^2.Jiangxi Province Key Laboratory of Water Information Cooperative Sensing and Intelligent Processing （Nanchang Institute of Technology），Nanchang 330099，China

Received:2021-06-15 Revised:2021-07-17 Accepted:2021-07-21 Online:2022-02-21 Published:2022-02-10
Contact: Lei WANG
About author:LIU Chao， born in 1997， M. S. candidate. His research interests include rough set， three-way decision， granular computing.
WANG Lei， born in 1967， Ph. D.， professor. His research interests include rough set， data mining， knowledge discovery.
YANG Wen， born in 1996， M. S. candidate. Her research interests include granular computing， rough set， data mining.
ZHONG Qiangqiang， born in 1994， M. S. candidate. His research interests include granular computing， rough set， data mining.
LI Min， born in 1975， Ph. D.， professor. His research interests include machine learning， data mining， rough set， granular computing.
Supported by:
National Natural Science Foundation of China(61562061);Science and Technology Project of Jiangxi Provincial Department of Education(GJJ170995)

摘要/Abstract

摘要：

为了解决集值决策信息系统中的属性数量不断发生动态变化时，静态属性约简方法无法高效更新属性约简的问题，提出一种以知识粒度为启发信息的增量式属性约简方法。首先，介绍集值决策信息系统的相关概念，接着介绍知识粒度的定义并将其矩阵表示方法推广到此系统中；然后，分析增量式约简的更新机制，并基于知识粒度设计了增量式属性约简方法；最后，选取了3个不同的数据集进行实验。当3个数据集的属性数由20%增加到100%时，传统的非增量式方法的约简耗时分别为54.84 s、108.01 s、565.93 s，增量式方法的约简耗时分别为7.57 s、4.85 s、50.39 s。实验结果表明，在不影响属性约简精度的前提下，所提出的增量式方法比非增量式方法更加快速。

关键词: 粗糙集理论, 集值决策信息系统, 知识粒度, 属性约简, 增量学习

Abstract:

In order to solve the problem that static attribute reduction cannot update attribute reduction efficiently when the number of attributes in the set-valued decision information system changes continuously， an incremental attribute reduction method with knowledge granularity as heuristic information was proposed. Firstly， the related concepts of the set-valued decision information system were introduced， then the definition of knowledge granularity was introduced， and its matrix representation method was extended to this system. Secondly， the update mechanism of incremental reduction was analyzed， and an incremental attribute reduction method was designed on the basis of knowledge granularity. Finally， three different datasets were selected for the experiments. When the number of attributes of the three datasets increased from 20% to 100%， the reduction time of the traditional non-incremental method was 54.84 s， 108.01 s， and 565.93 s respectively， and the reduction time of the incremental method was 7.57 s， 4.85 s， and 50.39 s respectively. Experimental results demonstrate that the proposed incremental method is more faster than the non-incremental method under the condition that the accuracy of attribute reduction is not affected.

Key words: rough set theory, set-valued decision information system, knowledge granularity, attribute reduction, incremental learning

中图分类号:

TP311

刘超, 王磊, 杨文, 钟强强, 黎敏. 属性集变化条件下集值决策信息系统的增量属性约简方法[J]. 计算机应用, 2022, 42(2): 463-468.

Chao LIU, Lei WANG, Wen YANG, Qiangqiang ZHONG, Min LI. Incremental attribute reduction method for set-valued decision information system with variable attribute sets[J]. Journal of Computer Applications, 2022, 42(2): 463-468.

图/表 5

表1 集值决策信息系统

Tab. 1 Set-valued decision information system

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$d$
$x 1$	｛1｝	｛1，2｝	｛1｝	｛1，2｝	｛2｝	｛1｝
$x 2$	｛1，2｝	｛2｝	｛1，2｝	｛1｝	｛1｝	｛1｝
$x 3$	｛1｝	｛1，2｝	｛1｝	｛1，2｝	｛1｝	｛2｝
$x 4$	｛1｝	｛1｝	｛1｝	｛1｝	｛1，2｝	｛1｝
$x 5$	｛2｝	｛1｝	｛1，2｝	｛2｝	｛1｝	｛1｝
$x 6$	｛1，2｝	｛1｝	｛1，2｝	｛1｝	｛1｝	｛2｝
$x 7$	｛1｝	｛1，2｝	｛1，2｝	｛1｝	｛2｝	｛2｝
$x 8$	｛1，2｝	｛2｝	｛2｝	｛2｝	｛1，2｝	｛1｝

表1 集值决策信息系统

Tab. 1 Set-valued decision information system

$U$	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$	$d$
$x 1$	｛1｝	｛1，2｝	｛1｝	｛1，2｝	｛2｝	｛1｝
$x 2$	｛1，2｝	｛2｝	｛1，2｝	｛1｝	｛1｝	｛1｝
$x 3$	｛1｝	｛1，2｝	｛1｝	｛1，2｝	｛1｝	｛2｝
$x 4$	｛1｝	｛1｝	｛1｝	｛1｝	｛1，2｝	｛1｝
$x 5$	｛2｝	｛1｝	｛1，2｝	｛2｝	｛1｝	｛1｝
$x 6$	｛1，2｝	｛1｝	｛1，2｝	｛1｝	｛1｝	｛2｝
$x 7$	｛1｝	｛1，2｝	｛1，2｝	｛1｝	｛2｝	｛2｝
$x 8$	｛1，2｝	｛2｝	｛2｝	｛2｝	｛1，2｝	｛1｝

表2 实验数据集

Tab. 2 Experimental datasets

序号	数据集	对象数	属性数	类别数
1	Wine	178	13	3
2	Lymphography	148	18	4
3	Congressional voting rewords	435	16	2

图1 非增量式方法与增量式方法的属性约简时间比较

Fig. 1 Comparison of attribute reduction time between non-incremental method and incremental method

表3 两种方法的属性约简结果比较

Tab. 3 Comparison of attribute reduction results of two methods

数据集	HARM-KG	IARM-KG
Wine	1，2，3，4，5，6，7，9，10，11，12，13	1，2，3，4，5，6，7，9，10，11，12，13
Lymphography	1，2，3，4，7，8，9，11，12，13，14，15，17	1，2，3，4，5，6，7，8，9，12，13，14，15
Congressional voting rewords	1，2，3，4，5，6，9，10，11，12，13，14，15，16	1，2，3，4，5，6，7，9，10，11，12，13，14，15，16

表4 两种方法的分类精度比较 ( %)

Tab. 4 Comparison of classification accuracy of two methods

数据集	HARM-KG	IARM-KG
Wine	98.876 4	98.876 4
Lymphography	81.756 8	81.756 8
Congressional voting rewords	90.804 6	90.574 7

参考文献 17

1	PAWLAK Z. Rough sets［J］. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356. 10.1007/bf01001956
2	KRYSZKIEWICZ M. Rough set approach to incomplete information systems［J］. Information Sciences， 1998， 112（1/2/3/4）： 39-49. 10.1016/s0020-0255(98)10019-1
3	吴鹏，杨勇，张阿红.基于集值的Rough集扩充模型［J］.计算机工程与应用， 2008， 44（32）： 134-136. 10.3778/j.issn.1002-8331.2008.32.040
	WU P， YANG Y， ZHANG A H. Extensional model based on set-valued Rough set［J］. Computer Engineering and Applications， 2008， 44（32）： 134-136. 10.3778/j.issn.1002-8331.2008.32.040
4	乔全喜，秦克云.集值信息系统基于限制相容关系的属性约简［J］.计算机工程与应用， 2013， 49（7）： 24-27. 10.3778/j.issn.1002-8331.1209-0117
	QIAO Q X， QIN K Y. Attribute reduction of set-valued information system based on restriction tolerance relation［J］. Computer Engineering and Applications， 2013， 49（7）： 24-27. 10.3778/j.issn.1002-8331.1209-0117
5	GUAN Y Y， WANG H K. Set-valued information systems［J］. Information Sciences， 2006， 176（17）： 2507-2525. 10.1016/j.ins.2005.12.007
6	QIAN Y H， DANG C Y， LIANG J Y， et al. Set-valued ordered information systems［J］. Information Sciences， 2009， 179（16）： 2809-2832. 10.1016/j.ins.2009.04.007
7	DAI J H， TIAN H W. Entropy measures and granularity measures for set-valued information systems［J］. Information Sciences， 2013， 240： 72-82. 10.1016/j.ins.2013.03.045
8	WEI W， CUI J B， LIANG J Y， et al. Fuzzy rough approximations for set-valued data［J］. Information Sciences， 2016， 360： 181-201. 10.1016/j.ins.2016.04.005
9	马建敏，张文修.基于信息量的集值信息系统的属性约简［J］.模糊系统与数学， 2013， 27（2）： 177-182. 10.3969/j.issn.1001-7402.2013.02.028
	MA J M， ZHANG W X. Information quantity-based attribute reduction in set-valued information systems［J］. Fuzzy Systems and Mathematics， 2013， 27（2）： 177-182. 10.3969/j.issn.1001-7402.2013.02.028
10	刘莹莹，吕跃进.基于相似度的集值信息系统属性约简算法［J］.南京大学学报（自然科学版）， 2015， 51（2）： 384-389. 10.13232/j.cnki.jnju.2015.02.025
	LIU Y Y， LYU Y J. Attribute reduction in set-valued information system based on similarity［J］. Journal of Nanjing University （Natural Sciences）， 2015， 51（2）： 384-389. 10.13232/j.cnki.jnju.2015.02.025
11	ZHANG J B， LI T R， RUAN D， et al. Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems［J］. International Journal of Approximate Reasoning， 2012， 53（4）： 620-635. 10.1016/j.ijar.2012.01.001
12	邹维丽，陈红梅，胡成祥，等.集值粗糙集模型的近似集增量更新方法研究［J］.广西师范大学学报（自然科学版）， 2009， 27（3）： 93-96. 10.3969/j.issn.1001-6600.2009.03.022
	ZOU W L， CHEN H M， HU C X， et al. Approach to incremental updating approximations based on set-valued information system［J］. Journal of Guangxi Normal University （Natural Science Edition）， 2009， 27（3）： 93-96. 10.3969/j.issn.1001-6600.2009.03.022
13	王映龙，华佳佳，钱文彬，等.集值决策信息系统的动态属性约简算法［J］.计算机工程与应用， 2017， 53（17）： 60-64. 10.3778/j.issn.1002-8331.1703-0007
	WANG Y L， HUA J J， QIAN W B， et al. Dynamic algorithm of attribute reduction in set-valued decision information system［J］. Computer Engineering and Applications， 2017， 53（17）： 60-64. 10.3778/j.issn.1002-8331.1703-0007
14	王映龙，华佳佳，钱文彬，等.集值决策信息系统的增量式属性约简算法［J］.小型微型计算机系统， 2018， 39（6）： 1239-1244. 10.3969/j.issn.1000-1220.2018.06.022
	WANG Y L， HUA J J， QIAN W B， et al. Incremental attribute reduction algorithm of the set-valued decision information system［J］. Journal of Chinese Computer Systems， 2018， 39（6）： 1239-1244. 10.3969/j.issn.1000-1220.2018.06.022
15	LUO C， LI T R， CHEN H M， et al. Fast algorithms for computing rough approximations in set-valued decision systems while updating criteria values［J］. Information Sciences， 2015， 299： 221-242. 10.1016/j.ins.2014.12.029
16	王磊，李天瑞.一种基于矩阵的知识粒度计算方法［J］.模式识别与人工智能， 2013， 26（5）： 447-453. 10.3969/j.issn.1003-6059.2013.05.005
	WANG L， LI T R. A matrix-based approach for calculation of knowledge granulation［J］. Pattern Recognition and Artificial Intelligence， 2013， 26（5）： 447-453. 10.3969/j.issn.1003-6059.2013.05.005
17	JING Y G， LI T R， HUANG J F， 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. 10.1016/j.ijar.2016.05.001

[1]	康猛, 蒙祖强. 基于局部条件区分能力的高效属性约简算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 449-456.
[2]	彭莉, 张海清, 李代伟, 唐聃, 于曦, 何磊. 基于粗糙集理论的不完备数据分析方法的混合信息系统填补算法[J]. 计算机应用, 2021, 41(3): 677-685.
[3]	罗长银, 陈学斌, 马春地, 王君宇. 面向区块链的在线联邦增量学习算法[J]. 计算机应用, 2021, 41(2): 363-371.
[4]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[5]	刘丹, 姚立霜, 王云锋, 裴作飞. 面向类不平衡流量数据的分类模型[J]. 计算机应用, 2020, 40(8): 2327-2333.
[6]	王磊. 改进粗糙集属性约简结合K-means聚类的网络入侵检测方法[J]. 计算机应用, 2020, 40(7): 1996-2002.
[7]	章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 518-523.
[8]	骆克云, 叶保留, 唐斌, 梅峰, 卢文达. 基于增量学习的RocksDB键值系统主动缓存机制[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 321-327.
[9]	欧彬利, 钟夏汝, 代建华, 杨田. 基于变精度覆盖粗糙集的入侵检测方法[J]. 计算机应用, 2020, 40(12): 3465-3470.
[10]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[11]	鲍迪, 张楠, 童向荣, 岳晓冬. 区间值决策表的正域增量式属性约简算法[J]. 计算机应用, 2019, 39(8): 2288-2296.
[12]	陈曼如, 张楠, 童向荣, 东野升龙, 杨文静. 基于多尺度属性粒策略的快速正域约简算法[J]. 计算机应用, 2019, 39(12): 3426-3433.
[13]	谭永奇, 樊建聪, 任延德, 周晓明. 改进的属性约简算法及其在肝癌微血管侵犯预测中的应用[J]. 计算机应用, 2019, 39(11): 3221-3226.
[14]	李旭, 荣梓景, 阮晓曦. 关系决策系统中相对不可区分和区分关系的约简[J]. 计算机应用, 2019, 39(10): 2852-2858.
[15]	忽丽莎, 王素贞, 陈益强, 胡春雨, 蒋鑫龙, 陈振宇, 高兴宇. 基于目标均衡度量的核增量学习跌倒检测方法[J]. 计算机应用, 2018, 38(4): 928-934.

属性集变化条件下集值决策信息系统的增量属性约简方法

Incremental attribute reduction method for set-valued decision information system with variable attribute sets

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 17

相关文章 15

编辑推荐

Metrics