带惩罚的相同容量k-均值问题的局部搜索算法

作     者：剧嘉琛 刘茜 张昭 周洋 JU Jiachen;LIU Qian;ZHANG Zhao;ZHOU Yang

作者机构：北京工业大学数学学院运筹学与信息工程系 山东师范大学数学与统计学院 浙江师范大学数学与计算机科学学院 

基　　金：国家自然科学基金(No.12131003) 山东省自然科学基金(Nos.ZR2020MA029,ZR2021MA100) 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2022年第26卷第1期

页      码：113-124页

摘      要：经典k-均值问题是一类应用广泛的聚类问题,它是指给定R^(d)中观测点集合D和整数k,目的是在空间中寻找k个点作为中心集合S,使得集合D中的每个观测点到S中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典k-均值问题有很多推广,本文研究的带惩罚的相同容量k-均值问题就是其中之一。与经典k-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接U个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取(3+α)k个中心的情况下,可以达到β-近似,其中,参数α>34,β>α+34/α-34。

主 题 词：k-均值问题 惩罚 相同容量 双准则 局部搜索 近似算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.15960/j.cnki.issn.1007-6093.2022.01.008

馆 藏 号：203108475...