一种新型的基于密度和栅格的聚类算法*

针对网格和密度方法的聚类算法存在效率和质量问题,给出了密度和栅格相结合的聚类挖掘算法,即基于密度和栅格的聚类算法DGCA（density and grid based clustering algorithm）。该算法首先将数据空间划分为栅格单元,然后把数据存储到栅格单元中,利用DBSCAN密度聚类算法进行聚类挖掘;最后进行聚类合并和噪声点消除,并将局部聚类结果映射到全局聚类结果。实验通过人工数据样本集对该聚类算法进行理论上验证,表明了该算法在时间效率和聚类质量两方面都得到了提高。     

一种基于密度峰值的高效分布式聚类算法

基于密度峰值的聚类算法（DPC）是最近提出的一种高效密度聚类算法。该算法可以对非球形分布的数据聚类,有待调节参数少、聚类速度快等优点,但在计算每个数据对象的密度值和高密度最邻近距离时,需要进行距离度量,其时间复杂度为 。在大数据时代,尤其是处理海量高维数据时,该算法的效率会受到很大的影响。为了提高该算法的效率和扩展性,利用 Spark 在内存计算以及迭代计算上的优势,提出一种高效的基于E2LSH分区的聚类算法ELSDPC（an efficient distributed density peak clustering algorithm based on E2LSH partition with spark）。算法利用DPC算法的局部特性,引入局部敏感哈希算法LSH实现将邻近点集划分到一个区域。通过实验分析表明：该算法可在满足较高准确率的同时有效提高聚类算法的扩展性和时间效率。     

基于不相似性度量优化的密度峰值聚类算法

密度峰值聚类（clustering by fast search and find of density peaks,简称DPC）是一种基于局部密度和相对距离属性快速寻找聚类中心的有效算法.DPC通过决策图寻找密度峰值作为聚类中心,不需要提前指定类簇数,并可以得到任意形状的簇聚类.但局部密度和相对距离的计算都只是简单依赖基于距离度量的相似度矩阵,所以在复杂数据上DPC聚类结果不尽如人意,特别是当数据分布不均匀、数据维度较高时.另外,DPC算法中局部密度的计算没有统一的度量,根据不同的数据集需要选择不同的度量方式.第三,截断距离d_c的度量只考虑数据的全局分布,忽略了数据的局部信息,所以d_c的改变会影响聚类的结果,尤其是在小样本数据集上.针对这些弊端,提出一种基于不相似性度量优化的密度峰值聚类算法（optimized density peaks clustering algorithm based on dissimilarity measure,简称DDPC）,引入基于块的不相似性度量方法计算相似度矩阵,并基于新的相似度矩阵计算样本的K近邻信息,然后基于样本的K近邻信息重新定义局部密度的度量方法.经典数据集的实验结果表明,基于不相似性度量优化的密度峰值聚类算法优于DPC的优化算法FKNN-DPC和DPC-KNN,可以在密度不均匀以及维度较高的数据集上得到满意的结果;同时统一了局部密度的度量方式,避免了传统DPC算法中截断距离d_c对聚类结果的影响.     

基于密度的分布式聚类算法研究

大量复杂异构数据分布于各个网络站点上,分布式聚类是海量数据处理的一个重要应用。该文针对基于密度的分布式聚类(DBDC)算法提出一种改进算法,利用局部聚类获取更佳的代表对象,将代表对象集附带相关信息传送至主站点,用增强的基于密度的聚类算法进行全局聚类,并更新子站点聚类。理论分析和实验结果表明,该算法在聚类质量和算法效率方面优于DBDC算法。     

一种分布式隐私保护的密度聚类算法

对基于密度的分布式聚类算法DBDC进行改进,提出了一种基于密度的分布式隐私保护聚类算法DBPPDC。在由局部模型确定全局模型时,通过相关安全协议有效地保护了局部模型,同时不影响全局聚类。在利用全局模型更新局部模型时,通过改进算法、应用安全协议保护隐私信息,最终使各站点分布的数据能够安全聚类。理论分析和实验结果表明,DBPPDC算法是有效的。     

基于MapReduce和IFOA的并行密度聚类算法

