基于二阶序列最小优化的最小闭包球近似算法  

Approximation algorithm of minimum enclosing ball based on second-order sequential minimum optimization

作　　者：丛伟杰 王佳佳 安梦园 CONG Weijie;WANG Jiajia;AN Mengyuan(School of Science,Xi'an University of Posts and Telecommunications,Xi'an 710121,China;School of Computer Science and Technology,Xi'an University of Posts and Telecommunications,Xi'an 710121,China)

机构地区：[1]西安邮电大学理学院,陕西西安710121 [2]西安邮电大学计算机学院,陕西西安710121

出　　处：《西安邮电大学学报》2022年第3期16-20,共5页Journal of Xi’an University of Posts and Telecommunications

基　　金：国家自然科学基金项目(12102341);陕西省教育厅专项科研计划项目(21JK0904)。

摘　　要：对求解大规模高维数据集的最小闭包球问题进行研究。基于机器学习中训练支持向量机的序列最小优化(Sequential Minimal Optimization,SMO)算法,提出一种近似计算最小闭包球的二阶SMO-型算法。利用Lagrangian对偶函数的二阶泰勒展开式计算新的工作集,每次迭代只更新工作集所对应可行解的两个分量,构造新的可行解,并建立二阶SMO-型算法的多项式时间复杂度。数值实验结果表明,对于大规模高维数据集,二阶SMO-型算法比一阶SMO-型算法运行速度更快,尤其结合了加速技术的二阶SMO-型算法计算效率更高。The minimum enclosing ball problem of large-scale high-dimensional datasets is studied.Based on the sequential minimum optimization(SMO)algorithm for training support vector machines in machine learning,a second-order SMO-type algorithm for approximately solving the minimum enclosing ball is designed.The algorithm uses the second-order Taylor expansion of the Lagrangian dual function to calculate a new working set.In each iteration,it only updates two components of the feasible solution corresponding to the working set to construct a new feasible solution.Furthermore,the polynomial time complexity of the second-order SMO-type algorithm is established.Numerical experiment results show that the second-order SMO-type algorithm runs faster than the first-order SMO-type algorithm for large-scale high-dimensional datasets.In particular,the second-order SMO-type algorithm combined with acceleration technology has higher computational efficiency.

关 键 词：机器学习 最小闭包球 二阶序列最小优化型算法 大规模高维数据集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]