人工智能 第二版 课件 第5、6章 统计机器学习方法、神经网络与深度学习

第五章统计机器学习方法5.1统计学习方法统计学习方法在人工智能历史上的作用属于机器学习的一种方法引导人工智能走出低谷让人工智能真正走向实用机器学习如果一个系统能够通过执行某个过程改进它的性能，这就是学习——司马贺（赫伯特·西蒙）统计机器学习通过运用数据及统计方法提高系统性能的机器学习运用统计方法，从数据出发提取数据的特征，抽象出问题的模型，发现数据中所隐含的知识，最终用得到的模型对新的数据进行分析和预测统计学习方法分类有监督学习（分类）统计学习方法分类无监督学习（聚类）统计学习方法分类半监督学习统计学习方法分类弱监督学习不完全监督：很少的标注样本统计学习方法分类弱监督学习不确切监督：标注对象不明确统计学习方法分类弱监督学习强化学习：试错和收益延迟统计学习方法本篇讲授内容监督学习无监督学习5.2朴素贝叶斯方法朴素贝叶斯方法是一种基于概率的分类方法基本思想：对于一个以若干特征表示的待分类样本，依次计算样本属于每个类别的概率，其中所属概率最大的类别作为分类结果输出贝叶斯方法

贝叶斯方法

独立性假设假设特征是独立的

朴素贝叶斯方法引入独立性假设后的贝叶斯方法称作朴素贝叶斯方法消除了特征取值的组合爆炸问题

举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

举例

平滑因样本不足可能存在的概率为0问题拉普拉斯平滑假设每一种情况都至少出现一次

拉普拉斯平滑举例：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

朴素贝叶斯方法应用举例文本分类问题设有体育、财经、政治和军事4个新闻类别，新来一个新闻稿件，应该属于哪个类别呢？两个过程训练过程：计算概率分类过程：依据朴素贝叶斯方法对新来的稿件分类语料库的建立收集足够多的新闻稿件，每个稿件为一个训练样本，标注好所属的类别依据语料库计算概率朴素贝叶斯方法应用举例概率计算采用拉普拉斯平滑方法例如：

朴素贝叶斯方法应用举例概率计算以单词为特征例如：

朴素贝叶斯方法应用举例分类过程对数形式：

5.3决策树决策树是一种分类方法例：根据饮食习惯判断是哪里人一些概念树结构节点根节点叶节点：类别非叶节点：特征父节点子节点如何构建决策树？训练集（数据集）根据训练集构建一个决策树ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性如何构建决策树同一个数据集可以构建不同的决策树如何构建决策树如何评价？决策树尽可能与训练集一致更好的泛化能力组合爆炸问题不可能建立所有可能的决策树，再从中选择一个最好的如何构建决策树启发式方法优先使用分类效果好的特征特征的效果依赖于数据集特征的评价数据集的熵熵是对数据集混乱程度的评价例：一个数据集中70%男生，30%女生一个数据集中50%男生，50%女生

特征的评价

特征的评价信息增益对数据集D实施特征A后，熵的下降程度信息增益可以评价特征的分类能力信息增益越大的特征分类能力越强信息增益越小的特征分类能力越弱

信息增益计算举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

5.3.1决策树算法——ID3算法ID3是一个按照信息增益选择特征的决策树算法基本思想：每次选择一个信息增益最大的特征，逐节点建立决策树ID3算法举例初始数据集D={1,2,…,15}ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例年龄特征的条件熵按照年龄取值将D划分为3个子集{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}分别计算三个子集的熵：年龄的条件熵：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例年龄特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例发长特征的条件熵按照发长取值将D划分为3个子集{1,2,5,6,7,12,14},{3,9,10,15},{4,8,11,13}分别计算三个子集的熵：发长的条件熵：ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例发长特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例同理得到鞋跟、服装的信息增益对比4个特征的信息增益ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例选择鞋跟特征，将数据集D划分为D1、D2

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

ID3算法举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性ID3算法举例ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

