移动查询点的最近邻查询方法研究

移动查询点的最近邻查询在时空数据库查询的领域具有很重要的地位。本文提出了一个以处理动态环境下的K个最近邻居(K-NN)查询问题的有效的方法。     

移动对象的反向最近邻查询方法研究

在移动对象允许相互提供某些服务的地方,反向最近邻居(RNN)能有效地运用到许多应用中。提出了一个在指定时间间隔内计算一个查询点的RNN查询的有效方法,在这里假设查询和数据点都在空间内连续移动。做为解决子问题的方法,同时提出了解决连续移动点NN查询的算法。     

移动点的反向最近邻查询

反向最近邻（RNN）查询是空间数据库查询的一个重要的问题。随着无线通讯的发展，时空数据库中反向最近邻查询问题越来越受到关注。本文基于Voronoi图的定义和性质，采用一种不同于Delaunay三角剖分的另外一种三角剖分进行研究，其优势在于对于某个特定点，包含它的三角形的数量较少，查询效率较高。     

约束的移动对象最近邻轨迹查询

提出了一种新的查询概念,即约束的移动对象最近邻轨迹(constrained nearest neighbor search on moving objects trajectories,简称CNNMOT)查询.针对两阶段算法分阶段处理最近邻查询和范围查询的缺陷,对传统空间最近邻算法进行了改进和扩展,使其能够合并到一步完成,并对传统的mindist定义进行了修改.实验结果表明:该改进算法能较好地克服两阶段算法的缺陷,并在数据量较大时仍保持较高的性能.     

空间数据库反向最近邻聚类方法

针对当前空间数据库聚类方法未考虑降维后的距离特征反向结果, 导致空间数据分量失真, 存在聚类精度低、 耗时长的问题, 提出一种空间数据库反向最近邻聚类方法. 首先, 通过选取训练样本集实现核矩阵的特征分解, 获得其距离特征修正值去除初始值的影响; 然后, 根据核主成分分析（KPCA）降维并结合降维后的距离特征反向结果, 利用反向最近邻聚类方法与扩展的部分失真搜索法相结合, 实现空间数据的聚类; 最后利用选定的聚类中心对数据集进行计算, 计算数据集第一维分量与聚类中心第一维分量之间的失真, 得到反向最近邻, 直至所有空间数据均找到所属类别, 最终完成空间数据库反向最近邻聚类. 实验结果表明, 该方法提高了空间数据的聚类精度, 减少了空间数据聚类所用时间.     

空间网络数据库中基于M-tree索引的反最近邻查询算法

欧式空间中的反k最近邻查询算法不适用于空间网络环境,故采用任意度量空间中的M-tree索引结构,进行空间网络数据库中的反k最近邻查询处理.首先通过预计算的方法得到网络距离信息,依据此距离信息,对空间网络对象建立M-tree索引结构.然后,给出并证明了M-tree中间结点修剪定理,提出一种适用于空间网络环境的反k最近邻查询算法.最后实验验证了该算法的有效性.     

道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。     

基于Voronoi图的最近邻查询的索引结构的研究

基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中,基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树。进而提出了基于VR树索引结构的NN查询算法并对这该算法进行分析,在理论上证明了这个算法较基于R树索引结构的最近邻查询算法优。     

基于路网的连续K最近邻查询

连续K最近邻(CKNN)查询是最近邻查询的扩展,可广泛地应用于地理信息系统、城市规划、智能交通等领域.CKNN查询搜索某一路径上所有点的K个最近的感兴趣对象.本文研究基于交通路网的连续K最近邻查询问题,不同于传统的基于欧式空间的CKNN查询,基于路网的CKNN查询中对象间的距离度量不再是欧式距离,而是基于路网的最短可达距离.显然,传统的基于欧式距离的CKNN查询算法并不能直接应用于基于路网的CKNN查询问题.本文提出了一种基于路网的高效的CKNN查询算法-IIE算法,广泛实验表明本文提出的IIE算法优于传统的IE算法.     

基于格网划分的道路最近邻查询算法

针对现有道路最近邻查询算法均以数据点作为道路端点进行查询,并未考虑数据点在道路上的情况,使得在大数据量时查询效率不够理想的问题,利用格网划分算法进行解决。利用分治法的思想,将查询区域进行格网划分,缩小有效的查询区域,快速定位查询点所在道路,进而找到最近邻数据点。研究结果表明:当数据量足够大时,格网划分算法与增量网络扩张(INE)算法相比,查询时间明显降低,效率明显提升,格网划分查询的时间复杂度为O(1);当数据量较少时,格网划分算法与INE算法相比,查询时间减少并不明显,表明格网划分算法更适用于大数据量最近邻查询。     

连续近邻查询方法的研究

连续近邻查询(CNN)是时空数据库中一种重要的查询类型。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文利用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

一种新的基于伪最近邻算法的降水预报方法

