基于遗传算法的半监督学习研究

论文摘要

聚类是数据挖掘领域中的一种常用方法,它是通过数据之间的相似程度,把数据集分割成若干簇。传统的聚类没有利用到数据的监督信息,所以被当作是一种无监督的机器学习方法。半监督聚类就是利用数据的监督信息来帮助提升无监督聚类的性能。其中,数据的监督信息包括数据的类标记信息和数据间的成对约束信息（must-link约束和cannot-link约束）。半监督聚类是在无监督聚类中加入监督信息,利用这些监督信息来辅助聚类的学习。如何有效利用数据的监督信息来提升聚类学习的性能,是现今数据挖掘中的一个重要问题。目前,已有很多半监督聚类的有效方法。本文从遗传算法的角度研究半监督聚类方法,主要从两个方面出发,一方面研究在半监督聚类中利用成对约束信息的新方法,一方面研究如何改进现有的基于遗传算法的半监督聚类算法,使遗传算法更好地用于半监督聚类中。本文的主要工作及创新点包括：1、提出了近邻度这个新的概念。每个样本都有一个近邻度,近邻度大,说明该样本附近的样本分布比较稀疏,样本之间的距离比较远；反之,近邻度小,说明该样本附近的样本分布比较密集,样本之间的距离比较近。2、提出了一种在半监督聚类中利用成对约束信息的新方法。凝聚层次聚类（AHC）是层次聚类的一种,它采用自底向上的方式,把原子簇一步步合并起来。但是,AHC算法并没有利用到数据的监督信息,是一种无监督的聚类过程。本文把成对约束信息引入到AHC算法中,利用样本的近邻度,提出了基于成对约束的半监督凝聚层次聚类算法（PS-AHC）. PS-AHC算法利用成对约束来重新调整聚类簇之间的距离,使聚类簇之间的距离更真实,最终影响聚类的结果。实验结果说明了PS-AHC算法可以有效提升聚类性能。3、遗传算法是一种自适应全局优化概率搜索算法,是解决搜索问题的一种通用算法。现有的一种基于遗传算法的半监督聚类算法（LG-SSC）只利用了数据的类标记信息,并未利用数据的成对约束信息。本文提出了基于遗传算法的改进半监督聚类算法（PLG-SSC）,该算法同时利用了数据的类标记信息和成对约束信息,充分利用了数据的监督信息。在该算法中提出了PFDS样本分配方法,该方法充分减少了成对约束的违反个数。实验结果表明PLG-SSC算法能进一步提高聚类的准确率。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题研究的背景和意义
• 1.2 国内外研究现状
• 1.3 本文的主要工作及组织结构
• 第二章 半监督聚类相关知识
• 2.1 数据挖掘技术简介
• 2.1.1 数据挖掘的定义、历史和发展
• 2.1.2 数据挖掘的主要方法
• 2.1.2.1 关联规则方法
• 2.1.2.2 决策树方法
• 2.1.2.3 人工神经网络
• 2.2 聚类分析技术
• 2.2.1 聚类分析概念
• 2.2.1.1 聚类分析定义
• 2.2.1.2 距离和相似性的度量
• 2.2.2 聚类分析方法分类
• 2.2.2.1 划分聚类方法
• 2.2.2.2 层次聚类方法
• 2.2.2.3 密度聚类方法
• 2.3 半监督聚类技术
• 2.3.1 基于约束的半监督聚类方法
• 2.3.2 基于距离的半监督聚类方法
• 2.3.3 基于遗传算法的半监督聚类方法
• 2.4 本章小结
• 第三章 半监督聚类利用成对约束信息的新方法
• 3.1 成对约束的定义
• 3.2 近邻度的定义
• 3.3 凝聚层次聚类算法（AHC）
• 3.4 基于成对约束的半监督凝聚层次聚类算法（PS-AHC）
• 3.4.1 利用成对约束改变聚类簇之间的距离
• 3.4.2 PS-AHC算法的步骤
• 3.5 实验结果与分析
• 3.5.1 实验方案
• 3.5.2 结果与分析
• 3.6 本章小结
• 第四章 基于遗传算法的改进半监督聚类算法
• 4.1 建立遗传算法模型
• 4.2 基于遗传算法的半监督聚类算法（LG-SSC）
• 4.3 基于遗传算法的改进半监督聚类算法（PLG-SSC）
• 4.3.1 利用类标记信息
• 4.3.2 通过PFDS方法来利用成对约束信息
• 4.3.3 PLG-SSC的整体描述
• 4.4 实验结果与分析
• 4.4.1 实验方案
• 4.4.2 结果与分析
• 4.5 本章小结
• 结论
• 参考文献
• 在读期间已发表和录用的论文
• 个人简历