扩散模式的聚类算法研究

针对各种扩散模式数据点分布的聚类问题,提出了一种基于密度变化的聚类算法（CDD）。CDD采用基于密度的典型聚类算法（DBSCAN）寻找核心点,通过分析数据样本及其周围点密度的扩散规律,计算密度扩散的方向、速度和加速度,对数据样本进行聚类。实验结果表明：与DBSCAN相比,能准确对扩散模式数据进行聚类,对非扩散模式数据具有抗噪声干扰能力强,参数较易确定的优点。     

分布的自动阈值密度峰值聚类算法

密度峰值聚类（DPC）是一种基于局部密度的聚类方法,在DPC中影响算法的效果的两个基本因素是局部密度定义和类中心选择。针对经典DPC在定义局部密度时没有考虑到邻域内样本点的分布情况,以及无法自动选择类中心等问题,提出一种基于分布的局部密度定义和基于最大类间差法的自动类中心选择策略。计算每个样本点截断距离圆圈内的数据点个数,同时考虑数据点的分布情况。当圈内具有相同的点个数时,如果圆圈内的数据点分布越均匀,该点的局部密度就越大,密度峰值的可能性越高。通过最大类间差法（Otsu）自动选择阈值找出类中心。实验结果表明,新算法不仅能够自动选择聚类中心,而且相比已有原算法能获得更高分类准确度。     

基于边界点检测的变密度聚类算法

密度聚类算法因具有对噪声鲁棒、能够发现任意形状的类等优点,得到了广泛的应用。然而,在实际应用中,这种算法面临着由于数据集中不同类的密度分布不均,且类与类之间的边界难以区分等导致聚类效果较差的问题。为解决以上问题,提出一种基于边界点检测的变密度聚类算法（VDCBD）。首先,基于给出的相对密度度量方法识别变密度类之间的边界点,以此增强相邻类的可分性;其次,对非边界区域的点进行聚类以找到数据集的核心类结构;接着,依据高密度近邻分配原则将检测到的边界点分配到相应的核心类结构中;最后,基于类结构信息识别数据集中的噪声点。在人造数据集和UCI数据集上与K-means、基于密度的噪声应用空间聚类（DBSCAN）算法、密度峰值聚类算法（DPCA）、有效识别密度主干的聚类（CLUB）算法、边界剥离聚类（BP）算法进行了比较分析。实验结果表明,所提算法可以有效解决类分布密度不均、边界难以区分的问题,并在调整兰德指数（ARI）、标准化互信息（NMI）、F度量（FM）、准确度（ACC）评价指标上优于已有算法;在运行效率分析中,当数据规模较大时,VDCBD运行效率高于DPCA、CLUB和BP算法。     

基于密度峰值与密度聚类的集成算法

针对快速搜索和发现密度峰值聚类（CFSFDP）算法需人工在决策图上选择聚类中心的问题，提出一种基于密度峰值和密度聚类的集成算法。首先，借鉴CFSFDP思想，将局部密度最大的数据作为第一个中心；接着，从该中心点出发采用一种利用Warshall算法求解密度相连改进的基于密度的噪声应用空间聚类（DBSCAN）算法进行聚类，得到第一个簇；最后，在尚未被划分的数据中找出最大局部密度的数据，将它作为下一个簇的中心后再次采用上述算法进行聚类，直到所有数据被聚类或有部分数据被视为噪声。所提算法既解决了CFSFDP选择中心需人工干预的问题，又优化了DBSCAN算法，即每次迭代都是从当前最好的点（局部密度最大的点）出发寻找簇。通过可视化数据集和非可视化数据集与经典算法（CFSFDP、DBSCAN、模糊C均值（FCM）算法和K均值（K-means）算法）的对比实验结果表明，所提算法聚类效果更好，准确率更高，优于对比算法。     

混合的密度峰值聚类算法