5.3.2决策树算法——C4.5算法C4.5是对ID3决策树算法改进ID3算法存在的问题倾向于选择取值多的特征当特征取值多时，D被划分为多个子数据集，每个子数据集中的样本数可能比较少，里面只包含单一类别样本的可能性就比较大，这样就会导致条件熵比较小，从而使得信息增益比较大极限情况下，特征A的取值特别多，以至于每个样本都有一个不同的取值，这样每个子数据集就只含有一个样本，每个子数据集的类别都是确定的。比如：以毫米为单位的发长特征本质上还是数据量不足

C4.5算法改进思想“相对”信息增益——信息增益率用信息增益率代替信息增益选择特征分离信息也是一种熵按照特征取值计算概率

C4.5算法信息增益率计算举例

ID年龄发长鞋跟服装性别1老年短发平底深色男性2老年短发平底浅色男性3老年中发平底花色女性4老年长发高跟浅色女性5老年短发平底深色男性6中年短发平底浅色男性7中年短发平底浅色男性8中年长发高跟花色女性9中年中发高跟深色女性10中年中发平底深色男性11青年长发高跟浅色女性12青年短发平底浅色女性13青年长发平底深色男性14青年短发平底花色男性15青年中发高跟深色女性

C4.5算法

C4.5算法计算举例ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法

ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法

ID发长（厘米）类别12男性24男性310女性420女性

C4.5算法注意：特征取连续值时，并不是只能使用一次。发长>7?D1是不是D2C4.5的不足倾向于取值不平衡的特征改进方法从n个信息增益大的特征中选择信息增益率最大的特征n的确定：信息增益大于平均值的特征5.3.3决策树：过拟合与剪枝过拟合问题决策树节点数错误率训练集错误率验证集错误率恰拟合过拟合欠拟合N剪枝方法DD2D1D22D21D23D12D11D13DD2D1D22D21D23如何评价剪枝是否有效？

剪枝方法举例

剪枝方法举例

简直方法举例

剪枝方法举例5.3.4随机森林算法决策森林“三个臭皮匠顶个诸葛亮”随机森林利用有限数据建立尽可能不同的决策树重复采样特征采样…数据采样决策树决策树决策树特征采样特征采样特征采样随机森林投票机制随机森林森林大小太小投票机制作用有限太大决策树之间缺乏独立性合适的大小错误率最小集外数据的利用集外数据约占37%利用集外数据测试错误率确定最小错误率时的森林大小重复采样约37%不被采集5.4k近邻方法k近邻一种分类方法基本思想物以类聚相近的样本属于同一个类别的概率大发长鞋跟高度男性女性xyba男性女性k近邻方法存在噪声时变得不可靠解决办法：看周围k个样本发长鞋跟高度男性女性xak近邻方法k值的影响发长鞋跟高度男性女性xk=1,女性k=3，男性k=5，女性k=11，男性距离计算

k近邻方法举例ID特征1特征2特征3类别10.71.20.9a21.51.30.8a31.10.81.2a40.91.10.7a51.21.41.3a60.23.50.3b70.34.10.7b80.33.21.2b90.12.80.5b100.73.31.1b112.80.21.1c123.10.51.5c134.51.21.3c144.10.90.9c152.90.71.2cx=(3.5,3.3,0.8)？距离3.502.833.493.413.023.343.303.233.452.823.192.912.382.482.70排序155141271110913486123k近邻方法的特点是一种不需要训练的方法直接存储训练样本简单有效当训练样本足够多时具有比较好的性能效率问题需要计算与每个样本的距离5.5支持向量机（SVM）什么是支持向量机？一种分类方法适用于二分类可以通过多个支持向量机的组合实现多分类支持向量机yxABCD最大间隔yABx间隔间隔最大间隔最优分界面支持向量与支持向量机yxAabcdea、b、c、d、e称作支持向量，唯一决定了最优分界面。这样得到的二分类器称作支持向量机。几个基本概念

几个基本概念决策函数

yAabcde

