一种优化初始点与自适应半径的密度聚类算法

传统DBSCAN算法不能正确聚类密度不均匀的数据集,聚类结果受邻域阈值和密度阈值参数的影响较大。提出一种新的优化初始点和自适应半径的密度聚类算法。利用反向最近邻和相似度矩阵发现当前全局密度最大的数据样本,分析该样本周围密度的分布情况,采用自适应的方法计算当前簇的邻域阈值,并利用DBSCAN算法进行聚类。在人工数据集和UCI数据集上进行测试的结果表明,与经典的DBSCAN、OPTICS、RNN-DBSCAN算法相比,优化初始点和自适应半径的密度聚类算法在ARI、NMI、Homogeneity、Completeness和V-measure 5个评价指标上整体取得最优值,其中在Compound、Jain等数据集上达到1.0,具有较高的聚类效率和准确度。     

基于加权共享近邻与累加序列的密度峰值算法

密度峰值聚类（DPC）算法在对密度分布差异较大的数据进行聚类时效果不佳,聚类结果受局部密度及其相对距离影响,且需要手动选取聚类中心,从而降低了算法的准确性与稳定性。为此,提出一种基于加权共享近邻与累加序列的密度峰值算法DPC-WSNN。基于加权共享近邻重新定义局部密度的计算方式,以避免截断距离选取不当对聚类效果的影响,同时有效处理不同类簇数据集分布不均的问题。在原有DPC算法决策值的基础上,生成一组累加序列,将累加序列的均值作为聚类中心和非聚类中心的临界点从而实现聚类中心的自动选取。利用人工合成数据集与UCI上的真实数据集测试与评估DPC-WSNN算法,并将其与FKNN-DPC、DPC、DBSCAN等算法进行比较,结果表明,DPC-WSNN算法具有更好的聚类表现,聚类准确率较高,鲁棒性较强。     

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

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

基于相互邻近度的密度峰值聚类算法

密度峰值聚类算法对密集程度不一数据的聚类效果不佳,样本分配过程易产生连带错误.为此,提出一种基于相互邻近度的密度峰值聚类算法.所提算法引入k近邻思想计算局部密度,以此保证密度的相对性.定义综合数据全局和局部特征的样本相互邻近度的度量准则,据此准则,提出一种新的样本分配策略.新的分配策略采用k近邻思想寻找密度峰值,将密度峰值的k个近邻点分配给其对应类簇,对所有已分配数据点寻找相互邻近度最高的未分配数据点,将未分配数据点分配给已分配数据点所在类簇.在合成和UCI数据集上,将所提算法与DPC、DBSCAN、OPTICS、AP、K-Means及DPC的改进算法进行比较,实验结果表明,所提出的算法性能最优.     

一种改进的谱聚类算法

谱聚类算法是基于谱图理论的一类新的聚类算法,能对任意形状的数据进行划分,已经被成功应用到图像分割等领域.但谱聚类很难正确发现密度相差比较大的簇,参数的选取要靠多次实验和个人经验.结合DBSCAN的思想,充分考虑数据的局部结构,提出了一种基于近邻自适应尺度的改进谱聚类算法.其基本思想是根据数据点的近邻分布,对每个点设置一个近邻自适应尺度,代替标准谱聚类算法中的全局统一尺度.近邻自适应尺度简化了参数的选取,使得新算法对密度的变化不敏感,对离群点有一定的鲁棒性,同时比标准谱聚类更适合任意形状的数据分布.通过与传统的聚类算法和常见的谱聚类算法做比较,在人工数据集和实际数据集UCI上的实验都验证了本算法能够获得更好的聚类效果.     

基于kNN-DBSCAN的缺失数据填补优化算法

针对传统的kNN(k-NearestNeighbor)近邻填补算法对缺失数据的填补效果会因为k最近邻数据存在噪声受到较大干扰的问题,提出一种基于kNN-DBSCAN(k-NearestNeighbor Density-based Spatial Clustering of Applications with Noise)的缺失数据填补优化算法。将基于密度的DBSCAN聚类算法运用到kNN近邻填补算法中,先用kNN算法得到目标填补数据的原始k最近邻数据集,运用DBSCAN聚类算法对原始k最近邻数据集进行噪声检测并消除噪声数据,得到当前k最近邻数据集,最后并入kNN计算,填补目标缺失数据;同时,针对DBSCAN聚类算法参数设置敏感的问题,通过分析数据集的统计特性来确定参数,避免人为经验判断。最后利用真实数据对算法进行验证,结果显示该算法对目标缺失数据的填补准确度要优于传统的kNN算法。     

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

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

快速搜索与发现密度峰值聚类算法的优化研究

CFSFDP是基于密度的新聚类算法,可聚类非球形数据集,具有聚类速度快实现简单等优点。CFSFDP需人工尝试确定密度阈值dc且对一个类中存在多密度峰值的数据无法进行准确聚类,为解决该缺点,本文提出基于近邻距离曲线和类合并优化CFSFDP（简称 NM-CFSFDP）的聚类算法。首先,算法用近邻距离曲线变化情况自动确定密度阈值dc;然后,用本文提出自动确定dc的CFSFDP对数据聚类;最后用本文计算dc值的方法指导类的合并,引入内聚程度衡量参数解决了类合并后不能撤销的难题,从而实现对多密度峰值数据的正确聚类。通过实验对比,NM-CFSFDP算法确实比CFSFDP算法具有更加精确的聚类效果。     

针对非均匀数据集的DBSCAN过滤式改进算法*

针对在数据分布不均匀时,由于DBSCAN使用统一的全局变量,使得聚类的效果差,提出了一种基于过滤的DBSCAN算法。该算法的思想是：在调用传统的DBSCAN算法前,先对数据集进行预处理,针对所有点的k-dist数据进行一维聚类,自动计算出不同的Eps;然后再根据每个Eps分别调用传统的DBSCAN算法,从而找出非均匀数据集的各种聚类。实验结果表明,改进算法对密度不均匀的数据能够有效聚类。     

基于代表点与K近邻的密度峰值聚类算法

密度峰值聚类(density peaks clustering, DPC)是一种基于密度的聚类算法,该算法可以直观地确定类簇数量,识别任意形状的类簇,并且自动检测、排除异常点.然而, DPC仍存在些许不足:一方面, DPC算法仅考虑全局分布,在类簇密度差距较大的数据集聚类效果较差;另一方面, DPC中点的分配策略容易导致“多米诺效应”.为此,基于代表点(representative points)与K近邻(K-nearest neighbors, KNN)提出了RKNN-DPC算法.首先,构造了K近邻密度,再引入代表点刻画样本的全局分布,提出了新的局部密度;然后,利用样本的K近邻信息,提出一种加权的K近邻分配策略以缓解“多米诺效应”;最后,在人工数据集和真实数据集上与5种聚类算法进行了对比实验,实验结果表明,所提出的RKNN-DPC可以更准确地识别类簇中心并且获得更好的聚类结果.     

基于DBSCAN算法的城轨车站乘客聚集特征分析

发掘并掌握站内乘客群体的聚集时空变化规律,对于优化城市轨道交通线网间车辆的调度,特别是优化灾害条件下的客流组织管理等,具有积极的作用.针对具有密度分布非均匀特征的车站乘客位置数据集,提出一种基于高斯混合模型的DBSCAN聚类算法.首先,利用高斯混合模型对数据集进行密度的分层处理;然后,面向不同密度层次的数据集进行局部聚类,确定各密度层数据集的参数,并选取恰当的种子以完成局部聚类簇扩展;最后,将各密度层次数据集的聚类结果进行合并.通过标准和实测数据的计算结果表明,基于高斯混合模型优化后的DBSCAN算法,对于非均匀密度分布的乘客位置分布数据具有更好的聚类效果.     

基于加权K近邻的改进密度峰值聚类算法

密度峰值聚类算法是一种新颖的密度聚类算法,但是原算法仅仅考虑了数据的全局结构,在对分布不均匀的数据集进行聚类时效果不理想,并且原算法仅仅依据决策图上各点的分布情况来选取聚类中心,缺乏可靠的选取标准。针对上述问题,提出了一种基于加权K近邻的改进密度峰值聚类算法,将最近邻算法的思想引入密度峰值聚类算法,重新定义并计算了各数据点的局部密度,并通过权值斜率变化趋势来判别聚类中心临界点。通过在人工数据集上与UCI真实数据集上的实验,将该改进算法与原密度峰值聚类、K-means及DBSCAN算法进行了对比,证明了改进算法能够在密度不均匀数据集上有效完成聚类,能够发现任意形状簇,且在三个聚类性能指标上普遍高于另外三种算法。     

复杂高维数据的密度峰值快速搜索聚类算法

机器学习的无监督聚类算法已被广泛应用于各种目标识别任务。基于密度峰值的快速搜索聚类算法(DPC)能快速有效地确定聚类中心点和类个数,但在处理复杂分布形状的数据和高维图像数据时仍存在聚类中心点不容易确定、类数偏少等问题。为了提高其处理复杂高维数据的鲁棒性,文中提出了一种基于学习特征表示的密度峰值快速搜索聚类算法(AE-MDPC)。该算法采用无监督的自动编码器(AutoEncoder)学出数据的最优特征表示,结合能刻画数据全局一致性的流形相似性,提高了同类数据间的紧致性和不同类数据间的分离性,促使潜在类中心点的密度值成为局部最大。在4个人工数据集和4个真实图像数据集上将AE-MDPC与经典的K-means,DBSCAN,DPC算法以及结合了PCA的DPC算法进行比较。实验结果表明,在外部评价指标聚类精度、内部评价指标调整互信息和调整兰德指数上,AE-MDPC的聚类性能优于对比算法,而且提供了更好的可视化性能。总之,基于特征表示学习且结合流形距离的AE-MDPC算法能有效地处理复杂流形数据和高维图像数据。     

