大规模数据集聚类方法研究及应用

论文摘要

聚类问题一直是模式识别领域的热点课题,很多聚类方法纷纷涌现。这些方法大多在适合自身特点的小规模数据集上表现出优良的性能,但在大规模数据集上往往收效甚微,甚至无法运行。针对大规模数据环境下聚类问题的这种困境,本课题进行了相关研究,并先后提出了四种适用于大规模数据集的聚类方法和一个基础理论,分述如下:第二章给基于图论的松弛聚类算法GRC的目标表达式引入约束条件和一次优化项后首先提出约束型图论松弛聚类算法CGRC,又CGRC可视作一个中心约束型最小包含球问题,于是使用基于核心集的最小包含球快速估计技术进而提出了快速图论松弛聚类算法FGRC,渐进时间复杂度与样本容量呈线性关系是FGRC的最大优点。概率密度估计是模式识别领域的基础研究之一,很多后续工作都基于它而展开。本文第三章提出快速自适应相似度聚类方法FASCM和第四章提出快速均值漂移谱聚类算法FMSSC都是如此,它们均以快速压缩集密度估计器FRSDE为基础而展开。第三章首先证明相似度聚类方法SCM的相似度度量函数相当于一个基于高斯密度核的概率密度估计函数,于是利用FRSDE可以快速地得到具有稀疏权系数形式的相似度函数,从而大大降低了SCM中SCA过程的计算开销。接着使用图论松弛聚类技术代替层次聚类过程,使算法具有了自适应能力,摆脱了人工经验的依赖增强了实用性。这就是FASCM的主要思想。第四章指出原均值漂移谱聚类算法MSSC繁重计算开销的根源是使用了Parzen窗密度估计式。为此该章重新设计了MSSC的架构,以FRSDE取代其PW,以本文第二章提出的CGRC算法代替其简单模式合并方法,从而提出了快速均值漂移谱聚类FMSSC算法。FMSSC较MSSC显著提高了实用性,其总体时间复杂度与样本容量近似呈线性关系。第五章推导了图论松弛聚类算法GRC的目标表达式可表示成“PW加权和+平方熵”的形式,因此GRC也可看作一个KDE问题。于是利用KDE近似定理提出了基于KDE近似的大规模数据集图论松弛聚类SUGRC-KDEA新方法。SUGRC-KDEA的关键抽样容量要适量,为此该章同步提出了基于超球分割的随机抽样算法HSBRS。HSBRS既保证抽样子集容量合适又保证能较好地反映原数据集的数据分布规律。第六章提出了一个基础性理论:快速核密度估计定理。该章利用柯西-许瓦茨不等式证明了基于抽样子集的KDE和基于完整数据集的KDE的误差上限仅与抽样容量和核参数相关,与其它因素无关。即只要抽样容量和核窗宽合适,可以用抽样子集代替原数据集进行核密度估计。该定理的得出为所有基于数据抽样的模式识别方法或技术提供了新的理论支撑。本课题的所有研究均属于此范畴。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景
• 1.2 课题目标和意义
• 1.3 课题主要研究内容、特色和创新
• 第二章 基于最小包含球的大规模数据集快速谱聚类算法
• 2.1 引言
• 2.2 相关理论和技术
• 2.2.1 Normalized Cuts
• 2.2.2 基于图论的松弛聚类算法
• 2.2.3 MEB 和CCMEB
• 2.2.4 基于Core-set 的MEB 快速逼近技术
• 2.3 快速基于图论的松弛聚类算法
• 2.3.1 约束型GRC
• 2.3.2 约束型GRC 与最小包含球问题之间的联系
• 2.3.3 快速基于图论的松弛聚类算法
• 2.4 实验结果及分析
• 2.4.1 人造数据集实验
• 2.4.2 真实数据集实验
• 2.5 本章小结
• 第三章 基于稀疏Parzen 窗的快速自适应相似度聚类方法
• 3.1 引言
• 3.2 相关理论或方法
• 3.2.1 基于相似度的聚类方法SCM
• 3.2.2 快速压缩集密度估计器
• 3.3 快速自适应相似度聚类方法
• 3.3.1 SCM 和核密度估计问题之间的联系
• 3.3.2 FASCM
• 3.3.3 FASCM 时间复杂度分析
• 3.3.4 FASCM 与SCM 的比较
• 3.4 实验结果及分析
• 3.4.1 人造数据集上的实验
• 3.4.2 图像分割实验
• 3.5 本章小结
• 第四章 快速均值漂移谱聚类算法
• 4.1 引言
• 4.2 均值漂移谱聚类
• 4.3 快速均值漂移谱聚类算法
• 4.3.1 FMSSC 的架构实现
• 4.3.2 关于FMSSC 的几点说明
• 4.3.3 FMSSC 时间复杂度分析
• 4.4 实验结果及分析
• 4.4.1 人造数据环境实验
• 4.4.2 FMSSC 在图像分割中的应用
• 4.5 本章小结
• 第五章 基于KDE 近似的大规模图论松弛聚类方法
• 5.1 引言
• 5.2 基于KDE 近似的快速数据压缩方法
• 5.3 基于KDE 近似的大规模图论松弛聚类方法
• 5.3.1 GRC 和KDE 之间的联系
• 5.3.2 SUGRC-KDEA
• 5.3.3 SUGRC-KDEA 时间开销分析
• 5.4 实验结果及分析
• 5.4.1 人造大规模数据集
• 5.4.2 真实大规模数据集实验
• 5.5 本章小结
• 第六章 快速核密度估计定理
• 6.1 引言
• 6.2 快速核密度估计定理
• 6.2.1 定理1
• 6.2.2 定理2
• 6.2.3 定理3
• 6.3 本章小结
• 第七章 结束语
• 致谢
• 参考文献
• 附录1：作者在攻读博士学位期间发表的论文
• 附录2：攻读博士学位期间参加的科研项目列表