概述：

        所谓K近邻算法（也称kNN算法），即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

案例介绍：

        如图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类，下面，我们就要解决这个问题：给这个绿色的圆分类。

 

        如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

        如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

Knn算法的优缺点：

优点：精度高，对异常值不敏感，无输入数据假定

缺点：计算复杂度高，空间复杂度高

使用数据范围：数值型和标称型。

Knn算法一般流程：

1. 收集数据：可以使用任何方法
2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式
3. 分析数据：可以使用任何方法
4. 训练算法：此步骤不适用于k-近邻算法
5. 测试算法：计算错误率
6. 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个类，最后应对计算输出的分类执行后续的处理

k-近邻算法实例：

        首先，先收集到住在不同区域宿舍（五社区或集友楼）的学生一周内使用自行车（电动车）和步行上课的次数。然后给出某学生一周内使用自行车（电动车）和步行上课的次数，根据这些次数判断该学生居住宿舍的区域（五社区或集友楼）。

训练集：

学生	车行	步行	宿舍区域
1	21	3	集友楼
2	12	10	五社区
3	8	14	五社区
4	16	4	集友楼
5	11	9	五社区
6	23	1	集友楼
7	10	11	五社区
8	17	2	集友楼
9	19	5	集友楼
10	13	9	五社区
11	12	12	五社区
12	11	3	集友楼
13	9	13	五社区
14	15	7	集友楼
15	6	1	集友楼
16	9	7	五社区
17	14	13	五社区
18	6	12	五社区
19	12	7	集友楼
20	10	13	集友楼

测试集：

学生	车行	步行	宿舍区域
1	14	7	五社区
2	18	6	集友楼
3	12	6	五社区

Python实现：

import numpy as np
import operator

    #创建训练集
def createDataSet():
    #二位特征
    group = np.array([[21,3],[12,10],[8,14],[16,4],[11,9],
                      [23,1],[10,11],[17,2],[19,5],[13,9],
                      [12,12],[11,3],[9,13],[15,7],[6,1],
                      [9,7],[14,13],[6,12],[12,7],[10,13]])
    #特征的标签
    labels=['集友楼','五社区','五社区','集友楼','五社区',
            '集友楼','五社区','集友楼','集友楼','五社区',
            '五社区','集友楼','五社区','集友楼','集友楼',
            '五社区','五社区','五社区','集友楼','集友楼']
    return group,labels

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndices = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]

if __name__ == '__main__':
    i = 0
    print("训练集:")
    group, labels = createDataSet()
    for index in group:
        print('学生%d： 车行%3d次  步行%3d次 宿舍区域:%s' %(i+1,index[0],index[1],labels[i]))
        i=i+1

    i = 0
    print("\n测试集:")
    test = np.array([[14,7],[18,6],[12,6]])
    for index1 in test:
        label = classify0(index1, group, labels,3)#测试不同k的取值对结果的影响
        print('学生%d： 车行%3d次  步行%3d次 宿舍区域:%s' %(i+1,index1[0],index1[1],label))
        i = i+1

当k取3.7.10.13.14时的输出结果：

思考与小结：

         K-近邻算法最基本也最核心的点就是k的取值大小，K的大小影响着算法得出结果的准确度。根据上述例子中不同k值得出不同结果的现象可以看出k值过大过小都会使预测结果降低，这是由于：

       当K值较小时：意味着只有与输入实例较近的训练实例才会对预测结果起作用，容易发生过拟合。

        当K 值较大时：虽然可以减少学习的估计误差，但是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

        在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优K

的取值。