今天开始， 开始尝试进行机器学习算法的一些查缺补漏知识的整理， 主要还是之前没有注意的一些点吧， 这次主要是KNN算法和线性回归的两个点， 这两个算法或许在大家看来或许都是两个比较简单的算法， 但是这次又偶然学习了一次， 发现还是有些知识是被忽略掉的， 所以借这个机会进行补充。 首先是KNN算法的kd树部分， 这里会通过一个具体的例子来说一下kd树的原理， 之前写白话KNN的时候， 这块知识是略掉的， 但感觉还是有必要了解一下这个东西的， 因为毕竟KNN我们知道， 如果拿一个新样本来判断它属于哪个类， 我们可是要计算它与其他样本点所有的距离， 这在样本非常多的时候时间复杂度可是很可怕的， 所以kd树的这种数据结构有利于降低一下时间复杂度， 差不多能从O(n)降到O(logn)， 也是kd树要引入的原因， 后面会通过一个例子来看看kd树的构建和搜索k近邻点的方式， 就知道为啥它能降低时间复杂度了。
然后就是线性回归， 这个之前也是忽略了一个点， 就是损失函数， 我们知道线性回归的损失函数就是平方差损失， 因为这个可以衡量预测值和真实值之间的差距嘛， 那既然是差距， 为啥不用别的差损失单单选定了平方差呢？ 其实这个损失函数是由基于一个误差项的假设推导出来的， 这里会补充一下。 所以这两个小细节希望能对这两个简单的算法加深理解吧。
大纲如下
KNN算法的重点在于找出K个最近邻的点， 在寻找过程中我们其实有两种方式进行选择：
这里主要是拿一个例子来看一下如何构建Kd树以及如何寻找近邻点， 至于kd树的理论可以参考后面给出的链接， 那里面说的比较详细。 说白了， kd树就可以看成是多维的二叉搜索树。
构造kd树的方式很简单， 首先我们从构建根节点开始。 两个原则：
具体步骤如下：这里先放一个图比较好理解：
构建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(n) O(n)提到 O ( l o g n ) O(logn) O(logn)。
线性回归我们肯定是很熟悉了， 给定一批数据 ( Y i , X i 1 , X i 2 , . . . , X i p ) (Y_i, X_{i1}, X_{i2}, ...,X_{ip}) (Yi,Xi1,Xi2,...,Xip)， 模型是
Y = X β + ε Y=X beta+varepsilon Y=Xβ+ε
这里采用了向量化的表示方法， β beta β里面就是那些参数了， 我们喜欢称之为 W W W， 而这里的 ε varepsilon ε就是误差项。 我们的误差函数往往定义成下面这个样子：
J ( β ) = ∥ X β − Y ∥ 2 J(beta)=|X beta-Y|^{2} J(β)=∥Xβ−Y∥2
也就是平方差损失。 我们往往通过最小二乘法，就可以得到最终 β beta β的解析解：
β ^ = ( X T X ) − 1 X T Y hat{beta}=left(X^{T} Xright)^{-1} X^{T} Y β^=(XTX)−1XTY
但是上面有个细节，就是为啥误差函数要定义成平方差损失呢？ 这个问题之前没有研究过， 这次学习看到了， 所以整理下来吧， 这个误差函数其实是基于误差项的一个假设进行推导出来的。
我们知道， 对于每个样本来说， 线性回归的公式可以写成：
y i = β T x i + ε i y^i=beta^Tx^i+varepsilon ^i yi=βTxi+εi
其中我们是假设这里的误差项服从标准正态的， 也就是 ε ∼ N ( 0 , σ 2 ) varepsilonsim N(0, sigma^2) ε∼N(0,σ2), 这时候就有
p ( ε i ) = 1 σ 2 π e − ε i 2 2 σ 2 p(varepsilon^i)=frac{1}{sigma sqrt {2pi}}e^{-frac{{varepsilon^i}^2}{2sigma^2}} p(εi)=σ2π 1e−2σ2εi2
这时候， 如果把 ε i varepsilon^i εi用上面等式替换掉, 就会得到：
P ( y i ∣ x i , β , σ ) = 1 σ 2 π e − ( y i − β T x i ) 2 2 σ 2 Pleft({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}}} P(yi∣xi,β,σ)=σ2π 1e2σ2−(yi−βTxi)2
这时候， 我们如果想让 y i y_i yi与 β T x i beta^Tx^i βTxi非常接近， 那么我们就要最大化上面的这个公式， 找那个最高点， 也就是均值所在处。 即我们需要 M a x i m u m L i k e l i h o o d : P ( y i ∣ x i , β , σ ) Maximum Likelihood: Pleft({y}^{i} mid x^{i}, {beta},{sigma}right) MaximumLikelihood:P(yi∣xi,β,σ)， 如果是针对所有样本， 我们使用连乘 M a x i m u m L i k e l i h o o d : ( 1 σ 2 π ) n ∏ i = 1 n e − ( y i − β T x i ) 2 2 σ 2 Maximum Likelihood: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}}} MaximumLikelihood:(σ2π 1)ni=1∏ne2σ2−(yi−βTxi)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∏ne2σ2−(yi−βTxi)2}
下面换成加法运算：
arg max w { ( 1 σ 2 π ) n ∏ i = 1 n e − ( y i − β T x i ) 2 2 σ 2 } = arg max w ( log [ ( 1 σ 2 π ) ) n ] + ∑ i = 1 n − ( y i − β T x i ) 2 2 σ 2 operatorname{arg} max _{w}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 max _{w}left(operatorname{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}} argwmax{(σ2π 1)ni=1∏ne2σ2−(yi−βTxi)2}=argwmax(log[(σ2π 1))n]+i=1∑n2σ2−(yi−βTxi)2
由于 l o g log log的那块和 2 σ 2 2sigma^2 2σ2都是常数， 我们可以直接去掉， 就变成了：
arg max w ∑ i = 1 n − ( y i − β T x i ) 2 underset{w}{arg max } sum_{i=1}^{n}-left(y^{i}-beta^{T} x^{i}right)^{2} wargmaxi=1∑n−(yi−βTxi)2
我们把负号去掉， 就相当于最小化了， 就得到了最终的形式：
arg min w ∑ i = 1 n ( y i − β T x i ) 2 underset{w}{arg min } sum_{i=1}^{n}left(y^{i}-beta^{T} x^{i}right)^{2} wargmini=1∑n(yi−βTxi)2
这才得到了最终的损失函数的形式。 可以发现也不是随便定义的吧。
有了损失函数， 在推导一下解析解
L ( β ) = ∥ X β − Y ∥ 2 = ( X β − Y ) T ( X β − Y ) = Y T Y − Y T X β − β T X T Y + β T X T X β mathcal{L}(beta)=|X beta-Y|^{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} L(β)=∥Xβ−Y∥2=(Xβ−Y)T(Xβ−Y)=YTY−YTXβ−βTXTY+βTXTXβ
我们对 β beta β求梯度
∇ β L ( β ) = ∇ β ( Y T Y − Y T X β − β T X T Y + β T X T X β ) = 0 − X T Y − X T Y + 2 X T X β = 2 X T X β − 2 X T Y 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 betaright)=0-X^{T} Y-X^{T} Y+2 X^{T} X beta=2 X^{T} X beta-2 X^{T} Y ∇βL(β)=∇β(YTY−YTXβ−βTXTY+βTXTXβ)=0−XTY−XTY+2XTXβ=2XTXβ−2XTY
令梯度等于0， 我们就可以得到 2 X T X β = 2 X T Y 2 X^{T} X beta=2 X^{T} Y 2XTXβ=2XTY， 即推导出 β = ( X T X ) − 1 X T Y beta=left(X^{T} Xright)^{-1} X^{T} Y β=(XTX)−1XTY
细节补充好了， 下面是关于线性回归的小总结：
关于线性回归， 先不充到这里吧。
参考：
本文发布于:2024-01-29 08:29:39，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170648818313995.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
