分类问题是数据挖掘领域中最基本和最重要的问题之一,在计算机视觉、自然语言处理、生物特征识别和医学诊断等领域都有着广泛的应用。最近邻算法是一种常见的分类算法：给定一个测试样本,找出与它相似的训练样本进行比较来学习。k-最近邻方法(kNN)在训练样本集中找出最接近测试样本的k个邻居,然后根据它们分类。kNN作为一种经典的分类算法,是数据挖掘领域应用最广泛的分类算法之一,广泛应用于人脸识别、手写字符识别等各个领域。但kNN也有其不足的地方,对于kNN的改进一直是学者们研究的热点,其中kNN中k值的确定是一个公开性问题,本文重点研究了kNN中k值的选取问题,主要工作如下：1)kNN使用固定k值对于所有的测试样本都使用同样数目的训练样本来进行分类、预测等,这在实际情况中是不合理的。本文将稀疏表示引进kNN算法,提出CM-kNN算法,通过重构技术尝试性解决k值固定问题,即对于不同的测试样本,应该在训练样本空间中使用不同数目的训练样本对其进行分类,这样才更加符合实际情况。2)和经典kNN算法相比,CM-kNN准确率提升了很多,不过当样本数据量很大时,重构过程耗费时间过长。为此,本文引入决策树技术,提出kTree算法,通过建立决策树来避免重构这一过程,从而大大提高分类速度,同时可以保持和CM-kNN接近的分类准确率。3)在k Tree算法基础上,将决策树叶子结点附近的k个邻近样本及其最近邻样本考虑在内,提出k*Tree算法,在这个小范围内进行kNN分类,从而获得进一步的计算速度提升,同时也能保证和CM-kNN接近的准确率。