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)

717

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] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] LI Chengdong,LEI Hong,SHI Kaiquan . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 73-80 .
[8] 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] CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[2] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[3] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[4] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[5] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[6] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 131 -136 .
[7] LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[8] ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .
[9] ZHAO Zhi-guang,WANG Deng-jie,TIAN Yun-fei . Roadbed settlement based on the gray theory[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 86 -88 .
[10] DIAO Yong, TIAN Si-Meng, CAO Zhe-Meng. Geological work method for the construction of the Yichang Wanzhou Railway tunnel in high risk karst areas[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 91 -95 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd