An Interior Point Algorithm for Minimum Sum-of-Squares Clustering
An Interior Point Algorithm for Minimum Sum-of-Squares Clustering
复制标题
最小平方和聚类的内点算法
DOI：
10.1137/s1064827597328327
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
N. Mladenović
中科院分区：
文献类型：
--
作者：
O. D. Merle;P. Hansen;B. Jaumard;N. Mladenović
提出了一种最小平方和非层次聚类的精确算法，用于将来自欧几里德m空间的给定点集划分为给定数目的簇，以便最小化从所有点到它们所属的簇的质心的平方距离之和。这个问题被表示为一个0-1变量的约束双曲规划。该解析方法结合了内点算法，一种加权解析中心列生成方法，带有分支定界。确定进入列的辅助问题（即，Oracle）是具有二次分子和线性分母的0-1变量的无约束双曲规划。它通过一系列0-1变量的无约束二次规划来求解。为了加快求解速度，使用可变邻域搜索算法来获得良好的初始解，并在未达到全局最优的情况下快速求解辅助问题。估计的双重变量的界限推导出的启发式解决方案，并在决议过程中作为一个信赖域。证明最小平方和分区确定的第一次几个相当大的数据集，从文献中，包括费舍尔的150虹膜。
An exact algorithm is proposed for minimum sum-of-squares nonhierarchical clustering, i.e., for partitioning a given set of points from a Euclidean m-space into a given number of clusters in order to minimize the sum of squared distances from all points to the centroid of the cluster to which they belong. This problem is expressed as a constrained hyperbolic program in 0-1 variables. The resolution method combines an interior point algorithm, i.e., a weighted analytic center column generation method, with branch-and-bound. The auxiliary problem of determining the entering column (i.e., the oracle) is an unconstrained hyperbolic program in 0-1 variables with a quadratic numerator and linear denominator. It is solved through a sequence of unconstrained quadratic programs in 0-1 variables. To accelerate resolution, variable neighborhood search heuristics are used both to get a good initial solution and to solve quickly the auxiliary problem as long as global optimality is not reached. Estimated bounds for the dual variables are deduced from the heuristic solution and used in the resolution process as a trust region. Proved minimum sum-of-squares partitions are determined for the first time for several fairly large data sets from the literature, including Fisher's 150 iris.