JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (1): 1-9.doi: 10.6040/j.issn.1672-3961.2.2015.033

    Next Articles

An incremental approach for reduction based on knowledge granularity

JING Yunge1,2, LI Tianrui1*   

  1. 1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, Sichuan, China;
    2. Department of Public Computer Teaching, Yuncheng University, Yuncheng 044000, Shanxi, China
  • Received:2015-05-18 Online:2016-02-20 Published:2015-05-18

PDF (PC)

821

Abstract: The object set in a decision table varied dynamically nowadays. It cost a lot of time for non-incremental algorithms solving reduction of dynamical data set. Incremental technique supplied an efficient and effective soluation to such dynamic data. An incremental mechanism for updating knowledge granularity was introduced and then an incremental approach for attribute reduction based on knowledge granularity was developed. With the existing knowledge granularity and reduction, the new reduction could be obtained by the proposed method when multiple objects were added to the decision table. Theoretical analysis validated that incremental approach could reduce complexity of time for computing attribute reduction. Experiments conducted on different data sets from UCI showed that the proposed incremental algorithm could achieve better performance than the non-incremental approach.

Key words: attribute reduction, incremental method, decision table, knowledge granularity, rough set theory

CLC Number: 

  • TP301
[1] SUN Lin, XU Jiucheng, TIAN Yun. Feature selection using rough entropy-based uncertainty measures in incomplete decision systems[J].Knowledge-Based Systems, 2013(36):206-216.
[2] YAO Yiyu, ZHONG Ning. Potential applications of granular computing in knowledge discovery and data mining[C] // Proceedings of the World Multi-conference on Systemics, Cybernetics and Informatics.[S.l.] : Betascript Publishing, 1999:573-580.
[3] ROMAN W, SWINIARSKI, ANDRZEJ Skowron A. Rough set methods in feature selection and recognition[J].Pattern Recognition Letters, 2003, 24(6):833-849.
[4] ANANTHANARAYANA V S, NARASIMHA Murty M, SUBRAMANIAN D K. Tree structure for efficient data mining using rough sets[J].Pattern Recognition Letter, 2003, 24(6):851-862.
[5] SHUSAKU Tsumoto. Automated extraction of medical expert system rules from clinical databases based on RST[J]. Information Sciences,1998,112(1-4):67-84.
[6] 王磊,叶军. 知识粒度计算的矩阵方法及其在属性约简中的应用[J].计算机工程与科学, 2013,35(3):98-102. WANG Lei, YE Jun. Matrix-based approach for calculating knowledge granulation and its application in attribute reduction[J]. Computer Engineering & Science, 2013, 35(3):98-102.
[7] 翟俊海,高原原,王熙照,等. 基于划分子集的属性约简算法[J].山东大学学报(工学版),2011,41(4):25-28. ZHAI Junhai, GAO Yuanyuan, WANG Xizhao,et al. An attribute reduction algorithm based on a partition subset[J]. Journal of Shandong University(Engineering Science), 2011, 41(4):25-28.
[8] 邱桃荣,刘清,黄厚宽. 多值信息系统中基于粒计算的多级概念获取算法[J].模式识别与人工智能,2009,22(1):22-27. QIU Taorong, LIU Qing, HUANG Houkuan. Granular computing based hierarchical concept capture algorithm in multi-valued information system[J].Pattern Recognition and Artificial Intelligence, 2009, 22(1):22-27.
[9] 钟珞,梅磊,郭翠翠,等. 粒矩阵属性约简启发式算法[J].小型微型计算机系统,2011,2(3):516-520. ZHONG Lu, MEI Lei, GUO Cuicui,et al. Heuristic algorithm for attribute reduction on granular matrix[J]. Journal of Chinese Computer Systems, 2011, 2(3):516-520.
[10] ZENG Anping, LI Tianrui, LIU Dun, et al. A fuzzy rough set approach for incremental feature selection on hybrid information systems[J]. Fuzzy Sets and Systems, 2014(258):39-60.
[11] LIANG Jiye, WANG Feng, DANG Chuangyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2):1-31.
[12] QIAN Yuhua, LIANG Jiye, PEDRYCZB W. et al. Positive approximation: An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9-10):597-618.
[13] 刘洋,冯博琴,周江卫. 基于差别矩阵的增量式属性约简完备算法[J].西安交通大学学报,2007,41(2):158-161. LIU Yang, FENG Boqin, ZHOU Jiangwei. Complete algorithm of increment for attribute reduction based on discernibility matrix[J]. Journal of Xi'an Jiaotong University, 2007, 41(2):158-161.
[14] CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A rough set-based method for updating decision rules on attribute values coarsening and refining[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(12):2886-2899.
[15] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822. YANG Ming. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese Journal of Computer, 2007, 30(5):815-822.
[16] SHU Wenhao, SHEN Hong. Updating attribute reduction in incomplete decision systems with the variation of attribute set[J].International Journal of Approximate Reasoning, 2014, 55(3):867-884.
[17] LI Shaoyong, LI Tianrui, HU Jie. Update of approximations in composite information systems[J]. Knowledge-Based Systems, 2015(83):138-148.
[18] 刘清.Rough set及Rough推理[M].北京:科学出版社,2001:7-16.
[19] YAO Yiyu. Probabilistic approaches to rough sets[J]. Expert Systems, 2003, 20(5):287-297.
[20] 苗夺谦,范世栋.知识粒度的计算及其应用[J].系统工程理论与实践,2002,22(1):48-56. MIAO Duoqian, FAN Shidong. The calculation of knowledge granulation and its application[J]. Systems Engineer-Theory & Practice, 2002, 22(1):48-56.
[21] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度max(O(|C||U|,O(|C|2|U/C|))的快速约简算法[J].计算机学报,2006,29(3):391-398. XU Zhangyan, LIU Zuopeng, YANG Bingru, et al. A quickly attribute reduction algorithm with complexity of max(O(|C||U|,O(|C|2|U/C|))[J]. Chines Journal of Computer, 2006, 29(3):391-398.
[1] QIU Liqin, WANG Lei, YU Yue, SUN Yahui. Incremental attribute reduction of interval-valued decision-making information systems from the perspective of knowledge granularity [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 45-57.
[2] XIN Liling, HE Wei, YU Jian, JIA Caiyan. An outlier detection algorithm based on density difference [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 7-14.
[3] CHEN Yu-ming, WU Ke-shou, XIE Rong-sheng. Reduction for decision table based on relative knowledge granularity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(6): 8-12.
[4] LI Hui1,2, HU Yun1,3, LI Cun-hua1. The technique of gas disaster information feature extraction based on rough set theory [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(5): 91-95.
[5] WU Ke-shou, CHEN Yu-ming, ZENG Zhi-qiang. Decision table reduction based on neighborhood relation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 7-10.
[6] LI Guo-he1,2, YUE Xiang1,2, LI Xue3, WU Wei-jiang1,2, LI Hong-qi1. A method of feature selection for continuous attributes [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(6): 1-6.
[7] ZHAI Jun-hai, GAO Yuan-yuan, WANG Xi-zhao, CHEN Jun-fen. An attribute reduction algorithm based on partition subset [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 24-28.
[8] LI Chengdong,LEI Hong,SHI Kaiquan . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 73-80 .
[9] GUAN Yan-yong,HU Hai-qing,WANG Hong-kai . Indiscernible relation in α-rough sets model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 75-80 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHANG Yong-hua,WANG An-ling,LIU Fu-ping . The reflected phase angle of low frequent inhomogeneous[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 22 -25 .
[2] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[3] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[4] KONG Xiang-zhen,LIU Yan-jun,WANG Yong,ZHAO Xiu-hua . Compensation and simulation for the deadband of the pneumatic proportional valve[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 99 -102 .
[5] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[6] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[7] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[8] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[9] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[10] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd