面向复杂簇的聚类算法研究与实现

有效聚类各种复杂的数据对象簇是聚类算法应用干事务对象划分、图像分割、机器学习等方面需要解决的关键技术.在分析与研究现有聚类算法的基础上,提出一种基于密度和自适应密度可达的改进算法.实验证明,该算法能够有效聚类任意分布形状、不同密度、不同尺度的簇;同时,算法的计算复杂度与传统基于密度的聚类算法相比有明显的降低.     

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

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

基于密度可达的多密度聚类算法

为对多密度数据集聚类,提出一种基于密度可达的多密度聚类算法。使用网格划分技术来提高计算每个点密度值的效率,每次聚类都是从最高密度点开始,根据密度可达的概念和广度优先的策略逐步向外扩展进行聚类。实验表明,该算法能够有效地对任意形状、大小的均匀数据集和多密度数据集进行聚类,并能较好地识别出孤立点和噪声,其精度和效率优于SNN算法。     

基于相对密度的密度峰值聚类算法

密度峰值聚类算法在处理密度不均匀的数据集时易将低密度簇划分到高密度簇中或将高密度簇分为多个子簇,且在样本点分配过程中存在误差传递问题。提出一种基于相对密度的密度峰值聚类算法。引入自然最近邻域内的样本点信息,给出新的局部密度计算方法并计算相对密度。在绘制决策图确定聚类中心后,基于对簇间密度差异的考虑,提出密度因子计算各个簇的聚类距离,根据聚类距离对剩余样本点进行划分,实现不同形状、不同密度数据集的聚类。在合成数据集和真实数据集上进行实验,结果表明,该算法的FMI、ARI和NMI指标较经典的密度峰值聚类算法和其他3种聚类算法分别平均提高约14、26和21个百分点,并且在簇间密度相差较大的数据集上能够准确识别聚类中心和分配剩余的样本点。     

一种基于密度和网格的簇心可确定聚类算法

以网格化数据集来减少聚类过程中的计算复杂度,提出一种基于密度和网格的簇心可确定聚类算法.首先网格化数据集空间,以落在单位网格对象里的数据点数表示该网格对象的密度值,以该网格到更高密度网格对象的最近距离作为该网格的距离值;然后根据簇心网格对象同时拥有较高的密度和较大的距离值的特征,确定簇心网格对象,再通过一种基于密度的划分方式完成聚类;最后,在多个数据集上对所提出算法与一些现有聚类算法进行聚类准确性与执行时间的对比实验,验证了所提出算法具有较高的聚类准确性和较快的执行速度.     

基于密度复杂簇聚类算法研究与实现

聚类算法在模式识别、数据分析、图像处理、以及市场研究的应用中,需要解决的关键技术是如何有效地聚类各种复杂的数据对象簇。在分析与研究现有聚类算法的基础上,提出了一种基于密度和自适应密度可达的改进算法。实验证明,该算法能够有效聚类任意分布形状、不同密度、不同尺度的簇;同时,算法的计算复杂度与传统基于密度的聚类算法相比有明显的降低。     

自动确定聚类中心的密度峰聚类

密度峰聚类是一种新的基于密度的聚类算法,该算法不需要预先指定聚类数目,能够发现非球形簇。针对密度峰聚类算法需要人工确定聚类中心的缺陷,提出了一种自动确定聚类中心的密度峰聚类算法。首先,计算每个数据点的局部密度和该点到具有更高密度数据点的最短距离;其次,根据排序图自动确定聚类中心;最后,将剩下的每个数据点分配到比其密度更高且距其最近的数据点所属的类别,并根据边界密度识别噪声点,得到聚类结果。将新算法与原密度峰算法进行对比,在人工数据集和UCI数据集上的实验表明,新算法不仅能够自动确定聚类中心,而且具有更高的准确率。     

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

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

一种基于网格框架下改进的多密度SNN聚类算法

针对数据集中数据分布密度不均匀以及存在噪声点,噪声点容易导致样本聚类时产生较大的偏差问题,提出一种基于网络框架下改进的多密度SNN聚类算法。网格化递归划分数据空间成密度不同的网格,对高密度网格单元作为类簇中心,利用网格相对密度差检测出在簇边界网格中包含噪声点;使用改进的SNN聚类算法计算边界网格内样本数据点的局部密度,通过数据密度特征分布对噪声点进行类簇分配,从而提高聚类算法的鲁棒性。在UCI高维的数据集上的实验结果表明,与传统的算法相比,该算法通过网格划分数据空间和局部密度峰值进行样本类簇分配,有效地平衡聚类效果和时间性能。     

自然邻居密度极值聚类算法

针对密度峰值聚类算法存在数据集密度差异较大时,低密度区域聚类中心难以检测和参数敏感的问题,提出了一种新型密度极值算法。引入自然邻居概念寻找数据对象自然近邻,定义椭圆模型计算自然稳定状态下数据局部密度;计算数据对象余弦相似性值,用余弦相似性值来更新数据对象连通值,采用连通值划分高低密度区域和离群点;构造密度极值函数找到高低密度不同区域聚类中心点;将不同区域非聚类中心点归并到离其最近的聚类中心所在簇中。通过在合成数据集和UCI公共数据集实验分析：该算法比其他对比算法在处理密度分布差异较大数据集上取得了更好的结果。     

基于网格密度和局部敏感哈希函数的并行化聚类算法

针对大数据背景下基于划分的聚类算法中存在初始中心敏感,节点间通信开销大以及集群效率低下等问题,提出了基于网格密度和局部敏感哈希函数的PBGDLSH-MR并行化聚类算法。首先,对初始数据集提出网格密度策略(GDS)获取初始中心点,有效避免了随机选取引起的初始中心敏感的问题;其次,提出基于局部敏感哈希函数的数据分区(DP-LSH)用于投射关联性较大的数据对象到同一子数据集中,得到map上的数据分区,并设计相似性度量公式(SI)对数据分区结果进行评价,从而降低了节点间的通信开销;接着设计自适应分组策略(AGS)处理数据分区中数据倾斜的问题,进而有效地提高了集群效率;最后,结合MapReduce计算模型并行挖掘簇中心,生成最终聚类结果。实验结果表明,PBGDLSH-MR算法的聚类效果更佳,同时在大数据环境下能有效地提高并行计算的效率。     

基于Spark并行的密度峰值聚类算法

针对FSDP聚类算法在计算数据对象的局部密度与最小距离时,由于需要遍历整个数据集而导致算法的整体时间复杂度较高的问题,提出了一种基于Spark的并行FSDP聚类算法SFSDP。首先,通过空间网格划分将待聚类数据集划分成多个数据量相对均衡的数据分区;然后,利用改进的FSDP聚类算法并行地对各个分区内的数据执行聚类分析;最后,通过将分区间的局部簇集合并,生成全局簇集。实验结果表明,SFSDP与FSDP算法相比能够有效地进行大规模数据集的聚类分析,并且算法在准确性和扩展性方面都有很好的表现。     

一种改进的K-Prototypes聚类算法

针对K-Prototypes聚类算法中人为指定初始聚类中心和聚类数目导致算法准确度和稳定性低下的问题,提出了基于密度优化的K-Prototypes聚类算法,该算法根据数据对象的密度分布,自适应地优化聚类数目和初始聚类中心的设置,并通过区分每个属性对聚类结果的不同影响权重,改进相异度计算公式,提升聚类的准确度。在合成数据集和UCI数据集上实验结果表明,该算法与K-Prototypes算法、DPCM算法和Fuzzy K-Prototypes算法相比,平均准确率分别提高了8.52%、4.28%和8.33%,达到了相对较好的聚类结果。     

基于密度峰值优化的谱聚类算法

针对经典谱聚类算法无法自适应确定聚类数目、以及在处理大数据量的聚类问题时效率不高的问题,本文提出了一种基于密度峰值优化的谱聚类算法。该方法首先计算数据对象的局部密度,以及每个数据对象与较其他数据对象的最小距离,并依据一定的规则自适应产生初始聚类中心,确定聚类数目。其次,使用Nystr?m抽样来降低特征分解的计算复杂度以达到提高谱聚类算法的效率。实验结果表明,本文方法能够准确地得到聚类数目,并且有效提高聚类的准确率和效率。     

基于网格的快速搜寻密度峰值的聚类算法优化研究

CFSFDP是基于密度的新型聚类算法,可聚类非球形数据集,具有聚类速度快、实现简单等优点。然而该算法在指定全局密度阈值dc时未考虑数据空间分布特性,导致聚类质量下降,且无法对多密度峰值的数据集准确聚类。针对以上缺点,提出基于网格分区的CFSFDP(简称GbCFSFDP)聚类算法。该算法利用网格分区方法将数据集进行分区,并对各分区进行局部聚类,避免使用全局dc,然后进行子类合并,实现对数据密度与类间距分布不均匀及多密度峰值的数据集准确聚类。两个典型数据集的仿真实验表明,GbCFSFDP算法比CFSFDP算法具有更加精确的聚类效果。     

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.     

基于密度期望和有效性指标的尽均值算法

传统尽均值聚类算法虽然收敛速度快,但存在聚类数后无法预先确定,并且算法对初始中心点敏感的缺点。针对上述缺点,提出了基于密度期望和聚类有效性Silhouette指标的K-均值优化算法。给出了基于密度期望的初始中心点选取方案,将处于密度期望区间内相距最远的石个样本作为初始聚类中心。该方案可有效降低尽均值算法对初始中心点的依赖,从而获得较高的聚类质量。在此基础上,可进一步通过选择合适的聚类有效性指标Silhouette4指标分析不同后值下的每次聚类结果,确定最佳聚类数,则可有效改善k-值无法预先确定的缺点。实验及分析结果验证了所提出方案的可行性和有效性。     

基于网格的带有参考参数的聚类算法

提出一种基于网格的带有参考参数的聚类算法,通过密度阈值数组的计算,为用户提供有效的参考参数,不但能满足一般的聚类要求,而且还能将高密度的聚类从低密度的聚类中分离出来,解决了传统网格聚类算法在划分网格时很少考虑数据分布导致聚类质量降低的问题。实验仿真表明,该算法能有效处理任意形状和大小的聚类,很好地识别出孤立点或噪声,并且有较好的精度。     

Self-Organizing-Map Based Clustering Using a Local Clustering Validity Index

Classical clustering methods, such as partitioning and hierarchical clustering algorithms, often fail to deliver satisfactory results, given clusters of arbitrary shapes. Motivated by a clustering validity index based on inter-cluster and intra-cluster density, we propose that the clustering validity index be used not only globally to find optimal partitions of input data, but also locally to determine which two neighboring clusters are to be merged in a hierarchical clustering of Self-Organizing Map (SOM). A new two-level SOM-based clustering algorithm using the clustering validity index is also proposed. Experimental results on synthetic and real data sets demonstrate that the proposed clustering algorithm is able to cluster data in a better way than classical clustering algorithms on an SOM.     

SUDBC:一种基于空间单元密度的快速聚类算法

随着数据规模越来越大,要求聚类算法有很高的执行效率,很好的扩展性,能发现任意形状的聚类以及对噪音数据的不敏感性.提出了一种基于空间单元密度的快速聚类算法SUDBC,该算法首先将被聚类的数据划分成若干个空间单元,然后基于空间单元密度将密度超过给定阈值的邻居单元合并为一个类.实验结果验证了SUDBC算法具有处理任意形状的数据和对噪音数据不敏感的特点.