面向复杂数据的聚类算法研究

近年来,数据量急剧增长,数据源的种类日益增多,导致从复杂的数据中获取有用的信息变得越来越困难。要想很好地利用这些数据,就必须理解这些复杂的数据,从中挖掘出其内在的模式。聚类分析能根据数据间的相似性识别出数据集中的内在模式。但很多聚类算法在划分不同类型的数据集时,都会遇到精确性不高或者执行效率较低等问题,这就需要投入更多的精力去提高聚类算法的性能。本论文以更高效、更精确地对复杂数据进行聚类为目的,针对三种不同类型的数据,集中在聚类研究的三个方面,提出了四个聚类算法:EPC、MulSim、CLUB和SUM。EPC是一个根据污染特征将大气污染抽样数据进行聚类的算法,它能提高CMB、PMF、UNMIX和PCA等源解析模型的精确性,并且和传统算法算法相比更易于使用、更适合于聚类高维数据;MulSim和CLUB是挖掘数据集中包含的任意形状、任意密度以及任意规模的簇的两个聚类算法,其中,MulSim基于单点与多点相似的策略进行聚类,CLUB通过识别簇的密度主干进行聚类;SUM是对图数据中的顶点进行聚类的算法,其基本原理是质疑簇中的最大度顶点在聚类时对其他顶点的连接作用。(1)EPC EPC在第一步对数据进行预处理后,迭代进行第二步,每次迭代选择第一个未标记的数据点作为一个簇中心点,然后根据本文提出的相似性函数和用户给定的相似性阈值,把每个数据点分配到与它最相似的中心点所属的簇,最后利用与k-Means相似的方法对簇进行更新,形成最终的簇结构。本文在实验部分通过人工数据集和真实数据集分别验证了EPC算法的有效性。结果表明,EPC算法不但能根据污染特征的相似性对环境污染抽样数据进行聚类,而且还能同时检测出其中的异常点。(2)MulSim MulSim定义了一个能自动适应数据点密度变化的相似性函数,若一个数据点同时与另一个数据点以及该点的邻居相似,就认为这两个数据点属于同一个簇。实验结果显示,在测试的任意密度数据集、统一密度数据集、簇内包含多个中心点的数据集、包含螺旋形簇的数据集、包含球状簇的数据集、包含任意形状簇的数据集以及多维数据集等各种类型的数据集上,MulSim的聚类质量在多数情况下优于六个对比算法。(3)CLUB CLUB首先基于互k最近邻方法发现初始簇,接着将初始簇作为算法第二步的输入,基于k最近邻方法识别出簇的密度主干。然后,通过把无标签的数据点分配给密度比它大的最近邻所在的簇以形成最终簇结构。最后,从簇的内部检测出异常点。实验部分在九个包含任意形状、任意密度、任意规模簇的二维数据集以及七个广泛使用的多维数据集上,通过与三个经典算法、三个新算法进行比较,对CLUB的性能进行了评价。而且,还将CLUB应用于Olivetti Face数据集上,展示了其在人脸识别中的有效性。实验结果显示,CLUB在大多数情况下优于对比算法。(4)SUM SUM利用相邻顶点间的公共邻居个数和较小度顶点的度定义了一个相似度函数。在将相似的顶点放置到同一个簇中之后,SUM质疑簇中的最大度顶点对其他顶点的连接作用,断开簇中最大度顶点与其邻居顶点的连线,将最大度顶点重新分配来获得初始簇。然后,SUM将尚未标记的点分配给初始簇后,调整边界点以形成最终簇。通过与四个经典的、两个新的图聚类算法在四个有真实簇结构、四个无真实簇结构的图上的实验比较显示,SUM能够较精确地检测出簇结构,并且结果优于对比算法。四个算法的时间复杂度都接近于线性复杂度。所以,这四个算法均能以较高的精确性对其相应特征的数据集高效地进行聚类分析。