x正类负类yAabcde

x正类负类几个基本概念

几个基本概念函数间隔的特点超平面方程与函数间隔同一个超平面可以对应不同的函数间隔

几个基本概念几何间隔归一化的函数间隔实质就是点到平面的欧氏距离

几个基本概念几何间隔与函数间隔的关系训练集T到超平面(w.b)的函数间隔训练集T到超平面(w.b)的几何间隔

5.5.2线性可分支持向量机支持向量机分类线性可分支持向量机线性支持向量机非线性支持向量机线性可分支持向量机yAx

线性可分支持向量机给定训练集T：求解：用函数间隔表示：

线性可分支持向量机

线性可分支持向量机线性可分支持向量机求解

线性可分支持向量机求解

满足约束条件时≤0

>0

线性可分支持向量机求解原始问题：对偶问题：一般来说二者并不等价例：A、B最高，C、D最小，并假定B年龄小于A，C身高大于D身高最高的同学中年龄最小的同学：B年龄最小的同学中身高最高的同学：C年龄角度、身高角度均有：C≤B

线性可分支持向量机求解

对偶问题原始问题线性可分支持向量机求解

KKT条件在满足KKT条件下，原始问题与对偶问题等价线性可分支持向量机求解

KKT条件在满足KKT条件下，原始问题与对偶问题等价线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解

线性可分支持向量机求解如何得到超平面方程？

求解举例例：

设有正样本x1=(3,3)、x2=(4,3)，y1=y2=1，负样本x3=(6,4)，y3=-1

求该问题的最优分界面，并据此给出样本(1,1)所属的类别。

最小值在边界上

样本x=(1,1)为正类☆回顾：线性可分支持向量机5.5.3线性支持向量机yx函数间隔0.9函数间隔0.1abc

线性支持向量机

线性支持向量机

线性支持向量机yx函数间隔=1

总结

5.5.4非线性支持向量机

非线性支持向量机

非线性支持向量机原空间的椭圆方程变换后的空间成为平面方程

非线性支持向量机线性支持向量机新空间超平面方程

非线性支持向量机

举例设x1=(0,0)、x2=(1,1)属于正类，x3=(1,0)，x4=(0,1)属于负类选择变换

11

非线性支持向量机

5.5.5核函数与核方法回顾：非线性支持向量机

核函数

核方法求解非线性支持向量机通过核函数在原空间计算变换后空间的点积不需要知道变换函数非线性支持向量机

变换后空间的超平面原始空间的超曲面决策函数

常用核函数多项式核函数最优分界超曲面方程分类决策函数

常用核函数高斯核函数最优分界超曲面方程分类决策函数

常用核函数sigmoid核函数最优分界超曲面方程分类决策函数

支持向量机的过拟合问题

举例

待分类样本x=(0,1)所属的类别：

待分类样本x=(0,1)为负类

x1x2x311-1-1

支持向量机总结非线性支持向量机线性支持向量机线性可分支持向量机

5.5.6支持向量机用于多分类问题支持向量机是二分类器如何求解多分类问题呢？支持向量机用于多分类问题

一对一法示意图类2、类3分类器类2得1票、类3的2票类2得2票、类3的1票类3类1

类2类3类2类1

一对一法的特点

支持向量机用于多分类问题一对多法K个类别，每个类别做正类，其余K-1个类别合并在一起做负类，共构建K个支持向量机类2类3类1

xzy红色：正蓝色：负类2类3类1

一对多法的特点比较少的分类器K（>3）个类别，K个分类器样本不平衡问题正类少，负类多解决方法对正负两类样本设置不同的参数C

支持向量机用于多分类问题层次法从根节点开始，每次划分为两个类别类1～类4类1～类2类3～类4类1类2类3类4层次法的特点

附录B支持向量机求解算法SMO

B.1SMO算法的基本思想梯度下降法

梯度下降法示意图SMO算法的基本思想

SMO算法的基本思想坐标下降法一次只修改一个变量SMO算法的基本思想

