面向密度分布不均数据的加权逆近邻密度峰值聚类算法

针对密度分布不均数据,密度峰值聚类算法易忽略类簇间样本的疏密差异,导致误选类簇中心;分配策略易将稀疏区域的样本误分到密集区域,导致聚类效果不佳的问题,本文提出一种面向密度分布不均数据的加权逆近邻密度峰值聚类算法。该算法首先在局部密度公式中引入基于sigmoid函数的权重系数,增加稀疏区域样本的权重,结合逆近邻思想,重新定义了样本的局部密度,有效提升类簇中心的识别率;其次,引入改进的样本相似度策略,利用样本间的逆近邻及共享逆近邻信息,使得同一类簇样本间具有较高的相似度,可有效改善稀疏区域样本分配错误的问题。在密度分布不均、复杂形态和UCI数据集上的对比实验表明,本文算法的聚类效果优于IDPC-FA、FNDPC、FKNN-DPC、DPC和DPCSA算法。     

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

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

K近邻和加权相似性的密度峰值聚类算法

密度峰值聚类算法的局部密度定义未考虑密度分布不均数据类簇间的样本密度差异影响, 易导致误选类簇中心; 其分配策略依据欧氏距离通过密度峰值进行链式分配, 而流形数据通常有较多样本距离其密度峰值较远, 导致大量本应属于同一个类簇的样本被错误分配给其他类簇, 致使聚类精度不高. 鉴于此, 本文提出了一种K近邻和加权相似性的密度峰值聚类算法. 该算法基于样本的K近邻信息重新定义了样本局部密度, 此定义方式可以调节样本局部密度的大小, 能够准确找到密度峰值; 采用样本的共享最近邻及自然最近邻信息定义样本间的相似性, 摒弃了欧氏距离对分配策略的影响, 避免了样本分配策略产生的错误连带效应. 流形及密度分布不均数据集上的对比实验表明, 本文算法能准确找到疏密程度相差较大数据集的密度峰值, 避免了流形数据的分配错误连带效应, 得到了满意的聚类效果; 同时在真实数据集上的聚类效果也十分优秀.     

面向密度分布不均数据的近邻优化密度峰值聚类算法

密度分布不均数据是指类簇间样本分布疏密程度不同的数据.密度峰值聚类(DPC)算法在处理密度分布不均数据时,倾向于在密度较高区域内找到类簇中心,并易将稀疏类簇的样本分配给密集类簇.为避免上述缺陷,提出一种面向密度分布不均数据的近邻优化密度峰值聚类(DPC-NNO)算法.DPC-NNO算法结合逆近邻和k近邻定义新的局部密度,提高稀疏样本的局部密度,使算法能更准确地找到类簇中心;定义分配策略时引入共享近邻,计算样本间相似性,构造相似矩阵,使同一类簇样本联系更紧密,避免错误分配样本.将所提出的DPC-NNO算法与IDPC-FA、DPCSA、FNDPC、FKNN-DPC、DPC算法进行对比,实验结果表明,DPC-NNO算法在处理密度分布不均数据时能获得优异的聚类效果,对于复杂数据集和UCI数据集,DPC-NNO算法的综合性能优于对比算法.     

基于K近邻和优化分配策略的密度峰值聚类算法

密度峰值聚类(density peak clustering, DPC)是一种简单有效的聚类分析方法.但在实际应用中,对于簇间密度差别大或者簇中存在多密度峰的数据集,DPC很难选择正确的簇中心;同时,DPC中点的分配方法存在多米诺骨牌效应.针对这些问题,提出一种基于K近邻(K-nearest neighbors,KNN)和优化分配策略的密度峰值聚类算法.首先,基于KNN、点的局部密度和边界点确定候选簇中心;定义路径距离以反映候选簇中心之间的相似度,基于路径距离提出密度因子和距离因子来量化候选簇中心作为簇中心的可能性,确定簇中心.然后,为了提升点的分配的准确性,依据共享近邻、高密度最近邻、密度差值和KNN之间距离构建相似度,并给出邻域、相似集和相似域等概念,以协助点的分配;根据相似域和边界点确定初始聚类结果,并基于簇中心获得中间聚类结果.最后,依据中间聚类结果和相似集,从簇中心到簇边界将簇划分为多层,分别设计点的分配策略;对于具体层次中的点,基于相似域和积极域提出积极值以确定点的分配顺序,将点分配给其积极域中占主导地位的簇,获得最终聚类结果.在11个合成数据集和27个真实数据集上进行仿真...     

基于相对密度估计和多簇合并的密度峰值聚类算法

