学习笔记： 机器学习经典算法-kNN(k近邻算法)

算法特点
背后思想简单，应用数学原理简单，效果好，而且可以说是在诸多ML算法中独有的不需要训练模型的算法。

基本过程：对于判断特征空间中的一个样本点的归类，通过在该样本点周围搜索$k$个与其距离最近的邻居，然后根据这$k$个邻居所属类别占比来来判断目标样本点的最可能类别。

一、分类kNN算法的基本过程（python）

①数据集准备

import matplotlib.pyplot as plt
import numpy as np
Point_set = np.concatenate([np.random.normal(1,1,10),np.random.normal(2.5,1,10)]).reshape(10,2) ### 样本特征集
Point_class = np.array([0,0,0,0,0,1,1,1,1,1])  ### 样本标签集

plt.scatter(Point_set[Point_class == 0,0],Point_set[Point_class == 0,1],color = "g")
plt.scatter(Point_set[Point_class == 1,0],Point_set[Point_class == 1,1],color = "r")
plt.show()

②算法过程

### 测试点
x = np.array([1.25,1.5])

from math import sqrt
distances = [ sqrt(np.sum(p - x)**2) for p in Point_set ] ### 求取特征空间上已有点集与目标点的距离
top_k = Point_class[np.argsort(distances)[:3]] ## 排序提取离目标点最近的3个点

from collections import Counter
votes = Counter(top_k)  ## 统计离目标点最近的3个点的类别信息（类似R中的tabble()函数），该过程叫做投票
votes.most_common(1)[0][0] ### 获取这3个点最多来源的类别，从而完成 kNN过程 得出基于3个最近邻居类别判断的目标点的类别信息

③使用scikit-learn中的kNN

from sklearn.neighbors import KNeighborsClassifier
kNN_classfier = KNeighborsClassifier(n_neighbors=3) ###  sklearn 框架中的算法函数以面向对象的方式进行包装，调用的时候需要初始化实例
kNN_classfier.fit(Point_set,Point_class) ### fit模型，虽然kNN算法本身没有创建模型的过程，在sklearn中为了与其它算法统一，也引入了fit过程，该过程可以认为训练集就是模型本身
kNN_classfier.predict(x.reshape(1,-1)) ### 现实使用过程中，通常是对多个数据点进行预测，所以sklean默认接受2D矩阵的数据集输入，所以这里需要将1维向量进行reshape

④算法的类封装

import numpy as np
from math import sqrt
from collections import Counter

class KNNClassifier:
    def __init__(self,k):
        """初始化kNN分类器"""
        assert k >= 1, "k must be valid"
        self.k = k
        self._X_train = None
        self._Y_train = None

    def fit(self,X_train,Y_trian):
        """根据训练集X_tain和Y_train训练kNN分类器"""
        assert X_train.shape[0] == Y_train.shape[0], "the size of X_train must be equal to the size of "
        assert self.k <= X_train.shape[0], "the size of X_train must be at least k."
        self._X_train = X_train
        self._Y_train = Y_trian
        return self

    def preditc(self,X_predict):
        """给定预测数据集X_predict,返回表示X_predict 的结果向量"""
        assert self._X_train is not None and self._Y_train is not None, "must fit before predict!"
        assert X_predict.shape[1] == self._X_train.shape[1], "the feature number of X_predict must be equal to X_train"

        Y_predict = [self._predict(x) for x in X_predict]
        return np.array(Y_predict)
    def _predict(self,x):
        """给定单个待预测x，返回x的预测结果值"""
        assert x.shape[0] == self._X_train.shape[1],"the feature number of x must be equal to X_train"

        distances = [sqrt(np.sum((x - x_train)**2)) for x_train in self._X_train]
        nearest = np.argsort(distances)
        topK_y = [self._Y_train[i] for i in nearest[:self.k]]
        votes = Counter(topK_y)

        return votes.most_common(1)[0][0]

    def __repr__(self):
        return "KNN(k=%d)" % self.k ### 类实例化之后的输出信息

自己封装方法在jupyter-notebook的调用 %run path/your_script.py

二、分类kNN 算法中的超参数

超参数：运行一个机器学习之前需要指定的参数，比如运行kNN算法的时候需要指定的k就是该算法的超参数。
模型参数：算法过程中学习的参数。kNN算法没有模型参数。

寻找最佳超参数的方法：

• 领域知识
• 经验数值(sklearn 框架内的kNN算法中，就给出了k = 5的经验值)
• 实验搜索

实验法搜索kNN中超参数k

import numpy as np
from sklearn import datasets

digits = datasets.load_digits() ### 载入手写数字数据集
X = digits.data
y = digits.target
### test_train_split
from sklearn.model_selection import train_test_split
Train_X,Test_X,Train_Y,Test_Y = train_test_split(X,y,test_size= 0.2,random_state=666)


### search k
from sklearn.neighbors import KNeighborsClassifier
best_score = 0.0
best_k     = -1
for k in range(1,11): ### 小范围搜索
    knn_clf = KNeighborsClassifier(n_neighbors= k)
    knn_clf.fit(Train_X,Train_Y)
    score = knn_clf.score(Test_X,Test_Y) ## 计算预测准确度(accuarcy)

    if score >= best_score :
        best_score = score
        best_k = k