密度峰值聚类（DP）算法是一种新的基于密度的聚类算法，当它处理的单个聚类包含多个密度峰值时，会将每个不同密度峰值视为潜在聚类中心，以致难以在数据集中确定正确数量聚类，为此，提出一种混合的密度峰值聚类算法C-DP。首先，以密度峰值点为初始聚类中心将数据集划分为子簇；然后，借鉴代表点层次聚类算法（CURE），从子簇中选取分散的代表点，将拥有最小距离的代表点对的类进行合并，引入参数收缩因子以控制类的形状。仿真实验结果表明，在4个合成数据集上C-DP算法比DP算法聚类效果更好；在真实数据集上的Rand Index指标对比表明，在数据集S1上，C-DP算法比DP算法性能提高了2.32%，在数据集4k2_far上，C-DP算法比DP算法性能提高了1.13%。由此可见，C-DP算法在单个类簇中包含多密度峰值的数据集中能提高聚类的准确性。     

密度分布函数在聚类算法中的应用

深入分析了传统的基于密度的聚类方法的特点和存在的问题及讨论了基于密度聚类算法研究现状,提出了一种改进的基于密度分布函数的聚类算法.使用K最近邻（KNN）的思想度量密度以寻找当前密度最大点,即中心点.并使用区域比例,将类从中心点开始扩展,每次扩展的同时引入半径比例因子以发现核心点.再从该核心点的KNN扩展类,直至密度下降到中心点密度的给定比率时结束.给出了数个算法实例并与基于网格的共享近邻聚类（GNN）算法在聚类准确率和效率上进行了试验比较,试验表明该算法极大降低了基于密度聚类算法对参数的敏感性、改善了对高维密度分布不均数据集的聚类效果、提高了聚类准确率和效率.     

快速识别密度骨架的聚类算法

针对如何快速寻找密度骨架、提高高维数据聚类准确性的问题,提出一种快速识别高密度骨架的聚类（ECLUB）算法。首先,在定义了对象局部密度的基础上,根据互k近邻一致性及近邻点局部密度关系,快速识别出高密度骨架;然后,对未分配的低密度点依据邻近关系进行划分,得到最终聚类。人工合成数据集及真实数据集上的实验验证了所提算法的有效性,在Olivetti Face数据集上的聚类结果显示,ECLUB算法的调整兰德系数（ARI）和归一化互信息（NMI）分别为0.8779和0.9622。与经典的基于密度的聚类算法（DBSCAN）、密度中心聚类算法（CFDP）以及密度骨架聚类算法（CLUB）相比,所提ECLUB算法效率更高,且对于高维数据聚类准确率更高。     

毫米波雷达点云的密度和划分联合聚类方法

针对室内人员检测环境毫米波雷达点云数据特性，并考虑多目标点云密集复杂情况，提出一种毫米波雷达点云的密度和划分联合聚类方法。毫米波雷达点云数据具有稀疏、均匀性差的特征。首先采用基于 DBSCAN（Density-Based Spatial Clustering of Applications with Noise）改进的参数自适应算法进行密度聚类，并对其存在的无限制密度扩张问题，通过决策树归类，对异常数据簇进行二次划分，保证了数据簇属性的单一性。试验结果表明，改进的密度聚类算法可自适应地寻找聚类过程中所需要的最佳参数并实现聚类，更适应毫米波雷达点云数据的特性，同时结合划分聚类对异常数据进行二次划分，使得聚类效果更加细腻和准确，实现了多目标密集情况下点云数据精准聚类划分的效果。     

基于密度函数加权的模糊C均值聚类算法研究

模糊聚类算法具有较强的实用性,但传统模糊C均值算法（FCM）具有对样本集进行等划分趋势的缺陷,没有考虑不同样本的实际分布对聚类效果的影响,当数据集中各样本密集程度相差较大时,聚类结果不是很理想。因此,提出一种基于密度函数加权的模糊C均值聚类算法（DFCM算法）,该算法利用数据对象的密度函数作为每个数据点权值。实验结果表明,与传统的模糊C均值算法相比,DFCM算法具有较好的聚类效果。     

基于自适应近邻参数的密度峰聚类算法

