k近邻空间插值算法优化研究

在k近邻空间插值中,如果能减少近邻点的搜索次数,可进一步提高空间插值的性能。引入k近邻距离阈值的概念和计算方法,并以该阈值为基础,发展了k+M优化算法。其算法核心是在空间插值过程中,获取初始栅格的k+M近邻点集,计算k+M近邻距离阈值。若从初始栅格向右移动至其他栅格的距离小于该阈值,则直接利用初始栅格的近邻点集进行空间插值。实验证明,该算法相对于每个栅格均搜索近邻点的算法,性能有明显的提升。

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

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

基于点云边界质心的粗配准方法

点云配准的质量直接影响着三维重建的质量。针对传统K-4PCS耗时长且易出现错误匹配等问题,文中提出一种基于边界质心的点云粗配准方法。通过对点云进行边界提取,既保留点云外表特征,又减少了点云数据的大小,提高了粗配准速度。为了加快边界点的提取速度,使用K-D tree算法完成对k近邻点的搜索。通过配准边界点的质心,减少点云初始距离并增加重叠度,保证了粗配准的精度。实验结果证明,文中方法在粗配准速度和精度方面都优于传统K-4PCS算法,其速度约为传统K-4PCS算法的2倍,平移和旋转精度也比传统K-4PCS高了40%以上。文中所提方法对提高点云粗配准的速度和精度具有一定的参考价值。

航空部件测量数据的三维散乱点云边界特征快速提取算法

提出一种三维散乱点云边界特征提取算法,该算法采用R^(*)-tree建立散乱点云的空间索引结构,基于该结构快速获取任意点的k近邻点集X,计算该点集的型心,依据型心及任意点构建向量v,建立经过点P且垂直于v的基准平面L,若点集X中各点均位于平面L的同侧,则点P为边界点,否则为非边界点。实例表明该算法运行速度快,且在快速准确提取点云边框特征点外,可同时提取孔洞处的边界特征点。

一种求解旅行商问题的高效混合遗传算法

旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。

粗略不相似度量及其在层次聚类中的应用

局部结构特征在数据分析过程中具有重要的作用.为获得简单有效的数据集局部结构化特征检测方法,本文结合重采样误差分析和传统的近邻选择方法提出了一种检测局部结构特征的方向一致性度量—粗略不相似性度量.该度量是一种优化的近邻选择方法,不仅考虑了传统的欧氏距离排序,而且考虑了局部方向结构特征.因其计算和存储复杂度小以及具有优越的结构检测性能,可应用于无监督学习形成一种层次化的子图聚类算法—RDClust,与经典聚类算法相比,其优势在于:一是计算复杂度较小,是近似线性算法;二是无需对类的形状和分布形式做任何的假设,可自动体现数据集的局部结构;三是有一个近邻参数,且该参数对结果较鲁棒.在人工和真实数据集上的实验显示了新的度量方式应用于新算法的优越性能.

LLE算法中有关参数选取问题的研究

本文针对locally linear embedding (LLE)算法中的两个参数:近邻点的个数k和降维后输出的维数d如何选取的问题,对LLE算法进行了改进。首先对降维的相关知识进行了描述,并具体介绍了对高维数据进行降维的目的。其次,讨论了LLE算法的基本思想和计算步骤。最后,针对LLE算法中存在的问题进行了分析。