DCAD： a Dual Clustering Algorithm for Distributed Spatial Databases

Spatial objects have two types of attributes: geometrical attributes and non-geometrical attributes, which belong to two different attribute domains (geometrical and non-geometrical domains). Although geometrically scattered in a geometrical domain, spatial objects may be similar to each other in a non-geometrical domain. Most existing clustering algorithms group spatial datasets into different compact regions in a geometrical domain without considering the aspect of a non-geometrical domain. However, many application scenarios require clustering results in which a cluster has not only high proximity in a geometrical domain, but also high similarity in a non-geometrical domain. This means constraints are imposed on the clustering goal from both geometrical and non-geometrical domains simultaneously. Such a clustering problem is called dual clustering. As distributed clustering applications become more and more popular, it is necessary to tackle the dual clustering problem in distributed databases. The DCAD algorithm is proposed to solve this problem. DCAD consists of two levels of clus- tering: local clustering and global clustering. First, clustering is conducted at each local site with a local clustering algorithm, and the features of local clusters are extracted. Second, local features from each site are sent to a central site where global clustering is obtained based on those features. Experiments on both artificial and real spatial datasets show that DCAD is effective and efficient.     

一种基于双重距离的空间聚类方法

传统聚类方法大都是基于空间位置或非空间属性的相似性来进行聚类,分裂了空间要素固有的二重特性,从而导致了许多实际应用中空间聚类结果难以同时满足空间位置毗邻和非空间属性相近。然而,兼顾两者特性的空间聚类方法又存在算法复杂、结果不确定以及不易扩展等问题。为此,本文通过引入直接可达和相连概念,提出了一种基于双重距离的空间聚类方法,并给出了基于双重距离空间聚类的算法,分析了算法的复杂度。通过实验进一步验证了基于双重距离空间聚类算法不仅能发现任意形状的类簇,而且具有很好的抗噪性。     

顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例

针对Delaunay三角网空间聚类存在的不足,提出一种顾及属性空间分布不均的空间聚类方法。首先将Delaunay三角网空间位置聚类作为约束条件,采用广度优先搜索方法,以局部参数"属性变化率"作为阈值识别非空间属性相似簇的聚类过程。以城市商业中心为例,验证了该方法能够更客观地识别非空间属性相似的簇,且自适应属性阈值可以满足不同聚类需求,为城市商业中心等空间实体的提取提供了一种有效方法。     

An adaptive dual clustering algorithm based on hierarchical structure: A case study of settlement zoning

Traditional dual clustering algorithms cannot adaptively perform clustering well without sufficient prior knowledge of the dataset. This article aims at accommodating both spatial and non‐spatial attributes in detecting clusters without the need to set parameters by default or prior knowledge. A novel adaptive dual clustering algorithm (ADC+) is proposed to obtain satisfactory clustering results considering the spatial proximity and attribute similarity with the presence of noise and barriers. In this algorithm, Delaunay triangulation is utilized to adaptively obtain spatial proximity and spatial homogenous patterns based on particle swarm optimization (PSO). Then, a hierarchical clustering method is employed to obtain clusters with similar attributes. The hierarchical clustering method adopts a discriminating coefficient to adaptively control the depth of the hierarchical architecture. The clustering results are further refined using an optimization approach. The advantages and practicability of the ADC+ algorithm are illustrated by experiments on both simulated datasets and real‐world applications. It is found that the proposed ADC+ algorithm can adaptively and accurately detect clusters with arbitrary shapes, similar attributes and densities under the consideration of barriers.     

空间和属性双重约束下的自组织空间聚类研究

形式化定义了双重聚类的聚类准则及其判定方法,提出了双重聚类的两步法求解思路和自组织双重聚类算法。通过实例验证了该算法的可行性,自组织双重聚类可以发现非空间属性的聚集、延伸等空间分布特征,可以发现任意复杂形状的聚类,并降低了人为影响。     

多层次空间同位模式自适应挖掘方法

