基于积极集策略的最小闭包球问题算法研究

计算机科学 ›› 2013, Vol. 40 ›› Issue (9): 234-236.

基于积极集策略的最小闭包球问题算法研究

丛伟杰,刘红卫

西安邮电大学理学院西安710121;西安电子科技大学理学院西安710071

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(61072144,7),陕西省教育厅专项科研基金项目(12JK0735),西安邮电大学博士科研启动基金项目(1051203)资助

Study on Algorithm of Minimum Enclosing Ball Problem Based on Active Set Strategy

CONG Wei-jie and LIU Hong-wei

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法。对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε)。然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点。将该策略结合到提出的算法中,得到一个基于积极集策略的算法。最后,实验结果表明基于积极集策略的算法能够快速、有效地求解mn的大规模数据集的近似最小闭包球。

关键词: 最小闭包球,核心集,积极集策略,大规模数据集中图法分类号TP301.6文献标识码A

Abstract: Firstly,based on computing two furthest points from the current center at each iteration,a(1+ε)- approximation algorithm was proposed for solving the minimum enclosing ball problem of m points in n dimensions．The algorithm returns a core set of size O(1/ε)and achieves an O(mn/ε)time complexity for a given ε∈(0,1)．Secondly,an active set strategy was presented,which computes N furthest points from the current center at each iteration．By incorporating this strategy into the proposed algorithm,an algorithm based on active set strategy was obtained．Finally,the experiment results show that the algorithm based on active set strategy can quickly and effectively solve approximate minimum enclosing ball of the large-scale date sets with mn.

Key words: Minimum enclosing ball,Core set,Active set strategy,Large-scale date sets

丛伟杰,刘红卫. 基于积极集策略的最小闭包球问题算法研究[J]. 计算机科学, 2013, 40(9): 234-236. https://doi.org/

CONG Wei-jie and LIU Hong-wei. Study on Algorithm of Minimum Enclosing Ball Problem Based on Active Set Strategy[J]. Computer Science, 2013, 40(9): 234-236. https://doi.org/

参考文献

[1] Ben-Hur A,Horn D,Siegelmann H T,et al．Support vector clustering [J]．Journal of Machine Learning Research,2001,2(12):125-137
[2] 来疆亮,王守觉．最小球覆盖几何算法及其在模式识别中的应用[J]．模式识别与人工智能,2006,19(2):271-276
[3] Tsang I W,Kwok J T,Cheung P-M．Core Vector machines:Fast SVM training on very large date sets [J]．Journal of Machine Learning Research,2005,6(4):363-392
[4] 艾青,赵骥,秦玉平．基于最大间隔最小体积超球支持向量机的多主题分类算法[J]．计算机科学,2012,39(8):237-238,267 (下转第253页)(上接第236页)
[5] Badoiu M,Har-Peled S,Indyk P．Approximate clustering viacore-sets [C]∥Proceedings of the 34^th Annual ACM Sympo-sium on Theory of Computing．2002:250-257
[6] Badoiu M,Clarkson K L．Smaller core-sets for balls [C]∥Proceedings of the 14^th Annual ACM-SIAM Symposium on Discrete Algorithms．2003:801-802
[7] Badoiu M,Clarkson K L．Optimal core-sets for balls [J]．Computational Geometry:Theory and Applications,2008,40(1):14-22
[8] Kumar P,Mitchell J S B,Ylldlrlm E A．Approximate minimum enclosing balls in high dimensions using core- sets [J]．The ACM Journal of Experimental Algorithmics,2003,8(1)
[9] Fischer K,Gartner B．The smallest enclosing ball of balls:Combinatorial structure and algorithms [J]．International Journal of Computational Geometry and Applications,2004,14:341-378
[10] Zhou G,Toh K C,Sun J．Efficient algorithms for the smallest enclosing ball problem [J]．Computational Optimization and Applications,2005,30:147-160
[11] Pan S H,Li X S．An efficient algorithm for the smallest enclosing ball problem in high dimensions [J]．Applied Mathematics and Computation,2006,172:49-61
[12] Ylldlrlm E A．Two algorithms for the minimum enclosing ball problem [J]．SIAM Journal on Optimization,2008,19(3):1368-1391
[13] 丛伟杰,刘红卫．求解最小闭包球问题的一种SMO-型方法[J]．西北大学学报:自然科学版,2010,40(6):965-969
[14] Frank M,Wolfe P．An algorithm for quadratic programming[J]．Naval Research Logistics Quarterly,1956,3(1/2):95-110
[15] Guelat J,Marcotte P．Some comments on Wolfe’s away steps [J]．Mathematical Programming,1986,35(1):110-119
[16] Chen P H,Fan R E,Lin C J．A study on SMO-type decomposition methods for support vector machines [J]．IEEE Transactions on Neural Networks,2006,17:893-908

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed