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

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

融合转移概率矩阵的多阶最近邻图聚类算法

聚类是根据样本之间的相似性将数据集划分为多个类簇。现有的大多数聚类方法都存在两个挑战:一方面,在定义样本间相似性时往往没有考虑样本的空间分布结构,无法构建稳定的相似度矩阵;另一方面,图聚类构造的样本图结构过于复杂,计算成本较高。为解决这两个问题,提出融合转移概率矩阵的多阶最近邻图聚类算法(MNNGC)。首先,综合样本的近邻关系和空间分布结构,将共享近邻定义的相似度进行趋密性加权,得到节点间的趋密性亲和矩阵;其次,利用节点间多阶概率转移预测非邻接点的关联程度,并通过融合多阶转移概率矩阵得到稳定的节点间亲和矩阵;再次,为进一步增强图局部结构,重新构建节点的多阶最近邻图,并对多阶最近邻图的局部结构分层聚类;最后,优化了边缘点分配策略。定位实验结果表明,MNNGC在合成数据集上的准确率(Acc)均优于对比算法,且在8个UCI数据集上的Acc为最大值。其中在Compound数据集上,MNNGC的Acc、调整互信息(AMI)、调整兰德指数(ARI)和FM指数(FMI)相较于基于局部密度峰值的谱聚类(LDP-SC)算法分别提高38.6、27.2、45.4、35.1个百分点。

基于共享最近邻的自适应密度峰值聚类算法

密度峰值聚类算法(DPC)是一种简单高效的无监督聚类算法,该算法虽能自动发现簇中心,实现任意形状数据的高效聚类,但依然存在一些缺陷。针对密度峰值聚类算法在定义相关度量值时未考虑数据的位置信息、聚类中心数目需要人工预先设定且分配样本点时易出现连锁反应这3个缺陷,提出一种基于共享最近邻的自适应密度峰值聚类算法。首先,利用共享最近邻重新定义局部密度等度量值,充分考虑了数据分布的局部特点,使样本点的空间分布特征得以更好地体现;其次,通过引入密度衰减现象让样本点自动聚集成微簇,实现了簇个数自适应确定和簇中心自适应选取;最后,提出一种两阶段的分配方法,先将微簇合并形成簇的主干部分,再用上一步分配好的簇主干指导剩余点的分配,避免了链式反应的发生。在二维合成数据集以及UCI数据集上的实现表明,相较于经典的密度峰值聚类算法及近年来对其提出的改进算法,在大多数情况下,所提算法表现出更优异的性能。

基于共享邻近度和概率分配的密度峰值聚类算法

针对密度峰值聚类(DPC)算法难以准确找到流形数据的类簇中心以及剩余样本点分配过程易发生连带错误等问题,提出了一种基于共享邻近度和概率分配的密度峰值聚类(SP-DPC)算法。基于K近邻和共享K近邻定义了样本点间的共享邻近度,使用共享邻近度重新定义了样本点的局部密度,从而找到正确的类簇中心;利用样本点的K近邻信息,提出传递概率分配策略和证据概率分配策略共同优化剩余样本点的分配,从而避免分配连带错误;在17个合成数据集和12个UCI数据集上进行实验,将SP-DPC算法与DPC算法、SKM-DPC算法、DPC-NN算法、DBSCAN算法、K-means算法进行对比,实验结果表明SP-DPC算法在AMI、ARI、FMI这3个评价指标上整体取得了相对最优值,聚类效果优于其他对比算法。

基于改进密度峰值算法的轨迹聚类

为解决用户群体移动轨迹划分和密度峰值聚类算法自身局限性的问题,以校园轨迹为对象,考虑时间和位置语义信息层面的信息,建立网络用户间的相似性度量模型,提出一种基于共享近邻贡献度的密度峰值聚类算法(density peak clustering based on shared nearest neighbor contribution,SNNC-DPC),结合信息熵理论,通过最小化局部密度熵自适应选择截断距离;在局部密度计算上,利用共享近邻贡献度重新计算局部密度,更加全面地反映数据分布的特性;采用非线性变换方法选取决策值,解决聚类中心选取困难且方法单一的问题。在真实校园轨迹数据集上实验,验证了改进算法的有效性。

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