坐标下降法示意图

SMO算法的基本思想

SMO算法的基本思想

SMO算法的基本思想

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

裁剪方法

SMO算法KKT条件y

SMO算法基本思想小结

B.2SMO算法的详细计算过程

根据上一讲的结果：

更新偏置b

更新偏置b

更新偏置b

更新偏置b

根据定义：有：

SMO算法5.6K均值聚类算法聚类问题按形状按大小按颜色c聚类结果与选择的特征有关K均值聚类算法几个类别？朴素的想法类内样本越是紧密地簇

拥在一起聚类效果越好如何衡量？类别内样本之间的距离K均值聚类算法

K均值聚类算法

K均值聚类算法N个样本数、K个类别，所有可能的聚类方案数（含一个类别中样本为0的情况）

……N个样本K个类别每个样本K个可能有K!种排列

K均值聚类算法如何做到J最小？当知道类中心时，每个样本归到最近的类中心如何得到类中心？

K均值聚类算法

K均值聚类举例

假定选择x1、x2、x3分别为类1、类2、类3的中心聚类结果第一类：x1第二类：x2、x5第三类：x3、x4、x6

x1x2x3x4x5x6类10126362934类21025372025类3262502252020202000

聚类结果第一类：x1第二类：x2、x5第三类：x3、x4、x6

类中心第一类：(2,2)第二类：(3,5)第三类：(6.7,4)

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(3,5)(6.7,4)类1类3类2

x1x2x3x4x5x6类10126362934类2105203458类325.822.81.15.816.111.8类中心第一类：(2,2)，第二类：(3,5)，第三类：(6.7,4)

聚类结果第一类：x1、x2第二类：x5

、x6第三类：x3、x4011.15.858

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(3,5)(6.7,4)类1类3类2聚类结果第一类：x1、x2第二类：x5

、x6第三类：x3、x4

24682468(2,3)(2,2)(8,2)(7,3)(4,7)(5,7)

(4.5,7)(7.5,2.5)类1类3类2(2,2.5)二分K均值聚类算法K均值算法存在的问题聚类结果与初始选择的类别中心有关采用多次聚类选择J值最小的聚类结果效率问题二分K均值聚类算法先聚类两个类别从已有聚类结果中选择一个类别将其聚类成两个类别直到得到K个类别为止可一定程度上缓解初始类别中心选择问题二分K均值聚类算法如何选择一个类别再聚类？选择使J值最大降低的类别如何确定K？最小化J？一个样本一个类别时J=0

No！如何确定K？拐点法逐渐增加K值，寻找J下降的拐点K选择为45.7层次聚类算法数据的层次性层次聚类算法自底向上聚类初始化：每个样本为一个类别合并两个最相似的类别重复第2步，直到聚成了K个类别或者聚成一个类别为止。层次聚类示意图层次聚类算法层次聚类算法举例abcdefgh距离度量中心距离法以两个类别中心的距离作为两个类别之间距离的度量平均距离法以两个类别中任意两个样本间距离的平均值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最小距离法以两个类别中任意两个样本间距离的最小值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最大距离法以两个类别中任意两个样本间距离的最大值作为两个类别之间距离的度量（两个样本分别来自不同的类别）。最小距离法与最大距离法效果对比最小距离法最大距离法5.8DBSCAN聚类算法数据有梳有密、形态不一可能含有噪声DBSCAN：一种基于密度的聚类方法DBSCAN聚类算法如何评价一个样本所处位置的密度？DBSCAN聚类算法核心样本以某个样本p为圆心、r为半径做圆，圆内至少包含有minPts个样本，则称p为核心样本。圆内的任一样本q称作被p包含，或者说q相对p来说直接可达。DBSCAN聚类算法边界样本被核心样本包含的非核心样本称作边界样本DBSCAN聚类算法异常样本如果一个样本既不是核心样本，也不被任何核心样本所包含，则称该样本为异常样本。异常样本说明该样本处于一个比较稀疏的区域，大概率是一个噪声样本。DBSCAN聚类算法选取一个核心样本p，将p所包含的所有样本加入到类c中，标记样本p被处理过从类c中依次选取没有处理过的核心样本q，并将q所包含的样本加入到类c中，标记样本q被处理过在这个过程中，类c中的样本逐渐增加，新增加的样本有核心样本也有非核心样本重复以上过程，直到类c中所有核心样本被标记处理过，则完成了第一个类别的聚类，类c中的所有样本为一个类别再选取一个没有被处理过的核心样本，按照上述方法完成聚类依次进行下去，直到所有的核心样本被处理完，则结束聚类，剩下的异常样本被认作是噪声DBSCAN聚类算法——举例假定minPts=3

