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

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

点云数据的k近邻快速建立改进算法

针对点云数据最近点搜索时栅格化所得空间子块大,并且在未完全找到前搜索范围需扩展一圈的问题,提出一种基于二次栅格化和扩展方向可控的快速搜索算法。采用传统分块算法一次栅格化数据空间;综合考虑非空栅格、最近点数目及一次划分边长,计算二次栅格化的边长;在局部搜索过程中控制扩展方向,优先在最有可能出现的栅格中进行搜索。实验结果表明,与现存的方法相比,该算法在搜索时间上至少减少了20%。     

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

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

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

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

基于八叉树编码的点云数据精简方法

针对逆向工程中的点云数据预处理,分析了现有数据精简方法的不足,提出了基于八叉树编码的均匀精简方法。应用八叉树编码法划分点云邻域空间为多个指定边长的子立方体,保留每个子立方体中距中心点最近的点,实现从空间整体角度对点云的精简。对涡轮叶片测量数据进行了精简测试,证明了该算法的有效性和实用性。     

基于自适应空间球的k最近邻域快速搜索算法

利用空间球搜索大规模点云数据k邻域存在速率慢和稳定性差的问题,为此,提出一种新的k邻域快速搜索算法。利用与k无关的分块策略对点云进行分块,使用候选点所在子块内采样点的近似密度自适应确定候选点的初始动态球半径,应用动态球的外切立方体搜索k邻域候选点。当候选点数目不满足要求或搜索不成功时,采用候选点动态球外切立方体的外接球扩大搜索范围。实验结果表明,与已有算法相比,该算法的k邻域搜索效率明显提高,而且当子块内预设点数变化、采样密度提高时具有较强稳定性,自动化程度较高。     

一种基于最小搜索圆平面多边形域约束Delaunay三角剖分算法

给出一种新的基于边优先的二维多边形域任意散乱数据的约束Delaunay三角剖分算法.算法结合网格分块技术,提出基于最小搜索圆的点搜索思想,并证明了该思想的正确性,有效地提高了搜索第三点的速度.算法中散乱数据可以是任意复杂的折线、封闭多边形环及离散点.另外,在三角剖分过程中,实时地去掉封闭点和封闭边,极大地加快了构网速度,实现了平面多边形域散乱数据的快速约束Delaunay三角化.     

基于查询集空间分布的聚合最近邻查询算法

聚合最近邻查询涉及到多个查询对象,因此比传统最近邻查询更复杂,而且其查询集空间分布特征暗含了查询集聚合最近邻的区域分布信息。充分考虑查询集分布特征,给出了利用分布特征指导聚合最近邻搜索的方法,并以此提出了一种新的聚合最近邻查询算法——AM算法。AM算法能动态地捕捉并利用查询集空间分布特征,使得对数据点的搜索按正确的次序进行,避免对不必要数据点的搜索。最后通过实验验证了AM算法的高效性。     

超平面树:度量空间中相似性搜索的索引结构

相似性搜索是从数据库中检索出同给定数据对象相似的数据对象，已有的基于R-tree的相似性搜索，当搜索空间的维的个数较小时效率较高，但当搜索空间的维的个数较大时则效率很低．针对此问题，提出了新的度量空间分割方法和索引结构pgh-tree，利用数据对象与很少几个固定参考对象的距离之差进行数据分割和索引，产生一个平衡的索引树．在此基础上，提出了新的算法，利用查询数据对象与固定参考对象的距离之差过滤掉大部分的不相关数据，具有较小的I／O代价和距离计算复杂性，平均复杂性为θ(n^0.58)，是目前复杂性最小的相似性搜索算法．另外还讨论了基于pgh-tree的最近相邻点搜索策略．     

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

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

基于局部加权重构的化工过程数据恢复算法

针对化工过程数据中存在缺失数据的问题,在保持局部数据结构特征的基础上提出了基于局部加权重构的化工过程数据恢复算法。通过定位缺失的数据点并以符号NaN(Not a Number)标记,将缺失的数据集分为完备数据集和不完备数据集。不完备的数据集按照完整性的大小依次找到它们在完备数据集中相应的k个近邻,根据误差平方和最小的原则,求出k个近邻相应的权值,用k个近邻及相应的权值重构出缺失的数据点。将该算法应用在不同缺失率下的两种化工过程数据中并与望最大化主成分分析(EM-PCA)法和平均值(MA)两种传统的数据恢复算法相比较,该算法的恢复数据误差最小,并且计算速度相比EM-PCA算法平均提高了2倍。实验结果表明,局部加权重构的化工过程数据恢复算法可以有效地对数据进行恢复,提高了数据的利用率,适用于非线性化工过程缺失数据的恢复。     

基于局部密度的快速离群点检测算法

已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测,INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题,但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题。针对该问题,提出局部密度离群点检测算法--LDBO,引入强k近邻点和弱k近邻点概念,通过分析邻近数据点的离群相关性,对数据点区别对待;并提出数据点离群性预判断策略,尽可能避免不必要的反向k近邻分析,有效提高数据分布异常情况离群点检测算法的效率。理论分析和实验结果表明,LDBO算法效率优于INFLO,算法是有效可行的。     

基于局部邻域多流形度量的人脸识别