针对基于共享最近邻的密度峰聚类算法中的近邻参数需要人为设定的问题,提出了一种基于自适应近邻参数的密度峰聚类算法。首先,利用所提出的近邻参数搜索算法自动获得近邻参数;然后,通过决策图选取聚类中心;最后,根据所提出的代表点分配策略,先分配代表点,后分配非代表点,从而实现所有样本点的聚类。将所提出的算法与基于共享最近邻的快速密度峰搜索聚类（SNN?DPC）、基于密度峰值的聚类（DPC）、近邻传播聚类（AP）、对点排序来确定聚类结构（OPTICS）、基于密度的噪声应用空间聚类（DBSCAN）和K-means这6种算法在合成数据集以及UCI数据集上进行聚类结果对比。实验结果表明,所提出的算法在调整互信息（AMI）、调整兰德系数（ARI）和FM指数（FMI）等评价指标上整体优于其他6种算法。所提算法能自动获得有效的近邻参数,且能较好地分配簇边缘区域的样本点。     

基于自然最近邻的密度峰值聚类算法

针对密度峰值聚类算法(Density Peaks Clustering,DPC)需要人为指定截断距离d c,以及局部密度定义简单和一步分配策略导致算法在复杂数据集上表现不佳的问题,提出了一种基于自然最近邻的密度峰值聚类算法(Density Peaks Clustering based on Natural Nearest Neighbor,NNN-DPC)。该算法无需指定任何参数,是一种非参数的聚类方法。该算法首先根据自然最近邻的定义,给出新的局部密度计算方法来描述数据的分布,揭示内在的联系;然后设计了两步分配策略来进行样本点的划分。最后定义了簇间相似度并提出了新的簇合并规则进行簇的合并,从而得到最终聚类结果。实验结果表明,在无需参数的情况下,NNN-DPC算法在各类数据集上都有优秀的泛化能力,对于流形数据或簇间密度差异大的数据能更加准确地识别聚类数目和分配样本点。与DPC、FKNN-DPC(Fuzzy Weighted K-nearest Density Peak Clustering)以及其他3种经典聚类算法的性能指标相比,NNN-DPC算法更具优势。     

基于密度峰值和近邻优化的聚类算法

针对密度峰值算法在选取聚类中心时的时间复杂度过高,需要人工选择截断距离并且处理流形数据时有可能出现多个密度峰值,导致聚类准确率下降等问题,提出一种新的密度峰值聚类算法,从聚类中心选择、离群点筛选、数据点分配三方面进行讨论和分析,并给出相应的聚类算法。在聚类中心的选择上采取KNN的思想计算数据点的密度,离群点的筛选和剪枝以及数据点分配则利用Voronoi图的性质,结合数据点的分布特征进行处理,并在最后应用层次聚类的思想以合并相似类簇,提高聚类准确率。实验结果表明:所提算法与实验对比算法相比较,具有较好的聚类效果和准确性。     

基于密度峰和划分的快速聚类算法

传统基于划分的聚类算法需要人工给定聚类数,且由于算法采取刚性划分,可能会导致将较大或延伸状的聚类簇分割的现象,导致错误的聚类结果。密度峰聚类是近年提出的一种新的基于密度的聚类算法,该算法不需要预先指定聚类数目,且能够发现非球形簇。将密度峰思想引入基于划分的聚类算法,提出一种基于密度峰和划分的快速聚类算法（DDBSCAN）,该算法首先获取一组簇的核心对象(密度峰),用于描述簇的“骨骼”,而后将周围的点划分到最近的核心对象,最后通过判断划分边界处的密度情况合并簇。实验证明,该算法能有效地适应任意形状、大小不一的数据集,与传统基于密度的聚类算法相比收敛速度更快。     

基于网格和最近邻居的聚类算法

针对目前已有的聚类算法不能很好地处理包含不同密度的簇数据,或者不能很好地区分相邻的密度相差不大的簇的问题,提出1种新的基于严格最近邻居和共享最近邻居的聚类算法．通过构造共享严格最近邻图,使样本点在密度一致的区域保持连接,而在密度不同的相邻区域断开连接,并尽可能去除噪声点和孤立点．该算法可以处理包含有不同密度的簇数据,而且在处理高维数据时具有较低的时间复杂度、实验结果证明,该算法能有效找出不同大小、形状和密度的聚类．     

A new hybrid method based on partitioning-based DBSCAN and ant clustering

