Ch 10. 决策树 1

特征类型 数值数据（numerical data） 标称数据 （nominal data） 例：{1.2, 4.5, 3.3} 模式间可以计算距离度量 基于度量的模式分类方法 标称数据 （nominal data） 例：{红色，有光泽，甜，小} 模式间没有距离的概念 非度量方法

决策树 什么是决策树？ 决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别 决策树的构成 根节点（root） 分支（branch） 叶节点（leaf）

决策树

决策树 决策树分类过程 从根节点开始，首先对某一属性的取值提问 与根节点相连的不同分支，对应这个属性的不同取值 Color? 与根节点相连的不同分支，对应这个属性的不同取值 green; yellow; red; 根据不同的回答，转向相应的分支 green 在新到达的节点处做同样的分支判断 Size? – big. 这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记 Watermelon

决策树 决策树的判决面

决策树 决策树的优势 语义可表示性 分类速度快 可以很自然地嵌入专家的先验知识 从根节点到叶节点表示为合取式 （颜色=黄）AND（形状=细长） 香蕉 利用合取式和析取式获得某个类别的明确描述 苹果=（绿色 AND 中等大小）OR（红色 AND 中等大小） 分类速度快 只需一系列简单查询即可对模式的类别做出判断 可以很自然地嵌入专家的先验知识

决策树学习算法 决策树研究历史 第一个决策树算法称为CLS (Concept Learning System) [E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction”published by Academic Press in 1966] 真正引发决策树研究热潮的算法是ID3 [J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979] 最流行的决策树算法C4.5 [J. R. Quinlan’s book “C4.5: Programs for Machine Learning” published by Morgan Kaufmann in 1993]

决策树学习算法 决策树研究历史 通用的决策树算法CART (Classification and Regression Tree) [L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees” published by Wadsworth in 1984] 基于决策树的集成学习算法：随机森林 (Random Forests) [L. Breiman’s MLJ’01 paper “Random Forests”]

构造决策树 基本过程 从上到下，分而治之（divide-and-conquer），递归生长 最初，所有的样本都在根节点 所有属性都是标称型的（如果是连续数值型的，则需要预先离散化） 所有样本根据每次选择出的属性递归的逐渐划分开来 选择出来的属性称为一个划分（split）或测试（test）或查询 （query） 查询的选择基于启发式或者统计特征

构造决策树 基本过程 满足如下条件之一时，划分操作停止 所有落入某一节点的样本均属于同一类别 没有特征能够进一步用于划分样本集 该节点成为叶节点，标记为该类别 没有特征能够进一步用于划分样本集 该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别 没有任何样本落入某一节点 该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别

CART 分类和回归树（Classification And Regression Tree, CART) 属性的值是二值的还是多值的？即节点可以有几个分支？ 如何确定某节点处应该测试哪个属性？ 何时令某个节点为叶节点？ 如果树生长的过大，如何使其变小变简单，即如何剪枝？ 如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？

分支数目 同一个节点分出去的分支的数目称为分支系数或分支率（branching ratio） 任意决策树都可以用分支系数为2的决策树（即二叉树）来表示 二叉树是最常用的决策树形式

分支数目

分支数目

测试的选取 决策树设计的核心问题之一 基本思想： 使后继结点的数据尽可能的“纯粹” 节点N的不纯度（impurity）i(N) 当N节点上的所有模式都来自同一类时，i(N)=0； 当N节点上的模式类别分布均匀时，i(N)应很大

测试的选取 常用不纯度度量 熵不纯度（entropy impurity） Gini不纯度 误分类不纯度

测试的选取 常用不纯度度量

测试的选取 对N节点如何选择查询？ 使不纯度下降最快的那个查询！ 和 分别为左、右子节点 和 分别为左、右子节点的不纯度 和 分别为左、右子节点 和 分别为左、右子节点的不纯度 是N节点的模式划分到 的比例 如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（information gain）

信息增益 信息增益（information gain） ：节点N上样本总个数 ：其中属于 类的样本个数（i=1,2, …, m） ：属性A的第j个取值（j=1,2, …, v） 该节点处的熵不纯度 属性A将S划分为v个子集 中属于 类的样本个数为

信息增益 信息增益（information gain） 以A作为查询，生长出v个分支的信息熵 以A为查询的信息增益

信息增益 例子 训练集 S1: buys_computer= “yes”, S2: buys_computer= “no”

信息增益 根节点上的熵不纯度 age作为查询的信息熵

信息增益 age作为查询的信息增益 类似可以计算出所有属性的信息增益 age的信息增益最大，所以选择age作为根节点的查询，对训练集进行首次划分

信息增益率 信息增益作为查询选择标准的缺点： 偏向有较多不同取值的属性 为克服这一缺点，J. R. Quinlan在其著名的C4.5算法中采用信息增益率（gain ratio）作为选择标准

信息增益率 例子

Gini不纯度 ：节点N上样本总个数 ：其中属于 类的样本个数（i=1,2, …, m） ：属性A的第j个取值（j=1,2, …, v） 属性A将S划分为v个子集 中属于 类的样本个数为 中国2006年Gini系数0.47

