基于网格和信息熵的多密度聚类算法

虽然现有的很多聚类算法能发现任意形状、任意大小的类,但用于多密度的数据集时却难以取得令人满意的结果。为提高对多密度数据集的聚类效果,提出了一种基于网格和信息熵的多密度聚类算法,它通过不同密度的网格所携带的信息熵,自动计算出密度阈值,找出在多密度数据集中不同的类。实验证明,该算法能有效的去处噪声,发现多密度的类,具有较好的聚类效果。     

聚类算法综述

数据挖掘技术可以从大量数据中发现潜在的、有价值的知识,它给人们在信息时代所积累的海量数据赋予了新的意义。随着数据挖掘技术的迅速发展,作为其重要的组成部分,网格聚类技术已经被广泛应用于数据分析、图像处理、市场研究等许多领域。网格聚类算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。 介绍了数据挖掘理论,对网格聚类算法进行了深入的分析研究。在研究了传统网格聚类算法的基础上,提出了一些改进的网格聚类算法,这些算法相比传统网格聚类算法有更好的聚类质量和效率。在分析了传统的多密度聚类算法的基础上,提出了基于网格的多密度聚类算法(Grid-based Clustering Algorithm for Multi-density)[1],该算法主要采用密度阈值递减的多阶段聚类技术提取不同密度的聚类,同时对聚类结果进行了人工干预。研究结果表明,基于网格的多密度聚类算法不仅能够对数据集进行正确的聚类,同时还能有效地弥补孤立点检测,有效地解决了传统多密度聚类算法不能有效识别孤立点和噪声的缺陷。基于网格的多密度聚类算法比传统的共享近邻SNN算法精度高,适合于均匀密度数据集、大部分多密度数据集,并且可以发现任意形状的聚类,对噪声数据和数据输入顺序不敏感,但对小部分多密度数据集的聚类结果不理想[1]。     

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

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

一种用于居住热区聚类的改进CLIQUE算法

在居住热区分析应用中,已有的CLIQUE算法密度阈值初始化多采用主观性较强的经验值,容易对聚类结果造成不良影响.针对该问题提出了一种自适应密度阈值选取的CLIQUE算法(APS-CLIQUE,Adaptive Parameter Selection-CLIQUE),并对聚类边界进行了优化处理.该算法首先使用四分位数箱型模型排除数据形态两端对结果的干扰,解决密度阈值自适应问题;其次通过边界网格的判定,提高了聚类边界精度.使用UCI标准数据集、成都市出租车GPS轨迹浮动数据集进行了对比实验,实验结果表明本文算法的Dunn指数较CLIQUE算法分别提高了26.53%、28.66%.     

一种基于网格划分的密度峰值聚类改进算法

针对密度峰值聚类(Density Peak Clustering, DPC)算法具有时空复杂度高而降低了对大规模数据集聚类的有效性,以及依靠决策图人工选取聚类中心等缺点,提出基于网格的密度峰值聚类(G-DPC)算法。采用基于网格的方式进行网格划分,用网格代表点替换网格单元整体;对各代表点聚类,通过改进的自适应方法选出核心网格代表点作为聚类中心;将剩余点归类,剔除噪声点。仿真实验验证了该算法对大规模数据集和高维数据集聚类的有效性。     

一种优化初始点与自适应半径的密度聚类算法

传统DBSCAN算法不能正确聚类密度不均匀的数据集,聚类结果受邻域阈值和密度阈值参数的影响较大。提出一种新的优化初始点和自适应半径的密度聚类算法。利用反向最近邻和相似度矩阵发现当前全局密度最大的数据样本,分析该样本周围密度的分布情况,采用自适应的方法计算当前簇的邻域阈值,并利用DBSCAN算法进行聚类。在人工数据集和UCI数据集上进行测试的结果表明,与经典的DBSCAN、OPTICS、RNN-DBSCAN算法相比,优化初始点和自适应半径的密度聚类算法在ARI、NMI、Homogeneity、Completeness和V-measure 5个评价指标上整体取得最优值,其中在Compound、Jain等数据集上达到1.0,具有较高的聚类效率和准确度。     

