通用的决策树算法CARTClassificati课件

Ch10.决策树Ch10.决策树特征类型数值数据（numericaldata）例：{1.2,4.5,3.3}模式间可以计算距离度量基于度量的模式分类方法标称数据（nominaldata）例：{红色，有光泽，甜，小}模式间没有距离的概念非度量方法特征类型数值数据（numericaldata）决策树什么是决策树？决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别决策树的构成根节点（root）分支（branch）叶节点（leaf）决策树什么是决策树？决策树决策树决策树决策树分类过程从根节点开始，首先对某一属性的取值提问Color?与根节点相连的不同分支，对应这个属性的不同取值green;yellow;red;根据不同的回答，转向相应的分支green在新到达的节点处做同样的分支判断Size?–big.这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记Watermelon决策树决策树分类过程决策树决策树的判决面决策树决策树的判决面决策树决策树的优势语义可表示性从根节点到叶节点表示为合取式（颜色=黄）AND（形状=细长）香蕉利用合取式和析取式获得某个类别的明确描述苹果=（绿色AND中等大小）OR（红色AND中等大小）分类速度快只需一系列简单查询即可对模式的类别做出判断可以很自然的嵌入专家的先验知识决策树决策树的优势决策树学习算法决策树研究历史第一个决策树算法称为CLS(ConceptLearningSystem)

[E.B.Hunt,J.Marin,andP.T.Stone’sbook“ExperimentsinInduction”publishedbyAcademicPressin1966]真正引发决策树研究热潮的算法是ID3

[J.R.Quinlan’spaperinabook“ExpertSystemsintheMicroElectronicAge”editedbyD.Michie,publishedbyEdinburghUniversityPressin1979]最流行的决策树算法C4.5

[J.R.Quinlan’sbook“C4.5:ProgramsforMachineLearning”publishedbyMorganKaufmannin1993]决策树学习算法决策树研究历史决策树学习算法决策树研究历史通用的决策树算法CART(ClassificationandRegressionTree)

[L.Breiman,J.H.Friedman,R.A.Olshen,andC.J.Stone’sbook“ClassificationandRegressionTrees”publishedbyWadsworthin1984]基于决策树的集成学习算法：随机森林

(RandomForests)

[L.Breiman’sMLJ’01paper“RandomForests”]决策树学习算法决策树研究历史构造决策树基本过程从上到下，分而治之（divide-and-conquer），递归生长最初，所有的样本都在根节点所有属性都是标称型的（如果是连续数值型的，则需要预先离散化）所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分（split）或测试（test）或查询

（query）查询的选择基于启发式或者统计特征构造决策树基本过程构造决策树基本过程满足如下条件之一时，划分操作停止所有落入某一节点的样本均属于同一类别该节点成为叶节点，标记为该类别没有特征能够进一步用于划分样本集该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别没有任何样本落入某一节点该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别构造决策树基本过程CART分类和回归树（ClassificationAndRegressionTree,CART)CART为通用的树生长算法框架，涉及如下问题：属性的值是二值的还是多值的？即节点可以有几个分支？如何确定某节点处应该测试哪个属性？何时令某个节点为叶节点？如果树生长的过大，如何使其变小变简单，即如何剪枝？如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？CART分类和回归树（ClassificationAnd分支数目同一个节点分出去的分支的数目称为分支系数或分支率（branchingratio）任意决策树都可以用分支系数为2的决策树（即二叉树）来表示二叉树是最常用的决策树形式分支数目同一个节点分出去的分支的数目称为分支系数或分支率（b分支数目分支数目分支数目分支数目测试的选取决策树设计的核心问题之一基本思想：

