三维散乱数据的k个最近邻域快速搜索算法

提出一种新的快速搜索算法．首先,采用空间分块策略,把数据空间分成许多大小相同的立方体子空间,立方体的大小决定了最近点的搜索速度;然后,综合考虑了数据集的范围、点的总数及最近点数目k,给出了一种新的估算立方体边长的方法．大量真实数据的实验结果表明：文中算法可以快速地给出接近于最佳搜索速度的立方体边长．     

大规模散乱点的k邻域快速搜索算法

针对大规模散乱点数据k最近邻域搜索速度慢和稳定性差的问题,提出一种新的k邻域快速搜索算法.首先,引入空间分块策略将数据集中的点归入不同的子空间;其次,动态控制搜索步长的改变量,根据点到其自身小立方体边界的最小距离保证搜索结果的准确性;最后,通过改变预筛选点数量的右侧控制阈值来消除已有算法中由于初始数值不当引起的死循环.实验结果表明该算法对初始搜索步长、搜索步长增量、采样密度和不同的拓扑结构具有较强的稳定性,并且能更快地完成k邻域搜索.     

基于P2P的自适应分布式k最近邻搜索算法

k最近邻搜索算法无法满足数据挖掘的分布性、实时性和可扩展性要求,针对该问题提出基于P2P的自适应分布式k最近邻搜索算法[0]（P2PAKNNs）。闸述GHT＊结构,定义高维数据相似度函数HDSF（X,Y）,论述GHT。中的插入算法、范围查找算法和搜索算法。给出P2PAKNNs的实现过程,通过实验证明典正确性。     

基于八叉树空间分割的k近邻搜索算法

以三维扫描得到的散乱点云为基础,提出了一种基于空间八叉树的快速k近邻搜索算法,通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在的包围盒及其周围的包围盒,并通过剪枝策略使搜索范围进一步缩小。大量真实数据的实验结果表明：该算法可以很好地提高近邻点的搜索速度。     

海量空间数据点k近邻的快速搜索算法

提出一种新的海量空间数据点k近邻的快速搜索算法.本算法综合考虑了空间数据的范围、数据点的总数、近邻点数目k以及数据点的密度,给出了一种新的估算子立方体边长的方法;采用空间分块策略,把数据空间划分成多个子立方体,子立方体的大小决定k近邻的搜索速度;最后记录每个子立方体所包含的数据点及每个点所属的子立方体编号,搜索测点的k近邻.大量数据的实验结果表明本算法可以大大提高在海量空间数据点中搜索测点k近邻的速度.     

求k邻域的体素栅格算法研究

给定一个度量空间中的一组数据点集,k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本。目前主要有2种方法,一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格（CG（Cell Grid）方法,另一种方法是基于树索引结构的方法如kd-Tree等。论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法：排序体素栅格（SCG）方法和投影体素栅格（PCG）方法。CG、SCG、PCG算法采用了改进的搜索方法,避免了传统CG算法[2-4]可能得到错误k邻域的问题。对三种算法的时空性能进行了分析比较,给出了相应的实验比较数据。     

基于动态网格k邻域搜索的激光点云精简算法

由非接触式扫描方法获得的点云数据存在大量的冗余点,为便于模型重构, 提出一种新的基于动态网格k邻域搜索的点云精简方法.首先,对点云进行k邻域搜索,在k邻域搜索过程中采用动态网格的方法快速寻找k邻域点;然后,根据数据点的k邻域计算点的曲率、点与邻域点法向夹角的平均值、点与邻域点的平均距离,并利用这3个参数定义特征判别参数和特征阈值,比较大小,对特征点进行提取;最后,利用包围盒法对非特征点进行二次精简,将精简后的点云与特征点拼接,实现精简目的.实验结果表明,所提出方法与其他k邻域搜索方法相比,提高了计算效率,并且将特征提取与二次精简方法相结合,既可保留模型的几何特征,又能避免空洞区域的产生,在精度和速度上都取得了较好的效果.     

基于散乱点云加权邻域采样点的简化算法

提出一种基于散乱点云的邻域采样点数目加权的聚类简化算法,此算法以曲面变化度和聚类中采样点的数目加权共同进行阈值控制,能够在简化过程中更偏向于将包含采样点数比较多且有一定曲率的聚类进行划分,得到更合理的简化效果。     

基于特征空间k最近邻的批次过程监视

针对具有非高斯、非线性及多工况特性的批次过程,提出一种基于特征量最近邻统计指标的过程监视方法. 首先,将批次过程正常工况原始数据投影到其特征空间,提取主元T和平方预测误差SPE,并进行特征量k最近邻距离平方和的求解. 然后,采用核密度估计法获得概率密度分布函数,确定统计监视控制限. 特征空间的主元T和SPE特征量能全面代表原始数据的有用信息. 采用特征量k最近邻建立监视模型将会节省存储空间,提高建模样本数量与变量之比以及检测异常工况的速度. 另外,利用局部近邻数据建模可以解决过程具有的非线性和多工况问题,而应用核密度估计法可以解决过程数据具有的非高斯分布问题. 最后,在半导体生产过程的成功应用表明了所提方法的有效性.     

