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

对高维大规模数据集的近似最小闭包球(Minimum Enclosing Ball,MEB)问题进行研究,提出一种基于二阶远离步的积极集最小闭包球算法。首先,基于对偶目标函数的二阶泰勒展开选择远离步指标,给出求解MEB问题的二阶远离步算法,并计算算法的多项式时间复杂度。然后,进一步设计一个改进的积极集算法计算高维大规模数据集的近似MEB,算法每次迭代选取距离球心较远的数据点构造积极集,并调用二阶远离步算法求解。数值实验结果表明,所提算法能够快速有效地处理高维大规模数据集的高精度近似MEB问题。

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

对求解大规模高维数据集的最小闭包球问题进行研究。基于机器学习中训练支持向量机的序列最小优化(Sequential Minimal Optimization,SMO)算法,提出一种近似计算最小闭包球的二阶SMO-型算法。利用Lagrangian对偶函数的二阶泰勒展开式计算新的工作集,每次迭代只更新工作集所对应可行解的两个分量,构造新的可行解,并建立二阶SMO-型算法的多项式时间复杂度。数值实验结果表明,对于大规模高维数据集,二阶SMO-型算法比一阶SMO-型算法运行速度更快,尤其结合了加速技术的二阶SMO-型算法计算效率更高。