论文摘要
当前,聚类分析是国际数据挖掘和机器学习领域中的研究热点之一。聚类分析是人们认识和揭示事物间内在联系的一种有效手段。作为一种高效的数据分析手段,它已广泛地被应用到数据压缩、图像处理、计算机视觉、语音识别、文本聚类和异常点检测等等领域。而作为一种较新的聚类分析方法的谱聚类方法具有传统聚类方法不具有的许多优点,如谱聚类方法简单直观、容易实现、能得到全局最优解和能对任意形状的数据空间进行聚类分析等等。传统谱聚类方法以关联矩阵为基础,构建Laplacian矩阵,从而计算出矩阵的特征值和特征向量,接下来根据某种规则选取一个或多个特征向量进行聚类分析。然而,上述过程至少面临两个亟需解决的难题,一是,如何设置构造关联矩阵所需的高斯核尺度参数;二是,直接对Laplacian矩阵进行特征值分解的计算复杂度高达O(n3)。这两个难题制约了传统谱聚类方法的在实际中的应用。因此,设计出无需人为设置尺度参数和计算复杂度低的谱聚类方法具有重要的理论意义和应用价值。若是用余弦法取代高斯核来度量数据对象间的相似性,那么我们将可避免尺度参数的精确设置问题。前人的研究亦表明采样技术是降低谱聚类方法计算复杂度的有效手段之一。然而,抽样技术存在逼近误差大和样本点不能准确地捕获簇的几何结构等缺点。为了进一步改进谱聚类算法,本文作了如下工作:(1)针对谱聚类集成算法在图像分割中运行效率低下的问题,首先提出了一种基于相似度矩阵的谱聚类集成算法(SCESM算法)。SCESM算法在谱分解过程中使用代数变换进行近似求解,大大降低谱聚类集成算法的计算复杂度。为了扩展SCESM算法在大图像的处理能力和分割质量,首先采用Meanshift算法对大图像进行预分割,随后引入谱聚类集成思想对Mean shift预分割后的图像进行处理,以此设计实现了一种结合Mean shift和SCESM的图像分割聚类新算法MSSCESM。以此设计实现了一种结合Mean shift和SCESM的图像分割算法(MSSCESM算法)。实验结果表明MSSCESM算法能够获得比其他常用的算法更好的分割效果,验证了本论文提出算法的有效性。(2)研究表明,低秩逼近技术和采样技术一样可以解决矩阵的特征值分解的计算复杂度高的问题,而且低秩逼近技术的逼近误差要低于采样技术。为此,本文将低秩逼近技术与传统谱聚类算法结合起来提出了一个新的谱聚类算法,命名为基于低秩逼近技术的谱聚类算法。实验结果表明,新的算法能够在降低算法的逼近误差的同时,取得较高的执行效率和较好的聚类效果。(3)虽然低秩逼近技术和采样技术可以在大大的降低解决谱聚类算法的计算复杂度,但是二者均基于抽样技术。众所周知,在抽样技术中无论样本点是被随机抽取的或是采用其它较复杂的方法抽取的,这些样本点均不能够完全地代表整个数据集合且不能正确地捕获到整个数据集合的几何结构。因而,需要引入不涉及采样技术的其它手段来获得嵌入空间。为此,本文将通勤时间与传统谱聚类算法结合起来提出了一个新的谱聚类算法,命名为基于通勤时间的谱聚类算法。实验结果表明,新的算法能够在保证较高的执行效率的同时取得更好的聚类效果。