给定了半径rabcdefghijkmnabcdefghijkmn核心样本：c类1：c,d,e类1：c,d,e类1：c,d,e,f类1：c,d,e,f,g类1：c,d,e,f,gabcdefghijkmn核心样本：j类2：j,i,k类2：j,i,k,m类1：c,d,e,f,g类2：j,i,k类2：j,i,k,mabcdefghijkmn类1：c,d,e,f,g类2：j,i,k,m噪声：a,b,h,n总结优点可以发现任意形状的聚类可以处理噪声样本不需要给定聚类个数对数据输入顺序不敏感缺点需要给定minPts和半径r难于处理密度差异过大的聚类边界点具有不确定性属于哪个类别可能取决于处理顺序聚类质量依赖于参数选择cdefgijkmncdefgijkmminPts=4总结优点可以发现任意形状的聚类可以处理噪声样本不需要给定聚类个数对数据输入顺序不敏感缺点需要给定minPts和半径r难于处理密度差异过大的聚类边界点具有不确定性属于哪个类别可能取决于处理顺序聚类质量依赖于参数选择5.9验证与测试问题问题的提出超参数的确定比如支持向量机中高斯核函数σ的确定性能测试数据集训练集验证集测试集验证与测试问题数据不足的问题实际问题中面临采集困难问题交叉验证（k折交叉验证）将数据划分为k等份，使用其中的k-1份作为训练集，1份作为验证集k份数据轮流使用余一法k为数据集的数据个数性能评价指标常用的评价指标（分类问题为例）准确率召回率F1指标两大类评价指标宏指标从类别的角度微指标从样本的角度准确率类别i的准确率Pi宏平均准确率Macro_P微平均准确率Micro_P

召回率类别i的召回率Ri宏平均召回率Macro_R微平均召回率Micro_R对于分类问题

F1值类别i的F1值为该类别准确率与召回率的调和平均值宏平均F1值两种计算方法

F1值微平均F1值是微平均准确率和微平均召回率的调和平均值对于分类问题

性能评价指标宏平均指标受测试样本中不同类别样本的比例影响比较小，应用的更多一些当没有明确说明时，大多指宏平均指标5.10特征抽取问题（一）特征对于统计机器学习方法的重要性什么是特征？土士短长特征抽取问题特征对于统计机器学习方法的重要性什么是特征？清请三点水言字旁如何寻找计算机能处理的特征？两个例子脱机手写体汉字识别文本分类例1：脱机手写体汉字识别方向线素特征8×8=64个区域

每个区域4种特征组成256维的特征向量例1：脱机手写体汉字识别存在的问题手写汉字规范性差大小不一笔画位置、长短变化大影响识别效果解决办法非线性归一化软划分与模糊化例1：脱机手写体汉字识别非线性归一化方法例1：脱机手写体汉字识别软划分与模糊化硬划分软划分模糊化中间权重大，四周权重小模糊方向线素特征8×8=64个区域

