An Improvement in Branch and Bound Algorithm for Feature Selection

Ahood Naif Alharbi, Mohamed Dahab

Abstract


Branch and bound (BB) algorithm undergoes an exponential growth in feature selection as the number of features increases, which may require, in the worst cases, exploring the whole tree looking for an optimal solution. This paper presents an enhancement in the BB algorithm for feature selection using an approximate monotonic criteria function. The enhanced version of the sub-optimal BB algorithm seeking for the solution by cutting unpromising paths and deleting multiple features at each internal tree node based on a predefined tao variable. The experiment was applied to different datasets and compared to the original BB algorithm and numerous selection methods. The results show promising results in terms of accuracy, elapsed time, and tree size.

Full Text:

PDF

References


Adeli, H. (1999). Machine Learning‐Neural Networks, Genetic Algorithms, and Fuzzy Systems. Kybernetes.

Alharbi, A. N., & Dahab, M. (2018). Comparative Study on Fast Feature Selection. International Journal of Information Technology and Language Studies, 2(2).

Alwadei, M. D. S., Dahab, M., & Kamel, M. (2017). A Feature Selection Model based on High-Performance Computing (HPC) Techniques. International Journal of Computer Applications, 180(7), 11-16.

Alwadei, S., Dahab, M., & Kamel, M. (2019). High performance GA-LDA feature selection model for Brain-Computer Interface data. International Journal of Information Technology, 3(1), 1-12.

Chen, X. W. (2003). An improved branch and bound algorithm for feature selection. Pattern Recognition Letters, 24(12), 1925-1933.

Cunningham, P. (2008). Dimension reduction Machine Learning Techniques for Multimedia: Case Studies on Organization and Retrieval.

Derksen, S., & Keselman, H. J. (1992). Backward, forward, and stepwise automated subset selection algorithms: Frequency of obtaining authentic and noise variables. British Journal of Mathematical and Statistical Psychology, 45(2), 265-282.

Erich Strohmaier. Erich Strohmaier, Jack Dongarra, H. S. M. M. top 500. https://www.top500.org/site/50585. Accessed: 2019-11-4.

Friedman, N. (1997, July). Learning belief networks in the presence of missing values and hidden variables. In ICML (Vol. 97, No. July, pp. 125-133).

Fuj. (2015). Fujitsu Supports King Abdul-Aziz University Research Capabilities with New Supercomputing System. King Abdul-Aziz University. Fujitsu Limited.

Guyon, I., Gunn, S., Nikravesh, M., & Zadeh, L. A. (Eds.). (2008). Feature extraction: foundations and applications (Vol. 207). Springer.

Hubby, J. L., & Lewontin, R. C. (1966). A molecular approach to the study of genic heterozygosity in natural populations. I. The number of alleles at different loci in Drosophila pseudoobscura. Genetics, 54(2), 577.

Jain, A., & Zongker, D. (1997). Feature selection: Evaluation, application, and small sample performance. IEEE transactions on pattern analysis and machine intelligence, 19(2), 153-158.

Kamel, M. I., & Hadi, A. A. (2014). Improving P300 based speller by feature selection. Journal of Medical Imaging and Health Informatics, 4(4), 469-487.

Liao, Y., & Vemuri, V. R. (2002). Use of k-nearest neighbor classifier for intrusion detection. Computers & Security, 21(5), 439-448.

Liu, H., & Motoda, H. (Eds.). (2007). Computational methods of feature selection. CRC Press.

Malhi, A., & Gao, R. X. (2004). PCA-based feature selection scheme for machine defect classification. IEEE Transactions on Instrumentation and Measurement, 53(6), 1517-1525.

Marill, T., & Green, D. (1963). On the effectiveness of receptors in recognition systems. IEEE transactions on Information Theory, 9(1), 11-17.

McKinney, W. (2008). python data analysis library. http://pandas.sourceforge.net. Accessed: 2019-10-4.

Nakariyakul, S., & Casasent, D. P. (2007). Adaptive branch and bound algorithm for selecting optimal features. Pattern Recognition Letters, 28(12), 1415-1427.

Narendra, P. M., & Fukunaga, K. (1977). A branch and bound algorithm for feature subset selection. IEEE Transactions on Computers, (9), 917-922.

Nilsson, R. (2007). Statistical feature selection: with applications in life science (Doctoral dissertation, Institutionen för fysik, Kemi och biologi).

Pudil, P., Ferri, F. J., Novovicova, J., & Kittler, J. (1994, October). Floating search methods for feature selection with nonmonotonic criterion functions. In Proceedings of the 12th IAPR International Conference on Pattern Recognition, Vol. 3-Conference C: Signal Processing (Cat. No. 94CH3440-5) (Vol. 2, pp. 279-283). IEEE.

Schneidman, E., Berry II, M. J., Segev, R., & Bialek, W. (2006). Weak pairwise correlations imply strongly correlated network states in a neural population. Nature, 440(7087), 1007.

Sejnowski, T. Sonar dataset from UCI. https://archive.ics.uci.edu/ml/datasets/Connectionist+Bench+(Sonar,+Mines+vs.+Rocks). Accessed: 2019-11-4.

Sigillito, V. (1989). Ionosphere dataset from UCI. https://archive.ics.uci.edu/ml/datasets/Ionosphere. Accessed: 2019-10-15.

Somol, P., Pudil, P., & Kittler, J. (2004). Fast branch & bound algorithms for optimal feature selection. IEEE Transactions on pattern analysis and machine intelligence, 26(7), 900-912.

Sorzano, C. O. S., Vargas, J., & Montano, A. P. (2014). A survey of dimensionality reduction techniques. arXiv preprint arXiv:1403.2877.

Stein, J. J., & Blackman, S. S. (1975). Generalized correlation of multi-target track data. IEEE Transactions on Aerospace and Electronic Systems, (6), 1207-1217.

Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1), 267-288.

Whitney, A. W. (1971). A direct method of nonparametric measurement selection. IEEE Transactions on Computers, 100(9), 1100-1103.

William Wolberg. (1995). William Wolberg, Nick Street, O. M. (1995). Wisconsin diagnostic breast cancer (wdbc) dataset from UCI. https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic). Accessed: 2019-10-4.

Yu, B., & Yuan, B. (1993). A more efficient branch and bound algorithm for feature selection. Pattern Recognition, 26(6), 883-889.