Hilbert填充曲线与空间分布模式探测结合的点数据集空间划分方法

空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。本文针对点数据集多目标空间划分问题,在Hilbert空间填充曲线的基础上建立随机、规则、聚集三类空间分布模式的判定模型,设计针对均匀和随机分布模式的等差划分以及针对聚集分布模式的迭代寻优划分。实验表明该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度三种约束条件。     

基于PostGIS的线要素空间聚合方法

针对当前常规方法线空间流量数据聚合效率低的问题，提出基于PostGIS的流空间线要素聚合方法。通过离散化所有的线为点集，建立点集的空间索引，计算点集的唯一点集，对唯一点集上的每个点累加所有与该点重叠的属性值并进行更新，根据点的序列号和上一步更新的属性值，重新连接该条线上所有的点，在属性值变化处进行打断形成新的线要素。在此基础上，去除空间重叠的线要素和图形为空的线要素得到最后的线聚合结果。实验结果表明，该方法以矢量数据形式输出的线聚合结果正确，提取速度显著提升，有效地解决了大量矢量线数据融合时常规方法效率低下的问题。     

面向断层划分的点集聚类方法

在三维地质建模过程中存在断层划分问题,多个断层面的数据常以单个点集形式给出,无法判定每个断层面所包含的点,为了解决该问题,提出一种方法对点集进行划分。该方法结合空间聚类的思想,使得划分结果包含多个点集,并且每一个点集都能够描述一个断层面。该方法包含3个步骤,先计算每个点的法矢量和平面度,根据点间的临近程度和法矢量夹角,对平面度较大的点进行初次划分。最后通过比较的方法,对平面度较大的点与初次划分失败的点进行二次划分。给出了一个算例,其结果验证了该方法的可行性。     

基于基尼系数的用户兴趣分布模式度量方法

目前关于用户兴趣方面的研究大多数是根据用户兴趣的相似性划分用户群,缺乏对用户兴趣分布模式的度量。为此,提出一种用户兴趣分布模式度量方法。根据向量空间模型进行用户兴趣建模,利用基尼系数和洛伦茨曲线划分用户兴趣分布模式。Movielens数据集上的实验结果验证了该方法的有效性。     

一种新的局部空间排列算法

局部切空间排列算法(local tangent space alignment,LTSA)是一种经典的非线性流形学习方法,能够有效地对非线性分布数据进行降维,但它无法学习局部高曲率数据集.针对此问题,给出了描述数据集局部曲率的参数,并提出一种局部最小偏差空间排列(locally minimal deviation spacealignment,LMDSA)算法.该算法考虑到局部切空间低鲁棒性的缺陷,在计算局部最小偏差空间的同时,能够发现数据的局部高曲率现象,通过参数控制及邻域间的连接信息,减少计算局部高曲率空间的可能,进而利用空间排列技术进行降维,手工流形及真实数据集的实验证实了该算法学习局部高曲率数据集的有效性.     

稀疏条件下的重叠子空间聚类算法

现有子空间聚类算法不能很好地平衡子空间数据的稠密性和不同子空间数据稀疏性的关系,且无法处理数据的重叠问题。针对上述问题,提出一种稀疏条件下的重叠子空间聚类(OSCSC)算法。算法利用L1范数和Frobenius范数的混合范数表示方法建立子空间表示模型,并对L1范数正则项进行加权处理,提高不同子空间的稀疏性和同一子空间的稠密性;然后对划分好的子空间使用一种服从指数族分布的重叠概率模型进行二次校验,判断不同子空间数据的重叠情况,进一步提高聚类的准确率。在人造数据集和真实数据集上分别进行测试,实验结果表明,OSCSC算法能够获得良好的聚类结果。     

利用子空间划分的局部离群数据挖掘算法

目前大多数局部离群数据挖掘算法需人为事先设置参数或阈值,且难以应用到高维数据集.给出一种新的局部离群数据挖掘算法PSO-SPLOF,该算法首先将数据集划分为互不相交的子空间,利用偏斜度判断子空间划分的优劣,并采用微粒群算法搜索最优划分子空间集;其次针对每个最优划分子空间,计算其数据对象的局部离群因子SPLOF值,并用SPLOF值来度量数据对象的局部偏离程度.最后采用离散化的天体光谱数据作为数据集,实验验证了PSO-SPLOF算法具有受人为因素影响小、伸缩性强和运算效率高等优点.     

一种基于质量估算的空间数据流聚类算法研究

