A balanced k-means algorithm for weighted point sets
A balanced k-means algorithm for weighted point sets
复制标题
加权点集的平衡 k 均值算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Gritzmann
中科院分区：
文献类型：
--
作者：
S. Borgwardt;A. Brieden;P. Gritzmann
将RD中的n个点划分为k个子集的经典k-Means算法是科学和商业应用中最流行和最广泛的聚类方法之一。本文给出了一个能够处理加权点集的推广，并给出了簇大小的上下界。新算法通过计算加权平衡的最小二乘分配来代替k-均值的分配步骤。这被建模为权重平衡的划分多面体上的线性规划，其最优顶点对应于允许强可行的功率图的计算。利用这种对应关系，我们得到了运算次数的最坏情况的上界n O(Dk)。这类似于k-均值的已知上界，固定k和d的多项式，并且考虑到k-均值的已知复杂性结果，基本上是人们所能期望的最好结果。此外，我们还展示了我们方法的可核化能力。
The classical k-means algorithm for paritioning n points in R d into k sub- sets is one of the most popular and widely spread clustering methods in scientific and business applications. The present paper gives a generalization that is capable of handling weighted point sets and prescribed lower and upper bounds on the cluster sizes. The new algorithm replaces the assignment step of k-means by the computation of a weight-balanced least-squares assignment. This is modelled as a linear program over a weight-balanced partition polytope whose optimal vertices correspond to clus- terings that allow strongly feasible power diagrams. We use this correspondence to derive a worst-case upper bound n O(dk) for the number of operations. This is similar to the known upper bound for k-means, polynomial for fixed k and d, and in view of the known complexity results for k-means, essentially the best one can expect. Further, we show the kernelizability of our approach.
影响因子：
1.6
作者：
A. Alpers;A. Brieden;P. Gritzmann;A. Lyckegaard;H. F. Poulsen
通讯作者：
H. F. Poulsen