k近邻算法(k-Nearest Neighbors,kNN)是一种基于统计的经典分类方法,具有算法简洁、分类准确性较高和无需先验统计知识等特点,目前已成为数据挖掘领域中广泛研究与应用的算法之一。本文在分析现有k近邻算法的基础上,主要开展对k近邻算法的改进与并行化研究。传统k近邻分类算法具有二次方时间复杂度,为了提高分类速度,一类方法通过构造树型索引结构以加快k近邻查找,但是基于树型k近邻算法随着数据集维度增加其分类性能会变差;另一类方法则通过查找近似近邻而避免精确近邻的大量计算,其中基于参考点k近邻算法对各类数据集均具有较高的分类效率,但分类精度相对于传统k近邻算法仍有较大损失,针对该问题,本文提出一种改进的参考点k近邻分类算法,其时间复杂度为O(nlogn)。本文考虑到训练样本的空间分布特征,根据到样本距离的方差改善参考点的选取,并在查找近邻样本时依据参考点所起不同作用而赋予参考点自适应权重。通过在公开与人工数据集上实验,验证了本文算法具有较高的分类效率,相比于现有参考点k近邻算法获得了更好的分类精度。为了解决单机环境下大规模数据分类存在计算性能弱、内存消耗高与扩展性差等问题,提出了基于MPI(Message Passing Interface,消息传递接口)并行编程模型的DPkNN与PkNN两种算法。前者基于数据并行的思想,将待分类数据集均衡分配给各进程来并行处理,后者把所有进程构造为流水线模型,各进程并行完成分类任务中的一部分。针对本文提出的参考点k近邻算法,还设计了通过划分训练集来并行求取参考点的方法。将这两种并行算法应用于本文参考点k近邻算法与传统kNN算法,并在超算平台上使用至多48个核心资源进行实验,和现有并行方法作对比,验证了这两种并行算法均能显著地提高分类效率,其中PkNN算法具有更好的加速比和可扩展性。最后,将k近邻算法应用于手写识别中,实现了一个集成多种算法的手写识别系统,它具有友好的交互界面,能对手写输入的数字进行有效识别。同时利用手写数据集进一步验证了本文第三章提出算法的有效性。