四、k-邻近算法的应用
1.对电影的题材类型进行分类
众所周知，电影可以按照题材分类，然而题材本身是如何定义的？由谁来判定某部电影属于哪个题材？也就是说同一题材的电影具有哪些公共特征？这些都是在进行电影分类时必须要考虑的问题。
动作片具有哪些共同特征，使得动作片之间非常类似，而与爱情片存在着明显的差别呢？动作片中也会有接吻镜头，爱情片中也会存在打斗场景，我们不能单纯依靠是否存在打斗或者接吻来判断影片的类型。但是爱情片中的接吻镜头更多，动作片中打斗场景也更频繁，基于此类场景在某部电影中出现的次数可以用来进行电影分类。
假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们可以使用KNN来解决这个问题。
每部电影的打斗镜头数、接吻镜头数以及电影评估类型
电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
California Man | 3 | 104 | 爱情片 |
He’s Not Really into Dudes | 2 | 100 | 爱情片 |
Beautiful Woman | 1 | 81 | 爱情片 |
Kevin Longblade | 101 | 10 | 动作片 |
Robo Slayer 3000 | 99 | 5 | 动作片 |
Amped II | 98 | 2 | 动作片 |
？ | 18 | 90 | 未知 |
首先，计算未知电影与样本集中其他电影的距离。
齐次，按照距离递增排序，可以找到k个距离最近的电影。
假定k = 3，则三个最靠近的电影依次是He’s Not Really into Dudes，Beautiful Woman，California Man。k-邻近算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们断定未知电影是爱情片。
2.改进约会网站的配对效果
我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾经交往过三种类型的人：
（1）不喜欢的人
（2）魅力一般的人
（3）极具魅力的人
尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人，而周末则更喜欢与哪些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。
海伦收集约会数据已经有一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包含以下3种特征：
（1）每年获得的飞行常客里程数
（2）玩视频游戏所耗费时间百分比
（3）每周消费的冰激淋公升数
约会网站原始数据
每年获得的飞行常客里程数 | 玩视频游戏所耗费时间百分比 | 每周消费的冰激淋公升数 | 样本分类 | |
1 | 400 | 0.8 | 0.5 | 1 |
2 | 134000 | 12 | 0.9 | 3 |
3 | 20000 | 0 | 1.1 | 2 |
4 | 32000 | 67 | 0.1 | 2 |
在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式：训练样本矩阵和类标签向量。
准备数据：归一化数值
如果想要计算样本3和样本4之间的距离，可以使用下面的方法：
我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响远远大于其他两个特征——玩视频游戏和每周消费冰激淋公升数——的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。
在处理这种不同取值范围的特征值时，我们通常采用的方法是将数据值归一化，如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转为为0到1区间内的值：
newValue = (oldValue - min)/(max - min)
其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。
测试算法：作为完整程序验证分类器
机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。需要注意的是，10%的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定目的来排序，所以我们可以随意选择10%数据而不影响其随机性。
我们可以改变分类器参数：测试样本所占总样本的百分比、k邻近算法中的k值，检测错误率是否随着变量值的变化而增加。依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。
如果可以正确地预测分类（错误率仅仅为2.4%），我们会给海伦一小段程序，海伦完全可以输入未知对象的属性信息，由分类软件来帮助她判定某一对象的可交往程度：讨厌、一般喜欢、非常喜欢。
3.手写识别系统
为了简单起见，这里构造的系统只能识别数字0到9。需要识别的数字已经使用图形处理软件，处理成相同的色彩和大小：宽高是32像素*32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。
实际图像存储在两个子目录内：目录trainingDigits中包含了大约20000个例子，每个数字大约有200个样本；目录testDigists中包含了大约900个测试数据。我们使用目录trainingDigists中的数据训练分类器，使用目录testDigists中的数据测试分类器的效果。
我们必须将图像格式化处理为一个向量。我们将把一个32*32的二进制图像矩阵转换为1*1024的向量，这样分类器就可以处理数字图像信息了。将这些数据输入到分类器，检测分类器的执行效果。
实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做20000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢？k决策树就是k-邻近算法的优化版，可以节省大量的计算开销。
通过微信学习的知识只能是碎片化的知识，作为新时代的我们希望能够构建自己的知识结构，使我们的知识体系化，系统化，以后在遇到碎片化的知识，我们做的只是融合到自己的知识结构中，故我们将推出“与LSGO一起学”系列课程，帮助大家来构建知识框架，初步规划有：
“与LSGO一起学C++”；
“与LSGO一起学C#”；
“与LSGO一起学Matlab”；
“与LSGO一起学数据结构”；
“与LSGO一起学设计模式”；
“与LSGO一起学可视化建模语言（UML）”；
“与LSGO一起学线性代数”；
“与LSGO一起学高等数学”
“与LSGO一起学概率论与数理统计”；
“与LSGO一起学抽象代数；
“与LSGO一起学点集拓扑”
“与LSGO一起学数字图像处理”；
“与LSGO一起学智能计算”；
如果对这些内容感兴趣，可以一起来学习讨论。
我们的官网： www.lsgogroup.com
联系客服
