K-近邻算法(KNN)

算法简介

K-近邻算法（KNN）是通过测量不同特征值之间的距离进行分类。
该算法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

算法原理

在训练集数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
1）计算从测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取截距最小的K个点，其中K一般不大于20且为奇数；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
在KNN中，通过计算对象间距来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，通常采用欧式距离，欧式距离也称为欧几里得距离；

还有其他距离衡量亦可以，比如：余弦值距离（cos）, 相关度（correlation）, 曼哈顿距离 （Manhattan distance）。

假设我们现在有两种不同形状的点分别为黑色矩形和蓝色圆行，分布在二维空间中，这就对应了训练样点包含的两个类别，且特征数量为3。如果我们希望推测图中红色五角星那个点是属于哪个类别，那么KNN算法将会计算该待推测点与所有训练样点之间的距离，并且挑出距离最小的K个样点（此处分别设K=1、K=5），则图中圈起来的点将被视为待推测点类别的参考依据。当K=1时，圈起来的点除了待测点之外就只有矩形，故预测该点为黑色矩形类别的；当K=5时，圈起来的点中有4个是圆行，1个是矩形，针对这种情况，KNN通常采用投票法来进行推测，即找出K个样本中类别出现次数最多的那个类别，因此该待推测点的类型值即被推测为蓝色圆形类别。


K的取值对算法的结果有影响，K太小，分类结果容易受到噪点的影响，误差会增大；K太大，近邻中可能包含太多其他类别的点（对距离加权，可以降低K值设定的影响）；K=N（样本数），则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。
一般采用8:2或者6:4对训练集切分，通过交叉与验证得出最佳K值。

程序：

# KNN算法
def knn(x_test, x_data, y_data, k):
    '''
    x_test:测试数据
    x_data:已知数据
    y_data:已知数据的标签
    K：选择K个最近的实例
    返回k个中标签最多的类别
    '''
    # 计算样本数量
    x_data_size = x_data.shape[0]
    # 复制x_test
    np.tile(x_test, (x_data_size,1))
    # 计算x_test与每一个样本的差值
    diffMat = np.tile(x_test, (x_data_size,1)) - x_data
    # 计算差值的平方
    sqDiffMat = diffMat**2
    # 求和
    sqDistances = sqDiffMat.sum(axis=1)
    # 开方
    distances = sqDistances**0.5
    # 从小到大排序
    sortedDistances = distances.argsort()
    classCount = {}
    for i in range(k):
        # 获取标签
        votelabel = y_data[sortedDistances[i]]
        # 统计标签数量
        classCount[votelabel] = classCount.get(votelabel,0) + 1
    # 根据operator.itemgetter(1)-第1个值对classCount排序，然后再取倒序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True)
    # 获取数量最多的标签
    return sortedClassCount[0][0]