• 欢迎访问数智,大数据学习

【ML第四节】:机器学习之K近邻算法详解

机器学习 Raybra_Wei 2年前 (2018-09-06) 441次浏览 0个评论 扫描二维码

    概念理解:最近邻规则算法又称 K 近邻算法,采用测量不同特征值之间的距离方法进行分类。

优点:精度高、对异常值不敏感、无数据输入假定。

缺点:计算复杂度高、空间复杂度高。

适用范围:数值型和标称型

工作原理:存在一个训练集,并且这些训练集的数据都存在标签,那我们知道每一个数据的所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与训练集中每个数据对应的特征进行比较,然后计算出与训练集最相似的分类标签。通常,我们只选择训练集中的 k 个数据,这 K 个数据是在整个训练集中经过计算排序后帅选出的。然后我们从这 K 个数据中,选择 k 个最相似数据中出现次数最多的分类,作为测试数据的分类。

案例解释:比如我们我们现在拿到了 6 个电影的数据,这 6 个电影分别分为爱情片、动作片。那么还有描述这些电影的特征比如:打斗镜头次数、接吻镜头次数。那么我们就可以通过这两个特征对新来的一部电影进行分类。数据如图:

【ML 第四节】:机器学习之 K 近邻算法详解

得到数据之后,如何进行预测分类呢?根据KNN算法介绍,我们可以将打斗镜头和接吻镜头与每部电影做差然后平方最后算相加和,这样我们会得到 6 个数据,比如我们要取三个,那么先对这六个数据进行排序,选择最小的三个数据这里的 3 相当于 K 值,然后我们找到这 3 个数据对应的标签值,比如有两个爱情片一个动作片,那么我们就自然的得出了这个待分类的电影的分类为爱情片。

算法流程:

(1)收集数据

(2)准备数据:距离计算所需要的数值,最好是结构化的数据格式。

(3)分析数据

(4)训练算法:此步驟不适用于 K-近邻算法。

(5)测试算法:计算错误率。

(6)使用算法:首先需要输入样本数据和结构化的输出结果,然后运行 K-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理

算法详解:首先构建一个训练集,一个测试集便于描述:

接下来用这一组数据构建 K 近邻算法:

K 近邻算法的代码如下:

代码解释:

代码中 datasetsize 代表这个训练集的大小,然后我们将测试集扩展成长度与训练集大小一样。通过 numpy 中的 tile 函数实现,然后将生成的测试集矩阵减去训练集矩阵,这样就得到了每个数据在每一个特征上的距离,然后通过将性得到的差矩阵做平方,得到每个值的距离的平方,这样做的目的是将一些负数也转化为整数,因为距离部分正负,最后将每个特征的距离算之和平开平方,得到距离。并且将这个距离进行升序排序,通过传参传进来的 K 值取距离数据集中的前 K 个值。接下来,算出早 K 个数据中对应标签最多的值。这个值即是我们所需要求的值。

UCI 数据集测试

IRIS 数据集测试

程序源代码:

总结:总体上,KNN算法在以上几个数据集表现良好有的准确率可以达到 95%以上,但是在部分数据集上表现不好准确率在 50%左右。KNN是一种最简单最有效的算法,使用算法时必须有接近实际数据的训练样本数据,KNN必须保存全部数据集,如果训练集很大,必须使用大量的存储空间。除此之外,由于要算每个点之间的距离,所以时间复杂度可能非常大。


数智 Lab , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:【ML 第四节】:机器学习之 K 近邻算法详解
喜欢 (2)
[]
分享 (0)
关于作者:
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址