在当今互联网时代,海量信息处理已成为我国经济建设进程中的一个重大需求。最近邻方法是海量信息处理中最重要的理论与技术之一,运用已知的最邻近点估计或逼近问题的解,为海量信息计算与服务提供了简单、易理解、有效的理论和技术。本论文研究最近邻方法在缺失值填充与分类中应用的新技术和算法。首先,从缺失值填充和数据分类的应用角度对k最近邻算法进行研究,详细地阐述了k最近邻算法的基本原理,分析它的优缺点和一些常用的改进方法。在此基础上,本论文以获取更高的填充(分类)准确率为主要目标,针对k最近邻算法的某些缺点提出新的改进策略,并从理论和实验两方面验证策略的有效性。一方面,本论文研究最近邻填充的新理论与算法。针对k最近邻填充算法(kNNI)在缺失数据的k个最近邻的选择上可能存在偏好,提出一种新的缺失填充算法:象限近邻填充算法QENNI(是一种壳近邻填充算法),它仅仅使用缺失数据象限方向的最近邻来填充该缺失值,避免了kNNI中选取的k个最近邻点有偏好这一情况。进一步,本论文采用三种可能的加权方法对壳近邻填充算法(SNI)[1,2]进行分析,通过实验总结出壳近邻填充中近邻数据重复选择有利于提高填充效果,而基于频率与距离加权方式的壳近邻填充算法fdwSNI具有最好的填充效果这一结论。关于缺失值填充,填充算法固然重要,但好的评价方式无疑能为算法的选择提供有效的指导。通过具体的实例分析,本论文指出常用的填充效果指标RMSE容易偏向严重的填充误差,并提出一种新的goodness评价方式。即使存在个别严重的填充误差,goodness仍然能得出理想的结论。另一方面,本论文建立一个壳近邻分类算法SNC,克服了kNN最近邻选择上可能存在偏好这一问题,该算法对距离度量不敏感,在大数据集上具有更好的分类效果。另外,在实际的数据挖掘应用中,面对的数据通常是质量差的或者不完全的,开发噪声鲁棒性较好的挖掘算法是一个具有实际应用价值的挑战性工作。噪声消除常常是困难且昻贵的,并且减少历史数据来换取信息的完备,会导致可分析的数据容量大量减少,造成资源的浪费,并丢弃了大量隐藏在这些数据中的信息。kNN是基于距离的局部最优的算法,忽略了部分或整体上的数据分布可能对分类结果的影响,会导致分类器对训练集中噪声数据的敏感性增大。本论文提出综合考虑k近邻、簇和训练集中的数据分布特性,建立一个新的分类算法,称为NCT,由于充分利用了局部、部分和全局三方面的数据资源,该算法具有良好的噪声鲁棒性。实验结果表明,NCT算法不仅具有更好的分类效果,而且在噪声环境中具有良好的鲁棒性。在不含噪声的环境中,NCT算法稍微好于kNN;而在含噪声的环境中,NCT算法的分类准确率明显高于kNN算法,且噪声率越大,这种优势越显著。最后,对NCT算法引进的聚类信息和全局信息做其他形式的组合变型,通过实验证明在含噪声的环境中,无论用哪种组合方式加入新信息都有利于提高kNN算法的分类效果,而线性插值组合方式的NCT算法提高分类准确率的幅度最大。简言之,本论文的主要创新点可以概述如下:提出一种象限近邻填充算法QENNI,克服kNNI算法缺失数据的最近邻选择可能存在偏好;提出一种新的goodness缺失值填充评价方式,当个别数据存在严重填充误差时,goodness评价方式优于RMSE;构造一种新型的壳近邻分类算法SNC,克服了kNN算法最近邻选择上可能存在偏好这一问题,该算法对距离度量不敏感,在大数据集上具有更好分类效果;提出一种综合考虑k近邻、簇和训练集中的数据分布特性的NCT分类算法,有效增强对噪声的鲁棒性。为证明其有效性,本论文提出的算法均在真实数据集上进行大量的实验。实验结果表明,本论文提出的QENNI、SNC和NCT算法均优于k最近邻算法,特别NCT算法在噪声环境中分类效果的优势显著。