文档介绍：Research on Semi-Supervised Spectral ClusteringAlgorithm Based on Active Learning A Thesis Submitted toChongqingUniversity in Partial Fulfillment of the Requirementfor the Degree ofMaster ofEngineering By Liu Ronghui Supervised by Associate Prof. Zhong Jiang puter Software and Theory College puter Scienceof Chongqing University,Chongqing, China April2011 重庆大学硕士学位论文中文摘要 I 摘要聚类技术是用于数据分析的最常应用的技术之一,其应用领域涉及统计学、计算机科学、生物学以及社会学等。传统的聚类算法如常见的K-means算法,EM 算法等都是建立在凸状分布的样本空间上,当样本空间分布不为凸时,算法就会陷入局部最优,因而此类算法不适合在任意形状分布的样本空间上解决聚类问题。近些年来,谱聚类算法作为一种新颖的聚类方法受到广泛的关注,并成为了机器学****模式识别等领域的研究热点。谱方法建立在谱图划分理论基础上。与其他传统聚类技术相比,它能够在任意分布形状的样本空间上进行聚类,并且最终能够收敛于全局最优解。谱聚类算法在聚类过程中,通过特征向量构建更加简化的样本数据空间,这样不仅降低了样本数据的维数,而且还使得样本数据的分布结构在子空间内更为清晰和明显。半监督聚类是指在聚类过程中,利用样本先验信息去指导聚类过程以获得更好的聚类效果。与无监督聚类相比,半监督聚类利用少量的监督信息去指导聚类过程。而半监督聚类算法的性能取决于监督信息。因此,监督信息的选取非常关键。本文首先介绍本课题的研究背景和意义,以及当前谱聚类的研究状况,接着具体介绍了数据挖掘和聚类分析的相关理论,然后着重介绍了谱聚类的相关理论, 并对其优势和面临的问题做出分析,最后介绍了本文的研究内容及贡献: ①针对半监督聚类的性能取决于所提供的监督信息这个问题,本文构建了一种新的选取成对约束信息的主动学****策略,该策略在聚类过程中主动的选取信息含量丰富的成对约束信息。其主要思想就是:找出同一类中距离远的数据对象对, 记为Must-link;找出不同类中距离近的数据对象对,记为Cannot-link。②构造了一种基于主动学****的半监督谱聚类算法,就是在聚类过程中,利用主动学****策略选取得到的成对约束信息,来调整数据对象之间的距离矩阵,使得同一类中各个数据对象分布尽可能紧凑,不同类之间的数据对象分布尽可能分散。通过在UCI数据集上的实验可以证明本文算法的有效性。关键词:谱聚类,半监督,主动学****重庆大学硕士学位论文英文摘要 II ABSTRACT Clustering technology is one of the most widely usedtechniquesfor exploratory data analysis, withapplications ranging from statistics, computer science, biology to social clustering algorithmssuch as K-means algorithm , EM algorithmare basedon convexsample spaces, while the sample spacesarenot distributed convexly, theycan be easily converged to local optimal solution, so such kinds of clustering algorithmsare not quite suitable toacquireoptimal solution on the sample datasets which distributed non-convexly. Spectral clustering algorithm has receiveda significant amount of attention as a newlydeveloping techniquein recent years, and ithas e aresearch hotspot in the domain suc