针对大数据下密度聚类算法中存在的数据划分不合理、参数寻优能力不佳、并行性能较低等问题,提出一种基于IFOA的并行密度聚类算法(density-based clustering algorithm by using improve fruit fly optimization based on MapReduce,MR-DBIFOA)。首先,该算法基于KD树,提出网格划分策略(divide gird based on KD tree,KDG)来自动划分数据网格;其次在局部聚类中,提出基于自适应搜索策略(step strategy based on knowledge learn,KLSS)和聚类判定函数(clustering criterion function,CCF)的果蝇群优化算法(improve fruit fly optimization algorithm,IFOA);然后根据IFOA进行局部聚类中最优参数的动态寻优,从而使局部聚类的聚类效果得到提升;同时结合MapReduce模型提出局部聚类算法DBIFOA(density-based clustering algorithm using IFOA);最后提出了基于QR-tree的并行合并局部簇算法(cluster merging algorithm by using MapReduce,MR-QRMEC),实现局部簇的并行合并,使算法整体的并行性能得到加强。实验表明,MR-DBIFOA在大数据下的并行效率更高,且聚类效果更好。     

基于Web-Log Mining的Web文档聚类

速度和效果是聚类算法面临的两大问题.DBSCAN(density based spatial clustering of applications with noise)是典型的基于密度的一种聚类方法,对于大型数据库的聚类实验显示了它在速度上的优越性.提出了一种基于密度的递归聚类算法(recursive density based clustering algorithm,简称RDBC),此算法可以智能地、动态地修改其密度参数.RDBC是基于DBSCAN的一种改进算法,其运算复杂度和DBSCAN相同.通过在Web文档上的聚类实验,结果表明,RDBC不但保留了DBSCAN高速度的优点,而且聚类效果大大优于DBSCAN.     

一种基于时态密度的倾斜分布数据流聚类算法

