kNN思想简介
kNN(k-NearestNeighbor)，也就是k最近邻算法。顾名思义，所谓K最近邻，就是k个最近的邻居的意思。也就是在数据集中，认为每个样本可以用离他最距离近的k个邻居来代表。
因此我们说：
在一个给定的类别已知的训练样本集中，已知样本集中每一个数据与所属分类的对应关系（标签）。在输入不含有标签的新样本后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似的k个数据(最近邻)的分类标签。通过多数表决等方式进行预测。即选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
K近邻法不具有显式的学习过程，而是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。
kNN算法流程
通过理解算法思想，可以将其简化为“找邻居+投票”。K近邻法使用的模型，实际上是特征空间的划分。模型由三个基本要素决定：
距离度量
k值
分类决策规则
其中两个实例点之间的距离反映了相似程度。一般来说使用欧氏距离来计算。
梳理kNN算法流程如下：
1.计算测试对象到训练集中每个对象的距离
2.按照距离的远近排序
3.选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4.统计这k个邻居的类别频率
5.k个邻居里频率最高的类别，即为测试对象的类别
算法实现
kNN算法自实现
创建一一组数据：
import numpy as np
import matplotlib.pyplot as plt
#raw_data_x是特征，raw_data_y是标签，0为良性，1为恶性
raw_data_X = [[3.393533211, 2.331273381],
[3.110073483, 1.781539638],
[1.343853454, 3.368312451],
[3.582294121, 4.679917921],
[2.280362211, 2.866990212],
[7.423436752, 4.685324231],
[5.745231231, 3.532131321],
[9.172112222, 2.511113104],
[7.927841231, 3.421455345],
[7.939831414, 0.791631213]
]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
# 设置训练组
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)
# 将数据可视化
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
#plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = 'Time')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.axis([0,10,0,5])
plt.show()
数据可视化后生成的图片如下图所示。其中横轴是肿块大小，纵轴是发现时间。每个病人的肿块大小和发病时间构成了二维平面特征中的一个点。对于每个点，我们通过label明确是恶性肿瘤（绿色）、良性肿瘤（红色）。
image.png
那么现在给出一个肿瘤患者的数据（样本点）x：[8.90933607318, 3.365731514]，是良性肿瘤还是恶性肿瘤
x=[8.90933607318, 3.365731514]
x = np.array(x)
求距离
我们要做的是：求点x到数据集中每个点的距离，首先计算距离，使用欧氏距离
image.png
from math import sqrt
distances = [] # 用来记录x到样本数据集中每个点的距离
for x_train in X_train:
d = sqrt(np.sum((x_train - x) ** 2))
distances.append(d)
# 使用列表生成器，一行就能搞定，对于X_train中的每一个元素x_train都进行前面的运算，把结果生成一个列表
distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
distances
输出
[5.611968000921151,
6.011747706769277,
7.565483059418645,
5.486753308891268,
6.647709180746875,
1.9872648870854204,
3.168477291709152,
0.8941051007010301,
0.9830754144862234,
2.7506238644678445]
在求出距离列表之后，我们要找到最小的距离，需要进行一次排序操作。其实不是简单的排序，因为我们把只将距离排大小是没有意义的，我们要知道距离最小的k个点是在样本集中的位置。
这里我们使用函数：np.argsort(array) 对一个数组进行排序，返回的是相应的排序后结果的索引。
nearest = np.argsort(distances)
nearest
输出
array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2], dtype=int64)
结果的含义是：距离最小的点在distances数组中的索引是7，第二小的点索引是8... 近到远是哪些点
选K值
然后我们选择k值，这里暂定为6，那就找出最近的6个点（top 6），并记录他们的标签值（y）
k = 6
topK_y = [y_train[i] for i in nearest[:k]]
topK_y
输出
[1, 1, 1, 1, 1, 0]
决策规则
下面进入投票环节。找到与测试样本点最近的6个训练样本点的标签y是什么。可以查不同类别的点有多少个。
将数组中的元素和元素出现的频次进行统计
from collections import Counter
votes = Counter(topK_y)
votes
输出：一个字典，原数组中值为0的个数为1，值为1的个数有为5
Counter({1: 5, 0: 1})
# Counter.most_common(n) 找出票数最多的n个元素，返回的是一个列表，列表中的每个元素是一个元组，元组中第一个元素是对应的元素是谁，第二个元素是频次
votes.most_common(1)
输出
[(1, 5)]
predict_y = votes.most_common(1)[0][0]
predict_y
输出
1
得到预测的y值是1
自实现完成工程代码
我们已经在jupyter notebook中写好了kNN算法，下面我们在外部进行封装。
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):
"""根据训练数据集X_train和y_train训练knn分类器kNN分类器"""
assert X_train.shape[0] == y_train.shape[0],\
"the size of X_train must be equal to the size of y_train"
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_train
return self
def predict(self,X_predict):
"""给定待遇测数据集X_predcit,返回表示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):
distances = [sqrt(np.sum((x_train - x)**2)) for x_train in self._X_train]
nearest = np.argsort(distances)
topK_y = [self._y_train[i] for i in nearest]
votes = Counter(topK_y)
return votes.most_common(1)[0][0]
def __repr__(self):
return "kNN(k=%d)" %self.k
当我们写完定义好自己的kNN代码之后，可以在jupyter notebook中使用魔法命令进行调用：
from math import sqrt
%run C:\Users\Administrator\Desktop\knnp\kNN0
knn_clf = kNNClassifier(k=6)
knn_clf.fit(X_train,y_train)
X_predict = x.reshape(1,-1)
y_predict =knn_clf.predict(X_predict)
y_predict
输出
array([1])
sklearn中的kNN
代码
对于机器学习来说，其流程是：训练数据集 -> 机器学习算法 -fit-> 模型 输入样例 -> 模型 -predict-> 输出结果
我们之前说过，kNN算法没有模型，模型其实就是训练数据集，predict的过程就是求k近邻的过程。
我们使用sklearn中已经封装好的kNN库。你可以看到使用有多么简单。
from sklearn.neighbors import KNeighborsClassifier
#创建kNN_classifier实例kNN
kNN_classifier = KNeighborsClassifier(n_neighbors = 6)
#kNN_classifier做一遍fit(拟合)的过程，没有返回值，模型就存储在kNN_classifier实例中
kNN_classifier.fit(X_train,y_train)
#kNN进行预测predict,需要传入一个矩阵，而不能是一个数组。reshape()成一个二维数组，第一个参数是1表示只有一个数据，
#第二个参数是-1，numpy自动决定第二维度有多少
y_predict = kNN_classifier.predict(x.reshape(1,-1))
y_predict
输出
array([1])
在kNN_classifier.fit(X_train, y_train)这行代码后其实会有一个输出：
kNN_classifier.fit(X_train, y_train)
输出
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
metric_params=None, n_jobs=None, n_neighbors=6, p=2,
weights='uniform')
方法
对于KNeighborsClassifier的方法：
image.png
水仙花分类
读取相应的库
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import numpy as np
读取数据框X,y
iris = datasets.load_iris()
X = iris.data
y = iris.target
把数据分成训练数据和测试数据
X_train,X_test,y_train,y_test = train_test_split(X,y,random_state = 20)
构建KNN模型，K值为3，并做训练
clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(X_train,y_train)
predicty = clf.predict(X_test)
计算准确率
from sklearn.metrics import accuracy_score
correct = np.count_nonzero((predicty==y_test)==True)
print("Accuracy is:%.3f"%(correct/len(X_test)))
#accuracy_score(y_test,predicty)
输出Accuracy is:0.921
本文主要参照微信公众号 术东居士 的机器学习的敲门砖：kNN算法（上）
网友评论