基于数据场的改进DBSCAN聚类算法

DBSCAN(density based spatial clustering of applications with noise)算法是一种典型的基于密度的聚类算法。该算法可以识别任意形状的类簇,但聚类结果依赖于参数Eps和MinPts的选择,而且对于一些密度差别较大的数据集,可能得不到具有正确类簇个数的聚类结果,也可能将部分数据错分为噪声。为此,利用数据场能较好描述数据分布,反映数据关系的优势,提出了一种基于数据场的改进DBSCAN聚类算法。该算法引入平均势差的概念,在聚类过程中动态地确定每个类的Eps和平均势差,从而能够在一些密度相差较大的数据集上得到较好的聚类结果。实验表明,所提算法的性能优于DBSCAN算法。     

基于区域划分的DBSCAN多密度聚类算法*

DBSCAN聚类算法使用固定的Eps和Minpts,处理多密度的数据效果不理想;并且算法的时间复杂度为O(n2)。针对以上问题,提出一种基于区域划分的DBSCAN多密度聚类算法。算法利用网格相对密度差把数据空间划分成密度不同的区域,每个区域的Eps根据该区域的密度计算自动获得,并利用DBSCAN算法进行聚类,提升了DBSCAN的精度;避免了DBSCAN在查找密度相连时需要遍历所有数据,从而改善了算法效率。实验表明算法能有效地对多密度数据进行聚类,对各种数据的适应力较强,效率较优。     

不确定数据的最优?? 近邻和局部密度聚类算法

传统聚类算法一般针对的是确定数据, 无法解决不确定数据的聚类问题; 现有基于密度的不确定数据聚类算法存在参数敏感且计算率低的问题. 对此, 在引进新的不确定数据相异度函数、最优?? 近邻、局部密度和互包含概念的基础上, 提出解决不确定数据聚类问题的不确定数据的最优?? 近邻和局部密度聚类(OLUC) 算法. 该算法不仅能降低参数敏感性, 提高计算效率, 而且具有动态自适应优化?? 近邻, 快速发现聚类中心和除噪优化的能力. 实验结果表明, 所提出的算法对无论是否存在噪声的不确定数据集都效果良好.

     

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

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

一种基于共享近邻的密度峰值聚类算法

基于加权K近邻的密度峰值发现算法(FKNN-DPC)是一种简单、高效的聚类算法,能够自动发现簇中心,并采用加权K近邻的思想快速、准确地完成对非簇中心样本的分配,在各种规模、任意维度、任意形状的数据集上都能得到高质量的聚类结果,但其样本分配策略中的权重仅考虑了样本间的欧氏距离。文中提出了一种基于共享近邻的相似度度量方式,并以此相似度改进样本分配策略,使得样本的分配更符合真实的簇归属情况,从而提高聚类质量。在UCI真实数据集上进行实验,并将所提算法与K-means,DBSCAN,AP,DPC,FKNN-DPC等算法进行对比,验证了其有效性。     

基于二阶k近邻的密度峰值聚类算法研究

密度峰值聚类(DPC)是近年来提出的一种新的密度聚类算法,算法的核心是基于局部密度和相对距离,通过画出决策图,人为选定聚类中心,进而完成聚类.DPC算法利用截断距离计算局部密度,本质上只考虑了周围近邻节点的数量,且算法采用单步分配策略,一定程度上限制了算法对任意数据集的计算精度和有效性.针对上述问题,提出基于二阶k近邻的密度峰值聚类算法(SODPC).算法通过引入节点的二阶k近邻,计算直接密度和间接密度,重新定义局部密度的计算方式.在此基础上,定义非中心节点的多步骤分配策略完成聚类.通过人工和真实数据的测试,证明了该算法对不规则、密度不均匀的数据集具有较好的聚类效果.     

结合K近邻的改进密度峰值聚类算法

针对密度峰值聚类算法（DPC）在处理维数较高、含噪声及结构复杂数据集时聚类性能不佳问题,提出一种结合K近邻的改进密度峰值聚类算法（IDPCA）。该算法首先给出新的局部密度度量方法来描述每个样本在空间中的分布情况,然后引入核心点的概念并结合K近邻思想设计了全局搜索分配策略,通过不断将核心点的未分配K近邻正确归类以加快聚类速度,进而提出一种基于K近邻加权的统计学习分配策略,利用剩余点的K近邻加权信息来确定其被分配到各局部类的概率,有效提高了聚类质量。实验结果表明,IDPCA算法在21个典型的测试数据集上均有良好的适用性,而在与DPC算法及另外3种典型聚类算法的性能指标对比上,其优势更为明显。