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

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

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

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

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

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

基于[k]-近邻与局部相似度的稀疏子空间聚类

为了获得结构更加合理的仿射矩阵,提出了一种基于[k]-近邻与局部相似度的稀疏子空间聚类算法。该算法首先计算每个点的[k]-近邻,并对其用[k]-近邻数据点进行线性表示,使仿射矩阵在整体稀疏的情况下保证局部的强线性关系。基于图论知识,利用数据的实际分布情况对仿射矩阵进行约束,使仿射矩阵进一步合理地等价于待进行谱聚类的相似矩阵。在人造数据集、随机生成的子空间数据集、图像数据集以及真实数据集上进行了实验,结果表明该算法是有效的。     

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

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

海量散乱点的曲面重建算法研究

基于海量散乱点的曲面重建在机械产品测量造型、计算机视觉、根据切片数据的医学图像重建等领域中有重要应用.给出了一种以物体表面上不附加任何几何和拓扑信息(包括测点法矢、曲面边界信息)的散乱点集为处理对象,自动生成物体表面的三角网格模型的算法.该算法首先根据测点的邻近测点估算曲面在该测点处的法矢,并采用优化的顺序对法矢方向进行调整以使各测点处的法矢都指向曲面外侧,最后用步进立方体算法输出三角网格模型.采用新的方法计算切平面,不但进一步提高了效率,而且改善了曲面边界及尖锐棱边区域的重建效果.还提出并解决了法矢方向传播中可能出现的局部“孤岛”问题.同时,提出了一种对海量数据进行空间划分的算法,从而大大提高了海量数据的处理效率.应用实例表明,算法效果良好     

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

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

散乱点云曲面边界的二次提取算法

针对点云曲面边界提取算法计算量大、时间耗费多的问题,提出一种点云曲面的二次边界提取算法。采用空间包围盒法将点云曲面均匀地分为若干个小立方体,将每个点都放入一个立方体内,并通过每个立方体周围非空子立方体的个数以及分布情况提取边界子立方体。结合点云曲面数据点的分布特征,在边界子立方体内将目标点的所有K近邻点投影到以目标点为中心的平面上,计算投影点与中心点形成的向量与某条坐标轴的夹角,通过判断其是否满足预先设定的条件来判定目标点是否为边界点。实验结果表明,该方法可有效减少计算量,提高提取精度。     

一种增量迭代方式下的特征向量聚类方法

采用一种数据组织方式,提出一种特征向量聚类方法。首先选取特征空间中一些容易聚类的高密度数据点作为初始种子集合,并对其进行聚类。然后从剩下的数据点中选取种子集合的所有k近邻数据点,通过半监督判别式分析方法将当前种子集合及其k近邻数据投影到一个新的投影空间中,在该空间中对这些数据点再进行聚类,得到新的聚类结果,并将这些k近邻数据添加到当前种子集合中。通过迭代上述步骤,当种子集合的k近邻数据为空集时,算法结束。实验表明,该聚类方法优于经典的K-means、均值漂移、谱聚类等算法。     

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

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

简化的粒子群优化快速KNN分类算法

提出了一种有效的k近邻分类文本分类算法,即SPSOKNN算法,该算法利用粒子群优化方法的随机搜索能力在训练集中随机搜索.在搜索k近邻的过程中,粒子群跳跃式移动,掠过大量不可能成为k近邻的文档向量,并且去除了粒子群进化过程中粒子速度的影响,从而可以更快速地找到测试样本的k个近邻.通过验证算法的有效性表明,在查找k近邻相同时,SPOSKNN算法的分类精度高于基本KNN算法。     

基于曲率特征的点云快速简化算法

为了提高实体反求的效率,提出一种点云快速简化算法.该算法依据特征点群曲率变化的特点在点云邻域拟合曲面上搜寻特征点并进行储存,依据搜寻结果对点云进行特征点分布评估,并根据评估结果设定相应的简化距离对点云进行简化.算法充分保留了特征区域点云,使得简化后的点云能够较好地表达形状,整个搜寻过程只针对高斯曲率极值点的附近点,相对于需要在全局上进行曲率计算的传统简化算法,该算法在运行速度上具有明显优势.     

基于覆盖树的可扩展邻近搜索方法

