K近邻算法和线性回归的幕后细节

1. 写在前面

今天开始， 开始尝试进行机器学习算法的一些查缺补漏知识的整理， 主要还是之前没有注意的一些点吧， 这次主要是KNN算法和线性回归的两个点， 这两个算法或许在大家看来或许都是两个比较简单的算法， 但是这次又偶然学习了一次， 发现还是有些知识是被忽略掉的， 所以借这个机会进行补充。 首先是KNN算法的kd树部分， 这里会通过一个具体的例子来说一下kd树的原理， 之前写白话KNN的时候， 这块知识是略掉的， 但感觉还是有必要了解一下这个东西的， 因为毕竟KNN我们知道， 如果拿一个新样本来判断它属于哪个类， 我们可是要计算它与其他样本点所有的距离， 这在样本非常多的时候时间复杂度可是很可怕的， 所以kd树的这种数据结构有利于降低一下时间复杂度， 差不多能从O(n)降到O(logn)， 也是kd树要引入的原因， 后面会通过一个例子来看看kd树的构建和搜索k近邻点的方式， 就知道为啥它能降低时间复杂度了。

然后就是线性回归， 这个之前也是忽略了一个点， 就是损失函数， 我们知道线性回归的损失函数就是平方差损失， 因为这个可以衡量预测值和真实值之间的差距嘛， 那既然是差距， 为啥不用别的差损失单单选定了平方差呢？ 其实这个损失函数是由基于一个误差项的假设推导出来的， 这里会补充一下。 所以这两个小细节希望能对这两个简单的算法加深理解吧。

大纲如下

• KNN的kd树
• 线性回归的概率理解

2. KNN的kd树

KNN算法的重点在于找出K个最近邻的点， 在寻找过程中我们其实有两种方式进行选择：

1. 蛮力实现
   这个方法很简单， 就是计算出待测样本到所有训练样本的距离， 然后选择最小的k个距离即可得到k个最近邻点， 这个方法样本数据少的时候， 还可以， 但是训练集很大的时候， 计算非常耗时，其实是不太可取的。所以在这里也能看出学习算法的重要性了， 有时候学完了理论是没法在实际应用中用的， 实际工程中还需要考虑各种最优化的策略呢， 比如第二种方式
2. KD Tree
   这个算法中， 首先是对训练数据进行建模， 构造出一个KD树来， 然后再根据构建好的Kd树来获取近邻样本的数据， 这个方式是KNN算法中用于快速寻找近邻的一种方式， 会降低蛮力实现的复杂度。

这里主要是拿一个例子来看一下如何构建Kd树以及如何寻找近邻点， 至于kd树的理论可以参考后面给出的链接， 那里面说的比较详细。 说白了， kd树就可以看成是多维的二叉搜索树。

构造kd树的方式很简单， 首先我们从构建根节点开始。 两个原则：

• 选维度进行分裂（方差最大原则)
• 依据方差最大选好了维度， 从该维度的哪个点去分割呢？ 中位数，这样才平衡。

具体步骤如下：这里先放一个图比较好理解：

1. 构建根节点， 通过计算, x(1)的方差大，此时的切分维度x(1)，上点集合在x(1)维度下从小到大排序(2,3), (4,7). (5, 4), (7, 2), (8, 1), (9, 6)； 中值为（7, 2)。
   （注：2,4,5,7,8,9在数学中的中值为(5 + 7)/2=6，但因该算法的中值需在点集合之内，所以本文中值计算用的len(points)//2=3, points[3]=(7,2)）
2. (2,3)，(4,7)，(5,4)挂在(7,2)节点的左子树，(8,1)，(9,6)挂在(7,2)节点的右子树。
3. 构建(7,2)节点的左子树时，点集合(2,3)，(4,7)，(5,4)此时的切分维度为x(2)，这三点
   按照x(2)维度从小到大排序(2, 3), (5, 4), (4, 7)，中值为(5,4)作为分割平面，(2,3)挂在
   其左子树，(4,7)挂在其右子树。
4. 构建(7,2)节点的右子树， 点集合(8,1), (9,6)的分割维度x(2), points[1]=(9, 6)作为分割
   平面， (8,1)挂在其左子树。至此k-d tree构建完成。

