基于密度的空间聚类算法研究

基于密度的聚类算法作为数据挖掘方法中的一种主要方法,不仅可以从数据集中发现任意形状的簇,而且可以观察到一个并发的、完整的聚类结构,以及具有对噪声数据不敏感的特点.针对目前常用的几种基于密度的聚类算法及改进算法进行讨论,分析了这些密度聚类算法各自的优缺点,并且以地理信息系统为应用研究背景,提出了基于密度的聚类算法与GIS相结合,通过对多维数据属性特征的提取,扩展到多维数据的处理,在三维空间地形数据中的分析中取得了高效的聚类结果.     

基于密度的空间聚类算法研究

基于密度的聚类算法作为数据挖掘方法中的一种主要方法,不仅可以从数据集中发现任意形状的簇,而且可以观察到一个并发的、完整的聚类结构,以及具有对噪声数据不敏感的特点。针对目前常用的几种基于密度的聚类算法及改进算法进行讨论,分析了这些密度聚类算法各自的优缺点,并且以地理信息系统为应用研究背景,提出了基于密度的聚类算法与GIS相结合,通过对多维数据属性特征的提取,扩展到多维数据的处理,在三维空间地形数据中的分析中取得了高效的聚类结果。     

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

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

基于连通核的鲁棒模糊C-均值聚类算法

提出一种新的鲁棒核模糊C-均值聚类算法.将连通核与AFCM(Alternative fuzzy C-means)聚类算法相结合,给出基于连通核的核AFCM:CRKFCM(Connectivity kernel based robust fuzzy C-means).CRKFCM一方面有效地利用了连通核,可以对任意形状数据聚类,且避免了核参数的选取问题;另一方面在特征空间使用非欧氏距离,可以有效地处理含噪声数据的聚类问题.实验结果表明,与原有的AFCM和连通核硬C-均值(CKHCM,Connectivity kernel based hard C-means)聚类算法相比,新算法在处理噪声环境中的任意形状聚类问题方面更有效.     

SUDBC:一种基于空间单元密度的快速聚类算法

随着数据规模越来越大,要求聚类算法有很高的执行效率,很好的扩展性,能发现任意形状的聚类以及对噪音数据的不敏感性.提出了一种基于空间单元密度的快速聚类算法SUDBC,该算法首先将被聚类的数据划分成若干个空间单元,然后基于空间单元密度将密度超过给定阈值的邻居单元合并为一个类.实验结果验证了SUDBC算法具有处理任意形状的数据和对噪音数据不敏感的特点.     

基于距离和密度的多阶段聚类

随着聚类技术的发展．对不同密度的数据集的聚类需求也越来越迫切。为了解决不同密度数据集的聚类问题,提出一种基于距离和密度的多阶段聚类算法MCDD。该算法主要采用多阶段密度处理技术提取不同密度的聚类,同时使用密度因子提高聚类的精度．最后通过使用距离阈值的方法去除孤立点和噪声数据。实验表明,该算法在扩展性方面表现良好．对任意形状和大小的聚类都可以很好地处理,并能够很好地识别出孤立点或噪声,在处理多密度聚类方面有很好的精度。     

适合多密度的DBSCAN改进算法

针对具有噪声的基于密度的空间聚类(DBSCAN)算法使用固定参数Eps和Minpts,导致多密度的数据聚类效果不理想的问题,提出了一种适合多密度的DBSCAN改进算法.对数据进行预处理,识别出每个数据对象周围的密度,据此自动生成适合本区域密度的密度阈值.聚类结束前,采用密度阈值进行扩展聚类;进行下一个簇的聚类时自动生成适合本区域的密度阈值,依次进行,直到达到聚类停止条件.大量实验表明:所提算法能有效地对多密度,任意形状的数据进行聚类.     

基于GIS的空间邻接关系的聚类算法及其实现

随着空间数据挖掘技术和GIS的发展与结合,人们逐渐将空间数据挖掘技术应用于GIS的很多相关领域.聚类分析是空间数据挖掘的一种方法,聚类分析能从空间数据库中直接发现一些有用的聚类结构.为了实现空间复杂地理对象的聚类分析,本文引入了一种空间聚类算法,并将其应用于土地规划.在具体的模拟试验中,利用该算法将相邻的并且符合选取条件的空间目标聚类成一类,实现了能够发现任意形状、并满足特定约束条件的聚类.     

一种基于网格的引力聚类算法

将万有引力和牛顿第二运动定律的思想引入到聚类分析中,提出了一种基于网格的引力聚类算法GCABG.该算法可以自动决定目标数据集中的簇的个数,并且能发现任意形状的簇且可以过滤"噪声"数据.实验结果表明GCABG可以产生高质量的聚类结果.     

