长沙网站推广运营,营销型网站建设选择题,合肥网络公司 网站建设,扁平化 网站 模板文章目录 1 KNN算法1.1 KNN算法原理1.2 KNN过程1.3 KNN三要素1.4 KNN分类预测规则1.5 KNN回归预测规则1.6 KNN算法实现方式#xff08;重点#xff09;1.7 k近邻算法优缺点 2 KD-Tree2.1 KD Tree构建方式2.2 KD Tree查找最近邻2.3 KNN参数说明 1 KNN算法
定义#xff1a;如… 文章目录 1 KNN算法1.1 KNN算法原理1.2 KNN过程1.3 KNN三要素1.4 KNN分类预测规则1.5 KNN回归预测规则1.6 KNN算法实现方式重点1.7 k近邻算法优缺点 2 KD-Tree2.1 KD Tree构建方式2.2 KD Tree查找最近邻2.3 KNN参数说明 1 KNN算法
定义如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别则该样本也属于这个类别。来源KNN算法最早是由Cover和Hart提出的一种分类算法
1.1 KNN算法原理
K近邻K-nearst neighborsKNN是一种基本的机器学习算法所谓k近邻就是k个最近的邻居的意思说的是每个样本都可以用它最接近的k个邻居来代表。比如判断一个人的人品只需要观察与他来往最密切的几个人的人品好坏就可以得出即“近朱者赤近墨者黑KNN算法既可以应用于分类应用中也可以应用在回归应用中。KNN在做回归和分类的主要区别在于最后做预测的时候的决策方式不同。KNN在分类预测时一般采用多数表决法而在做回归预测时一般采用平均值法。
1.2 KNN过程
1、从训练集合中获取K个离待预测样本距离最近的样本数据 2、根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。
1.3 KNN三要素
在KNN算法中非常重要的主要是三个因素
K值的选择对于K值的选择一般根据样本分布选择一个较小的值然后通过交叉验证来选择一个比较合适的最终值当选择比较小的K值的时候表示使用较小领域中的样本进行预测训练误差会减小但是会导致模型变得复杂容易过拟合当选择较大的K值的时候表示使用较大领域中的样本进行预测训练误差会增大同时会使模型变得简单容易导致欠拟合距离的度量一般使用欧氏距离欧几里得距离决策规则在分类模型中主要使用多数表决法或者加权多数表决法在回归模型中主要使用平均值法或者加权平均值法。
1.4 KNN分类预测规则
在KNN分类应用中一般采用多数表决法或者加权多数表决法。
多数表决法每个邻近样本的权重是一样的也就是说最终预测的结果为出现类别最多的那个类比如下图中蓝色圆圈的最终类别为红色加权多数表决法每个邻近样本的权重是不一样的一般情况下采用权重和距离成反比的方式来计算也就是说最终预测结果是出现权重最大的那个类别比如下图中假设三个红色点到待预测样本点的距离均为2两个黄色点到待预测样本点距离为1那么蓝色圆圈的最终类别为黄色。 1.5 KNN回归预测规则
在KNN回归应用中一般采用平均值法或者加权平均值法。
平均值法每个邻近样本的权重是一样的也就是说最终预测的结果为所有邻近样本的目标属性值的均值比如上图中蓝色圆圈的最终预测值为2.6加权平均值法每个邻近样本的权重是不一样的一般情况下采用权重和距离成反比的方式来计算也就是说在计算均值的时候进行加权操作比如上图中假设上面三个点到待预测样本点的距离均为2下面两个点到待预测样本点距离为1那么蓝色圆圈的最终预测值为2.43权重分别为1/7和2/7
1.6 KNN算法实现方式重点
KNN算法的重点在于找出K个最邻近的点主要方式有以下几种
蛮力实现brute计算预测样本到所有训练集样本的距离然后选择最小的k个距离即可得到K个最邻近点。缺点在于当特征数比较多、样本数比较多的时候算法的执行效率比较低KD树kd_treeKD树算法中首先是对训练数据进行建模构建KD树然后再根据建好的模型来获取邻近样本数据。
除此之外还有一些从KD-Tree修改后的求解最邻近点的算法比如Ball Tree BBF TreeMVP Tree等。
1.7 k近邻算法优缺点
优点简单易于理解易于实现无需估计参数无需训练
缺点
懒惰算法对测试样本分类时的计算量大内存开销大必须指定K值K值选择不当则分类精度不能保证
使用场景小数据场景几千几万样本具体场景具体业务去测试
2 KD-Tree
KD Tree是KNN算法中用于计算最近邻的快速、便捷构建方式。当样本数据量少的时候我们可以使用brute这种暴力的方式进行求解最近邻即计算到所有样本的距离。但是当样本量比较大的时候直接计算所有样本的距离工作量有点大所以在这种情况下我们可以使用kd tree来快速的计算。
2.1 KD Tree构建方式
KD树采用从m个样本的n维特征中分别计算n个特征取值的方差用方差最大的第k维特征nk作为根节点。对于这个特征选择取值的中位数nkv作为样本的划分点对于小于该值的样本划分到左子树对于大于等于该值的样本划分到右子树对左右子树采用同样的方式找方差最大的特征作为根节点递归即可产生KD树。
2.2 KD Tree查找最近邻
当我们生成KD树以后就可以去预测测试集里面的样本目标点了。
对于一个目标点我们首先在KD树里面找到包含目标点的叶子节点。
以目标点为圆心以目标点到叶子节点样本实例的距离为半径得到一个超球体最近邻的点一定在这个超球体内部。
然后返回叶子节点的父节点检查另一个子节点包含的超矩形体是否和超球体相交如果相交就到这个子节点寻找是否有更加近的近邻有的话就更新最近邻。如果不相交那就简单了我们直接返回父节点的父节点在另一个子树继续搜索最近邻。当回溯到根节点时算法结束此时保存的最近邻节点就是最终的最近邻。
2.3 KNN参数说明
