网站定位,谷歌推广服务,网站建设咨询有客诚信,深圳ww目录 一. KNN算法原理二. KNN算法三要素1. K值的选择2. 距离2.1 欧氏距离2.2 曼哈顿距离(城市街区距离)2.3 切比雪夫距离(棋盘距离)2.4 闵可夫斯基距离2.5 标准化欧式距离2.6 余弦距离欧氏距离与余弦距离对比 3. 决策规则3.1 KNN分类任务多数表决法加权多数表决法 3.2 KNN回归任… 目录 一. KNN算法原理二. KNN算法三要素1. K值的选择2. 距离2.1 欧氏距离2.2 曼哈顿距离(城市街区距离)2.3 切比雪夫距离(棋盘距离)2.4 闵可夫斯基距离2.5 标准化欧式距离2.6 余弦距离欧氏距离与余弦距离对比 3. 决策规则3.1 KNN分类任务多数表决法加权多数表决法 3.2 KNN回归任务平均值法加权平均值法 本篇博客我们开启新的算法讲解KNN算法 首先通过一张直观的图片来解释KNN的概念
一. KNN算法原理
K近邻(K-nearest neighbors, KNN)既可以应用于分类应用中也可以应用在回归应用中 一种基本的机器学习算法k近邻k个最近的邻居的意思即每个样本都可以用它最接近的 k个邻居来代表比如近朱者赤近墨者黑KNN在做回归和分类的主要区别在于最后预测的决策方式
KNN在分类预测时一般采用多数表决法KNN在回归预测时一般采用平均值法
一句话简单说KNN的原理就是相似的人聚在一起 KNN算法分类的具体操作从训练集合中获取K个离待测样本距离最近的样本数据根据获取到的K个样本数据来预测当前待预测样本的目标属性值很显然根据上图可以得到K3时绿色圆的预测值为红色三角(多数投票)
将上述分类操作抽象为数学公式就会得到 y i ^ argmax C j ∑ x i ∈ N k ( x ) I ( y i C j ) ( i 1 , 2 , … , N , j 1 , 2 , … , C ) \hat{y_{i}}\underset{C_{j}}{\operatorname{argmax}} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}C_{j}\right) \quad(i1,2, \ldots, N, j1,2, \ldots, C) yi^Cjargmaxxi∈Nk(x)∑I(yiCj)(i1,2,…,N,j1,2,…,C) 参数说明: N \mathrm{N} N 是训练集中的样本数量C是类别数量 C j C_{j} Cj 是第 j \mathrm{j} j 个类别 x i \mathrm{x}_{\mathrm{i}} xi 是第 i \mathrm{i} i 个样本的特征向量 y i \mathrm{y}_{\mathrm{i}} yi 是第 i \mathrm{i} i 个样本的标签 k k k 是KNN模型的 k k k 值 N k ( x ) \mathrm{N}_{\mathrm{k}}(\mathrm{x}) Nk(x) 样本 x \mathrm{x} x 的 k \mathrm{k} k 个最近邻组成的集合 y ^ i \hat{y}_{i} y^i 是第 i \mathrm{i} i 个样本的预测类别 公式解释 当送入一个样本 x i x_{i} xi时取给定的K个邻居 统计样本 x i x_{i} xi的K个近邻等于 C j C_{j} Cj类别的情况 I I I函数返回1 此时我们可以得到样本K个邻居中不同类别的个数 求K个邻居中出现个数最多的 C C C即为样本 x i x_{i} xi的预测值 y i ^ \hat{y_{i}} yi^ 二. KNN算法三要素
对于上面给出的示例图我们做进一步的分析 这里我们可以看到预测值的结果与K邻居的个数有密切关联
如果K3绿色圆的预测结果为红色三角形如果K5绿色圆的预测结果为蓝色正方形
KNN三要素 K值的选择K值的选择一般根据样本分布选择一个较小的值然后通过交叉验证来选择一个比较合适的最终值当选择比较小的K值的时候 表示使用较小领域中的样本进行预测训练误差会减小但是会导致模型变得复杂容易过拟合当选择较大的K值的时候表示使用较大领域中的样本进行预测训练误差会增大同时会使模型变得简单容易导致欠拟合 距离的度量一般使用欧氏距离决策规则在分类模型中主要使用多数表决法或者加权多数表决法在回归模型中主要使用平均值法或者加权平均值法1. K值的选择
k值的减小就意味着整体模型变得复杂容易发生过拟合k值的增大就意味着整体的模型变得简单容易发生欠拟合
在应用中k值一般取一个比较小的数值通常采用交叉验证法来选取最优的k值
对于K值得选择我们可以通过定义KNN的损失函数得到 注意该损失函数是用来选择 k 值的而不用于训练对于分类问题KNN模型的损失函数是 L 1 N ∑ x i ∈ N k ( x ) I ( y i C j ) ( i 1 , 2 , … , N , j 1 , 2 , … , C ) L\frac{1}{N} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}C_{j}\right) \quad(i1,2, \ldots, N, j1,2, \ldots, C) LN1xi∈Nk(x)∑I(yiCj)(i1,2,…,N,j1,2,…,C) 本质计算准确率 2. 距离
2.1 欧氏距离 ∑ i 1 n ( x i − y i ) 2 \sqrt{\sum_{i1}^{n}\left(x_{i}-y_{i}\right)^{2}} i1∑n(xi−yi)2
2.2 曼哈顿距离(城市街区距离) ∑ k 1 n ∣ x 1 k − x 2 k ∣ \sum_{k1}^{n}\left|x_{1 k}-x_{2 k}\right| k1∑n∣x1k−x2k∣
2.3 切比雪夫距离(棋盘距离) max ( ∣ x 1 i − x 2 i ∣ ) \max \left(\left|x_{1 i}-x_{2 i}\right|\right) max(∣x1i−x2i∣)
2.4 闵可夫斯基距离 ∑ k 1 n ∣ x 1 k − x 2 k ∣ p p \sqrt[p]{\sum_{k1}^{n}\left|x_{1 k}-x_{2 k}\right|^{p}} pk1∑n∣x1k−x2k∣p
当 p1 的时候是曼哈顿距离;当 p2 的时候是欧式距离;当 p∞ 的时候是切比雪夫距离
2.5 标准化欧式距离 ∑ i 1 n ( u i − v i ) 2 V [ x i ] \sqrt{\sum_{i1}^{n} \frac{\left(u_{i}-v_{i}\right)^{2}}{V\left[x_{i}\right]}} i1∑nV[xi](ui−vi)2 本质做法为先对数据进行标准化再计算欧氏距离计算本质计算一个特征的方差方差开根号为标准差2.6 余弦距离 1 − [ x , y ] ∥ x ∥ ⋅ ∥ y ∥ 1-\frac{[x, y]}{\|x\| \cdot\|y\|} 1−∥x∥⋅∥y∥[x,y]
其中余弦相似度(即 cot θ \cot \theta cotθ)为: k ( x , y ) [ x , y ] ∥ x ∥ ⋅ ∥ y ∥ \quad k(x, y)\frac{[x, y]}{\|x\| \cdot\|y\|} k(x,y)∥x∥⋅∥y∥[x,y]
余弦相似度的取值范围是 [ − 1 , 1 ] [-1,1] [−1,1] 余弦距离的取值范围是 [ 0 , 2 ] [0,2] [0,2] 如果两个向量方向相同则余弦距离为0 如果两个向量的方向相反则余弦距离为2下面我们举一个例子 假如新闻X和新闻Y对应向量分别是 x 1 , x 2 , … , x 6400 x_{1}, x_{2}, \ldots, x_{6400} x1,x2,…,x6400 和 y 1 , y 2 , … , y 6400 \mathrm{y}_{1}, \mathrm{y}_{2}, \ldots, \mathrm{y}_{6400} y1,y2,…,y6400 则它们的余弦相似度为: cos θ x 1 y 1 x 2 y 2 ⋯ x 6400 y 6400 x 1 2 x 2 2 ⋯ x 6400 2 ⋅ y 1 2 y 2 2 ⋯ y 6400 2 \cos \theta\frac{x_{1} y_{1}x_{2} y_{2}\cdotsx_{6400} y_{6400}}{\sqrt{x_{1}^{2}x_{2}^{2}\cdotsx_{6400}^{2}} \cdot \sqrt{y_{1}^{2}y_{2}^{2}\cdotsy_{6400}^{2}}} cosθx12x22⋯x64002 ⋅y12y22⋯y64002 x1y1x2y2⋯x6400y6400 当两条新闻向量夹角余弦等于1时这两条新闻完全重复用这个办法可以删除爬虫所收集网页中的重复网页当夹角的余弦值接近于1时两条新闻相似可以用作文本分类夹角的余弦越小两条新闻越不相关欧氏距离与余弦距离对比 这里我们用一个例子说明两种距离的关注点
示例1 对于某两部电视剧 用户A的观看向量为 ( 0 , 1 ) (0,1) (0,1)用户B的观看向量为 ( 1 , 0 ) (1,0) (1,0) 在分析两个用户对于不同电视剧的偏好时更关注相对差异显然应当使用余弦距离且欧氏距离很小示例2 对于某个游戏平台 以登陆次数(单位次)和平均游戏时长(单分钟)作为特征时 用户A的向量为 ( 1 , 10 ) (1,10) (1,10)、用户B的向量为 ( 10 , 100 ) (10,100) (10,100) 在分析两个用户活跃度时更关注数值绝对差异应当使用欧氏距离且余弦距离会认为两个用户距离很近总结 余弦距离注重两个向量的空间夹角与方向上的差异直接相关 欧氏距离注重两个向量的绝对距离与位置坐标直接相关 注意余弦距离在形容两个特征向量之间的关系方面有很大用处比如人脸识别推荐系统等3. 决策规则
3.1 KNN分类任务 多数表决法 每个邻近样本的权重是一样红色 3 5 \frac{3}{5} 53
黄色 2 5 \frac{2}{5} 52
预测结果为红色
加权多数表决法 每个邻近样本的权重是不一样的一般情况下采用权重和距离成反比的方式来计算也就是说最终预 测结果是出现权重最大的那个类别这里假设红色到预测目标的距离为2黄色到预测目标的距离为1
红色权重 1 2 \frac{1}{2} 21归一化后单个权重为 1 7 \frac{1}{7} 71
黄色权重 1 1 \frac{1}{1} 11归一化后单个权重为 2 7 \frac{2}{7} 72
预测结果为黄色
3.2 KNN回归任务 平均值法 每个邻近样本的权重是一样预测结果为 13 5 2.6 \frac{13}{5}2.6 5132.6
加权平均值法 每个邻近样本的权重是不一样的一般情况下采用权重和距离成反比的方式来计算在计算均值的时候进行加权操作这里假设圆3到预测目标的距离为2圆2到预测目标的距离为1
圆3权重 1 2 \frac{1}{2} 21归一化后单个权重为 1 7 \frac{1}{7} 71
圆2权重 1 1 \frac{1}{1} 11归一化后单个权重为 2 7 \frac{2}{7} 72
预测结果为 1 7 ∗ 3 ∗ 3 2 7 ∗ 2 ∗ 2 17 7 2.43 \frac{1}{7}*3*3\frac{2}{7}*2*2\frac{17}{7}2.43 71∗3∗372∗2∗27172.43 感谢阅读 如果喜欢这篇文章记得点赞和转发哦 有任何想法或问题欢迎留言交流我们下次见 本文相关代码存放位置 【手写KNN算法 代码实现】
祝愉快