针对经典的快速漂移(Quick Shift)算法在偏移过程中需要人为地指定领域值,导致在复杂数据集上表现不佳等问题,提出一种改进的共享近邻密度聚类算法(QS-SNN)。该聚类算法基于共享近邻(SNN),计算出样本点之间的相似度;通过相似度衡量得到样本点的局部密度矩阵;通过在SNN领域中对样本点进行快速偏移,得到最终的聚类结果。在多个数据集上进行实验,结果分析表明,该算法比传统的Quick shift算法以及其他的聚类算法在准确度上有了较大的提升。

基于共享近邻的自适应谱聚类

谱聚类是一种极具竞争力的聚类算法.相似度定义对谱聚类算法的性能有至关重要的影响.本文用两点的共享近邻数目表征局部密度,从而获知隐含的簇结构信息.将这一信息与自调节的高斯核函数结合,提出了基于共享近邻的自适应相似度及相应的谱聚类算法.它满足聚类假设的要求,具有局部密度的自适应性,能有效识别数据点之间的内在联系.典型人工和真实数据集上的实验结果证明了算法的有效性.

基于改进的凝聚性和分离性的层次聚类算法

由于传统的数据聚类算法都是在单一表上进行,因此如何在多表中进行聚类是现在聚类分析的一个新方向.提出了一种基于改进的凝聚性和分离性的层次聚类算法——ICCSH(a hierarchical clustering algorithmbased oni mproved cluster cohesion and separation) ,该算法首先通过ID传播把关系数据库中的各个表联系起来,再通过计算共享最近邻的相似度和改进的凝聚性算法将数据对象聚类为大量相对较小的子聚类,然后通过计算改进的簇间分离性合并子类来找到真正的结果簇.实验表明,该算法不仅运行时间相对较短,具有较强的可伸缩性,还可以得到较高精确的聚类结果.

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

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

K均值聚类算法初始质心选择的改进

聚类分析在信息检索和数据挖掘等领域都有很广泛的应用,K均值聚类算法是一个比较简洁和快速的聚类算法,但是它存在着初始聚类个数必须事先设定以及初始质心的选择也具有随机性等缺陷,造成聚类的结果不是最优的。针对K均值聚类算法中的随机指定初始质心的缺点,提出了基于密度和最近邻相似度的初始质心选择算法,实验显示该算法可以生成质量较高而且较稳定的聚类结果,但是改进的算法需要事先设定最近邻相似度的阈值计算量较大等缺点,还有待改进。

基于高斯核函数的局部离群点检测算法

随着信息技术的快速发展,数据资源的结构越来越复杂,离群点挖掘受到越来越多人关注.基于高斯核函数,考虑数据对象的k个最近邻居,反向k近邻居和共享最近邻居三种邻居关系,估计数据对象的密度,提出了一种基于高斯核函数的局部离群点检测算法.该算法通过KNN图存储每个数据对象的最近邻,包括k最近邻,反向k近邻和共享最近邻,构成数据对象的邻居集合S;通过核密度估计KDE方法估计数据对象的密度;通过相对密度离群因子RDOF来估计数据对象偏离邻域的程度,进而判定数据对象是否为离群点,并在真实和合成的数据集上证明了该算法的有效性.

多扩展目标滤波器的量测集划分算法

针对不同扩展目标产生的量测密度差别较大时的量测集划分问题,为扩展目标概率假设密度(PHD)滤波器提出了一种基于共享最近邻(SNN)相似度的量测集划分算法。量测间的SNN相似度可体现量测在量测空间局部分布情况,考虑了量测周围的量测信息,因此提出的SNN相似度划分法能够较好地划分量测密度差别较大的量测集,进而提高了扩展目标的跟踪性能,且基于提出的划分算法的PHD滤波器计算量也所减少。

基于共享最近邻聚类和模糊集理论的分类器

提出一种基于共享最近邻聚类和模糊集理论的分类器.首先,在提出与核点密切相关的核半径概念的基础上,应用共享最近邻聚类得到正常类空间的部分核点和核半径,建立求解正常类空间补充核点的多目标优化模型,从而获得刻画正常类空间的全部核点和核半径.然后,将模糊集理论引入正常类的类属划分中,利用核点和核半径定义正常类的隶属度函数,建立基于隶属度函数的分类函数或分类器.实验表明,该分类器能处理包含噪音、孤立点和不规则子类的高维数据集的分类问题.

