2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于最大信息系数和近似马尔科夫毯的特征选择方法

孙广路 宋智超 刘金来 朱素霞 何勇军

孙广路, 宋智超, 刘金来, 朱素霞, 何勇军. 基于最大信息系数和近似马尔科夫毯的特征选择方法. 自动化学报, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
引用本文: 孙广路, 宋智超, 刘金来, 朱素霞, 何勇军. 基于最大信息系数和近似马尔科夫毯的特征选择方法. 自动化学报, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
SUN Guang-Lu, SONG Zhi-Chao, LIU Jin-Lai, ZHU Su-Xia, HE Yong-Jun. Feature Selection Method Based on Maximum Information Coefficient and Approximate Markov Blanket. ACTA AUTOMATICA SINICA, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
Citation: SUN Guang-Lu, SONG Zhi-Chao, LIU Jin-Lai, ZHU Su-Xia, HE Yong-Jun. Feature Selection Method Based on Maximum Information Coefficient and Approximate Markov Blanket. ACTA AUTOMATICA SINICA, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851

基于最大信息系数和近似马尔科夫毯的特征选择方法


DOI: 10.16383/j.aas.2017.c150851
详细信息
    作者简介:

    宋智超 哈尔滨理工大学计算机科学与技术学院硕士研究生.主要研究方向为机器学习与特征选择.E-mail:chaozhisonghlg@163.com

    刘金来 哈尔滨理工大学计算机科学与技术学院硕士研究生.主要研究方向为机器学习与信息安全.E-mail:liujinlai678@163.com

    朱素霞 哈尔滨理工大学计算机科学与技术学院副教授.主要研究方向为cache一致性协议, 并发错误检测与并行计算.E-mail:zhusuxia@hrbust.edu.cn

    何勇军 哈尔滨理工大学计算机科学与技术学院副教授.主要研究方向为机器学习与模式识别.E-mail:holywit@163.com

    通讯作者: 孙广路 哈尔滨理工大学计算机科学与技术学院教授.主要研究方向为计算机网络与信息安全, 机器学习与智能信息处理.E-mail:guanglusun@163.com
  • 基金项目:

    国家自然科学基金 61502123

    国家自然科学基金 60903083

    黑龙江省新世纪人才项目 1155-ncet-008

Feature Selection Method Based on Maximum Information Coefficient and Approximate Markov Blanket

