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

基于半监督学习的分布式和演化聚类研究

作　者: 於跃成
导　师: 王建东
学　校: 南京航空航天大学
专　业: 计算机应用技术
关键词: 分布式聚类半监督聚类先验信息并行k-means 高斯混合模型分布式EM 演化聚类时序平滑
分类号: TP311.13
类　型: 博士论文
年　份: 2012年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

传统聚类分析是一种无监督学习方法，聚类过程仅仅使用了无标记数据，忽略了数据集自然存在的各种先验信息。然而，半监督聚类则在使用无标记数据进行聚类分析时，将数据集中的先验信息引入到聚类过程以改善聚类的执行。现有的大多数半监督聚类方法往往假定数据以集中方式存储于一个中心站点，同时隐含假设所处理的样本个数和样本服从的概率分布不会随着时间的推移而发生变化。但是，在数据挖掘的许多实际应用中广泛存在着分布式数据集和动态演变数据集这两种特定的数据形式。在分布式场景下，数据集自然分布于多个站点，受数据安全、数据隐私、通讯代价等因素的限制，站点数据无法集中存储于一个站点。对于动态演变数据，聚类的目的是要产生一个随时间变化的聚类序列，聚类序列中的每一个聚类结果需要同时满足两个标准：对当前时段的数据应当具有较高的聚类质量；与先前时段的聚类结果较为相似。本文的研究工作包括两部分：第一部分重点研究了当数据集合以水平分布方式存储时，使用并行k-means和分布式EM作为基本算法的半监督分布式聚类框架；第二部分则将约束并行k-means和基于约束的分布式EM思想扩展应用于演化数据集，实现了基于约束聚类框架的演化聚类。本文的主要研究成果包括：1、提出了以并行k-means为基本算法的三种分布式半监督聚类框架。(1)启发式分布k-means算法将已有的站点局部聚类结果作为先验信息，其最大优点在于能够改善并行k-means算法对初始中心的依赖。(2)基于约束的并行k-means算法(CPKM)以并行k-means算法为基础，以站点用户提供的成对约束为先验信息，改善了并行k-means收敛于局部最优的缺陷；进而通过使用成对样本的均值中心来估计这些约束样本的簇指派方案，避免了约束样本的簇指派方案依赖于约束样本排列顺序的不足。(3)软约束分布式k-means算法(DBSC)仍然使用成对约束作为先验信息，但是样本间的约束关系为软约束，这意味着允许约束信息中存在错误约束。CPKM通过定义约束违反权重，有差别地处理约束违反，能够有效利用这些约束信息来改善分布式聚类精度。2、将成对约束信息以软约束的形式引入高斯混合模型(GMM)，提出了约束一致高斯混合模型(CCGMM)，并将CCGMM模型进一步扩展为基于约束一致的分布式高斯混合模型(DCCGMM)，以用于分布式数据的半监督聚类。(1)CCGMM模型的主要特点包括：估计参数同时反映了数据的固有分布和用户的先验信息；参数估计的迭代公式有封闭的解析表达式。(2)DCCGMM模型在使用分布式EM作为迭代框架来估计全局模型参数时，只使用了各站点的局部模型参数，站点数据和约束信息仅限于本站点使用。3、通过分析最大化对数似然与标准k-means目标函数的内在关联，以MPCK-MEANS算法为基础，提出了一种在分布式环境下同时进行约束聚类和局部距离学习的半监督分布式聚类框架。4、将先前聚类结果视为当前数据样本的先验信息，提出了两种基于约束聚类方法的演化聚类框架。两种演化聚类框架均以约束违反的形式定义历史代价，以实现聚类序列的时序平滑。(1)基于约束k-means的演化聚类算法(CEKM)以当前时段的簇指派方案下计算得到的簇中心去拟合历史数据，以所有历史数据与当前簇中心之间的距离的和作为总的历史代价。(2)约束演化混合模型(EGMM)以历史数据中具有相同簇标记的成对样本作为约束信息，通过计算这些样本在当前时段的参数模型下后验分布之间的总体差异来调整当前模型的参数估计。