使后继结点的数据尽可能的“纯粹”节点N的不纯度（impurity）i(N)当N节点上的所有模式都来自同一类时，i(N)=0；当N节点上的模式类别分布均匀时，i(N)应很大测试的选取决策树设计的核心问题之一测试的选取常用不纯度度量熵不纯度（entropyimpurity）Gini不纯度误分类不纯度测试的选取常用不纯度度量测试的选取常用不纯度度量测试的选取常用不纯度度量测试的选取对N节点如何选择查询？使不纯度下降最快的那个查询！和分别为左、右子节点和分别为左、右子节点的不纯度是N节点的模式划分到的比例如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（informationgain）测试的选取对N节点如何选择查询？信息增益信息增益（informationgain）：节点N上样本总个数

：其中属于类的样本个数（i=1,2,…,m）：属性A的第j个取值（j=1,2,…,v）该节点处的熵不纯度属性A将S划分为v个子集中属于类的样本个数为信息增益信息增益（informationgain）信息增益信息增益（informationgain）以A作为查询，生长出v个分支的信息熵以A为查询的信息增益选择信息增益最大的属性作为N节点的查询信息增益信息增益（informationgain）信息增益例子训练集S1:buys_computer=“yes”,

S2:buys_computer=“no”信息增益例子S1:buys_computer=“yes”信息增益根节点上的熵不纯度age作为查询的信息熵信息增益根节点上的熵不纯度信息增益age作为查询的信息增益类似可以计算出所有属性的信息增益age的信息增益最大，所以选择age作为根节点的查询，对训练集进行首次划分信息增益age作为查询的信息增益信息增益率信息增益作为查询选择标准的缺点：

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

偏向有较多不同取信息增益率例子信息增益率例子Gini不纯度：节点N上样本总个数：其中属于类的样本个数（i=1,2,…,m）：属性A的第j个取值（j=1,2,…,v）该节点处的Gini不纯度属性A将S划分为v个子集中属于类的样本个数为Gini不纯度：节点N上样本总个数Gini不纯度以A作为查询，生长出v个分支的Gini不纯度选择Gini不纯度差最大（即Gini(A)最小）的属性作为N节点的查询Gini不纯度以A作为查询，生长出v个分支的Gini不纯度Gini不纯度例子Gini不纯度例子分支停止准则如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“过拟合”极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为查找表如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差常用分支停止准则交叉验证预设一个不纯度下降差的阈值监测每个节点代表的样本数目是否小于某个阈值分支停止准则如果决策树持续生长，直到所有叶节点都达到最小不纯分支停止准则最小化如下指标不纯度下降的统计显著分析如果一个划分不能显著降低不纯度，则停止分支正则项分支停止准则最小化如下指标正则项剪枝剪枝（pruning）用于消除过拟合预剪枝（prepruning）和后剪枝（postpruning）预剪枝即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分后剪枝指首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝可用交叉验证技术来确定剪掉哪些分支剪掉使不纯度增长最小的分支一般来讲，后剪枝性能较好，但需要更多计算量剪枝剪枝（pruning）叶节点的标记如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点叶节点的标记如果叶节点对应的样本都来自同一类，则用该类别标记ID3ID3:InteractiveDichotomizer-3（交互式二分法第三版）仅仅适用于标称（无序）数据

