数据流模型下k-means聚类核心集的算法

发布时间：2021-11-22 18:40

　　聚类是将给定的集合按照某种特征进行分类的过程,其应用于各个领域,为各行业的发展提供便利,具有极高的实用价值。按照分类方法的不同,聚类可以分为很多种,但其中应用最广的是fk-means聚类。fk-means聚类问题可以表述为:给定Rd上含有n个点的集合P和一个整数fk,目标是在Rd上找出fk个中心点,使得P中每个点到距它最近的中心点的距离的平方和最小。不同于一般的fk-meams聚类问题,在数据流模型下的fk-means聚类问题中,集合P中的点是随时间依次到达的,且数据量极其庞大没有足够的空间来存储全部的数据点。因此,为了解决该模型下的fk-means聚类问题,我们引入了核心集这一概念,较原始集合P而言,核心集规模更小,更便于储存,并且在所求得的核心集上进行聚类得到的解与在原始集合P上聚类得到的解之间的相对误差可以任意小。然而,fk-means聚类问题是NP-难问题,在P≠NP的假设下,不存在多项式时间的精确算法。因此,本文首先考虑了 fk-means聚类问题所得解为近似解时,如何计算原始集合的核心集。我们发现在近似解的情况下,无法找到满足定义的真正的核心集,但可以得到带有微小误差的近似... 

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

【文章页数】：38 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景以及研究意义
    1.2 国内外研究现状
    1.3 k-means聚类
    1.4 预备知识
    1.5 论文结构
第2章 k-means聚类的(k,ε)-核心集构建算法
    2.1 算法介绍
    2.2 算法及主要结论
    2.3 算法分析
    2.4 本章小结
第3章 k-means聚类的ξ-近似(k,ε)-核心集构建算法
    3.1 算法介绍
    3.2 算法及主要结论
    3.3 算法分析
    3.4 本章小结
结论
参考文献
致谢


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



本文编号：3512246