密度峰值聚类(DPC)算法是一种新颖的基于密度的聚类算法,其原理简单、运行效率高.但DPC算法的局部密度只考虑了样本之间的距离,忽略了样本所处的环境,导致算法对密度分布不均数据的聚类效果不理想;同时,样本分配过程易产生分配错误连带效应.针对上述问题,提出一种基于相对密度估计和多簇合并的密度峰值聚类(DPC-RD-MCM)算法. DPC-RD-MCM算法结合K近邻和相对密度思想,定义了相对K近邻的局部密度,以降低类簇疏密程度对类簇中心的影响,避免稀疏区域没有类簇中心;重新定义微簇间相似性度量准则,通过多簇合并策略得到最终聚类结果,避免分配错误连带效应.在密度分布不均数据集、复杂形态数据集和UCI数据集上,将DPC-RD-MCM算法与DPC及其改进算法进行对比,实验结果表明:DPC-RD-MCM算法能够在密度分布不均数据上获得十分优异的聚类效果,在复杂形态数据集和UCI数据集的聚类性能上高于对比算法.     

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

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

优化分配策略的密度峰值聚类算法

针对密度峰值聚类算法在面对复杂结构数据集时容易出现分配错误的问题,提出一种优化分配策略的密度峰值聚类算法(ODPC)。新算法首先引入参数积γ,扩大了聚类中心的选取范围;然后使用改进的数据点分配策略,对数据集的数据点进行基于相似度指标MS的重新分配,进一步优化了簇类中点集的分配;最后使用dc近邻法优化识别数据集的噪声点。在人工数据集及UCI真实数据集上的实验均可证明,新算法能够在优化噪声识别的同时,提高复杂流形数据集中数据点分配的正确率,并取得比DPC算法、DenPEHC算法、GDPC算法更好的聚类效果。     

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

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

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

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

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

针对密度峰值聚类算法(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算法更具优势。     

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

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

基于共享k-近邻与共享逆近邻的密度峰聚类

为了更好地解决密度不均衡问题与刻画高维数据相似性度量问题，提出一种基于共享[k]-近邻与共享逆近邻的密度峰聚类算法。该算法计算两个点的共享[k]-近邻数与共享逆近邻数，并结合欧氏距离来确定这两个点之间的共享相似度；将样本点与其逆近邻点的共享相似度之和定义为该点的共享密度，再通过共享密度选取聚类中心。通过实验证明，该算法在人工数据集和真实数据集上的聚类结果较其他密度聚类算法更加准确，并且能更好地处理密度不均衡问题，同时也提高了高维数据的聚类精度。     

面向大数据处理的并行优化抽样聚类K-means算法

针对大数据环境下K-means聚类算法聚类精度不足和收敛速度慢的问题,提出一种基于优化抽样聚类的K-means算法(OSCK)。首先,该算法从海量数据中概率抽样多个样本;其次,基于最佳聚类中心的欧氏距离相似性原理,建模评估样本聚类结果并去除抽样聚类结果的次优解;最后,加权整合评估得到的聚类结果得到最终k个聚类中心,并将这k个聚类中心作为大数据集聚类中心。理论分析和实验结果表明,OSCK面向海量数据分析相对于对比算法具有更好的聚类精度,并且具有很强的稳健性和可扩展性。     

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

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

一种基于K近邻的比较密度峰值聚类算法

快速搜索与发现密度峰值聚类算法（Fast Search and Discovery Density Peak Clustering Algorithm，CFSFDP）的聚类效果十分依赖截断距离[dc]的主观选取，而最佳[dc]值的确定并不容易，并且当处理分布复杂、密度变化大的数据集时，算法生成的决策图中类簇中心点与非类簇中心点的区分不够明显，使类簇中心的选取变得困难。针对这些问题，对其算法进行了优化，并提出了基于K近邻的比较密度峰值聚类算法（Comparative Density Peak Clustering algorithm Based on K-Nearest Neighbors，CDPC-KNN）。算法结合K近邻概念重新定义了截断距离和局部密度的度量方法，对任意数据集能自适应地生成截断距离，并使局部密度的计算结果更符合数据的真实分布。同时在决策图中引入距离比较量代替原距离参数，使类簇中心在决策图上更加明显。通过实验验证，CDPC-KNN算法的聚类效果整体上优于CFSFDP算法与DBSCAN算法，分离度实验表明新算法使类簇中心与非类簇中心点的区分度得到有效提高。     

基于K近邻的众包数据分类算法

针对众包数据处理中的质量控制问题,提出了一种加权K近邻投票分类方法。该方法不单单只是考虑了某个样例的标记来返回一个答案,而是通过综合考虑样例的近邻来得到更加准确的答案。同时对样例的近邻加以适当的权重来进一步提高算法的性能,并保持了传统多数投票分类的简单性。K近邻投票分类算法可以有效地解决缺乏标记的情况,通过对近邻加以权重可以解决不平衡标记造成的影响,从而使算法的泛化性更强。通过各种场景下的实验,结果表明加权K近邻投票分类方法取得了很好的效果。