机器学习02 k近邻法（通俗分析理解）
一、 实验内容
（1） 问题描述
k近邻法（KNN）是一种基本分类与回归算法。其核心思想就是对新的输入实例，在训练数据中找到与该实例最邻近的k个实例，然后少数服从多数，归属于多数属于的类。
（2） 数据集描述
数据集的第一列数据为带划分样本数据的结果（标签），除了第一列数据之外的数据为样本数据。该数据集共有42000个样本数据，每个样本由784个数据组成，数据类型为整型
（3） 实验环境（软硬件）
硬件：联想小新air13
软件：Windows10操作系统；Python 3.7；Pycharm Community
二、算法原理
其实这个算法原理非常之简单，取之于一个非常简单的思想，比如说咱输入好多周氏张氏王氏李氏列祖列宗的照片，然后再输入一个后辈的照片，咱怎么看这个孩子是哪家的呢，当然是看他和谁像啦，找出和他最像的k个人，如果这些人都是周氏，就是周的概率大些咯。道理咱都懂，落在代码上咋实现呢，咋告诉机器这个规则呢？
咱抽象出了这个思想的核心基本要素：距离度量（如何判断相似），k值选择，还有分类决策规则（怎么科学合理地得出结论）
1、距离度量
咋科学合理地判断相似度呢？你总得看眼睛像不像鼻子像不像嘴巴像不像，咱的输入训练集有n维的特征空间，那我们就要结合n维来看，同一维上数值越接近在这一维度就越像，像的多的维度越多总体就越像。就使用距离啦，我喜欢传统的欧氏距离，当然其他的距离也可以，定义为
L
p
(
x
i
,
x
j
)
=
(
∑
l
=
1
n
∣
x
i
(
l
)
?
x
j
(
l
)
∣
p
)
1
p
L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}
Lp?(xi?,xj?)=(l=1∑n?∣xi(l)??xj(l)?∣p)p1?
p>=1,p=2,欧氏距离，p=1，曼哈顿距离，p=无穷大，各个坐标距离最大值。距离越小，两个样本之间就越像！
2、k值选择
k值的选择是个好问题，k肯定不能取所有人，k也不能只取一个人，万一碰巧有个人和他最像但他和他不是一个祖辈，这就很容易出错呀，当然还是有一个比较小的值是最好的，通常采用交叉验证法来选取最优的k值，就是将原始输入的训练集分出一部分测试集，然后不同的k带进去训练，训练出结果模型参数后哪个模型测试集准确率高就选哪个。
3、分类决策
在你选出的k个人里，k个人中哪个族的人多就选哪个族。意思浅显明了，但从数学角度，你得有个科学合理的说法吧。
假如正确的分类为c_j,N_k(x)是你挑出的k个样本点，那你的误分类率
1
k
∑
x
i
∈
N
k
(
x
)
I
(
y
i
≠
c
j
)
=
1
?
1
k
∑
x
i
∈
N
k
(
x
)
I
(
y
i
=
c
j
)
\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j)
k1?xi?∈Nk?(x)∑?I(yi??=cj?)=1?k1?xi?∈Nk?(x)∑?I(yi?=cj?)
要使误分类率最小，则经验风险最小，使
∑
x
i
∈
N
k
(
x
)
I
(
y
i
=
c
j
)
\sum_{x_i\in N_k(x)}I(y_i=c_j)
∑xi?∈Nk?(x)?I(yi?=cj?)最大，即多数投票
对了,
I
=
{
1
?????
(
y
i
=
c
j
)
0
?????
(
y
i
≠
c
j
)
I=\begin{cases}1\,\,\,\,\,(y_i=c_j)\\0\,\,\,\,\,(y_i \neq c_j) \end{cases}
I={1(yi?=cj?)0(yi??=cj?)?
4、kd树搜索（以最近邻为例）
当我们训练集特别特别多，我们不可能逐一比对，太耗时了，我们应该怎样才能找到最接近的样本呢？（可扩展为K个）
咱想想看，假如咱看人先看眼睛，那咱要构建一棵树，把眼睛最大众最中等的放在树的顶端。
第一排，咱挂上去就因为它是所有类里面从某一维度上看它是最大众脸的，因为它既然最大众那它的参考价值肯定是最小的，比大众脸眼睛大的先放在左边，比大众脸眼睛小的放在右边，
第二看鼻子，然后把在眼睛大的那一类中找到鼻子最一般的放在第二排，然后鼻子比大众脸大的放在右边，比大众脸小的放在左边，眼睛小的也是同理。
然后咱每一个维度挂着挂着挂到最后，发现没人可以挂的时候呢，诶，发现最后一排都是非常特殊的，因为大众的在前面已经被你们挂完了，这时候孩子的照片来了，你先和所有的特殊的比对一下，找到最接近的，把他放在包里，然后顺着那个人的线索往上找。
毕竟那么特殊的人不可能一找就准，但是能给你一个大概的方向，然后你再顺着往上找呀，有点大众的，大众的，非常大众的。突然诶咱看到这个第四排某一个大众的和他真的很像，那咱就把原来那个人丢了，把他装包里。
咱发现诶这个和他很像的人，发现那个人竟然比那个原来特殊的人更像了，那肯定是某一维度更像了，咱从咱爬上来那一枝没找到，咱就从咱发现这个最像的节点，从另一枝搜下一排有没有人更像，诶如果有，继续放包里，然后从这个点继续往下搜，直到搜到最像的点，停住。
如果没有或者停住了，那我们继续一步步回退往上搜，一直搜到根节点为止，说明我们没有错过漏过啥重要消息。
官方话语：
输入：已构造的kd树；目标点x；
输出：x的最近邻。
（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若 目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
（2）以此叶结点为“当前最近点”。
（3）递归地向上回退，在每个结点进行以下操作：
? （a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前 最近点”。
? （b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以 目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。
（4）当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。
三、代码分析
暴力搜索！
import pandas as pd
import numpy as np
import cv2
import random
import time
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
def get_hog_features(trainset):
features = []
hog = cv2.HOGDescriptor('hog.xml')
for img in trainset:
img = np.reshape(img,(28,28))
cv_img = img.astype(np.uint8)
hog_feature = hog.compute(cv_img)
features.append(hog_feature)
features = np.array(features)
features = np.reshape(features,(-1,324))
return features
def Predict(testset,trainset,train_labels):
predict = []
count = 0
for test_vec in testset:
print (count)
count += 1
knn_list = []
max_index = -1
max_dist = 0
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)
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]
if dist < max_dist:
knn_list[max_index] = (dist,label)
max_index = -1
max_dist = 0
result=np.zeros((k,1))
for i in range(k):
(dist,label)=knn_list[i]
result[label]=result[label]+1;
single_predict=np.argmax(result)
print(single_predict)
predict.append(single_predict)
return np.array(predict)
k = 10
if __name__ == '__main__':
print ('Start read data')
time_1 = time.time()
raw_data = pd.read_csv('train_binary.csv',header=0)
data = raw_data.values
imgs = data[0::,1::]
labels = data[::,0]
features = get_hog_features(imgs)
train_features, test_features, train_labels, test_labels = train_test_split(features[0:4000,:], labels[0:4000], test_size=0.1, random_state=23323)
print (test_features.shape)
time_2 = time.time()
print('read data cost ',time_2 - time_1,' second','\n')
print ('Start training')
print ('knn do not need to train')
time_3 = time.time()
print ('training cost ',time_3 - time_2,' second','\n')
print ('Start predicting')
test_predict = Predict(test_features,train_features,train_labels)
time_4 = time.time()
print ('predicting cost ',time_4 - time_3,' second','\n')
score = accuracy_score(test_labels,test_predict)
print ("The accruacy socre is ", score)
|