Gini不纯度 以A作为查询，生长出v个分支的Gini不纯度 选择Gini不纯度差最大（即Gini(A)最小）的属性作为N节点的查询

Gini不纯度 例子

分支停止准则 如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“过拟合” 极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为查找表 如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差 常用分支停止准则 交叉验证 预设一个不纯度下降差的阈值 监测每个节点代表的样本数目是否小于某个阈值

分支停止准则 最小化如下指标 不纯度下降的统计显著分析 正则项 如果一个划分不能显著降低不纯度，则停止分支 Size指树的大小，包括节点数或者连接数

剪枝 剪枝（pruning） 预剪枝（prepruning）和后剪枝（postpruning） 用于消除过拟合 预剪枝即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分 后剪枝指首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝 可用交叉验证技术来确定剪掉哪些分支 剪掉使不纯度增长最小的分支 一般来讲，后剪枝性能较好，但需要更多计算量

叶节点的标记 如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点 一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点

ID3 ID3: Interactive Dichotomizer-3（交互式二分法第三版） 仅仅适用于标称（无序）数据 如果涉及实值数据，则需离散化，然后当做标称数据处理 每个划分的分支因子等于查询属性的取值个数 采用信息增益率作为选择查询的依据 算法直到所有叶节点的不纯度最小，或者没有可用于划分的属性时停止 标准版中无剪枝步骤

C4.5 C4.5: ID3算法的后继和改进 可以处理实值数据 每个划分的分支因子等于查询属性的取值个数 采用信息增益率作为选择查询的依据 首先让树充分生长，然后利用分支的统计显著性来实现剪枝 C4.5为目前最为流行的决策树算法之一

Ch 11. 聚类 36

无监督学习 有监督（supervised）学习 无监督（unsupervised）学习 训练集中每个样本都有一个类别标记 所有类别事先已知 常用于：分类、回归 无监督（unsupervised）学习 训练集中样本的类别标记未知 给定一组样本，发现其内在性质，如类别和聚类 常用于：聚类、概率密度估计

无监督学习的动机 收集并且标记大量模式往往花费巨大 在很多应用中，模式的特征会随时间而变化 希望首先在一个较小的有标记样本集上训练一个粗略的分类器，然后让这个分类器以非监督的方式在一个较大的样本集上运行 或者，用大量未标记的样本集来训练分类器，让它自动发现数据中的分组，然后用代价更高的办法（如人工）来标记这些分组 在很多应用中，模式的特征会随时间而变化 如果这种特征的变化能够被某种运行在无监督方式下的分类器捕捉到，那么分类性能将得到大幅提高

无监督学习的动机 无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备 例如：PCA降维 在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律 发现模式中内在的聚类或分组可能为分类器设计提供依据

聚类 聚类（clustering） 聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程 因为训练集样本并无类别标记，所以聚类是无监督学习过程 一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似 聚类可用作 一种独立的数据分析工具，用于分析数据的内在特性 一种数据预处理方法，为后续模式识别服务

相似性度量 “同一聚类内部的样本之间比不同聚类的样本之间更相似”基于某种定义的样本间的相似性（或不相似性）度量 两类主要的相似性（不相似性）度量 基于度量的距离标准 非度量的相似性函数 一个度量（即距离函数）需满足如下条件 非负性： 自反性： 对称性： 三角不等式：

距离度量 常用的距离度量 根据距离对样本进行聚类 最为常用的距离度量为欧氏距离，作为不相似性度量 其次为考虑数据分布的马氏距离 计算任意两个样本之间的距离 如果两个样本之间的距离小于某个阈值 ，那么这两个样本就属于同一个聚类 过大，所有样本都被分为同一个聚类 过小，每个样本都自成一个聚类

距离度量 欧氏距离 越小，每个聚类就越小，聚类个数就越多

距离度量 缩放坐标尺度引 起聚类结果的变 化

规格化 在聚类之前可先“规格化”（normalization）原始数据，以实现不变性 规格化不能滥用！ 位移和缩放不变性 旋转不变性 通过平移和缩放，使得新特征具有零均值和单位方差 旋转不变性 旋转坐标轴，使得坐标轴与样本协方差矩阵的本征向量平行 规格化不能滥用！ 零均值 单位方差

相似性函数 不使用距离，可以直接定义非度量的相似性函数 相似性函数是度量样本之间相似性的函数 常用的相似性函数 对称性 当两个样本具有某种相似性时，函数的值较大 常用的相似性函数 归一化内积（两个向量夹角的余弦） 对二值特征（0-1）来说，归一化内积相当于共享属性的相对计数，进一步，可简化为共享属性的比例

何谓好的聚类？ 一个好的聚类过程产生高质量的聚类 聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现 聚类内部相似度高 聚类之间相似度低 聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现 评价聚类结果的好坏往往具有主观性

聚类的准则函数 “一种聚类的划分比另一种划分好”基于某种聚类的准则函数 聚类问题可以看做一种离散优化问题 准则函数用于度量对数据聚类的某种划分的质量 目标是找到某种划分，使得准则函数最小（大）化 采用不同的准则函数可能得到不同的聚类结果 常用准则函数 误差平方和准则 最小方差准则 散布准则

