求解最小闭包球问题改进的SMO-型算法

作者：丛伟杰; 刘红卫

来源：计算机工程与应用, 2013, (03): 1-3+9.

• 最小闭包球
• 确定并删除内部点
• 序列最小最优化
• 线性收敛
• 大规模数据集 Minimum Enclosing Ball(MEB)
• identification and elimination of interior points
• sequential minimal optimization
• linear convergence
• large-scale data sets

研究n维空间中m个点的最小闭包球(MEB)问题。通过结合确定并删除内部点的技术到序列最小最优化(SMO)方法中,提出一种近似求解MEB问题的改进的SMO-型算法。证明了该算法具有线性收敛性。数值结果表明对于一些mn的大规模数据集,改进的算法与原算法相比速度可以提高10倍以上。尤其,当n等于100且m等于100000时,改进的SMO-型算法仅需执行8s。此外,对于n等于10000且m等于1000的大规模数据集,改进的算法也仅需执行150s。

• 单位
  西安电子科技大学; 西安邮电大学