空间同位模式挖掘旨在从空间数据中发现频繁发生在邻近位置的事件集合,对于揭示地理现象间的共生规律具有重要价值。由于地理现象的空间异质特质,空间同位模式也存在区域性分异的特点,在不同空间层次上的分析结果各异。然而,现有方法仅从全局视角挖掘空间同位模式,发现局部空间同位模式依然是一个亟待解决的难题。为此,本文基于由整体到局部的思想,提出了一种多层次空间同位模式自适应挖掘方法。首先,从全局视角提取频繁的空间同位模式,将全局不频繁的空间同位模式作为候选的局部空间同位模式;然后,通过对候选局部同位模式进行自适应聚类自动识别其局部分布区域,并在这些局部区域内度量候选模式的频繁程度;进而,提出了一种叠置推绎的方法,从频繁子模式的局部区域中进一步推绎获得超模式的局部分布区域,最终生成所有频繁的局部空间同位模式集合。通过试验分析与比较发现,本文方法不仅可以发现全局的空间同位模式,还能有效提取具有区域性分布特征的局部空间同位模式,可以从多个空间层次上反映地理事件间的共生规则。     

基于空间加权距离的自适应Fuzzy C-Means算法研究

空间聚类不仅应考虑GIS对象属性特征的相似性,还应考虑对象的空间邻近性。不同属性、位置特征在聚类中起到的作用不同。采用信息熵方法计算空间距离中各属性距离、位置距离的权重,权值大小用于度量相应特征在fuzzy c-means隶属度计算时的作用大小,并引入相似性指标,当两个聚类之间的相似度高于某个合并阈值时,则对应的一对聚类进行合并,从而克服需预先设置聚类类数的问题。通过应用实例的聚类有效性分析,与普通空间距离相比,基于空间加权距离的FCM算法具有稳定性和有效性。     

一种基于语义分簇聚类的P2P空间数据索引机制

分布式环境下空间数据的索引是空间数据处理中一个关键性的基础问题,引入了控制点及四叉树划分结构,并通过Hash函数把控制点映射到Chord网络中,在此基础上提出了基于语义的分簇聚类分布式四叉树的空间数据索引机制(spatial data index based on clustering distributed quad-tree,SDI-CDQT),该机制主要包含四叉树划分、空间数据查询和分簇聚类3个子算法。实验表明,SDI-CDQT机制是可行和有效的。     

基于场论的空间聚类算法

从空间数据场的角度出发,提出了一种适用于空间聚类的场——凝聚场,并给出了一种新的空间聚类度量指标(即凝聚力)。进而,提出了一种基于场论的空间聚类算法(简称FTSC算法)。该算法根据凝聚力的矢量计算获取每个实体的邻近实体,通过递归搜索的策略,生成一系列不同的空间簇。通过模拟实验验证、经典算法比较和实际应用分析,发现所提出的算法具有3个方面的优势:(1)不需要用户输入参数;(2)能够发现任意形状的空间簇;(3)能够很好适应空间数据分布不均匀的特性。     

Graph distance and feature-guided multi-view clustering: A novel method for clustering urban buildings

Urban buildings are an integral component of urban space, and accurately identifying their spatial configurations and grouping them is vital for various urban applications. However, most existing building clustering methods only utilize the original spatial and nonspatial features of buildings, disregarding the potential value of complementary information from multiple perspectives. This limitation hinders their effectiveness in scenarios with intricate spatial configurations. To address this, this article proposes a novel multi-view building clustering method that captures cross-view information from spatial and nonspatial features. Drawing inspiration from both spatial proximity characteristics and nonspatial attributes, three views are established, including two spatial distance graphs (centroid distance graph and the nearest outlier distance graph) and a building attribute graph (multiple-attribute graph). The three graphs undergo iterative cross-diffusion processes to amplify similarities within each predefined graph view, culminating in their fusion into a unified graph. This fusion facilitates the comprehensive correlation and mutual enhancement of spatial and nonspatial information. Experiments were conducted using 10 real-world community-building datasets from Wuhan and Chengdu, China. The results demonstrate that our approach achieves 21.27% higher accuracy and 22.28% higher adjusted rand index in recognizing diverse complex arrangements compared to existing methods. These findings highlight the importance of leveraging complementary and consensus information across different feature dimensions for improving the performance of building clustering.     

顾及空间分布与注记相关性的点要素注记配置算法EI北大核心CSCD