More Information
    Author Bio:

    Master student at the School of Computer Science and Technology, Harbin University of Science and Technology. His research interest covers machine learning and feature selection

    Master student at the School of Computer Science and Technology, Harbin University of Science and Technology. His research interest covers machine learning and information security

    Associate professor at the School of Computer Science and Technology, Harbin University of Science and Technology. Her research interest covers cache coherence protocol, concurrent bug detection, and parallel computing

    Associate professor at the School of Computer Science and Technology, Harbin University of Science and Technology. His research interest covers machine learning and pattern recognition

    Corresponding author: SUN Guang-Lu Professor at the School of Computer Science and Technology, Harbin University of Science and Technology. His research interest covers computer network and information security, machine learning, and intelligent information processing. Corresponding author of this paper
  • Fund Project:

    National Natural Science Foundation of China 61502123

    National Natural Science Foundation of China 60903083

    Research Fund for the Program of New Century Excellent Talents in Heilongjiang Provincial University 1155-ncet-008

  • 摘要: 最大信息系数(Maximum information coefficient,MIC)可以对变量间的线性和非线性关系,以及非函数依赖关系进行有效度量.本文首先根据最大信息系数理论,提出了一种评价各维特征间以及每维特征与类别间相关性的度量标准,然后提出了基于新度量标准的近似马尔科夫毯特征选择方法,删除冗余特征.在此基础上提出了基于特征排序和近似马尔科夫毯的两阶段特征选择方法,分别对特征的相关性和冗余性进行分析,选择有效的特征子集.在UCI和ASU上的多个公开数据集上的对比实验表明,本文提出的方法总体优于快速相关滤波(Fast correlation-based filter,FCBF)方法,与ReliefF,FAST,Lasso和RFS方法相比也具有优势.
  • 图  1  本文提出的特征选择方法总体框架

    Fig.  1  The framework of the proposed feature selection method

    图  2  六种特征选择方法在SMK-CAN数据集上的比较

    Fig.  2  The comparison of six feature selection methods on the SMK-CAN dataset

    图  3  六种特征选择方法在TOX-171数据集上的比较

    Fig.  3  The comparison of six feature selection methods on the TOX-171 dataset

    图  4  六种特征选择方法在PIE10P数据集上的比较

    Fig.  4  The comparison of six feature selection methods on the PIE10P dataset

    图  5  六种特征选择方法在ORL10P数据集上的比较

    Fig.  5  The comparison of six feature selection methods on the ORL10P dataset

    表  1  UCI数据集

    Table  1  UCI datasets

    数据集 特征总数 样本数 类别数
    Spambase 57 4 601 2
    Arrhythmia 452 279 16
    Dermatology 34 366 6
    Colon 2 000 62 2
    下载: 导出CSV

    表  2  两种特征选择方法选择的特征数

    Table  2  The number of selected features in FCBF-MIC and FCBF

    数据集 特征总数 FBCF-MIC FCBF
    Spambase 57 7.2 16.8
    Arrhythmia 279 7.2 12.2
    Dermatology 34 18.2 12.6
    Colon 2 000 12.8 21
    下载: 导出CSV

    表  3  两种特征选择方法在UCI数据集上的实验结果(均值 $\pm$ 标准差%)

    Table  3  The comparison of two feature selection methods on UCI datasets (Mean $\pm$ Std%)

    数据集 NB 3NN SVM
    Full set NB FCBF-MIC FCBF Full set 3NN FCBF-MIC FCBF Full set SVM FCBF-MIC FCBF
    Spambase 79.93±0.30 86.93±2.15 78.60±2.34 87.55±1.47 89.43±0.51 87.8±2.05 90.11±0.62 90.15±0.98 90.24±0.88
    Arrhythmia 61.17±3.81 62.66±3.91 65.84±3.83 57.5±3.72 65.04±4.62 62.13±3.96 61.87±3.98 65.49±3.64 64.07±3.33
    Dermatology 96.06±1.00 97.16±1.27 96.27±0.91 95.08±1.51 95.63±0.84 95.52±0.64 96.61±1.27 96.83±0.40 95.85±0.74
    Colon 80.00±3.76 83.02±2.89 83.06±3.29 78.07±4.56 77.42±5.67 76.87±3.08 78.71±3.29 83.87±2.04 83.23±3.76
    Average 79.29 82.44 80.94 79.55 81.69 80.94 81.83 83.91 82.74
    下载: 导出CSV

    表  4  ASU数据集

    Table  4  ASU datasets

    数据集 特征总数 样本数 类别数
    SMK-CAN 19 993 187 2
    TOX-171 5 748 171 4
    PIE10P 2 420 210 10
    ORL10P 10 304 100 10
    下载: 导出CSV

    表  5  六种特征选择方法在NB上的比较(均值 $\pm$ 标准差%)

    Table  5  The comparison of six feature selection methods on NB classification (Mean $\pm$ Std%)

    数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
    SMK-CAN 70.66±1.56 65.19±3.53 62.21±3.49 64.9±3.74 68.12±1.88 68.67±2.36
    TOX-171 67.61±3.48 65.95 5.37 57.53±4.00 63.21±2.50 66.34±3.09 66.11±3.13
    PIE10P 92.11±2.33 87.58±3.92 92.46±3.12 93.14±3.01 84.22±1.42 84.71±3.11
    ORL10P 73.84±3.48 73.76±3.78 70.32±3.12 82.61±2.89 67.89±3.72 75.03±3.61
    Average 76.06 73.12 70.63 75.97 71.64 73.63
    下载: 导出CSV

    表  6  六种特征选择方法在3NN上的比较(均值 $\pm$ 标准差%)

    Table  6  The comparison of six feature selection methods on 3NN classification (Mean $\pm$ Std%)

    数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
    SMK-CAN 62.79±2.36 61.14±1.91 62.39±1.13 62.77±2.01 62.60±3.03 62.66±2.63
    TOX-171 69.25±2.02 69.49±2.82 60.51±3.11 64.55±3.17 67.31±3.09 69.32±3.19
    PIE10P 95.77±1.19 94.86±1.15 95.12±1.71 94.89±1.21 90.11±2.78 92.97±1.61
    ORL10P 88.88±3.06 90.16±1.78 83.76±3.49 90.34±2.65 82.22±3.95 87.94±3.07
    Average 79.17 78.91 78.14 75.45 75.56 78.22
    下载: 导出CSV

    表  7  六种特征选择方法在SVM上的比较(均值 $\pm$ 标准差%)

    Table  7  The comparison of six feature selection methods on SVM classification (Mean $\pm$ Std%)

    数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
    SMK-CAN 68.28±1.60 65.26±2.31 67.27±1.33 68.04±1.47 67.81±1.54 68.04±1.78
    TOX-171 69.26±2.13 69.44±5.35 61.76±1.19 65.16±3.33 69.30±2.12 70.12±3.31
    PIE10P 97.56±1.24 95.35±0.51 95.21±0.97 96.38 1.56 95.27±1.17 95.58±1.21
    ORL10P 82.08±5.32 76.08±2.66 75.24±2.46 81.84±3.01 78.80±5.55 82.56±4.60
    Average 79.30 76.62 74.87 77.86 77.79 79.08
    下载: 导出CSV
  • [1] Koller D, Sahami M. Toward optimal feature selection. In: Proceedings of the 13th International Conference on Machine Learning. Bari, Italy: Morgan Kaufmann, 1996. 284-292
    [2] Liu H, Motoda H. Feature Selection for Knowledge Discovery and Data Mining. Berlin: Springer Science and Business Media, 2012. 1-5
    [3] Bolón-Canedo V, Sánchez-Maroňo N, Alonso-Betanzos A. A review of feature selection methods on synthetic data. Knowledge and Information Systems, 2013, 34(3): 483-519 doi:  10.1007/s10115-012-0487-8
    [4] 崔潇潇, 王贵锦, 林行刚.基于Adaboost权值更新以及K-L距离的特征选择算法.自动化学报, 2009, 35(5): 462-468 http://www.aas.net.cn/CN/abstract/abstract13753.shtml

    Cui Xiao-Xiao, Wang Gui-Jin, Lin Xing-Gang. Feature selection based on weight updating and K-L distance. Acta Automatica Sinica, 2009, 35(5): 462-468 http://www.aas.net.cn/CN/abstract/abstract13753.shtml
    [5] Yu L, Liu H. Feature selection for high-dimensional data: a fast correlation-based filter solution. In: Proceedings of the 20th International Conferences on Machine Learning. Washington DC, USA: AAAI Press, 2003. 856-863
    [6] Lazar C, Taminau J, Meganck S, Steenhoff D, Coletta A, Molter C, de Schaetzen V, Duque R, Bersini H, Nowe A. A survey on filter techniques for feature selection in gene expression microarray analysis. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9(4): 1106-1119 doi:  10.1109/TCBB.2012.33
    [7] 刘建伟, 李双成, 罗雄麟. p范数正则化支持向量机分类算法.自动化学报, 2012, 38(1): 76-87 http://www.aas.net.cn/CN/abstract/abstract17657.shtml

    Liu Jian-Wei, Li Shuang-Cheng, Luo Xiong-Lin. Classification algorithm of support vector machine via p-norm regularization. Acta Automatica Sinica, 2012, 38(1): 76-87 http://www.aas.net.cn/CN/abstract/abstract17657.shtml
    [8] Li Z C, Liu J, Yang Y, Zhou X F, Lu H Q. Clustering-guided sparse structural learning for unsupervised feature selection. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(9): 2138-2150 doi:  10.1109/TKDE.2013.65
    [9] 刘峤, 秦志光, 陈伟, 张凤荔.基于零范数特征选择的支持向量机模型.自动化学报, 2011, 37(2): 252-256 http://www.aas.net.cn/CN/abstract/abstract17388.shtml

    Liu Qiao, Qin Zhi-Guang, Chen Wei, Zhang Feng-Li. Zero-norm penalized feature selection support vector machine. Acta Automatica Sinica, 2011, 37(2): 252-256 http://www.aas.net.cn/CN/abstract/abstract17388.shtml
    [10] Gheyas I A, Smith L S. Feature subset selection in large dimensionality domains. Pattern Recognition, 2010, 43(1): 5-13 doi:  10.1016/j.patcog.2009.06.009
    [11] Feng D C, Chen F, Xu W L. Detecting local manifold structure for unsupervised feature selection. Acta Automatica Sinica, 2014, 40(10): 2253-2261 doi:  10.1016/S1874-1029(14)60362-1
    [12] Livni R, Lehavi D, Schein S, Nachlieli H. Vanishing component analysis. In: Proceedings of the 30th International Conference on Machine Learning. Atlanta, USA: Microtome Publishing, 2013. 597-605
    [13] Liu H W, Sun J G, Liu L, Zhang H J. Feature selection with dynamic mutual information. Pattern Recognition, 2009, 42(7): 1330-1339 doi:  10.1016/j.patcog.2008.10.028
    [14] Estévez P, Tesmer M, Perez C A, Zurada J M. Normalized mutual information feature selection. IEEE Transactions on Neural Networks, 2009, 20(2): 189-201 doi:  10.1109/TNN.2008.2005601
    [15] Dash M, Liu H. Feature selection for classification. Intelligent Data Analysis, 1997, 1(1-4): 131-156 doi:  10.1016/S1088-467X(97)00008-5
    [16] Kononenko I. Estimating attributes: analysis and extensions of RELIEF. In: Proceedings of the 1994 European Conference on Machine Learning. Berlin, Germany: Springer, 1994. 171-182
    [17] Mitra P, Murthy C A, Pal S K. Unsupervised feature selection using feature similarity. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(3): 301-312 doi:  10.1109/34.990133
    [18] Yang Y M, Pedersen J O. A comparative study on feature selection in text categorization. In: Proceedings of the 14th International Conference on Machine Learning. Nashville, Tennessee, USA: Morgan Kaufmann, 1997. 412-420
    [19] Xing E P, Jordan M I, Karp R M. Feature selection for high-dimensional genomic microarray data. In: Proceedings of the 18th International Conference on Machine Learning. Williams College, Williamstown, MA, USA: Morgan Kaufmann, 2001. 601-608
    [20] Yu L, Liu H. Efficient feature selection via analysis of relevance and redundancy. The Journal of Machine Learning Research, 2004, 5: 1205-1224 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.5055
    [21] Reshef D N, Reshef Y A, Finucane H K, Grossman S R, McVean G, Turnbaugh P J, Lander E S, Mitzenmacher M, Sabeti P C. Detecting novel associations in large data sets. Science, 2011, 334(6062): 1518-1524 doi:  10.1126/science.1205438
    [22] Kira K, Rendell L A. The feature selection problem: traditional methods and a new algorithm. In: Proceedings of the 10th National Conference on Artificial Intelligence. Massachusetts, USA: AAAI Press, 1992. 129-134
    [23] Forman G. An extensive empirical study of feature selection metrics for text classification. The Journal of Machine Learning Research, 2003, 3: 1289-1305 http://www.citeulike.org/user/markymaypo/article/1915886
    [24] Fleuret F. Fast binary feature selection with conditional mutual information. The Journal of Machine Learning Research, 2004, 5: 1531-1555 https://www.researchgate.net/publication/220320537_Fast_Binary_Feature_Selection_with_Conditional_Mutual_Information
    [25] Yu L, Liu H. Redundancy based feature selection for microarray data. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2004. 737-742
    [26] Hall M A. Correlation-based feature selection for discrete and numeric class machine learning. In: Proceedings of the 17th International Conference on Machine Learning. Stanford, USA: Morgan Kaufmann, 2000. 359-366
    [27] Ding C, Peng H C. Minimum redundancy feature selection from microarray gene expression data. Journal of Bioinformatics and Computational Biology, 2005, 3(2): 185-205 doi:  10.1142/S0219720005001004
    [28] Peng H C, Long F H, Ding C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(8): 1226-1238 doi:  10.1109/TPAMI.2005.159
    [29] Seth S, Principe J C. Variable selection: a statistical dependence perspective. In: Proceedings of the 9th International Conference on Machine Learning and Applications. Washington DC, USA: IEEE, 2010. 931-936
    [30] Vergara J R, Estévez P A. A review of feature selection methods based on mutual information. Neural Computing and Applications, 2014, 24(1): 175-186 doi:  10.1007/s00521-013-1368-0
    [31] 崔自峰, 徐宝文, 张卫丰, 徐峻岭.一种近似Markov Blanket最优特征选择算法.计算机学报, 2007, 30(12): 2074-2081 doi:  10.3321/j.issn:0254-4164.2007.12.002

    Cui Zi-Feng, Xu Bao-Wen, Zhang Wei-Feng, Xu Jun-Ling. An approximate Markov blanket feature selection algorithm. Chinese Journal of Computers, 2007, 30(12): 2074-2081 doi:  10.3321/j.issn:0254-4164.2007.12.002
    [32] Saeed M. Bernoulli mixture models for Markov blanket filtering and classification. In: Proceedings of the 2008 IEEE World Congress on Computational Intelligence. Hong Kong, China: IEEE, 2008. 77-91
    [33] Zhang Y, Ding C, Li T. A two-stage gene selection algorithm by combining ReliefF and mRMR. In: Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering. Massachusetts, USA: IEEE, 2007. 164-171
    [34] Javed K, Babri H A, Saeed M. Feature selection based on class-dependent densities for high-dimensional binary data. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(3): 465-477 doi:  10.1109/TKDE.2010.263
    [35] Song Q B, Ni J J, Wang G T. A fast clustering-based feature subset selection algorithm for high-dimensional data. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 1-14 doi:  10.1109/TKDE.2011.181
    [36] Ruiz R, Riquelme J C, Aguilar-Ruiz J S. Incremental wrapper-based gene selection from microarray data for cancer classification. Pattern Recognition, 2006, 39(12): 2383-2392 doi:  10.1016/j.patcog.2005.11.001
    [37] de Souza R S, Maio U, Biffi V, Ciardi B. Robust PCA and MIC statistics of baryons in early minihaloes. Monthly Notices of the Royal Astronomical Society, 2013, 440(1): 240-248 http://adsabs.harvard.edu/abs/2014MNRAS.440..240D
    [38] Liu H M, Rao N, Yang D, Yang L, Li Y, Ou F. A novel method for identifying SNP disease association based on maximal information coefficient. Genetics and Molecular Research, 2014, 13(4): 10863-10877 doi:  10.4238/2014.December.19.7
    [39] Mani-Varnosfaderani A, Ghaemmaghami M. Assessment of the orthogonality in two-dimensional separation systems using criteria defined by the maximal information coefficient. Journal of Chromatography A, 2015, 1415: 108-114 doi:  10.1016/j.chroma.2015.08.049
    [40] 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. Chambéry, France: Springer, 1993. 1022-1027
    [41] Lichman M. UCI machine learning repository [Online], available: http://archive.ics.uci.edu/ml, November 10, 2015
    [42] Zhao Z, Morstatter F, Sharma S, Alelyani S, Anand A, Liu H. Advancing feature selection research. ASU Feature Selection Repository, 2010. 1-28
    [43] Tibshirani R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 1996, 58(1): 267-288 http://www.ams.org/mathscinet-getitem?mr=1379242
    [44] Nie F P, Huang H, Cai X, Ding C. Efficient and robust feature selection via joint l2, 1-norms minimization. In: Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems. Vancouver, British Columbia, Canada: NIPS, 2010. 1813-1821
    [45] 段洁, 胡清华, 张灵均, 钱宇华, 李德玉.基于邻域粗糙集的多标记分类特征选择算法.计算机研究与发展, 2015, 52(1): 56-65 doi:  10.7544/issn1000-1239.2015.20140544

    Duan Jie, Hu Qing-Hua, Zhang Ling-Jun, Qian Yu-Hua, Li De-Yu. Feature selection for multi-label classification based on neighborhood rough sets. Journal of Computer Research and Development, 2015, 52(1): 56-65 doi:  10.7544/issn1000-1239.2015.20140544
    [46] Hall M, Frank E, Holmes G. The WEKA data mining software: an update. ACM SIGKDD Explorations Newsletter, 2009, 11(1): 10-18 doi:  10.1145/1656274
  • [1] 孟琭, 杨旭. 目标跟踪算法综述[J]. 自动化学报, 2019, 45(7): 1244-1260. doi: 10.16383/j.aas.c180277
    [2] 徐德. 单目视觉伺服研究综述[J]. 自动化学报, 2018, 44(10): 1729-1746. doi: 10.16383/j.aas.2018.c170715
    [3] 吕菲, 夏秀渝. 基于方位特征的听觉选择性注意计算模型研究[J]. 自动化学报, 2017, 43(4): 634-644. doi: 10.16383/j.aas.2017.c160277
    [4] 陈龙, 刘全利, 王霖青, 赵珺, 王伟. 基于数据的流程工业生产过程指标预测方法综述[J]. 自动化学报, 2017, 43(6): 944-954. doi: 10.16383/j.aas.2017.c170136
    [5] 张靖, 周明全, 张雨禾, 耿国华. 基于马尔科夫随机场的散乱点云全局特征提取[J]. 自动化学报, 2016, 42(7): 1090-1099. doi: 10.16383/j.aas.2016.c150627
    [6] 周全, 王磊, 周亮, 郑宝玉. 基于多尺度上下文的图像标注算法[J]. 自动化学报, 2014, 40(12): 2944-2949. doi: 10.3724/SP.J.1004.2014.02944
    [7] 侯杰, 茅耀斌, 孙金生. 基于指数损失和0-1损失的在线Boosting算法[J]. 自动化学报, 2014, 40(4): 635-642. doi: 10.3724/SP.J.1004.2014.00635
    [8] 冯定成, 陈峰, 徐文立. 一种基于局部流形结构的无监督特征学习方法[J]. 自动化学报, 2014, 40(10): 2253-2261. doi: 10.3724/SP.J.1004.2014.02253
    [9] 桂卫华, 阳春华, 徐德刚, 卢明, 谢永芳. 基于机器视觉的矿物浮选过程监控技术研究进展[J]. 自动化学报, 2013, 39(11): 1879-1888. doi: 10.3724/SP.J.1004.2013.01879
    [10] 刘建伟, 李双成, 罗雄麟. p范数正则化支持向量机分类算法[J]. 自动化学报, 2012, 38(1): 76-87. doi: 10.3724/SP.J.1004.2012.00076
    [11] 徐丹蕾, 杜兰, 刘宏伟, 洪灵, 李彦兵. 一种基于变分相关向量机的特征选择和分类结合方法[J]. 自动化学报, 2011, 37(8): 932-943. doi: 10.3724/SP.J.1004.2011.00932
    [12] 刘峤, 秦志光, 陈伟, 张凤荔. 基于零范数特征选择的支持向量机模型[J]. 自动化学报, 2011, 37(2): 252-256. doi: 10.3724/SP.J.1004.2011.00252
    [13] 崔潇潇, 王贵锦, 林行刚. 基于Adaboost权值更新以及K-L距离的特征选择算法[J]. 自动化学报, 2009, 35(5): 462-468. doi: 10.3724/SP.J.1004.2009.00462
    [14] 杨涛, 李子青, 潘泉, 李静, 赵春晖, 程咏梅. 基于在线特征选择的实时多姿态人脸跟踪[J]. 自动化学报, 2008, 34(1): 14-20. doi: 10.3724/SP.J.1004.2008.00014
    [15] 曹媛媛, 杨波, 徐光祐. 基于分形纹理特征和小波变换的网状纹理检测方法[J]. 自动化学报, 2007, 33(7): 688-692. doi: 10.1360/aas-007-0688
    [16] 谢衍涛, 桑农, 张天序. 基于自适应隶属度函数的特征选择[J]. 自动化学报, 2006, 32(4): 496-503.
    [17] 张鸿宾, 孙广煜. Tabu搜索在特征选择中的应用[J]. 自动化学报, 1999, 25(4): 457-466.
    [18] 章新华. 一种特征选择的动态规划方法[J]. 自动化学报, 1998, 24(5): 675-680.
    [19] 徐雷. 模拟退火组合优化法在模式识别中的若干应用[J]. 自动化学报, 1989, 15(2): 114-121.
    [20] 钱学双. 类间散度特征选择法及其应用[J]. 自动化学报, 1986, 12(1): 10-17.
  • 加载中
