本文主要研究K最近邻(K-Nearest Neighbor,KNN)算法及其应用。KNN算法是一种经典的分类算法,该算法需要计算待测样本与每个训练集样本的相似性,相似性通常用欧氏距离表示,然而在大数据的背景下,KNN算法将会产生巨大的计算量,使得算法的效率大打折扣,而且KNN算法中,k值的选取对分类结果也有一定的影响,一般需要做多次实验确定,因此针对KNN算法的以上缺陷,本文做了以下一些主要工作。第一,通过改进的局部线性嵌入算法(Locally Linear Embedding, LLE)对高维数据降维,再结合模糊C均值(Fuzzyc-means,FCM)算法对训练集聚类,从距离待测样本最近的几个聚类包含的数据中,通过计算找到k最近邻,这样就不需要计算训练集的所有样本与待测样本的距离,只计算一小部分即可,然后设计了一种基于距离为k最近邻赋予权值的方法,削弱k值的选取对分类结果的影响。第三章将KNN算法与数据降维、FCM算法、基于距离加权相结合,提出了基于训练集聚类的距离加权KNN算法,通过对模拟数据和UCI数据集进行实验,将新算法与KNN算法进行对比,验证了新算法的有效性。第二,数据的分布通常是不均匀的,对于存在类偏斜的训练集数据,第四章提出了基于训练集聚类的密度加权KNN算法,通过改进的LLE算法对训练集降维,运用K-means算法对训练集进行聚类操作,在找到待测样本的k最近邻之后,用设计的一种基于密度赋予k最近邻权重的方法进行加权操作,根据权重的大小判断待测样本的类别,通过对模拟数据和UCI数据集进行实验,将新算法与KNN算法、基于训练集聚类的距离加权KNN算法进行对比,验证了新算法对于分布不均匀的数据有着更高的分类准确率。第三,将上述两种改进的KNN算法应用于入侵检测数据集KDD Cup 1999 Data,通过与KNN算法对比,验证了改进算法的准确率更高。除此之外,对两种改进的KNN算法进行对比分析,基于训练集聚类的密度加权KNN算法在处理分布不均匀的数据时有着更好的效果。最后,总结了论文中所做的工作,提出可以进一步研究的内容。