高效k近邻算法及其MPI并行化的研究

发布时间：2023-06-08 22:13

　　基本k近邻算法通过搜索数据集中相似度最高的k个样本来实现分类或者回归,其没有显式的学习过程,天然的具有简单、离线学习、适用于多分类等优点。由于该算法需要计算每个结点到其他所有结点的距离,所以也被称为全搜索算法(FSA,full search algorithm),因其获得最优k值需要O(N²)的时间复杂度,所以计算代价比较高。目前主要有两种加速的算法,一种是结合树索引的精确近邻查找算法,这种算法虽然可以通过树索引结构减少距离的计算,但在高维数据中,其时间复杂度依然接近于FSA。另一种是近似近邻查找算法,它相较于精确近邻查找算法而言,虽然在查找近邻时略有偏差,但却在时间复杂度上有明显的优势,故而被广泛研究。在近似k近邻算法中,优先搜索k-means树算法是针对高维数据搜索查找的一种高效的近似近邻查找算法,其使用k-means聚类来构建树模型。由于k-means聚类本身的时间复杂度较低,且算法采用特定策略来对树进行近邻搜索,故而算法的效率很高。然而,高维数据中可能存在的属性噪声会直接影响该算法中k-means树的构建。针对这一问题,本文在基于优先搜索k-means树的...

【文章页数】：61 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
        1.2.1 近邻查找
        1.2.2 并行计算
    1.3 论文主要工作
    1.4 论文组织结构
第2章 相关研究
    2.1 近邻查找算法
        2.1.1 精确近邻查找
        2.1.2 近似近邻查找
        2.1.3 评价指标
    2.2 Bagging
        2.2.1 算法原理
        2.2.2 算法描述
    2.3 MPI并行化
        2.3.1 相关概念
        2.3.2 MPI并行设计方法
        2.3.3 并行性能评价指标
    2.4 本章小结
第3章 高效近邻分类算法
    3.1 k-means森林分类算法
        3.1.1 概述
        3.1.2 算法描述
        3.1.3 算法时间复杂度分析
    3.2 基于MPI的并行k-means森林
        3.2.1 并行性分析
        3.2.2 并行结构
    3.3 粒球近邻分类算法
        3.3.1 概述
        3.3.2 相关定义
        3.3.3 算法描述
        3.3.4 算法时间复杂度分析
    3.4 本章小结
第4章 实验结果与分析
    4.1 实验环境
    4.2 实验数据集
    4.3 串行实验
        4.3.1 k-means森林实验
        4.3.2 粒球近邻实验
    4.4 并行实验
    4.5 本章小结
第5章 总结与展望
参考文献
致谢
攻读硕士学位期间从事的科研工作及取得的成果



本文编号：3832598