《机器学习实战》学习笔记(一)k-近邻算法

k-近邻算法(k-Nearest Neighbor,简称kNN)

工作原理是:存在一个样本数据集合,也称作是训练样本集,并且样本集中每个数据都存在标签,即知道样本集合中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集合中数据对应的特征进行比较,然后算法提取样本集合中特征最相似数据(最近邻)的分类标签。一般来说,只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

示例1:首先看一个简单的例子,了解kNN的工作原理。

示例2:使用k-近邻算法改进约会网站的配对效果

  • 约会数据集存放在文本文件datingTestSet2.txt中,每一个样本数据占据一行,总共有1000行,数据内容如下图所示,其中样本主要包含以下3种特征:
  • ①每年获得的飞行常客里程数
  • ②玩视频游戏所耗时间百分比
  • ③每周消费的冰淇淋公升数
  • 2.1 准备数据:从文本文件中解析数据
  • 2.2 分析数据:使用matplotlib创建散点图
  • 2.3 准备数据:归一化数值
  • 首先观察该文本数据发现,每年获取的飞行常客里程数的取值明显远远大于其他两个特征,在处理这种不同取值范围的特征值时,通常采用的方法就是将数值归一化,如将数值范围处理为0到1或者-1到1之间。
  • newValue = (oldValue – min) / (max – min)
  • 2.3 测试算法:验证分类器
  • 2.3 预测算法

示例3:手写识别系统

  • 3.1 准备数据:将图像转换为测试向量
  • 实际图像存在在两个子目录中:目录trainingDigits中包含了大约2000个例子,每个列子的内容如下图所示,每个数字大约有200个样本;目录testDigits中包含了大约900个测试数据。使用目录trainingDigits中的数据训练分类器,使用目录testDigits中的数据测试分类器的效果。
  • 将一个32*32的二进制图像矩阵转换为1*1024的向量,代码如下:
  • 3.2 测试算法:使用k-近邻算法识别手写数字

实际使用这个算法时,算法的执行效率并不高,因为算法需要为每个测试向量做2000次距离计算,每个距离计算包括了1024个维度浮点元算,总计要执行900次,此外,还需要为测试向量准备2MB的存储空间,k-近邻算法是分类数据最简单最有效的算法,k-近邻算法是基于实例的学习,使用算法时必须有接近实际数据的训练样本数据,由于需要对数据集中的每个数据计算距离值,实际使用时可能非常耗时。