高维数据中KNN分类算法的优化研究

发布时间：2021-01-09 05:13

　　近年来,数据挖掘逐渐成为各类研究者争相研究的热门课题。其中KNN分类算法由于其简单、易于实现等特性已经被广泛应用于金融分析等各个领域。但是传统KNN算法需要当前待分类样本点与所有训练样本点做相似度计算,才能得出前K个最近邻点,从而得到待测点的类别。然而当数据量增大或数据维度较大时,算法将产生巨大的计算开销。另外,如果K值选择过大,最近邻点中可能会包含相似度较低的样本点,从而导致分类准确率降低及计算量增加等问题;如果K值选择过小,尚未分类样本点可能会缺失一些相似度较高的样本点,同样也会导致准确率较低的问题。针对上述问题,本文在训练点数量的削减及K值选择上做了以下研究:针对KNN算法中存在冗余计算的问题,本文提出了基于聚类的环形KNN算法（Clustering-based Annular K-Nearest Neighbor Algorithm,AKNN）。该算法主要由数据处理、更新训练点与簇心之间的距离、构建环形过滤器及KNN分类四个部分构成。在数据处理过程中,算法可以根据训练集的实际情况选择不同的聚类算法进行聚类,从而得到合适的簇心点。其中算法的核心是为每个测试点构建一个环形过滤器,进... 

【文章来源】：广东工业大学广东省

【文章页数】：70 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 主要研究内容和贡献点
    1.4 论文结构
第二章 预备知识
    2.1 聚类算法
    2.2 K-Means++算法
    2.3 KNN分类算法
    2.4 算法性能的评价准则
        2.4.1 分类准确率
        2.4.2 分类耗时
        2.4.3 均方根误差
    2.5 符号定义
    2.6 本章总结
第三章 基于聚类的环形KNN算法
    3.1 K-Means算法
        3.1.1 Elkan算法
        3.1.2 基于Hamerly的改进算法
    3.2 环形过滤器
    3.3 算法形式化描述
    3.4 时间复杂度分析
    3.5 实验结果及分析
        3.5.1 不同的K值对算法性能影响
        3.5.2 比较几种优化算法之间的区别
    3.6 本章总结
第四章 基于环形过滤器的K值自适应KNN算法
    4.1 环形过滤器
2,1范数的定义">    4.2 L_2,1范数的定义
    4.3 LPP算法
    4.4 稀疏向量
        4.4.1 构建稀疏向量
        4.4.2 构建过程的优化
    4.5 算法形式化描述
    4.6 时间复杂度分析
    4.7 实验验证及分析
1和λ₂对算法性能的影响">        4.7.1 不同λ₁和λ₂对算法性能的影响
        4.7.2 比较几种优化算法之间的区别
    4.8 本章总结
总结与展望
参考文献
攻读学位期间发表的成果
致谢



本文编号：2966035