一种改进的GP-CLIQUE自适应高维子空间聚类算法

GP-CLIQUE算法是基于高斯过程的CLIQUE改进算法,但是此算法中存在固定划分网格和人为输入密度阈值这两个不足.提出了一种改进GP-CLIQUE的算法——REG-CLIQUE算法.该算法利用相对熵对每一维数据进行自适应网格划分,引入二叉树存储信息,删除冗余维,解决了固定划分网格的缺陷,提高了聚类结果的精度;同时,提出密度阈值的计算公式,根据数据集本身用递归算法计算密度阈值,解决了人为输入的不足,大大降低算法对先验知识的依赖性.实验结果表明,该算法在时间、聚类准确度等方面都优于GP-CLIQUE算法和CLIQUE算法.     

密度网格参数自适应的数据流聚类算法

针对传统密度网格算法在聚类中自动获取密度阈值不够精确的问题,提出了一种基于密度网格参数自适应的数据流聚类算法A-Stream。通过引入"双密度阈值",并以平均值作为密度阈值,对传统聚类算法进行了改进,解决了算法不能获取精确值的问题。实验结果表明,A-Stream算法不仅保留了传统密度网格算法的高效性,而且较大程度上提高了聚类精度。     

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

提出了一种多密度网格聚类算法GDD。该算法主要采用密度阈值递减的多阶段聚类技术提取不同密度的聚类,使用边界点处理技术提高聚类精度,同时对聚类结果进行了人工干预。GDD算法只要求对数据集进行一遍扫描。实验表明,该算法可扩展性好,能处理任意形状和大小的聚类,能够很好的识别出孤立点或噪声,在处理多密度聚类方面有很好的精度。     

.基于网格梯度的多密度聚类算法*

大多数现有的聚类算法都致力于发现任意形状、任意大小的类,但很难有效处理多密度的数据集。提出的算法利用网格聚类速度快的特点,先通过高斯平滑去除噪声,再采用网格梯度的思想找出隐藏在多密度数据集中的簇。算法在人工数据集上进行了实验,结果表明该算法能有效地去除噪声,发现多密度的簇,具有较好的聚类效果。     

利用区域划分的多密度快速聚类算法

针对基于网格的聚类算法存在簇边缘网格中包含噪声点、利用网格相对密度差进行网格合并时不能区分密度均匀变化的网格等问题。提出一种利用区域划分的多密度快速聚类算法MFCBR。算法把数据空间划分成密度不同的网格,利用网格索引表和网格中心密度差合并网格形成簇,然后分别计算每个簇的边界网格质心、边界网格和最近簇网格中心位置,利用三者之间的关系来排除簇边界网格数据中包含的噪声点。实验表明,该算法在降低噪声数据对聚类干扰的同时,且对密度均匀变化的多密度数据集也有较优的处理效果。     

不确定数据信任密度峰值聚类算法

密度峰值聚类算法具有简单高效、无需迭代计算和提前设定类簇数的优势,但是在划分非类中心样本时容易产生“多米诺骨牌”效应,并且不能准确划分重叠区域的样本和噪声。为了解决以上问题,提出了不确定数据信任密度峰值聚类算法。首先,该算法在密度峰值聚类算法获取类中心样本的基础上,利用非类中心样本的K近邻求出样本属于不同类的信任值,将...     

基于密度峰值和网格的自动选定聚类中心算法

