k近邻算法

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)。
高度数据相关，依赖数据。
预测结果不具有可解释性。
随着维数的增加，“看似相近”的两点之间的距离越来越大。