前言
经典的knn了解一下。
1.算法思路
1.1算法基本思想
knn的基本思想:需要确定一个样本A的类别，可以计算出它与所有训练样本的距离，然后找出和该样本距离最小的k个样本，对这k个样本的类别进行统计，样本数最多的那个类别就是我们A的类别了。
1.2预测算法流程
knn没有需要求解的参数，没有训练过程，参数k由人工指定。对于分类问题，给定n个训练样本(xi,yi)，xi为特征向量，yi为标签值。设定合适的参数k，类别数为c，待分类的样本为x。算法的预测流程如下。
(1)在训练数据中找出离x最近的k个样本，假设这些样本的集合为N。
(2)统计集合N中每类样本的数量Ci,i=0,1,2…,c-1。
(3)最终分类结果为argmaxCi,即样本数最多的那个类别。
在实现的时候还可以考虑样本的权重，即每个样本带有不同的样本权重，比如说这个权重和每个类样本数在总样本数占比有关，这种方法成为带权重的k近邻算法。
1.3常用距离公式
(1)曼哈顿距离：
(2)欧式距离
(3)闵可夫斯基距离
可以看作是欧式的一种推广。
(4)夹角余弦
夹角余弦取值范围为[-1,1],可以用来衡量两个向量方向的差异。夹角余弦越大，表示两个向量的夹角越小。
(4)巴氏距离
定义两个离散型或连续型概率分布的相似性。对于离散型随机变量，它定义为:
其中，xi,yi为两个随机变量取某个值得概率，它们是向量x,y得分量。两个向量越相似，这个距离值越小。
简单的numpy实现
按照上面所陈述得思路，knn得简单numpy实现如下，笔者使用的是iris数据集。
'''
knn numpy简单实现
追天一方
'''
import numpy as np
from sklearn import datasets
class knn(object):
'''
实现k近邻算法
'''
def __init__(self,x,y):
'''
样本集数据和标签
'''
self.x=x
self.y=y
def pre(self,point_x,k):
'''
预测函数
'''
#有多少特征维度
dim=self.x.shape[1]
#point_x和样本点之间的欧氏距离
distance=None
for i in range(dim):
d=self.x[:,i]-point_x[:,i]
if distance is None:
distance=d
else:
distance=distance+d
distance=np.sqrt(np.square(distance))
max_distance=np.max(distance,axis=0)
#选取k个离point_x最近的，也就是距离最小的
k_points=[]
for i in range(k):
point = np.argmin(distance, 0)
k_points.append(point)
#计算的最小值给一个很大的值，或者可以给样本数据中的最大值,就不会妨碍后面的计算了
distance[point]=max_distance
assert len(k_points)==k,"len(k_points!=k"
#把这k个样本点的标签拿出来
k_y=self.y[k_points]
# 算出分类类别数，因为一般类别都是从0开始的连续数字
class_nums=np.max(k_y,0)+1
#计算每个类别在这k个样本点中的个数
y_num=np.zeros((class_nums,1))
for i in range(k):
y_num[k_y[i]]=y_num[k_y[i]]+1
result=np.argmax(y_num,0)
return result
if __name__ == '__main__':
# 载入iris数据集
iris = datasets.load_iris()
# 只使用前面连个特征
X = iris.data
# 样本标签值
y = iris.target
clf=knn(X,y)
data=np.array([[5.8,3.1,5.0,1.7]])
result=clf.pre(data,10)
print(result)
代码注释很清晰，笔者就不详解了
sklearn实现
sklearn提供两种方法实现knn，第一种是类KNeighborsRegressor 基于每个查询点的 k 个最近邻实现，也就是类似上面的numpy实现。
类RadiusNeighborsRegressor 基于每个查询点的固定半径 r 内的邻点数量实现。它的近邻查找使用使KDTree 或 BallTree。
实现代码如下：
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
import matplotlib
# 生成所有测试样本点
def make_meshgrid(x, y, h=.02):
x_min, x_max = x.min() - 1, x.max() + 1
y_min, y_max = y.min() - 1, y.max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
return xx, yy
# 对测试样本进行预测，并显示
def plot_test_results(ax, clf, xx, yy, **params):
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
ax.contourf(xx, yy, Z, **params)
# 载入iris数据集
iris = datasets.load_iris()
# 只使用前面连个特征
X = iris.data[:, :2]
# 样本标签值
y = iris.target
# 创建kNN分类器
knn = KNeighborsClassifier()
knn.fit(X,y)
title = ('KNNClassifier')
fig, ax = plt.subplots(figsize = (5, 5))
plt.subplots_adjust(wspace=0.4, hspace=0.4)
X0, X1 = X[:, 0], X[:, 1]
# 生成所有测试样本点
xx, yy = make_meshgrid(X0, X1)
# 显示测试样本的分类结果
plot_test_results(ax, knn, xx, yy, cmap=plt.cm.coolwarm, alpha=0.8)
# 显示训练样本
ax.scatter(X0, X1, c=y, cmap=plt.cm.coolwarm, s=20, edgecolors='k')
ax.set_xlim(xx.min(), xx.max())
ax.set_ylim(yy.min(), yy.max())
ax.set_xlabel('x1')
ax.set_ylabel('x2')
ax.set_xticks(())
ax.set_yticks(())
ax.set_title(title)
plt.show()
运行结果如下：
