Journal of Computers, Vol 7, No 7 (2012), 1769-1779, Jul 2012
doi:10.4304/jcp.7.7.1769-1779

Decision Degree-based Decision Tree Technology for Rule Extraction

Lin Sun, Jiucheng Xu, Zhan'ao Xue, Jinyu Ren

Abstract


Traditional rough set-based approaches to reduct have difficulties in constructing optimal decision tree, such as empty branches and over-fitting, selected attribute with more values, and increased expense of computational effort. It is necessary to investigate fast and effective search algorithms. In this paper, to address this issue, the limitations of current knowledge reduction for evaluating decision ability are analyzed deeply. A new uncertainty measure, called decision degree, is introduced. Then, the attribute selection standard of classical heuristic algorithm is modified, and the new improved significance measure of attribute is proposed. A heuristic algorithm for rule extraction from decision tree is designed. The advantages of this method for rule extraction are that it needn’t compute relative attribute reduction of decision tables, the computation is direct and efficient, and the time complexity is much lower than that of some existing algorithms. Finally, the experiment and comparison show that the algorithm provides more precise and simplified decision rules. So, the work of this paper will be very helpful for enlarging the application areas of rough set theory.


Keywords


granular computing; rough set; decision table; decision tree; decision degree; rule extraction

References


 

[1] A. Skowron, J. Stepaniuk, and R. Swiniarski, “Modeling Rough Granular Computing Based on Approximation Spaces”, Information Sciences, vol. 184, no.1, pp.20–43, 2012.
http://dx.doi.org/10.1016/j.ins.2011.08.001

[2] L. Sun, J. C. Xu, Z. A. Xue, and L. J. Zhang, “Rough Entropy-Based Feature Selection and Its Application”, Journal of Information and Computational Science, vol.8, no.9, pp.1525–1532, 2011.

[3] L. Sun, J. C. Xu, and S. Q. Li, “Knowledge Reduction Based on Granular Computing from Decision Information Systems”, Lecture Notes in Computer Science, vol.6401, pp.46–53, 2010.
http://dx.doi.org/10.1007/978-3-642-16248-0_12

[4] L. Sun, J. C. Xu, S. Q. Li, X. Z. Cao, and Y. P. Gao, “New Approach for Feature Selection by Using Information Entropy”. Journal of Information and Computational Science, vol.8, no.12, pp.2259–2268, 2011.

[5] L. Sun, J. C. Xu, S. Q. Li, and Y. P. Gao, “Rough Entropy Extensions for Feature Selection under Incomplete Decision Information Systems”, Advances in Information Sciences and Service Sciences, vol.3, no.11, pp.264–274, 2011.
http://dx.doi.org/10.4156/aiss.vol3.issue11.33

[6] J. C. Xu and L. Sun, “A New Knowledge Reduction Algorithm Based on Decision Power in Rough Set”, Transactions on Rough Sets, vol.XII, pp.76–89, 2010.
http://dx.doi.org/10.1007/978-3-642-14467-7_4

[7] G. Y. Wang, “Rough Reduction in Algebra View and Information View”, International Journal of Intelligent Systems, vol.18, no.6, pp.679–688, 2003.
http://dx.doi.org/10.1002/int.10109

[8] L. P. An and L. Y. Tong, “Binary Relations as A Basis for Rule Induction in Presence of Quantitative Attributes”, Journal of Computers, vol.5, no.3, pp. 440–447, 2010.

[9] L. Sun, J. C. Xu, and L. J. Zhang, “Approaches to Knowledge Reduction of Decision Systems Based on Conditional Rough Entropy”, International Journal of Advancements in Computing Technology, vol.3, no.9, pp.129–139, 2011.
http://dx.doi.org/10.4156/ijact.vol3.issue9.17

[10] R. Q. Chang, Z. Pei, and C. Zhang, “A Modified Editing K-Nearest Neighbor Rule”, Journal of Computers, vol.6, no.7, pp.1493–1500, 2011.
http://dx.doi.org/10.4304/jcp.6.7.1493-1500

[11] Y. H. Qian, J. Y. Liang, and C. Y. Dang. “Converse Approximation and Rule Extraction from Decision Tables in Rough Set Theory”, Computers and Math-ematics with Applications, vol.55, no.8, pp. 1754–1765, 2008.
http://dx.doi.org/10.1016/j.camwa.2007.08.031

