knn算法python理解与预测_机器学习模型1 K-Nearest Neighbor（KNN）算法-基于Python sklearn的实现...

1、模型原理

(一)原理

1、原理：是一种常用的监督学习方法，给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。也有无监督的最近邻，暂不讨论。

2、判定方法主要有两种：

(1)在分类任务中的可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；

(2)在回归任务中可使用“平均法”，即将这k个样本的标记平均值作为预测结果。

(3)还可以根据距离远近，对样本进行加权，实现加权平均或加权投票。

(二)注意点：

1、距离度量方法不同，找到的“近邻”也可能有显著区别，进而导致分类结果不同。通常是用欧式距离，即平方和开根号。

2、k在其中是一个相当重要的参数，k取值不同时，分类结果会有显著不同。

3、

(三)相关概念

1、“维度灾难”，如果样本的属性维度过多，在这种高维情况下，会出现数据样本稀疏(不密集，太过分散)，距离计算困难等问题，这是所有机器学习方法共同面对的问题，被称为维度灾难。

2、由于这种情况，就需要进行降维。在低维空间中保持样本点间的距离不变，最简单的是对原始的高维空间进行线性变换，主成分分析就是最常见的一种线性降维方法。

有时，需要非线性映射才能找到恰当的低维嵌入，就会采用比如“核技巧”等非线性降维方法。

这里引申出来了“主成分分析”方法，可以在下面做补充。

(四)Python实现步骤

(1)计算已知类别数据集中的每个点依次执行以下操作；

(2)按照距离递增次序排序(越来越大)；

(3)选取与当前点距离最小的k个点；

(4)确定前k个点所在类别的出现频率；

(5)返回前k个点出现频率最高的类别作为当前点的预测分类

最近邻算法，是基于输入样本的，它和其他算法不一样，最近邻不会试图去构造一个泛化的模型(即，它的思路不是去拟合出一个含有各种参数的函数，然后把新的数据带入就可以得到新的结果)，而只是去简单的使用输入训练集的所有数据，通过测算距离，来实现分类或回归。

分为KNN分类(KNeighborsClassifier)和KNN(KNeighborsRegressor)回归两种，一种是预测属性(离散值)，一种是预测数值(连续值)。

与它对应的还有，通过设置半径R来进行分类和回归的，RadiusNeighborsClassifier和RadiusNeighborsRegressor。当用户确定了一个半径之后，这些在半径之内的点都会被考虑。

当我们需要训练的数据不那么规范的时候RadiusNeighborsClassifier (RN)会是一个更好的选择，对于一些高维空间，RN的效率会受到影响，这也是一种“维度之殇”了吧。

2、Python3中sklearn-KNN的代码实现

第一，sklearn中的KNN包源代码(未查到，以后补充)

第二，sklearn中的KNN包，有几个可调参数，及每个参数代表的意义

KNeighborsClassifier( n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=1, **kwargs )

n_neighbors，即选择k值，较大的k值可以容忍较多的噪声，但是会使得分类的结果变的不那么精确；但样本不平衡时，一个类样本容量很大，其他样本容量很小，导致输入新样本时，该样本邻近中大样本占多数，因此可以采取权值的方法(和样本距离小的邻近权值大)来改进，减少k值选择对结果的影响；可以通过循环来尝试不同的k值的效果。

weights，即权重设置，‘uniform’和‘distance’，对每个点赋予同样的权重，或者根据距离远近，赋予不同的权重(距离越远权重越小)。

algorithm，即搜索最近邻算法的选择，包括ball_tree、kd_tree、brute和auto。

brute代表Brute Force算法，就是一个最原始(蛮力)邻居搜索做法，Brute Force在寻找邻居时，会把输入的点同所有样本中的点做一个距离计算，然后再排序选择最近的点。

kd_tree代表KD树算法，为了解决BF算法效率低下的问题，人们提出了很多树形结构的算法，树形结构的主要贡献在于，它们一般通过事先的合理组织，降低了我们搜索中的开销，也就是使用树形结构的算法，我们在搜索时可以不用每个样本都去计算距离了，这无疑降低了很多的开销。在不太高的维度(小于20)下，KD树的效果是很不错的，不过当维度走向更高时，KD树的效率也会随之下降，这也呼应了我们之前提到的“维度之殇”的问题。

