基于近邻路径的自适应尺度谱聚类算法研究（可编辑）.doc

基于近邻路径的自适应尺度谱聚类算法研究(可编辑)基于近邻路径的自适应尺度谱聚类算法研究哈尔滨工程大学硕士学位论文基于近邻路径的自适应尺度谱聚类算法研究姓名:罗怀金申请学位级别:硕士专业:计算机技术指导教师:国林;韩学文2012-06基于近邻路径的自适应尺度谱聚类算法研究摘要谱聚类作为一种新兴的聚类方法,最近十年得到了广泛的研究和快速的发展,尤其在数据挖掘和机器学习等领域。相比传统聚类方法,谱聚类能够处理任意分布形状的数据集,可以收敛到全局最优并且易于实现,非常适合于很多的实际问题。由于谱聚类算法都是以相似矩阵为基础的,因此建立相似矩阵使用的相似度定义对于谱聚类算法的性能具有非常重要的意义。本文首先详细阐述了谱聚类相关的知识和方法,然后对经典谱聚类的相似度度量,从高斯核函数、尺度参数选择的影响、数据聚类的一致性三个角度对其进行了详细的分析和研究。发现经典谱聚类的相似度没有充分考虑局部统计信,禾全局结构对两个数据点相似度的影响,以致不能充分满足聚类一致性,反映出两点间真实的近似关系,最终导致处理大量复杂结构的数据集时不能得到满意的聚类结果。受此启发,结合近邻思想,首先提出了基于共享近邻加权的自适应尺度,其充分利用了近邻分布统计信息;然后提出了强调全局结构一致性的近邻路径距离;基于这两者给出了基于近邻路径的自适应尺度相似度,该相似度很好的满足了聚类一致性特征,将其引入谱聚类得到基于近邻路径的自适应尺度谱聚类算法。最后,在个人工数据集、个数据集和数据集上对将该算法与经典谱聚类、自调整谱聚类进行了对比实验。实验结果表明,该算法的聚类效果明显优于另两种算法,能够有效识别数据点之问的内在联系,得到正确聚类结果。关键词:谱聚类;相似度;共享近邻加权;自适应尺度;近邻路径基于近邻路径的自适应尺度谱聚类算法研究,,,.,,.,.,,,..,,?;;,,。,..,,..;;;:;,尤其是数据库技术的快速发展以及数据来源的多样化,人类正以前所未有的速度积累着越来越多、越来越复杂的数据,然而人们对数据的掌握了解却赶不上数据升级的速度,很难从中获取到数据隐含的具有潜在用处的深层信息,以致人们正在被数据所淹没。为了能够得到隐藏在海量数据背后的重要信息,数据挖掘应运而生,该技术是从大量数据中发现并抽取隐藏在内部的、人们预先不知道的但又可能有价值的信息和知识。数据挖掘的方法主要有分类或预测模型、聚类分析、关联规则、序列模式识别、空间多维数据访问与可视化、不确定性推理等。由于相当一部分待处理分析的数据对象集没有先验知识或者说其对象的类标号未知,使得聚类分析的研究变得尤为突出和重要,成为了不仅在数据挖掘领域,在许多其他如机器学习、统计学、模式识别、生物学等研究领域的一个研究热点,扮演着重要的角色。聚类分析只需要利用在数据集合中挖掘出的表征对象本身以及它们彼此间关系的信息,把数据对象合理划分到不同的簇,获得其中隐藏的有用信息。其目标是使簇内的对象相互之间尽量相似相关,而不同簇中的对象之间尽量相异不相关。簇内整体的相似性越大,簇问整体的相异性越大,则得到的聚类结果就会越趋近于理想。与有监督的分类相比完全不同,分类是通过学好的样本,得到适当的模型或规则,然后对新的样本对象实现标记分类。聚类分析是无监督的分析过程,往往是在没有任何数据先验信息的情况下,如事先不知道对象集应该划分为多少类,待划分的所有对象也没有标记等,根据某种距离度量对象间的相似性,实现对数据点中的内在关系的分析和研究,然后按照聚类目标在整个数据对象集合上执行聚类划分。目前已经存在非常多不同的聚类算法,具有代表性的有均值聚类算法?、旨在学习复杂模型的算法、新兴的基于谱图划分的谱聚类算法等。相比于谱聚类算法,传统聚类算法往往都需要假设数据结构空间表现为凸球形,即无法处理任意分布的数据对象集,只有在凸球形结构的数据集上才能取得满意的聚类效果,同时由于寻找最优解时使用的是迭代最优化方法,使算法得出的结果总在局部情况下最优,无法实现期望的全局最优。所以传统聚类算法需要首先基于对数据模型的明确估计,当数据根据假定的模型组织时,才可以提供高质量的聚类结果。而谱聚类算法作为聚类分析中的一个新兴分支,不仅可以对任意分布的数据空间进行聚类,而且最终的划分结果可以实现全哈尔滨工程大学硕学位论文局最优。谱聚类就是利用谱方法来实现聚类数据对象的一种方法,是从谱图划分思想发展而来【,。它不需要预先假定数据对象集的全局分布结构,首先对给定的样本数据集,按照基于某种距离的相似度量,建立一个成对数据点相似矩阵,求出相应的矩阵,接着对矩阵实施特征分解,得到矩阵的特征值即谱聚类中的谱和相应的特征向量,然后挑选适合的特征向量组合成新特征空间,在特征空间中把行看成点运行等传统聚类算法实施聚