KNN
KNN(K-Nearest Neighbor)是最简单的机器学习算法之一，可以用于分类和回归，是一种监督学习算法。它的思路是这样，如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。也就是说，该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN用于分类
- 计算待分类点与已知类别的点之间的距离
- 按照距离递增次序排序
- 选取与待分类点距离最小的K个点
- 确定前K个点所在类别的出现次数
- 返回前K个点出现次数最高的类别作为待分类点的预测分类
KNN回归预测
回归中，一般采用平均值法或者加权平均值法
平均值法： 每个邻近样本的权重是一样的，最终预测的结果为所有邻近样本目标属性值的均值
加权平均值法：一般采用权重和距离成反比的方式计算
KNN算法要注意的问题
无论是分类还是回归，KNN算法的几个关键点：
- 算法超参数K
- 距离度量，特征空间中样本点的距离是样本点间相似程度的反映
- 分类决策规则，少数服从多数。
算法超参数K
如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有输入实例较近的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，K值得减小就意味着整体模型非常复杂，容易发生过拟合。
如果选择较大的K值，就相当于用较大邻域中的训练实例进行预测，其实优点是减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的训练实例也会起预测作用，使预测发生错误，k值的增大就意味着整体的模型变得简单，容易发生欠拟合。可以假定极端条件K=N，那么无论输入实例是什么，都将简单的预测它属于训练实例中最多的类。这时，模型过于简单，完全忽略训练中的大量有用信息，是不可取的。
在应用中，通常采用交叉验证法来选择最优K值。从上面的分析也可以知道，一般K值取得比较小。我们会选取K值在较小的范围，同时在验证集上准确率最高的那一个确定为最终的算法超参数K。
距离度量
常用的距离有三种，分别为曼哈顿距离、欧式距离和闵可夫斯基距离
KNN的优缺点
优点：
1）算法简单，理论成熟，既可以用来做分类也可以用来做回归。
2）可用于非线性分类。
3）没有明显的训练过程，而是在程序开始运行时，把数据集加载到内存后，不需要进行训练，直接进行预测，所以训练时间复杂度为0。
4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合。
5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况。
缺点：
1）需要算每个测试点与训练集的距离，当训练集较大时，计算量相当大，时间复杂度高，特别是特征数量比较大的时候。
2）需要大量的内存，空间复杂度高。
3）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少），对稀有类别的预测准确度低。
4）是lazy learning方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。
实战
'''
数据集：Mnist
训练集数量：60000
测试集数量：10000（实际使用：10）可更改
'''
import time
import numpy as np
import sys
import os
parent_path=os.path.dirname(os.path.dirname(sys.argv[0]))
sys.path.append(parent_path)
from torchvision.datasets.mnist import MNIST
from torch.utils.data import DataLoader
from torchvision import datasets
import torchvision
import torchvision.transforms as transforms
class KNN:
def __init__(self, x_train, y_train, x_test, y_test, k):
'''
Args:
x_train [Array]: 训练集数据
y_train [Array]: 训练集标签
x_test [Array]: 测试集数据
y_test [Array]: 测试集标签
k [int]: k of kNN
'''
self.x_train, self.y_train = x_train, y_train
self.x_test, self.y_test = x_test, y_test
self.x_train_mat, self.x_test_mat = np.mat(
self.x_train), np.mat(self.x_test)
self.y_train_mat, self.y_test_mat = np.mat(
self.y_test).T, np.mat(self.y_test).T
self.k = k
def _calc_dist(self, x1, x2):
'''计算两个样本点向量之间的距离,使用的是欧氏距离
:param x1:向量1
:param x2:向量2
:return: 向量之间的欧式距离
'''
return np.sqrt(np.sum(np.square(x1 - x2)))
def _get_k_nearest(self,x):
'''
预测样本x的标记。
获取方式通过找到与样本x最近的topK个点，并查看它们的标签。
查找里面占某类标签最多的那类标签
:param trainDataMat:训练集数据集
:param trainLabelMat:训练集标签集
:param x:待预测的样本x
:param topK:选择参考最邻近样本的数目（样本数目的选择关系到正确率，详看3.2.3 K值的选择）
:return:预测的标记
'''
dist_list=[0]* len(self.x_train_mat)
for i in range( len(self.x_train_mat)):
x0 = self.x_train_mat[i]
dist_list[i] = self._calc_dist(x0, x)
k_nearest_index = np.argsort(np.array(dist_list))[:self.k]
return k_nearest_index
def _predict_y(self,k_nearest_index):
label_list=[0] * 10
for index in k_nearest_index:
one_hot_label=self.y_train[index]
number_label=np.argmax(one_hot_label)
label_list[number_label] += 1
y_predict=label_list.index(max(label_list))
return y_predict
def test(self,n_test=10):
'''
测试正确率
:param: n_test: 待测试的样本数
:return: 正确率
'''
print('start test')
error_count = 0
for i in range(n_test):
print('test %d:%d' % (i, n_test))
x = self.x_test_mat[i]
k_nearest_index=self._get_k_nearest(x)
y=self._predict_y(k_nearest_index)
if y != np.argmax(self.y_test[i]):
error_count += 1
print("accuracy=",1 - (error_count /(i+1)))
return 1 - (error_count / n_test)
if __name__ == "__main__":
k=1
start = time.time()
train_dataset = datasets.MNIST(root = '../datasets', train = True,transform = transforms.ToTensor(), download = True)
test_dataset = datasets.MNIST(root = '../datasets', train = False, transform = transforms.ToTensor(), download = True)
train_loader = DataLoader(dataset=train_dataset, batch_size=60000, shuffle=True)
test_loader = DataLoader(dataset=test_dataset, batch_size=1000, shuffle=True)
x_train,y_train = next(iter(train_loader))
x_test,y_test = next(iter(test_loader))
x_train = x_train.squeeze(1).view(60000,-1)
x_test = x_test.squeeze(1).view(1000,-1)
model=KNN( x_train, y_train, x_test, y_test,k)
accur=model.test()
end = time.time()
print("total acc:",accur)
print('time span:', end - start)
start test
test 0:10
accuracy= 1.0
test 1:10
accuracy= 1.0
test 2:10
accuracy= 1.0
test 3:10
accuracy= 1.0
test 4:10
accuracy= 1.0
test 5:10
accuracy= 1.0
test 6:10
accuracy= 1.0
test 7:10
accuracy= 1.0
test 8:10
accuracy= 1.0
test 9:10
accuracy= 1.0
total acc: 1.0
time span: 17.0129714012146
使用sklearn
- 将数据集分割成测试数据集和训练数据集
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test =train_test_split(X,y)
- 创建一个KNeighborsClassifier 对象
from sklearn.neighbors import KNeighborsClassifier
knn= KNeighborsClassifier()
- 使用KNeighborsClassifier 对象进行fit创建出模型，得出分类准确度
knn.fit(X_train,y_train)
knn.score(X_test,y_test)
- 使用模型预测测试集
y_predict = knn.predict(X_test)
KNN的初始函数(构造函数)的参数和默认参数是(n_neighbors=5,weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’,metric_params=None, n_jobs=1, **kwargs)
[n_neighbors] 也就是K，默认参数为5。
[weights] str参数，为了降低k值的影响所设置的权重值，即每个拥有投票权的样本是按什么比重投票，'uniform'表示等比重投票，'distance'表示按距离 反比投票，[callable]表示自己定义的一个函数，这个函数接收一个距离数组，返回一个权值数组。默认参数为‘uniform’。
[algorithm] str参数，即内部采用什么数据结构实现。有以下几种选择参：'ball_tree':球树、'kd_tree':kd树、'brute':暴力搜索、'auto':自动根据数据的类型和结构选择合适的算法。默认情况下是‘auto’。暴力搜索就不用说了大家都知道。具体前两种树型数据结构哪种好视情况而定。KD树是依次对K维坐标轴，以中值切分构造的树，每一个节点是一个超矩形，在维数小于20时效率最高。ball tree 是为了克服KD树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每一个节点是一个超球体。一般低维数据用kd_tree速度快，用ball_tree相对较慢。超过20维之后的高维数据用kd_tree效果反而不佳，而ball_tree效果要好，具体构造过程及优劣势的理论大家有兴趣可以去具体学习。
[leaf_size] int参数，基于以上介绍的算法，此参数给出了kd_tree或者ball_tree叶节点规模，叶节点的不同规模会影响数的构造和搜索速度，同样会影响用于储存树的内存的大小。具体最优规模是多少视情况而定。
[matric] str或者距离度量对象，即怎样度量距离，前面有具体介绍。默认minkowski。
[p] int参数，就是以上闵氏距离各种不同的距离参数，默认为2，即欧氏距离。p=1代表曼哈顿距离等等。
[metric_params] 距离度量函数的额外关键字参数，一般不用管，默认为None。
[n_jobs] int参数，指并行计算的线程数量，默认为1表示一个线程，为-1的话表示为CPU的内核数，也可以指定为其他数量的线程，这里不是很追求速度的话不用管，需要用到的话去看看多线程。
|