ball_tree代表Ball Tree算法，KD-Tree是为了解决Brute Force的效率问题，那么Ball-Tree也就是为了解决KD-Tree在高维情况下的效率不佳的另一个做法了，Ball树在构建的时候，比起KD树要复杂许多，不过在最后的搜索过程中，其表现就会非常好。

三者的选取：样本≤30，用BF；样本较大，但维度≤20，用KD_tree；维度更多的，用ball tree。

参考：知乎回答：KDtree和Ball Tree的区别

默认值是auto，在auto下，将会从你给定的测试数据当中选择最终性能最好的哪一个算法。

leaf_size，设置一个数值，什么时候切换到BF暴力求解，默认是30。

metric ，用于树的距离度量。默认’minkowski与P = 2(即欧氏度量)。

第三，KNN的基本操作

from sklearn.neighbors import KNeighborsClassifier

knn ＝ KNeighborsClassifier(n_neighbors=6) #设置knn中的参数，并赋予某变量

knn.fit(x,y) #导入训练集，进行模型训练，x是数据，y是标签

y_pred = knn.predict(X_new) #带入新样本进行分类预测

如何判断准确率？那只能是把有标签的数据划分为训练集、测试集，然后看它预测的准确率。

from sklearn.model_selection import train_test_split #调用了sklearn中进行测试集和训练集分类的函数

X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=42,stratify=y)

knn.score(X_test,y_test) # .score，就是测试准确度用的

具体的用法如下：

fit(x,y) #导入数据

get_params([deep]) #获取此估算器的参数

kneighbors([X, n_neighbors, return_distance]) #找到一个点的n个邻居，并返回距离值

kneighbors_graph([X, n_neighbors, mode]) # 计算X中的点的k-邻居的(加权)图

predict(X) #预测提供的数据的分类标签

predict_proba(X) #返回测试数据X的概率估计。

score(X, y[, sample_weight]) #返回给定测试数据上的平均精确度

set_params(**params) #设置此估算器的参数

取不同k值时，计算准确度

#取不同k值的效率图：

#创建一个数组储存训练和测试数据的精确度

neighbors = np.arange(1, 9)

train_accuracy = np.empty(len(neighbors))

test_accuracy = np.empty(len(neighbors))

# 循环对k进行赋值

for i, k in enumerate(neighbors):

# Setup a k-NN Classifier with k neighbors: knn

knn = KNeighborsClassifier(n_neighbors=k)

# Fit the classifier to the training data

knn.fit(X_train,y_train)

#计算训练集的准确度

train_accuracy[i] = knn.score(X_train, y_train)

#计算测试集的准确度

test_accuracy[i] = knn.score(X_test, y_test)

用一个循环对

一个简单的小例子

import numpy as np

from sklearn import neighbors

knn = neighbors.KNeighborsClassifier() #取得knn分类器

data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]) #data对应着打斗次数和接吻次数

labels = np.array([1,1,1,2,2,2]) #labels则是对应Romance和Action

knn.fit(data,labels) #导入数据进行训练

print(knn.predict([18,90]))

一点注意

拿《机器学习实战》中第二章KNN部分的约会网站数据进行了测试，发现虽然直接用的是结果类别标签数据‘largeDoses’、‘smallDoses’、‘didntLike’，未进行类别变量的转换，但在模型预测时，可以正确执行预测，结果直接为‘didntLike’等。

3、参考资料

参考的两篇帖子，NumPy 和 sklearn入门,以及 ML神器：sklearn的快速使用。

里面提到的几个点很好，比如为什么不用Python自带的数组list，而使用Numpy的array。

比如，sklearn中各个算法有统一的API接口，各个算法的一般实现流程是：

step1. 数据加载和预处理

step2. 定义分类器, 比如： lr_model = LogisticRegression()

step3. 使用训练集训练模型 ： lr_model.fit(X,Y)

step4. 使用训练好的模型进行预测： y_pred = lr_model.predict(X_test)

step5. 对模型进行性能评估：lr_model.score(X_test, y_test)

引申问题

1、计算样本间的差异有多大，也就是样本间距离。涉及到如何衡量距离。

2、排序问题，最经典的算法问题了。

这应该都有专门的代码。