基于分治法的快速确定规则获取算法

摘要
图/表
参考文献
相关文章 (4)

全文: PDF (534 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要值约简是Rough集理论研究的一个重要内容，目前已有的算法很难快速处理大数据集。文中通过在属性空间上对论域对象的分解，提出一种基于分治法的快速确定规则获取算法，并给出实例说明。该算法可直接从离散的决策表获取确定决策规则，在数据服从均匀分布的条件下，算法的时间复杂度低于n²，适合大数据集的确定规则获取。实验结果说明算法的高效性。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	胡峰
	王国胤

关键词 ：粗集, 决策表, 值约简, 分治法

Abstract：Value reduction is a very important issue in rough set theory. Many efficient algorithms have been developed, however, few of them can process huge data sets quickly. In this paper, a quick algorithm for certain rule acquisition based on divide and conquer method is developed by dividing universe objects in attribute space. The proposed algorithm is illustrated by a case research as well. A certain rule set can be got quickly from a discrete decision table in this algorithm. If the data set is in uniform distribution, the time complexity of the algorithm is less than n², which is fit to process large data sets efficiently. Experiment results show its high efficiency.

Key words： Rough Set Decision Table Value Reduction Divide and Conquer Method

收稿日期: 2009-03-09

ZTFLH:

TP181

基金资助:国家自然科学基金项目(No.60573068, 60773113)、重庆市重点自然科学基金项目(No.2008BA2017)、重庆市杰出青年基金项目(No.2008BA2041)和重庆市教育委员会科学技术研究项目(No.KJ090512)资助

作者简介: 胡峰，男，1978年生，博士研究生，副教授，主要研究方向为智能信息处理.E-mail:hufeng@cqupt.edu.cn.王国胤，男，1970年生，教授，博士生导师，主要研究方向为智能信息处理.

引用本文:

胡峰，王国胤. 基于分治法的快速确定规则获取算法[J]. 模式识别与人工智能, 2010, 23(3): 349-356. HU Feng,WANG Guo-Yin. Quick Algorithm for Certain Rule Acquisition Based on Divide and Conquer Method. , 2010, 23(3): 349-356.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/ 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2010/V23/I3/349

[1] Pawlak Z. Rough Set. International Journal of Computer and Information Sciences, 1982, 11: 341-356
[2] Pawlak Z, Grzymala-Busse J, Slowinski R, et al. Rough Sets. Communications of the ACM, 1995, 38(11): 88-95
[3] Pawlak Z. Vagueness-A Rough Set View // Mycielski J, Rozenberg G, Salomaa A, eds. Structures in Logic and Computer Science:
A Selection of Essays in Honor of Andrzej Ehrenfeucht. Berlin, Germany: Springer-Verlag, 1997: 106-117
[4] Mllestad T, Skowron A. A Rough Set Framework for Data Mining of Propositional Default Rules // Proc of the 9th International Symposium on Foundation of Intelligent Systems. Zakopane, Poland, 1996: 448-457
[5] Ziarko W, Cerone N, Hu Xiaochu. Rule Discovery from Database with Decision Matrices // Proc of the 9th International Symposium on Foundation of Intelligent Systems. Zakopane, Poland, 1996: 653-662
[6] Liu Qing, Huang Zhaohua, Liu Shaohui, et al. Decision Rules with Rough Operator and Soft Computing of Data Mining. Journal of Computer Research and Development, 1999, 36(7): 800-804 (in Chinese)
(刘清,黄兆华,刘少辉,等.带Rough算子的决策规则及数据挖掘中的软计算.计算机研究与发展, 1999, 36(7): 800-804)
[7] Chang Liyun, Wang Guoyin, Wu Yu. An Approach for Attribute Reduction and Rule Generation Based on Rough Set Theory. Journal of Software, 1999, 10(11): 1206-1211 (in Chinese)
(常犁云,王国胤,吴渝.一种Rough Set理论的属性约简及规则提取方法.软件学报, 1999, 10(11): 1206-1211)
[8] Wang Guoyin, He Xiao. A Self-Learning Model under Uncertain Condition. Journal of Software, 2003, 14(6): 1096-1102 (in Chinese)
(王国胤,何晓.一种不确定性条件下的自主式知识学习模型.软件学报, 2003, 14(6): 1096-1102)
[9] Wang Jue, Yao Yiyu, Wang Feiyue. “Reduct+ Exception” Learning Based on Reduct. Chinese Journal of Computers, 2005, 28(11): 1778-1789)
(王珏,姚一豫,王飞跃.基于Reduct 的“规则+例外”学习.计算机学报, 2005, 28(11): 1778-1789)
[10] Wang Guoyin. Rough Set Theory and Knowledge Acquisition. Xian, China: Xian Jiaotong University Press, 2001 (in Chinese)
(王国胤.Rough集理论与知识获取.西安:西安交通大学出版社, 2001)
[11] Skowron A, Rauszer C. The Discernibility Functions Matrices and Functions in Information Systems // Slowinski R, ed. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht, Netherlands: Kluwer Academic Publisher, 1991: 331-362
[12] Hu Xiaohua, Cercone N. Learning in Relational Databases: A Rough Set Approach. Computational Intelligence, 1995, 11(2): 323-337
[13] Ye Dongyi, Chen Zhaojiong. A New Discernibility Matrix and The Computation of a Core. Acta Electronica Sinica, 2002, 30(7): 1086-1088 (in Chinese)
(叶东毅,陈昭炯.一个新的差别矩阵及其求核方法.电子学报, 2002, 30(7): 1086-1088)
[14] Wang Jue, Wang Ju. Reduction Algorithms Based on Discernibility Matrix: The Order Attributes Method. Journal of Computer Science and Technology, 2001, 16(6): 489-504
[15] Zhao Min. The Data Description Based on Reduct. Ph.D Dissertation. Beijing, China: Chinese Academy of Sciences. Institute of Automation, 2004 (in Chinese)
(赵岷.基于Reduct理论的数据描述.博士学位论文.北京:中国科学院自动化研究所, 2004)
[16] Han Suqing, Wang Jue. Reduct and Attribute Order. Journal of Computer Science and Technology, 2004, 19(4): 429-449
[17] Hu Feng, Wang Guoyin. Quick Reduction Algorithm Based on Attribute Order. Chinese Journal of Computers, 2007, 30(8): 1429-1435 (in Chinese)
(胡峰,王国胤.属性序下的快速约简算法.计算机学报, 2007, 30(8): 1429-1435)
[18] Yu Xiangxuan, Cui Guohua, Zou Haiming. Fundamentals of Computer Algorithms. Wuhan, China: Huazhong University of Science and Technology Press, 2005 (in Chinese)
(余祥宣,崔国华,邹海明.计算机算法基础.武汉:华中科技大学出版社, 2005)
[19] Hu Feng, Wang Guoyin. Analysis of the Complexity of Quick Sort for Two Dimension Table. Chinese Journal of Computers, 2007, 30(6): 693-698 (in Chinese)
(胡峰,王国胤.二维表快速排序的复杂度分析.计算机学报, 2007, 30(6): 693-698)