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

doi:10.11772/j.issn.1001-9081.2021051024

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 463-468.DOI: 10.11772/j.issn.1001-9081.2021051024

• Data science and technology • Previous Articles Next Articles

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-11 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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311

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.

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

Figures/Tables 5

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｝

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｝

Tab. 2 Experimental datasets

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

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

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

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

References 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]	Xue LI, Guangle YAO, Honghui WANG, Jun LI, Haoran ZHOU, Shaoze YE. Remote sensing image classification based on sample incremental learning [J]. Journal of Computer Applications, 2024, 44(3): 732-736.
[2]	Jianli DING, Hui HUANG, Weidong CAO. Dynamic monitoring method of flight chain operation status [J]. Journal of Computer Applications, 2024, 44(12): 3941-3948.
[3]	Yuanjiang LI, Jinsheng QUAN, Yangyi TAN, Tian YANG. Attribute reduction for high-dimensional data based on bi-view of similarity and difference [J]. Journal of Computer Applications, 2023, 43(5): 1467-1472.
[4]	Yan LI, Bin FAN, Jie GUO. Attribute reduction algorithm based on cluster granulation and divergence among clusters [J]. Journal of Computer Applications, 2022, 42(9): 2701-2712.
[5]	Jing LIU, Zhihong DONG, Zheyu ZHANG, Zhigang SUN, Haipeng JI. Data sharing method of industrial internet of things based on federal incremental learning [J]. Journal of Computer Applications, 2022, 42(4): 1235-1243.
[6]	Le WANG, Meng HAN, Xiaojuan LI, Ni ZHANG, Haodong CHENG. Ensemble classification algorithm based on dynamic weighting function [J]. Journal of Computer Applications, 2022, 42(4): 1137-1147.
[7]	Meng KANG, Zuqiang MENG. Efficient attribute reduction algorithm based on local conditional discernibility [J]. Journal of Computer Applications, 2022, 42(2): 449-456.
[8]	PENG Li, ZHANG Haiqing, LI Daiwei, TANG Dan, YU Xi, HE Lei. Imputation algorithm for hybrid information system of incomplete data analysis approach based on rough set theory [J]. Journal of Computer Applications, 2021, 41(3): 677-685.
[9]	LUO Changyin, CHEN Xuebin, MA Chundi, WANG Junyu. Online federated incremental learning algorithm for blockchain [J]. Journal of Computer Applications, 2021, 41(2): 363-371.
[10]	DENG Wenhan, ZHANG Ming, WANG Lijin, ZHONG Yiwen. Hybrid population-based incremental learning algorithm for solving closed-loop layout problem [J]. Journal of Computer Applications, 2021, 41(1): 95-102.
[11]	LIU Dan, YAO Lishuang, WANG Yunfeng, PEI Zuofei. Classification model for class imbalanced traffic data [J]. Journal of Computer Applications, 2020, 40(8): 2327-2333.
[12]	WANG Lei. Network intrusion detection method based on improved rough set attribute reduction and K-means clustering [J]. Journal of Computer Applications, 2020, 40(7): 1996-2002.
[13]	Xiajie ZHANG, Jinghua ZHU, Yang CHEN. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[14]	Keyun LUO, Baoliu YE, Bin TANG, Feng MEI, Wenda LU. Incremental learning based proactive caching mechanism for RocksDB key-value system [J]. Journal of Computer Applications, 2020, 40(2): 321-327.
[15]	OU Binli, ZHONG Xiaru, DAI Jianhua, YANG Tian. Intrusion detection method based on variable precision covering rough set [J]. Journal of Computer Applications, 2020, 40(12): 3465-3470.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 17

Related Articles 15

Recommended Articles

Metrics