咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >IMPROVED CONIC REFORMULATIONS ... 收藏

IMPROVED CONIC REFORMULATIONS FOR <i>K</i>-MEANS CLUSTERING

为聚类的 $K$ 工具的改进圆锥形的重新阐述

作     者:Prasad, Madhushini Narayana Hanasusanto, Grani A. 

作者机构:Univ Texas Austin Grad Program Operat Res & Ind Engn Austin TX 78712 USA 

出 版 物:《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期:2018年第28卷第4期

页      面:3105-3126页

核心收录:

学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基  金:National Science Foundation Directorate For Engineering Div Of Electrical, Commun & Cyber Sys Funding Source: National Science Foundation 

主  题:semidefinite programming K-means conic programming copositive programming 

摘      要:In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing schemes, our proposed SDP formulation gives rise to solutions that can be leveraged to identify the clusters. We devise a new approximation algorithm for K-means clustering that utilizes the improved formulation and empirically illustrate its superiority over the state-of-the-art solution schemes.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分