构建kd树的过程是对一个平面或者空间进行逐步划分的过程：

我们到这里或许会有疑问， 这个东西干啥用呢？ 我们拿一个样本来尝试搜索它的最近邻：

拿这个(3,5)点来看， 我们如果想搜索它的k近邻， 首先要找到包含目标点的叶子节点， 以此节点作为“当前最近点”， 这个点的话，我们先从根节点开始(7,2), 第一个维度3<7, 可以断定(3,5)在根节点的左子树上， 然后到了左子树的根节点(5,4)， 第二个维度5>4， 可以断定在(5,4)的右子树上， (5,4)的右子树只有一个节点(4,7)， 此时维度也比较完毕了， 那么就先假定(4,7)这个点为(3,5)的最近邻节点，这时候就出现了第一个红圆。

然后递归的向上回退， 即回到(4,7)的父节点(5,4)上面，因为我这个点只是在(4,7)那个区域， 但具体在什么位置不知道， 所以就可以算一下与(4,7)的父节点(5,4)有多远，如果发现离父节点更近一些， 就会认为这个父节点是离(3,5)最近的节点。 果然， (3,5)离得(5,4)近一些， 这时候， 最近邻节点更新成(5,4)， 出现了绿色的那个圆。

这时候， 我们得考虑一下， 因为父节点(5,4)把左边的区域化成了两块， (4,7)是(5,4)的一个子节点， 这时候我们需要检查(5,4)的另一个子节点里面是不是还有离着目标点更近的点， 具体方法就是看看那个绿色的圆是否已经和另一个子节点对应的区域相交， 如果相交之后， 就有可能在另一个子节点对应区域里面有离着目标点最近的， 这里相交了， 所以这时候移动到父节点的另一个子节点， 也就是(2,3)上。 计算这个点和目标点的距离， 发现比父节点的距离近， 那么就更新最近邻节点， 出现了蓝色的圆。如果不想交， 那么就再去找父节点(5,4)的父节点(7,2)， 这个点已经是根节点了， 然后再看一下当前的蓝色圆是否与(7,2)的另一个子节点的区域是否相交， 发现不相交了， 这样找到了最近的节点是(2,3)。 具体过程是下面这个图：


下面看一个更加复杂的例子：这个例子之所以说是复杂， 是因为与根节点的另一个节点所在的区域也相交了。

简单的过一遍这个过程， 首先S认为D是它的最近邻节点， 那么就以SD为半径画个圆， 然后回退到D的父节点B， 发现BS距离在圆之外， 且圆与B的另一个子节点所在区域也没有相交， 于是回退到B的父节点A， A是根节点， 另一个节点是C所在区域， 发现圆与C所在区域有相交， 于是到了C， 再看C里面有两个子节点G和E， 计算了一下， 就找到了最近点E。

下面分析一下kd树的时间复杂度， 我们发现， kd树的搜索是沿着树的高度直上直下进行搜索比较的， 这样，最后的搜索时间复杂度就和树的高度有关了， 之所以我们要尽可能的建立平衡的二叉树(找每一个维度中位数所在的样本)， 就是为了能让树的高度小一些， 这时候， 能把搜索效率提到最高， n个节点的话， 如果建成平衡二叉树的话， 差不多时间复杂度由$O(n)$提到$O(logn)$。

3. 线性回归的概率理解

线性回归我们肯定是很熟悉了， 给定一批数据$(Y_i,X_{i1},X_{i2},...,X_{ip})$， 模型是

$$Y=X\beta +\epsilon$$
这里采用了向量化的表示方法， $\beta$里面就是那些参数了， 我们喜欢称之为$W$， 而这里的$\epsilon$就是误差项。 我们的误差函数往往定义成下面这个样子：
$$J(\beta )=\Vert X\beta -Y{\Vert }^2$$
也就是平方差损失。 我们往往通过最小二乘法，就可以得到最终$\beta$的解析解：
$$\hat{\beta }={\left(X^{T}X\right)}^{-1}{X}^{T}Y$$

但是上面有个细节，就是为啥误差函数要定义成平方差损失呢？ 这个问题之前没有研究过， 这次学习看到了， 所以整理下来吧， 这个误差函数其实是基于误差项的一个假设进行推导出来的。