针对传统的基于网格密度的数据流聚类方法丢失数据的空间位置特性的缺陷,提出了一种基于质量估算（mass estimation）的空间数据流聚类方法。通过 树进行空间划分,可将到达数据映射到不同的划分区域,在树得到质量（mass）的基础上,进行各子区域的密度推算的同时引入衰减因子,以及在线动态维护微簇,可精确反映空间数据流的演化信息。该方法在真实数据与模拟数据的综合试验中验证了算法的聚类效果与高效率性,并通过与传统数据流聚类算法的对比,进一步体现出其在聚类效果上的优势。该方法能够在保证较低的时间复杂度的基础上,更好的保留了数据的空间位置特性,因而能够更好的适应空间数据流聚类的需求。     

动态空间集下的轮廓更新算法

现有的轮廓查询算法都是针对静态空间集设计的,不适用于空间集变化的情况。针对上述问题,提出动态空间集下的轮廓更新算法。当空间集发生变化导致现有轮廓失效时,无须重新计算所有数据点,只需在共享策略的基础上对部分数据点进行判断,即可快速完成轮廓的更新。理论分析和实验结果证明,该算法可有效减少冗余操作,保证结果的正确性和完整性。     

基于商空间粒度聚类的异常入侵检测*

针对异常入侵检测技术中传统聚类方法需要被检测类大小均衡的问题,在商空间粒度理论的基础上,论述了商空间粒度变换可以使复杂问题在不同的粒度世界求解,最终使整个问题得到简化。分析了商空间划分与聚类操作的相似性,提出了基于商空间的粒度聚类方法,并将该方法与入侵检测技术相结合,构建了基于商空间粒度聚类的入侵检测系统,用于对KDD CUP 1999数据集的异常入侵检测。实验结果表明,该入侵检测系统的性能明显优于基于传统聚类方法的入侵检测系统,从而证明了该方法的正确性和有效性。     

Fuzzy spectral clustering with robust spatial information for image segmentation

In recent years, spectral clustering has become one of the most popular clustering algorithms in areas of pattern analysis and recognition. This algorithm uses the eigenvalues and eigenvectors of a normalized similarity matrix to partition the data, and is simple to implement. However, when the image is corrupted by noise, spectral clustering cannot obtain satisfying segmentation performance. In order to overcome the noise sensitivity of the standard spectral clustering algorithm, a novel fuzzy spectral clustering algorithm with robust spatial information for image segmentation (FSC_RS) is proposed in this paper. Firstly, a non-local-weighted sum image of the original image is generated by utilizing the pixels with a similar configuration of each pixel. Then a robust gray-based fuzzy similarity measure is defined by using the fuzzy membership values among gray values in the new generated image. Thus, the similarity matrix obtained by this measure is only dependent on the number of the gray-levels and can be easily stored. Finally, the spectral graph partitioning method can be applied to this similarity matrix to group the gray values of the new generated image and then the corresponding pixels in the image are reclassified to obtain the final segmentation result. Some segmentation experiments on synthetic and real images show that the proposed method outperforms traditional spectral clustering methods and spatial fuzzy clustering in efficiency and robustness.     

基于空间特征的谱聚类含噪图像分割

为克服传统谱聚类算法应用到含噪图像分割时易受到图像中噪声影响的问题,提出一种基于空间特征的谱聚类含噪图像分割算法。该方法利用图像各个像素的灰度信息、局部空间邻接信息及非局部空间信息设计像素的三维特征,通过引入空间紧致性函数建立像素特征点与其K个最近邻之间的相似性,进而利用谱聚类算法得到图像的最终分割结果。实验中采用含噪的人工图像、自然图像及合成孔径雷达图像与空间模糊聚类、规范切谱聚类和Nystrm方法3种算法进行对比实验,实验结果验证文中方法能克服图像中噪声影响并取得较满意的分割效果。     

基于空间邻域加权的模糊C-均值聚类及其应用研究*

针对模糊C-均值聚类法用于图像聚类时仅利用了像素的灰度信息,而忽视空间位置信息,导致在噪声区域和边界处有误分类现象,提出一种新的基于空间邻域加权的模糊C-均值图像聚类法。首先,定义了一个空间邻域信息函数,该函数能够有力抑制噪声点,同时能够很好保留边界的特性;其次,设计了具有空间约束的样本邻域信息加权隶属度矩阵;最后,将该方法应用于人工合成图像和模拟MR脑图像的聚类。实验结果表明,该方法能够获得较好的聚类效果,同时具有较强的抑制噪声的能力。     

基于空间邻近的点目标聚类方法