图(5) / 表(7)
计量
  • 文章访问数:  1278
  • HTML全文浏览量:  382
  • PDF下载量:  998
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-12-16
  • 录用日期:  2016-10-09
  • 刊出日期:  2017-05-01

基于最大信息系数和近似马尔科夫毯的特征选择方法

doi: 10.16383/j.aas.2017.c150851
    基金项目:

    国家自然科学基金 61502123

    国家自然科学基金 60903083

    黑龙江省新世纪人才项目 1155-ncet-008

    作者简介:

    宋智超 哈尔滨理工大学计算机科学与技术学院硕士研究生.主要研究方向为机器学习与特征选择.E-mail:chaozhisonghlg@163.com

    刘金来 哈尔滨理工大学计算机科学与技术学院硕士研究生.主要研究方向为机器学习与信息安全.E-mail:liujinlai678@163.com

    朱素霞 哈尔滨理工大学计算机科学与技术学院副教授.主要研究方向为cache一致性协议, 并发错误检测与并行计算.E-mail:zhusuxia@hrbust.edu.cn

    何勇军 哈尔滨理工大学计算机科学与技术学院副教授.主要研究方向为机器学习与模式识别.E-mail:holywit@163.com

    通讯作者: 孙广路 哈尔滨理工大学计算机科学与技术学院教授.主要研究方向为计算机网络与信息安全, 机器学习与智能信息处理.E-mail:guanglusun@163.com

