Abstract
Recently, new supervised machine learning algorithm has been proposed which is heavily supported by the construction of an attribute-based decision graph (AbDG) structure, for representing, in a condensed way, the training set associated with a learning task. Such structure has been successfully used for the purposes of classification and imputation in both, stationary and non-stationary environments. This chapter provides a detailed presentation of the motivations and main technicalities involved in the process of constructing AbDGs, as well as stresses some of the strengths of this graph-based structure, such as robustness and low computational costs associated with both, training and memory use. Given a training set, a collection of algorithms for constructing a weighted graph (i.e., an AbDG) based on such data is presented. The chapter describes in details algorithms involved in creating the set of vertices, the set of edges and, also, assigning labels to vertices and weights to edges. Ad-hoc algorithms for using AbDGs for both, classification or imputation purposes, are also addressed.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, S., Branson, K., Belongie, S.: Hihger order learning with graphs. In: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006), pp. 17–24. ACM, New York (2006)
Aupetit, M.: Learning topology with the generative Gaussian graph and the em algorithm (2006). In: Weiss, Y., Schölkopf, B., Platt, J. (eds.) Advances in Neural Information Processing Systems 18, pp. 83–90. MIT Press, Cambridge (2006)
Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 1, 1–48 (2006)
Bertini Jr., J.R., Nicoletti, M.C.: A genetic algorithm for improving the induction of attribute-based decision graph classifiers. In: Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 4104–4110. IEEE Press, New York (2016)
Bertini Jr., J.R., Nicoletti, M.C., Zhao, L.: Attribute-based decision graphs for multiclass data classification. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC), pp. 1779–1785 (2013)
Bertini Jr., J.R., Nicoletti, M.C., Zhao, L.: Ensemble of complete p-partite graph classifiers for non-stationary environments. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC), pp. 1802–1809 (2013)
Bertini Jr., J.R., Nicoletti, M.C., Zhao, L.: Imputation of missing data supported by complete p-partite attribute-based decision graph. In: Proceedings of the International Joint Conference on Neural Networks (IJCNN), pp. 1100–1106 (2014)
Bertini Jr., J.R., Nicoletti, M.C., Zhao, L.: An embedded imputation method via attribute-based decision graphs. Expert Syst. Appl. 57, 159–177 (2016)
Bertini Jr., J.R., Nicoletti, M.C., Zhao, L.: Attribute-based decision graphs: a framework for multiclass data classification. Neural Netw. 85, 69–84 (2017)
Bertini Jr., J.R., Zhao, L., Motta, R., Lopes, A.A.: A nonparametric classification method based on k-associated graphs. Inf. Sci. 181, 5435–5456 (2011)
Bi, W., Kwok, J.: Multi-label classification on tree and dag-structured hierarchies. In: Proceedings of the 28th International Conference on Machine Learning (ICML 2011), pp. 17–24. ACM, New York (2011)
Chapelle, O., Zien, A., Schölkopf, B. (eds.): Semi-supervised Learning, 1st edn. MIT Press, Cambridge (2006)
Cheh, Z., Zhao, H.: Pattern recognition with weighted complex networks. Phys. Rev. E 78(056107), 1–6 (2008)
Chen, J., Fang, H.R., Saad, Y.: Fast approximate knn graph construction for high dimensional data via recursive lanczos bisection. J. Logic Program. 10, 1989–2012 (2009)
Cook, D., Holder, L.: Graph-based data mining. IEEE Intell. Syst. 15(2), 32–41 (2000)
Culp, M., Michailidis, G.: Graph-based semisupervised learning. IEEE Trans. Pattern Anal. Mach. Intell. 30(1), 174–179 (2008)
Eppstein, D., Paterson, M.S., Yao, F.: On nearest-neighbor graphs. Discret. Comput. Geom. 17(3), 263–282 (1997)
Fayyad, U.M., Irani, K.B.: Multi-interval discretization of continuous valued attributes for classification learning. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence, vol. 2, pp. 1022–1027. Morgan Kaufmann Publishers, San Francisco (1993)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75–174 (2010)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference and Prediction, 2nd edn. Springer, Canada (2009)
Hein, M., Audibert, J.Y., von Luxburg, U.: Discretization: an enabling technique. Data Min. Knowl. Disc. 6, 393–423 (2002)
Hein, M., Audibert, J.Y., von Luxburg, U.: Graph Laplacians and their convergence on random neighborhood graphs. J. Mach. Learn. Res. 8, 1325–1368 (2007)
Holder, L., Cook, D.: Graph-based relational learning: current and future directions. ACM SIGKDD Explor. 5(1), 90–93 (2003)
Holder, L., Cook, D., Coble, J., Mukherjee, M.: Graph-based relational learning with application to security. Fundamenta Informaticae 66, 1–19 (2005)
Jensen, D., Neville, J., Gallagher, B.: Why collective inference improves relational classification? In: Proceedings of the 10th International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD’04), pp. 593–598. ACM (2004)
Lichman, M.: UCI machine learning repository (2013). http://archive.ics.uci.edu/ml
Macskassy, S., Provost, F.: A simple relational classifier. In: Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD), Workshop on Multi-Relational Data Mining, pp. 64–76 (2003)
Malliaros, F., Vazirgiannis, M.: Clustering and community detection in directed networks: a survey. Phys. Rep. 533, 95–142 (2013)
Muggleton, S.: Inductive logic programming: issues, results and the challenge of learning language in logic. Artif. Intell. 114, 283–296 (1999)
Muggleton, S., Raedt, L.D.: Inductive logic programming: theory and methods. J. Logic Progr. 19–20, 629–679 (1994)
Newman, M.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
Quinlan, J.R.: C4.5 Programs for Machine Learning, 1st edn. Morgan Kaufmann Publishers, San Francisco (1993)
Schaeffer, S.: Graph clustering. Comput. Sci. Rev. 1, 27–34 (2007)
Specht, D.F.: Probabilistic neural networks. Neural Netw. 3, 109–118 (1990)
Vapnik, V.: The nature of statistical learning theory. Springer, Berlin (1999)
Wenga, L., Dornaikab, F., **a, Z.: Graph construction based on data self-representativeness and Laplacian smoothness. Neurocomputing 207, 476–487 (2016)
** community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv. 45(43), 1–35 (2013)
Yang, Z., Cohen, W.W., Salakhutdinov, R.: Revisiting semi-supervised learning with graph embeddings. In: Proceedings of the 33rd International Conference on Machine Learning (2016)
Yoshida, K., Motoda, H., Indurkhya, N.: Graph-based induction as a unified learning framework. J. Appl. Intell. 4, 297–328 (1994)
Zhu, X.: Semi-supervised learning literature survey. Technical report 1530, Computer-Science, University of Wisconsin-Madison (2008)
Zhu, X., Lafferty, J., Ghahramani, Z.: Semi-supervised learning: from Gaussian fields to Gaussian processes. Technical report CMU-CS-03-175, Carnegie Mellon University (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Bertini Junior, J.R., Nicoletti, M.d.C. (2018). Attribute-Based Decision Graphs and Their Roles in Machine Learning Related Tasks. In: Stańczyk, U., Zielosko, B., Jain, L. (eds) Advances in Feature Selection for Data and Pattern Recognition. Intelligent Systems Reference Library, vol 138. Springer, Cham. https://doi.org/10.1007/978-3-319-67588-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-67588-6_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67587-9
Online ISBN: 978-3-319-67588-6
eBook Packages: EngineeringEngineering (R0)