学位论文 > 优秀研究生学位论文题录展示

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

作　者: 钱鹏江
导　师: 王士同
学　校: 江南大学
专　业: 轻工信息技术与工程
关键词: 聚类大规模数据集时间复杂度谱聚类相似度聚类均值漂移核密度估计最小包含球 Parzen窗压缩集密度估计
分类号: TP391.41
类　型: 博士论文
年　份: 2011年
下　载: 337次
引　用: 1次
阅　读: 论文下载

内容摘要

聚类问题一直是模式识别领域的热点课题,很多聚类方法纷纷涌现。这些方法大多在适合自身特点的小规模数据集上表现出优良的性能,但在大规模数据集上往往收效甚微,甚至无法运行。针对大规模数据环境下聚类问题的这种困境,本课题进行了相关研究,并先后提出了四种适用于大规模数据集的聚类方法和一个基础理论,分述如下:第二章给基于图论的松弛聚类算法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的误差上限仅与抽样容量和核参数相关,与其它因素无关。即只要抽样容量和核窗宽合适,可以用抽样子集代替原数据集进行核密度估计。该定理的得出为所有基于数据抽样的模式识别方法或技术提供了新的理论支撑。本课题的所有研究均属于此范畴。

全文目录

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

相似论文

基于熵的音乐声纹检索算法的研究与实现,TP391.3
基于Parzen窗估计与Renyi\'s熵的动态随机系统输出分布控制研究,TP13
基于类Harr特征和最小包含球的纸币识别方法的研究,TP391.41
Copula-EGARCH-核密度模型研究及应用,O211.3
我国信息消费与经济增长关系及区域差异性分析,F49;F124;F207
随机过程核密度估计的大偏差,O211.6
模糊支持向量机算法研究,O159
动态场景中基于背景建模的运动目标检测算法的研究,TP391.41
我国通信设备制造业上市公司效率研究,F272;F426.63
Copula选择及其条件核密度估计,F830
演化数据流的异常检测研究,TP311.13
运动目标检测中减背景技术的若干方法,TP391.41
基于核密度估计的金融市场谱风险度量,F830.9
智能计算方法及其在发酵过程中的应用研究,Q-33
数字图像处理中去噪算法的研究,TP391.41
基于时域分析的旋转机械故障诊断方法研究,TH17
基于投影的聚类算法研究及应用,TP301.6
基于阈值选取的图像分割方法研究,TP391.41
中文扫描印刷体文档中数学公式的特征提取及定位,TP391.41
模式分类中特征降维方法的研究,TP391.4