带高斯核的支持向量数据描述问题的高效积极集法

doi:10.11772/j.issn.1001-9081.2023121809

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (12): 3808-3814.DOI: 10.11772/j.issn.1001-9081.2023121809

带高斯核的支持向量数据描述问题的高效积极集法

张奇业, 曾心蕊()

北京航空航天大学数学科学学院，北京 102206

收稿日期:2024-01-02 修回日期:2024-04-12 接受日期:2024-04-18 发布日期:2024-06-13 出版日期:2024-12-10
通讯作者: 曾心蕊
作者简介:张奇业（1975—），女，河南洛阳人，副教授，博士，主要研究方向：最优化理论、机器学习；
基金资助:
北京航空航天大学研究生教育与发展研究专项基金资助项目(JG2023014)

Efficient active-set method for support vector data description problem with Gaussian kernel

Qiye ZHANG, Xinrui ZENG()

School of Mathematical Sciences，Beihang University，Beijing 102206，China

Received:2024-01-02 Revised:2024-04-12 Accepted:2024-04-18 Online:2024-06-13 Published:2024-12-10
Contact: Xinrui ZENG
About author:ZHANG Qiye， born in 1975， Ph. D.， associate professor. Her research interests include optimization theory， machine learning.
Supported by:
Special Fund for Graduate Education and Development Research of Beihang University(JG2023014)

摘要/Abstract

摘要：

针对积极集法求解支持向量数据描述（SVDD）问题时，在大规模数据场景下每次迭代计算量大、效率低的问题，设计一种带高斯核的SVDD问题的高效积极集法（ASM-SVDD）。首先，利用SVDD对偶模型约束条件的特殊性，每次迭代求解一个降维的等式约束子问题；其次，通过矩阵操作实现积极集的更新，每次更新计算只与当前支持向量及单个样本点有关，从而极大地降低计算量；另外，由于ASM-SVDD算法是传统积极集法的一种变体，应用积极集法理论得到该算法的有限终止性；最后，基于仿真和真实数据集，验证ASM-SVDD算法性能。结果表明，随着训练轮次的增加，ASM-SVDD算法可以有效提升模型性能。与求解SVDD问题的快速增量算法FISVDD （Fast Incremental SVDD）相比，ASM-SVDD算法在典型的低维高样本数据集shuttle上训练得到的目标函数值可减小25.9%，对支持向量的识别能力可提高10.0%。同时，ASM-SVDD算法在不同数据集上的F1分数相较于FISVDD算法均有提高，在超大规模数据集criteo上提高量可达0.07%。可见，ASM-SVDD算法在检测异常值的同时，训练得到的超球体更稳定，且对测试样本的判断准确率也更高，适用于大规模数据场景下的异常值检测。

关键词: 支持向量数据描述, 二次规划, 积极集法, 异常值检测, 有限终止性

Abstract:

To address the large amount of calculation and low efficiency during each iteration in large-scale data scenarios when using active-set method to solve the problem of Support Vector Data Description （SVDD）， an efficient Active-Set Method for SVDD problem with Gaussian kernel （ASM-SVDD） was designed. Firstly， due to the peculiarity of constraint conditions in SVDD dual model， a dimension-reduced subproblem with equality constraints was solved in each iteration. Then， the active-set was updated through matrix manipulations. Each update calculation was only related to the existing support vectors and a single sample point， which reduced the amount of computation dramatically. In addition， since ASM-SVDD algorithm can be seen as a variant of the traditional active-set method， the limited termination of this algorithm was obtained by applying the theory of active-set method. Finally， simulation and real datasets were used to verify the performance of ASM-SVDD algorithm. The results show that ASM-SVDD algorithm can improve the model performance effectively as the number of training rounds increases. Compared to the fast incremental algorithm to solve SVDD problem — FISVDD （Fast Incremental SVDD）， ASM-SVDD algorithm has the objective value obtained by training reduced by 25.9% and the recognition ability of support vectors improved by 10.0% on the typical low-dimensional high-sample dataset shuttle. At the same time， ASM-SVDD algorithm obtains F1 scores on different datasets all higher than FISVDD algorithm with the maximum improvement of 0.07% on the super large-scale dataset criteo. It can be seen that ASM-SVDD algorithm can obtain more stable hypersphere through training， and obtain higher judgment accuracy of test samples while performing outlier detection. Therefore， ASM-SVDD algorithm is suitable for outlier detection in large-scale data scenarios.

