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

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

对高维大规模数据集的近似最小闭包球(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.