Extracting Decision Trees from Diagnostic Bayesian Networks to Guide Test Selection
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Abstract
In this paper, we present a comparison of five different approaches to extracting decision trees from diagnostic Bayesian nets, including an approach based on the dependency structure of the network itself. With this approach, attributes used in branching the decision tree are selected by a weighted information gain metric computed based upon an associated D-matrix. Using these trees, tests are recommended for setting evidence within the diagnostic Bayesian nets for use in a PHM application. We hypothesized that this approach would yield effective decision trees and test selection and greatly reduce the amount of evidence required for obtaining accurate classification with the associated Bayesian networks. The approach is compared against three alternatives to creating decision trees from probabilistic networks such as ID3 using a dataset forward sampled from the network, KL-divergence, and maximum expected utility. In addition, the effects of using χ2 statistics and probability measures for pre-pruning are examined. The results of our comparison indicate that our approach provides compact decision trees that lead to high accuracy classification with the Bayesian networks when compared to trees of similar size generated by the other methods, thus supporting our hypothesis.
How to Cite
##plugins.themes.bootstrap3.article.details##
PHM
Craven., M. W., & Shavlik, J. W. (1996). Extracting tree- structured representations of trained networks. In Advances in neural information processing systems (Vol. 8, pp. 24–30).
Frey, L., Tsamardinos, I., Aliferis, C. F., & Statnikov, A. (2003). Identifying markov blankets with decision tree induction. In In icdm 03 (pp. 59–66). IEEE Computer Society Press.
Heckerman, D., Breese, J. S., & Rommelse, K. (1995). Decision-theoretic troubleshooting. Communications of the ACM, 38, 49–57.
Heckerman, D., Geiger, D., & Chickering, D. M. (1995). Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20(3), 20–197.
Hogg, R. V., & Craig, A. T. (1978). Introduction to mathematical statistics (4th ed.). Macmillan Publishing Co.
Ide, J. S., Cozman, F. G., & Ramos, F. T. (2004). Generating random bayesian networks with constraints on induced width. In Proceedings of the 16th European conference on artificial intelligence (pp. 323–327).
Jensen, F. V., Kjærulff, U., Kristiansen, B., Lanseth, H., Skaanning, C., Vomlel, J., et al. (2001). The sacso methodology for troubleshooting complex systems. AI EDAM Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 15(4), 321–333.
Jordan, M. I. (1994). A statistical approach to decision tree modeling. In In m. warmuth (ed.), Proceedings of the seventh annual acm conference on computational learning theory (pp. 13–20). ACM Press.
Kim, Y. gyun, & Valtorta, M. (1995). On the detection of conflicts in diagnostic bayesian networks using abstraction. In Uncertainty in artificial intelligence: Proceedings of the eleventh conference (pp. 362–367). Morgan-Kaufmann.
Koller, D., & Friedman, N. (2009). Probabilistic graphical models. The MIT Press.
Liang, H., Zhang, H., & Yan, Y. (2006). Decision trees for probability estimation: An empirical study. Tools with Artificial Intelligence, IEEE International Conference on, 0, 756-764.
Martin, J. K. (1997). An exact probability metric for decision tree splitting and stopping. Machine Learning, 28, 257-291.
Mengshoel, O. J., Wilkins, D. C., & Roth, D. (2006). Controlled generation of hard and easy bayesian networks: Impact on maximal clique size in tree clustring. Artificial Intelligence, 170(16–17), 1137–1174.
Murthy, S. K. (1997). Automatic construction of decision trees from data: A multi-disciplinary survey. Data Mining and Knowledge Discovery, 2, 345– 389.
Mussi, S. (2004). Putting value of information theory into practice: A methodology for building sequential decision support systems. Expert Systems,
21(2), 92-103.
Pattipati, K. R., & Alexandridis, M. G. (1990). Application of heuristic search and information theory to sequential fault diagnosis. IEEE Transactions on Systems, Man and Cybernetics, 20(44), 872–887.
Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann.
Przytula, K. W., & Milford, R. (2005). An efficient framework for the conversion of fault trees to diagnostic bayesian network models. In Proceedings of the IEEE aerospace conference (pp. 1–14).
Quinlan, J. R. (1986). Induction of decision trees. Ma- chine Learning, 1(1), 81–106.
Shwe, M., Middleton, B., Heckerman, D., Henrion, M., Horvitz, E., Lehmann, H., et al. (1991). Probabilistic diagnosis using a reformulation of the internest-1/qmr knowledge base: 1. the probabilistic model and inference algorithms. Methods of Information in Medicine, 30(4), 241-255.
Simpson, W. R., & Sheppard, J. W. (1994). System test and diagnosis. Norwell, MA: Kluwer Academic Publishers.
Skaanning, C., Jensen, F. V., & Kjærulff, U. (2000). Printer troubleshooting using bayesian networks. In Iea/aie ’00: Proceedings of the 13th international conference on intustrial and engineering applications of artificial intelligence and expert systems (pp. 367–379).
Smile reasoning engine. (2010). University of Pittsburgh Decision Systems Laboratory. (http://genie.sis.pitt.edu/)
Vomlel, J. (2003). Two applications of bayesian networks.
Zheng, A. X., Rish, I., & Beygelzimer, A. (2005). Efficient test selection in active diagnosis via entropy approximation. In Uncertainty in artificial intelligence (pp. 675–682).
Zhou, Y., Zhang, T., & Chen, Z. (2006). Applying bayesian approach to decision tree. In Proceedings of the international conference on intelligent computing (pp. 290–295).
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
The Prognostic and Health Management Society advocates open-access to scientific data and uses a Creative Commons license for publishing and distributing any papers. A Creative Commons license does not relinquish the author’s copyright; rather it allows them to share some of their rights with any member of the public under certain conditions whilst enjoying full legal protection. By submitting an article to the International Conference of the Prognostics and Health Management Society, the authors agree to be bound by the associated terms and conditions including the following:
As the author, you retain the copyright to your Work. By submitting your Work, you are granting anybody the right to copy, distribute and transmit your Work and to adapt your Work with proper attribution under the terms of the Creative Commons Attribution 3.0 United States license. You assign rights to the Prognostics and Health Management Society to publish and disseminate your Work through electronic and print media if it is accepted for publication. A license note citing the Creative Commons Attribution 3.0 United States License as shown below needs to be placed in the footnote on the first page of the article.
First Author et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.