如果涉及实值数据，则需离散化，然后当做标称数据处理每个划分的分支因子等于查询属性的取值个数采用信息增益率作为选择查询的依据算法直到所有叶节点的不纯度最小，或者没有可用于划分的属性时停止标准版中无剪枝步骤ID3ID3:InteractiveDichotomizC4.5C4.5:ID3算法的后继和改进可以处理实值数据每个划分的分支因子等于查询属性的取值个数采用信息增益率作为选择查询的依据首先让树充分生长，然后利用分支的统计显著性来实现剪枝C4.5为目前最为流行的决策树算法之一C4.5C4.5:ID3算法的后继和改进Ch11.聚类Ch11.聚类无监督学习有监督（supervised）学习训练集中每个样本都有一个类别标记所有类别事先已知常用于：分类、回归无监督（unsupervised）学习训练集中样本的类别标记未知给定一组样本，发现其内在性质，如类别和聚类常用于：聚类、概率密度估计无监督学习有监督（supervised）学习无监督学习的动机收集并且标记大量模式往往花费巨大希望首先在一个较小的有标记样本集上训练一个粗略的分类器，然后让这个分类器以非监督的方式在一个较大的样本集上运行或者，用大量未标记的样本集来训练分类器，让它自动发现数据中的分组，然后用代价更高的办法（如人工）来标记这些分组在很多应用中，模式的特征会随时间而变化如果这种特征的变化能够被某种运行在无监督方式下的分类器捕捉到，那么分类性能将得到大幅提高无监督学习的动机收集并且标记大量模式往往花费巨大无监督学习的动机无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备例如：PCA降维在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律发现模式中内在的聚类或分组可能为分类器设计提供依据无监督学习的动机无监督方法可以用来提取特征，或者预处理现存特聚类聚类（clustering）聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程因为训练集样本并无类别标记，所以聚类是无监督学习过程一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似聚类可用作一种独立的数据分析工具，用于分析数据的内在特性一种数据预处理方法，为后续模式识别服务聚类聚类（clustering）相似性度量“同一聚类内部的样本之间比不同聚类的样本之间更相似”基于某种定义的样本间的相似性（或不相似性）度量两类主要的相似性（不相似性）度量基于度量的距离标准非度量的相似性函数一个度量（即距离函数）需满足如下条件非负性：自反性：对称性：三角不等式：相似性度量“同一聚类内部的样本之间比不同聚类的样本之间更相似距离度量常用的距离度量最为常用的距离度量为欧氏距离，作为不相似性度量其次为考虑数据分布的马氏距离根据距离对样本进行聚类计算任意两个样本之间的距离如果两个样本之间的距离小于某个阈值

，那么这两个样本就属于同一个聚类过大，所有样本都被分为同一个聚类过小，每个样本都自成一个聚类距离度量常用的距离度量距离度量

越小，每个聚类就越小，聚类个数就越多欧氏距离距离度量越小，每个聚类就越小，聚类个数就越多欧氏距距离度量缩放坐标尺度引

起聚类结果的变

化距离度量缩放坐标尺度引

起聚类结果的变

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

