第2章 K-近邻算法-【千锋教育】Python快乐编程——机器学习从入门到实战同步教案

课程名称 第2章 K-近邻算法 计划学时 2学时 内容分析 本章主要介绍K-近邻算法概述、K-近邻算法的实现：KD树、实战：利用K-近邻算法改进约会网站 教学目标 与教学要求 要求学生理解K-近邻算法的概念、掌握近邻的距离度量表示法、掌握KD树的构建方法、掌握通过K近邻算法实现改善约会网站配对效果的方法 教学重点 K-近邻算法的实现：KD树、实战：利用K-近邻算法改进约会网站 教学难点 K-近邻算法的实现：KD树、实战：利用K-近邻算法改进约会网站 教学方式 课堂讲解及ppt演示 教 学 过 程 第一课时 （K-近邻算法概述） 了解Python机器学习知识 1.介绍本书，引出本课时的主题 古语“近朱者赤, 近墨者黑”反映了一种有意思的社会现象: 长期接触好人可能促使人变好, 长期接触坏人可能促使人变坏。 这在一定程度上反映了一种现象: 坏人身边的人也是坏人的可能性比较大, 好人身边的人也是好人的可能性比较大。 在数据的分类上, K-近邻算法便利用了这种现象来解决分类问题。 假设小张与邻里之间具有多个相同的特征, 通过对小张的多个邻居的特征标签进行分析得出: 小张的10 个邻居中有8 个喜欢玩麻将。那么, 在这种环境下, 小张喜欢玩麻将的可能性就非常高。 虽然这种推导关系在现实生活中 并不总是成立, 但在解决数据的分类问题时往往很实用。 本章将学习 K-近算法的有关知识, 了解这种常见分类算法的基本概念和使用方法。 2.明确学习目标 （1） 能够K-近邻算法的基本思想 （2） 能够掌握K-近邻的距离度量表示法 （3） 能够掌握K值的选择 知识讲解 · K-近邻算法的基本思想 接下来, 通过一个示例图来帮助大家理解 K-近邻算法的思想, 如图所示。 图中数据x 是没有标签的新数据, 经过与样本集中的数据比较后, 使用算法提取出5 个与数据x 最近的分类标签, 其中圆形标签有4 个( 数量多于三角形标签), 因此将数据x 归类为与圆形标签相同的类型。 从本节的介绍中不难看出, 在 K-近邻算法中有三个基本要素: 距离的度量、K 值的选择以及分类决策规则。K-近邻算法中分类规则一般采用多数表决的方式, 即由K 个近邻训练数据中多数类决定输入数据所属的类。 多数表决规则等价于经验风险最小化规则。 · K-近邻的距离度量表示法 K-近邻算法的核心在于找到新数据的最近邻所属的分类标签。 在特征空间中, 两个数据点的距离可反映两个数据点之间的相似性程度, 因此距离的度量是 K-近邻算法的关键。K-近邻算法的特征空间一般是n 维实数向量空间, 数据之间的距离可以通过欧几里得距离(简称欧氏距离) 公式(或其他类型距离公式) 计算求得。 本节将讲解几种常用的距离度量方法, 包括欧氏距离、 曼哈顿距离、 切比雪夫距离、 闵可夫斯基距离和标准化欧氏距离等。 在距离的计算中经常会用到SciPy 工具包distance 模块中的pdist() 函数。 1. 欧氏距离 欧氏距离是最常见的两点之间或多点之间的距离表示法。 它定义于欧几里得空间中,在二维空间中点(x1 ,y1 ) 和(x2 ,y2 ) 之间的欧氏距离公式如下所示。 ρ = (x2 -x1 )2 +(y2 -y1 )2 三维空间中点(x1 ,y1 ,z1 ) 和(x2 ,y2 ,z2 ) 之间的距离公式如下所示。 ρ = (x2 -x1 )2 +(y2 -y1 )2 +(z2 -z1 )2 两个n 维向量(x11 ,x12 ,…,x1n ) 与(x21 ,x22 ,…,x2n ) 间的欧氏距离表达式如下所示。ρ = ∑n k=1(x2k -x1k )2 计算二维空间中点v1 = (1 ,2) 和v2 = (3 ,4) 间的距离, 使用 Python 实现的过程具体如例所示。 2. 曼哈顿距离 假如在曼哈顿街头, 想要从一个街区开车穿过复杂的地形到达另外一个街区, 行驶路线往往不可能是直线, 因为城区中会有建筑物的阻碍。 两个位置间的行车实际距离就是“曼哈顿距离”, 曼哈顿距离 也 称 为 城 市 街 区 距 离 (city block distance )。图中连接两个黑点的直线距离为欧氏距离, 而另外三种折线距离则属于曼哈顿距离。 3. 切比雪夫距离 切比雪夫距离(Chebyshev distance) 是向量空间中的一种距离度量, 两个点之间的距离为其坐标数值差的最大值。 若将国际象棋棋盘放在二维直角坐标系中, 格子的边长定义为1 , 坐标系的x 轴及y 轴与棋盘上的方格平行, 原点恰好落在棋局某一格的中心点处, 则“王”从一个位置走到其他位置需要的步数恰为两个位置间的切比雪夫距离, 因此切比雪夫距离也称为棋盘距离。 具体如图所示。