每个区域4种特征组成256维的特征向量例1：脱机手写体汉字识别细化问题抽取笔画的骨架例1：脱机手写体汉字识别解决办法以汉字轮廓代替骨架在轮廓上抽取方向线素特征《四库全书》数字化《四库全书》数字化乾隆年间纪晓岚组织3000多人手工抄写历时10年完成。国家图书馆文津阁《四库全书》，共有36304册，分装于6144个木质书函，摆放在128个书架上。全书共8亿字，缩印成四分之一后影印版重达2.5吨。5.10特征抽取问题（二）文本分类问题比如：将新闻自动分类为体育、经济、军事、政治4个类别基于内容分类内容理解难度大、耗时、计算资源要求高、成本高基于特征分类容易实现、快速、计算资源要求低关键问题如何抽取文本的分类特征词袋模型假设文本的类别只与文中包含的词有关，而与词的位置无关例：北京国安战胜广州恒大

广州恒大战胜北京国安词袋模型词袋模型为什么称作词袋模型？文本的表示：词频特征tf

文本的表示：词频特征tf词频特征存在的问题常用词的作用被放大我们、他们、的、地、得……解决思路人工筛选词表对词频加权重越是少数文本中出现的词汇权重越大，越是多数文本出现的词汇权重越小文本的表示：tf-idf特征

第六章神经网络与深度学习第六章神经网络与深度学习神经网络发展历史深度学习图象识别2011语音识别什么是神经网络？人工神经元网络（ANN或者NN）6.1从数字识别谈起数字3的图像数字8的图像数字3的模式模式匹配·=

数字3、数字8与模式3的匹配·=143·=115存在的问题笔画多少带来的问题1的笔画少8的笔画多如何评判匹配的程度？使用Sigmoid函数

增加偏置项通过增加偏置项让sigmoid函数平移

netnet+b(b<0)

net

net+b(b<0)

-1414增加偏置项

图示表示

神经元神经网络模式3模式8

神经网络

数字识别神经网络

y4y6……

y5y1y3y2y8y0y9y7神经网络的横向扩展——增加模式y3y8……

神经网络的纵向扩展——局部模式相同不相同让神经网络更深——模式组合……

３的右部３的左部８的右部８的左部多层神经网络输入层输出层隐含层隐含层

……………………如何获得模式？模式通过神经元的连接权重表示通过训练样本，自动学习权重，也就是模式不是人工设计！学习到的模式是一种隐含表达，并不像我们举例的这样清晰6.2神经元与神经网络

∑b…x1x2xnw1w2wnonet

神经元

神经元的向量表示

激活函数

激活函数

激活函数

激活函数

激活函数

输入层输出层隐含层

………………

softmax全连接网络术语：全连接网络，前馈网络，多层感知机，全连接层，稠密层输入层输出层隐含层1隐含层2隐含层3猫狗兔鸟6.3神经网络是如何训练的输入层输出层隐含层1隐含层2隐含层3猫狗兔鸟小朋友如何认识小动物？建立数据集收集各种动物的照片不同姿势不同角度不同大小数据标注每张照片标注上动物的名称训练集与测试集样本这个是猫！这个是狗！如何训练？淋浴器示意图热水冷水水量水温w1w2感知调节++如何评价调节效果？

损失函数——误差平方和

……………………

如何训练？损失函数最小化问题

……………………

梯度下降法

梯度下降法

梯度下降法

梯度下降算法

符号说明o1oM……ok…………

g的后续

反向传播算法（BP：BackPropagation）又称作误差反向传播算法给出了一种计算偏导数的方法

o1oMx1…xj…xn……输入一个样本计算所有神经元的输出2，得到输出层神经元k的输出

ok…………

反向传播算法（BP）？该BP算法的条件具体条件不同，算法会有差异，总体思路一样全连接网络其他形式的网络随机梯度下降算法批量、小批量梯度下降算法激活函数：sigmoid函数其他的激活函数损失函数：误差平方和其他的损失函数交叉熵损失函数

输入层输出层隐含层

………………

softmax交叉熵损失函数

……………………

两种损失函数的作用误差平方和损失函数用于输出是具体数值的问题交叉熵损失函数用于分类问题小结建立数据集损失函数误差平方和、交叉熵梯度下降法批量梯度下降算法随机梯度下降算法小批量梯度下降算法BP算法随机梯度下降算法的一种实现6.4卷积神经网络全连接网络的不足连接权重过多影响训练速度影响使用速度

