带惩罚的κ-平均问题的有效并行初始化算法

发布时间：2021-11-09 11:43

　　K-平均问题是经典的NP-难问题,NP-难问题无法在多项式时间内找到精确解除非P=NP.k-平均问题在数据挖掘、机器学习等领域有广泛的应用.在大数据时代,与大数据相关的聚类问题也成为当前研究的热点.我们通常采用启发式算法或近似算法求解该类问题.在该问题中,给定由n个d维空间中观测点组成的数据集χ和整数k（k≤n）,目标是将χ划分成k个子集,使得所有子集的方差（或点到其聚类中心的距离平方）和最小.在χ中观测点有不同的重要程度,为了将重要的观测点更好聚类,学者们提出了带惩罚的k-平均问题.在该问题中,越重要的观测点给定惩罚费用越大.带惩罚的k-平均问题是k-平均问题的推广.任意一个观测点x∈χ尤的惩罚费用为p（x）.每个观测点必须聚类到某个中心点或者被惩罚.在本文中,我们研究了带惩罚的kk-平均问题,给出了并行初始化算法,每次迭代采样点的数量是随机的,在给定迭代次数的情形下,给出了算法的近似比分析. 

【文章来源】：北京工业大学北京市 211工程院校

【文章页数】：35 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景以及研究意义
    1.2 国内外研究现状
    1.3 预备知识
    1.4 主要结果
    1.5 论文结构
第2章 带惩罚的k-平均问题有效并行初始化算法
    2.1 k-means++算法
        2.1.1 算法介绍
        2.1.2 算法
    2.2 k-means||算法
        2.2.1 算法介绍
        2.2.2 算法
        2.2.3 算法分析
    2.3 带惩罚的k-means||算法
        2.3.1 算法介绍
        2.3.2 算法
        2.3.3 算法分析
    2.4 本章小结
结论
参考文献
致谢


【参考文献】：
期刊论文
[1]k-平均问题及其变形的算法综述[J]. 徐大川,许宜诚,张冬梅.  运筹学学报. 2017(02)



本文编号：3485266