统计学习方法——修炼学习笔记3：k近邻法
一、KNN算法
基本模型：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例。这k个实例的多数属于某个类，就把输入实例分为这个类。
KNN没有显式的学习过程。
KNN使用的模型实际上对应于特征空间的划分。特征空间中，对每个训练实例点xi，距离该点比其它点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例拥有一个单元。所有的训练实例点的单元构成对特征空间的一个划分。
如下图所示。
image.png
二、基本三要素
KNN模型由三个基本要素——距离度量，k值的选择，分类决策规则决定。
当三要素和训练集确定后，对任何一个新的输入实例，它所属的类唯一地确定。
KNN三要素之1——距离度量
由不同的距离度量所确定的最近邻点是不同的。
KNN的特征空间一般是n维实数向量空间R^n，使用的距离是欧氏距离。但也可以是其他距离，如更一般的Lp距离。
设xi为第i个样本，n维向量，
image.png
则
image.png
p=2时称为欧式距离，p=1称为曼哈顿距离。
下图是二维空间中，与原点的Lp距离为1的图形。
image.png
image.png
image.png
KNN三要素之2——K值选择
K值的选择会对KNN结果产生重大影响
-
选择较小的K值：
如果选择较小的K值，相当于用较小的邻域中的训练实例进行预测，只有与输入实例较近的训练实例才会对预测结果起作用。“学习”的近似误差会减小。
缺点是“学习”的估计误差会增大，预测结果对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。
K值的减小意味着整体模型变得复杂，容易发生过拟合。
-
选择较大的K值：
如果选择较大的K值，相当于用较大邻域中的训练实例进行预测。其优点是减小学习的估计误差，缺点是近似误差会增大。这时离输入实例较远的训练实例起预测作用，使预测发生错误。
K值的增大意味着整体模型变得简单。K=N时，无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类，这时模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
在应用中：
K值一般取一个比较小的数值，通常采用交叉验证法来选取最优的K值。
KNN三要素之3——分类决策规则
KNN的分类决策规则往往是多数表决，即由输入实例的K个邻近的训练实例中的多数类决定输入实例的类。
image.png
三、KNN的实现：kd树
KNN最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高KNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。
具体方法很多，下面介绍其中的kd树方法。
构造kd树
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。
【算法】构造平衡kd树
image.png
image.png
image.png
搜索kd树
利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。这里以最近邻为例加以叙述。
【算法】用kd树的最近邻搜索
输入：已构造的kd树；目标点x；
输出：x的最近邻
（1）从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则左移，否则右移，直到子结点为叶结点。
（2）以此叶结点为“当前最近点”。
（3）递归向上回退，在每个结点进行以下操作：
（a）若该结点保存的实例点比“当前最近点”离目标点更近，则以该实例点为“当前最近点”。
（b）检查另一子结点对应的区域是否与“以目标点为球心，以目标前与‘当前最近点’的距离为半径的超球体”相交。
如果相交，可能在另一子结点对应的区域内存在距离目标点更近的点，移动到另一结点，递归搜索。
如果不相交，向上回退。
（4）回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。
image.png
【代码】
三个基本要素：k值的选择、距离度量及分类决策规则
测试数据集：train.csv
实现代码：
# encoding=utf-8
import pandas as pd
import numpy as np
import time
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
def Predict(testset, trainset, train_labels):
predict = [] # 保存测试集预测到的label，并返回
count = 0 # 当前测试数据为第count个
for test_vec in testset:
# 输出当前运行的测试用例坐标，用于测试
count += 1
print("the number of %d is predicting..."%count)
knn_list = [] # 当前k个最近邻居
max_index = -1 # 当前k个最近邻居中距离最远点的坐标
max_dist = 0 # 当前k个最近邻居中距离最远点的距离
# 初始化knn_list,将前k个点的距离放入knn_list中
for i in range(k):
label = train_labels[i]
train_vec = trainset[i]
dist = np.linalg.norm(train_vec - test_vec) # 计算两个点的欧氏距离
knn_list.append((dist, label))
# 剩下的点
for i in range(k, len(train_labels)):
label = train_labels[i]
train_vec = trainset[i]
dist = np.linalg.norm(train_vec - test_vec) # 计算两个点的欧氏距离
# 寻找k个邻近点中距离最远的点
if max_index < 0:
for j in range(k):
if max_dist < knn_list[j][0]:
max_index = j
max_dist = knn_list[max_index][0]
# 如果当前k个最近邻中存在点距离比当前点距离远，则替换
if dist < max_dist:
knn_list[max_index] = (dist, label)
max_index = -1
max_dist = 0
# 统计选票
class_total = k
class_count = [0 for i in range(class_total)]
for dist, label in knn_list:
class_count[label] += 1
# 找出最大选票
mmax = max(class_count)
# 找出最大选票标签
for i in range(class_total):
if mmax == class_count[i]:
predict.append(i)
break
return np.array(predict)
k = 10 # 选取k值
if __name__ == '__main__':
print("Start read data")
time_1 = time.time()
raw_data = pd.read_csv('../data/train.csv', header=0) # 读取csv数据
data = raw_data.values
features = data[::, 1::]
labels = data[::, 0]
# 避免过拟合，采用交叉验证，随机选取33%数据作为测试集，剩余为训练集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
time_2 = time.time()
print('read data cost %f seconds' % (time_2 - time_1))
print('Start training')
print('knn need not train')
time_3 = time.time()
print('training cost %f seconds' % (time_3 - time_2))
print('Start predicting')
test_predict = Predict(test_features, train_features, train_labels)
time_4 = time.time()
print('predicting cost %f seconds' % (time_4 - time_3))
score = accuracy_score(test_labels, test_predict)
print("The accruacy score is %f" % score)
实现代码(用sklearn实现)：
# encoding=utf-8
import pandas as pd
import numpy as np
import time
from sklearn.neighbors import KNeighborsClassifier
from sklearn.cross_validation import train_test_split
if __name__ == '__main__':
print("Start read data...")
time_1 = time.time()
raw_data = pd.read_csv('../data/train.csv', header=0) # 读取csv数据
data = raw_data.values
features = data[::, 1::]
labels = data[::, 0]
# 随机选取33%数据作为测试集，剩余为训练集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
time_2 = time.time()
print('read data cost %f seconds' % (time_2 - time_1))
print('Start training...')
neigh = KNeighborsClassifier(n_neighbors=10)
neigh.fit(train_features, train_labels)
time_3 = time.time()
print('training cost %f seconds...' % (time_3 - time_2))
print('Start predicting...')
test_predict = neigh.predict(test_features)
time_4 = time.time()
print('predicting cost %f seconds' % (time_4 - time_3))
score = neigh.score(test_features, test_labels)
print("The accruacy score is %f" % score)
【总结】
工作原理：
- 存在一个样本数据集合（训练样本集），并且样本集中每个数据都存在标签，即样本集中每个数据与所属分类的对应关系。
- 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
- 一般来说，只选择样本数据集中前N个最相似的数据。k一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类
K近邻算法的一般流程：
- 收集数据：可以使用任何方法
- 准备数据：距离计算所需要的数值，最后是结构化- 的数据格式
- 分析数据：可以使用任何方法
- 训练算法：（此步骤KNN）中不适用
- 测试算法：计算错误率
- 使用算法：首先要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对将计算出的分类执行后续的处理
注：统计学习方法——修炼学习笔记系列参考学习资料：
《统计学习方法》第2版 李航
补充学习资料：
https://www.jianshu.com/p/11d0ee7d9e5f 李威威学习笔记
https://blog.csdn.net/weixin_43374508/article/details/102784079 城序猿
代码学习资料：https://github.com/WenDesi/lihang_book_algorithm
