KNN算法是一种非常经典的划分类别的算法,主要解决未知属性样本分类问题,算法在分类过程中,需要计算未知属性样本与每个已知属性样本的距离,因此在海量高维数据的应用中,传统KNN算法计算复杂度较高的缺点受到严重挑战,针对该缺点本文进行了研究。基于距离的离群数据检测算法是常用的离群数据检测算法之一,但该算法在海量高维数据面前计算复杂度较高,针对这个缺点本文也进行了研究。论文主要工作如下:第一,针对传统KNN算法在海量高维数据面前分类效率较低,提出低时间复杂度的快速KNN算法。该算法与传统KNN算法不同之处在于:首先,从未知属性样本集中任意选择一部分样本进行分类,然后,从剩余未知属性样本中任选一个样本,计算其与所有已分类样本的距离,最后,以距离其最近的已分类样本为圆心,以两者距离的两倍再加上最近已分类样本k近邻中距离最远样本的距离为半径,作超球体。超球体外的样本则无需与该待分类样本计算距离,从而减少计算量,达到降低计算复杂度的效果。实验结果显示,提出的算法分类效率更高。第二,将基于类重心的KNN算法与低时间复杂度的快速KNN算法相结合,得到基于类重心的快速KNN算法,该算法步骤与低时间复杂度的快速KNN算法基本一致,不同之处在于算法的k值全部取1,并用均值作为各个类的类重心,则待分类样本只需与类重心计算距离,其余步骤与低时间复杂度的快速KNN算法一致。实验结果显示,基于类重心的快速KNN算法的效率比传统基于类重心的KNN算法效率更高。第三,将传统基于距离的离群数据检测算法进行改进,提出基于距离的快速离群数据检测算法。传统算法需要计算待测样本与所有样本的距离,而提出的算法从第二个待测样本开始(第一个任意选择的样本,与传统算法计算方法一致),无需与其他所有样本计算距离,只需与以第一个已测样本为圆心,以待测样本与圆心的距离加上事先给定的邻域半径为半径的超球体内的样本计算距离。当待测样本与圆心的距离大于给定的邻域半径时,此时建立空心超球体,空心部分的半径是待测样本与圆心的距离减去给定的邻域半径,超球体外和空心部分的样本则无需与待测样本计算距离,从而达到降低算法计算复杂度的效果。实验结果显示提出的算法的检测效率比传统算法的检测效率更高。第四,利用低时间复杂度的快速KNN算法思想,提出一种低时间复杂度的快速KNN离群数据检测算法,该算法与传统基于距离的离群数据检测算法不同之处在于:传统算法是让检测样本的邻域半径都为d的情况下,用检测样本的邻居数量与给定的邻域参数ε进行比较,而提出的算法则是让检测样本邻居数量都为ε的情况下,用事先给定的邻域半径d与检测样本邻域内最远样本的距离进行比较,实验结果显示,提出的算法的检测效率比传统算法的检测效率更高。最后,总结了论文的研究内容,并提出研究领域的不足之处,以及可继续研究的方向。