Key words: Support Vector Data Description (SVDD), quadratic programming, active-set method, outlier detection, limited termination

中图分类号:

TP301.6

张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 计算机应用, 2024, 44(12): 3808-3814.

Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel[J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.

图/表 4

参考文献 30

1	VAPNIK V N， LERNER A Y. Recognition of patterns with help of generalized portraits ［J］. Avtomatika i Telemekhanika， 1963， 24（6）： 774-780.
2	TAX D M J， DUIN R P W. Support vector data description ［J］. Machine Learning， 2004， 54： 45-66.
3	CHANG W C， LEE C P， LIN C J. A revisit to support vector data description ［EB/OL］. ［2023-09-02］..
4	PLATT J. Sequential minimal optimization： a fast algorithm for training support vector machines ［EB/OL］. ［2023-09-04］..
5	BOTTOU L， LIN C J. Support vector machine solvers ［EB/OL］. ［2023-09-03］..
6	FAN R E， CHANG K W， HSIEH C J， et al. LIBLINEAR： a library for large linear classification［J］. Journal of Machine Learning Research， 2008， 9： 1871-1874.
7	SCHEINBERG K. An efficient implementation of an active set method for SVMs［J］. Journal of Machine Learning Research， 2006， 7： 2237-2257.
8	JIANG H， WANG H， HU W， et al. Fast incremental SVDD learning algorithm with the Gaussian kernel ［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 3991-3998.
9	ZHANG J， ZHANG Q， QIN X， et al. A two-stage fault diagnosis methodology for rotating machinery combining optimized support vector data description and optimized support vector machine ［J］. Measurement， 2022， 200： No.111651.
10	ZHAO Y P， XIE Y L， YE Z F. A new dynamic radius SVDD for fault detection of aircraft engine ［J］. Engineering Applications of Artificial Intelligence， 2021， 100： No.104177.
11	TAO X， CHEN W， ZHANG X， et al. SVDD boundary and DPC clustering technique-based oversampling approach for handling imbalanced and overlapped data ［J］. Knowledge-Based Systems， 2021， 234： No.107588.
12	TAO X， ZHENG Y， CHEN W， et al. SVDD-based weighted oversampling technique for imbalanced and overlapped dataset learning ［J］. Information Sciences， 2022， 588： 13-51.
13	WU X， LIU S， BAI Y. The manifold regularized SVDD for noisy label detection ［J］. Information Sciences， 2023， 619： 235-248.
14	胡天杰，胡文军，王士同. 分布熵惩罚的支持向量数据描述［J］. 计算机应用， 2021， 41（8）： 2212-2218.
	HU T J， HU W J， WANG S T. Distribution entropy penalized support vector data description ［J］. Journal of Computer Applications， 2021， 41（8）： 2212-2218.
15	XIE W， LIANG G， GUO Q. A new improved FSVM algorithm based on SVDD ［J］. Concurrency and Computation： Practice and Experience， 2019， 31（9）： No.e4893.
16	LI D， XU X， WANG Z， et al. Boundary-based Fuzzy-SVDD for one-class classification［J］. International Journal of Intelligent Systems， 2022， 37（3）： 2266-2292.
17	ALAM S， SONBHADRA S K， AGARWAL S， et al. Sample reduction using Farthest Boundary Point Estimation （FBPE） for Support Vector Data Description （SVDD）［J］. Pattern Recognition Letters， 2020， 131： 268-276.
18	CHOU H Y， LIN P Y， LIN C J. Dual coordinate-descent methods for linear one-class SVM and SVDD ［C］// Proceedings of the 2020 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2020： 181-189.
19	CARLEVARO A， MONGELLI M. A new SVDD approach to reliable and explainable AI ［J］. IEEE Intelligent Systems， 2022， 37（2）： 55-68.
20	ORR G B， MÜLLER K R. Neural networks： tricks of the trade， LNCS 1524 ［M］. Berlin： Springer， 1998： 9-48.
21	LASKOV P， GEHL C， KRÜGER S， et al. Incremental support vector learning： analysis， implementation and applications ［J］. Journal of Machine Learning Research， 2006， 7： 1909-1936.
22	WANG X， QU J， DI Y， et al. Fast online SVDD based on support vectors merging［C］// Proceedings of the 10th International Conference on Advanced Computational Intelligence. Piscataway： IEEE， 2018： 197-203.
23	刘红英，夏勇，周水生. 数学规划基础［M］. 北京：北京航空航天大学出版社， 2012：191-194.
	LIU H Y， XIA Y， ZHOU S S. Mathematical programming basics［M］. Beijing： Beihang University Press， 2012： 191-194.
24	NOCEDAL J， WRIGHT S J. Numerical optimization ［M］. New York： Springer， 1999： 467-480.
25	GALLIER J. The Schur complement and symmetric positive semidefinite （and definite） matrices［EB/OL］. ［2023-09-06］..
26	刘浩洋，户将，李勇峰，等. 最优化：建模、算法与理论［M］. 北京：高等教育出版社， 2020：184-193.
	LIU H Y， HU J， LI Y F， et al. Optimization： modeling， algorithm and theory ［J］. Beijing： Higher Education Press， 2020： 184-193.
27	CHANG C C， TSAI H C， LEE Y J. A minimum enclosing balls labeling method for support vector clustering ［R］. Taipei， Taiwan： National Taiwan University of Science and Technology， 2007.
28	DUA D， GRAFF C. UCI machine learning repository ［DB/OL］. ［2023-09-08］..
29	WOODS K S， DOSS C C， BOWYER K W， et al. Comparative evaluation of pattern recognition techniques for detection of microcalcifications in mammography ［J］. International Journal of Pattern Recognition and Artificial Intelligence， 1993， 7（6）： 1417-1436.
30	CHANG C C， LIN C J. LIBSVM： a library for support vector machines［J］. ACM Transactions on Intelligent Systems and Technology， 2011， 2（3）： No.27.

训练轮次	测试结果
训练轮次	圆心	半径	支持向量数	异常值数
200	（1.27，2.56）	8.14	97	327
1 000	（0.89，1.50）	7.55	98	277
3 000	（0.23，0.10）	7.08	102	268

训练轮次	测试结果
训练轮次	圆心	半径	支持向量数	异常值数
200	（1.27，2.56）	8.14	97	327
1 000	（0.89，1.50）	7.55	98	277
3 000	（0.23，0.10）	7.08	102	268

数据集名称	正常样本数	异常样本数	训练集样本数	测试集样本数	维数
shuttle	45 586	12 414	36 469	21 531	9
mammography	7 595	254	6 076	1 773	10
a9a	19 717	6 291	15 774	10 234	123
criteo	45 840 617	6 042 135	41 506 202	10 376 550	1 000 000

数据集名称	正常样本数	异常样本数	训练集样本数	测试集样本数	维数
shuttle	45 586	12 414	36 469	21 531	9
mammography	7 595	254	6 076	1 773	10
a9a	19 717	6 291	15 774	10 234	123
criteo	45 840 617	6 042 135	41 506 202	10 376 550	1 000 000

数据集	算法	测试集中识别得到的异常值数	训练集对应目标函数值		训练集得到的支持向量数		F1分数
数据集	算法	测试集中识别得到的异常值数	数值	比FISVDD 降低百分比/%	数值	比FISVDD 增加百分比/%	数值	比FISVDD 提高百分比/%
shuttle	ASM-SVDD	0	1.75395×10^-3	25.91	1720	10.04	0.9669	0.01
shuttle	FISVDD	—	2.367 25×10^-3	—	1 563	—	0.966 8	—
mammography	ASM-SVDD	218	9.79150×10^-3	6.69	312	2.30	0.5524	0.42
mammography	FISVDD	—	1.049 37×10^-2	—	305	—	0.550 1	—
a9a	ASM-SVDD	0	1.69490×10^-4	0.06	13541	4.64	0.6766	0.11
a9a	FISVDD	—	1.694 91×10^-4	—	12 941	—	0.675 8	—
criteo	ASM-SVDD	23 957	8.56380×10^-3	14.78	13748633	0.03	0.8735	0.07
criteo	FISVDD	—	1.004 92×10^-2	—	13 744 982	—	0.872 9	—

带高斯核的支持向量数据描述问题的高效积极集法

Efficient active-set method for support vector data description problem with Gaussian kernel

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 30

相关文章 15

编辑推荐

Metrics

[1]	胡天杰, 胡文军, 王士同. 分布熵惩罚的支持向量数据描述[J]. 计算机应用, 2021, 41(8): 2212-2218.
[2]	李小文, 范艺芳, 侯宁宁. 基于阴影域的搜索树检测算法[J]. 计算机应用, 2019, 39(5): 1400-1404.
[3]	杨晨, 王婕婷, 李飞江, 钱宇华. 基于概率的支持向量数据描述方法[J]. 计算机应用, 2019, 39(11): 3134-3139.
[4]	靳燕, 彭新光. 多子域隔离学习组合决策用于不均衡样本[J]. 计算机应用, 2016, 36(9): 2475-2480.
[5]	刘兴, 张浩, 徐凌伟. 基于波束成形的60GHz无线局域网络定位算法[J]. 计算机应用, 2016, 36(8): 2170-2174.
[6]	李方伟, 张新跃, 朱江, 张海波. 基于信息融合的网络安全态势评估模型[J]. 计算机应用, 2015, 35(7): 1882-1887.
[7]	杨小明, 胡文军, 楼俊钢, 蒋云良. 局部分块的一类支持向量数据描述[J]. 计算机应用, 2015, 35(4): 1026-1029.
[8]	李金静, 陈庆奎, 刘宝平, 刘伯成. 基于图形处理器的视频二值概率分割[J]. 计算机应用, 2015, 35(11): 3187-3193.
[9]	谢国城蒋芸陈娜. 基于超球体多类支持向量数据描述的医学图像分类新方法[J]. 计算机应用, 2013, 33(11): 3300-3304.
[10]	吴桂峰王轩. 基于二次规划的无线传感器网络数据恢复算法[J]. 计算机应用, 2013, 33(04): 935-938.
[11]	黄仕建. 支持向量数据描述在烟叶异物检测中的应用[J]. 计算机应用, 2012, 32(03): 881-884.
[12]	陈伟余旭初张鹏强王智超王鹤. 基于一类支持向量机的高光谱影像地物识别[J]. 计算机应用, 2011, 31(08): 2092-2096.
[13]	何伟成方景龙. 基于信息熵的支持向量数据描述分类[J]. 计算机应用, 2011, 31(04): 1114-1116.
[14]	刘宗礼曹洁郝元宏. 一种新的特征提取方法及其在模式识别中的应用[J]. 计算机应用, 2009, 29(4): 1032-1035.
[15]	山艳须文波孙俊 . QPSO算法在训练支持向量机中的应用[J]. 计算机应用, 2006, 26(11): 2645-2647.