Clustering problem is an unsupervised learning problem. It is a procedure that partition data objects into matching clusters. The data objects in the same cluster are quite similar to each other and dissimilar in the other clusters. Density-based clustering algorithms find clusters based on density of data points in a region. DBSCAN algorithm is one of the density-based clustering algorithms. It can discover clusters with arbitrary shapes and only requires two input parameters. DBSCAN has been proved to be very effective for analyzing large and complex spatial databases. However, DBSCAN needs large volume of memory support and often has difficulties with high-dimensional data and clusters of very different densities. So, partitioning-based DBSCAN algorithm (PDBSCAN) was proposed to solve these problems. But PDBSCAN will get poor result when the density of data is non-uniform. Meanwhile, to some extent, DBSCAN and PDBSCAN are both sensitive to the initial parameters. In this paper, we propose a new hybrid algorithm based on PDBSCAN. We use modified ant clustering algorithm (ACA) and design a new partitioning algorithm based on ‘point density’ (PD) in data preprocessing phase. We name the new hybrid algorithm PACA-DBSCAN. The performance of PACA-DBSCAN is compared with DBSCAN and PDBSCAN on five data sets. Experimental results indicate the superiority of PACA-DBSCAN algorithm.     

结合自然和共享最近邻的密度峰值聚类算法

基于快速搜索和寻找密度峰值聚类算法(DPC)具有无需迭代且需要较少参数的优点,但其仍然存在一些缺点:需要人为选取截断距离参数;在流形数据集上的处理效果不佳。针对这些问题,提出一种密度峰值聚类改进算法。该算法结合了自然和共享最近邻算法,重新定义了截断距离和局部密度的计算方法,并且算法融合了候选聚类中心计算概念,通过算法选出不同的候选聚类中心,然后以这些候选中心为新的数据集,再次开始密度峰值聚类,最后将剩余的点分配到所对应的候选中心点所在类簇中。改进的算法在合成数据集和UCI数据集上进行验证,并与K-means、DBSCAN和DPC算法进行比较。实验结果表明,提出的算法在性能方面有明显提升。     

一种基于相对密度和决策图的聚类算法

聚类是数据挖掘领域的一个重要研究方向,针对复杂数据集中存在的簇间密度不均匀、聚类形态多样、聚类中心的识别等问题,引入样本点k近邻信息计算样本点的相对密度,借鉴快速搜索和发现密度峰值聚类(CFSFDP)算法的簇中心点识别方法,提出一种基于相对密度和决策图的聚类算法,实现对任意分布形态数据集聚类中心快速、准确地识别和有效聚类.在7类典型测试数据集上的实验结果表明,所提出的聚类算法具有较好的适用性,与经典的DBSCAN算法和CFSFDP等算法相比,在没有显著提高时间复杂度的基础上,聚类效果更好,对不同类型数据集的适应性也更广.     

自适应聚合策略优化的密度峰值聚类算法

针对密度峰值聚类算法受人为干预影响较大和参数敏感的问题,即不正确的截断距离dc会导致错误的初始聚类中心,而且在某些情况下,即使设置了适当的dc值,仍然难以从决策图中人为选择初始聚类中心。为克服这些缺陷,提出一种新的基于密度峰值的聚类算法。该算法首先根据K近邻的思想来确定数据点的局部密度,然后提出一种新的自适应聚合策略,即首先通过算法给出阈值判断初始类簇中心,然后依据离初始类簇中心最近分配剩余点,最后通过类簇间密度可达来合并相似类簇。在实验中,该算法在合成和实际数据集中的表现比DPC、DBSCAN、KNNDPC和K-means算法要好,能有效提高聚类准确率和质量。     

基于密度和层次的快速聚类算法在数据挖掘中的设计及实现

本论文在对各种算法深入分析的基础上,尤其在对基于密度的聚类算法he基于层次的聚类算法深入研究的基础上,提出了一种全新的基于密度和层次的快速聚类算法。该算法保持了基于密度聚类算法发现任意形状簇的优点,而且具有近似线性的时间复杂性,因此该算法适合对大规模数据的挖掘。理论分析和实验结果也证明了基于密度和层次的聚类算法具有处理任意形状簇的聚类、对噪音数据不敏感的特点,并且其执行效率明显高于传统的DBSCAN算法。