我们知道， 对于每个样本来说， 线性回归的公式可以写成：
$$y^i={\beta }^T{x}^i+{\epsilon }^i$$

其中我们是假设这里的误差项服从标准正态的， 也就是$\epsilon \sim N(0,{\sigma }^2)$, 这时候就有
$$p({\epsilon }^i)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{{{\epsilon }^i}^2}{2{\sigma }^2}}$$
这时候， 如果把${\epsilon }^i$用上面等式替换掉, 就会得到：
$$P\left(y^i\mid x^i,\beta ,\sigma \right)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{\frac{-{\left(y^i-{\beta }^T{x}^i\right)}^2}{2{\sigma }^2}}$$
这时候， 我们如果想让$y_i$与${\beta }^T{x}^i$非常接近， 那么我们就要最大化上面的这个公式， 找那个最高点， 也就是均值所在处。 即我们需要$MaximumLikelihood:P\left(y^i\mid x^i,\beta ,\sigma \right)$， 如果是针对所有样本， 我们使用连乘$$MaximumLikelihood:{\left(\frac{1}{\sigma \sqrt{2\pi }}\right)}^n\prod _{i=1}^n{e}^{\frac{-{\left(y^i-{\beta }^T{x}^i\right)}^2}{2{\sigma }^2}}$$
我们用log转成加法运算：
log ⁡ [ P ( D ∣ β , σ ) ] = l o g { ( 1 σ 2 π ) n ∏ i = 1 n e − ( y i − β T x i ) 2 2 σ 2 } \log [P(D \mid \beta, \sigma)]=log\{\left(\frac{1}{\sigma \sqrt{2 \pi}}\right)^{n} \prod_{i=1}^{n} e^{\frac{-\left(y^{i}-\beta^{T} x^{i}\right)^{2}}{2 \sigma^{2}}}\} log[P(D∣β,σ)]=log{(σ2π ​1​)ni=1∏n​e2σ2−(yi−βTxi)2​}

下面换成加法运算：
$$\arg \underset{w}{\max }\left\{{\left(\frac{1}{\sigma \sqrt{2\pi }}\right)}^n\prod _{i=1}^n{e}^{\frac{-{\left(y^i-{\beta }^T{x}^i\right)}^2}{2{\sigma }^2}}\right\}=\arg \underset{w}{\max }\left(\log {\left[\left(\frac{1}{\sigma \sqrt{2\pi }}\right)\right)}^n\right]+\sum _{i=1}^n\frac{-{\left(y^i-{\beta }^T{x}^i\right)}^2}{2{\sigma }^2}$$
由于$log$的那块和$2{\sigma }^2$都是常数， 我们可以直接去掉， 就变成了：
$$\underset{w}{\mathrm{argmax}}\sum _{i=1}^n-{\left(y^i-{\beta }^T{x}^i\right)}^2$$
我们把负号去掉， 就相当于最小化了， 就得到了最终的形式：
$$\underset{w}{\mathrm{argmin}}\sum _{i=1}^n{\left(y^i-{\beta }^T{x}^i\right)}^2$$

这才得到了最终的损失函数的形式。 可以发现也不是随便定义的吧。

有了损失函数， 在推导一下解析解
$$\mathcal{L}(\beta )=\Vert X\beta -Y{\Vert }^2=(X\beta -Y{)}^T(X\beta -Y)=Y^{T}Y-Y^{T}X\beta -{\beta }^T{X}^{T}Y+{\beta }^T{X}^{T}X\beta$$
我们对$\beta$求梯度
$${\nabla }_{\beta }\mathcal{L}(\beta )={\nabla }_{\beta }\left(Y^{T}Y-Y^{T}X\beta -{\beta }^T{X}^{T}Y+{\beta }^T{X}^{T}X\beta \right)=0-X^{T}Y-X^{T}Y+2X^{T}X\beta =2X^{T}X\beta -2X^{T}Y$$
令梯度等于0， 我们就可以得到$2X^{T}X\beta =2X^{T}Y$， 即推导出$\beta ={\left(X^{T}X\right)}^{-1}{X}^{T}Y$

细节补充好了， 下面是关于线性回归的小总结：

关于线性回归， 先不充到这里吧。

参考：

• 统计学习方法之KNN笔记
• 白话机器学习算法理论+实战之K近邻算法