发布网友
发布时间:2024-05-04 19:59
共1个回答
热心网友
时间:2024-06-24 00:58
感知机是二分类的线性分类模型,感知机对应于特征空间中将实例划分为正负两类的分离超平面,属于判别模型。
感知机模型如下:
其损失函数为误分类的样本到超平面的几何距离之和(去掉系数 ):
从而损失函数的梯度为:
随机选择一个误分类点 ,对 进行更新,就得到感知机学习算法:
每次找一个误分类点作上述操作,直至找到一个超平面将所有点正确分类(若样本点线性可分)。
其收敛性的证明也很简单,思路就是设有一个 (含 ),使得分类结果全部正确,则我们的模型可以不断调整 方向并在有限步使得 与 同向(证明见 here )。
KNN的主要优点有:
KNN的主要缺点有:
值的选择没有经验性的方法,一般只能通过交叉验证来选取合适的k值。
如果 值选择较小,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差会减小,只有与输入实例较近的训练实例才会对预测起作用,但估计误差会增大,预测结果会对近邻的实例点非常敏感,如果近邻的实例点恰巧是噪声,预测就会出错。相反如果 值选择较大,就相当于用较大的领域中的训练实例进行预测,近似误差会增大,但估计误差会减小。
对于 近邻法来说, 越大模型越简单,这一点乍一看不容易理解,但其实我们可以考虑极端情况 ( 为样本数),此时任何新样本都会被归入当前样本集中实例最多的类别,从而丢失大量信息。反之, 越小模型越复杂,模型将面临过拟合风险。
解决办法是:使用 KD 树来提高 KNN 搜索的效率。
KD 树是一种对 维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。它是二叉树,表示对 维空间的一个划分。构造 KD 树的过程相当于不断的用垂直于坐标轴的超平面将 维空间切分的过程。树的每个结点对应于一个 维的超矩形区域。
用 KD 树进行最近邻搜索的时候,首先在 KD 树中找到包含目标节点的叶结点,以此叶结点为“当前最近点”,然后递归地向上回退,若该结点保存的实例点比当前最近点距离目标更近,则以该点为“当前最近点”。检查该子结点的父节点的另一个子结点对应的区域是否有更近的点,即检查另一子结点对应的区域是否与以目标节点为球心,以目标点到“当前最近点”的距离为半径的超球体相交。若相交,可能在另一个子结点对应区域中存在距离目标更近的点,移动到另一个子结点,继续递归地进行搜索。若不相交,向上回退。当回退到根结点,搜索结束,此时的“当前最近点”即为最近邻点。K 近邻的搜索与之类似。
KD 树搜索的平均计算复杂度为 , 为训练集大小。KD 树适合样本数远大于特征数的情形。