针对快速搜索和发现密度峰值的聚类算法(DPC)中数据点之间计算复杂,最终聚类的中心个数需要通过决策图手动选取等问题,提出基于密度峰值和网格的自动选定聚类中心的改进算法GADPC。首先结合Clique网格聚类算法的思想,不再针对点对象进行操作,而是将点映射到网格,并将网格作为聚类对象,从而减少了DPC算法中对数据点之间的距离计算和聚类次数;其次通过改进后的聚类中心个数判定准则更精确地自动选定聚类中心个数;最后对网格边缘点和噪声点,采用网格内点对象和相邻网格间的相似度进行了处理。实验通过采用UEF(University of Eastern Finland)提供的数据挖掘使用的人工合成数据集和UCI自然数据集进行对比,其聚类评价指标(Rand Index)表明,改进的算法在计算大数据集时聚类质量不低于DPC和K-means算法,而且提高了DPC算法的处理效率。     

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

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

手机信令的时空密度轨迹点识别算法

手机信令具有时空序列性以及数据量大、采样频率不均、定位精度低与基站振荡等特点,导致传统手机信令聚类方法数据密度分布不均、时空开销大且聚类效果差.提出一种用于手机信令的时空密度轨迹点识别算法.将手机信令数据网格化以统一评估尺度,根据振荡噪声特征对网格簇进行时空联结减少空间不确定性和计算量,结合网络轨迹的曲折性以及移动与停...     

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

针对基于密度网格的数据流聚类算法中存在的缺陷进行改进,提出一种基于D-Strcam算法的改进算法NDD-Stream。算法通过统计网格单元的密度与簇的数目,动态确定网格单元的密度阂值;对位于簇边界的网格单元采用不均匀划分,以提高簇边界的聚类精度。合成与真实数据集上的实验结果表明,算法能够在数据流对象上取得良好的聚类质量。     

不确定GM-CFSFDP聚类算法在滑坡危险性预测中的应用

针对滑坡危险性预测中降雨等不确定诱发因素难以有效处理,CFSFDP算法需要人工尝试设置密度阈值以及对大规模数据集无法进行准确聚类等问题,为了提高滑坡危险性预测准确度,提出一种基于网格与类合并的不确定CFSFDP （简称不确定GM-CFSFDP）聚类算法.该算法首先引入不确定数据处理方法,设计了E-ML距离公式,有效刻画降雨不确定因素;其次通过网格划分的思想把大规模数据集划分到多个网格空间中,实现大规模数据有效编码;计算网格平均密度,建立网格密度阈值分布模型,动态获得网格密度阈值;最后利用层次聚类思想对关联性较高的类进行合并,构建不确定GM-CFSFDP算法模型,在延安宝塔区进行滑坡实例验证.实验结果表明不确定GM-CFSFDP聚类算法获得较高的预测精度,从而验证了该算法在滑坡危险性预测中的可行性和先进性.     

基于残差和密度网格的簇心自确认聚类算法

为了解决DPC（Clustering by fast search and ?nd of Density Peaks）算法中依赖截断距离、计算复杂度大和需要人工选取簇心的问题，提出了基于残差和密度网格的簇心自确认聚类算法。将数据对象映射到网格上，用网格对象作为聚类对象，删除不含任何信息的网格对象；用特定方式计算网格对象的密度值和距离值；接着通过残差分析确定含有簇心的网格对象；用与非边缘点的距离和自变动的阈值来处理网格边缘点和噪声点。仿真实验表明所提出的算法与一些其他聚类算法对比，有着较高的聚类精度和较低的时间复杂度。     

一种基于局部密度的网格排序聚类算法

针对复杂及带噪声的数据集的聚类问题, 提出了一种基于局部密度的网格排序策略(GSS-LD)并以其作为网格聚类的组织模式. GSS-LD一方面利用聚类的局部性质进行网格单元排序, 将基于网格的聚类问题转化为网格的排序问题;另一方面运用相对局部密度变化率的概念, 克服了传统网格聚类算法中全局性参数的局限性, 使其可以适应多密度数据集的聚类. 通过3组具有不同拓扑结构的数据集测试GSS-LD的聚类性能并同其它两种方法进行比较, 结果表明GSS-LD可以对复杂数据集进行有效聚类, 它的时间复杂度分别与数据规模及网格结构具有线性关系, 同时具有较强的噪声处理能力.