误差平方和准则 误差平方和准则是最简单也使用最广的聚类准则函数 其中 是第i个聚类 中样本的均值 当数据点能被划分成很好的相互区分的几个聚类，并且聚类内部又很稠密时，适用误差平方和准则

误差平方和准则 采用误差平方和准则可能存在的问题 当不同聚类所包含的样本个数相差较大时，将一个大的聚类分割开来反而可能得到更小的误差平方和

最小方差准则 由于误差平方和准则度量的是样本点到聚类均值的方差，所以它是最小方差准则的一种 与误差平方和准则等价的形式 其中， 为第i个聚类中的样本个数 最小方差准则的一般形式 为某种相似性函数

散布准则 均值向量 第i个聚类的均值向量 总的均值向量

散布准则 散布矩阵 第i个聚类的散布矩阵 总的散布矩阵 聚类内散布矩阵

散布准则 散布矩阵 聚类间散布矩阵 聚类内散布矩阵和聚类间散布矩阵的关系

散布准则 为了得到更好的聚类质量，我们希望得到较小的聚类内散布和较大的聚类间散布 需要某种标量度量矩阵的“大小”，如矩阵的迹（trace，即矩阵对角线上元素之和） 由于 ，而 与如何划分聚类无关，所以，最小化 就同时最大化聚类间散布矩阵的迹 标量度量也可选用矩阵的行列式

迭代最优化 对一个有限样本集来说，可能的划分的个数是有限的，理论上可以用穷举法找到最优解。然而，穷举法因计算量过大而往往无法实现 迭代最优化方法经常用于寻求最优划分 首先开始于一些合理的初始划分 然后将某些样本从一个聚类移动到另一个聚类——如果这样做能够改善准则函数的话 重复迭代直到没有显著改善时停止 这种迭代方法可以保证收敛到局部最优，但不能保证找到全局最优

基于划分的聚类方法 给定一个数据集，基于划分的方法将数据集划分为k个子集，每个子集对应一个聚类 两种方案 典型算法 每个聚类由其所包含的样本的均值来表示 每个聚类由靠近该聚类中心的样本（中心点）来表示 典型算法 k-均值（k-means） k-medoids Medoid: 中心点

k-means算法 每个聚类由其所包含的样本的均值来表示 步骤1：随机选择k个样本作为k个聚类的中心 步骤2：对剩余的每一个样本，将其划分入中心距离该样本最近的聚类 步骤3：计算每个聚类的均值作为新的中心 步骤4：如果聚类中心没有任何改变，算法停止，否则 回到步骤2

k-means算法

k-medoids算法 每个聚类由靠近该聚类中心的样本来表示 步骤1：随机选择k个样本作为k个聚类的中心 步骤2：对剩余的每一个样本，将其划分入中心距离该样本最近的聚类 步骤3：计算每个聚类的medoid（即距离均值最近的样 本） 步骤4：如果聚类的medoid没有任何改变，算法停止， 否则回到步骤2

k-medoids算法

小结 特征类型 决策树 数值数据（numerical data） 标称数据 （nominal data） 根节点（root） 基于度量的模式分类方法 标称数据 （nominal data） 非度量方法 决策树 根节点（root） 分支（branch） 叶节点（leaf）

小结 构造决策树 分支数目 测试的选取 信息增益 信息增益率 Gini不纯度 剪枝 预剪枝 后剪枝

小结 根据训练样本是否有类别标记，学习算法分为 聚类（clustering） 有监督（supervised）学习 无监督（unsupervised）学习 聚类（clustering） 聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程

小结 聚类算法 迭代最优化聚类算法 基于划分的聚类方法 k-均值（k-means） k-medoids

回顾 神经网络 前馈神经网络 简单感知器 多层前馈神经网络 多层前馈神经网络的表达能力 神经元 连接神经元的权值 偏置单元 任何判别函数都能由一个三层神经网络实现

回顾 反向传播算法 隐含层到输出层的权值更新 输入层到隐含层的权值更新 训练协议 在线训练 随机训练 成批训练

回顾 随机优化方法 依赖随机性所起的关键作用，使搜索朝着预期最优解的区域前进，同时允许一定程度的随机扰动，以利于发现最优解 模拟退火 基于统计力学的概念和技术 遗传算法 基于生物学概念，尤其是进化论的数学描述

回顾 模拟退火 随机状态转移 Metropolis准则

回顾 遗传算法 三种基本操作 基本过程 复制（replication） 交叉（crossover） 变异（mutation） 编码 生成种群 计算适应度 选择 交叉 变异

回顾 特征类型 决策树 数值数据（numerical data） 标称数据 （nominal data） 根节点（root） 基于度量的模式分类方法 标称数据 （nominal data） 非度量方法 决策树 根节点（root） 分支（branch） 叶节点（leaf）

测试的选取 常用不纯度度量 熵不纯度（entropy impurity） Gini不纯度 误分类不纯度

信息增益 信息增益（information gain） 以A作为查询，生长出v个分支的信息熵 以A为查询的信息增益