面向多类别分类问题的子抽样主动学习方法

doi:10.12305/j.issn.1001-506X.2021.03.13

摘要/Abstract

摘要：

由于传统主动学习方法的计算量随着问题规模的增大呈指数增长, 因此很难应用于大规模多类数据分类任务中。为解决该问题, 设计了一种基于子抽样的主动学习(subsampling-based active learning, SBAL)算法。该算法将无监督聚类算法与传统主动学习方法整合, 在二者之间增加了子抽样操作, 该操作能够显著降低算法的时间复杂度, 在保证实验准确率的基础上减少实验耗时, 从而更加高效地处理大规模数据集的分类问题。实验结果显示, 采用SBAL算法的实验性能优于传统主动学习算法, 证明了所提算法可以突破传统主动学习方法不能处理大规模数据集多类别分类问题的局限性。

关键词: 子抽样, 主动学习, 无监督聚类, 多类别分类问题

Abstract:

Because the computational amount of the traditional active learning method increases exponentially with the increase of problem size, it is difficult to apply to the large-scale multi-category data classification tasks. To solve this problem, a subsampling-based active learning (SBAL) algorithm is designed. This algorithm integrates unsupervised clustering algorithm with traditional active learning method, and adds subsampling operation between them. This operation can significantly reduce the time complexity of the algorithm, reduce the experimental time-consuming on the basis of ensuring the accuracy of the experiment, so as to deal with the classification problem of large-scale data sets more efficiently. The experimental results show that the experimental performance of the SBAL algorithm is better than that of the traditional active learning algorithm, which proves that the proposed method can break through the limitation that the traditional active learning method can not deal with multi-category classification of large-scale data sets.

Key words: subsampling, active learning, unsupervised clustering, multi-category classification problem

中图分类号:

TP181

施伟, 黄红蓝, 冯旸赫, 刘忠. 面向多类别分类问题的子抽样主动学习方法[J]. 系统工程与电子技术, 2021, 43(3): 700-708.

Wei SHI, Honglan HUANG, Yanghe FENG, Zhong LIU. Subsampling oriented active learning method for multi-category classification problem[J]. Systems Engineering and Electronics, 2021, 43(3): 700-708.

图/表 11

图1

图2

图3

图4

表1

图5

表2

表3

表4

图6

图7

参考文献 32

1	冯蕴天, 张宏军, 郝文宁. 面向军事文本的命名实体识别[J]. 计算机科学, 2015, 42 (7): 15- 18, 47.
	FENG Y T , ZHANG H J , HAO W N . Named entity recognition for military text[J]. Computer Science, 2015, 42 (7): 15- 18, 47.
2	CHENG G , YANG C Y , YAO X W , et al. When deep learning meets metric learning: remote sensing image scene classification via learning discriminative CNNs[J]. IEEE Trans.on Geoence and Remote Sensing, 2018, 56 (5): 2811- 2821. doi: 10.1109/TGRS.2017.2783902
3	王国胤, 何晓. 一种不确定性条件下的自主式知识学习模型[J]. 软件学报, 2003, 14 (6): 68- 74.
	WANG G Y , HE X . A self-learning model under uncertain condition[J]. Journal of Software, 2003, 14 (6): 68- 74.
4	YANG Y , MA Z G , NIE F P , et al. Multi-class active learning by uncertainty sampling with diversity maximization[J]. International Journal of Computer Vision, 2015, 113 (2): 113- 127. doi: 10.1007/s11263-014-0781-x
5	JENNIFER V , ALDEA E . Evidential query-by-committee active learning for pedestrian detection in high-density crowds[J]. International Journal of Approximate Reasoning, 2019, 104 (1): 166- 184.
6	HAO S . Query by diverse committee in transfer active learning[J]. Frontiers of Computer Science, 2019, 13 (2): 280- 291. doi: 10.1007/s11704-017-6117-6
7	吴伟宁, 刘扬, 郭茂祖, 等. 基于采样策略的主动学习算法研究进展[J]. 计算机研究与发展, 2012, 49 (6): 1162- 1173.
	WU W N , LIU Y , GUO M Z , et al. Advances in active learning algorithms based on sampling strategy[J]. Journal of Computer Research and Development, 2012, 49 (6): 1162- 1173.