全文目录

摘要  4-6
Abstract  6-13
第一章绪论  13-27
  1.1 研究背景  13-14
  1.2 现有工作回顾  14-22
    1.2.1 传统聚类学习  14-15
    1.2.2 分布式聚类  15-16
    1.2.3 演化聚类  16-17
    1.2.4 半监督聚类  17-20
    1.2.5 聚类过程和聚类评价标准  20-22
  1.3 本文的主要研究工作  22-23
  1.4 本文的内容安排  23-27
第二章分布式约束 K-MEANS 算法  27-51
  2.1 引言  27
  2.2 相关工作  27-31
    2.2.1 k-means 算法  27-28
    2.2.2 Seeded k-means 算法  28-29
    2.2.3 PCC 聚类算法  29
    2.2.4 并行 k-means 算法  29-31
  2.3 基于启发信息的分布式 K-MEANS 算法  31-36
    2.3.1 背景和动机  31-32
    2.3.2 局部簇融合算法  32-34
    2.3.3 启发式分布 k-means 算法  34
    2.3.4 实验与分析  34-36
  2.4 约束并行 K-MEANS 算法  36-44
    2.4.1 背景和动机  36-37
    2.4.2 约束选择和表示  37-38
    2.4.3 目标函数及算法  38-41
    2.4.4 实验分析  41-44
  2.5 软约束分布式 K-MEANS 算法  44-50
    2.5.1 背景和动机  44-45
    2.5.2 约束违反代价  45-46
    2.5.3 目标函数  46-47
    2.5.4 算法描述  47-49
    2.5.5 实验与分析  49-50
  2.6 本章小结  50-51
第三章基于高斯混合模型的分布式约束聚类  51-71
  3.1 引言  51
  3.2 相关工作  51-53
  3.3 约束一致高斯混合模型  53-63
    3.3.1 基于模型的聚类  53-54
    3.3.2 约束一致正则化算子  54-55
    3.3.3 正则化模型拟合  55-61
    3.3.4 实验结果及分析  61-63
  3.4 基于约束一致的分布式高斯混合模型  63-69
    3.4.1 DCCGMM 模型  63-67
    3.4.2 正则化分布式 EM 算法  67-68
    3.4.3 实验结果及分析  68-69
  3.5 本章小结  69-71
第四章基于度量学习的分布式聚类  71-81
  4.1 引言  71-72
  4.2 相关工作  72-74
  4.3 基于度量学习的约束并行 K-MEANS 聚类算法  74-78
    4.3.1 目标函数  74-76
    4.3.2 MPCPK 算法  76-78
  4.4 实验分析  78-80
    4.4.1 人造数据集  78-79
    4.4.2 UCI 数据集  79-80
  4.5 本章小结  80-81
第五章基于约束聚类框架的演化聚类方法研究  81-99
  5.1 引言  81-82
  5.2 符号定义及相关工作  82-85
    5.2.1 符号定义  82
    5.2.2 演化 k-means  82-84
    5.2.3 演化谱聚类  84-85
  5.3 基于约束 K-MEANS 的演化聚类算法  85-91
    5.3.1 聚类质量函数  85
    5.3.2 历史代价函数  85-87
    5.3.3 目标函数  87
    5.3.4 算法  87-89
    5.3.5 实验分析  89-91
  5.4 基于约束一致高斯混合模型的演化聚类  91-96
    5.4.1 聚类质量函数  92
    5.4.2 基于簇标记保持的历史代价函数  92-93
    5.4.3 目标函数  93
    5.4.4 算法  93-95
    5.4.5 实验分析  95-96
  5.5 本章小结  96-99
第六章总结和展望  99-101
  6.1 论文总结  99-100
  6.2 展望  100-101
参考文献  101-113
致谢  113-114
在学期间的研究成果及发表的学术论文  114

基于半监督学习的分布式和演化聚类研究

内容摘要

全文目录

相似论文