基于相对密度的聚类算法

基于密度的聚类算法因其抗噪声能力强和能发现任意形状的簇等优点,在聚类分析中被广泛采用,本文提出的基于相对密度的聚类算法,在继承上述优点的基础上。有效地解决了基于密度的聚类结果对参数值过于敏感、参数值难以设置以及高密度簇完全被相连的低密度簇所包含等问题。     

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

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

障碍空间中不确定数据聚类算法

近些年,由于数据采集的不精确和数据本身的不确定性,使不确定性在位置数据中普通存在。在障碍空间中,聚类不确定数据面临新的挑战。提出了障碍空间中聚类不确定数据的OBS-UK-means(obstacle uncertain K-means)算法,并提出了分别基于R树和Voronoi图的两种剪枝策略和最近距离区域的概念,大大减少了计算量。通过实验验证了OBS-UK-means算法的高效性和准确性,同时证明了剪枝策略在不损害聚类有效性的情况下,能够有效地提高聚类效率。     

基于相对密度的多分辨率聚类算法

提出基于相对密度的多分辨率聚类算法,结合了密度聚类和模糊聚类的优点,能形成任意形状、多级分辨率的聚类结果,具有抗噪声能力和处理大数据集的能力,并有效地解决参数值难以设置,以及高密度簇完全被相连的低密度簇所包含等问题.     

不确定数据聚类算法研究

UK均值算法需要计算每个对象之间的期望距离（EDS）和聚类中心, EDS计算的成本就成了UK均值计算的性能瓶颈。为了提高UK均值的计算效率,本文提出一种优化的UK均值算法,通过一个高效的公式来估计期望距离,大大降低了UK均值的额外时间,并在实验中得以证明。我们还说明这个优化公式有效地将UK均值算法降低到了传统的基于K均值的聚类算法。     

高维不确定数据高效聚类算法

维度灾难、含有噪声数据和输入参数对领域知识的强依赖性,是不确定数据聚类领域中具有挑战性的问题。针对这些问题,基于相似性度量和凝聚层次聚类思想的基础上提出了高维不确定数据高效聚类HDUDEC（High Dimensional Un-certain Data Efficient Clustering）算法。该算法采用一个能够准确表达不确定高维对象之间的相似度的度量函数计算出对象之间的相似度,然后根据相似度阈值自底向上进行聚类分析。实验证明新的算法需要的先验知识较少、可以有效地过滤噪声数据、可以高效的获得任意形状的高维不确定聚类结果。     

基于网格相对密度的多密度聚类算法

提出网格相对密度的概念和边界点提取技术,在此基础上给出了一种多密度聚类算法。该算法使用网格相对密度识别具有不同密度聚簇的相对高密度网格单元,聚类时从相对高密度网格单元开始逐步扩展生成聚簇。实验结果表明,算法能有效地识别不同形状、不同密度的聚簇并对噪声数据不敏感,具有聚类精度高等优点。     

基于相对密度的数据流模糊聚类算法

提出的基于相对密度的数据流模糊聚类算法结合了相对密度聚类和模糊聚类的优点,能形成任意形状、多密度分辨率的层次聚类结果.同时,利用微簇空间位置重叠关系,定义了微簇集合间的差运算,从而有效地支持了用户指定时间窗口内的数据流聚类要求.通过与CluStream算法在聚类质量和处理时间两个方面的比较分析,发现基于相对密度的数据流模糊聚类算法具有明显的优势.     

高维不确定数据高效聚类算法

维度灾难、含有噪声数据和输入参数对领域知识的强依赖性,是不确定数据聚类领域中具有挑战性的问题。针对这些问题,基于相似性度量和凝聚层次聚类思想的基础上提出了高维不确定数据高效聚类HDUDEC(High Dimensional Uncertain Data Efficient Clustering)算法。该算法采用一个能够准确表达不确定高维对象之间的相似度的度量函数计算出对象之间的相似度,然后根据相似度阈值自底向上进行聚类分析。实验证明新的算法需要的先验知识较少、可以有效地过滤噪声数据、可以高效的获得任意形状的高维不确定聚类结果。     

基于Voronoi图的障碍不确定数据的聚类算法

数据采集过程中普遍存在不确定性,并且在现实地理空间中,不确定数据之间可能存在障碍物间隔。为解决障碍空间中不确定数据的聚类问题,提出APPGCUO算法,该算法包括三个过程:在障碍物约束下采用R树节点最小最大值方法提出的RPT-OUCure算法,用以生成局部最优解,提高生成局部最优解的效率;继而利用近似骨架的理论提出GIABO算法,以局部最优解生成有效初始解,避免划分聚类算法中任意初始解的不足;最后结合Voronoi图的特性提出VPT-KMediods算法,减少不确定数据的积分运算量。实验结果表明,APPGCUO算法具有较高的聚类效率和质量。     

基于密度的不确定性数据概率聚类

近期传感数据监测和移动对象跟踪等许多从自然界直接采集数据的新应用引发了不确定性数据管理这一新的研究课题.这些应用中相关数据的不确定性为传统的数据处理方法提出了新的挑战.探讨的重点是不确定性数据的聚类.提出了一个针对不确定性数据的基于密度的聚类算法,根据不确定性数据内在的概率分布信息进行概率聚类,并采用R树索引和概率阀值索引提高算法的效率.仿真试验表明,提出的算法在有效性和效率方面均优于当前主要的基于密度的不确定性数据聚类算法.     

不确定数据聚类的U-PAM算法和UM-PAM算法的研究

