聚类是一种无监督机器学习方法,它通过数据潜在的结构来分析数据,并根据特定的特征度量进行类别划分,如内部同质性和外部分岔。聚类对于揭示现实世界中固有的、潜在的和未知的知识、原理或协议是至关重要的,在科学和工程中得到了广泛的应用。在过去的三十年中,学者们提出了几种聚类策略,如基于划分的、基于层次的、基于网格的、基于模型的和基于密度的,这些策略在类簇的定义和识别类簇效率上存在着显著差异。不同聚类策略或算法在同一数据集上的聚类结果通常是不同的。基于密度的聚类算法是处理任意形状大规模数据集的基本聚类方法之一,并对噪声具有一定的鲁棒性,是当前最流行的聚类策略之一。密度聚类通常将高密度区域或一组密集连接的数据点视为一个类簇,并且这些类簇被低密度区域所隔离。在多种能够处理带噪声数据的密度聚类方法中,DBSCAN(Density-based spatial clustering of applications with noise)是一种最著名的密度聚类算法,也率先提出局部密度的概念。DBSCAN主要优点在于能够处理离群样本,并针对任意形状类簇的处理有两个主要优势,即形成高密度数据样本点(即核心点)的链结构,并将离群样本识别为低密度数据样本点。然而,DBSCAN也存在着明显的局限性:ⅰ)聚类效果很大程度上取决于用户定义的参数值,但在没有先验知识的情况下,很难针对不同数据集给出合理的估计值;ii)在类簇扩张过程中,需要计算所有邻近区域的点对而得到最近样本点,计算复杂度高;ⅲ)由于采用全局密度评价,使得DBSCAN不能很好的区分临近的、密度不同的类簇。最近,Rodriguez和Liao提出了另一种基于密度的聚类算法,称为密度峰值聚类算法(DPC,Density Peak Clustering),该算法采用了均值漂移法中的局部密度最大值的思想,以及数据样本之间距离单参数的概念。DPC具有独特的特点,例如i)能够基于生成的决策图检测非球面簇,ⅱ)控制参数数量较少,ⅲ)计算复杂度相对较低。DPC分两个阶段进行聚类。在第一阶段,DPC使用精心设计的决策图方法找到具有密度最大值或密度峰值的簇形心。在第二阶段,每个剩余的数据点被分配到与其最近的高密度邻居相同的集群中。尽管DPC算法在多个数据集上处理效果较好,但仍然存在一些不足,也限制了它的应用范围,具体如下:第一,在计算局部密度的时候,DPC算法采用整个数据集计算样本局部密度,从而生成选择类簇中心的决策图,这使得DPC算法在处理有重叠的簇和低密度数据点时非常困难。第二,数据样本的局部密度受截断距离参数Cd的影响,该参数的选取与数据集样本规模相关,并带来不同的聚类结果。DPC算法是通过Cd来评价数据样本的密度,即数据样本之间的距离决定样本密度。事实上,参数Cd代表了一个关于数据集的半径,在截断距离范围内有多少数据样本在其周围就是它的密度。通常情况下,参数Cd的选择是基于启发式方法,数据集中相邻样本的平均数应该仅占整个数据集的1-2%,这种方法在一些情况下能取得较好的效果,但并不是一种通用的方法。具体来说,DPC算法针对数据集规模的不同,使用不同方法来估计样本局部密度。当数据集规模足够大时,该方法可以有效的计算样本的局部密度,否则采用高斯核函数并且预先指定截断距离参数Cd。因此,数据集规模大小的不同使得密度矩阵不同,截断距离Cd的任意选择对聚类结果有很大影响。然而,目前没有统一的指标来确定数据集的大小,也不存在计算精确密度的鲁棒性方法。因此产生的不同聚类结果,所以需要根据数据集的本质,使用不同的方法来估计密度。第三,DPC算法通过数据样本的局部密度生成一个启发式决策图,类簇中心需要用户手工进行选取,而选取一个好的簇中心取决于用户对数据集本质的观察和理解。与DBSCAN不同,DPC需要首先找到类簇的中心,然后再分配其他样本。这使得类簇中心的选取对DPC算法效果起着至关重要的作用,也是DPC算法的核心。一旦类簇中心被错误的选取,聚类效果将明显下降。特别是在处理复杂数据集时,在缺少先验知识的情况下,用户很难选择正确的类簇中心数目,因为DPC的决策图不能表示自然的类簇中心。在智能数据分析中,手工选择簇中心是DPC算法的一个很大的缺陷,也使得DPC的性能受限于簇中心的人工选取。第四,有效处理异常样本是聚类算法所能提供的基本功能,而DPC算法不具有处理异常样本的能力,并且它不能很好地处理不均匀的簇分布。在簇附近的异常样本总是被视为簇的一部分,因为在DPC算法里没有“噪声信号截断距离”,无论采用怎样的Cd值,DPC也很难识别异常样本,且不能发现小规模的簇或由异常值组成的簇。第五,DPC算法在处理非簇中心样本时的聚类策略与K-Means和K-Medoids聚类算法类似,非簇中心样本将被分配到最近且密度最大的簇中,这使得DPC算法对数据随机分布情况下的聚类效果很不理想,因为数据集中一个或多个类簇可能存在多于一个密度峰值。因此,在处理多密度峰值类簇时,DPC算法不能很好的识别类簇数目以及类簇中心,即使在决策图中正确选取了类簇数目,实际的自然类簇也会被聚成多个类簇。为了克服上述问题,本文提出了一种度量数据样本局部特征的残差方法,并结合多种聚类思想,提出了克服密度峰值聚类的四种不同策略和新的聚类算法,并通过实验验证了提出算法的效果,具体如下:本文第一部分介绍提出的样本局部特征残差方法,通过该方法构建决策图,能更有效的识别类簇中心,并通过样本残差进一步检测边缘样本,从而有效的检测聚类中的异常样本。为了更好地处理多峰值类簇和低密度样本,本文提出了一种新的残差聚类算法(Residual Error-based Clustering algorithm,REC),REC 算法在生成决策图时借鉴了DPC算法思想,在确定邻域内的密度连通性时借鉴了DBSCAN思想,在计算样本局部特征方面学习了残差理论。具体地,REC算法计算每个样本和N近邻之间的残差作为其局部特征,在获得中间聚类结果后,将特征值低的样本称作Halo样本,并做进一步处理。这样,可以更好地区分异常样本和边界数据样本。REC算法的具体过程包括四个阶段:首先,计算单个样本的残差作为局部特征,通过残差计算的局部特征是只考虑邻域内数据样本的特性。与DPC算法相反,DPC将整个数据集中的所有数据样本都考虑在内。而这种基于残差的方法能够生成更好的决策图,用于簇中心的识别。其次,生成决策图,识别类簇中心,并将数据样本分配给各个类簇。根据经验法则,选取残差值较低、距离值较高的数据点作为类簇中心。然后,确定Halo样本(包括边界样本和异常样本)。最后,从Halo样本分离异常样本,并在最终聚类结果之前做进一步处理。在异常样本检测过程中,将残差高、距离值小的Halo样本识别为异常样本,并给出最终的聚类结果。本文通过对Halo样本的进一步分析,证明该方法能够较好地识别和处理不同数据集中不同模式下的各种异常样本。为了评估REC算法的效果,本文采用10个UCI数据集、7个广泛使用的合成数据集和3个自定义数据集开展了实验,采用F-Score比较了 REC算法与其他基准算法在相同数据集上的聚类效果。实验结果展示了在19个数据集中,REC算法在20个数据集上的F-Score最高。此外,本文分析了每种算法的时间复杂度,以及各算法所花费的计算时间(所有模型平均运行20次的均值),还从多个侧面比较了REC的聚类效果,包括对类簇中心的识别效果、对异常样本的识别效果、对大小不等类簇的识别效果、对不规则形状类簇的识别效果、对密度不同的类簇识别效果等方面。真实数据集和合成数据集的实验结果表明,本文所提出的残差聚类方法优于DPC、DBSCAN、AP和K-Means聚类算法。本文第二部分工作主要研究了半自动聚类算法,以解决对决策图的依赖和人工类簇中心选择带来的风险。本文提出了一种可行的残差片段融合聚类算法(Residual Error-based Clustering with Fragment merging strategy,FREC),该算法不再需要使用决策图一类的启发式方法,就可以有效地识别类簇中心和异常样本检测。FREC算法借鉴了DPC算法中密度估计的思想、借鉴了DBSCAN在邻域内的密度连通性、借鉴了SCAN算法对的结构相似性计算方法和残差理论。FREC采用REC中样本的残差计算方法,来更好地估计数据样本的局部特征,通过生成残差集来形成残差片段,并通过进一步处理完成数据样本的聚类过程,从而达到不使用决策图启发式方法的情况下完成聚类。具体地,FREC在类簇形成过程中与DPC等算法的思路不同,它以相反的顺序形成类簇。初始时,FREC通过合并具有更高相似性的残差片段形成类簇;进一步,FREC将每一个类簇中残差值相对更低的样本作为类簇的中心,通过这种方式可以有效的替代在决策图上人工选取残差中心的过程。通过对残差片段融合算法的进一步分析,FREC不但是一种半自动聚类算法,而且能够更好地识别和处理不同模式数据集中的异常样本。FREC算法的具体过程包括四个阶段:首先,计算每个数据点的残差作为样本局部特征。其次是生成残差片段,FREC残差片段的生成是通过计算每个样本的邻接样本来完成的,通过预定义的残差截断距离阈值Cd及其链接结构来确定每个样本的邻接样本,通过邻接样本来完成残差片段的生成。然后,根据结构相似性原理,计算各残差片段结构相似性指数(Structure Similarity Index,SSI),结构相似性越高,片段之间的聚集概率就越高,由结构相似性高的残差片段间形成同一个簇;同时,将生成的类簇中残差最小的样本作为该类簇的中心。最后,异常样本也将通过残差片段间的相似性指数得到正确的识别,因为该片段相对其他片段的相似度更低。为了评估FREC算法的效果,本文采用12个UCI数据集、4个广泛使用的合成数据集和3个自定义数据集开展了实验,采用F-Score评估FREC算法与其他基准算法在相同数据集上的聚类效果。实验结果展示了在19个数据集中,FREC算法在18个数据集上获得了最高的F-Score分值。此外,本文还比较了几种算法在处理19个数据集时所需要的计算时间(所有方法平均运行10次)。本文从多个侧面比较了FREC算法与其他算法的聚类效果,包括检测簇中心、检测异常簇、检测任意形状簇、检测不同大小簇、检测不同密度簇等方面的性能。实验结果表明,本文所提出的残差片段融合聚类算法不但是一种半自动的聚类算法,而且聚类结果也优于传统的DPC等其他几类算法。本文第三部分工作主要研究了具有路径连通特性的低密度簇识别算法,通过对低密度数据样本采用更有效的分配策略,最小化REC算法的误分配率。REC算法虽然能够有效识别异常样本和不同密度的类簇数目,但在处理一些更为复杂、低密度连接的弧形簇的数据集时仍然存在不足。REC算法能够检测到低密度的弧形簇作为Halo样本,但不能在输入不同参数时正确地聚类Halo样本。REC算法总是将弧形簇进行分割,并错误地将其分配给其他簇,低密度数据样本的特殊分布使得REC无法有效的处理Halo样本。此外,由于REC算法形成类簇的方法与DPC算法相似,REC根据识别出的类簇中心来分配其他数据样本,即使在自然类簇中识别出正确的类簇中心,REC也存在分割自然类簇的可能。特别是当一个数据集由一个包含高斯分布簇的弧形簇组成时,即使在决策图中正确选区了簇中心,也不能正确地识别类簇的数目。本文解决REC算法存在的问题,本文提出了一种改进的路径跟踪残差聚类算法(Path-following Residual Error-based Clustering algorithm,PREC),该算法通过更有效的弧形簇Halo样本检测方法来提高聚类效果。PREC采用Halo网络对低密度数据点进行处理,根据Halo样本自身的特性将其分为边界样本、异常样本、枢纽样本(存在于两个或多个簇之间的样本)和类簇样本。PREC引入了两个主要概念,分别是“Halo网络生成”和“Halo优化”,首先识别Halo样本,然后生成Halo网络结构,并一步细化各Halo样本的类别分别进行处理。作为REC的改进算法,PREC算法过程由以下五个阶段组成:第一步,计算每个数据样本的残差作为局部特征,以及每个样本到邻居中残差最小样本间的距离。第二步,生成决策图并识别类簇中心,并给每一个样本点分配聚类标签。第三步,识别Halo样本(由异常样本、边界样本、枢纽样本和类簇样本组成)。第四步,根据Halo样本之间的距离生成Halo结构网络,并计算每个Halo网络中每个Halo样本的核心样本,核心样本是同一个Halo网络中到每个样本距离小于预定义阈值Cd的样本。第五步,计算每个核心样本的类簇标签,并计算每个Halo网络的邻域类簇数目。单独的一个Halo网络是一个结构化的网络,包含了核心样本数目和其邻域簇总数信息。PREC算法根据Halo网络的特性及其与邻域簇的关系,对Halo样本的类型进行检测和识别,并输出最终的聚类结果(弧形簇、异常样本和枢纽样本)。本文采用8个UCI数据集、7个标准合成数据集和3个自定义数据集开展了实验,采用F-Score评估PREC算法与其他基准算法在相同数据集上的聚类效果。实验结果展示了在18个数据集中,FREC算法在17个数据集上获得了最高的F-Score分值,聚类结果最好。还展示了每个算法所用的计算时间(每个算法平均运行20次)。实验结果表明,本文所提出的路径跟踪残差聚类算法能够更好的处理弧形数据分布,聚类效果较REC、DPC等基准聚类算法更优。本文最后一部分内容主要研究识别低密度环形簇的聚类算法,这是一类具有路径连通性或螺旋特性的簇。本文提出了一种新的混合算法KREC(A combined clustering algorithm based on K-Means and REC),将K-Means算法与REC算法相结合,在不使用截断距离参数Cd的情况下,任然能够有效对异常样本进行检测和处理低密度环形簇的聚类算法,提高了聚类效果。本文提出的KREC算法利用K-Means将数据分成微簇、残差理论计算样本局部特征、REC中分配数据样本的方法构成了新的算法。KREC包含两阶段的过程,在划分阶段使用K-Means将数据集聚类为相对较小的微簇,然后实现REC算法概念,对这些微簇进行聚集和进一步分析,以找到自然簇和合并阶段的异常样本。KREC算法包括四个步骤:第一步,通过实现K-Means算法将数据集划分为一组微簇。第二步,计算每个微簇的残差作为局部特征,然后计算微簇间距离。第三步,生成决策图,选择微簇中心,并通过将剩余的微簇分配给各自的微簇中心来生成类簇。第四步,将异常样本分离为残差最大的微簇,并给出最终的聚类结果。为了验证本文提出的KREC算法的有效性、可扩展性和鲁棒性,本文采用7个UCI数据集、6个合成数据集和9个自定义数据集进行测试,采用F-Score评估KREC算法与K-Means、AP、DBSCAN、DPC和REC算法在相同数据集上的聚类效果。实验结果展示了KREC在21个数据集上的F-Score分值最高,并且能够有效处理低密度环形簇。实验结果表明了KREC算法相较于DPC等其他基准聚类算法的有效性。综上所述,基于密度的聚类算法在处理类簇边缘样本时不能有效表达样本的紧凑关系,而基于残差的聚类算法在处理类簇时更加鲁棒。基于残差的聚类算法能够有效表达数据集中样本之间真实的关系,对于识别类簇数目和边缘样本更加有效。本文通过大量的实验验证本文提出的残差策略和算法的效果。实验结果表明,基于残差的算法与现有的基于密度的算法相比具有更好的性能,是一种合理有效的局部特征描述方法,本文的研究为采用基于残差的方法代替基于密度的模型提供了有力的支持