基于二阶远离步的积极集最小闭包球算法
An active-set minimum enclosing ball algorithm based on second-order away-step
丛伟杰 1安梦园 2李承臻2
作者信息
- 1. 西安邮电大学理学院,陕西西安 710121
- 2. 西安邮电大学计算机学院,陕西西安 710121
- 折叠
摘要
对高维大规模数据集的近似最小闭包球(Minimum Enclosing Ball,MEB)问题进行研究,提出一种基于二阶远离步的积极集最小闭包球算法.首先,基于对偶目标函数的二阶泰勒展开选择远离步指标,给出求解MEB问题的二阶远离步算法,并计算算法的多项式时间复杂度.然后,进一步设计一个改进的积极集算法计算高维大规模数据集的近似MEB,算法每次迭代选取距离球心较远的数据点构造积极集,并调用二阶远离步算法求解.数值实验结果表明,所提算法能够快速有效地处理高维大规模数据集的高精度近似MEB问题.
Abstract
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 ob-jective 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 ac-tive-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 ac-tive-set at each iteration,and calls the second-order away-step algorithm.Numerical experiments re-sult show that the proposed algorithm can quickly and efficiently deal with the high-precision ap-proximate MEB problem of the high-dimensional large-scale datasets.
关键词
机器学习/最小闭包球/高维大规模数据集/远离步/积极集算法Key words
machine learning/minimum enclosing ball/high-dimensional large-scale datasets/away-step/active-set algorithm引用本文复制引用
基金项目
国家自然科学基金项目(12102341)
陕西省自然科学基础研究计划项目(2024JC-YBQN-0052)
出版年
2024
NETL
NSTL
万方数据