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

Abstract
Figure/Table
References
Related Citation (4)

Download: PDF (534 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

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

Received: 09 March 2009

ZTFLH:

TP181

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	HU Feng
	WANG Guo-Yin

Cite this article:

HU Feng,WANG Guo-Yin. Quick Algorithm for Certain Rule Acquisition Based on Divide and Conquer Method[J]. , 2010, 23(3): 349-356.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/ OR http://manu46.magtech.com.cn/Jweb_prai/EN/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)