Quick Algorithm for Certain Rule Acquisition Based on Divide and Conquer Method
HU Feng,WANG Guo-Yin
School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031 Institute of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065
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 n2, which is fit to process large data sets efficiently. Experiment results show its high efficiency.
[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] Mllestad 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)
2010, Vol. 23 