……………………

提取局部模式边缘信息2102395420234561231004428-101-101-101-501-1-2-58-13输出（匹配结果）权重（模式）输入(-1)*2+0*1+1*0+(-1)*9+0*5+1*4+(-1)*2+0*3+1*4=-52102395420234561231004428-101-101-101-501-1-2-58-13输出（匹配结果）权重（模式）输入2102395420234561231004428-101-101-101-501-1-2-58-13输出（匹配结果）权重（模式）输入2102395420234561231004428-101-101-101-501-1-2-58-13输出（匹配结果）权重（模式）输入卷积核卷积神经网络-局部连接-权值共享

训练获得全连接、卷积神经网络对比WWWW权值不同权值共享全连接局部连接全连接参数：5×5+9=234卷积核参数：3×3+1=10输入输出输入输出举例：边缘提取上边缘下边缘输入输出卷积核举例：边缘提取图象匹配结果加sigmoid卷积核的大小对于二维输入，一般是3×3、5×5、7×7…填充W步长步长卷积核每次移动的距离步长是可以设定的以2为例WWW多卷积核1*0+0*0+(-1)*0+(-1)*0+0*2+1*1+1*0+0*9+(-1)*5=-4输出（通道2）卷积核2(-1)*0+0*0+1*0+(-1)*0+0*2+1*1+(-1)*0+0*9+1*5=6卷积核1输出（通道1）多通道输入时的卷积3×3×36×6×3必须一致输出一个通道多通道卷积举例通道1通道2输出为一个通道3×3×2卷积核1×2+0×1+(-1)×0+(-1)×9+0×5+1×4+1×2+0×3+(-1)×4+(-1)×3+0×1+1×0+(-1)×2+0×4+1×4+(-1)×2+0×3+1×5=-3卷积核的大小小卷积核：细粒度特征大卷积核：大粒度特征多层小卷积实现大卷积两层3×3卷积等效一个5×5的卷积池化一种降维的手段最大池化取窗口内的最大值窗口大小、步长都

可以设定平均池化112451567807321041123432865331102120687344853输入为一个通道最大池化窗口：2×2步长：2神经网络应用举例LeNet神经网络VGG-16神经网络小结卷积神经网络局部连接权值共享卷积核通道池化应用举例LeNetVGG-166.5梯度消失问题神经网络遇到的两大问题梯度消失问题过拟合问题什么是梯度消失问题？

≤0.25解决思路使用ReLU激活函数ReLU的导数=1

Sigmoid的导数两个实例GoogLeNet残差网络（ResNet）GoogLeNet平均池化卷积层全连接层全连接层softmax平均池化卷积层全连接层全连接层softmax平均池化卷积层全连接层softmax输入高楼供水系统GoogLeNet输入Inception模块Inception模块192个通道32个卷积核参数个数：(5×5×192+1)×32=153,632降维的Inception模块

192个通道32个卷积核参数个数：(1×1×192+1)×32+(5×5×32+1)×32=31,80832个卷积核1×1卷积核？Inception模块说明：每个Inception的参数有所不同，这是其中的一个64个1*1卷积28*28*6428*28*19296个1*1卷积28*28*96128个3*3卷积28*28*12832个1*1卷积28*28*3232个5*5卷积28*28*32填充1步长1最大池化28*28*19232个1*1卷积28*28*3228*28*25664+128+32+32=2567×7平均池化步长为1，无填充5×5平均池化步长为3，无填充GoogLeNet为什么称作Inception?“我们需要更加深入！”

“Weneedtogodeeper!”残差网络（ResNet）神经网络的退化现象k层神经网络

k+1层

解决思路k层神经网络

k+1层

k+1层

残差模块F(X)

X

F’(X)=F(X)+X

恒等映射

残差模块3×3卷积步长为1填充为1通道数、通道大小必须一致残差网络（ResNet）输入:224×224×3

