面向分类的流特征在线特征选择算法

doi:10.3969/j.issn.0372-2112.2020.02.015

电子学报 ›› 2020, Vol. 48 ›› Issue (2): 321-332.DOI: 10.3969/j.issn.0372-2112.2020.02.015

面向分类的流特征在线特征选择算法

尤殿龙^1,2, 郭松^1,2, 赵春慧^1,2, 原福永^1,2, 申利民^1,2, 陈真^1,2

1. 燕山大学信息科学与工程学院, 河北秦皇岛 066004;
2. 河北省计算机虚拟技术与系统集成重点实验室, 河北秦皇岛 066004

收稿日期:2019-06-10 修回日期:2019-10-17 出版日期:2020-02-25
- 通讯作者:
- 原福永
- 作者简介:
- 尤殿龙 男,1981年1月生,内蒙古赤峰人,博士,副教授.主要研究方向:流特征选择和因果发现,图信号处理,数据挖掘、人工智能、知识工程.E-mail:youdianlong@sina.com;郭松男,1994年5月生,河北邯郸人,硕士研究生.主要研究方向:流特征选择,人工智能.E-mail:guosongysu@163.com;赵春慧 女,1994年4月生,山西阳泉人,硕士研究生.主要研究方向:数据挖掘,推荐系统.E-mail:zch635134004@163.com
- 基金资助:
- 国家自然科学基金 (No.61772450）; 中国博士后科学基金 (No.2018M631764）; 河北省自然科学基金 (No.F2019203287，No.F2017203307）; 河北省科技计划项目 (No.17210701D）河北省博士后科研项目 (No.B2018003009）; 河北省教育厅科学研究计划项目 (No.KCJSX2017028）燕山大学基础研究专项课题 (No.16SKY011）; 燕山大学博士基金 (No.BL18003）

Online Feature Selection with Streaming Features for Classification

YOU Dian-long^1,2, GUO Song^1,2, ZHAO Chun-hui^1,2, YUAN Fu-yong^1,2, SHEN Li-min^1,2, CHEN Zhen^1,2

1. School of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China;
2. The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Qinhuangdao, Hebei 066004, China

Received:2019-06-10 Revised:2019-10-17 Online:2020-02-25 Published:2020-02-25

摘要/Abstract

摘要： 在线流特征选择通过实时过滤无关特征和冗余特征，实现流特征空间降维.针对已有算法，如Alpha-investing分类精度低、SAOLA选择特征数多和OSFS在低冗余高相关数据集下运行时间长的问题，提出了一种面向分类的流特征在线特征选择算法——OSFIC.算法运用四层过滤框架，通过无条件独立过滤不相关新特征、单条件下互信息过滤冗余新特征和候选特征集合中的部分冗余特征，最后通过多条件独立过滤候选特征集中的剩余冗余特征，最终得到分类标签的近似马尔可夫毯.为了分析OSFIC的性能，选择了NIPS 2003和Causality Workbench中的数据集，从预测精度、特征数量、运行时间和AUC方面与已有基准算法进行比较.实验表明，OSFIC平均分类精度比Alpha-investing提升4.41%.在保证精度的前提下，平均特征数量比SAOLA减少41.9%，运行时间比OSFS减少91.59%.最后，在真实的应用场景下验证了OSFIC的有效性.

关键词: 在线特征选择, 流特征, 互信息, 条件独立, 近似马尔可夫毯

Abstract: Online streaming feature selection achieves stream feature space dimensionality reduction by filtering irrelevant features and redundant features in real time.Existing works, such as Alpha-investing and Online Streaming Feature Selection (OSFS), have been proposed to serve this purpose, but they have drawbacks, including low prediction accuracy and high running time if the streaming features exhibit characteristics such as low redundancy and high relevance.We propose a novel classification-oriented online feature selection algorithm for streaming features, named OSFIC.OSFIC uses a four-layer filtering framework to filter irrelevant new features by null-conditional independence, filter redundant new features and redundant features in a candidate feature set by a single-conditional mutual information, and finally filter the remaining redundancy in the candidate feature set by multi-conditional independence.The approximate Markov blanket of the classify label is finally obtained.To analyze the performance of the algorithm, we selected the datasets in NIPS 2003 and Causality Workbench to compare prediction accuracy, number of selected features, runtime, and AUC with existing state-of-the-art algorithms.Experiments show that the average classification accuracy of OSFIC is 4.41% higher than that of Alpha-investing.Under the premise of high precision, the average number of features is 41.9% lower than SAOLA, and the runtime is 91.59% lower than OSFS.Finally, the efficiency of OSFIC is verified in real scenarios.

Key words: online feature selection, streaming feature, mutual information, conditional independence, approximate Markov blanket

中图分类号:

TP39

尤殿龙, 郭松, 赵春慧, 原福永, 申利民, 陈真. 面向分类的流特征在线特征选择算法[J]. 电子学报, 2020, 48(2): 321-332.

YOU Dian-long, GUO Song, ZHAO Chun-hui, YUAN Fu-yong, SHEN Li-min, CHEN Zhen. Online Feature Selection with Streaming Features for Classification[J]. Acta Electronica Sinica, 2020, 48(2): 321-332.

参考文献

[1] Charu C Aggarwal.Data Classification:Algorithms and Applications[M].1^th ed.Boca Raton:CRC press,2014.37-64.
[2] 乔立岩,彭喜元,彭宇.基于微粒群算法和支持向量机的特征子集选择方法[J].电子学报,2006,34(3):496-498. Qiao Li-yan,Peng Xi-yuan,Peng Yu.BPSO-SVM wrapper for feature subset selection[J].Acta Electronica Sinica,2006,34(3):496-498.(in Chinese)
[3] Li J,Cheng K,Wang S,et al.Feature selection:A data perspective[J].ACM Computing Surveys (CSUR),2018,50(6):94:1-94:45.
[4] Cai J,Luo J,Wang S,et al.Feature selection in machine learning:A new perspective[J].Neurocomputing,2018,300(7):70-79.
[5] Zhang Q,Zhang P,Long G,et al.Online learning from trapezoidal data streams[J].IEEE Trans,2016,KDE-28(10):2709-2723.
[6] Wu X,Yu K,Ding W,et al.Online feature selection with streaming features[J].IEEE Trans,2013,PAMI-35(5):1178-1192.
[7] Kohavi R,John G H.Wrappers for feature subset selection[J].Artificial intelligence,1997,97(1-2):273-324.
[8] Loscalzo S,Yu L,Ding C.Consensus group stable feature selection[A].Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining[C].New York:ACM press,2009.567-576.
[9] Rodriguez-Lujan I,Huerta R,Elkan C,et al.Quadratic programming feature selection[J].Journal of Machine Learning Research,2010,11(1):1491-1516.
[10] Zhao Z,Liu H.Searching for interacting features in subset selection[J].Intelligent Data Analysis,2009,13(2):207-228.
[11] 吴信东,何进,陆汝钤.从大数据到大知识:HACE+BigKE[J].自动化学报,2016,42(7):965-982. Wu Xin-dong,He Jing,Lu Ru-qian.From big data to big knowledge:HACE+ BigKE[J].Acta Automatica Sinica,2016,42(7):965-982.(in Chinese)
[12] Yu K,Wu X,Ding W,et al.Scalable and accurate online feature selection for big data[J].ACM Trans,2016,KDD-11(2):16:1-16:39.
[13] 张昊,陶然,李志勇.基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究[J].电子学报,2009,37(7):1628-1632. Zhang Hao,Tao Ran,Li Zhi-yong.A research and application of feature selection based on KNN and tabu search algorithm in the intrusion detection[J].Acta Electronica Sinica,2009,37(7):1628-1632.(in Chinese)
[14] Jia X,Kuo B C,Crawford M M.Feature mining for hyperspectral image classification[J].Proceedings of the IEEE,2013,101(3):676-697.
[15] Wang D,Irani D,Pu C.Evolutionary study of web spam:Webb spam corpus 2011 versus webb spam corpus 2006[A].Proceedings of the 8th International Conference on Collaborative Computing:Networking,Applications and Worksharing (CollaborateCom)[C].Pittsburgh:IEEE,2012.40-49.
[16] Singh N, Lai K H, Vejvar M, et al.Big data technology:Challenges,prospects and realities[J].IEEE Engineering Management Review,2019,47(1):58-66.
[17] Wu X,Zhu X,Wu G Q,et al.Data mining with big data[J].IEEETrans,2014,KDE-26(1):97-107.
[18] Kira K,Rendell L A .The Feature Selection Problem:Traditional Methods and a New Algorithm[A].Proceedings of the Tenth National Conference on Artificial Intelligence[C].San Jose:AAAI Press,1992.129-134.
[19] Peng H,Long F,Ding C.Feature selection based on mutual information:criteria of max-dependency,max-relevance,and min-redundancy[J].IEEE Trans,2005,PAMI-27(8):1226-1238.
[20] Yu K,Ding W,Simovici D A,et al.Classification with streaming features:An emerging-pattern mining approach[J].ACM Trans,2014,KDD-9(4):30:1-30:31.
[21] Mairal J,Bach F,Ponce J,et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research,2010,11(1):19-60.
[22] Wang J,Zhao P,Hoi S C H,et al.Online feature selection and its applications[J].IEEE Trans,2014,KDE-26(3):698-710.
[23] Perkins S,Theiler J.Online feature selection using grafting[A].Proceedings of the 20th International Conference on Machine Learning (ICML)[C].Washington DC:AAAI Press,2003.592-599.
[24] Zhou J, Foster D P, Stine R A, et al.Streamwise Feature Selection [J].Journal of Machine Learning Research,2006,7(9):1861-1885.
[25] Wang J,Wang M,Li P,et al.Online feature selection with group structure analysis[J].IEEE Trans,2015,KDE-27(11):3029-3041.
[26] Yu K,Wu X,Ding W,et al.Scalable and accurate online feature selection for big data[J].ACM Trans,2016,KDD-11(2):16:1-16:39.
[27] Aliferis C F,Statnikov A,Tsamardinos I,et al.Local causal and markov blanket induction for causal discovery and feature selection for classification part i:Algorithms and empirical evaluation[J].Journal of Machine Learning Research,2010,11(1):171-234.
[28] Koller D.Toward optimal feature selection[A].Proceedings of the Proceedings of the 20th International Conference on Machine Learning (ICML)[C].Washington DC:AAAI Press,1996.284-292.
[29] Neapolitan R E.Learning Bayesian Networks[M].1^th ed.Upper Saddle River,NJ:Pearson Prentice Hall,2004.600-604.
[30] Press W H,Teukolsky S A,Vetterling W T,et al.Numerical Recipes in C[M].Cambridge:Cambridge university press,1992.632-636.

面向分类的流特征在线特征选择算法

Online Feature Selection with Streaming Features for Classification

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	彭丝雨, 周到, 张家琦, 王宇, 高军峰. 基于互信息的脑网络及测谎研究[J]. 电子学报, 2019, 47(7): 1551-1556.
[2]	李庆武, 马云鹏, 周亚琴, 邢俊. 基于无监督栈式降噪自编码网络的显著性检测算法[J]. 电子学报, 2019, 47(4): 871-879.
[3]	雷维嘉, 宋海娜, 陈胜男, 谢显中. 基于无率纠错码和高阶QAM调制的收端速率自适应方案[J]. 电子学报, 2017, 45(8): 2001-2007.
[4]	马润年, 王班, 王刚, 郭晓成, 刘文斌. 基于互信息的通信网络节点重要性度量方法[J]. 电子学报, 2017, 45(3): 747-752.
[5]	张晴晖, 张榆锋, 林文晶, 周屹, 章克信, 高莲. 颈动脉B超估计血管壁搏动位移的干扰抑制[J]. 电子学报, 2017, 45(12): 2903-2908.
[6]	续欣莹, 张扩, 谢珺, 谢刚. 基于互信息下粒子群优化的属性约简算法[J]. 电子学报, 2017, 45(11): 2695-2704.
[7]	王静云, 刘三阳, 朱明敏. 基于条件独立测试的链图结构学习算法[J]. 电子学报, 2017, 45(10): 2443-2448.
[8]	宋岚, 文堂柳, 黎海生, 王杉. 基于云模型、图论和互信息的遥感影像分割方法[J]. 电子学报, 2015, 43(8): 1518-1525.
[9]	黄虹, 张建秋. 一个图像质量盲评估的统计测度[J]. 电子学报, 2014, 42(7): 1419-1423.
[10]	朱明敏, 刘三阳, 杨有龙. 基于混合方式的贝叶斯网络等价类学习算法[J]. 电子学报, 2013, 41(1): 98-104.
[11]	张博;景晓军;孙松林;张少乐. 基于梯度离散度和互信息准则的残缺指纹方向场重建融合算法[J]. 电子学报, 2011, 39(9): 2130-2134.
[12]	袁华强;叶阳东;刘东. 遗传顺序IB算法[J]. 电子学报, 2009, 37(8): 1804-1809.
[13]	马建华;陈武凡;黄静;杨迪;毕一鸣. 基于最大互信息量熵差分割的CT金属伪影消除[J]. 电子学报, 2009, 37(8): 1779-1783.
[14]	刘兆广;彭玉华;杨阳. 一种基于类haar小波的MCTF视频编码方案[J]. 电子学报, 2008, 36(2): 386-391.
[15]	杨静;胡顺波;刘常春;杨金宝. 基于简单Schur凹函数的图像配准测度研究[J]. 电子学报, 2008, 36(12): 2328-2332.