KNN 代码实现
2019-12-23 本文已影响0人
zidea
KNN 模型(K-Nearest Neighbor)
Easy-Steps-to-Understanding.jpg
KNN 算法的一个最吸引人的特点是简单易懂，由于模型在较少训练时间内就可以达到一个不错效果，所以被应用到一些数据集的即时分析，这也是 KNN 的优点。因为 KNN 不需要带有参数的模型进行训练，所以 KNN 是无参数的模型，可以用于分类和回归。
算法
其中 K 表示在新样本点附近(距离)选取 K 个样本数据，通过在 K 个样本进行投票来判断新增样本的类型。
- k 是否可以取偶数，当 K 为偶数时，如果 K 点不同类别样本点各占一半，我们不是无法对新样板点进行推测。我们可以通过距离来进一步推测样本点类别。
我们可以取每一个点权重 - k 取 1 可能发生过拟合，如果 K 选取无穷大，那么就变成哪个点多就把任何新的数据分为哪个数据多类别
- 任何两个点距离的之间连接连线，每一个小块，最近邻的数据，不再是中线而是面，
- k近邻可以做预测，估计一个人成绩，也就是我们可以通过临近点的均值或者带有按离推测样本点距离作为权重来计算该样本点的值。
A 和 B 两点间距离需要满足以下条件
- 对称 d(A,B) = d(B,A) 也就是 A 到 B 的距离等于 B 到 A 的距离
- d(A,A) = 0 样本点到自己本身的距离为 0
- d(A,B) = 0 iff A = B 两点距离为 0 那么这两个点就是同一个点
- d(A,B) <= d(A,C) + d(B,C) 三角不等式
距离(模)
- 欧氏距离
- 曼哈顿距离
- 切比雪夫距离
- hamming distance(异或运算)，通过两个二进制数做异或来得到估计值
- consine similarity
代码实现
接下来就是程序员最感兴趣的部分，coding 了，对于程序员总是喜欢自己实现一下，这样才会相信。这里参考 sklearn 的 api 来设计模型提供 fit 和 predict
# coding=utf-8
class KNN:
def __init__(self,k=3):
self.k = k
# 训练数据
def fit(X,y):
pass
def predict(self,X):
pass
- 构造函数接受 k 参数
- fit 函数接受样本，第一个参数样本集合而第二参数是样本标签
- predict 方法只有一个参数就是预测样本
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from matplotlib.colors import ListedColormap
cmap = ListedColormap(['#FF0000','#00FF00','#0000FF'])
iris = datasets.load_iris()
X,y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X,y,test_size=0.2,random_state=1234)
print(X_train.shape)
print(X_train[0])
这里数据集九四 iris 经典数据集，因为经典也就不再多说了。输出一下数据集数据结构和样本值
(120, 4)
[5.1 2.5 3. 1.1]
cmap = ListedColormap(['#FF0000','#00FF00','#0000FF'])
iris = datasets.load_iris()
X,y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X,y,test_size=0.2,random_state=1234)
print(X_train.shape)
print(X_train[0])
print(y_train.shape)
print(y_train)
plt.figure()
plt.scatter(X[:,0],X[:,1],c=y,cmap=cmap,edgecolors='k',s=20)
plt.show()
为更直观观察数据分布我们 matlibplot 将其以图形方式现实处理啊，不同颜色表示不同类别，用样本前两个特征作为 x 轴和 y 轴
iris_scatter.png
class KNN:
def __init__(self,k=3):
self.k = k
# 训练数据
def fit(self,X,y):
self.X_train = X
self.y_train = y
# 预测
def predict(self,X):
predicted_labels = [self._predict(x) for x in X]
return np.array(predicted_labels)
#
def _predict(self,x):
pass
- 在 KNN 的属性 X_train 和 y_train 接受样本和样本标签
- predict 返回一个样本所属类型的组数
这里我们定义计算两个点距离采用欧式距离来衡量样本间的距离
def euclidean_distance(x1,x2):
return np.sqrt(np.sum((x1-x2)**2))
def predict(self,X):
predicted_labels = [self._predict(x) for x in X]
return np.array(predicted_labels)
#
def _predict(self,x):
# 计算距离
distances = [euclidean_distance(x,x_train) for x_train in self.X_train]
# 获取 k 邻近样本和标签
k_indices = np.argsort(distances)[:self.k]
k_nearest_labels = [self.y_train[i] for i in k_indices]
# 通过投票进行分类
most_common = Counter(k_nearest_labels).most_common(1)
有关 Counter 方法如何使用，说起来可能有点不好解释，还是用代码来说明更加直观易于理解
a = [1,1,1,3,5,6,7,7,8]
from collections import Counter
most_common = Counter(a).most_common(1)
print(most_common)
[(1, 3)]
从 code 运行结果不难看出，most_common 就是计算出现，返回一个 tuple 结构的数据第一个值是在数组 a 中哪一个数出现次数最多，这样就是 1 第二个数表示 1 一共在数组 a 中出现几次。
class KNN:
def __init__(self,k=3):
self.k = k
# 训练数据
def fit(self,X,y):
self.X_train = X
self.y_train = y
# 预测
def predict(self,X):
predicted_labels = [self._predict(x) for x in X]
return np.array(predicted_labels)
#
def _predict(self,x):
# 计算距离
distances = [euclidean_distance(x,x_train) for x_train in self.X_train]
# 获取 k 邻近样本和标签
k_indices = np.argsort(distances)[:self.k]
k_nearest_labels = [self.y_train[i] for i in k_indices]
# 通过投票进行分类
most_common = Counter(k_nearest_labels).most_common(1)
return most_common[0][0]
这里说一说 predict 方法，这里做法就是依次计算预测样本到每一个数据集样本点距离，然后按大小排序后取前 k 样本，然后在 k 个距离其附近样本点所属标签出现次数做多标签作为其标签来决定这个样本属于那个分类。
最后来验证之前的代码是否有效，最好方法就是运行一下。
from knn_model import KNN
clf = KNN(k=3)
clf.fit(X_train,y_train)
predictions = clf.predict(X_test)
acc = np.sum(predictions == y_test) / len(y_test)
print(acc)
