KNN算法
本篇将介绍knn算法，knn算法因为思想非常简单，运用的数学知识比较浅显，是非常适合机器学习入门的算法。不仅如此，knn算法在很多分类问题上表现优异， k近邻算法最基本的可以解决分类问题，不过也可以解决回归问题（以后会介绍）。借助此算法，可以解释机器学习算法使用过程中的很多细节问题，从而更加完整地刻画机器学习应用的流程。
下面以一个简单的肿瘤判别问题介绍knn是做什么的。
knn1
如上图所示，假设横轴方向表示肿瘤大小，纵轴方向表示肿瘤存在多久时间，绿色表示良性肿瘤，红色表示恶性肿瘤。现在有一个新的样本不知是良性还是恶性，要对它作出判断。knn算法的做法是，检查它周围的k个数据点，如果良性居多则判断为良性，否则判断为恶性。
下面生成模拟数聚集：
#展示算法原理（肿瘤判别）
import numpy as np
import matplotlib.pyplot as plt
#生成模拟数据
raw_data_x=[
[3.393,2.331]
,[3.110,1.782]
,[1.344,3.368]
,[3.582,4.679]
,[2.281,2.867]
,[7.423,4.697]
,[5.745,3.534]
,[9.172,2.511]
,[7.793,3.424]
,[7.940,0.792]
]
raw_data_y=[0,0,0,0,0,1,1,1,1,1]#0表示良性，1恶性
x_train=np.array(raw_data_x)#制作训练集
y_train=np.array(raw_data_y)
数聚集共包含10个样本点，首先对数聚集做图得到直观的分布情况：
'''首先作散点图观察数据分布'''
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='g')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='r')
plt.show()
traindata
现在新来了一个样本点[8.094,3.366]，要判断是良性还是恶性，首先将它画入图中：
''' knn算法要作的是，判断新来的数据点属于哪一类'''
x=np.array([8.094,3.366])
'''为了看清楚新来点与其它点位置关系，上色为blue'''
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='g')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='b')
plt.show()
sample
我们可以直观地判断这是恶性肿瘤，因为它周围几乎都是恶性肿瘤样本点，下面从原理的角度来看一下KNN流程：
首先计算新的样本点与训练集各样本的距离，距离可以选用曼哈顿距离、欧式距离、明氏距离等，这里选用欧式距离：
from math import sqrt
distances=[]#欧式距离，曼哈顿距离，明式距离
#计算新的样本点与训练集中每个样本点的距离
for x_t in x_train:
d = sqrt(np.sum((x_t - x)**2))#universal function，结果向量的每个元素都平方，再求和，然后开方
distances.append(d)
distances
out:[4.813587643327999,
5.2296569677178635,
6.750000296296289,
4.699160882540626,
5.834378287358473,
1.4905710315177867,
2.354999999999999,
1.37590297623052,
0.30653711031455805,
2.5786027224060706]
或者生成表达式一步到位：
#上面的过程python中一句话搞定
distances=[sqrt(np.sum((x_t-x)**2)) for x_t in x_train]
distances
下面对距离进行排序，而且要知道排序对应的是哪个样本，使用argsort返回排序索引：
#下面要进行排序，而且要知到排序结果是哪些点，用argsort
np.argsort(distances)#sort默认升序排列
out:array([8, 7, 5, 6, 9, 3, 0, 1, 4, 2])#即离x最近的是索引为8的点
进行预测：
nearest=np.argsort(distances)
k=6
返回与新来样本前6近的数据集样本类别：
topk_y=[y_train[i] for i in nearest[:k]]#返回与给定样本点最近的k个样本的分类
topk_y
out:[1, 1, 1, 1, 1, 0]
计数投票：
#计数
from collections import Counter
Counter(topk_y)
out:Counter({1: 5, 0: 1})
上述结果表示最近的6个中，为1（恶性）有5个，为0（良性）有一个。于是给出预测结果：
predict
预测结果为1，即为恶性肿瘤。
sklearn中的分类器
函数方式封装knn分类器
新建knn.py，内容如下：
import numpy as np
from math import sqrt
from collections import Counter
def kNN_classify(k,x_train,y_train,x):
assert 1<=k<=x_train.shape[0],"k must be valid"
assert x_train.shape[0] == y_train.shape[0],"must be same"
assert x_train.shape[1]==x.shape[0],"must be the same"
distances=[sqrt(np.sum((x_t-x)**2)) for x_t in x_train]
nearest=np.argsort(distances)
topk_y=[y_train[i] for i in nearest[:k]]
votes=Counter(topk_y)
predict_y=votes.most_common(1)[0][0]#knn预测结果
return predict_y
在jupyter notebook中：
%run knn.py
predict_y=kNN_classify(6,x_train,y_train,x)
predict_y
可以得到相同的预测结果。
有人可能会有疑问了，不是说机器学习算法都需要建模之后训练模型吗，没错，但knn算法比较特殊，可以说knn是唯一一个不需要训练过程的算法，即输入样例可直接送给训练数剧集得到输出预测。由此也可以看出，knn算法是非常特殊的，可以被认为是没有模型的算法，为了和其它算法统一，可以认为训练集就是模型本身。这也是scikit-learn中的处理方式，为了所有机器学习算法有统一的宏观流程，都有fit和predict过程。knn的fit过程算是最简单的。
sklearn中的knn
上述过程也可以用sklearn中提供的机器学习算法实现，如实现knn算法：
from sklearn.neighbors import KNeighborsClassifier
kNN_classifier = KNeighborsClassifier(n_neighbors=6)#创建knnclassifier实例
kNN_classifier.fit(x_train,y_train)#fit过程训练数据集，得到模型
'''将x整理为矩阵格式'''
x_new=x.reshape(1,-1)
kNN_classifier.predict(x_new)
out:array([1])
注意：在sklearn中，输入进行预测的数据从version_19之后只支持矩阵格式的数据，不再支持单个数据预测了，如果要预测单个数据需要整理为矩阵格式。
sklearn中实现机器学习的基本步骤一般包括三个：
- 实例化分类器
- 执行fit训练过程
- 执行predict预测过程
如在上述代码调用sklearn实现knn算法执行过程。
改造我们的代码为sklearn代码调用格式
我们可以修改自己的knn代码，使得在调用形式上和sklearn中调用knn算法是一样的，这能让我们更加理解knn算法和理解sklearn进行机器学习的流程。
'''kNN_sklearn.py'''
import numpy as np
from math import sqrt
from collections import Counter
class kNNClassifier:
def __init__(self,k):
assert k>=1,"k must be valid"
self.k=k
self._x_train=None#训练数剧集外部用户不能随便操作，设为私有
self._y_train=None
def fit(self,x_train,y_train):
assert x_train.shape[0] == y_train.shape[0],"must be same"
assert self.k<=x_train.shape[0],"k must be valid"
self._x_train=x_train
self._y_train=y_train
return self
def predict(self,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],"must be the same"
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],"must be the same"
distances=[sqrt(np.sum((x_t-x)**2)) for x_t 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]#knn预测结果
def __repr__(self):
return "kNN(k=%d)"%self.k
然后就可以使用我们自己写的knn分类器了
%run kNN_sklearn.py
实例化、fit、预测
knn_clf=kNNClassifier(k=6)
knn_clf.fit(x_train,y_train)
out:kNN(k=6)
y_predict=knn_clf.predict(x_new)
y_predict
out:array([1])
y_predict[0]
out:1
但实际中sklearn的算法为了在格式上统一比这个要复杂的多，这里只是简单实现了sklearn的底层。
网友评论