基于先验知识的半监督聚类算法研究

论文摘要

聚类是数据挖掘中一种常用的方法,在实际应用和学术研究中常用来进行数据分析及数据的类别划分。半监督聚类作为聚类分析的一个重要分支,在近十年来,受到了广泛的关注。半监督聚类利用少量的先验知识,协助聚类分析,提高聚类的准确率或效率。半监督聚类中先验知识的表现形式多样,主要包括数据的类别标签信息(标注数据)和数据对的类别异同信息(约束对数据)。先验知识在数据集中的分布不同,在聚类过程中的作用也不一样,甚至可能对聚类产生消极影响,降低聚类的准确度。本文通过对先验知识的重要性进行评价,并根据先验知识重要性的不同,采取不同的处理方式,更好地利用先验知识,提高半监督聚类的准确性。针对不同的先验知识,本文主要进行以下研究：(1)本文首先分析标注数据降低聚类准确度的原因,提出基于标注数据的改进半监督聚类算法。本文提出的改进方法首先分析标注数据的重要性,然后针对性地利用标注数据协助聚类初始化和聚类过程,分别为LDP初始化方法和双向选择调整策略。LDP方法采用改进的相似度计算方法和标签繁殖方法,优化初始聚类种子。双向选择调整策略通过标注数据和未标注数据的相互选择,提高标签繁殖的准确率,并在聚类解搜索过程中,动态调整标注数据的作用强度。(2)通过分析不同的约束对数据在半监督聚类中的作用,本文提出基于约束对数据的改进半监督聚类算法。本文提出的改进方法首先引入“团”(表示为Clique)的概念,由分散的约束对数据形成团,然后分析团的重要性,并通过势能作用和反馈作用利用团,优化聚类解的搜索。势能作用采用改进的约束违反惩罚函数和约束繁殖的方法增强重要约束在聚类过程中的强度,改善聚类的搜索路径。依据聚类过程中团约束违反的情况,反馈作用对团所在类簇拆分或合并,改善聚类解的搜索。本文采用多个数据集对算法的有效性进行实验验证,并分析实验结果的合理性。实验结果表明,结合先验知识重要性的半监督聚类算法,能够降低先验知识对算法的消极作用,优化聚类解的搜索,提高聚类的准确度和稳定性。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 课题研究背景及意义
• 1.2 半监督聚类研究现状
• 1.3 本文主要研究内容
• 2 半监督聚类方法概述
• 2.1 半监督聚类
• 2.1.1 相似性度量准则
• 2.1.2 基于距离学习的半监督聚类算法
• 2.1.3 基于优化准则的半监督聚类算法
• 2.2 算法验证数据
• 2.2.1 UCI数据集
• 2.2.2 文本数据集
• 2.2.3 数据分布分析
• 2.3 算法评价指标
• 2.3.1 Rand与Jaccard指标
• 2.3.2 F-measure指标
• 2.3.3 e指标
• 2.3.4 NMI指标
• 2.3.5 Wave指标
• 2.4 本章小结
• 3 基于标注数据的改进半监督聚类算法
• 3.1 研究思路
• 3.1.1 标注数据的消极作用
• 3.1.2 改进方法
• 3.2 标注数据重要性评价
• 3.3 半监督聚类初始化优化方法
• 3.3.1 初始化的重要性
• 3.3.2 初始化优化方法
• 3.4 半监督双向选择方法
• 3.4.1 问题描述
• 3.4.2 半监督双向选择策略
• 3.4.3 半监督双向选择聚类算法
• 3.5 实验结果与讨论
• 3.5.1 实验方案
• 3.5.2 结果与分析
• 3.6 本章小结
• 4 基于约束对数据的改进半监督聚类算法
• 4.1 研究思路
• 4.1.1 约束对数据与标注数据的比较
• 4.1.2 约束对数据的消极作用
• 4.1.3 算法改进方法
• 4.2 基于约束对的Clique建模
• 4.2.1 Clique的生成
• 4.2.2 Clique的重要性度量
• 4.2.3 Clique的势能作用
• 4.2.4 Clique的反馈作用
• 4.3 结合Clique的半监督聚类算法
• 4.3.1 竞争凝聚聚类算法
• 4.3.2 结合Clique的半监督竞争凝聚聚类算法
• 4.4 实验结果与讨论
• 4.4.1 实验方案
• 4.4.2 结果与分析
• 4.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文及项目参加情况
• 致谢