KNN算法以及欧式距离

1.KNN算法介绍

KNN 是什么？

KNN(K-Nearest Neighbor)是最简单的机器学习算法之一，可以用于分类和回归，是一种监督学习算法。它的思路是这样，如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。也就是说，该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN用于分类
如上图所示，图中的正方形和三角形是打好了label的数据，分别代表不同的标签，那个绿色的圆形是我们待分类的数据。
如果选K=3，那么离绿色点最近K个点中有2个三角形和1个正方形，这3个点投票，三角形的比例占2/3，于是绿色的这个待分类点属于三角形类别。
如果选K=5，那么离绿色点最近K个点中有2个三角形和3个正方形，这5个点投票，蓝色的比例占3/5，于是绿色的这个待分类点属于正方形类别。

从上述例子看到，KNN本质是基于一种数据统计的方法，其实很多机器学习算法也是基于数据统计的。同时， KNN是一种instance-based learning，属于lazy learning， 即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，就可以直接开始分类。其中，每次判断一个未知的样本点时，就在该样本点附近找K个最近的点进行投票，这就是KNN中K的意义，通常K是不大于20的奇数。

KNN分类算法的计算过程：
1）计算待分类点与已知类别的点之间的距离
2）按照距离递增次序排序
3）选取与待分类点距离最小的K个点
4）确定前K个点所在类别的出现次数
5）返回前K个点出现次数最高的类别作为待分类点的预测分类

KNN算法要注意什么问题？
参数分为：模型参数和超参数
超参数：就相当于一个开关：告诉模型启用不同的训练方式；

（1）把一个物体表示成向量/矩阵；
（2）标记号每个物体的标签；
（2）计算两个物体之间的距离/相似度；距离度量，特征空间中样本点的距离是样本点间相似程度的反映
（3）选择合适的 K
其中，K值的选择和设置距离度量是最应该注意的几个问题;

代码实现：

1. 调用KNN函数来实现分类¶

数据采用的是经典的iris数据，是三分类问题

# 读取相应的库
from sklearn import datasets   # 使用sklearn 自带的数据集；
from sklearn.model_selection import train_test_split  # 把数据分为训练 和  测试数据
from sklearn.neighbors import KNeighborsClassifier
import numpy as np

# 读取数据 X, y
iris = datasets.load_iris()   # UCI dataset；3类描述；
X = iris.data  #特征：矩阵： N*D  N：#OF
y = iris.target   #label ：标签（0，1，2），向量；
print (X, y)
-------------------------------------------------------
[[ 5.1  3.5  1.4  0.2]
 [ 4.9  3.   1.4  0.2]
 [ 4.7  3.2  1.3  0.2]
 [ 4.6  3.1  1.5  0.2]
 [ 5.   3.6  1.4  0.2]
 [ 5.4  3.9  1.7  0.4]
 [ 4.6  3.4  1.4  0.3]
 [ 5.   3.4  1.5  0.2]
 [ 4.4  2.9  1.4  0.2]
 [ 4.9  3.1  1.5  0.1]
......

# 把数据分成训练数据和测试数据
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2003)

# 构建KNN模型， K值为3、 并做训练
clf = KNeighborsClassifier(n_neighbors=3)  #指定K值
clf.fit(X_train, y_train)     #训练

# 计算准确率
from sklearn.metrics import accuracy_score
correct = np.count_nonzero((clf.predict(X_test)==y_test)==True)
#accuracy_score(y_test, clf.predict(X_test))
print ("Accuracy is: %.3f" %(correct/len(X_test)))
------------------------------------
Accuracy is: 0.921

2. 从零开始自己写一个KNN算法

from sklearn import datasets
from collections import Counter  # 为了做投票
from sklearn.model_selection import train_test_split   
import numpy as np

# 导入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)

def euc_dis(instance1, instance2):
    """
    计算两个样本instance1和instance2之间的欧式距离
    instance1: 第一个样本， array型
    instance2: 第二个样本， array型
    """
    # TODO
    dist = np.sqrt(sum((instance1 - instance2)**2))
    return dist
    
 
def knn_classify(X, y, testInstance, k):
    """
    给定一个测试数据testInstance, 通过KNN算法来预测它的标签。 
    X: 训练数据的特征
    y: 训练数据的标签
    testInstance: 测试数据，这里假定一个测试数据 array型
    k: 选择多少个neighbors? 
    """
    # TODO  返回testInstance的预测标签 = {0,1,2}
    distances = [euc_dis(x, testInstance) for x in X]
    kneighbors = np.argsort(distances)[:k]
    count = Counter(y[kneighbors])
    return count.most_common()[0][0]

# 预测结果；
predictions = [knn_classify(X_train, y_train, data, 3) for data in X_test]
correct = np.count_nonzero((predictions==y_test)==True)
#accuracy_score(y_test, clf.predict(X_test))
print ("Accuracy is: %.3f" %(correct/len(X_test)))
-------------------------------------------------------------
Accuracy is: 0.921

3. KNN的决策边界¶

import matplotlib.pyplot as plt
import numpy as np
from itertools import product
from sklearn.neighbors import KNeighborsClassifier

# 生成一些随机样本
n_points = 100
X1 = np.random.multivariate_normal([1,50], [[1,0],[0,10]], n_points)
X2 = np.random.multivariate_normal([2,50], [[1,0],[0,10]], n_points)
X = np.concatenate([X1,X2])
y = np.array([0]*n_points + [1]*n_points)
print (X.shape, y.shape)

# KNN模型的训练过程
clfs = []
neighbors = [1,3,5,9,11,13,15,17,19]
for i in range(len(neighbors)):
    clfs.append(KNeighborsClassifier(n_neighbors=neighbors[i]).fit(X,y))

# 可视化结果
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),
                     np.arange(y_min, y_max, 0.1))

f, axarr = plt.subplots(3,3, sharex='col', sharey='row', figsize=(15, 12))
for idx, clf, tt in zip(product([0, 1, 2], [0, 1, 2]),
                        clfs,
                        ['KNN (k=%d)'%k for k in neighbors]):
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    axarr[idx[0], idx[1]].contourf(xx, yy, Z, alpha=0.4)
    axarr[idx[0], idx[1]].scatter(X[:, 0], X[:, 1], c=y,
                                  s=20, edgecolor='k')
    axarr[idx[0], idx[1]].set_title(tt)
    
plt.show()