基于知识粒度的增量约简算法

doi:10.6040/j.issn.1672-3961.2.2015.033

山东大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (1): 1-9.doi: 10.6040/j.issn.1672-3961.2.2015.033

• 机器学习与数据挖掘 • 下一篇

基于知识粒度的增量约简算法

景运革^1,2,李天瑞^1*

1. 西南交通大学信息科学与技术学院, 四川成都 611756;
2.运城学院公共计算机教学部, 山西运城 044000

收稿日期:2015-05-18 出版日期:2016-02-20 发布日期:2015-05-18
通讯作者: 李天瑞(1969- ),男,福建莆田人,教授,博士生导师,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现,云计算与大数据.E-mail:trli@swjtu.edu.cn E-mail:jyg701022@163.com
作者简介:景运革(1970-),男,山西运城人,副教授,博士研究生,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现.E-mail:jyg701022@163.com
基金资助:
国家自然科学基金资助项目(61175047);国家自然科学基金委员会-中国工程物理研究院NSAF联合基金资助项目(U1230117)

An incremental approach for reduction based on knowledge granularity

JING Yunge^1,2, LI Tianrui^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

摘要/Abstract

摘要： 在现实中,许多数据库都是动态变化的,非增量约简方法处理这些数据需要花费大量的时间和空间。增量技术是处理动态数据的有效方法。首先介绍了计算知识粒度的增量机制,然后提出了基于知识粒度的增量约简算法,当一些对象增加到决策表时,能够利用原有决策表的知识粒度和约简,快速计算出增加对象后的知识粒度和约简,并通过理论分析验证了增量方法可以减少计算属性约简的时间复杂度,最后用增量方法和非增量方法对UCI数据集进行一系列试验。试验结果表明,所提增量算法在处理动态数据时能够节省大量的计算时间。

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

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

中图分类号:

TP301

景运革,李天瑞. 基于知识粒度的增量约简算法[J]. 山东大学学报(工学版), 2016, 46(1): 1-9.

JING Yunge, LI Tianrui. An incremental approach for reduction based on knowledge granularity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 1-9.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于知识粒度的增量约简算法

An incremental approach for reduction based on knowledge granularity

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

多维度评价

本文评价

推荐阅读 10

[1]	辛丽玲, 何威, 于剑, 贾彩燕. 一种基于密度差异的离群点检测算法[J]. 山东大学学报(工学版), 2015, 45(3): 7-14.
[2]	陈玉明,吴克寿,谢荣生. 基于相对知识粒度的决策表约简[J]. 山东大学学报(工学版), 2012, 42(6): 8-12.
[3]	李慧1,2,胡云1,3,李存华1. 基于粗糙集理论的瓦斯灾害信息特征提取技术[J]. 山东大学学报(工学版), 2012, 42(5): 91-95.
[4]	施珺,朱敏. 一种基于灰色系统和支持向量机的预测优化模型[J]. 山东大学学报(工学版), 2012, 42(5): 7-11.
[5]	吴克寿,陈玉明,曾志强. 基于邻域关系的决策表约简[J]. 山东大学学报(工学版), 2012, 42(2): 7-10.
[6]	李国和1,2,岳翔1,2,李雪3,吴卫江1,2,李洪奇1. 一种面向连续型属性的特征选取方法[J]. 山东大学学报(工学版), 2011, 41(6): 1-6.
[7]	翟俊海,高原原,王熙照,陈俊芬. 基于划分子集的属性约简算法[J]. 山东大学学报(工学版), 2011, 41(4): 24-28.
[8]	李成栋,雷红,史开泉 . 一种基于粗集的模糊系统设计方法[J]. 山东大学学报(工学版), 2006, 36(4): 73-80 .
[9]	管延勇,胡海清,王洪凯 . α-粗糙集模型中的不可分辨关系[J]. 山东大学学报(工学版), 2006, 36(1): 75-80 .
[10]	刘纪芹,张萍,颜建军 . 变异知识与它的过滤特征[J]. 山东大学学报(工学版), 2006, 36(1): 93-99 .