Reducing the structure space of Bayesian classifiers using some general algorithms. (English) Zbl 1346.68154

Summary: The use of Bayesian Networks (BNs) as classifiers in different application fields has recently witnessed a noticeable growth. Yet, using the Naïve Bayes application, and even the augmented Naïve Bayes, to classifier-structure learning, has been vulnerable to some extent, which accounts for the resort of experts to other more sophisticated types of algorithms. Consequently, the use of such algorithms has paved the way for raising the problem of super-exponential increase in computational complexity of the Bayesian classifier learning structure, with the increasing number of descriptive variables. In this context, the main objective of our present work lies in trying to conceive further solutions to solve the problem of the intricate algorithmic complexity imposed during the learning of Bayesian classifiers structure through the use of sophisticated algorithms. Our results revealed that the newly suggested approach allows us to considerably reduce the execution time of the Bayesian classifier structure learning without any information loss.


68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)


Full Text: DOI


[1] Langley, P., Sage, S.: Induction of selective Bayesian classifiers In: Proceedings of the 10th conference on uncertainty in artificial intelligence, pp. 399-406 (1994)
[2] Friedman, N., Geiger, D., Goldszmid, M.: Bayesian network classifiers. Mach. Des., 131-163 (1997) · Zbl 0892.68077
[3] Pernkopf, F.: Bayesian network classifiers versus selective k-NN classifier. Pattern Recogn., 1-10 (2005) · Zbl 1101.68826
[4] Stuart, M., Yulan, H., Kecheng, L.: Choosing the best Bayesian classifier : An empirical study. IAENG Int. J. Comput. Sci., 1-10 (2009)
[5] Madden, M.G.: A new Bayesian network structure for classification tasks In: Proceedings of 13th Irish conference on artificial intelligence & cognitive science, pp. 203-208 (2002) · Zbl 1018.68746
[6] Lerner, B., Malka, R.: Investigation of the K2 algorithm in learning Bayesian network classifiers. Appl. Artif. Intell., 74-96 (2011)
[7] Witten, H.I., Eibe, F.: Data mining: Practical machine learning tools and techniques with java implementations. Morgan Kaufmann, San Mateo (1999) · Zbl 1076.68555
[8] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science, 671-681 (1983) · Zbl 1225.90162
[9] Domingos, P., Pazzani, M.: On the optimality of the simple Bayesian classifier under zero-one loss. Mach. Learn., 103-130 (1997) · Zbl 0892.68076
[10] Cooper, G.; Hersovits, E., A Bayesian method for the induction of probabilistic networks from data, Mach. Learn., 9, 309-347, (1992) · Zbl 0766.68109
[11] Spirtes, P., Glymour, C., Scheines, R.: Causation, prediction, and search, 2nd ed. The MIT Press, Cambridge (2000) · Zbl 0806.62001
[12] Judea, P., Tom, V.: A theory of inferred causation. In: Allen, J., Fikes, R., Sandewall, E. (eds.) Principles of knowledge representation and reasoning, KR’ 91, pp. 441-452 (1991) · Zbl 0765.68177
[13] Robinson, RW, Counting unlabeled acyclic digraphs, Comb. Math., 622, 28-43, (1977) · Zbl 0376.05031
[14] Tufféry, S.: Data mining et statistique décisionnelle: l’intelligence des données. Editions TECHNIP (2010) · Zbl 1270.62016
[15] Jain, AK, Data clustering: 50 years beyond K-means, Pattern Recogn. Lett., 31, 651-666, (2010)
[16] Chavent, M., Kuentz, V., Liquet, B., Saracco, J.: ClustOfVar: an R package for the clustering of variables The R user conference, p 44. University of Warwick Coventry UK (2011) · Zbl 1277.62144
[17] Chavent, M., Kuentz, V., Saracco, J.: A partitioning method for the clustering of categorical variables. In: Locarek-Junge, H., Weihs, C. (eds.) Proceedings of the IFCS in classification as a tool for research. Springer, Berlin Heidelberg New York (2009)
[18] Lerman, IC, Likelihood linkage analysis (LLA) classification method :An example treated by hand, Biochimie, 75, 379-397, (1993)
[19] Green, P., Kreiger, A.: A generalized rand-index method for consensus clustering of separate partitions of the same data base. J. Classif., 63-89 (1999)
[20] Chow, C.; Liu, C., Approximating discrete probability distributions with dependence trees, IEEE Trans. Inf. Theory, 14, 462-467, (1968) · Zbl 0165.22305
[21] Francois, O., Leray, P.: Evaluation d’algorithmes d’apprentissage de structure pour les réseaux bayésiens In: Proceedings of 14ème congrès francophone reconnaissance des formes et intelligence artificielle, pp. 1453-1460 (2004)
[22] Murphy, K.: The BayesNet toolbox for matlab In: Proceedings of Interface on computing science and statistics, p 33 (2001). http://www.ai.mit.edu/ murphyk/Software/BNT/bnt.html
[23] Sprinthall, R.C.: Basic statistical analysis, 7th ed. (2003)
[24] Ezawa, K., Singh, M., Norton, S.: Learning goal oriented Bayesian networks for telecommunications risk management In: Proceedings of the 13th international conference on machine learning, pp. 139-147 (1996)
[25] Porwal, A.; Carranza, E.; Hale, M., Bayesian network classifiers for mineral potential mapping, Comput. Geosci., 32, 1-16, (2006)
[26] Malka, R.; Lerner, B., Classification of fluorescence in situ hybridization images using belief networks, Pattern Recogn. Lett., 25, 1777-1785, (2004)
[27] Estevam, R.; Hruschka, J.; Ebecken, N., Towards efficient variables ordering for Bayesian networks classifier, Data Knowl. Eng., 63, 258-269, (2007)
[28] Carta, JA; Velázquez, S.; Matías, JM, Use of Bayesian networks classifiers for long-term mean wind turbine energy output estimation at a potential wind energy conversion site, Energy Convers. Manag., 52, 1137-1149, (2011)
[29] Kelner, R.; Lerner, B., Learning Bayesian network classifiers by risk minimization, Int. J. Approx. Reason., 53, 248-272, (2012) · Zbl 1242.68230
[30] Chickering, D., Geiger, D., Heckerman, D.: Learning bayesian net-works: Search methods and experimental results In: Proceedings of 5th conference on artificial intelligence and statistics, pp. 112-128 (1995) · Zbl 0831.68096
[31] Cheng, J.; Greiner, R.; Kelly, J.; Bell, D.; Liu, W., Learning Bayesian networks from data: An information-theory based approach, Artif. Intell., 137, 43-90, (2002) · Zbl 0995.68114
[32] Chickering, DM, Optimal structure identification with greedy search, J. Mach. Learn. Res., 3, 507-554, (2002) · Zbl 1084.68519
[33] Lauritzen, S.; Speigelhalter, D., Local computations with probabilities on graphical structures and their application to expert systems, R. Stat. Soc. B, 50, 157-224, (1988) · Zbl 0684.68106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.