基于凸壳的半监督聚类算法研究

论文摘要

半监督聚类算法是目前机器学习和数据挖掘领域的一个研究热点,吸引了众多学者对该领域进行研究,并取得了一定的研究成果。本文对半监督聚类算法进行了研究,提出了一种基于凸壳的半监督聚类算法,并通过实验对其聚类效果进行了验证,一定程度上丰富了半监督聚类算法的研究内容,给半监督聚类问题的求解提供了新的思路,具有一定的科研价值和应用潜力。从机器学习的角度讲,传统的聚类算法属于无监督学习中的一种,而半监督聚类则属于半监督学习。半监督聚类就是利用数据集中带有标签或者限制信息的样本数据辅助聚类的过程,因此,半监督聚类中最重要的问题就是如何有效的利用原始数据中提供的已知标签或限制信息,指导聚类过程,使其趋向于得到较好的结果簇方向。目前存在的半监督聚类算法可以大体分为两大类:基于限制的方法和基于距离的方法。本文提出的SCBCH（基于凸壳的半监督聚类）算法属于后者。从结构上看,本文首先介绍了聚类的相关理论,对聚类中的基本概念进行了解释。由于SCBCH算法属于聚类中的一种,因此,这些概念对SCBCH算法同样适用。同时,还对聚类中的常见簇类型和常用的聚类算法进行了介绍,明确了聚类的通用流程。在随后的内容中,重点讲述了半监督聚类的有关知识,如半监督聚类的研究背景和意义,半监督聚类的基本理论以及发展现状,半监督聚类中的两种常用算法等,为后文中提出SCBCH算法奠定了理论上的基础。第二章中还对聚类质量度量的几种常用方式的原理进行了介绍,为后文中SCBCH算法的有效性验证实验取得的较好效果建立了依据。本文的第三章中对凸壳的相关理论以及常用算法进行了介绍,为本文中提出的SCBCH算法中引入凸壳的缘由进行了理论上的说明。然后,对凸壳构造算法在不同维度数据中的时间复杂度进行了探讨性的实验。结果表明,凸壳算法仅适用于低维空间,同样为SCBCH算法的验证性实验提供了理论支撑。第四章中提出了本文的核心内容SCBCH算法,从算法提出的意义、算法的具体流程、以及算法的验证实验三个方面进行了详细的阐述。验证实验表明,SCBCH这种半监督聚类算法与传统聚类算法相比,对聚类的准确率以及簇间的紧密程度等都有一定程度的提升,符合半监督聚类的特征。与文中介绍的Seeded-KMeans算法（由Sugato Basu提出的一种半监督聚类算法）相比,聚类效果相差不大。因此,可以说明本文提出的算法在一定程度上效果良好。最后对全文进行了总结,并指明了下一步的研究和工作方向,对基于凸壳的半监督聚类算法的进一步发展提出了自己的看法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 半监督学习简介
• 1.2 选题背景及其研究意义
• 1.3 半监督聚类算法的国内外研究现状
• 1.4 论文主要研究内容及章节安排
• 2 半监督聚类理论基础
• 2.1 聚类相关的概念及原理
• 2.1.1 簇的概念
• 2.1.2 簇的不同类型
• 2.1.3 常见的聚类类型
• 2.2 半监督聚类理论
• 2.2.1 基于限制的方法
• 2.2.2 基于距离测度的方法
• 2.3 经典聚类算法理论及实现
• 2.3.1 经典无监督聚类算法
• 2.3.2 经典半监督聚类算法
• 2.4 聚类质量度量
• 2.4.1 使用凝聚度和分离度度量
• 2.4.2 使用相似度度量
• 2.5 本章小结
• 3 凸壳理论及算法实现
• 3.1 凸壳的定义及凸壳问题的提出
• 3.2 凸壳理论的研究现状
• 3.2.1 凸壳应用的研究现状
• 3.2.2 凸壳算法的研究现状
• 3.3 几种常见凸壳求解算法的理论及实现
• 3.3.1 卷包裹法
• 3.3.2 格雷厄姆法
• 3.3.3 QuickHull 算法
• 3.4 凸壳算法的时间复杂度实验
• 3.4.1 实验数据说明
• 3.4.2 实验结果及说明
• 3.5 本章小结
• 4 SCBCH 算法的设计与实现
• 4.1 SCBCH 算法的提出
• 4.2 SCBCH 算法的流程
• 4.3 SCBCH 算法的验证实验
• 4.3.1 实验说明
• 4.3.2 相关数据说明
• 4.3.3 实验结果及分析
• 4.4 本章小结
• 5 总结和展望
• 5.1 全文总结
• 5.2 下一步工作
• 参考文献
• 致谢
• 个人简历
• 在学期间发表的学术论文