输出：1000

64个7×7卷积核，步长为2，填充为3。3×3最大池化，步长为2。3个残差模块64个3×3卷积核，步长为1，填充为1。128个3×3卷积核，步长为1，填充为1。256个3×3卷积核，步长为1，填充为1。512个3×3卷积核，步长为1，填充为1。虚线步长为2，长宽各减一半，通道数增加了一倍。恒等映射需要等维处理。全局平均池化小结梯度消失问题ReLU激活函数GooLeNet三个输出Inception模块同时使用不同大小的卷积核1×1卷积降维残差网络（ResNet）退化问题残差模块恒等映射学习残差6.6过拟合问题神经网络遇到的两大问题梯度消失问题过拟合问题什么是过拟合问题？xf(x)什么是过拟合问题？xf(x)过拟合欠拟合希望结果神经网络的过拟合问题减少过拟合的方法：正则化项法

正则化项的作用：降低模型复杂性

xf(x)

L2（2-范数）正则化项效果：很多参数值很小，但基本不会为0。抗干扰能力强。L1（1-范数）正则化项

减少过拟合的方法：舍弃法（Dropout）随机地临时舍弃一些神经元输出输入减少过拟合的方法：数据增强法数据越多，过拟合的风险就越小xf(x)如何获得更多的数据？数据增强通过各种变换增加数据的数量图象数据缩放、旋转、局部截取、改变颜色等《四库全书》数字化中用到的非线性数据增强方法方法小结过拟合问题解决方法利用测试集（验证集）限制模型的复杂性正则化项法舍弃法增加数据量数据增强6.7词向量神经网络如何处理文本问题？如何表示词如何表示文本独热（one-hot）编码

第i个元素独热编码举例文本：我在清华大学学习，生活在美丽的清华园中词表：{我，在，清华大学，学习，生活，美丽的，清华园，中}独热表示：“清华大学” =[0,0,1,0,0,0,0,0]“清华园” =[0,0,0,0,0,0,1,0]“美丽的” =[0,0,0,0,0,1,0,0]独热编码的特点优点编码简单缺点编码太长无法度量词之间的相似性

词的分布式表示独热编码稀疏向量分布式表示稠密向量[-0.85,2.3,1.5,-0.54,0.77,...]植物动物食物熊猫白菜猪羊词：(<动物>，<植物>，<食物>)猪：(1.0,0.1,1.0)羊：(1.0,0.2,1.0)熊猫：(1.0,0.3,0.0)白菜：(0.0,1.0,1.0)竹子：(0.0,1.0,0.1)竹子词的分布式表示独热编码稀疏向量分布式表示稠密向量[-0.85,2.3,1.5,-0.54,0.77,...]词向量词嵌入把词向量从高维空间嵌入到低维空间中的一个方法语言模型

前n-1个词语言模型p(系|清华大学计算机)大p(学院|清华大学计算机)中p(大学|清华大学计算机)小语言模型语言模型举例2元模型

“清华大学计算机系”p(清华大学计算机系)=p(大学|清华)×p(计算机|大学)×p(系|计算机)神经网络语言模型

神经网络前n-1个词

前n-1个词窗口为n

神经元个数等于词表长度Kn-1个m维向量拼接成的m(n-1)维向量H个神经元每个词对应m个输入，共n-1组全连接全连接

词向量，训练得到如何训练神经网络语言模型？样本设有句子：“清华大学计算机科学与技术系”当窗口为5时，可以得到3个训练样本：清华大学计算机科学与大学计算机科学与技术计算机科学与技术系如何训练神经网络语言模型？

如何训练神经网络语言模型？

如何训练神经网络语言模型？

如何训练神经网络语言模型？

似然函数对数似然函数如何训练神经网络语言模型？

如何训练词向量？遗留问题x1x2x3w1

w3

w2

1w1

w3

w2

x1

x2

x3

如何训练词向量词向量（词嵌入）的性质二者