针对人脸识别中特征的提取,提出了一种基于局部邻域多流形度量的人脸识别方法。针对人脸识别的小样本问题,用特征脸对人脸图像预处理。对预处理后的人脸数据集中每个流形内的数据点采用欧氏距离来选择各数据点的近邻点,由此得到局部权重矩阵,并计算重构数据点与原始数据点之间的误差距离;同时,采用图像集建模流形,用affine hull表示流形对应的数据集信息,计算多流形间的距离度量矩阵。通过最大化流形间距离以及最小化数据点与重构数据点误差距离来寻找投影降维矩阵。在人脸数据集上的大量比较实验,验证了该方法的准确性和有效性。     

Fast k-nearest neighbors search using modified principal axis search tree

The problem of k-nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. Among available methods, the principal axis search tree (PAT) algorithm always has good performance on finding nearest k neighbors using the PAT structure and a node elimination criterion. In this paper, a novel kNN search algorithm is proposed. The proposed algorithm stores projection values for all data points in leaf nodes. If a leaf node in the PAT cannot be rejected by the node elimination criterion, data points in the leaf node are further checked using their pre-stored projection values to reject more impossible data points. Experimental results show that the proposed method can effectively reduce the number of distance calculations and computation time for the PAT algorithm, especially for the data set with a large dimension or for a search tree with large number of data points in a leaf node.     

一种基于向量夹角的k近邻多标记文本分类算法

在多标记学习中,一个示例可以有多个概念标记.学习系统的目标是通过对由多标记样本组成的训练集进行学习,以尽可能正确地预测未知样本所对应的概念标记集.k近邻算法已被应用到多标记学习中,该算法将测试示例转化为多维向量,根据其k个近邻样本的标记向量来确定该测试示例的标记向量.传统的k近邻算法是基于向量的空间距离来选取近邻,而在自然语言处理中,文本间的相似度常用文本向量的夹角来表示,所以本文将文本向量间的夹角关系作为选取k近邻的标准并结合k近邻算法提出了一种多标记文本学习算法.实验表明,该算法在文档分类的准确率上体现出较好的性能.     

Fast exact k nearest neighbors search using an orthogonal search tree

The problem of k nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. In this paper, a novel fast kNN search method using an orthogonal search tree is proposed. The proposed method creates an orthogonal search tree for a data set using an orthonormal basis evaluated from the data set. To find the kNN for a query point from the data set, projection values of the query point onto orthogonal vectors in the orthonormal basis and a node elimination inequality are applied for pruning unlikely nodes. For a node, which cannot be deleted, a point elimination inequality is further used to reject impossible data points. Experimental results show that the proposed method has good performance on finding kNN for query points and always requires less computation time than available kNN search algorithms, especially for a data set with a big number of data points or a large standard deviation.     

Shell-neighbor method and its application in missing data imputation

Data preparation is an important step in mining incomplete data. To deal with this problem, this paper introduces a new imputation approach called SN (Shell Neighbors) imputation, or simply SNI. The SNI fills in an incomplete instance (with missing values) in a given dataset by only using its left and right nearest neighbors with respect to each factor (attribute), referred them to Shell Neighbors. The left and right nearest neighbors are selected from a set of nearest neighbors of the incomplete instance. The size of the sets of the nearest neighbors is determined with the cross-validation method. And then the SNI is generalized to deal with missing data in datasets with mixed attributes, for example, continuous and categorical attributes. Some experiments are conducted for evaluating the proposed approach, and demonstrate that the generalized SNI method outperforms the kNN imputation method at imputation accuracy and classification accuracy.     

适用于小样本的双邻接图判别分析算法

作为一种常用的降维方法,适用于小样本的监督化拉普拉斯判别分析方法通过使用图嵌入的判别近邻分析得到了很好的降维效果。但该方法在构建近邻图时,在K近邻中寻找同类和异类样本点存在数据不平衡问题;此外,在优化该方法的目标函数时,没有全面考虑到类间信息,从而会在一定程度上降低该方法的性能。针对以上两个问题,本文提出了适用于小样本的双邻接图判别分析方法。首先该方法分别在同类和异类样本中找出K个近邻点,然后使用这K个类内近邻点和K个类间近邻点来构造双邻接图,这样可以确保邻接图中既有同类样本点也有异类样本点,且数目相同。然后该方法在目标函数的推导结果中加入了类间拉普拉斯散度矩阵,从而使优化得到的投影矩阵融入更多的类间信息。在Yale和ORL人脸数据集上进行实验,并与同类方法相比,结果表明本文提出的适用于小样本的双邻接图判别分析方法能够得到更好的降维效果。     

利用区域划分的多密度快速聚类算法

针对基于网格的聚类算法存在簇边缘网格中包含噪声点、利用网格相对密度差进行网格合并时不能区分密度均匀变化的网格等问题。提出一种利用区域划分的多密度快速聚类算法MFCBR。算法把数据空间划分成密度不同的网格,利用网格索引表和网格中心密度差合并网格形成簇,然后分别计算每个簇的边界网格质心、边界网格和最近簇网格中心位置,利用三者之间的关系来排除簇边界网格数据中包含的噪声点。实验表明,该算法在降低噪声数据对聚类干扰的同时,且对密度均匀变化的多密度数据集也有较优的处理效果。