一种基于划分的不同参数值的DBSCAN算法

聚类是数据挖掘领域中一个重要的研究方向,DBSCAN是一种基于密度的聚类算法.该算法将具有足够高密度的区域划分成簇,并可以在带有“噪声”的空间数据库中发现任意形状的簇.分析DBSCAN算法发现存在如下问题：当数据分布不均匀时,由于使用统一的全局变量,使得聚类的效果差.针对这一缺陷,提出了一种基于数据划分的思想,并对各个局部数据集采取不同的参数值分别进行聚类,最后合并各局部聚类结果.实验结果表明,改进后的算法有效并可行.     

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

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

A distance-relatedness dynamic model for clustering high dimensional data of arbitrary shapes and densities

It is important to find the natural clusters in high dimensional data where visualization becomes difficult. A natural cluster is a cluster of any shape and density, and it should not be restricted to a globular shape as a wide number of algorithms assume, or to a specific user-defined density as some density-based algorithms require.In this work, it is proposed to solve the problem by maximizing the relatedness of distances between patterns in the same cluster. It is then possible to distinguish clusters based on their distance-based densities. A novel dynamic model is proposed based on new distance-relatedness measures and clustering criteria. The proposed algorithm “Mitosis” is able to discover clusters of arbitrary shapes and arbitrary densities in high dimensional data. It has a good computational complexity compared to related algorithms. It performs very well on high dimensional data, discovering clusters that cannot be found by known algorithms. It also identifies outliers in the data as a by-product of the cluster formation process. A validity measure that depends on the main clustering criterion is also proposed to tune the algorithm's parameters. The theoretical bases of the algorithm and its steps are presented. Its performance is illustrated by comparing it with related algorithms on several data sets.     

从空间数据库发现聚类：一种基于数学形态学的算法

聚类算法能从空间数据库中直接发现一些有意义的聚类结构而不需要背景知识，是空间数据发掘和知识发现的重要手段。在分析已有聚类算法的基础上，提出了一种基于数学形态学的聚类算法，该算法能够处理任意形状的聚类，采用启发式方法自动确定最优聚类数。同时，该算法也可以在矢量型空间数据库中得到实现。试验表明算法是可行和有效的，且能处理存在噪音的数据。     

Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space

We study the problem of clustering data objects with location uncertainty. In our model, a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. One method to cluster such uncertain objects is to apply the UK-means algorithm [1], an extension of the traditional K-means algorithm, which assigns each object to the cluster whose representative has the smallest expected distance from it. For arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration of the pdf. We study two pruning methods: pre-computation (PC) and cluster shift (CS) that can significantly reduce the number of integrations computed. Both pruning methods rely on good bounding techniques. We propose and evaluate two such techniques that are based on metric properties (Met) and trigonometry (Tri). Our experimental results show that Tri offers a very high pruning power. In some cases, more than 99.9% of the expected distance calculations are pruned. This results in a very efficient clustering algorithm. ¹     

一种抗噪的移动时间势能聚类算法

移动时间层次聚类是一种势能聚类算法,具有较好的聚类效果,但该算法无法识别数据集中存在的噪声数据点。为此,提出一种抗噪的移动时间势能聚类算法。通过各个数据点的势能值以及数据点之间的相似度找到各个数据点的父节点,计算各数据点到父节点的距离,按照该距离以及数据点的势能得到λ值,并依照λ值大小构造递增曲线,通过递增曲线中的拐点来识别出噪声点,将噪声数据归到新的类簇中,对去除噪声点后的数据集,根据数据点与父节点的距离进行层次聚类来获得聚类结果。实验结果表明,该算法能够识别出数据集中的噪声数据点,从而得到更优的聚类效果。     

软距离计算的地震聚类方法*

传统的基于真实距离的聚类分析方法不利于地震不同断层破裂传播和愈合速度的精确计算。为提高地震预测精度,提出并建立了基于软距离计算的聚类方法。给出了基于软距离聚类过程、软距离计算方法以及具体的基于软距离计算的聚类算法。以现实的强震样本点作为聚类数据源,采用该聚类方法以及其它传统聚类方法对该样本数据进行聚类分析。分析结果表明,采用该聚类方法获得的聚类中心点更接近地壳应力场演变的客观真实性,该聚类分析方法为地震的断层带下次发生强震的精确计算提供了很好的计算依据。     

一种基于熵的聚类算法

给出了一种以Reny熵为评价准则的聚类算法,通过非参数估计法估计密度函数,再利用类内熵和类间熵进行聚类和确定聚类的数目。这种算法不需要用户输入与聚类有关的参数,能根据由数据的分布的特性自动获取要聚类的数目,并能发现任意形状和任意大小的聚类。实验结果显示了算法的有效性和优越性。