空间聚类是空间数据挖掘和知识发现领域的主要研究方向之一,但点目标空间分布密度的不均匀、分布形状的多样化,以及"多桥"链接问题的存在,使得基于距离和密度的聚类算法不能高效且有效地识别聚集性高的点目标。提出了基于空间邻近的点目标聚类方法,通过Voronoi建模识别点目标间的空间邻近关系,并以Voronoi势力范围来定义相似度准则,最终构建树结构以实现点目标的聚集模式识别。实验将所提算法与K-means、具有噪声的基于密度的聚类(DBSCAN)算法进行比较分析,结果表明算法能够发现密度不均且任意形状分布的点目标集群,同时准确划分"桥"链接的簇,适用于空间点目标异质分布下的聚集模式识别。     

A data clustering algorithm for stratified data partitioning in artificial neural network

The statistical properties of training, validation and test data play an important role in assuring optimal performance in artificial neural networks (ANNs). Researchers have proposed optimized data partitioning (ODP) and stratified data partitioning (SDP) methods to partition of input data into training, validation and test datasets. ODP methods based on genetic algorithm (GA) are computationally expensive as the random search space can be in the power of twenty or more for an average sized dataset. For SDP methods, clustering algorithms such as self organizing map (SOM) and fuzzy clustering (FC) are used to form strata. It is assumed that data points in any individual stratum are in close statistical agreement. Reported clustering algorithms are designed to form natural clusters. In the case of large multivariate datasets, some of these natural clusters can be big enough such that the furthest data vectors are statistically far away from the mean. Further, these algorithms are computationally expensive as well. We propose a custom design clustering algorithm (CDCA) to overcome these shortcomings. Comparisons are made using three benchmark case studies, one each from classification, function approximation and prediction domains. The proposed CDCA data partitioning method is evaluated in comparison with SOM, FC and GA based data partitioning methods. It is found that the CDCA data partitioning method not only perform well but also reduces the average CPU time.     

Decentralized spatial partitioning for multi-vehicle systems in spatiotemporal flow-field

We consider the problem of characterizing a generalized Voronoi diagram/partition of a convex polygon in a two-dimensional Euclidean space that encodes information about the proximity relations between a team of aerial/marine vehicles and arbitrary points in the partition space. These proximity relations are determined by the time required for each vehicle to reach an arbitrary point (time-to-go) in the partition space when driven by a locally optimal feedback control law in the presence of a spatiotemporal drift field. The main contribution of this work is the presentation of a partitioning algorithm, which is decentralized, in the sense that each vehicle can independently compute its corresponding cell from the generalized Voronoi partition without computing or receiving information about the cells of the other vehicles. Finally, we present numerical simulations using data from real drift fields to illustrate the key features of the decentralized solution to the proposed class of spatial partitioning problems.     

基于结合空间信息的FCM聚类的分水岭图像分割

提出了一种分水岭变换和结合空间信息的FCM聚类相结合的图像分割方法。方法采用基于图论的结合区域特征信息和空间信息的距离度量,以分水岭变换得到的图像分割小区域为节点构建一个连通加权图,通过计算图上不同节点之间的最短路径来度量不同区域之间的相似程度,从而实现过分割小区域的合并。该方法综合考虑了区域的特征之间的差异和空间位置的差异,与传统的FCM聚类方法在特征空间进行聚类相比,具有较强的噪声抑制能力。图像分割的实验结果证明了该算法的可行性和有效性。     

A multiobjective spatial fuzzy clustering algorithm for image segmentation

This article describes a multiobjective spatial fuzzy clustering algorithm for image segmentation. To obtain satisfactory segmentation performance for noisy images, the proposed method introduces the non-local spatial information derived from the image into fitness functions which respectively consider the global fuzzy compactness and fuzzy separation among the clusters. After producing the set of non-dominated solutions, the final clustering solution is chosen by a cluster validity index utilizing the non-local spatial information. Moreover, to automatically evolve the number of clusters in the proposed method, a real-coded variable string length technique is used to encode the cluster centers in the chromosomes. The proposed method is applied to synthetic and real images contaminated by noise and compared with k-means, fuzzy c-means, two fuzzy c-means clustering algorithms with spatial information and a multiobjective variable string length genetic fuzzy clustering algorithm. The experimental results show that the proposed method behaves well in evolving the number of clusters and obtaining satisfactory performance on noisy image segmentation.     

基于Spark的点排序识别聚类结构算法

点排序识别聚类结构(Ordering Points to Identify the Clustering Structure,OPTICS)的密度聚类算法能以可视化的方式导出数据集的内在聚类结构,并且可以通过簇排序提取基本的聚类信息。但是该算法由于时空复杂度较高,不能很好地适应当今社会出现的大型数据集。随着云计算和并行计算的发展,提供了一种解决OPTICS算法复杂度缺陷的方法和一种建立在基于Spark内存计算平台的点排序识别聚类结构并行算法。测试的实验结果表明,它能极大地降低OPTICS算法对时间和空间的需要。