分析北京地区日降雨量资料,相较于其他降雨事件,大雨或暴雨事件发生的次数较少,因此该地区的降水量预报属于样本不均衡问题。在样本不平衡的情况下,K最近邻(PNN)算法的分类误差率将会大大提高,这也就使传统的基于K最近邻算法的降水量预报方法的应用受到了限制。针对北京地区降水量预报这一样本不均衡问题,应用伪最近邻算法构建了北京市的降水量预报模型。该方法利用北京地区日降雨量资料和美国国家环境预报中心全球格点资料,将降雨量作为类,将美国国家环境预报中心全球格点资料的各种因子场作为天气样本特征,通过决策规则实现最优分类。利用提出的降水预报模型对北京地区2010年6~8月进行了24 h降水预报,实验结果表明,提出的预报方法对于降水等级预报的预报准确率以及晴雨预报的TS评分、正样本概括率和漏报率均优于传统的K最近邻预报方法,该方法具有较好的预报效果。     

最近邻搜索用于分类问题的一种改进

最近邻搜索广泛应用于分类问题,其最显著的优点是分类准确率高、泛化性能好.但现有最近邻分类算法都存在着一个弱点——样本集增大分类计算量也显著增大.为了克服这一不足,本文基于一个新的思路,提出了最近邻分类方法的一种改进方法.该方法在进行最近邻分类时,不一定要找到待分类点的最近邻点,而只要知道最近邻点的类别即可,大大地减少了最近邻搜索时的计算量.用经典的分类问题双螺线问题(TSP)以及其他几个例子,就该改进方法的分类效果、分类速度和学习性能等3个方面进行了测试,并与经典的K维双叉树(KD树)最近邻搜索法以及压缩近邻法进行了比较.结果表明,就综合性能而言,本文改进方法是有竞争力的.     

非线性半参数模型最小二乘近邻估计

目前对非线性半参数模型的研究尚处于初级阶段,关于非线性半参数模型的计算理论还未见实质性报道.基于非线性半参数模型最小二乘近邻估计,给出了其参数分量和非参数分量估计的构造式,导出了参数分量和非参数分量顾及二次项直接解法的非线性直接解法.基于工程实际中的非线性模型用模拟数据进行计算,证明对于非线性半参数模型最小二乘近邻估计,可采用顾及二次项的直接解法.     

融合相对密度与近邻关系的密度峰值聚类算法

密度峰值聚类算法(density peaks cluster,DPC)是一种基于密度的聚类算法,该算法可以聚类任意形状的类簇.在类簇间有密度差距的数据集上,DPC不能准确地选择聚类中心.DPC的非中心点分配策略会引起连续错误,影响算法的聚类效果.模糊k近邻密度峰值算法(fuzzy k-nearest neighbor DPC,FKNN-DPC)是一种改进的DPC算法,该算法采用边界点检测并结合2步分配策略来避免连续错误.当类簇间有密度差距时,FKNN-DPC的边界点检测效果不理想,此外,其非中心点分配策略缺乏对样本近邻信息的考虑.定义相对密度(relative density)并结合近邻关系(nearest neighbor relationship)提出RN-DPC算法解决上述问题.针对DPC因为类簇间的密度差距而不能准确选择聚类中心的问题,定义相对密度用于消除类簇间的密度差距.基于反向k近邻关系检测边界点并且引入共享最近邻关系来对FKNN-DPC的分配策略进行改进.RN-DPC算法在人工数据集和真实数据集上分别与不同的聚类算法进行了对比,实验结果验证了RN-DPC算法的有效性和合理性.     

一维双原子链晶格振动中的次近邻

目的研究一维双原子链的色散关系,并与最近邻近似下的结果进行比较。方法以一维离子晶体为例,分别考虑次近邻原子和所有原子的作用,利用数值模拟的方法。结果得到了一维双原子链的色散关系的一般表达式,即ω2=2m11m2{-x(m1 m2)±[x2(m1 m2)2-4m1m2(x2-y2)]}。结论对一维双原子链来说,次近邻对色散关系的贡献也是比较大的。     

Theoretical analysis of the confidence metrics for nearest neighbor classifier

Confidence value plays a vital role in the decision of rejection threshold and the integration of multiple classifiers. Nearest neighbor (NN) classifier is the most traditional and most common nonparameter statistical pattern classifier. However, so far there is no explicate theoretical analysis of the connection between nearest distance and confidence value. An analytical insight into different approximations is presented and one formula is pointed out that it is optimal in the sense of mathematical expectation. Practice in handwritten numeral recognition strongly supports the conclusion.     

ND序列下最近邻密度估计的强相合速度

在ND(negatively dependent)样本下研究最近邻密度估计的强相合速度,利用ND序列的指数不等式以及ND序列的性质,给出了最近邻密度估计强相合速度的充分条件。