算法特点
背后思想简单，应用数学原理简单，效果好，而且可以说是在诸多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) 进行处理。
