网站做配置文件的作用,内涵图网站源码,营口网站设计,做一个招聘网站需要多少钱目录 一、KNN算法简介#xff08;一#xff09;KNN算法包括三个步骤#xff08;二#xff09;超参数K的影响 二、距离度量三、邻近点的搜索算法四、KNN算法的特点五、KNN常用的参数及其说明六、分类算法的性能度量#xff08;一#xff09;混淆矩阵及相关概念#xff08… 目录 一、KNN算法简介一KNN算法包括三个步骤二超参数K的影响 二、距离度量三、邻近点的搜索算法四、KNN算法的特点五、KNN常用的参数及其说明六、分类算法的性能度量一混淆矩阵及相关概念二F1_score和其他度量指标 一、KNN算法简介
想一想下面图片中只有三种豆有三个豆是未知的种类如何判定他们的种类 1968年Cover和Hart提出了最初的近邻算法。
一KNN算法包括三个步骤
算距离给定测试样本计算它与训练集中的每个样本的距离找邻居圈定距离最近的k个训练样本作为测试样本的近邻做分类根据这k个近邻归属的主要类别来对测试样本分类。
k值的选择、距离度量和分类决策规则是KNN的3个基本要素。
二超参数K的影响 K值取3时判断绿色点的类别为蓝色 K值取5时判断绿色点的类别为红色为了能得到较优的K值可以采用交叉验证和网格搜索的办法分别尝试不同K值下的分类准确性。 当增大k值时一般错误率会先降低因为有周围更多的样本可以借鉴了。但当K值更大的时候错误率会更高。这也很好理解比如说你一共就35个样本当你K增大到30的时候KNN基本上就没意义了。 左图为k选取不同值时对鸢尾花分类影响。当k逐步增大时局部噪音样本对边界的影响逐渐减小边界形状趋于平滑。较大的k是会抑制噪声的影响但是使得分类界限不明显。举个极端例子如果选取k值为训练样本数量即kn采用等权重投票这种情况不管查询点q在任何位置预测结果仅有一个分类结果只能是样本数最多的那一类kNN这一本来与空间位置相关的算法因此失去了作用。这种训练得到的模型过于简化忽略样本数据中有价值的信息。
二、距离度量
1、欧氏距离Euclidean Distance n n n 维空间点 a ( x 11 , x 12 , . . . , x 1 n ) a(x_{11},x_{12},...,x_{1n}) a(x11,x12,...,x1n) 与 b ( x 21 , x 22 , . . . , x 2 n ) b(x_{21},x_{22},...,x_{2n}) b(x21,x22,...,x2n) 间的欧氏距离两个 n n n维向量 d 12 ∑ k 1 n ( x 1 k − x 2 k ) 2 d_{12}\sqrt{\sum_{k1}^n(x_{1k}-x_{2k})^2} d12k1∑n(x1k−x2k)2
2、曼哈顿距离Manhattan Distance
曼哈顿距离Manhattan Distance是指两点在南北方向上的距离加上在东西方向上的距离。 n n n 维空间点 a ( x 11 , x 12 , . . . , x 1 n ) a(x_{11},x_{12},...,x_{1n}) a(x11,x12,...,x1n) 与 b ( x 21 , x 22 , . . . , x 2 n ) b(x_{21},x_{22},... ,x_{2n}) b(x21,x22,...,x2n) 的曼哈顿距离为 d 12 ∑ k 1 n ∣ x 1 k − x 2 k ∣ d_{12}\sum_{k1}^n|x_{1k}-x_{2k}| d12k1∑n∣x1k−x2k∣ 图中两点间的绿线代表的是欧式距离 。红线蓝线和黄线代表的都是曼哈顿距离由此可见在两点间曼哈顿距离相等的情况下线路有多种情况。
3、余弦距离Cosine Distance
两个 n n n 维样本点 a ( x 11 , x 12 , . . . , x 1 n ) a(x_{11},x_{12},...,x_{1n}) a(x11,x12,...,x1n) 和 b ( x 21 , x 22 , . . . , x 2 n ) b(x_{21},x_{22},...,x_{2n}) b(x21,x22,...,x2n) 的夹角余弦为 c o s ( θ ) a ⋅ b ∣ a ∣ ∣ b ∣ cos(\theta)\frac{a\cdot b}{|a||b|} cos(θ)∣a∣∣b∣a⋅b 即 c o s ( θ ) ∑ n k 1 x 1 k x 2 k ∑ n k 1 x 1 k 2 ∑ n k 1 x 2 k 2 cos(\theta)\frac{\sum_n^{k1}x_{1k}x_{2k}}{\sqrt{\sum_n^{k1}x_{1k}^2\sum_n^{k1}x_{2k}^2}} cos(θ)∑nk1x1k2∑nk1x2k2 ∑nk1x1kx2k
4、切比雪夫距离Chebyshev Disatance 切比雪夫距离Chebyshev Disatance是指二个点之间的距离定义是其各坐标数值差绝对值的最大值。 D C h e b y s h e v ( p , q ) max i ( ∣ p i − q i ∣ ) D_{Chebyshev}(p,q)\max_{i}(|p_i-q_i|) DChebyshev(p,q)imax(∣pi−qi∣)
这也等于以下 L p L_p Lp 度量的极限 lim k → ∞ ( ∑ i 1 n ∣ p i − q i ∣ k ) 1 k \lim_{k\to \infty}\left(\sum_{i1}^n|p_i-q_i|^k\right)^{\frac{1}{k}} k→∞lim(i1∑n∣pi−qi∣k)k1 因此切比雪夫距离也称为 L ∞ L_{\infty} L∞ 度量无穷范数。
国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距 f 6 f6 f6 位置的切比雪夫距离。
5、闵可夫斯基距离Minkowski Distance
闵氏距离的定义两个 n n n 维变量 a ( x 11 , x 12 , . . . , x 1 n ) a(x_{11},x_{12},...,x_{1n}) a(x11,x12,...,x1n) 与 b ( x 21 , x 22 , . . . , x 2 n ) b(x_{21},x_{22},...,x_{2n}) b(x21,x22,...,x2n) 间的闵可夫斯基距离定义为 d 12 ∑ k 1 n ∣ x 1 k − x 2 k ∣ p p d_{12}\sqrt[p]{\sum_{k1}^n\left|x_{1k}-x_{2k}\right|^p} d12pk1∑n∣x1k−x2k∣p 其中 p p p 是一个变参数
当 p 1 p1 p1 时就是曼哈顿距离当 p 2 p2 p2 时就是欧氏距离当 p → ∞ p→\infty p→∞ 时就是切比雪夫距离。
KNN算法默认使用闵可夫斯基距离。
三、邻近点的搜索算法 KNN算法需要在中搜索与x最临近的k个点最直接的方法是逐个计算x与中所有点的距离并排序选择最小的k个点即线性扫描。 当训练数据集很大时计算非常耗时以至于不可行。实际应用中常用的是kd-tree (k-dimension tree) 和ball-tree这两种方法。ball-tree是对kd-tree的改进在数据维度大于20时kd-tree性能急剧下降而ball-tree在高维数据情况下具有更好的性能。 kd-tree以空间换时间利用训练样本集中的样本点沿各维度依次对k维空间进行划分建立二叉树利用分治思想大大提高算法搜索效率。
样本集不平衡时的影响
观察下面的例子对于位置样本X通过KNN算法显然可以得到X应属于红点但对于位置样本Y通过KNN算法我们似乎得到了Y应属于蓝点的结论而这个结论直观来看并没有说服力。 由上面的例子可见该算法在分类时有个重要的不足是当样本不平衡时即一个类的样本容量很大而其他类样本容量很小时很有可能导致当输入一个未知样本时该样本的K个邻居中大数量类的样本占多数。
解决方法采用权值的方法来改进。和该样本距离小的邻居权值大和该样本距离大的邻居权值则相对较小避免因一个类别的样本过多而导致误判。
四、KNN算法的特点
优点
KNN 理论简单容易实现既可以用来做分类也可以用来做回归还可以用于非线性分类新数据可以直接加入数据集而不必进行重新训练对离群点不敏感。
缺点
样本不平衡问题即有些类别的样本数量很多而其它样本的数量很少效果差不适合高维数据对于样本容量大的数据集计算量比较大体现在距离计算上KNN 每一次分类都会重新进行一次全局运算K值不好确定各属性的权重相同影响准确率。
五、KNN常用的参数及其说明
class sklearn.neighbors.KNeighborsClassifier(n_neighbors5, weightsuniform,algorithmauto,
leaf_size30, p2, metricminkowski, metric_paramsNone,n_jobs1,**kwargs)参数名称说明n_neighbors接收int。表示近邻点的个数即K值。默认为5。weights接收str或callable可选参数有“uniform”和“distance”。表示近邻点的权重“uniform”表示所有的邻近点权重相等“distance”表示距离近的点比距离远的点的权重大。默认为“uniform”。algorithm接收str可选参数有“auto”“ball_tree”“kd_tree”和“brute”。表示搜索近邻点的算法。默认为“auto”即自动选择。leaf_size接收int。表示kd树和ball树算法的叶尺寸它会影响树构建的速度和搜索速度以及存储树所需的内存大小。默认为30。p接收int。表示距离度量公式1是曼哈顿距离公式2是欧式距离。默认为2。metric接收str或callable。表示树算法的距离矩阵。默认为“minkowski”。metric_params接收dict。表示metric参数中接收的自定义函数的参数。默认为None。n_jobs接收int。表示并行运算的CPU数量默认为1-1则是使用全部的CPU。
六、分类算法的性能度量
一混淆矩阵及相关概念 说明 1结论中的正例、反例以预测值为准而前面的定语真、假以真实值为准 2预测值与真实值一致则定语为真预测值与真实值不一致则定语为假 3主对角线表示预测值与真实值相符副对角线表示预测值与真实值不符。
相关概念
准确率ACCuracy全部预测中预测正确的比例即主对角线的占比查准率Precision 预测的正例中预测正确真正例的比例查全率或找回率Recall真实正例中预测正确真正例的比例 准确率 A C C T P T N T P T N F N F P 准确率ACC\frac{TPTN}{TPTNFNFP} 准确率ACCTPTNFNFPTPTN 查准率 P T P T P F P 查准率P\frac{TP}{TPFP} 查准率PTPFPTP 查全率 R T P T P F N 查全率R\frac{TP}{TPFN} 查全率RTPFNTP
二F1_score和其他度量指标
y_true [1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0]
y_pred [1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0]查准率和查全率是一对矛盾的度量一般来说查准率高时查全率往往会偏低查全率高时查准率往往会偏低。而F1-Score指标综合了Precision与Recall的产出的结果是F1是基于查准率与查重率的调和平均。F1-Score的取值范围从0到11代表模型的输出最好0代表模型的输出结果最差。 准确率 A C C 2 3 2 4 3 3 5 12 准确率ACC\frac{23}{2433}\frac{5}{12} 准确率ACC243323125 查准率 P r e c i s i o n 3 4 3 3 7 查准率Precision\frac{3}{43}\frac{3}{7} 查准率Precision43373 查全率 R e c a l l 3 3 3 3 6 查全率Recall\frac{3}{33}\frac{3}{6} 查全率Recall33363 1 F 1 _ s c o r e 1 2 ⋅ ( 1 P 1 R ) ⇒ F 1 _ s c o r e 2 ⋅ P ⋅ R P R \frac{1}{F1\_score}\frac{1}{2}\cdot(\frac{1}{P}\frac{1}{R})\Rightarrow F1\_score\frac{2\cdot P\cdot R}{PR} F1_score121⋅(P1R1)⇒F1_scorePR2⋅P⋅R F 1 _ s c o r e 2 × 3 7 × 3 6 3 7 3 6 6 13 F1\_score\frac{2×\frac{3}{7}×\frac{3}{6}}{\frac{3}{7}\frac{3}{6}}\frac{6}{13} F1_score73632×73×63136
此外还有P-R曲线、ROC曲线、 AUC值等分类性能的指标。
