机器学习-KNN

生命在于折腾,最近入坑机器学习,把python装好,也把语法和特性大致过了一遍。看了下都比较推荐斯坦福的cs231n,所以就决定学习它来作为入坑通道了😄。

安装环境

python

python3和python2区别还是很大的,咱还是用最新的吧

1
brew install python3

sklearn

这是一个通用的机器学习库,相比起来tensorflow应该更偏向定位于深度学习,一步一步来就先把这个装了吧

1
python3 -m pip install scikit-learn

numpy

一个python的科学计算的基础库,提供了多维数组和矩阵的运算。

1
python3 -m pip install numpy

matplotlib

基于python的2D绘图库。

1
python3 -m pip install matplotlib

debug

目前用的IDE是vs code, 已经有插件支持python。装好插件后,配上python3的执行环境以及lint等路径后,我随便找了个例子一跑发现numpy有个地方不对劲。function_base.py(line 4533)在import numpy的时候会抛出AttributeError和RuntimeError, 然后它直接except Exception,每次一debug就会先在那里停个n多次(调试模式打开了stop at uncaught exception),难道父类Exception不行? 机制的我立马想到那我给except了吧。

1
2
3
4
5
+	except (AttributeError, RuntimeError):
+ # 为了vscode别停在这里,当然修改launch.json也行...不过那样就直接针对全部生效了, 但是没用呢!
+ print('catch this err just to avoid vscode stop at uncaught exception')
except Exception:
pass

修改了代码后发现竟然没有用, 跑到插件github上看,发现很多人给出的方案是在lanugh.json文件里加上下面一句话忽略异常

1
2
3
"exceptionHandling": {
"ignore": ["AttributeError", "RuntimeError"]
}

虽然有用,我觉得这样修改全局也不好,所以先暂时取消了uncaught exception功能。

开始Hello World

K最近邻(k-Nearest Neighbor,KNN)分类算法,是最简单的机器学习算法之一。它的理念就是:给定一个数据集,对于新的输入实例,找到与该实例最邻近的k个实例,服从这k个实例属于最多的那个类。所以很明显的,这个算法是一个lazy-learning算法,它并不训练(只是储存训练数据),在分类时耗时。此外,当数据集是连续的时候,还可以用来做回归。显而易见,k值的选取以及距离函数,是影响结果的两个重要因素。

一些概念

闵可夫斯基度量(Minkowski metric)

在sklearn的knn中默认的距离度量标准,在空间$\mathbb{R}^n$给定两个点a和b:

$$X(x_{1}, x_{2}, …, x_{n})\quad And\quad Y(y_{1}, y_{2}, …, y_{n}) \in\mathbb{R}^n $$

这两个点的之间的闵氏距离为:

$$D(X,Y) = \left(\sum_{i=1}^n|x_i-y_i|^{p}\right)^{\frac{1}{p}}$$

当$p = 1$时, 即为曼哈顿距离(Manhattan distance):

$$D(X,Y) = \sum_{i=1}^n|x_i-y_i|$$

当$p = 2$时,即为欧几里得距离(Euclidean distance):

$$D(X,Y) = \sqrt[2]{\sum_{i=1}^n|x_i-y_i|^{2}}$$

之后的例子中我们采用$p = 2$来计算距离。

sk-learn中knn最近距离算法

  • brute: 暴力计算, 对于D维度下的N个数据,其复杂度高达$O(DN^2)$
  • kd_tree: kd树, 是一颗二叉树,它根据切分轴中值切分构造树,其本质就是,如果A点离B点很远,B点离C点很近,那么A点离C点也很远,其复杂度可以降低到$O(DNlogN)$。但是当$D >= 20$后,kd树效率将变低。这里有一篇文章讲解的很清楚(传送门)
  • ball_tree: 为了解决 KD 树在高维上效率低下的问题

关于算法时间复杂度以及如何根据k和选择的说明,sklearn官网有更多介绍(传送门)

numpy

numpy的主要对象ndarray, 是一个同类型元素的多维数组(homogeneous multidimensional array)。在numpy中, dimensions(维度)也称为axes(轴)。

  • 举个栗子:

    [1,2]这个数组只有一个axis,这个axis有两个元素,所以我们说这个axis长度为2.

  • 再举个栗子:

    [[1,2,3],[4,5,6]]这个数组,它有两个axes,第一个axis的长度为2,第二个axis的长度为3,我们可以理解其为一个2 * 3的数组。

