Fast feature selection method based on mutual information in multi-label learning

doi:10.11772/j.issn.1001-9081.2019030483

Abstract

Abstract: Concerning the high time complexity of traditional heuristic search-based multi-label feature selection algorithm, an Easy and Fast Multi-Label Feature Selection (EF-MLFS) method was proposed. Firstly, Mutual Information (MI) was used to measure the features and the correlations between the labels of each dimension; then, the obtained correlations were added up and ranked; finally, feature selection was performed according to the total correlation. The proposed method was compared to six existing representative multi-label feature selection methods such as Max-Dependency and Min-Redundancy (MDMR) algorithm, Multi-Label Naive Bayes (MLNB) method. Experimental results show that the average precision, coverage, Hamming Loss and other common multi-label classification indicators are optimal after feature selection and classificationby using EF-MLFS method. In addition, global search is not required in the method, so the time complexity is significantly reduced compared with MDMR and Pairwise Mutli-label Utility (PMU).

Key words: multi-label learning, feature selection, mutual information, label correlation

摘要： 针对传统的基于启发式搜索的多标记特征选择算法时间复杂度高的问题，提出一种简单快速的多标记特征选择（EF-MLFS）方法。首先使用互信息（MI）衡量每个维度的特征与每一维标记之间的相关性，然后将所得相关性相加并排序，最后按照总的相关性大小进行特征选择。将所提方法与六种现有的比较有代表性的多标记特征选择方法作对比，如最大依赖性最小冗余性（MDMR）算法和基于朴素贝叶斯的多标记特征选择（MLNB）方法等。实验结果表明，EF-MLFS方法进行特征选择并分类的结果在平均准确率、覆盖率、海明损失等常见的多标记分类评价指标上均达最优；该方法无需进行全局搜索，因此时间复杂度相较于MDMR、对偶多标记应用（PMU）等方法也有明显降低。

关键词: 多标签学习, 特征选择, 互信息, 标记相关性

CLC Number:

TP181

XU Hongfeng, SUN Zhenqiang. Fast feature selection method based on mutual information in multi-label learning[J]. Journal of Computer Applications, 2019, 39(10): 2815-2821.

徐洪峰, 孙振强. 多标签学习中基于互信息的快速特征选择方法[J]. 计算机应用, 2019, 39(10): 2815-2821.

References

