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

空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。针对点数据集多目标空间划分问题,引入Hilbert空间填充曲线和空间分布模式探测过程,提出针对规则、随机和聚集分布模式的点数据集空间划分方法。实验结果表明,该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度3种约束条件。     

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

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

基于数据空间融合的全局计算与数据划分方法

计算与数据划分问题是影响并行程序在分布主存多处理机中执行性能的重要因素,也是并行编译优化的重点.针对该问题,提出了一套关于数据空间融合的理论框架,并基于该框架给出了一种有效的全局计算与数据划分方法,用于分布主存计算环境中的计算与数据划分问题的求解.该方法能够尽量开发计算空间的并行度,利用数据融合技术优化数据分布,并能搜寻优化的全局计算与数据划分.该方法还能很自然地与数据复制以及偏移常量的对准结合在一起,从而使得数据通信量尽可能地小.实验结果表明了所提出方法的有效性.     

一种快速空间聚类算法 *

提出了一种基于空间单元单维运算的快速聚类算法SUSDC。该算法首先将被聚类的数据逐维划分成 若干个不相交的空间单元;然后基于空间距离阈值判定相邻的空间单元是否合并,直到全部维处理完毕。实验 结果验证了SUSDC算法运算速度快,能够处理不规则形状数据和高维数据,且具有对噪声数据不敏感的特点。     

大规模核方法的随机假设空间方法

大规模核方法是大规模数据分析与挖掘的基本机器学习方法。核方法在再生核希尔伯特空间中训练线性学习器求解样本空间中的非线性问题,求解时间复杂度关于数据规模是平方级的,预测也依赖于整个训练数据,因而不适用于大规模学习问题。针对这些问题,提出了大规模核方法的有效随机假设空间方法。首先,在关于样本维度对数时间复杂度内,应用循环随机特征映射显式构造假设空间,该空间称之为循环随机假设空间。然后,在循环随机假设空间中应用线性或亚线性学习算法训练线性模型。理论上,给出了循环随机假设空间的一致泛化误差上界及其相对于最优泛化误差的收敛性。实验结果表明,大规模核方法的随机假设空间方法不仅能够显著地提高非线性核方法的训练与预测效率,而且能够保持与非线性核方法相当的预测精度。该方法有理论保障,计算复杂度低,运行效率高,是当前最高效的大规模核方法实现方法。     

两种空间分块策略K近邻搜索算法的比较研究

空间分块策略是K近邻搜索算法研究中的有效方法,然而现有算法进行空间划分时给出的子立方体大小主要取决于K值的大小,K值变化时需重新进行空间划分,影响了时间效率和稳定性。利用空间分块策略的优点,提出一种以建立离散数据空间索引为空间划分目标的K近邻搜索新算法。该算法预先对空间包围盒进行微分块,形成的子立方体结构仅与离散数据和预设参数相关,同一点云数据只需进行一次空间分配。搜索过程中,以计算点为球心建立空间动态球,判定符合条件的子立方体,进行K近邻搜索。测试结果表明,新算法较现有算法点云分配和遍历时间效率、随机点搜索时间稳定性及对不同K值的适应性等方面更具有优势。     

基于自动子空间划分的高光谱数据特征提取

针对遥感高光谱图像数据量大、维数高的特点,提出了一种自动子空间划分方法用于高光谱图像数据量减小处理。该方法主要包括3个处理步骤:数据空间划分,子空间主成分分析和基于类别可分性准则的特征选择。该方法充分利用了高光谱图像各波段数据之间的局部相关性,将整个数据划分为若干个具有较强相关性的独立子空间,然后在子空间内利用主成分分析进行特征提取,根据各类地物间的类别可分性选择有效特征,最后利用地物分类来验证该方法的有效性。实验结果表明,该方法能够有效地实现高光谱图像数据维数减小和特征提取,同现有的自适应子空间分解方法和分段主成分变换方法相比,该方法所提取的特征用于分类时能获得较好的分类精度。利用该方法进行处理,当高光谱数据维数降低了90%时,9类地物分类实验的总体分类精度可以达到80.2%。     

加权路网空间中动态聚集最近邻居查询算法

聚集最近邻居（ANN）查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足：缺少针对大规模动态路网数据的高效索引结构,在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足,提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引,提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制（IER）算法结合起来的剪枝方法,以完成静态空间下的ANN查询;随后针对动态场景下数据点位置频繁更新的问题,加入时间窗口及安全区域更新策略,以减少算法的重复计算次数,实验结果表明效率能提高8%～85%;最后针对路网权重变化的ANN查询问题,提出两个基于校正的连续查询方法,在历史查询结果的基础上,根据权重变化的增量来得到当前的查询结果,在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明,所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。     

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

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

一种面向空间数据库矢量数据的授权模型与实现方法

