一种基于网格索引的数据聚类算法

为了提高基于密度聚类算法的效率,避免算法在执行过程中的多余搜索,提出了一种基于DBSCAN算法的改进的空间数据聚类算法。该算法采用对象邻域空间进行划分的方法,将网格索引结构应用于该算法。在核心对象的邻域内选择八个方向上未标记且距离核心对象最边缘的对象来扩展种子对象,减少查询次数,降低聚类的时间复杂度。在实验中,利用海量数据集对算法进行测试,测试结果证明新算法在保证聚类精度的情况下时间效率显著高于DBSCAN算法。     

基于KD树改进的DBSCAN聚类算法

针对DBSCAN聚类算法随着数据量增大,耗时越发非常严重的问题,提出一种基于KD树改进的DBSCAN算法(以下简称KD-DBSCAN).通过KD树对数据集进行划分,构造邻域对象集,提前区分出噪声点和核心点,避免聚类过程中对噪声的邻域集计算以及加快了核心点对象的邻域集查询速度.文中以浮动车GPS数据为实验数据,对比传统DBSCAN算法和KD-DBSCAN算法的聚类效果和时间性能,实验结果表明KD-DBSCAN算法的聚类效果和传统的DBSCAN基本一致,但时间性能有很大的提升.     

基于区域划分的DBSCAN多密度聚类算法*

DBSCAN聚类算法使用固定的Eps和Minpts,处理多密度的数据效果不理想;并且算法的时间复杂度为O(n2)。针对以上问题,提出一种基于区域划分的DBSCAN多密度聚类算法。算法利用网格相对密度差把数据空间划分成密度不同的区域,每个区域的Eps根据该区域的密度计算自动获得,并利用DBSCAN算法进行聚类,提升了DBSCAN的精度;避免了DBSCAN在查找密度相连时需要遍历所有数据,从而改善了算法效率。实验表明算法能有效地对多密度数据进行聚类,对各种数据的适应力较强,效率较优。     

基于网格的高效DBSCAN算法

DBSCAN是一种性能优越的基于密度的聚类算法。为提高它的运行效率,提出了基于网格的DBSCAN算法GbDBSCAN。该算法使用网格划分的方法和数据分箱技术,减少了判定密度可达对象时的搜索范围,降低了算法的运行时间,而且算法还能够识别并处理边界点。实验结果表明,GbDBSCAN在不降低DBSCAN聚类质量的前提下,大大提高了DBSCAN算法处理低维数据集的效率。     

一种基于密度的快速聚类方法

具有噪声的基于密度的聚类方法（Density based spatial clustering of applications with noise, DBSCAN）在数据规模上的扩展性较差。本文在其基础 上提出一种改进算法——具有噪声的基于密度的快速聚类方法(Fast density based spat ial clustering of applications with noise, F DBSCAN),对核心对象邻域中的对象只 作标记,不再进行扩展检查,通过判断核心对象邻域中是否存在已标记对象来实现簇合并,对 边界对象判断其邻域中是否存在核心对象来确认是否为噪声。此方法避免了原始算法中对重叠区域 的重复操作,在不需创建空间索引的前提下,其时间复杂度为O(nlogn)。通过实验数据集和 真实数据集,验证其聚类效果及算法效率。实验表明F DBSCAN算法不仅保证了有良好的聚 类效果及算法效率,并且在数据规模上具有良好的扩展性。     

Greedy DBSCAN:一种针对多密度聚类的DBSCAN改进算法*

针对基于密度的DBSCAN算法对于输入参数敏感、无法聚类多密度数据集等问题,提出了一种贪心的DBSCAN改进算法（Greedy DBSCAN）。算法仅需输入一个参数MinPts,采用贪心策略自适应地寻找Eps半径参数进行簇发现,利用相对稠密度识别和判定噪声数据,在随机寻找核对象过程中使用邻域查询方式提升算法效率,最终通过簇的合并产生最终的聚类结果。实验结果表明,改进后的算法能有效地分离噪声数据,识别多密度簇,聚类准确度较高。     

多密度阈值的DBSCAN改进算法

在分析了基于密度的聚类算法（DBSCAN）及其改进算法的缺点的基础上,提出了一种多密度阈值的DBSCAN改进算法。算法通过构建网格密度矩阵绘制密度分布图,辅助用户确定密度层次划分。根据基于网格与基于密度的聚类算法间的等效规则计算各个密度层次的密度阈值ε。通过多密度层次的聚类过程得到多个密度层次上的更加精细的聚类结果。解决了DBSCAN算法参数选取困难和难以发现密度相差较大的簇的问题,具有重要的实用意义。     

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

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

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

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

基于网格近邻优化的密度峰值聚类算法

