Abstract
In this paper, we propose a novel method to adaptively select the most informative and least redundant feature subset, which has strong discriminating power with respect to the target label. Unlike most traditional methods using vectorial features, our proposed approach is based on graph-based features and thus incorporates the relationships between feature samples into the feature selection process. To efficiently encapsulate the main characteristics of the graph-based features, we probe each graph structure using the steady state random walk and compute a probability distribution of the walk visiting the vertices. Furthermore, we propose a new information theoretic criterion to measure the joint relevance of different pairwise feature combinations with respect to the target feature, through the Jensen-Shannon divergence measure between the probability distributions from the random walk on different graphs. By solving a quadratic programming problem, we use the new measure to automatically locate the subset of the most informative features, that have both low redundancy and strong discriminating power. Unlike most existing state-of-the-art feature selection methods, the proposed information theoretic feature selection method can accommodate both continuous and discrete target features. Experiments on the problem of P2P lending platforms in China demonstrate the effectiveness of the proposed method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
- 1.
See the website http://www.wdzj.com/ for more details.
References
Bai, L., Escolano, F., Hancock, E.R.: Depth-based hypergraph complexity traces from directed line graphs. Pattern Recogn. 54, 229–240 (2016)
Bai, L., Hancock, E.R.: Fast depth-based subgraph Kernels for unattributed graphs. Pattern Recogn. 50, 233–245 (2016)
Bai, L., Rossi, L., Bunke, H., Hancock, E.R.: Attributed graph Kernels using the Jensen-Tsallis q-differences. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS, vol. 8724, pp. 99–114. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44848-9_7
Bai, L., Rossi, L., Cui, L., Zhang, Z., Ren, P., Bai, X., Hancock, E.R.: Quantum Kernels for unattributed graphs using discrete-time quantum walks. Pattern Recogn. Lett. 87, 96–103 (2017)
Bai, L., Rossi, L., Torsello, A., Hancock, E.R.: A quantum Jensen-Shannon graph Kernel for unattributed graphs. Pattern Recogn. 48(2), 344–355 (2015)
Bai, L., Rossi, L., Zhang, Z., Hancock, E.R.: An aligned subtree Kernel for weighted graphs. In: Proceedings of ICML, pp. 30–39 (2015)
Bai, L., Zhang, Z., Wang, C., Bai, X., Hancock, E.R.: A graph Kernel based on the Jensen-Shannon representation alignment. In: Proceedings of IJCAI, pp. 3322–3328 (2015)
Battiti, R.: Using mutual information for selecting features in supervised neural net learning. IEEE Trans. Neural Netw. 5(4), 537–550 (1994)
Bonev, B., Escolano, F., Cazorla, M.: Feature selection, mutual information, and the classification of high-dimensional patterns. Pattern Anal. Appl. 11(3–4), 309–319 (2008)
Brown, G.: A new perspective for information theoretic feature selection. In: Proceedings of AISTATS, pp. 49–56 (2009)
Cui, L., Bai, L., Wang, Y., Bai, X., Zhang, Z., Hancock, E.R.: P2P lending analysis using the most relevant graph-based features. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016. LNCS, vol. 10029, pp. 3–14. Springer, Cham (2016). doi:10.1007/978-3-319-49055-7_1
Han, J., Sun, Z., Hao, H.: Selecting feature subset with sparsity and low redundancy for unsupervised learning. Knowl.-Based Syst. 86, 210–223 (2015)
He, X., Cai, D., Niyogi, P., Laplacian score for feature selection. In: Proceedings of NIPS, pp. 507–514 (2005)
Kwak, N., Choi, C.-H.: Input feature selection by mutual information based on Parzen window. IEEE Trans. Pattern Anal. Mach. Intell. 24(12), 1667–1671 (2002)
Liu, S., Liu, H., Latecki, L.J., Yan, S., Xu, C., Lu, H.: Size adaptive selection of most informative features. In: Proceedings of AAAI (2011)
Malekipirbazari, M., Aksakalli, V.: Risk assessment in social lending via random forests. Expert Syst. Appl. 42(10), 4621–4631 (2015)
Pavan, M., Pelillo, M.: Dominant sets and pairwise clustering. IEEE Trans. Pattern Anal. Mach. Intell. 29(1), 167–172 (2007)
Peng, H., Long, F., Ding, C.H.Q.: Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans. Pattern Anal. Mach. Intell. 27(8), 1226–1238 (2005)
Pohjalainen, J., Räsänen, O., Kadioglu, S.: Feature selection methods and their combinations in high-dimensional classification of speaker likability, intelligibility and personality traits. Comput. Speech Lang. 29(1), 145–171 (2015)
Yang, H., Moody, J.: Feature selection based on joint mutual information. In: Proceedings of AIDA, pp. 22–25 (1999)
Zhang, Z., Hancock, E.R.: Hypergraph based information-theoretic feature selection. Pattern Recogn. Lett. 33(15), 1991–1999 (2012)
Acknowledgments
This work is supported by the National Natural Science Foundation of China (Grant no. 61602535 and 61503422), the Open Projects Program of National Laboratory of Pattern Recognition, the Young Scholar Development Fund of Central University of Finance and Economics (No. QJJ1540), and the program for innovation research in Central University of Finance and Economics.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Cui, L., Jiao, Y., Bai, L., Rossi, L., Hancock, E.R. (2017). Adaptive Feature Selection Based on the Most Informative Graph-Based Features. In: Foggia, P., Liu, CL., Vento, M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2017. Lecture Notes in Computer Science(), vol 10310. Springer, Cham. https://doi.org/10.1007/978-3-319-58961-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-58961-9_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-58960-2
Online ISBN: 978-3-319-58961-9
eBook Packages: Computer ScienceComputer Science (R0)