[1] 朱越, 姜远, 周志华. 一种基于多示例多标记学习的新标记学习方法[J]. 中国科学:信息科学, 2018, 48(12):1670-1680. (ZHU Y, JIANG Y, ZHOU Z H. Multi-instance multi-label new label learning[J]. Scientia Sinica (Information), 2018, 48(12):1670-1680.)
[2] SCHAPIRE R E, SINGER Y. BoosTexter:a boosting-based system for text categorization[J]. Machine Learning, 2000, 39(2/3):135-168.
[3] DIPLARIS S, TSOUMAKAS G, MITKAS P A, et al. Protein classification with multiple algorithms[C]//Proceedings of the 2005 Panhellenic Conference on Informatics, LNCS 3746. Berlin:Springer, 2005:448-456.
[4] 彭利红, 刘海燕, 任日丽, 等. 基于多标记学习预测药物-靶标相互作用[J]. 计算机工程与应用, 2017, 53(15):260-265. (PENG L H, LIU H Y, REN R L, et al. Predicting drug-target interactions with multi-label learning[J]. Computer Engineering and Applications, 2017, 53(15):260-265.)
[5] LIU G P, LI G Z, WANG Y L, et al. Modelling of inquiry diagnosis for coronary heart disease in traditional Chinese medicine by using multi-label learning[J]. BMC Complementary and Alternative Medicine, 2010, 10(1):No.37.
[6] DAI L, ZHANG J, LI C, et al. Multi-label feature selection with application to TCM state identification[J/OL]. Concurrency and Computation:Practice and Experience, 2018:No.e4634.[2019-01-10]. https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.4634.
[7] GUYON I, ELISSEEFF A. An introduction to variable and feature selection[J]. Journal of Machine Learning Research, 2003, 3:1157-1182.
[8] 宋国杰, 唐世渭, 杨冬青, 等. 基于最大熵原理的空间特征选择方法[J]. 软件学报, 2003, 14(9):1544-1550. (SONG G J, TANG S W, YANG D Q, et al. A spatial feature selection method based on maximum entropy theory[J]. Journal of Software, 2003, 14(9):1544-1550.)
[9] GUYON I, WESTON J, BARNHILL S, et al. Gene selection for cancer classification using support vector machines[J]. Machine Learning, 2002, 46(1/2/3):389-422.
[10] DY J G. BRODLEY C E. Feature selection for unsupervised learning[J]. Journal of Machine Learning Research, 2004,5:845-889.
[11] BATTITI R. Using mutual information for selecting features in supervised neural net learning[J]. IEEE Transactions on Neural Networks, 1994, 5(4):537-550.
[12] PENG H, LONG F, DING C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(8):1226-1238.
[13] LIN Y, LIU J, LIU J, et al. Multi-label feature selection based on max-dependency and min-redundancy[J]. Neurocomputing, 2015, 168:92-103.
[14] LEE J, KIM D. Feature selection for multi-label classification using multivariate mutual information[J]. Pattern Recognition Letters, 2013, 34(3):349-357.
[15] 朱颢东, 陈宁, 李红婵. 优化的互信息特征选择方法[J]. 计算机工程与应用, 2010, 46(26):122-124. (ZHU H D, CHEN N, LI H C. Optimized mutual information feature selection method[J]. Computer Engineering and Applications, 2010, 46(26):122-124.)
[16] WANG J, WEI J, YANG Z, et al. Feature selection by maximizing independent classification information[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(4):828-841.
[17] BROWN G, POCOCK A, ZHAO M, et al. Conditional likelihood maximization:a unifying framework for information theoretic feature selection[J]. Journal of Machine Learning Research, 2012, 13:27-66.
[18] 蔡亚萍, 杨明. 一种利用局部标记相关性的多标记特征选择算法[J]. 南京大学学报(自然科学版), 2016, 52(4):693-704. (CAI Y P, YANG M. A multi-label feature selection algorithm by exploiting label correlations locally[J]. Journal of Nanjing University (Natural Science Edition), 2016, 52(4):693-704.)
[19] 杨明, 蔡亚萍. 一种结合标记相关性的半监督多标记特征选择及分类方法:CN201610256462.9[P]. 2016-09-28[2019-01-10]. (YANG M, CAI Y P. A semi-supervised multi-label feature selection and classification method combined with marker correlation:CN201610256462.9[P]. 2016-09-28[2019-01-10].)
[20] BRAYTEE A, LIU W, CATCHPOOLE D R, et al. Multi-label feature selection using correlation information[C]//Proceedings of the 2017 ACM Conference on Information and Knowledge Management. New York:ACM, 2017:1649-1656.
[21] LIU L, ZHANG J, LI P, et al. A label correlation based weighting feature selection approach for multi-label data[C]//Proceedings of the 2016 International Conference on Web-Age Information Management, LNCS 9659. Cham:Springer, 2016:369-379.
[22] SPOLAÔR N, MONARD M C, TSOUMAKAS G. A systematic review of multi-label feature selection and a new method based on label construction[J]. Neurocomputing, 2016, 180:3-15.
[23] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(4):623-656.
[24] ZHANG M, ZHOU Z. ML-KNN:a lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7):2038-2048.
[25] ZHANG M, PEÑA J M, ROBLES V. Feature selection for multi-label naive Bayes classification[J]. Information Sciences, 2009, 179(19):3218-3229.
[26] ZHANG Y, ZHOU Z H. Multi-label dimensionality reduction via dependence maximization[C]//Proceedings of the 23rd National Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2008, 3:1503-1505.
[27] LIM H, LEE J, KIM D. Optimization approach for feature selection in multi-label classification[J]. Pattern Recognition Letters, 2017, 89:25-30.