密度峰值聚类(DPC)将数据样本点的局部密度和相对距离进行结合,能对任意形状数据集进行聚类处理,但密度峰值聚类算法存在主观选择截断距离、简单分配策略和较高时间复杂度等问题。为此,提出了一种基于网格近邻优化的密度峰值聚类算法(KG-DPC算法)。首先对数据空间进行网格化,减少了样本数据点之间距离的计算量;在计算局部密度时不仅考虑了网格自身的密度值,而且考虑了周围k个近邻的网格密度值,降低了主观选择截断距离对聚类结果的影响,提高了聚类准确率,设定网格密度阈值,保证了聚类结果的稳定性。通过实验结果表明,KG-DPC算法比DBSCAN、DPC和SDPC算法在聚类准确率上有很大提升,在聚类平均消耗时间上DPC、SNN-DPC和DPC-NN算法分别降低38%、44%和44%。在保证基本聚类准确率的基础上,KG-DPC算法在聚类效率上有特定优势。     

一种基于密度的快速聚类算法

聚类是数据挖掘领域中的一个重要研究方向,聚类技术在统计数据分析、模式识别、图像处理等领域有广泛应用,迄今为止人们提出了许多用于大规模数据库的聚类算法。基于密度的聚类算法DBSCAN就是一个典型代表。以DBSCAN为基础,提出了一种基于密度的快速聚类算法。新算法以核心对象领域中所有对象的代表对象为种子对象来扩展类,从而减少区域查询次数,降低I/O开销,实现快速聚类,对二维空间数据测试表明：快速算法能够有效地对大规模数据库进行聚类,速度上数倍于已有DBSCAN算法。     

基于网格查询的局部离群点检测算法

针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。     

一种基于密度的高效聚类算法

在聚类算法DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)的基础上,提出了一种基于密度的高效聚类算法。该算法首先对样本集按某一维排序,然后通过在核心点的邻域外按顺序选择一个未标记的样本点来扩展种子点,以便减少查询次数,降低聚类的时间花费。对样本进行非线性核变换后再进行聚类可以有效地改善聚类的质量。理论分析表明,该算法的时间复杂性接近于线性复杂度。同时测试结果也表明新算法的时间复杂度和聚类质量都显著优于DBSCAN算法。     

一种基于DBSCAN算法的代码包层次重构改进方法

在包层次的代码重构研究中,为了得到“高内聚、低耦合”的软件结构,层次聚类算法因其简单有效、聚类精度高等特点被认为是一种较好的软件聚类方法。但是,层次聚类算法时间复杂度高,不利于处理较大规模的软件。而基于密度聚类的DBSCAN算法则与之相反,具有较快的聚类速度,但是精度却较低。因此,提出一种基于DBSCAN的软件层次聚类算法,利用DBSCAN算法所产生的类来约束层次聚类算法的聚类空间,该算法可以保持层次聚类算法的精度不变,且它的时间复杂度介于DBSCAN和层次聚类算法之间。实验结果表明,该算法可以有效地对软件进行合理划分,并通过专家评判、模块划分度量指标和算法运行时间对比来表明其比其他常用聚类算法的性能更好。     

一种基于扩展区域查询的密度聚类算法

针对DBSCAN算法中最小点数和最大邻域半径难以确定,算法时间开销大,对起始数据点的选择比较敏感,以及难以发现不同密度下的邻近簇等问题,本文提出一种基于扩展区域查询的密度聚类算法(GISN-DBSCAN)。该方法首先提出扩展区域查询算法,随后采用最近邻域和反最近邻域的邻域关系,建立每个点的k-影响空间域,最后提出一种异常点判定函数,使得算法能够准确的识别边界点和噪声点。实验结果表明：GISN-DBSCAN算法能够有效的解决DBSCAN算法的不足。     

一种基于四叉树的快速聚类算法

以DBSCAN算法为基础,提出一种基于四叉树的快速聚类算法。新算法选择处于核心点的中空球形邻域中的点作为种子点来扩展类,大大减少区域查询的次数,降低I／O开销;使用快速生成的四叉树进行区域查询,在提高查询效率的同时,有效缩短构造空间索引的时间。文中对二维模拟数据和真实数据进行测试,结果表明新算法是有效的。     

FDBSCAN:一种快速 DBSCAN算法

聚类分析是一门重要的技术 ,在数据挖掘、统计数据分析、模式匹配和图象处理等领域具有广泛的应用前景 .目前 ,人们已经提出了许多聚类算法 .其中 ,DBSCAN是一种性能优越的基于密度的空间聚类算法 .利用基于密度的聚类概念 ,用户只需输入一个参数 ,DBSCAN算法就能够发现任意形状的类 ,并可以有效地处理噪声 .文章提出了一种加快 DBSCAN算法的方法 .新算法以核心对象邻域中所有对象的代表对象为种子对象来扩展类 ,从而减少区域查询次数 ,降低 I/ O开销 .实验结果表明 ,FDBSCAN能够有效地