接着上面的说,ndarray还有一个重要的属性也就是shape, 是一个表明数组在各个dimension上长度的元组。比如上面两个栗子中,其shape分别为(2,)和(3,2)

knn分类

下面用iris数据集[1]来模拟一次knn分类。虽然iris数据集其实是一个shape(150,4)的数据集,但是我们为了方便直接阉割到shape(150,2), 此外每个点的权重也分为了两种(同权重或距离权重)。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets

n_neighbors = 15 # k为15

iris = datasets.load_iris() # iris数据集 shape(150,4)

X = iris.data[:, :2] # 修改为shape(150, 2), 方便在2维图像上展示撒
y = iris.target # iris数据集的分类, 分为3类

h = .02 # 下面预测用的二维网格坐标点间隔

cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF']) # 预测点三个分类颜色
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF']) # 训练集三个分类颜色(纯深色)

for i, weights in enumerate(['uniform', 'distance']): # 统一权重或者按距离的倒数作为权重

clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
clf.fit(X, y) # 拟合

# 准备边界[x_min, x_max] * [y_min, y_max]的方形
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h)) # 生成对应2维数据网格坐标, h为每个点x,y轴的间隔

Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]) # c_ 等同于 np.r_['-1,2,0', index expression]
Z = Z.reshape(xx.shape) # reshape到meshgrid生成的网格的shape
plt.subplot(2, 1, i + 1)
plt.pcolormesh(xx, yy, Z, cmap=cmap_light) # 平面区域预测颜色

# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold,
edgecolor='k', s=20) # 训练集点的集合
plt.xlim(xx.min(), xx.max()) # 设置x,y轴边缘
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i, weights = '%s')"
% (n_neighbors, weights))

plt.show()

结果如下图所示:

从结果我们其实可以看出来,uniform和distance两种模式得到的区域结果是有差异的,显然是由于邻近点点权重不同引起的。

knn回归

当数据集是连续的情况下,我们也可以利用knn来做regression。下面是一个用knn回归来做正弦函数预测的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import numpy as np
import matplotlib.pyplot as plt
from sklearn import neighbors

np.random.seed(0) #设置个种子
X = np.sort(5 * np.random.rand(50, 1), axis=0) # 测试集, 生成shape(50, 1)的2d array, 然后放大5倍排序第一个数轴

T = np.linspace(0, 5, 500)[:, np.newaxis] # 预测集, 0到5中等距离取500个值, 然后添加新维度变成shape(500, 1)

y = np.sin(X).ravel() # 为x中的值取sin值,然后降维

yT = np.sin(T).ravel() # 预测集应该的真实值

n_neighbors = 5 # k为5

for i, weights in enumerate(['uniform', 'distance']): # distance的情况下, 距离会有权重效应
knn = neighbors.KNeighborsRegressor(n_neighbors, weights)
y_ = knn.fit(X, y).predict(T)
plt.subplot(2, 1, i + 1) # 画个子plot
plt.scatter(X, y, c='k', label='data', marker=".") # 测试集, 黑色点
plt.plot(T, y_, c='g', label='prediction') # 绿色预测线条
plt.plot(T, yT, c='y', label='real') # 真实值应该的线条
plt.axis('tight')
plt.legend()
plt.title("KNeighborsRegressor (k = %i, weights = '%s')" % (n_neighbors,
weights))

plt.show()

结果如下图:

从结果图中可以看出,采用distance作为权重的预测值,更为平滑,也更为贴近实际值。

总结

由于有了三方包,其实代码都很简短,但是每个api都要自己去看一大段解释。另外深深感觉到了python操作数组的方便,并且numpy封装后,由于python允许运算符重载,更是感觉要玩出花了。所以准备开一帖记录下numpy中一些函数概念,以便查阅。


  1. Iris数据集是常用的分类实验数据集,由Fisher, 1936收集整理。Iris也称鸢尾花卉数据集,是一类多重变量分析的数据集。数据集包含150个数据集,分为3类,每类50个数据,每个数据包含4个属性。可通过花萼长度,花萼宽度,花瓣长度,花瓣宽度4个属性预测鸢尾花卉属于(Setosa,Versicolour,Virginica)三个种类中的哪一类。