K-NN 近邻

作者: Bool吖 | 来源:发表于2019-06-29 23:43 被阅读0次

k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

k近邻算法

输入：训练数据集

$T={(x_1,y_1), (x_2, y_2),...,(x_n,y_n)}$

其中， $x_i\in\chi\subset R^n$ 为实例的特征向量， $y_i\in\gamma= (c_1,c_2,...c_k)$ 为实例的类别， $1, 2,...,N$ ;实例特征向量 $x$ ;
输出：实例 $x$ 所属的类 $y$ .

(1)根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的邻域记作 $N_k(x)$ ;

(2)在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$ :

$y=argmax_{c_j}\sum\limits_{x_i\in{N_k(x)}}I(y_i=c_j), i=1,2,...,N;j=1,2,...,K$

在上式中， $I$ 为指示函数，即当 $y_i=c_j$ 时， $I$ 为1，否则 $I$ 为0.

k近邻模型由三个基本要素组成：距离度量，k值选择，分类决策规则

距离度量

距离选择有很多种，常用的距离函数有：

1、明考斯基距离

2、曼哈顿距离

3、Cityblock 距离

4、欧几里德距离(欧氏距离)

5、Canberra 距离

...

目前使用最多的距离计算公式为欧式距离，也是常用的向量距离计算方法。

欧式距离

计算两个物体直接的距离/相似度

K近邻模型的特征空间一般是n维实数向量空间 $R^n$ 。使用的距离是欧氏距离，但也可以是其它距离。设特征空间X是n维实数向量空间
$R^n$ ，

$x_i,x_j∈X, x_i=(x^{(1)}_i,x^{(2)}_i,...x^{(n)}_i)， x_j=(x^{(1)}_j,x^{(2)}_j,...x^{(n)}_j)$ ,

$x_i,x_j$ 的 $L_p$ 距离定义为
$L_p(x_i,x_j)=(\sum\limits_{l=0}^{n}|x^{(l)}_i−x^{(l)}_j|^p)^{1/p}$

这里 $p≥1$ 。当 $p=2$ 时称为欧氏距离，即
$L_2(x_i,x_j)=(\sum\limits_{l=1}^{n}|x^{(l)}_i−x^{(l)}_j|^2)^{1/2}$

当 $p=1$ 时，称为曼哈顿距离，即
$L_1(x_i,x_j)= \sum\limits^{n}_{l=1}|x^{(l)}_i−x^{(l)}_j|$

当 $p=∞$ 时，它是各个坐标距离的最大值.

关于k取值

k对算法影响：

k值得选择会对k近邻算法的结果产生重大影响。
如果选择的k值较小，就相当于用较小的的邻域中的训练实例进行预测。此时预测的结果会对近邻的实例点非常敏感。

如果选择较大的k值，就相当于在较大的邻域中训练实例进行预测。此时，与输入实例较远的训练实例也会对预测起作用，使预测发生错误。

在使用k-NN算法的时候,k值一般会选择偶数，如1，3，5，7，9...。选择奇数是为了防止平手。K取1容易出现过拟合。

通过交叉验证选择合适的k，通常我们把它归类为“调参”。

交叉验证

把训练数据进一步分为训练数据(Training Data)和验证集合(Validation Data)。选择在验证数据里最好的超参数组合。

例：

![截屏2019-06-2921.17.13.png](https://img.haomeiwen.com/i3637572/0801a96567f60ed4.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

K折交叉验证（K-fold Cross Validation），把训练数据分为K部分，一部分作为验证数据，另外(K-1)部分作为训练数据。

交叉验证中需要注意的点：

千万不要用测试数据来调参；
数据量越少，可以适当增加折数。

特征的缩放

线性归一化(Min-max Normalization)
标准差标准化(Z-score Normalization)

coding time

from sklearn import datasets
from collections import Counter
from sklearn.model_selection import train_test_split
import numpy as np 


def euc_dis(instance1, instance2):
    """
    计算两个样本直接的欧氏距离
    """
    dist = np.sqrt(sum((instance1 - instance2)**2))
    return dist

def knn_classify(X,y, testinstance, k):
    dists = [euc_dis(x, testinstance) for x in X]
    kneighbors = np.argsort(dists)[:k] # 排序，截取前K
    count = Counter(y[kneighbors]) # 计算数量
    return count.most_common()[0][0] # 返回出现最多的label


# 导入iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2003)

# 结果预测
predict = [knn_classify(X_train, y_train, data, 3) for data in X_test]

correct = np.count_nonzero((predict==y_test)==True) # 预测正确数量
print('Accuracy is : %.3f' % (correct/len(X_test))) # 正确率

sklearn k近邻算法

官方文档

截屏2019-06-2921.17.13.png

k-NN最大的作用是可以随时间序列计算，即样本不能一次性获取只能随着时间一个一个得到的时候，k-NN能发挥它的价值。至于其他的特点，它能做的，很多方法都能做；其他能做的它却做不了。

......

参考文献
1、李航，统计学习方法，清华大学出版社，2012