针对邻近搜索技术受限于网络协议的支持以及存在空间嵌入误差的问题,提出一种基于覆盖树的可扩展邻近搜索方法CPS,包括覆盖树构建与维护协议和k近邻搜索算法两部分。节点自主计算自身所处层次,构造一棵层次化树。邻居维护协议负责维护覆盖树结构,确保其适应动态的网络环境。k近邻搜索算法通过对覆盖树剪枝,构造各层候选节点集合,提高搜索效率。实验结果表明,CPS的搜索精度优于典型的邻近搜索方法Tiers。     

基于相互邻近度的密度峰值聚类算法

密度峰值聚类算法对密集程度不一数据的聚类效果不佳,样本分配过程易产生连带错误.为此,提出一种基于相互邻近度的密度峰值聚类算法.所提算法引入k近邻思想计算局部密度,以此保证密度的相对性.定义综合数据全局和局部特征的样本相互邻近度的度量准则,据此准则,提出一种新的样本分配策略.新的分配策略采用k近邻思想寻找密度峰值,将密度峰值的k个近邻点分配给其对应类簇,对所有已分配数据点寻找相互邻近度最高的未分配数据点,将未分配数据点分配给已分配数据点所在类簇.在合成和UCI数据集上,将所提算法与DPC、DBSCAN、OPTICS、AP、K-Means及DPC的改进算法进行比较,实验结果表明,所提出的算法性能最优.     

路网中互近邻查询处理方法

提出路网中的互近邻查询问题.给定路网G(V,E),对象集P,查询点q,近邻数k1和k2,互近邻查询返回既是q的k1近邻,又是q的反k2近邻的对象集.为解决该问题,首先提出基础算法,即先求出查询点q的k1近邻作为候选,再验证这些候选是否为真正的结果.然后,在此基础上提出了优化算法,根据落在对象点与查询点最短路径边上的标记点个数直接排除掉一些错误的候选对象.最后,通过实验验证了优化算法的有效性.     

K-nearest neighbor finding using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These algorithms are generally applicable to any index based on hierarchical clustering. The idea is that the data is partitioned into clusters which are aggregated to form other clusters, with the total aggregation being represented as a tree. These algorithms have traditionally used a lower bound corresponding to the minimum distance at which a nearest neighbor can be found (termed MinDist) to prune the search process by avoiding the processing of some of the clusters as well as individual objects when they can be shown to be farther from the query object q than all of the current k nearest neighbors of q. An alternative pruning technique that uses an upper bound corresponding to the maximum possible distance at which a nearest neighbor is guaranteed to be found (termed MaxNearestDist) is described. The MaxNearestDist upper bound is adapted to enable its use for finding the k nearest neighbors instead of just the nearest neighbor (i.e., k=1) as in its previous uses. Both the depth-first and best-first k-nearest neighbor algorithms are modified to use MaxNearestDist, which is shown to enhance both algorithms by overcoming their shortcomings. In particular, for the depth-first algorithm, the number of clusters in the search hierarchy that must be examined is not increased thereby potentially lowering its execution time, while for the best-first algorithm, the number of clusters in the search hierarchy that must be retained in the priority queue used to control the ordering of processing of the clusters is also not increased, thereby potentially lowering its storage requirements.     

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

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

基于共享k-近邻与共享逆近邻的密度峰聚类

为了更好地解决密度不均衡问题与刻画高维数据相似性度量问题，提出一种基于共享[k]-近邻与共享逆近邻的密度峰聚类算法。该算法计算两个点的共享[k]-近邻数与共享逆近邻数，并结合欧氏距离来确定这两个点之间的共享相似度；将样本点与其逆近邻点的共享相似度之和定义为该点的共享密度，再通过共享密度选取聚类中心。通过实验证明，该算法在人工数据集和真实数据集上的聚类结果较其他密度聚类算法更加准确，并且能更好地处理密度不均衡问题，同时也提高了高维数据的聚类精度。     

Range nearest-neighbor query

A range nearest-neighbor (RNN) query retrieves the nearest neighbor (NN) for every point in a range. It is a natural generalization of point and continuous nearest-neighbor queries and has many applications. In this paper, we consider the ranges as (hyper)rectangles and propose efficient in-memory processing and secondary memory pruning techniques for RNN queries in both 2D and high-dimensional spaces. These techniques are generalized for kRNN queries, which return the k nearest neighbors for every point in the range. In addition, we devise an auxiliary solution-based index EXO-tree to speed up any type of NN query. EXO-tree is orthogonal to any existing NN processing algorithm and, thus, can be transparently integrated. An extensive empirical study was conducted to evaluate the CPU and I/O performance of these techniques, and the study showed that they are efficient and robust under various data sets, query ranges, numbers of nearest neighbors, dimensions, and cache sizes.