点状要素注记自动配置问题是数据可视化研究的难点之一。稠密型点状要素注记之间往往存在着较大的相关性和冲突性,从而导致注记效率低下及配置结果不合理的问题。本文通过充分挖掘稠密型点状要素的空间分布特征和注记相关性,提出了一种顾及空间分布与注记相关性的点要素注记配置算法。首先,充分挖掘点要素的局部空间分布特征和注记间的相关性构建注记关联度模型;其次,利用基于注记关联度模型的空间聚类算法对其整体空间分布特征进行描述和分析,将单一数据集划分为若干个独立的子数据集,以消除整体求解中独立数据集产生的干扰性和模糊性;最后,利用点要素的局部空间分布特征和注记相关性构建基于增序注记关联度模型的注记次序规则,并采用多层次元启发算法求解注记配置的近似最优解。试验结果表明:在5%~40%注记密度下的点要素注记配置,新算法较传统元启发式算法的求解效率提高10.41%~28.92%,注记质量评价函数值下降5.5~35.9,有效提升了点要素注记配置的效率和质量。     

基于MRF随机场的多光谱遥感影像最优化分级聚类

有限混合模型FM的分级聚类已广泛应用于不同领域,然而,由于它的计算复杂度与观测数据量平方成正比,致使在遥感影像方面应用受到了限制。另外,多光谱图像能提供空间和光谱两类信息详细的数据,但是,大多数多光谱图像聚类方法是基于像素的聚类,仅使用了其光谱信息而忽视了空间信息。本文定义一个相对混合密度函数,通过引入一个q-参数来调节各成分密度对其混合分布的贡献,提出一种广义有限混合模型GFM．设计一种新的适用于多光谱遥感影像的GFM分级聚类算法。该算法把MRF随机场和GFM模型结合在了一起,分类数通过PLIC准则自动确定。最后,利用仿真结果验证该算法的有效性,同时通过与K均值聚类、FM分级聚类以及SVMM分级聚类的比较说明本文算法的优越性。     

面向异构空间区域分片的3RM缝隙处理模型

针对分布式环境下区域分片片段间的各种原始缝隙,提出一种3RM(Three Relational Matrix)缝隙处理模型。该模型采用两阶段流程,第1步划分空间计算单元,对区域分片边界处的要素进行聚类分组;第2步对各个空间计算单元进行缝隙处理。模型研究区域分片边界处缝隙的描述和区分方法,依据要素拓扑关系、属性关系以及精度3种关系建立了3RM缝隙处理矩阵,发现线状和面状要素在分片数据边界处的38种潜在的缝隙,并建立了相应的缝隙处理方法。运用3RM模型对异构的土地利用分片数据进行缝隙处理试验,试验结果表明,本文提出的缝隙处理模型能够有效处理实际分片数据当中的各种缝隙。     

基于MRF随机场和广义混合模型的遥感图像分级聚类

有限混合模型FM的分级聚类已广泛应用于不同领域,然而,它的计算复杂度与观测数据的平方成正比,因此,在海量数据方面的应用就受到了限制。另一方面,多光谱图像数据中同时包含有空间和光谱两类信息,但大多数基于像素的多光谱图像聚类方法,仅使用了其频谱信息而忽视了空间信息。本文提出了一种新的基于广义有限混合模型GFM的分级聚类方法,该算法把MRF随机场和GFM模型结合在一起,分类数可以通过PLIC准则自动确定。算法在执行过程中,采用K均值聚类方式获得过分类图像,分级聚类从过分类图像开始,代替原来从单点类开始的方式,这样可以方便获取GFM模型成分密度的初始参数。最后,采用由Gibbs采样器生成的仿真测试图对算法的精度进行了定量评价,通过与K均值聚类和FM聚类的比较说明了本文算法的优越性,同时用荷兰Flevoland农业地区的极化SAR图像验证了本文算法的有效性。     

An adaptive approach for the segmentation and extraction of planar and linear/cylindrical features from laser scanning data

Laser scanning systems have been established as leading tools for the collection of high density three-dimensional data over physical surfaces. The collected point cloud does not provide semantic information about the characteristics of the scanned surfaces. Therefore, different processing techniques have been developed for the extraction of useful information from this data which could be applied for diverse civil, industrial, and military applications. Planar and linear/cylindrical features are among the most important primitive information to be extracted from laser scanning data, especially those collected in urban areas. This paper introduces a new approach for the identification, parameterization, and segmentation of these features from laser scanning data while considering the internal characteristics of the utilized point cloud – i.e., local point density variation and noise level in the dataset. In the first step of this approach, a Principal Component Analysis of the local neighborhood of individual points is implemented to identify the points that belong to planar and linear/cylindrical features and select their appropriate representation model. For the detected planar features, the segmentation attributes are then computed through an adaptive cylinder neighborhood definition. Two clustering approaches are then introduced to segment and extract individual planar features in the reconstructed parameter domain. For the linear/cylindrical features, their directional and positional parameters are utilized as the segmentation attributes. A sequential clustering technique is proposed to isolate the points which belong to individual linear/cylindrical features through directional and positional attribute subspaces. Experimental results from simulated and real datasets demonstrate the feasibility of the proposed approach for the extraction of planar and linear/cylindrical features from laser scanning data.     