UK-means算法在处理不确定数据时对孤立点非常敏感,而且事先必须已知不确定数据的分布函数或概率密度,然而这在实际中往往很难获得。因此,针对UK-means在处理不确定测量数据时的不足,首先提出了基于区间数的PAM不确定聚类算法——U-PAM,该算法用区间数和标准差合理地描述了不确定测量数据的不确定性,进而完成有效的聚类;其次,针对海量不确定测量数据难以聚类的问题,基于U-PAM聚类算法,采用抽样技术提出了处理海量不确定测量数据的算法——UM-PAM算法,该算法先抽样,对样本数据聚类,然后再总体聚类;最后,基于U-PAM算法和CH聚类的有效性指标函数对聚类结果进行分析,以确定最佳聚类数。实验理论表明,所提算法聚类效果明显。     

基于区间数的多维不确定性数据UID-DBSCAN聚类算法

不确定性数据聚类方法的研究日益受到广泛关注,其中UIDK-means算法与U-PAM算法继承了基于划分算法无法识别任意形状簇和对噪声点敏感的缺陷。FDBSCAN算法事先假定不确定性数据的概率分布函数或概率密度函数是已知的,然而这些信息在实际应用中往往难以获取。针对上述算法的不足,提出一种基于区间数的多维不确定性数据聚类UID-DBSCAN算法。该算法利用区间数结合数据的统计信息合理地表示不确定性数据,采用低计算复杂度的区间数距离函数衡量不确定性数据对象间的相似度,首次提出区间数的密度、密度可达与密度相连等概念,并将其用于扩展簇中,同时结合数据集的统计特征自适应地选取算法的密度参数来实现自动聚类。实验结果表明,UID-DBSCAN算法能够有效识别噪声,处理任意形状簇,具有较高的聚类精度和较低的计算复杂度。     

基于网格的数据流聚类算法

本文提出的基于网格的数据流聚类算法,克服了算法CluStream对非球形的聚类效果不好等缺陷,不仅能在噪声干扰下发现任意形状的类,而且有效地解决了聚类算法参数敏感和聚类结果无法区分密度差异等问题。     

基于近邻传播的不确定数据流演化聚类算法*

鉴于现有算法缺乏从时序演化角度解决不确定数据流聚类问题,提出基于近邻传播的不确定数据流演化聚类算法。考虑不确定数据流在线形成微簇时的变化因素对离线聚类的影响,提出不确定微簇变化率的概念。从不确定数据流演化的角度衡量微簇之间的相似程度,提出不确定微簇关联度的概念,并以此为基础构造不确定相似度矩阵,结合近邻传播思想实现不确定数据流演化聚类。通过实验证明文中算法的有效性和良好的聚类效果。     

基于密度的不确定数据离群点检测研究

针对不确定数据集进行离群点检测,设计了基于密度的不确定数据的局部离群因子(Uncertain Local Outlier Factor,ULOF)算法.通过建立不确定数据的可能世界模型来确定不确定对象在可能世界中的概率.结合传统的LOF算法推导出ULOF算法,根据ULOF值判断不确定对象的局部离群程度;然后对ULOF算法的效率性和准确性进行了详细分析,提出了基于网格的剪枝策略、k最近邻查询优化来减少数据的候选集;最后通过实验证明了ULOF算法对不确定数据检测的可行性和效率性,优化后的方法有效地提高了异常检测准确率,降低了时间复杂度,改善了不确定数据的异常检测性能.     

基于联系数的位置不确定性数据UCNK-Means聚类算法

摘要位置不确定性数据的聚类是一个新的不确定性数据聚类问题。其聚类方法主要包括获取对象的概率密度函数,通过积分计算对象间的期望距离来进行聚类分析和以区间数表示对象,通过区间数的系列运算来进行聚类分析这两大类。前者存在概率密度函数获取困难、计算复杂、实用性不强的缺陷;后者在区间数转化为实数过程中,忽略了区间数变化范围对聚类效果的影响,其聚类质量不佳。鉴于此,提出一种基于联系数的不确定对象聚类新算法UCNK-Means。该算法用联系数巧妙地表示不确定性对象,并专门定义了对象间的联系距离,运用联系数态势值比较联系距离大小,克服了现有算法的不足。仿真实验表明,UCNK-Means具有聚类精度高、计算复杂度低、实用性强的特点。     

一种不确定数据流聚类算法

提出了EMicro算法,以解决不确定数据流上的聚类问题.与现有技术大多仅考虑元组间的距离不同,EMicro算法综合考虑了元组之间的距离与元组自身不确定性这两个因素,同时定义新标准来描述聚类结果质量.还提出了离群点处理机制,系统同时维护两个缓冲区,分别存放正常的微簇与潜在的离群点微簇,以期得到理想的性能.实验结果表明,与现有工作相比,EMicro的效率更高,且效果良好.     

障碍空间里基于密度的快速聚类算法

传统的聚类方法不能直接运用于分布空间内存在障碍物的数据的聚类.提出了一种障碍空间内基于密度的快速聚类算法DBCO来解决此类问题.DBCO中,在基于密度的聚类基础上引入了障碍模型,提出了一种保持数据间可见性的简化障碍的方法.为了使障碍模型不影响聚类质量,定义了障碍顶点距离、连接距离和判断距离来维持聚类的质量.另外,在聚类过程中,选择某一些代表点和拓展点而不是每一个点来对每一个聚类进行扩展,从而大大提高了聚类算法的效率.实验结果表明了DB-CO算法可以快速地得到高质量的聚类结果.