K邻近算法 (KNN) 原理及 python 实现代码

K邻近算法思想 ：

在对于一个分类的问题而言，我们一般希望在已知样本点中找到一个和要预测的点完全相同的点，然后进行预测，但是由于我们的样本空间有限，所以不可能找到所有的要出现的点的全部集合。但是有一种直观的感受（据说是存在数学原理的）就是说一类相似事物，他们的特征非常接近，这说明什么呢 ？ 说明 如果我们找不到与预测样本完全相同的特征点，但是我们可以找到离这个样本点最近的k个点，然后根据这k个点中所包含的类别，类别最多的类，作为要分类的时候得到的类别就可以了。

算法的性能 ：

优点 ：精度高，对于异常值不敏感

缺点 ：算法的时间复杂度和空间复杂度较高

使用的数据 ：数值型数据和标称型数据

数值型数据是指 ：取值范围是无限的比如房子的价格，可以取任意值

标称型数据是指 ：取值范围有限，比如某种东西最多可以分成几类

算法的核心 ——-确定K

确定K的方法一般是通过交叉验证法，获得最小误差的k当做我们要使用的k就好了。注意防止好欠拟合和过拟合。最好是可以把折线图画出来，找到肘点的位置 （图的直观性比较好）

算法的实现 ：

import numpy as np
import operator
import matplotlib.pyplot as plt

#自己创建数据集
def createData () :
    group = np.array ([[, ], [, ], [, ], [, ]])
    # 是 numpy 数组 而不是 np 矩阵
    labels = ['A', 'A', 'B', 'B']
    return group, labels


# 使用 k 邻近算法构造分类器
# 各参数的意义 ： inX是待分类向量 , DATAset 是训练集 ，labels 是训练集的标签 ,k 是我们要选择的 k
# 返回所属于类的标签
def classify0 (inX, dataset, labels, k) :
    datasetsize = dataset.shape[] #返回数组的行数  shape 返回型号 shape[0] 返回行数 shape[1] 返回列数
    diffmat = np.tile (inX, (datasetsize, )) - dataset
    # tile 函数 把第一个 np 数组 复制 （i,j） 其中 i 代表行复制 i 次 j 表示 j 复制 j 次 先复制行再复列
    distmat = diffmat **  #计算距离 
    sqdist = distmat.sum (axis = ) # 得到一个向量 每一个向量代表这一行的和
    distance = sqdist ** 
    sorted_distancess = distance.argsort () # 从小到大排序 得到索引值
    class_count = {} 
    for i in range (k) :
        votelabel = labels[sorted_distancess[i]]
        if votelabel not in class_count.keys() :
            class_count.setdefault (votelabel,)
        class_count[votelabel] += 

    mx = 
    res = -
    for index in class_count.keys () :
        if class_count[index] > mx :
            mx = class_count[index]
            res = index
    return res


group,labels = createData ()
print (classify0 ([,], group, labels, ))