论文部分内容阅读
聚类分析是一种研究样本分类的统计方法,也是一种数据挖掘的方法,可以有效地实现数据结构的探测,在国际上已成近年机器学习领域的研究热点。谱聚类算法作为聚类算法的一个分支是一个重要的研究方向,以图论作为理论基础,基本思想是将聚类问题转化为图论中的对无向加权图的最优分割问题。与现有的其他典型的聚类分析算法相比较而言,谱聚类算法在聚类的过程中降低了对样本空间形状的要求,同时谱聚类算法还可以有效的克服一些经典聚类算法易收敛于局部最优解的缺点,可以得到收敛于全局的最优解。本文在对前人研究谱聚类算法所取得的现有成果进行了系统的学习,对已有的相关算法进行了部分改进。具体的工作内容概括如下:1)首先介绍了关于聚类算法特别是谱聚类算法的基本概念以及理论基础,分析了谱聚类算法中的一些相关技术的已有的研究成果以及应用的现状,然后对谱聚类研究领域中所涉及的几个关键性问题进行了总结,归纳了谱聚类算法未来的几个关键的研究方向。2)针对传统的谱聚类算法中的两个基本的难点:相似矩阵的构造以及自动确定类的数目问题,本文通过定义的一种新的距离度量—密度敏感的距离和引入的特征间隙两个概念,提出了一种基于密度敏感的自适应谱聚类算法。新提出算法的有效性在模拟数据集以及UCI数据集上的实验中都得到了较好的验证,同时本文还计算了该算法与传统的SC算法的分类正确率,比较结果显示新算法的聚类性明显优于SC算法。3)针对IPCM算法对稀疏程度不同的样本集的聚类效果不理想,而且需要人工手动输入聚类数目的缺点,本文通过引入密度敏感的距离与特征间隙两个概念,提出一种基于谱聚类的自适应IPCM算法,该算法用密度敏感的距离代替传统的欧氏距离,并通过特征间隙的性质准确地计算出聚类数目。通过数据实验,证明了改进后的算法的有效性以及正确率都有所提高,同时该算法能够有效的弥补IPCM算法及谱聚类算法在各自单独聚类时所存在的缺点。4)将本文所提的密度敏感相似性度量引入到判别割算法中,代替原有的欧氏距离,以此对判别割算法进行改进,在此基础上提出了一种基于密度敏感的判别割的图像单阈值分割算法。该方法在算法实现的复杂度和实现时所需存储空间等问题上都有了一定的改进。