摘要: 最大信息系数(Maximum information coefficient,MIC)可以对变量间的线性和非线性关系,以及非函数依赖关系进行有效度量.本文首先根据最大信息系数理论,提出了一种评价各维特征间以及每维特征与类别间相关性的度量标准,然后提出了基于新度量标准的近似马尔科夫毯特征选择方法,删除冗余特征.在此基础上提出了基于特征排序和近似马尔科夫毯的两阶段特征选择方法,分别对特征的相关性和冗余性进行分析,选择有效的特征子集.在UCI和ASU上的多个公开数据集上的对比实验表明,本文提出的方法总体优于快速相关滤波(Fast correlation-based filter,FCBF)方法,与ReliefF,FAST,Lasso和RFS方法相比也具有优势.

English Abstract

孙广路, 宋智超, 刘金来, 朱素霞, 何勇军. 基于最大信息系数和近似马尔科夫毯的特征选择方法. 自动化学报, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
引用本文: 孙广路, 宋智超, 刘金来, 朱素霞, 何勇军. 基于最大信息系数和近似马尔科夫毯的特征选择方法. 自动化学报, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
SUN Guang-Lu, SONG Zhi-Chao, LIU Jin-Lai, ZHU Su-Xia, HE Yong-Jun. Feature Selection Method Based on Maximum Information Coefficient and Approximate Markov Blanket. ACTA AUTOMATICA SINICA, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
Citation: SUN Guang-Lu, SONG Zhi-Chao, LIU Jin-Lai, ZHU Su-Xia, HE Yong-Jun. Feature Selection Method Based on Maximum Information Coefficient and Approximate Markov Blanket. ACTA AUTOMATICA SINICA, 2017, 43(5): 795-805. doi: 10.16383/j.aas.2017.c150851
  • 在当今的大数据时代, 高维数据的分类问题是机器学习任务中的重要问题.高维数据中存在的无关特征和冗余特征, 增加了机器学习模型的时间复杂度和空间复杂度, 严重影响了模型的准确性和运行效率, 带来了所谓的“维数灾难”[1-2].特征选择是降低特征维数、应对维数灾难的有效方法.它通过挖掘特征间以及特征与类别间的内在联系, 保留最有利于分类的有效特征, 去除与类别无关特征和冗余特征, 达到降低算法的时间和空间复杂度、提高机器学习模型的准确率的目的[3-4].

    国内外的学者提出了多种有效的特征选择方法.根据与机器学习模型的结合程度, 这些方法主要分为过滤模型(Filter模型)、封装模型(Wrapper模型)和嵌入模型(Embedded模型)[5].过滤模型独立于特定的机器学习模型, 常用的子集选取策略有特征排序和特征空间搜索[6].封装模型使用机器学习模型的性能来判断特征子集的好坏.嵌入模型将特征选择与机器学习模型的训练过程相结合, 使用类似于过滤模型的评价函数选出多个特征子集, 通过机器学习算法的性能选出最优特征子集[7-9].此外, 主成分分析(Principle component analysis, PCA)和线性判别分析(Linear discriminant analysis, LDA)等特征变换方法也可以看作一类特殊的特征选择方法[10-12].

    多种度量标准被用来衡量特征间以及特征与类别间的相关性.特征与类别间的相关性越强, 特征对类别的区分性就越强; 特征与特征间的相关性越强, 特征间的可替代性就越强, 即冗余性越强.度量标准的选取对于特征相关性和冗余性的衡量非常重要.大量研究工作通过改进度量标准提高特征选择性能[13-14], 提出了基于距离的度量标准、基于信息论的度量标准、基于依赖性的度量标准和基于一致性的度量标准等[15].其中, Pearson系数[16]、最小二乘回归误差和最大信息压缩指数[17]等度量标准被广泛用于度量特征间的线性关系, 但难以刻画特征间大量存在的非线性关系[5].信息论中的信息增益[18]、互信息[19]、对称不确定性[20]等度量标准虽然能够同时对特征间线性和非线性关系进行度量, 但是无法有效度量特征间非函数依赖关系. Reshef等在2011年提出了一种新的基于信息论的度量标准---最大信息系数[21].最大信息系数能够广泛地度量变量间依赖关系, 例如线性和非线性关系, 甚至对于不能使用单个函数表示的非函数依赖关系(例如多个函数叠加组成的依赖关系)也十分有效.

    根据相应的度量标准, 学者们提出了多种评价函数, 进而构造出不同的特征选择过滤模型.在确定评价函数后, 过滤模型一般要使用相应的搜索策略对特征子集进行选取.最优搜索、贪心序列搜索和基因算法等具有较好的效果, 但它们的时间复杂度也为O $(n^2)$ , 难以适应高维数据的降维要求[20].文献[20]将相关性和冗余性解耦, 显式地处理冗余特征, 避免使用搜索策略进行特征子集的选取, 并提出一种基于近似马尔科夫毯的启发式方法, 可以有效地处理高维数据.

    本文在提出基于最大信息系数的度量标准的基础上, 应用基于特征排序和近似马尔科夫毯的两阶段特征选择方法, 兼顾特征与类别间的相关性和特征间的冗余性, 并能够较为高效地处理高维数据集.在UCI和ASU上的多个公开数据集进行实验, 结果表明本文提出的特征选择方法具有很好的性能和效果.

    • 特征选择方法需要选择度量标准对特征与类别间的相关性以及特征间的冗余性进行度量, 也需要相应的搜索策略, 得到最后的特征子集.

      早期的特征选择方法只考虑选出与类别更加相关特征, 而未考虑特征间的冗余性[16, 22-23].最具代表性的是Relief[22]和ReliefF[16], 两者都应用基于距离的度量标准, 通过从数据中随机选取实例, 然后计算Manhattan距离找到与其最邻近的 $k$ 个正负样本, 对每个属性的相关性得分进行更新. ReliefF对Relief进行了扩展, 能够处理不完备和有噪音的数据并且健壮性更强, 但是仍然无法处理冗余特征.

      与无关特征类似, 冗余特征也会影响机器学习模型的速度和准确率, 因此也应该被删除[24-25].基于相关性的特征选择方法(Correlation-based feature selection, CFS)、最小冗余最大相关特征选择方法(Minimum redundancy maximum relevance, mRMR)和基于马尔科夫毯的特征选择方法是兼顾特征相关性和冗余性的三种经典方法. CFS方法是一种基于相关性的启发式算法, 应用了Pearson系数和信息论中的对称不确定性(Symmetric uncertainty, SU)度量, 并通过选择与类别相关性最高, 且特征间不相关的特征子集作为特征选择结果[26]. mRMR也是一种启发式的特征选择方法, 使用互信息和 $F$ 统计量分别对离散变量和连续变量的最大相关和最小冗余进行定义[27].文献[28]对mRMR方法进行扩展, 提出了一种增量搜索算法, 使用互信息对特征相关性进行度量, 使用Parzen窗对连续特征进行处理, 取得了更好的特征选择效果; 还分别使用过滤模型和封装模型分两阶段选出最优特征子集.文献[14]和文献[29]对mRMR方法进行了修改, 分别使用归一化互信息和多种单调性依赖度量, 代替互信息进行特征选择.

      马尔科夫毯在特征选择中也得到了广泛的应用, 其通过选取一个对类别信息最大保留的最小特征子集, 并使得剩余特征子集以已选特征子集为条件独立于类别, 达到选取最优特征子集的目的.马尔科夫毯属于条件独立性中的强条件, 然而这种条件独立关系的发现是一个NP-hard问题, 往往需要进行近似, 很多特征选择方法使用了近似马尔科夫毯的思想来选取最优特征子集[30-31].文献[1]提出马尔科夫毯过滤方法, 使用Pearson系数来计算特征间的相关性, 并且选择与某特征相关性最高的 $k$ 个特征, 使用交叉熵对马尔科夫毯进行近似, 删除无关和冗余特征.文献[32]中提出BMM-MBF方法对文献[1]的方法进行改进, 使用伯努利混合模型估计二元数据的交叉熵.

      在对特征间的相关性和冗余性分别考虑和衡量的基础上, 一些研究采用了两阶段的特征选择方法以提高特征子集选择的效率[33-34].其中, 文献[20]应用基于对称不确定性的度量标准, 提出了一种与以往研究不同的特征选择框架---FCBF方法.该方法将特征分为四类:无关特征、弱相关且冗余的特征、弱相关非冗余的特征和强相关特征, 认为最优的特征子集应该包含后两类特征, 并提出通过近似马尔科夫毯方法删除冗余特征来寻找最优子集.在大量实验比较中, FCBF被证明具有较低的时间复杂度和较好的特征选择结果[35-36].

      学者们应用最大信息系数理论, 在多个应用领域中研究了变量间关系, 并对最大信息系数的有效性进行了验证.文献[37]使用最大信息系数对红移和光晕间的关系进行挖掘, 实验表明最大信息系数优于Spearman相关系数.文献[38]使用最大信息系数对单核苷酸多态性和疾病的相关性进行度量, 并提出了基于最大信息系数的搜索算法, 取得了很好的效果.文献[39]将最大信息系数应用到二维分离系统中的正交化评价, 使用最大信息系数代替可决系数( $R^2$ ), 并通过实验证明了最大信息系数具有很好的稳定性和变量间关系度量能力.

    • 本文提出了基于最大信息系数的新度量标准, 并结合基于对称不确定性的度量标准, 建立基于特征排序和近似马尔科夫毯的两阶段特征选择方法, 方法的总体框图如图 1所示.

      图  1  本文提出的特征选择方法总体框架

      Figure 1.  The framework of the proposed feature selection method

      第一阶段是相关性分析阶段.基于特征与类别间的相关性进行特征选择.利用对称不确定性来度量特征与类别间的相关性, 应用特征排序方法删除与类别无关或者弱相关的特征, 得到的特征子集作为第二阶段的输入.第一阶段方法具有较低的时间复杂度, 能够降低第二阶段的计算量, 并且对不均衡数据集的处理也有较为理想的效果, 但是无法删除冗余特征.

      第二阶段是冗余性分析阶段.综合考虑特征与类别间的相关性, 以及特征间的冗余性进行特征选择.应用近似马尔科夫毯方法融合基于最大信息系数的度量标准来删除冗余特征, 最终选出兼顾特征高相关性和低冗余性的特征子集.

    • Reshef等提出了最大信息系数理论和求解方法, 最大信息系数不仅可以对大量数据中变量间的线性和非线性关系进行度量, 而且可以广泛地挖掘出变量间的非函数依赖关系[21].

      最大信息系数主要利用互信息和网格划分方法进行计算.互信息是衡量变量之间相关程度的指标, 给定变量 $A= \{a_i, i=1, 2, \cdots, n\}$ 和 $B=\{b_i, i=$ $1$ , $2, \cdots, n\}$ , $n$ 为样本数量, 其互信息定义为

      $$ MI(A,B) = \sum\limits_{a \in A} {\sum\limits_{b \in B} {p(a,b)\log \frac{{p(a,b)}}{{p(a)p(b)}}} } $$ (1)

      其中, $p(a, b)$ 为 $A$ 和 $B$ 的联合概率密度, $p(a)$ 和 $p(b)$ 分别为 $A$ 和 $B$ 的边缘概率密度, 使用直方图估计对上述的概率密度进行估计.假设 $D=\{(a_i, b_i)$ , $i$ $=1, 2, \cdots, n\}$ 为一个有限的有序对的集合, 定义划分 $G$ 将变量 $A$ 的值域分成 $x$ 段, 将 $B$ 的值域分成 $y$ 段, $G$ 即为 $x\times y$ 的网格.在得到的每一种网格划分内部计算互信息 $MI(A, B)$ , 相同 $x\times y$ 的网格划分方式有多种, 取不同划分方式中的 $MI(A, B)$ 最大值作为划分 $G$ 的互信息值.定义划分 $G$ 下 $D$ 的最大互信息公式为

      $$ \begin{equation} MI^*(D, x, y)=\max{MI(D|G)} \end{equation} $$ (2)

      其中, $D|G$ 表示数据 $D$ 在使用 $G$ 进行划分.虽然最大信息系数利用互信息来表示网格的好坏, 但是其不是简单地估计互信息.将不同划分下得到的最大归一化 $MI$ 值组成特征矩阵, 特征矩阵定义为 $M(D)_{x, y}$ , 计算公式为

      $$ \begin{equation} M(D)_{x, y}=\frac{MI^*(D, x, y)}{\log \min {\{x, y\}}} \end{equation} $$ (3)

      则最大信息系数定义为

      $$ \begin{equation} MIC(D)=\max\limits_{xy<B(n)}{\{M(D)_{x, y}\}} \end{equation} $$ (4)

      其中, $B(n)$ 为网格划分 $x\times y$ 的上限值, 一般地, $\omega(1)$ $\leq$ $B(n)\leq {\rm O}(n^{1-\varepsilon})$ , $0<\varepsilon<1$ .文献[21]中给出当 $B(n)=n^{0.6}$ 时效果最好, 因此实验中也采用该值.

      本文使用最大信息系数来定义特征与类别、特征与特征间的相关性.给定一个 $n$ 条样本的特征集 $F$ $=\{f_1, f_2, \cdots, f_m, c\}$ , 其特征数为 $m$ , 类别为 $c$ .

      对任意特征 $f_i$ 与类别 $c$ 间的相关性定义为 $MIC(f_i, c)$ , 取值范围在[0, 1]. $MIC(f_i, c)$ 值越大表明 $f_i$ 与 $c$ 间的相关性越强, 则 $f_i$ 为强相关特征, 越倾向被保留; $MIC(f_i, c)$ 值越小表明 $f_i$ 与 $c$ 间的相关性越弱, 则 $f_i$ 为弱相关特征, 越倾向被删除; 当 $MIC(f_i, c)$ 值为0时, $f_i$ 为无关特征, 应该被删除.

      对任意特征 $f_i$ 和 $f_j$ 之间的冗余性(也是一种相关性)定义为 $MIC(f_i, f_j)$ . $MIC(f_i, f_j)$ 值越大, 说明 $f_i$ 和 $f_j$ 间的可替代性越强, 即冗余性越强. $MIC(f_i, f_j)$ 值为0, 说明 $f_i$ 和 $f_j$ 间相互独立.

    • 冗余特征往往使用特征间的相关性进行定义, 如果两维特征完全相关, 则认为它们是冗余的.本节首先使用文献[1]中提出的马尔科夫毯思想, 对冗余特征进行形式化定义, 然后提出基于近似马尔科夫毯的特征选择方法, 对冗余特征进行删除.

      定义1(马尔科夫毯).对特征集 $F$ 和类别 $c$ , 特征子集 $M_i\subset F$ $(f_i\notin M_i)$ 为 $f_i$ 的马尔科夫毯的条件是: $f_i\perp \{F-M_i-\{f_i\}, c\}|M_i$ .

      上述定义中 $\perp $ 表示独立, $|M_i$ 表示以 $M_i$ 为条件.定义中马尔科夫毯的条件表示:给定特征集 $M_i$ , $f_i$ 独立于特征集 $F-M_i-\{f_i\}$ 和类别 $c$ .

      给定变量 $C$ , 变量 $A$ 和 $B$ 条件独立, 该条件独立表示为 $P(A|B, C)=P (A|C)$ .当变量 $C$ 存在时, 并不会因为变量 $B$ 存在而得到变量 $A$ 的更多额外信息.因此, 如果 $M_i$ 为 $f_i$ 的马尔科夫毯, 则 $M_i$ 中包含了 $f_i$ 对类别 $c$ 和其他特征 $F-M_i-\{f_i\}$ 的所有相关信息, 即当特征子集 $M_i$ 存在时, 特征 $f_i$ 对于分类没有贡献, 应该被删除.由此, 本文中冗余特征定义为:

      定义2(冗余特征).对特征集 $F$ 和类别 $c$ , $F$ 中特征 $f_i$ 为冗余特征, 当且仅当存在 $M_i\subset F$ $(f_i$ $\notin$ $M_i)$ 为 $f_i$ 的马尔科夫毯.

      按照冗余特征定义, 如果某一特征为冗余特征, 则存在特征集使得定义1中的条件独立关系成立.但是这种完全条件独立关系的发现为NP-hard问题, 因此需要对上述马尔科夫毯条件进行近似, 本文基于最大信息系数的度量标准对马尔科夫毯进行近似, 并提出基于近似马尔科夫毯的特征选择方法, 对冗余特征进行删除.

      根据第3.1节中对于特征(类别)间的相关性和冗余性的定义, 本文提出的近似马尔科夫毯方法的相关定义如下:

      定义3(近似马尔科夫毯).对于两个特征 $f_i$ 和 $f_j$ ( $ i\neq j$ ), $f_i$ 是 $f_j$ 的近似马尔科夫毯的条件为: $MIC (f_i, c)>MIC(f_j, c)$ 并且 $MIC (f_j, c) <MIC(f_i, f_j)$ .

      定义4(主元素).一个特征 $f_i$ 为主元素, 当且仅当没有元素是 $f_i$ 的近似马尔科夫毯.

      本文中定义的近似马尔科夫毯特征选择方法对冗余特征查找和删除过程为:

      步骤1.选取主元素, 将其放入最优特征子集;

      步骤2.按照近似马尔科夫毯定义删除以当前主元素为近似马尔科夫毯的所有冗余特征;

      步骤3.重复上述过程直到 $F$ 中没有主元素.

      由所有主元素组成的特征子集为最优特征子集, 该子集中特征与类别间相关性高, 并且特征之间冗余性低.根据近似马尔科夫毯和主元素的定义, 主元素不会有近似马尔科夫毯, 因此可以确保主元素不会被删除, 并且不与最优特征子集中的特征冗余; 与之相反, 被删除的元素必定能够从最优特征子集中找到其近似马尔科夫毯.

    • FCBF是一种将特征相关性分析和冗余性分析相分离的两阶段特征选择框架.第一阶段采用特征排序方法对无关或弱相关特征进行删除, 这种方法的时间复杂度低, 但是无法删除冗余特征; 经过第一阶段处理得到较小的子集后, 在第二阶段对冗余特征进行删除, 在进行特征子集选取时, FCBF使用的近似马尔科夫毯方法相比于前述的搜索策略速度更快, 同时能够保证选出特征的有效性.

      基于FCBF的特征选择框架, 本文应用对称不确定性和最大信息系数两种度量标准, 提出基于特征排序和近似马尔科夫毯的两阶段特征选择方法, 称为FCBF-MIC.

      1) 第一阶段:相关性分析.对每一个特征 $f_i$ , 计算其对称不确定性, 计算公式为

      $$ \begin{equation} SU(f_i, c)=2\left[\frac {IG(c|f_i)}{H(c)+H(f_i)}\right] \end{equation} $$ (5)

      其中, $IG(c|f_i)$ 表示类别 $c$ 与特征 $f_i$ 之间的信息增益, $H(c)$ 和 $H(f_i)$ 分别表示类别 $c$ 与特征 $f_i$ 的信息熵[18].给定一个阈值 $\gamma$ , 如 $SU(f_i, c)\geq \gamma$ , 则 $f_i$ 对于类别 $c$ 来说是强相关特征, 应该被保留, 反之 $f_i$ 应该被删除.第一阶段方法能够删除大量的不相关特征, 减少第二阶段特征选择方法的处理规模.

      2) 第二阶段:冗余性分析.首先, 计算特征与类别的相关性 $MIC(f_i, c)$ , 相关性得分越高的特征越重要, 并按照相关性的得分对特征降序排序; 然后度量特征间的冗余性, 并应用近似马尔科夫毯方法删除冗余特征, 最终得到最优特征子集.

      FCBF-MIC特征选择方法的实现过程如算法1所示.

      算法1. FCBF-MIC算法

      输入. $F(f_1, f_2, \cdots, f_m, c)$ , $SU$ 阈值 $\gamma $

      输出. $F_{\rm opt}$ 为最优特征子集

      第一阶段:无关或者弱相关特征删除

      1. for each $f_i \in F$

      2.  计算特征和类别之间的对称不确定性 $SU (f_i, c)$

      3.   if $SU (f_i, c)>\gamma $

      4.  将特征 $f_i$ 添加到特征子集 $F'$ 中

      5. end for

      第二阶段:冗余特征删除

      6. for each $f_i \in F'$

      7.  计算特征和类别之间的最大信息系数 $MIC (f_i, c) $

      8. end for

      9.对 $F'$ 中特征按照 $MIC (f_i, c)$ 降序排序, 结果赋给 $F_{\rm order}$

      10. while $F_{\rm order} \neq \varnothing $

      11. 找 $F_{\rm order}$ 中的主元素 $f_i$ , 并添加到 $F_{\rm opt}$ 中

      12. 将 $f_i$ 从 $F_{\rm order}$ 中删除

      13. 查找以 $f_i $ 为马尔科夫毯的特征子集 ${\{f_j\}}$

      14. 将冗余特征子集 ${\{f_j\}}$ 从 $F_{\rm order}$ 中删除

      15. end while

      步骤1~5为使用对称不确定性特征排序方法删除与类别无关或者弱相关特征的处理过程, 对于连续的数值使用MDL算法进行离散化[40], 最终得到一个与类别相关性较强的特征子集 $F'$ . $F'$ 中包含大量的冗余特征, 将在第二阶段进行删除.步骤6~9计算特征与类别间的相关性 $MIC(f_i, c)$ , 然后按照 $MIC (f_i, c)$ 值对特征进行降序排序, 并将得到的结果赋给 $F_{\rm order}$ .步骤10~15为本文提出的近似马尔科夫毯方法, 从 $F_{\rm order}$ 中选出 $MIC (f_i, c)$ 最高的元素 $f_i$ 作为主元素, 从 $F_{\rm order}$ 中删除该特征并添加到 $F_{\rm opt}$ 中, 然后从 $F_{\rm order}$ 中查找以特征 $f_i$ 为近似马尔科夫毯的特征子集, 将以特征 $f_i$ 为近似马尔科夫毯的特征子集 ${\{f_j\}}$ 从 $F_{\rm order}$ 中删除.重复上述过程直到 $F_{\rm order}$ 为空集.

      在最好情况下, 近似马尔科夫毯方法中当前所有特征均以一个主元素为近似马尔科夫毯, 时间复杂度为O $(n)$ .在最坏情况下, 所有的元素均为主元素, 时间复杂度为O $(n^2)$ .在FCBF-MIC方法中, 第一阶段往往能够删除大量的特征, 会减小第二阶段的特征计算规模, 提升方法整体速度.因此, FCBF-MIC具有较快的运行效率.

    • 本文使用UCI机器学习数据库[41]和ASU特征选择数据库[42]中多个公开数据集进行实验, 这些数据集也是很多特征选择工作中广泛使用的实验数据.除了与FCBF方法比较, 本文还与ReliefF[16]和FAST[35]两种不同类型的过滤方法以及嵌入特征选择方法Lasso[43]和RFS (Robust feature selection)[44]进行对比. FAST方法也是一种两阶段特征选择方法, 其第一阶段使用对称不确定性, 第二阶段使用聚类方法, 并且使用马尔科夫毯来定义冗余特征. Lasso是基于稀疏的特征选择方法, 将特征选择和基本的线性分类器的训练过程相结合, 通过对正则化项添加 $\ell_{1}$ 范数限制达到稀疏降维的目的. RFS与Lasso类似, 其通过同时对损失函数和正则化项应用 $\ell_{2, 1}$ 范数来提高特征选择的效率和健壮性.

      特征选择方法通常使用分类器的准确率来评价选取的特征子集的好坏[44-45].因此, 本文在实验中分别对使用FCBF-MIC, FCBF, ReliefF, FAST, Lasso和RFS六种特征选择方法选出的特征, 使用Weka[46]中的多个常用分类器进行分类和评价.利用分类准确率作为特征子集选择的评价标准, 所有分类器的分类准确率都通过交叉验证获得.

      本文通过实验证明提出的方法在以下两方面的有效性: 1) 将最大信息系数度量应用到基于近似马尔科夫毯的特征选择方法中, 验证FCBF-MIC方法在特征降维能力上的效果, 并验证其选取特征的分类准确率; 2) 验证在选取相同维数特征的情况下, FCBF-MIC方法选取特征的分类准确率.

    • 实验中使用了UCI机器学习数据库上多个常用的数据集(如表 1所示), 数据集中包含了二分类和多分类数据, 特征数为34~2 000维, 样本数为62~4 601个, 能够很好地体现出特征选择方法的性能.

      表 1  UCI数据集

      Table 1.  UCI datasets

      数据集 特征总数 样本数 类别数
      Spambase 57 4 601 2
      Arrhythmia 452 279 16
      Dermatology 34 366 6
      Colon 2 000 62 2

      采用随机抽取的方法将整个数据集分成50%的训练集和50%的测试集, 分别使用FCBF-MIC和FCBF从训练集中选出特征子集, 并将选出的特征子集应用到测试集进行测试.实验中使用了机器学习模型中最常用的朴素贝叶斯(Naive Bayesian, NB)、K近邻(3NN)和使用线性核的支持向量机(Support vector machine, SVM)三种分类器, 使用10-fold交叉验证对特征子集进行测试和评价.为了避免选出的数据偏置, 同时为了使得实验更有说服性, 重复上述实验过程10次, 对10次的实验结果求均值得到最后的实验结果.

      为了体现最大信息系数度量在特征选择中的降维能力, 在FCBF-MIC方法和FCBF方法的第一阶段使用了相同的特征选择参数, 以保证两种特征选择方法的第一阶段得到相同维数的特征.实验中将对称不确定性参数值均设置为0, 认为对称不确定性值大于0的特征是与类别相关的特征.在第二阶段, 两种方法都使用了近似马尔科夫毯方法删除冗余特征, 便于对基于不同度量标准的两种方法的特征降维能力进行比较.

      表 2表 3分别给出了FCBF-MIC方法和FCBF方法在不同数据集上的特征降维能力和两种方法选取的特征在测试集上的分类准确率、标准差以及同一特征选择方法在不同数据集上选取特征的分类准确率均值(Average项).由定义3中近似马尔科夫毯的条件以及算法1中的描述可知, 近似马尔科夫毯方法选择的特征个数是不能灵活改变的, 因此两种方法在第二阶段选取的特征个数将会固定.从表 2中可知两种近似马尔科夫毯方法在降维能力上的差异, FCBF-MIC中近似马尔科夫毯方法往往能够得到更少的特征维数, 降维能力总体上好于FCBF.从表 3中可以看到, 虽然FCBF-MIC与FCBF在分类效果上各有优势, 但是FCBF-MIC利用较少维特征可以得到与FCBF可比的分类效果.此外, 使用特征选择之后, 多数数据集在不同的分类器上的分类效果都有一定的提升.

      表 2  两种特征选择方法选择的特征数

      Table 2.  The number of selected features in FCBF-MIC and FCBF

      数据集 特征总数 FBCF-MIC FCBF
      Spambase 57 7.2 16.8
      Arrhythmia 279 7.2 12.2
      Dermatology 34 18.2 12.6
      Colon 2 000 12.8 21

      表 3  两种特征选择方法在UCI数据集上的实验结果(均值 $\pm$ 标准差%)

      Table 3.  The comparison of two feature selection methods on UCI datasets (Mean $\pm$ Std%)

      数据集 NB 3NN SVM
      Full set NB FCBF-MIC FCBF Full set 3NN FCBF-MIC FCBF Full set SVM FCBF-MIC FCBF
      Spambase 79.93±0.30 86.93±2.15 78.60±2.34 87.55±1.47 89.43±0.51 87.8±2.05 90.11±0.62 90.15±0.98 90.24±0.88
      Arrhythmia 61.17±3.81 62.66±3.91 65.84±3.83 57.5±3.72 65.04±4.62 62.13±3.96 61.87±3.98 65.49±3.64 64.07±3.33
      Dermatology 96.06±1.00 97.16±1.27 96.27±0.91 95.08±1.51 95.63±0.84 95.52±0.64 96.61±1.27 96.83±0.40 95.85±0.74
      Colon 80.00±3.76 83.02±2.89 83.06±3.29 78.07±4.56 77.42±5.67 76.87±3.08 78.71±3.29 83.87±2.04 83.23±3.76
      Average 79.29 82.44 80.94 79.55 81.69 80.94 81.83 83.91 82.74

      表 3所示, 在三个分类器和四个数据集上的12组实验结果中, FCBF-MIC在其中9组的实验结果好于FCBF方法.其中, 在Spambase数据集使用NB分类器的实验结果中, FCBF-MIC方法较FCBF方法有8.33%的提升.在其余3组实验中, FCBF-MIC方法略逊于FCBF方法, 然而最大差距只有3.18% (Arrhythmia数据和NB分类器).但是, FCBF-MIC方法使用的特征维数比FCBF方法少5维.与使用特征全集的分类效果相比, FCBF-MIC方法在11组分类结果上有提升, 最大提升为7.54% (Arrhythmia数据集和3NN分类器), 而FCBF方法有9组有提升, 最大提升为4.67% (Arrhythmia数据集和NB分类器).

      最大信息系数能够度量线性、非线性、非函数关系等多种依赖关系, 也就能够挖掘特征与类别以及特征间更多的依赖关系.对于具有相同级别噪声的变量间依赖关系, 最大信息系数给出的得分是近似的, 避免了向某种依赖关系的偏置.从特征与类别的相关性角度, FBCF-MIC方法能够最大限度地保留与类别相关的、更有区分能力的特征, 也可以避免特征与类别的相关性评价的偏置.从特征间的冗余性角度, FCBF-MIC方法能够更为公平地删除更多的冗余特征, 使得特征间的冗余性进一步降低.由此, FCBF-MIC方法选择的特征对类别的区分能力更强, 且冗余度低, 因此分类准确率有所提升.

    • 实验中使用了ASU特征选择数据库上的两个图像数据集PIE10P, ORL10P和两个微阵列数据集TOX-171, SMK-CAN (如表 4所示), 数据集中同样包含了二分类和多分类数据, 且特征维数较多, 为2 420~19 993维.

      表 4  ASU数据集

      Table 4.  ASU datasets

      数据集 特征总数 样本数 类别数
      SMK-CAN 19 993 187 2
      TOX-171 5 748 171 4
      PIE10P 2 420 210 10
      ORL10P 10 304 100 10

      实验过程与第5.1节类似, 为了考查FCBF-MIC, FCBF, ReliefF, FAST, Lasso和RFS六种特征选择方法选取的特征在不同分类器下的效果, 本节实验仍然使用了NB, 3NN和SVM分类器, 使用10-fold交叉验证对特征子集进行测试.

      为了验证FCBF-MIC方法中近似马尔科夫毯方法和FCBF-MIC两阶段特征选择方法的有效性, 对六种特征选择方法在选取相同维数特征下的分类效果进行比较.由于FCBF-MIC和FCBF两种方法在降维能力上有差别以及近似马尔科夫毯方法选取的特征个数不能够灵活改变, 将第一阶段对称不确定性设定为不同值后得到相关性较高的特征集, 然后使用近似马尔科夫毯方法选择期望维数的特征子集. ReliefF方法是一种特征排序方法, 分别选取排序结束后期望维数的特征. FAST方法通过设定第一阶段不同的阈值来得到期望维数的特征. Lasso和RFS方法通过对特征分配不同的权重, 根据权重对特征降序排序, 选取期望维数的特征.

      随着特征选择方法中选取特征维数的增加, 分类器对数据的分类准确率不断上下波动.为了研究不同方法在选取不同维数特征时的分类性能, 使用六种特征选择方法分别选出10、20、30、40、50维特征, 然后使用分类器进行评价.最后, 对不同特征维数的分类准确率求均值得到最终的分类准确率.

      表 5~7为六种特征选择方法在三种分类器上, 基于不同维数特征的分类准确率均值、标准差以及同一特征选择方法在不同数据集上分类准确率均值Average项.图 2~5为六种特征选择方法在不同数据集上分类准确率的变化趋势.在三种分类器四个数据集下的12组实验中FCBF-MIC在6组中的分类准确率最高, FCBF, FAST和RFS方法分别有1组、3组和2组分类结果最好.

      表 5  六种特征选择方法在NB上的比较(均值 $\pm$ 标准差%)

      Table 5.  The comparison of six feature selection methods on NB classification (Mean $\pm$ Std%)

      数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
      SMK-CAN 70.66±1.56 65.19±3.53 62.21±3.49 64.9±3.74 68.12±1.88 68.67±2.36
      TOX-171 67.61±3.48 65.95 5.37 57.53±4.00 63.21±2.50 66.34±3.09 66.11±3.13
      PIE10P 92.11±2.33 87.58±3.92 92.46±3.12 93.14±3.01 84.22±1.42 84.71±3.11
      ORL10P 73.84±3.48 73.76±3.78 70.32±3.12 82.61±2.89 67.89±3.72 75.03±3.61
      Average 76.06 73.12 70.63 75.97 71.64 73.63

      表 6  六种特征选择方法在3NN上的比较(均值 $\pm$ 标准差%)

      Table 6.  The comparison of six feature selection methods on 3NN classification (Mean $\pm$ Std%)

      数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
      SMK-CAN 62.79±2.36 61.14±1.91 62.39±1.13 62.77±2.01 62.60±3.03 62.66±2.63
      TOX-171 69.25±2.02 69.49±2.82 60.51±3.11 64.55±3.17 67.31±3.09 69.32±3.19
      PIE10P 95.77±1.19 94.86±1.15 95.12±1.71 94.89±1.21 90.11±2.78 92.97±1.61
      ORL10P 88.88±3.06 90.16±1.78 83.76±3.49 90.34±2.65 82.22±3.95 87.94±3.07
      Average 79.17 78.91 78.14 75.45 75.56 78.22

      表 7  六种特征选择方法在SVM上的比较(均值 $\pm$ 标准差%)

      Table 7.  The comparison of six feature selection methods on SVM classification (Mean $\pm$ Std%)

      数据集 FCBF-MIC FCBF ReliefF FAST Lasso RFS
      SMK-CAN 68.28±1.60 65.26±2.31 67.27±1.33 68.04±1.47 67.81±1.54 68.04±1.78
      TOX-171 69.26±2.13 69.44±5.35 61.76±1.19 65.16±3.33 69.30±2.12 70.12±3.31
      PIE10P 97.56±1.24 95.35±0.51 95.21±0.97 96.38 1.56 95.27±1.17 95.58±1.21
      ORL10P 82.08±5.32 76.08±2.66 75.24±2.46 81.84±3.01 78.80±5.55 82.56±4.60
      Average 79.30 76.62 74.87 77.86 77.79 79.08

      图  2  六种特征选择方法在SMK-CAN数据集上的比较

      Figure 2.  The comparison of six feature selection methods on the SMK-CAN dataset

      图  3  六种特征选择方法在TOX-171数据集上的比较

      Figure 3.  The comparison of six feature selection methods on the TOX-171 dataset

      图  4  六种特征选择方法在PIE10P数据集上的比较

      Figure 4.  The comparison of six feature selection methods on the PIE10P dataset

      图  5  六种特征选择方法在ORL10P数据集上的比较

      Figure 5.  The comparison of six feature selection methods on the ORL10P dataset

      1) FCBF-MIC和FCBF方法的对比.

      图 2~5的实验结果中, 在TOX-171和ORL10P数据集上, FCBF-MIC方法和FCBF方法在三个分类器上的分类准确率各有优势.而在SMK-CAN和PIE10P数据集上, FCBF-MIC方法明显好于FCBF方法.在图 2~5的12个图中, 随着特征维数的增加, FCBF-MIC方法得到的特征的分类准确率均呈上升趋势, 且最后点的分类器准确率均高于起始点.

      表 5~7的实验结果与图 2~5中的实验结果类似.总体而言, 本文提出的FCBF-MIC方法在选取相同维数特征的情况下, 分类器准确率好于FCBF方法.

      在本节的12组实验中, FCBF-MIC方法在9组实验中分类效果好于FCBF方法, 该实验结果与第5.1节中实验结果类似, 而且FCBF-MIC方法较FCBF方法在分类器的准确率上总体的差值在增大.在9组FCBF-MIC好于FCBF方法的实验中, 有7组的准确率差值超过1.5%, 而第5.1节的实验中只有3组.因此, 相比于第5.1节, FCBF-MIC方法在选择更多维特征后, 分类效果又有一定的提升. 3组FCBF好于FCBF-MIC方法的实验中, 分类准确率最大差值为1.27%, 剩下的2组分类器差值均不超过0.25%, 差值并不明显, 性能基本相当.

      2) FCBF-MIC与ReliefF方法对比.

      表 5~7图 2~5中的实验结果可见, FCBF-MIC的效果大多数均好于ReliefF方法.只有在PIE10P数据集上使用NB分类器时, ReliefF的分类效果好于FCBF-MIC方法.在12组实验中, 有10组的分类准确率相差1%, 最大差值为10.07% (TOX-171数据集和NB分类器).由于ReliefF只考虑了特征相关性而没有对冗余性进行处理, 冗余特征对分类的干扰导致了性能的降低.

      3) FCBF-MIC与FAST、Lasso、RFS方法对比.

      表 5中FCBF-MIC方法与FAST方法在NB分类器上各有胜负, 且两种特征选择方法选取特征的分类效果相差明显.在ORL10P和PIE10P数据集上, FAST方法好于FCBF-MIC方法, 而在SMK-CAN和TOX-171数据集上, FCBF-MIC方法有明显的优势.对表 6表 7中实验结果而言, FCBF-MIC在3NN和SVM分类器上分类准确率优于FAST方法. FCBF-MIC在10组实验结果中优于Lasso, 并且在不同数据集上的效果较Lasso更加稳定. Lasso在PIE10P和ORL10P上的分类准确率较FCBF-MIC有明显的差距. FCBF-MIC方法较RFS方法, 在SVM分类器上的分类准确率相差不大, 在NB和3NN分类器上FCBF-MIC则明显好于RFS方法.

    • 本文引入最大信息系数建立了新的度量标准, 与近似马尔科夫毯方法相结合, 用于删除冗余特征.结合基于对称不确定性的特征排序方法, 构建了分别进行特征相关性分析和冗余性分析的两阶段特征选择方法FCBF-MIC.在UCI和ASU的多个公开数据集上进行了大量的实验, 验证了最大信息系数度量在特征选择中的有效性.本文提出的FCBF-MIC方法在选择更少维特征时, 可获得与FCBF方法可比的分类准确率; 在选择相同维数特征时, 分类准确率总体好于FCBF方法, 与过滤模型中的ReliefF方法和FAST方法以及嵌入模型中的Lasso和RFS方法相比也具有一定的优势.

      特征与特征子集之间关系的挖掘对于特征选择工作同样重要, 我们下一步的工作将对特征与特征子集间关系的度量进行研究, 并对最大信息系数进行进一步研究和应用, 基于最大信息系数理论提出更加有效的度量标准和特征选择方法.

参考文献 (46)

目录

    /

    返回文章
    返回