knn,k-nearest-neighbors分类算法。如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，那么该样本也属于该类别。
knn_basic
在二维平面上随机生成10个点，并将它们标记。
import numpy as np
X_raw=np.random.random((10,2))*10
X_raw
#output
array([[4.75524752, 7.68492413],
[1.02771195, 6.74087649],
[3.78474663, 6.25722252],
[2.92309566, 4.1122721 ],
[5.68056271, 3.92225547],
[6.07938619, 6.77750749],
[6.00401888, 0.25916751],
[7.88214967, 7.13444055],
[6.56220062, 0.32779057],
[0.62898795, 4.84822446]])
y_raw=np.array([1,0,0,0,1,1,1,1,1,0])
使用matplotlib.pyplot绘制散点图
import matplotlib.pyplot as plt
plt.scatter(X_raw[y_raw==0,0],X_raw[y_raw==0,1],color='blue');
plt.scatter(X_raw[y_raw==1,0],X_raw[y_raw==1,1],color='red');
scatter.png
随机生成一个点，判断它应该被分为红色还是蓝色？
new_point=np.random.random((1,2))*10
new_point
#output
array([[2.45171953, 4.66062002]])
使用欧拉距离计算生成的点与之前10个点的距离
from math import sqrt
distances=[sqrt(np.sum((new_point-x)**2)) for x in X_raw]
distances
#output
[3.801664973962094,
2.520965006043233,
2.079928076084269,
0.7231050393363991,
3.31219118928088,
4.200140232259464,
5.656113054968524,
5.967357830013087,
5.972391966101662,
1.8323607262669857]
将存放10个距离值的列表中元素的索引进行排序
index=np.argsort(distances)
index
array([3, 9, 2, 1, 4, 0, 5, 6, 7, 8])
上面数组中第一个数字是3，代表最小元素索引为3，对应distances列表中的第四个元素0.7231........假设找离生成点最近的三个点，那么数组表示与索引为3，9，2的元素最近。
让k=3, 找出对应的标记值
k=3
mark=y_raw[index[:k]]
mark
#output
array([0, 0, 0])
统计标记数量
from collections import Counter
vote=Counter(mark)
vote.most_common(1)[0][0]
#output
0
标记为0的数量最多，所以生成的点归为蓝色部分。knn就是完成类似这样的任务。
从sklearn中加载digits数据集
from sklearn import datasets
digits=datasets.load_digits()
digits.keys()
#output:dict_keys(['data', 'target', 'target_names', 'images', 'DESCR'])
将数据集传给x,分类标签传给y
X=digits.data
y=digits.target
将数据集分成训练集和测试集，其中训练集占80%。这样划分可以知晓模型的准确率。方便调整参数，提高准确率。
使用sklearn中封装好的相关函数
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2)
设置网格参数,权重使用的是distance,k值是在1-10，p值在1-5
param_grid=[
{'weights':['distance'],
'n_neighbors':[i for i in range(1,11)],
'p':[p for p in range(1,6)]}
]
生成分类器
from sklearn.neighbors import KNeighborsClassifier
knn_clf=KNeighborsClassifier()
使用网格搜索，调整参数，然后训练模型
from sklearn.model_selection import GridSearchCV
grid_search=GridSearchCV(knn_clf,param_grid)
%%time
grid_search.fit(X_train,y_train)
得到准确率和相应参数
grid_search.best_score_
#0.9826026443980515
grid_search.best_params_
#{'n_neighbors': 3, 'p': 2, 'weights': 'distance'}
数据归一化
不进行归一化，无法反映每一个特征的重要程度，所以要把数据映射到同一尺度上。
最值归一化：x_scale=(X-X_min)/(X_max-X_min) 适用于分布有明显界限的情况。
均值归一化：x_scale=(X-X_mean)/(std(X))。
knn缺点：
效率低下。如果训练集有m个样本，n个特征，则预测每一个数据需要o(m*n)。
高度数据相关，依赖数据。
预测结果不具有可解释性。
随着维数的增加，“看似相近”的两点之间的距离越来越大。
