当前位置：首页 - 正文

Perceptron & KNN(面试准备)

发布网友发布时间：2024-05-04 19:59

我来回答

共1个回答

热心网友时间：2024-06-24 00:58

感知机是二分类的线性分类模型，感知机对应于特征空间中将实例划分为正负两类的分离超平面，属于判别模型。

感知机模型如下：

其损失函数为误分类的样本到超平面的几何距离之和（去掉系数）：

从而损失函数的梯度为：

随机选择一个误分类点，对进行更新，就得到感知机学习算法：

每次找一个误分类点作上述操作，直至找到一个超平面将所有点正确分类（若样本点线性可分）。

其收敛性的证明也很简单，思路就是设有一个 (含 )，使得分类结果全部正确，则我们的模型可以不断调整方向并在有限步使得与同向（证明见 here ）。

KNN的主要优点有：

KNN的主要缺点有：

值的选择没有经验性的方法，一般只能通过交叉验证来选取合适的k值。

如果值选择较小，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测起作用，但估计误差会增大，预测结果会对近邻的实例点非常敏感，如果近邻的实例点恰巧是噪声，预测就会出错。相反如果值选择较大，就相当于用较大的领域中的训练实例进行预测，近似误差会增大，但估计误差会减小。

对于近邻法来说，越大模型越简单，这一点乍一看不容易理解，但其实我们可以考虑极端情况（为样本数），此时任何新样本都会被归入当前样本集中实例最多的类别，从而丢失大量信息。反之，越小模型越复杂，模型将面临过拟合风险。

解决办法是：使用 KD 树来提高 KNN 搜索的效率。

KD 树是一种对维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。它是二叉树，表示对维空间的一个划分。构造 KD 树的过程相当于不断的用垂直于坐标轴的超平面将维空间切分的过程。树的每个结点对应于一个维的超矩形区域。

用 KD 树进行最近邻搜索的时候，首先在 KD 树中找到包含目标节点的叶结点，以此叶结点为“当前最近点”，然后递归地向上回退，若该结点保存的实例点比当前最近点距离目标更近，则以该点为“当前最近点”。检查该子结点的父节点的另一个子结点对应的区域是否有更近的点，即检查另一子结点对应的区域是否与以目标节点为球心，以目标点到“当前最近点”的距离为半径的超球体相交。若相交，可能在另一个子结点对应区域中存在距离目标更近的点，移动到另一个子结点，继续递归地进行搜索。若不相交，向上回退。当回退到根结点，搜索结束，此时的“当前最近点”即为最近邻点。K 近邻的搜索与之类似。

KD 树搜索的平均计算复杂度为，为训练集大小。KD 树适合样本数远大于特征数的情形。

Perceptron & KNN(面试准备)

解决办法是：使用 KD 树来提高 KNN 搜索的效率。KD 树是一种对维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。它是二叉树，表示对维空间的一个划分。构造 KD 树的过程相当于不断的用垂直于坐标轴的超平面将维空间切分的过程。树的每个结点对应于一个维的超矩形区域。用 ...

&amp; 归如何准备面试面试准备面试都需要准备什么去面试需要准备什么面试之前要做哪些准备面试前准备面试准备的内容有哪些面试前应做哪些准备

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
E-MAIL:11247931@qq.com