print("best k =", best_k)
print("best score =",best_score)

搜索技巧说明：对于以上在小范围1~10区间对最优k的搜索上，如果本次搜索最优的k值出现在1~10区间内，那么该最优k值是可以接受的。但是如果该搜索过程得出的最优k值出现在搜索范围的边界的话，如best_k = 10，那么就有必要扩大搜索范围进一步搜索，因为通常不同的参数决定了不同的分类准确率，它们之间是一个连续变化的关系。

①kNN算法-距离权重超参数

对于普通kNN算法，其仅仅只考虑了其最近k个邻居的投票，忽略了与邻居的距离权重因素，这样会使其分类的效果偏差。因此有必要考虑上其邻居投票的距离权重（一般使用距离的倒数作为权重，距离越大权重越小）。

scikit-learn框架中实例化kNN分类器的时候可以指定weights = distance参数指定使用距离权重KNeighborsClassifier(n_neighbors= k, weights = distance )

试验搜索kNN算法中超参数k和weights的方法

### search k
from sklearn.neighbors import KNeighborsClassifier
best_score = 0.0
best_k     = -1
best_method = ""
for method in ["uniform","distance"]:
    for k in range(1,11):
    knn_clf =KNeighborsClassifier(n_neighbors= k, weights = method )
    knn_clf.fit(Train_X,Train_Y)
    score = knn_clf.score(Test_X,Test_Y)

    if score >= best_score :
        best_score = score
        best_k = k
        best_method = method


print("best k =", best_k)
print("best score =",best_score)
print("best method =",best_score)

②kNN算法-距离超参数

关于距离定义的一般形式为：
明可夫斯基距离:$(\sum_{i=1}^{n}{|X_i^{(a)} - X_i^{(b)}|^{p }})^{\frac{1}{p}}$
由明可夫斯基距离的一般形式当$p$取不同值表示了其它距离类型：
①曼哈顿距离 :$(\sum_{i=1}^{n}{|X_i^{(a)} - X_i^{(b)}|})^{\frac{1}{1}}$ #描述的是空间上两个点各维度上差值的绝对值的和。

②欧拉距离：$\sqrt {\sum_{i =1}^{n}{(X_i^{(a)}} - X_i^{(b)})^{2}} = (\sum_{i=1}^{n}{|X_i^{(a)} - X_i^{(b)}|^{2}})^{\frac{1}{2}}$ #描述的是空间上两个点的直线距离。

在统计学范畴，通常还会使用样本的相似性来作为距离的度量,类如

• 向量空间的余弦相似度
• 调整余弦相似度
• 皮尔森相关系数
• Jaccard相似系数

scikit-learn框架中实例化kNN分类器的时候可以指定p参数指定使用距离类型(默认p= 2使用欧氏距离)：KNeighborsClassifier(n_neighbors= k, p= 2)。这p参数也是一个kNN分类器的超参数。

通过循环试验的方式搜索最优超参数的方式，称为网格搜索。

scikit-learn 框架下的网格搜索(Grid Search)实现

以list和字典(dict)*的格式网格搜索要搜索的超参数:

### 组织需要搜索的超参数以及搜索范围为 Grid search 的输入格式
param_grid = [
    ### 搜索的第一组超参数
    {
        'weights':['uniform']
        'n_neighbors':[i for i in range(1,11)]
    },
    ### 搜索的第二组超参数
    {
        'weights':['distance']
        'n_neighbors':[i for i in range(1,11)]
        'p':[i for i in range(1,6)]
    }
]

### 初始化kNN方法
knn_clf = KNeighborsClassifier()
### 加载Grid Search
from sklearn.model_selection import GridSearchCV
grid_search = GridSearchCV(knn_clf,param_grid,n_jobs= 4, verbose = 2) ### verbose 参数传入整数，对应输出信息的详细程度，越大则输出越详细
### 开始Grid Search
grid_search.fit(X_Train,Y_Train)
### 搜索到的最佳超参数结果
grid_search.best_params_
### 最佳超参数的准确度评分
grid_search.best_estimator_

### 使用具有最佳超参数的分类分类器
knn_clf = grid_search.best_estimator_
knn_clf.score(X_Test,Y_Test)

三、kNN 处理回归问题

kNN主要是为了解决多分类问题。但使用kNN算法也能用来解决回归问题(思路：求取k个最近邻居的值的平均值或者加权平均值(如距离权重)来求取样例的值)

在scikit-learn 框架中对应的是KNeighborsRegressor类。

四、kNN 算法缺点

①最大的缺点是 效率低下，优化可以通过使用树结构（KD-Tree，Ball-Tree）。
②kNN算法高度数据相关，对数据集中的outlier高度敏感，意味着如果数据集中存在错误的标签，那么预测结果也将变得不可靠。
③kNN算法的预测结果不具有可解释性，也就是说无法解释为什么预测结果属于A类别这件事，从而无法基于预测结果进行总结推广来发现新的理论。
④维数灾难，随着维度增加，看似相近 的两个样本点之间的距离会越来越大。该问题一般使用 降维(PCA) 进行处理。