Spatial pattern analysis of fire events in Central India – A case study

The impact of fires on environment can have adverse effects. To fully understand the synoptic behaviour of fire events, information on the spatial distributions and their pattern are highly important. In this study, we used 9-year (1997–2005) integrated fire count datasets derived from Along Track Scanning Radiometer (ATSR) satellite to geographically map the distribution of fire events in the Madhya Pradesh state, central India. We then used robust spatial metrics to test the spatial pattern of fire events against the hypothesis of complete spatial randomness (CSR). Specifically, we used the index of dispersion, Green's index, in addition to nearest neighbour statistic for testing CSR. Also, quantification of clustering is carried out using Ripley's K-function. To spatially map the fire events, we used Kernel density estimation that relies on bi-variate probability density functions. Results from using different spatial pattern metrics and nearest neighbour statistics suggested relatively high clustering of fire events in the study area. In addition, results from Ripley's K-function suggested the fire events to be clustered at a lag-distance of ～60 mile radius. By converting original fire ignition locations that are based on historical records to continuous density surfaces, the probability of fire events could be mapped effectively using kernel density estimation. As each fire event is the result of certain spatial process including biophysical and anthropogenic attributes, results from this study can provide useful information on fire management at a local district level. Also, the analysis presented in this study illustrates how spatial patterns in the point datasets can be quantified using different dispersion indices, clustering and density estimation techniques.     

复杂环境下高分二号遥感影像的城市地表水体提取

水体指数可以抑制背景噪声和提高地表水体的可分性,已经广泛用于地表水体提取。传统FCM聚类算法考虑了地物的不确定性,但没有顾及地物的邻域空间信息,对背景异质性比较敏感。针对传统FCM聚类算法的不足,提出一种可变邻域的区域FCM聚类算法。由于复杂环境下高分二号(GF-2)遥感影像的城市地表水体具有复杂异质背景和不确定性的特点,本文利用水体指数和区域FCM聚类算法的优点,提出一种整合水体指数和区域FCM的城市地表水体自动提取算法,该算法主要步骤包括:(1)去除影像阴影后计算归一化差分水体指数NDWI(Normalized Difference Water Index);(2)区域FCM聚类算法;(3)整合水体指数和区域FCM聚类的城市地表水体自动提取算法。最后采用两景GF-2高分辨率遥感影像(广州和武汉)进行实验,验证了该算法的有效性,并与经典地表水体提取算法进行对比分析。实验结果表明:该算法具有较高的水体提取精度,城市地表水体边界既具有较好的区域完整性又保持了局部细节,同时对城市地表水体复杂背景噪声具有较好的抑制作用,有效减少传统FCM聚类算法的"胡椒盐"现象。     

一种基于场论的空间异常探测方法

从空间数据场的角度,借鉴高斯势函数发展了一种新的空间异常度度量指标。进而,提出了一种基于场论的空间异常探测方法。该方法通过空间聚类获得局部相关性较强的空间簇,并构建合理、稳定的空间邻近域。在此基础上,采用专题属性变化梯度修复策略减弱空间邻近域中潜在异常的影响,并利用空间异常度度量指标计算实体的异常度,从而探测空间异常。实验结果及实例证明了此方法的正确性。     

空间层次聚类显著性判别的重排检验方法

同时顾及空间邻近与专题属性相似的空间层次聚类是挖掘空间分布模式的一种有效手段。空间层次聚类方法虽然可以获得多层次的聚集结构,但聚类结果显著性的统计判别依然是一个尚未解决的难题。为此,本文提出了一种空间层次聚类结果显著性的统计判别方法,用于确定空间层次聚类的停止准则,减少聚类过程对参数设置的依赖。通过试验分析与比较发现,该方法能够有效判别空间层次聚类结果的显著性和确定层次聚类合并过程的停止条件,同时具有很好的抗噪性,避免随机结构的干扰。