8	TOMASZ G , MACIEJ L . Stacked regression with a generalization of the moore-penrose pseudoinverse[J]. Statistics in Transition New Series, 2017, 18 (3): 443- 458. doi: 10.21307/stattrans-2016-080
9	MENG Q, WANG Y, CHEN W, et al. Generalization error bounds for optimization algorithms via stability[C]//Proc.of the 31st AAAI Conference on Artificial Intelligence, 2017: 2336-2342.
10	ZHANG C , CHEN T . An active learning framework for content-based information retrieval[J]. IEEE Trans.on Multimedia, 2002, 4 (2): 260- 268. doi: 10.1109/TMM.2002.1017738
11	SETTLES B, CRAVEN M. An analysis of active learning strategies for sequence labeling tasks[C]//Proc.of the Confe-rence on Empirical Methods in Natural Language Processing, 2008: 25-27.
12	HUANG H L , HUANG J C , FENG Y H , et al. On the improvement of reinforcement active learning with the involvement of cross entropy to address one-shot learning problem[J]. Public Library of Science One, 2019, 14 (6): 1- 17.
13	HUANG H L , FENG Y H , HUANG J C , et al. A reinforcement one-shot active learning approach for aircraft type recognition[J]. IEEE Access, 2019, 7, 147204- 147214. doi: 10.1109/ACCESS.2019.2946186
14	BRINKER K. Incorporating diversity in active learning with support vector machines[C]//Proc.of the 20th International Conference on Machine learning, 2003: 59-66.
15	YU K, BI J, TRESP V. Active learning via transductive experimental design[C]//Proc.of the 23rd International Conference on Machine Learning, 2006: 1081-1088.
16	YANG Y Z, LOOG M. Single shot active learning using pseudo annotators[EB/OL].[2020-03-10].https://arxiv.org/abs/1805.06660.
17	SHEN Y , WANG P J , PAN Z F , et al. An active learning framework for alpha matting[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2019, 33 (9): 1951003:1- 1951003:20.
18	ROMAN S, ARTEM S, IVAN S. Active learning with adaptive density weighted sampling for information extraction from scientific papers[C]//Proc.of the Conference on Artificial Intelligence and Natural Language, 2017: 77-90.
19	KONYUSHKOVA K, SZNITMAN R, FUA P. Learning active learning from data[C]//Proc.of the 31st International Conference on Nerual Information Processing Systems, 2017: 4228-4238.
20	HIEU T N, ARNOLD S. Active learning using pre-clustering[C]//Proc.of the 21st International Conference on Machine Learning, 2004: 623-630.
21	BODO Z, MINIER Z, CSATO L. Active learning with cluster-ing[C]//Proc.of the Workshop on Active Learning and Experimental Design, 2011, 16: 127-139.
22	吕宗平, 时熙然, 顾兆军. 基于模糊核聚类和主动学习的异常检测方法[J]. 现代电子技术, 2019, 42 (20): 53- 57, 63.
	LYU Z P , SHI X R , GU Z J . Anomaly detection method based on fuzzy kernel clustering and active learning[J]. Modern Electronics Technique, 2019, 42 (20): 53- 57, 63.
23	张鹏, 刘寅, 栾国强, 等. 基于图约束和预聚类的主动学习算法在威胁情景感知中的研究[J]. 计算机应用研究, 2017, 34 (5): 1544- 1547. doi: 10.3969/j.issn.1001-3695.2017.05.060
	ZHANG P , LIU Y , LUAN G Q , et al. Research on threat situation awareness in activing learning algorithm based on graph constraints and pre-clustering[J]. Application Research of Computers, 2017, 34 (5): 1544- 1547. doi: 10.3969/j.issn.1001-3695.2017.05.060
24	柴变芳, 吕峰, 李文斌, 等. 基于主动学习先验的半监督K-means聚类算法[J]. 计算机应用, 2018, 38 (11): 3139- 3143. doi: 10.11772/j.issn.1001-9081.2018041251
	CHAI B F , LYU F , LI W B , et al. Semi-supervised K-means clustering algorithm based on active learning priors[J]. Journal of Computer Applications, 2018, 38 (11): 3139- 3143. doi: 10.11772/j.issn.1001-9081.2018041251
25	ZHANG C , FANG Z . An improved K-means clustering algorithm[J]. Journal of Information and Computational Science, 2013, 10 (1): 193- 199.
26	AGGARWAL A, DESHPANDE A, KANNAN R. Adaptive sampling for k-means clustering[C]//Proc. of the 12th International Workshop and 13th Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2009: 15-28.
27	杨俊闯, 赵超. K-Means聚类算法研究综述[J]. 计算机工程与应用, 2019, 55 (23): 7- 14, 63.
	YANG J C , ZHAO C . Survey on K-means clustering algorithm[J]. Computer Engineering and Applications, 2019, 55 (23): 7- 14, 63.
28	ZHU J B , WANG H Z , TSOU B K , et al. Active learning with sampling by uncertainty and density for data annotations[J]. IEEE Trans.on Audio, Speech, and Language Processing, 2010, 18 (6): 1323- 1331. doi: 10.1109/TASL.2009.2033421
29	KEE S , CASTILLO E D , RUNGER G . Query-by-committee improvement with diversity and density in batch active learning[J]. Information Sciences, 2018, 454-455, 401- 418. doi: 10.1016/j.ins.2018.05.014
30	BEYGELZIMER A, DASGUPTA S, LANGFORD J. Importance weighted active learning[C]//Proc.of the 26th Annual International Conference on Machine Learning, 2009: 49-56.
31	ROWEIS S. Binary alphadigits[EB/OL].[2020-03-06]. http://cs.nyu.edu/~roweis/data/binaryalphadigs.mat.
32	LAKE B M , SALAKHUTDINOV R , TENENBAUM J B . Human-level concept learning through probabilistic program induction[J]. Science, 2015, 350 (6266): 1332- 1338. doi: 10.1126/science.aab3050

算法	样本类别
	3类		5类		8类
	平均准确率/%	查询数量	平均准确率/%	查询数量	平均准确率/%	查询数量
随机抽样	83.4	24	75.7	40	68.5	64
不确定性采样	86.6	24	78.9	40	71.5	64
基于专委会投票查询	86.1	24	78.5	40	71.3	64
密度加权	83.5	24	76.1	40	68.9	64
基于学习	84.5	24	75.8	40	68.2	64

算法	样本类别
	3类		5类		8类
	平均准确率/%	查询数量	平均准确率/%	查询数量	平均准确率/%	查询数量
随机抽样	72.5	24	63.2	40	55.0	64
不确定性采样	73.9	24	64.2	40	55.3	64
基于专委会投票查询	74.2	24	64.9	40	56.5	64
密度加权	70.2	24	61.5	40	53.7	64
基于学习	73.3	24	63.4	40	54.9	64

算法	平均准确率/%
算法	原始策略	3类别子抽样
随机抽样	61.2	71.6
不确定性采样	62.7	73.2
基于专委会投票查询	63.0	73.6
密度加权	62.6	70.1
基于学习	60.7	72.5
总耗时/min	126.765 1	20.936 6

算法	平均准确率/%
算法	原始策略	3类别子抽样
随机抽样	29.8	72.1
不确定性采样	27.3	72.9
基于专委会投票查询	28.8	74.4
密度加权	31.4	70.1
基于学习	24.9	73.5
总耗时/min	779.771 3	19.126 7

[1]	马骏, 杨镜宇, 吴曦. 基于预聚类主动半监督的作战体系效能评估[J]. 系统工程与电子技术, 2022, 44(6): 1889-1896.
[2]	孙煜飞, 马良荔, 吕闽晖, 覃基伟. 基于改进协同训练的本体映射方法[J]. 系统工程与电子技术, 2017, 39(2): 459-464.
[3]	徐海龙, 别晓峰, 冯卉, 吴天爱. 一种基于QBC的SVM主动学习算法[J]. 系统工程与电子技术, 2015, 37(12): 2865-2871.