k-近邻模糊粗糙集的快速约简算法研究

目前有很多粗糙集的推广模型通过引入参数的方法处理含有噪音的实际问题。基于粗糙集推广模型的约简算法可以发现保持信息含量不变的最小属性子集,但是其明显的不足是计算不同参数上的约简时,每次都要从头开始执行。将嵌套结构的理论结果应用于k-近邻模糊粗糙集的快速约简算法设计中,并利用嵌套结构,设计了一个基于已有约简的快速约简算法。该算法的特点是在参数改变时,不必重新运行经典的算法,而是利用已有的约简来计算新的约简。数值实验验证了快速约简算法可以显著地节省运行时间,表明了该算法的可行性和有效性。     

Geohash编码抗k近邻攻击的脆弱性分析

Geohash编码作为一种降维技术目前已应用于空间数据库和空间数据引擎中,但其安全性还有待进一步研究。文章关注Geohash编码存在的安全漏洞,从理论上分析了此种降维技术产生推理通道的原因,并提出一种基于k近邻查询的加密Geohash字段重构算法,通过观察大量k近邻查询响应中的明文信息进行统计推断并重构出加密Geohash的原始值。对加密兴趣点数据库进行重构实验,实验表明,观察到的查询响应数量越多,重构值的精确度越高。在Geohash编码精度为30 bit的情况下,当观察到100000到3000000次查询响应时,重构值与原始值平均误差为0.074%到0.015%。该实验揭示了Geohash编码在抵抗k近邻查询推理攻击方面的脆弱性及形成机理,将促进相关地理信息系统行业的安全应用与研究。     

一种基于自然最近邻的离群检测算法

任何涉及k近邻求解问题的算法被应用于处理不同特征的数据集时,参数k值的选择都会明显影响算法的性能和结果。因而,如何选择k近邻算法中敏感参数k值一直是一个研究难点。提出了一种新的近邻关系———自然最近邻,它不需要设置参数k,每个节点的邻居是由算法自适应计算而形成的。针对离群点检测的特殊性,通过确定自然最近邻居搜索算法的终止条件,提出一种基于自然最近邻的新的离群检测算法ODb3N。实验表明,该算法不仅避免了k近邻中参数的选择问题,而且能够更有效地发现离群簇。     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

球面上的K最近邻查询算法

针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法).对2种算法进行实验比较,结果表明,PAM方法和PCM方法都适合处理球面上的最近邻查询问题,PAM方法在存储量和查询复杂度方面相对于PCM方法具...     

空间数据库平面线段快速最近邻查询算法

给出了线段按其MBR进行排序的定义.以提高线段数据库最近邻查询效率为目标,以此为基础提出了一种线段数据的索引结构——SI-树,规定SI-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行最近邻查询时可以进行快速定位.给出了新的最近邻查询剪枝规则.利用这些规则在进行相应的查询时减少了许多不必要的计算,对节点有效地进行筛选和过滤,加快了查询的速度.实验表明：给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高.     

基于路由机制的时变路网k近邻算法

针对现实生活中动态路网的地理信息查询问题,提出了一种基于路由机制的动态路网中k近邻查询的算法。其主导思想是利用空间换时间,用路由表保存历史查询结果,用查询路由表的方法代替传统的最短路径计算,通过历史数据减少系统重复计算并对车辆行驶路径进行规划,用更新路由表的方法适应路况的变化。围绕路由表这一核心,改进相应的k近邻算法的过滤、精炼过程。通过路由表对动态路网进行少量的预处理,减少系统在k近邻搜索中的候选点数量,缩小查询范围,提高搜索效率。     

基于k-最近邻图的小样本KNN分类算法

提出一种基于k-最近邻图的小样本KNN分类算法。通过划分k-最近邻图,形成多个相似度较高的簇,根据簇内已有标记的数据对象来标识同簇中未标记的数据对象,同时剔除原样本集中的噪声数据,从而扩展样本集,利用该新样本集对类标号未知数据对象进行类别标识。采用标准数据集进行测试,结果表明该算法在小样本情况下能够提高KNN的分类精度,减小最近邻阈值k对分类效果的影响。     

基于自适应空间刨分的网格简化算法

提出了一种基于自适应空间刨分的网格简化算法，算法首先对模型中的所有的顶点进行量化赋予一个二次误差阵，并将它们视为一个簇，然后沿坐标轴方向将它们刨分成八个子簇并不断迭代刨分生成新的子簇直至达到指定的精度，将最终的离散点集用适当的方法重新进行三角化，得到简化模型，该算法不仅速度快，能在任意限定的时间内产生一个可显示的结果，而且结果质量也很好.另外，本文还用给出的实例与其他相关算法进行了比较．