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

基于最小生成树变种的半监督聚类算法研究

作　者: 霍萌萌
导　师: 陈晓云
学　校: 兰州大学
专　业: 计算机软件与理论
关键词: 数据挖掘半监督聚类标签传播最小生成树网格
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 46次
引　用: 0次
阅　读: 论文下载

内容摘要

半监督聚类是近几年模式识别和机器学习领域的一个新的热点研究问题,也是数据挖掘的一个重要分支。半监督聚类算法结合了完全标记信息的监督的分类分析方法和完全无监督信息的聚类分析方法的优点,使用少量已标签数据集来帮助聚类,从而显著改进无监督聚类的质量。尽管与监督学习相比,半监督学习需要的标签数据已经有所减少,但是现有的半监督聚类学习算法仍然需要一定数量的标签数据来保证聚类结果的准确性。由于现实生活中标签数据的不易获得,可以使用的标签数据较少,这成为半监督算法的一个局限性,严重影响了半监督聚类的性能。同时,对于多密度和形状不规则的簇,由于边界点数据难以检测,大多数聚类算法不能得到很好的聚类效果。本文使用极少量已知标签数据来帮助算法改进聚类质量。文中提出了三个基于最小生成树变种的聚类算法,分别为K-SSMST,M-SSMST和GSSMST。三个算法都能够使用极少量标签数据对象聚类密度不均匀和形状不规则的簇。K-SSMST基于最小生成树变种算法K-MST进行标签扩展。算法只需要K个已标签数据点,不需要任何参数就能完成自然聚类。M-SSMST在给定已知信息不足的情况下,能够完成发现新类的功能。GSSMST算法解决了由于使用最小生成树算法造成的时间复杂度高的问题。采用多个数据集对算法进行测试,实验结果证明算法可以得到理想的聚类结果。

全文目录

摘要  3-4
Abstract  4-8
第一章绪论  8-13
  1.1 研究背景与意义  8-9
  1.2 研究现状  9-11
  1.3 论文的研究内容和主要工作  11-12
    1.3.1 论文的研究内容  11
    1.3.2 论文的主要工作  11-12
  1.4 论文的组织结构  12-13
第二章聚类分析和半监督聚类分析概述  13-20
  2.1 聚类分析  13-18
    2.1.1 聚类分析的概念  13
    2.1.2 距离与相似度度量  13-15
    2.1.3 主要的聚类算法  15-18
  2.2 半监督聚类分析  18-19
    2.2.1 半监督聚类的概念  18-19
    2.2.2 半监督聚类算法  19
  2.3 本章小结  19-20
第三章 K-SSMST算法  20-31
  3.1 最小生成树变种算法  20-22
    3.1.1 最小生成树算法  20-22
    3.1.2 最小生成树变种算法：K-MST  22
  3.2 K-SSMST算法描述  22-23
  3.3 K-SSMST算法设计与实现  23-25
    3.3.1 K-SSMST算法流程图  23
    3.3.2 数据预处理  23-24
    3.3.3 标签数据集选取  24
    3.3.4 计算距离矩阵  24
    3.3.5 聚类过程  24-25
  3.4 K-SSMST算法性能分析  25
  3.5 K-SSMST算法实验结果与性能评价  25-30
    3.5.1 实验环境  25-26
    3.5.2 测试数据集  26-27
    3.5.3 实验结果评价标准  27-28
    3.5.4 聚类精确度分析  28-30
  3.6 本章小结  30-31
第四章 M-SSMST算法  31-43
  4.1 M-SSMST算法的相关概念  31-33
  4.2 M-SSMST算法描述  33
  4.3 M-SSMST算法设计与实现  33-38
    4.3.1 M-SSMST算法流程图  33
    4.3.2 标签数据集选取  33
    4.3.3 M-SSMST算法聚类过程  33-36
    4.3.4 检测边界点  36
    4.3.5 发现孤立点  36
    4.3.6 M-SSMST算法示例  36-38
  4.4 M-SSMST算法性能分析  38
  4.5 M-SSMST算法实验结果及性能评价  38-42
    4.5.1 实验环境  38-39
    4.5.2 实验数据集选取  39
    4.5.3 实验结果评价标准  39
    4.5.4 聚类精确度分析  39-42
  4.6 本章小结  42-43
第五章 GSSMST算法  43-49
  5.1 GSSMST算法的相关概念  43
  5.2 GSSMST算法描述  43-44
  5.3 GSSMST算法设计与实现  44-46
    5.3.1 GSSMST算法流程图  44
    5.3.2 数据标准化  44
    5.3.3 划分网格  44
    5.3.4 聚类过程  44-46
  5.4 GSSMST算法性能分析  46
  5.5 实验与分析  46-48
    5.5.1 实验环境  46
    5.5.2 实验结果评价标准  46
    5.5.3 聚类精确度对比实验  46-47
    5.5.5 聚类执行效率对比实验  47-48
  5.6 本章小结  48-49
第六章总结与展望  49-51
  6.1 全文工作总结  49-50
  6.2 工作展望  50-51
参考文献  51-54
在学期间的研究成果  54-55
致谢  55

基于最小生成树变种的半监督聚类算法研究

内容摘要

全文目录

相似论文