为解决倾斜分布的数据流聚类这一难题,提出了时态密度概念,给出其度量,揭示了其包括可增量计算在内的一系列数学性质;设计了时态密度树结构,提高了聚类时的存储和检索效率;设计了能够以实时或异步方式捕捉数据倾斜分布的数据流时态特征的聚类算法TDCA(temporal density based clustering algorithm),其时间复杂度为O(c(m(lgm).实验结果表明,该算法不仅有较强的功能,而且具有较好的规模可伸缩性.     

自然最近邻优化的密度峰值聚类算法*

针对现有的基于密度的聚类算法存在参数敏感,处理非球面数据和复杂流形数据聚类效果差的问题,提出一种新的基于密度峰值的聚类算法。该算法首先根据自然最近邻居的概念确定数据点的局部密度,然后根据密度峰局部密度最高并且被稀疏区域分割来确定聚类中心,最后提出一种新的类簇间相似度概念来解决复杂流形问题。在实验中,该算法在合成和实际数据集中的表现比DPC(clustering by fast search and find of density peaks)、DBSCAN(density-based spatial clustering of applications with noise)和K-means算法要好,并且在非球面数据和复杂流形数据上的优越性特别大。     

基于局部密度信息熵均值的密度峰值聚类算法

针对密度峰值聚类算法（The density peak clustering algorithm,DPC）聚类结果受距离阈值dc参数影响较大的问题,提出一种局部密度捕获范围以及利用局部密度信息熵均值进行加权优化的方法（简称为LDDPC）,在DPC算法选取到错误的距离阈值dc时,通过对最大密度邻近点的相对距离进行加权,重新获得正确的分类数量和聚类中心。经典数据集的实验结果表明,基于局部密度信息熵均值加权优化能避免 DPC 算法中距离阈值dc对聚类结果的影响,提高分类的正确率。     

密度分布函数在聚类算法中的应用

深入分析了传统的基于密度的聚类方法的特点和存在的问题及讨论了基于密度聚类算法研究现状,提出了一种改进的基于密度分布函数的聚类算法.使用K最近邻（KNN）的思想度量密度以寻找当前密度最大点,即中心点.并使用区域比例,将类从中心点开始扩展,每次扩展的同时引入半径比例因子以发现核心点.再从该核心点的KNN扩展类,直至密度下降到中心点密度的给定比率时结束.给出了数个算法实例并与基于网格的共享近邻聚类（GNN）算法在聚类准确率和效率上进行了试验比较,试验表明该算法极大降低了基于密度聚类算法对参数的敏感性、改善了对高维密度分布不均数据集的聚类效果、提高了聚类准确率和效率.     

自适应快速搜索密度峰值聚类算法

CFSFDP算法（Clustering by Fast Search and Find of Density Peaks）具有简单高效且需要较少参数的优点,但存在需要人为确定截断距离参数和聚类中心的不足。为克服以上不足,提出了自适应快速搜索密度峰值聚类算法。该算法针对截断距离参数的确定问题,构造关于截断距离参数的局部密度信息熵,通过最小化信息熵自适应地确定截断距离参数;针对聚类中心的确定问题,利用从非聚类中心到聚类中心数据点局部密度和距离的乘积,存在明显跳跃这一特征确定阈值,从而能自动确定聚类中心。实验结果表明该算法能够取得较好的聚类性能,且无需人为确定截断距离参数和聚类中心。     

基于共享近邻和优化关联策略的边界剥离聚类

边界剥离聚类算法(BP)是一种基于密度的聚类算法,它通过逐渐剥离边界点来揭示聚类的潜在核心,已经被证明是一种十分有效的聚类手段.然而, BP算法仍存在一些不足之处:一方面,数据点的局部密度仅考虑了距离特征,使得边界点的确定不够合理;另一方面, BP算法中的关联策略容易误判异常值,并且在分配边界点时容易产生连带错误.为此,本文提出了一种基于共享近邻和优化关联策略的边界剥离聚类算法(SOBP).该算法使用了基于共享近邻的局部密度函数来更好地探索数据点之间的相似性,同时优化了BP算法中的关联策略,使得每次迭代中边界点不再仅与一个非边界点进行关联,并进一步采用了边界点与非边界点、已剥离边界点之间的双重关联准则.在一些数据集上的测试表明,相较于其他6种经典算法,该算法在评估指标上表现更佳.     

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

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

     

基于不均匀密度的自动聚类算法

针对基于密度的聚类算法不能自动处理密度分布不均匀的数据问题,提出一种基于不均匀密度的自动聚类算法。该算法既保持了一般基于密度算法的优点,也能有效地处理分布不均匀的数据。实验结果表明,该算法是有效的。     

基于共享近邻相似度的密度峰聚类算法

密度峰聚类是一种基于密度的高效聚类方法,但存在对全局参数d_c敏感和需要人工干预决策图进行聚类中心选择的缺陷。针对上述问题,提出了一种基于共享近邻相似度的密度峰聚类算法。首先,该算法结合欧氏距离和共享近邻相似度进行样本局部密度的定义,避免了原始密度峰聚类算法中参数d_c的设置;其次,优化聚类中心的选择过程,能够自适应地进行聚类中心的选择;最后,将样本分配至距其最近并拥有较高密度的样本所在的簇中。实验结果表明,在UCI数据集和模拟数据集上,该算法与原始的密度峰聚类算法相比,准确率、标准化互信息（NMI）和F-Measure指标分别平均提高约22.3%、35.7%和16.6%。该算法能有效地提高聚类的准确性和聚类结果的质量。     

基于中心点及密度的分布式聚类算法

针对分布式聚类算法DBDC存在的不足,提出一种基于中心点及密度的分布式聚类算法DCUCD。将数据分布计算出的虚拟点作为核心对象,核心对象的代表性随算法的执行次数提高,聚类即是对所有核心对象分类的过程。理论分析和实验结果表明,该算法能有效处理噪声和分布不规则的数据点,时间效率和聚类质量较好。     

基于密度的模糊代表点聚类算法

结合密度聚类和模糊聚类的特点,提出一种基于密度的模糊代表点聚类算法.首先利用密度对数据点成为候选聚类中心点的可能性进行处理,密度越高的点成为聚类中心点的可能性越大;然后利用模糊方法对聚类中心点进行确定;最后通过合并聚类中心点确定最终的聚类中心.所提出算法具有很好的自适应性,能够处理不同形状的聚类问题,无需提前规定聚类个数,能够自动确定真实存在的聚类中心点,可解释性好.通过结合不同聚类方法的优点,最终实现对数据的有效划分.此外,所提出的算法对于聚类数和初始化、处理不同形状的聚类问题以及应对异常值等方面具有较好的鲁棒性.通过在人工数据集和UCI真实数据集上进行实验,表明所提出算法具有较好的聚类性能和广泛的适用性.