基于混合测度的并行仿射传播聚类算法

针对仿射传播聚类(AP)算法应用于流形结构复杂、密度不均匀的数据集存在的不足,通过学习数据集的低维流形结构,提出了密度自适应的"流形距离核"(ad-MDK)的概念。该距离测度既考虑了数据点的局部密度信息,又包含了数据集全局结构信息,从而提高了算法对这类数据集的处理能力。同时,针对引入流形距离所带来的计算复杂问题,提出了算法的并行化设计方法,有效提高了算法处理效率。通过在多个数据集上的实验验证了所提算法在处理大规模多尺度数据集上的性能优于传统AP算法。

非线性降维算法及其在医院绩效考核上的应用

流形学习算法中的等距嵌入算法(ISOMAP)具有对离群点敏感的瑕疵,针对此问题,提出利用基于共享近邻的距离度量方式,并充分利用了流形上对象的局部密度信息,有效改善了算法的性能,提高了算法的健壮性。同时,首次尝试将该改进的流形学习算法应用于医院绩效考核。人工数据与真实数据上的实验表明,改进的算法健壮且有效,在绩效考核上应用成功。

基于共享反K近邻的局部离群点检测算法

离群点检测和分析离群模式隐含的特征是离群点挖掘的重要研究内容。现有离群点检测算法存在两个明显的不足:根据离群度检测离群点,难以确定离群点的数量;忽略了与离群点邻接的聚类信息,不能提供解析离群模式的有效证据。为此,提出一种基于共享反K近邻的离群点检测算法,首先定义了一种对密度和维数变化不敏感的共享反K近邻相似度,然后应用聚类方法将数据集划分为聚类簇和包含离群点的离群簇,从而获取数据集中的离群点及解析离群点的聚类结构。仿真结果表明,反K近邻算法比现有方法更能精确地检测数据集中的局部离群点,具有很好的控制性能。

改进的共享型最近邻居聚类算法

聚类效果往往依赖于密度和相似度的定义,并且当数据的维增加时,其复杂度也随之增加。该文基于共享型最近邻居聚类算法SNN,提出了一种改进的共享型最近邻居聚类算法RSNN,并将RSNN应用于高速公路交通数据集上,解决了SNN算法在“去噪”、孤立点和代表点的判断、聚类效果等方面的不足之处。实验结果表明,RSNN算法比SNN算法在时空数据集上具有更好的聚类效果。

基于网格的共享近邻聚类算法

提出了一种基于网格的共享近邻聚类算法(Grid-based shared NearestNeighbor algorithm,GNN)。该算法主要利用网格技术去除数据集中的部分孤立点或噪声,使用密度阈值处理技术来处理网格的密度阈值,使用中心点技术提高聚类效率。GNN算法仅对数据集进行一遍扫描,且能处理任意形状和大小的聚类。实验表明,GNN有较好的可扩展性,其精度和效率明显地好于共享近邻SNN算法。

面向大数据集的共享近邻聚类研究

共享近邻(SNN)相似度能有效克服由高维和多密度等因素引起的聚类有效性问题,但计算效率不高.基于分治策略,提出一种改进的共享近邻聚类算法(DC-SNN).采用软划分策略将数据集分割为多个小规模子集,降低了计算SNN相似矩阵时需要搜索的数据点数量,同时,也避免了子集分割边界对数据点K近邻产生的不利影响.根据在子集中定义的核心数据点和扩展数据点,给出了子集中SNN相似矩阵的计算方法和合并策略,从而确保了以子集SNN相似矩阵表示整个数据集SNN相似矩阵的有效性.实验结果表明,DC-SNN算法能够在确保聚类精度不变的情况下,显著提高共享近邻聚类的效率.

密度不敏感的近邻传播聚类算法研究

近邻传播算法在非凸形、密度不均匀的数据集上很难得到理想的聚类结果。为此,基于核聚类的思想,将数据集非线性地映射到高维空间,使数据集更加分离。利用共享最近邻的相似度度量方法,提出一种密度不敏感的近邻传播算法DIS-AP,以弥补原算法易受特征集维数和密度影响的缺点,从而有效解决数据集非凸和密度不均匀问题,拓宽算法的应用范围。仿真实验结果证明,DIS-AP算法具有更好的聚类性能。