[1]冯少荣,张东站.基于改进差别矩阵的增量式属性约简算法[J].深圳大学学报理工版,2012,29(No.5(377-470)):405-411.[doi:10.3724/SP.J.1249.2012.05405]
 FENG Shao-rong and ZHANG Dong-zhan.Increment algorithm for attribute reduction based on improvement of discernibility matrix[J].Journal of Shenzhen University Science and Engineering,2012,29(No.5(377-470)):405-411.[doi:10.3724/SP.J.1249.2012.05405]
点击复制

基于改进差别矩阵的增量式属性约简算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第29卷
期数:
2012年No.5(377-470)
页码:
405-411
栏目:
电子与信息科学
出版日期:
2012-09-21

文章信息/Info

Title:
Increment algorithm for attribute reduction based on improvement of discernibility matrix
作者:
冯少荣张东站
厦门大学信息科学与技术学院,福建 厦门 361005
Author(s):
FENG Shao-rong and ZHANG Dong-zhan
School of Information Science and Technology, Xiamen University, Xiamen, Fujian 361005, P.R.China
关键词:
粗糙集理论 属性约简 差别矩阵 属性核 决策表 动态更新 增量式算法 知识约简 时间复杂性 空间复杂性
Keywords:
rough set theory attribute reduction discernibility matrix attribute core decision table dynamic updating Incremental algorithm knowledge reduction time complexity space complexity
分类号:
TP 311
DOI:
10.3724/SP.J.1249.2012.05405
文献标志码:
A
摘要:
研究目前粗糙集中求属性核和属性约简存在的效率低下问题,提出基于改进差别矩阵的核增量式更新算法,用于解决对象动态增加情况下核的更新问题.为降低现有增量式属性约简算法的时间和空间复杂度, 提出一种不存储差别矩阵的高效属性约简算法,用于处理对象动态增加情况下属性约简的更新问题.理论及实验结果表明,该算法可明显降低时间和空间的复杂度.
Abstract:
An incremental updating algorithm for computing core based on an improved discernibility matrix definition is proposed to improve the efficiency of computing attribute core and attribute reduction in rough sets. This new algorithm is mainly used to solve core updating when objects are dynamically increased.The purpose of this said algorithm is to decrease the complexity of time and space on the existing incremental attribute reduction algorithm. The discernibility matrix is not necessarry to be stored and therefore the attribute reduction is updated when objects are dynamically increased.Theoretical analysis and experimental results have shown that this new algorithm is feasible and effective.

参考文献/References:

[1] Pawlak Z.Rough sets[J].International Journal of Information and Computer Science,1982,11(5): 341-356.
[2] QIAN Yu-hua,LIANG Ji-ye,Pedrycz Witold,et al.Positive approximation: an accelerator for attribute reduction in rough set theory[J].Artificial Intelligence, 2010,174(9/10): 597-618.
[3] HE Qiang,WU Cong-xin,CHEN De-gang,et al.Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems,2011,24(5): 689-696.
[4] QIAN Yu-hua,LIANG Ji-ye,Pedrycz Witold,et al. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recognition,2011,44(8): 1658-1670.
[5] XU Wei-hua,LI Yuan,LIAO Xiu-wu.Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J].Knowledge-Based Systems,2012,27: 78-91.
[6] Wong S K M,Ziarko W.On optimal decision rules in decision tables[J].Bulletin of Polish Academy of Sciences,1985,33(11/12): 663-676.
[7] Hu X H,Cercone N.Mining knowledge rules from databases: a rough set approach[C]// Proceedings of the 12th International Conference on Data Engineering. New Orleans(USA):IEEE Press,1996:96-105.
[8] Hu X H,Nick Cercone. Learning in relational databases: a rough set approach[J].International Journal of Computational Intelligence,1995,11(2):323-338.
[9] WANG Guo-yin,YU Hong,YANG Da-chun.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766.(in Chinese)
王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.
[10] YE Dong-yi,CHEN Zhao-jiong.A new discernibility matrix and the computation of a core[J].ACTA Electronica Sinica,2002,30(7):1086-1088.(in Chinese)

叶东毅,陈昭炯.一个新的差别矩阵及其求核方法[J].电子学报,2002,30(7):1086-1088.
[11] YANG Ming.An incremental updating algorithm of the computation of a core based on the improved discernibility matrix[J].Chinese Journal of Computers,2006,29(3):407-413.(in Chinese)
杨明.一种基于改进差别矩阵的核增量式更新算法[J].计算机学报,2006,29(3):407-413.
[12] YANG Ming.An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J].Chinese Journal of Computers,2007,30(5):815-822.(in Chinese)
杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822.
[13] XU Zhang-yan,YANG Bin-ru.Quickly attribution reduction algorithm based on decision table[J].Journal of Chinese Computer Systems,2006,25(5):858-861.(in Chinese)
徐章艳,杨炳儒.一个基于决策表的快速属性约简算法[J].小型微型计算机系统,2006,25(5):858-861.
[14] GE Hao,LI Long-shu,YANG Chuan-jian.Improvement to quick attribution reduction algorithm[J].Journal of Chinese Computer Systems,2009,30(2):308-312.(in Chinese)
葛浩,李龙澍,杨传健.改进的快速属性约简算法[J].小型微型计算机系统,2009,30(2):308-312.
[15] LIU Yang,FENG Bo-qin,ZHOU Jiang-wei.Complete algorithm of increment for attribute reduction based on discernibility matrix[J].Journal of Xi′an Jiaotong University,2007,41(2):158-161.(in Chinese)
刘洋, 冯博琴, 周江卫. 基于差别矩阵的增量式属性约简完备算法[J].西安交通大学学报,2007,41(2):158-161.
[16] QIAN Jin, YE Fei-Yue, LU Ping. An incremental attribute reduction algorithm in decision table[C]// Proceedings of the Seventh International Conference on Fuzzy Systems and Knowledge Discovery (FSKD).Yantai(China):IEEE Press, 2010, 4:1848-1852.
[17] XU Yi-tian, WANG Lai-sheng, ZHANG Rui-yan. A dynamic attribute reduction algorithm based on 0-1 integer programming[J].Knowledge-Based Systems, 2011, 24(8): 1341-1347.
[18] ZHANG Jun-bo, LI Tian-rui, RUAN Da. Rough sets based incremental rule acquisition in set-valued information systems[J].Autonomous Systems: Developments and Trends, 2012, 391:135-146.

备注/Memo

备注/Memo:
Received:2010-05-04;Revised:2012-06-03;Accepted:2012-07-27
Foundation:National Natural Science Foundation of China (50604012)
Corresponding author:Associate professor FENG Shao-rong.E-mail: shaorong@xmu.edu.cn
Citation:FENG Shao-rong,ZHANG Dong-zhan.Increment algorithm for attribute reduction based on improvement of discernibility matrix[J]. Journal of Shenzhen University Science and Engineering, 2012, 29(5): 405-411.(in Chinese)
基金项目:国家自然科学基金资助项目(50604012)
作者简介:冯少荣(1964-),男(汉族),河北省南宫市人,厦门大学副教授、博士.E-mail: shaorong@xmu.edu.cn
引文:冯少荣,张东站. 基于改进差别矩阵的增量式属性约简算法[J]. 深圳大学学报理工版,2012,29(5):405-411.
更新日期/Last Update: 2012-09-26