空间数据库的广泛应用给人们的生活带来极大便利的同时,也带来了严重的安全威胁.空间应用要求授权系统支持灵活的细粒度授权策略以及否定策略,提供高效的授权实现技术.针对这些安全需求,提出一种基于谓词的矢量数据授权模型,并依据空间数据库管理系统在实现上的特征,采用谓词改写的方法实现对矢量数据的有效授权.和现有工作相比,该模型利用授权谓词表示授权区域,具有更灵活的表达能力,且支持否定授权;所提出的谓词改写的方式不仅避免授权判定时额外增加的一次空间查询,而且可以保证与空间数据库管理系统的低耦合度,还有利于空间谓词的优化,减少空间谓词的冗余.实验证明,该授权模型和实现方法能够满足空间应用的安全需求,实现对空间数据库矢量数据的访问控制和有效授权.     

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

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

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.     

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

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

基于改进流形距离的粗糙集k-means聚类算法

针对现有的基于流形距离的聚类算法对“绝对流形”数据集较“相对流形”数据集聚类效果佳和参数[ρ]在较大范围内变化时,聚类性能较差等问题,提出基于改进流形距离的粗糙集k-means聚类算法。该算法通过用属性划分和最大最小距离选择初始聚类中心,以改进的流形距离和粗糙集优化k-means,并结合终止判断条件以达到解决边界数据聚类问题和提升聚类效果的目的。仿真结果表明：该算法对“绝对流形”和“相对流形”数据集聚类效果均有较好改善,且参数变化对聚类性能影响较大。     

一种应用于机器人导航的激光点云聚类算法

提出一种适用于机器人导航和环境理解的聚类算法,该算法用来处理各向异性分布的点云数据.算法的基本思想是基于点云的密度分布变化和空间位置分布的不同进行聚类,将信息聚类思想触入传统的DBSCAN算法,既保留了DBSCAN算法抗噪声能力强的优点,又结合点云的空间概率分布改善了聚类结果.算法采用自适应的实时参数估计方法克服全局参...     

基于自组织神经网络的城市功能分区研究

城市功能分区是指运用有关模型和方法，使城市空间形成明确的功能单元和有序的空间结构，空间聚类是城市功能分区的一种常用方法。基于自组织映射神经网络，该文提出了一种组合式的城市功能区聚类方法，根据位置-属性一体化思想，综合考虑了影响城市功能分区的位置数据和属性信息，对城市功能区进行空间聚类计算。该方法挖掘了空间位置数据和属性信息中隐含的空间聚集信息，保证了城市功能分区结果的可靠性。实例分析表明，该方法的聚类结果可以为城市功能分区提供准确、可靠的依据。     

基于消息传递的谱聚类算法

谱聚类将数据聚类问题转化成图划分问题,通过寻找最优的子图,对数据点进行聚类。谱聚类的关键是构造合适的相似矩阵,将数据集的内在结构真实地描述出来。针对传统的谱聚类算法采用高斯核函数来构造相似矩阵时对尺度参数的选择很敏感,而且在聚类阶段需要随机确定初始的聚类中心,聚类性能也不稳定等问题,本文提出了基于消息传递的谱聚类算法。该算法采用密度自适应的相似性度量方法,可以更好地描述数据点之间的关系,然后利用近邻传播（Affinity propagation,AP）聚类中“消息传递”机制获得高质量的聚类中心,提高了谱聚类算法的性能。实验表明,新算法可以有效地处理多尺度数据集的聚类问题,其聚类性能非常稳定,聚类质量也优于传统的谱聚类算法和k-means算法。     

DCT子空间的邻域加权模糊C均值聚类算法

模糊C均值聚类是一种有效的图像分割方法, 但存在因忽略空间上下文信息和结构信息而易为噪声所干扰的现象. 为此提出了DCT子空间的邻域加权模糊C均值聚类方法. 该方法首先结合分块的思想, 对图像块进行离散余弦变换(discrete cosine transform,DCT), 建立了一个基于图像块局部信息的相似性度量模型; 然后定义目标函数中的欧式距离为邻域加权距离; 最后将该方法应用于加噪的人工合成图像、自然图像和MR图像. 实验结果表明, 该方法能够获得较好的分割效果, 同时具有较强的抗噪性.     

半监督谱聚类特征向量选择算法

对于一个K类问题,Ng-Jordan-Weiss(NJW)谱聚类算法通常采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量作为数据的一种表示。然而,对于某些模式识别问题,这K个特征向量不一定能够体现原始数据的结构。文中提出一种半监督谱聚类特征向量选择算法。该算法利用一定量的监督信息寻找能够体现数据结构的特征向量组合,进而获得优于传统谱聚类算法的聚类性能。UCI标准数据集和MNIST手写体数据集上的仿真实验验证该算法的有效性和鲁棒性。