单位方差规格化在聚类之前可先“规格化”（normalization）相似性函数不使用距离，可以直接定义非度量的相似性函数相似性函数是度量样本之间相似性的函数对称性当两个样本具有某种相似性时，函数的值较大常用的相似性函数归一化内积（两个向量夹角的余弦）对二值特征（0-1）来说，归一化内积相当于共享属性的相对计数，进一步，可简化为共享属性的比例相似性函数不使用距离，可以直接定义非度量的相似性函数何谓好的聚类？一个好的聚类过程产生高质量的聚类聚类内部相似度高聚类之间相似度低聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现评价聚类结果的好坏往往具有主观性何谓好的聚类？一个好的聚类过程产生高质量的聚类聚类的准则函数“一种聚类的划分比另一种划分好”基于某种聚类的准则函数聚类问题可以看做一种离散优化问题准则函数用于度量对数据聚类的某种划分的质量目标是找到某种划分，使得准则函数最小（大）化采用不同的准则函数可能得到不同的聚类结果常用准则函数误差平方和准则最小方差准则散布准则聚类的准则函数“一种聚类的划分比另一种划分好”基于某种聚类的误差平方和准则误差平方和准则是最简单也使用最广的聚类准则函数其中是第i个聚类中样本的均值当数据点能被划分成很好的相互区分的几个聚类，并且聚类内部又很稠密时，适用误差平方和准则误差平方和准则误差平方和准则是最简单也使用最广的聚类准则函数误差平方和准则采用误差平方和准则可能存在的问题当不同聚类所包含的样本个数相差较大时，将一个大的聚类分割开来反而可能得到更小的误差平方和误差平方和准则采用误差平方和准则可能存在的问题最小方差准则由于误差平方和准则度量的是样本点到聚类均值的方差，所以它是最小方差准则的一种与误差平方和准则等价的形式其中，为第i个聚类中的样本个数最小方差准则的一般形式为某种相似性函数最小方差准则由于误差平方和准则度量的是样本点到聚类均值的方差散布准则均值向量第i个聚类的均值向量总的均值向量散布准则均值向量散布准则散布矩阵第i个聚类的散布矩阵总的散布矩阵聚类内散布矩阵散布准则散布矩阵散布准则散布矩阵聚类间散布矩阵聚类内散布矩阵和聚类间散布矩阵的关系散布准则散布矩阵散布准则为了得到更好的聚类质量，我们希望得到较小的聚类内散布和较大的聚类间散布需要某种标量度量矩阵的“大小”，如矩阵的迹（trace，即矩阵对角线上元素之和）由于，而与如何划分聚类无关，所以，最小化就同时最大化聚类间散布矩阵的迹标量度量也可选用矩阵的行列式散布准则为了得到更好的聚类质量，我们希望得到较小的聚类内散布迭代最优化对一个有限样本集来说，可能的划分的个数是有限的，理论上可以用穷举法找到最优解。然而，穷举法因计算量过大而往往无法实现迭代最优化方法经常用于寻求最优划分首先开始于一些合理的初始划分然后将某些样本从一个聚类移动到另一个聚类——如果这样做能够改善准则函数的话重复迭代直到没有显著改善时停止这种迭代方法可以保证收敛到局部最优，但不能保证找到全局最优迭代最优化对一个有限样本集来说，可能的划分的个数是有限的，理基于划分的聚类方法给定一个数据集，基于划分的方法将数据集划分为k个子集，每个子集对应一个聚类两种方案每个聚类由其所包含的样本的均值来表示每个聚类由靠近该聚类中心的样本（中心点）来表示典型算法k-均值（k-means）k-medoids基于划分的聚类方法给定一个数据集，基于划分的方法将数据集划分k-means算法每个聚类由其所包含的样本的均值来表示步骤1：随机选择k个样本作为k个聚类的中心步骤2：对剩余的每一个样本，将其划分入中心距离该样本最近的聚类步骤3：计算每个聚类的均值作为新的中心步骤4：如果聚类中心没有任何改变，算法停止，否则 回到步骤2k-means算法每个聚类由其所包含的样本的均值来表示k-means算法k-means算法k-medoids算法每个聚类由靠近该聚类中心的样本来表示步骤1：随机选择k个样本作为k个聚类的中心步骤2：对剩余的每一个样本，将其划分入中心距离该样本最近的聚类步骤3：计算每个聚类的medoid（即距离均值最近的样 本）步骤4：如果聚类的medoid没有任何改变，算法停止， 否则回到步骤2k-medoids算法每个聚类由靠近该聚类中心的样本来表示k-medoids算法k-medoids算法小结特征类型数值数据（numericaldata）基于度量的模式分类方法标称数据（nominaldata）非度量方法决策树根节点（root）分支（branch）叶节点（leaf）小结特征类型小结构造决策树分支数目测试的选取信息增益信息增益率Gini不纯度剪枝预剪枝后剪枝小结构造决策树小结根据训练样本是否有类别标记，学习算法分为有监督（supervised）学习无监督（unsupervised）学习聚类（clustering）聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程小结根据训练样本是否有类别标记，学习算法分为小结聚类算法迭代最优化聚类算法基于划分的聚类方法k-均值（k-means）k-medoids小结聚类算法Ch10.决策树Ch10.决策树特征类型数值数据（numericaldata）例：{1.2,4.5,3.3}模式间可以计算距离度量基于度量的模式分类方法标称数据（nominaldata）例：{红色，有光泽，甜，小}模式间没有距离的概念非度量方法特征类型数值数据（numericaldata）决策树什么是决策树？决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别决策树的构成根节点（root）分支（branch）叶节点（leaf）决策树什么是决策树？决策树决策树决策树决策树分类过程从根节点开始，首先对某一属性的取值提问Color?与根节点相连的不同分支，对应这个属性的不同取值green;yellow;red;根据不同的回答，转向相应的分支green在新到达的节点处做同样的分支判断Size?–big.这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记Watermelon决策树决策树分类过程决策树决策树的判决面决策树决策树的判决面决策树决策树的优势语义可表示性从根节点到叶节点表示为合取式（颜色=黄）AND（形状=细长）香蕉利用合取式和析取式获得某个类别的明确描述苹果=（绿色AND中等大小）OR（红色AND中等大小）分类速度快只需一系列简单查询即可对模式的类别做出判断可以很自然的嵌入专家的先验知识决策树决策树的优势决策树学习算法决策树研究历史第一个决策树算法称为CLS(ConceptLearningSystem)

[E.B.Hunt,J.Marin,andP.T.Stone’sbook“ExperimentsinInduction”publishedbyAcademicPressin1966]真正引发决策树研究热潮的算法是ID3

[J.R.Quinlan’spaperinabook“ExpertSystemsintheMicroElectronicAge”editedbyD.Michie,publishedbyEdinburghUniversityPressin1979]最流行的决策树算法C4.5

[J.R.Quinlan’sbook“C4.5:ProgramsforMachineLearning”publishedbyMorganKaufmannin1993]决策树学习算法决策树研究历史决策树学习算法决策树研究历史通用的决策树算法CART(ClassificationandRegressionTree)

[L.Breiman,J.H.Friedman,R.A.Olshen,andC.J.Stone’sbook“ClassificationandRegressionTrees”publishedbyWadsworthin1984]基于决策树的集成学习算法：随机森林

(RandomForests)

[L.Breiman’sMLJ’01paper“RandomForests”]决策树学习算法决策树研究历史构造决策树基本过程从上到下，分而治之（divide-and-conquer），递归生长最初，所有的样本都在根节点所有属性都是标称型的（如果是连续数值型的，则需要预先离散化）所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分（split）或测试（test）或查询

（query）查询的选择基于启发式或者统计特征构造决策树基本过程构造决策树基本过程满足如下条件之一时，划分操作停止所有落入某一节点的样本均属于同一类别该节点成为叶节点，标记为该类别没有特征能够进一步用于划分样本集该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别没有任何样本落入某一节点该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别构造决策树基本过程CART分类和回归树（ClassificationAndRegressionTree,CART)CART为通用的树生长算法框架，涉及如下问题：属性的值是二值的还是多值的？即节点可以有几个分支？如何确定某节点处应该测试哪个属性？何时令某个节点为叶节点？如果树生长的过大，如何使其变小变简单，即如何剪枝？如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？CART分类和回归树（ClassificationAnd分支数目同一个节点分出去的分支的数目称为分支系数或分支率（branchingratio）任意决策树都可以用分支系数为2的决策树（即二叉树）来表示二叉树是最常用的决策树形式分支数目同一个节点分出去的分支的数目称为分支系数或分支率（b分支数目分支数目分支数目分支数目测试的选取决策树设计的核心问题之一基本思想：

使后继结点的数据尽可能的“纯粹”节点N的不纯度（impurity）i(N)当N节点上的所有模式都来自同一类时，i(N)=0；当N节点上的模式类别分布均匀时，i(N)应很大测试的选取决策树设计的核心问题之一测试的选取常用不纯度度量熵不纯度（entropyimpurity）Gini不纯度误分类不纯度测试的选取常用不纯度度量测试的选取常用不纯度度量测试的选取常用不纯度度量测试的选取对N节点如何选择查询？使不纯度下降最快的那个查询！和分别为左、右子节点和分别为左、右子节点的不纯度是N节点的模式划分到的比例如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（informationgain）测试的选取对N节点如何选择查询？信息增益信息增益（informationgain）：节点N上样本总个数

：其中属于类的样本个数（i=1,2,…,m）：属性A的第j个取值（j=1,2,…,v）该节点处的熵不纯度属性A将S划分为v个子集中属于类的样本个数为信息增益信息增益（informationgain）信息增益信息增益（informationgain）以A作为查询，生长出v个分支的信息熵以A为查询的信息增益选择信息增益最大的属性作为N节点的查询信息增益信息增益（informationgain）信息增益例子训练集S1:buys_computer=“yes”,

S2:buys_computer=“no”信息增益例子S1:buys_computer=“yes”信息增益根节点上的熵不纯度age作为查询的信息熵信息增益根节点上的熵不纯度信息增益age作为查询的信息增益类似可以计算出所有属性的信息增益age的信息增益最大，所以选择age作为根节点的查询，对训练集进行首次划分信息增益age作为查询的信息增益信息增益率信息增益作为查询选择标准的缺点：

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

偏向有较多不同取信息增益率例子信息增益率例子Gini不纯度：节点N上样本总个数：其中属于类的样本个数（i=1,2,…,m）：属性A的第j个取值（j=1,2,…,v）该节点处的Gini不纯度属性A将S划分为v个子集中属于类的样本个数为Gini不纯度：节点N上样本总个数Gini不纯度以A作为查询，生长出v个分支的Gini不纯度选择Gini不纯度差最大（即Gini(A)最小）的属性作为N节点的查询Gini不纯度以A作为查询，生长出v个分支的Gini不纯度Gini不纯度例子Gini不纯度例子分支停止准则如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“过拟合”极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为查找表如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差常用分支停止准则交叉验证预设一个不纯度下降差的阈值监测每个节点代表的样本数目是否小于某个阈值分支停止准则如果决策树持续生长，直到所有叶节点都达到最小不纯分支停止准则最小化如下指标不纯度下降的统计显著分析如果一个划分不能显著降低不纯度，则停止分支正则项分支停止准则最小化如下指标正则项剪枝剪枝（pruning）用于消除过拟合预剪枝（prepruning）和后剪枝（postpruning）预剪枝即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分后剪枝指首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝可用交叉验证技术来确定剪掉哪些分支剪掉使不纯度增长最小的分支一般来讲，后剪枝性能较好，但需要更多计算量剪枝剪枝（pruning）叶节点的标记如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点叶节点的标记如果叶节点对应的样本都来自同一类，则用该类别标记ID3ID3:InteractiveDichotomizer-3（交互式二分法第三版）仅仅适用于标称（无序）数据