[12] W. Ziarko, “Acquisition of Hierarchy-Structured Probabilistic Decision Tables and Rules from Data”, Expert Systems, vol.20, no.5, pp.305–310, 2003.
http://dx.doi.org/10.1111/1468-0394.00255

[13] J. S. Mi, Y. Leung, and W. Z. Wu, “Dependence-Space-Based Attribute Reduction in Consistent Decision Tables”, Soft Computing, vol.15, no.2, pp. 261−268, 2011.
http://dx.doi.org/10.1007/s00500-010-0656-1

[14] D. Y. Li, B. Zhang, and Y. Leung, “On Knowledge Reduction in Inconsistent Decision Information Systems”, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol.12, no.5, pp.651–672, 2004.
http://dx.doi.org/10.1142/S0218488504003132

[15] S. Greco, Z. Pawlak, and R. Slowinski, “Can Bayesian Confirmation Measures be Useful for Rough Set Decision Rules?”, Engineering Applications of Artificial Intelligence, vol.17, no.4, pp.345–361, 2004.
http://dx.doi.org/10.1016/j.engappai.2004.04.008

[16] U. Rückert, L. D. Raedt, “An Experimental Evalu-ation of Simplicity in Rule Learning”, Artificial Intelligence, vol.172, no.1, pp.19–28, 2008.
http://dx.doi.org/10.1016/j.artint.2007.06.004

[17] G. H. Chen, Y. Tang, Y. Pan, and Q. Deng, “Question Classification Using Multiple Kernel Learning and Semantic Information”, Journal of Computers, vol.6, no.11, pp.2325–2334, 2011.
http://dx.doi.org/10.4304/jcp.6.11.2325-2334

[18] S. N. Pang and N. Kasabov, “Encoding and Decoding the Knowledge of Association Rules over SVM Classification Trees”, Knowledge and Information Systems, vol.19, no.1, pp.79–105, 2009.
http://dx.doi.org/10.1007/s10115-008-0147-1

[19] S. Badr and A. Bargiela, “Case Study of Inaccuracies in The Granulation of Decision Trees”, Soft Computing, vol.15, no.6, pp.1129–1136, 2011.
http://dx.doi.org/10.1007/s00500-010-0587-x

[20] J. H. Zhai, “Fuzzy Decision Tree Based on Fuzzy-Rough Technique”, Soft Computing, vol.15, no.6, pp.1087–1096, 2011.
http://dx.doi.org/10.1007/s00500-010-0584-0

[21] L. X. Jiang and C. Q. Li, “Scaling up the Accuracy of Decision Tree Classifiers: A Naïve Bayes Combination”, Journal of Computers, vol.6, no.7, pp. 1325–1331, 2011.

[22] J. M. Wei, S. Q. Wang, M. Y. Wang, J. P. You, and D. Y. Liu, “Rough Set Based Approach for Inducing Decision Trees”, Knowledge-Based Systems, vol.20, no.8, pp.695–702, 2007.
http://dx.doi.org/10.1016/j.knosys.2006.10.001

[23] J. R. Quinlan, “C4.5: Programs for Machine Learning”, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1993.

[24] Y. S. Huang and B. C. Huang, “Recognition of Multi–Interval Rules in Dataset with Continuous–Valued Attributes”, Expert Systems with Applications, vol.36, no.2, pp.1485–1492, 2009.
http://dx.doi.org/10.1016/j.eswa.2007.11.042

[25] J. M. Wei, “Rough Set Based Approach to Selection of Node”, International Journal of Computational Cognition, vol.1, no.2, pp.25–40, 2003.

[26] Y. Liu, R. Xiong, and J. Chu, “Quick Attribute Reduction Algorithm with Hash”, Chinese Journal of Computers, vol.32, no.8, pp.1493–1499, 2009.

[27] G. Y. Wang, “Rough Set Theory and Knowledge Acquisition”, Xi'an Jiaotong University Press, China, 2001.

[28] UCI Repository of Machine Learning Databases, 1998. Available: http://ftp.ics.uci.edu/pub/machine-learning-data bases


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.