带惩罚μ-相似Bregman散度k-均值问题的初始化算法  

The seeding algorithm for μ-similar Bregman divergences k-means problem with penalties

作　　者：刘文杰 张冬梅[1] 张鹏 邹娟[3] LIU Wenjie;ZHANG Dongmei;ZHANG Peng;ZOU Juan(School of Computer Science and Technol-ogy,Shandong Jianzhu University,Jinan 250101,Shandong,China;School of Software,Shandong University,Jinan 250101,Shandong,China;School of Mathematical Sciences,Qufu Normal University,Qufu 273165,Shandong,China)

机构地区：[1]山东建筑大学计算机科学与技术学院 [2]山东大学软件学院 [3]曲阜师范大学数学科学学院

出　　处：《运筹学学报》2022年第1期99-112,共14页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11871081,61972228,11801310);山东省自然科学基金(No.ZR2021MF006)。

摘　　要：k-均值问题是聚类中的经典问题,亦是NP-难问题。如果允许数据点不聚类,而是支付惩罚费用,则引出带惩罚的k-均值问题。本文将带惩罚的k-均值问题从欧氏距离推广到更一般的μ-相似Bregman散度,研究了带惩罚μ-相似Bregman散度k-均值问题的初始化算法。本文给出的初始化算法,近似比与μ和数据点惩罚最大值与最小值的比例r相关。The k-means problem is a classic NP-hard problem in clustering analysis.If some data points are allowed not to be clustered but to pay some penalty,the k-means problem with penalty is induced.In this paper,we extend the k-means problem with penalty from Euclidean distance to the more general μ-similar Bregman divergences,and study the initialization algorithm for the μ-similar Bregman divergences k-means problem with penalty.The seeding algorithm is given where the approximation ratio is only related to μ and the ratio of the maximum value to the minimum value of the data point penalty.

关 键 词：近似算法 K-均值 惩罚 μ-相似Bregman散度 初始化算法 

分 类 号：O221.7[理学—运筹学与控制论]