如果涉及实值数据，则需离散化，然后当做标称数据处理每个划分的分支因子等于查询属性的取值个数采用信息增益率作为选择查询的依据算法直到所有叶节点的不纯度最小，或者没有可用于划分的属性时停止标准版中无剪枝步骤ID3ID3:InteractiveDichotomizC4.5C4.5:ID3算法的后继和改进可以处理实值数据每个划分的分支因子等于查询属性的取值个数采用信息增益率作为选择查询的依据首先让树充分生长，然后利用分支的统计显著性来实现剪枝C4.5为目前最为流行的决策树算法之一C4.5C4.5:ID3算法的后继和改进Ch11.聚类Ch11.聚类无监督学习有监督（supervised）学习训练集中每个样本都有一个类别标记所有类别事先已知常用于：分类、回归无监督（unsupervised）学习训练集中样本的类别标记未知给定一组样本，发现其内在性质，如类别和聚类常用于：聚类、概率密度估计无监督学习有监督（supervised）学习无监督学习的动机收集并且标记大量模式往往花费巨大希望首先在一个较小的有标记样本集上训练一个粗略的分类器，然后让这个分类器以非监督的方式在一个较大的样本集上运行或者，用大量未标记的样本集来训练分类器，让它自动发现数据中的分组，然后用代价更高的办法（如人工）来标记这些分组在很多应用中，模式的特征会随时间而变化如果这种特征的变化能够被某种运行在无监督方式下的分类器捕捉到，那么分类性能将得到大幅提高无监督学习的动机收集并且标记大量模式往往花费巨大无监督学习的动机无监督方法可以用来提取特征，或者预处理现存特征，从而为后续的模式识别问题做准备例如：PCA降维在任何探索性的工作中，无监督方法可以揭示观测数据的一些内部结构和规律发现模式中内在的聚类或分组可能为分类器设计提供依据无监督学习的动机无监督方法可以用来提取特征，或者预处理现存特聚类聚类（clustering）聚类是指将物理的或抽象的对象自然分组，使得每组由相似的对象构成一类的过程因为训练集样本并无类别标记，所以聚类是无监督学习过程一个聚类（cluster）是指一组样本，它们与属于同一聚类的样本相似，而与属于其他聚类的样本不相似聚类可用作一种独立的数据分析工具，用于分析数据的内在特性一种数据预处理方法，为后续模式识别服务聚类聚类（clustering）相似性度量“同一聚类内部的样本之间比不同聚类的样本之间更相似”基于某种定义的样本间的相似性（或不相似性）度量两类主要的相似性（不相似性）度量基于度量的距离标准非度量的相似性函数一个度量（即距离函数）需满足如下条件非负性：自反性：对称性：三角不等式：相似性度量“同一聚类内部的样本之间比不同聚类的样本之间更相似距离度量常用的距离度量最为常用的距离度量为欧氏距离，作为不相似性度量其次为考虑数据分布的马氏距离根据距离对样本进行聚类计算任意两个样本之间的距离如果两个样本之间的距离小于某个阈值

，那么这两个样本就属于同一个聚类过大，所有样本都被分为同一个聚类过小，每个样本都自成一个聚类距离度量常用的距离度量距离度量

越小，每个聚类就越小，聚类个数就越多欧氏距离距离度量越小，每个聚类就越小，聚类个数就越多欧氏距距离度量缩放坐标尺度引

起聚类结果的变

化距离度量缩放坐标尺度引

起聚类结果的变

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

单位方差规格化在聚类之前可先“规格化”（normalization）相似性函数不使用距离，可以直接定义非度量的相似性函数相似性函数是度量样本之间相似性的函数对称性当两个样本具有某种相似性时，函数的值较大常用的相似性函数归一化内积（两个向量夹角的余弦）对二值特征（0-1）来说，归一化内积相当于共享属性的相对计数，进一步，可简化为共享属性的比例相似性函数不使用距离，可以直接定义非度量的相似性函数何谓好的聚类？一个好的聚类过程产生高质量的聚类聚类内部相似度高聚类之间相似度低聚类结果的质量取决于采用的相似度度量以及聚类算法的具体实现评价聚类结果的好坏往往具有主观性何谓好的聚类？一个好的聚类过程产生高质量的聚类聚类的准则函数“一种聚类的划分比另一种划分好”基于某种聚类的准则函数聚类问题可以看做一种离散优化问题准则函数用于度量对数据聚类的某种划分的质量目标是找到某种划分，使得准则函数最小（大）化采用不同的准则函数可能得到不同的聚类结果常用准则函数误差平方和准则最小方差准则散布准则聚类的准则函数“一种聚类的划分比另一种划分好”基于某种聚类的误差平方和准则误差平方和准则是最简单也使用最广的聚类准则函数其中是第i个聚类中样本的均值当数据点能被划分成很好的相互区分的几个聚类，并且聚类内部又很稠密时，适用误差平方和准则误差平方和准则误差平方和准则是最简单也使用最广的聚类准则函数误差平方和准则采用误差平方和准则可能存在的问题当不同聚类所包含的样本个数相差较大时，将一个大的聚类分割开来反而可能得到更小的误差平方和误差平方和准则采用误差平方和准则可能存在的问题最小方差准则由于误差平方和准则度量的是样本点到聚类均