基于二阶远离步的积极集最小闭包球算法  

An active-set minimum enclosing ball algorithm based on second-order away-step

作　　者：丛伟杰 安梦园 李承臻 CONG Weijie;AN Mengyuan;LI Chengzhen(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

出　　处：《西安邮电大学学报》2024年第3期83-89,共7页Journal of Xi’an University of Posts and Telecommunications

基　　金：国家自然科学基金项目(12102341);陕西省自然科学基础研究计划项目(2024JC-YBQN-0052)。

摘　　要：对高维大规模数据集的近似最小闭包球(Minimum Enclosing Ball,MEB)问题进行研究,提出一种基于二阶远离步的积极集最小闭包球算法。首先,基于对偶目标函数的二阶泰勒展开选择远离步指标,给出求解MEB问题的二阶远离步算法,并计算算法的多项式时间复杂度。然后,进一步设计一个改进的积极集算法计算高维大规模数据集的近似MEB,算法每次迭代选取距离球心较远的数据点构造积极集,并调用二阶远离步算法求解。数值实验结果表明,所提算法能够快速有效地处理高维大规模数据集的高精度近似MEB问题。The approximate minimum enclosing ball(MEB)problem of high-dimensional large-scale data sets is studied.An active-set MEB algorithm based on the second-order away-step is proposed.Firstly,the away-step index is selected based on the second-order Taylor expansion of the dual objective function,the second-order away-step algorithm for solving the MEB problem is presented.The polynomial time complexity of the proposed algorithm is established.Then an improved fast active-set algorithm is further designed to compute the approximate MEB for high-dimensional large-scale datasets.The algorithm selects data points far from the center of the ball to construct an active-set at each iteration,and calls the second-order away-step algorithm.Numerical experiments result show that the proposed algorithm can quickly and efficiently deal with the high-precision approximate MEB problem of the high-dimensional large-scale datasets.

关 键 词：机器学习 最小闭包球 高维大规模数据集 远离步 积极集算法 

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