第四章-决策树&贝叶斯优化

决策树1大纲什么是决策树决策树算法•ID3•C4.5•CART总结2决策树•预备知识:根节点,叶子节点,非叶子节点•每个非叶子节点代表一个属性的划分•每次划分的结果要么导致下一个的决策问题要么导致最终结论•决策树通过从根节点开始沿着分支直到叶子节点结束来对样本进行分类•决策树最终的结论（叶子节点）对应一个目标值3构建决策树的要素构建决策树的要素1、属性及属性值2、预定义的类别（目标值）3、充足的标记数据4训练集5训练集对应三个要素构建决策树的三个问题（3）什么时候停止并得到目标值？（1）从哪个属性开始或者说选择哪个属性作为根节点？6（2）选择哪个属性作为后继节点？目标属性熵值最大者熵值次者决策树•决策树算法的基本思想：•选择最优属性划分当前样本集合并把这个属性作为决策树的一个节点•不断重复这个过程构造后继节点•直到满足下面三个条件之一停止:•对于当前节点，所有样本属于同一类•或者没有属性可以选择了•或者没有样本可以划分了7属性选择•决策树算法的一个关键问题：属性选择•不同决策树算法的差异：属性选择方法不同•下面以ID3算法为例讲解怎么构造决策树(ID3:InteractiveDichotomize3[RossQuinlan/1975])8ID3•ID3依据信息增益来选择最优属性•信息增益是通过信息熵计算而来•信息熵衡量一个集合的纯度例如：•集合1:10个好瓜•集合2:8个好瓜和2个坏瓜•集合3:5个好瓜和5个坏瓜纯度：集合1集合2集合39信息熵熵：物理中体系混乱程度的度量•pi是当前集合里类别为i的样本所占的比例,则：Entropy({p1,…,pk})=-sum(pilog(pi))•如果一个集合里的样本只有两个类别，那么：Entropy=-p1log(p1)-(1-p1)log(1-p1)•当集合里的所有样本都属于同一类时,信息熵是0•例如：集合1:10个好瓜•当集合里所有样本均匀混合时,信息熵是1•例如：集合2:5个好瓜，5个坏瓜p1=1orp1=0p1=0.510p1entropy信息熵当集合里所有样本属于同一类时（纯度最高时），信息熵最小。当集合里所有样本均匀混合时（纯度最低时），信息熵最大纯度越低，信息熵越大；纯度越高，信息熵越小11信息增益•一个属性的信息增益是本属性对样本集合进行划分所带来的信息熵下降•Di是集合D的第i个子集,a是一个属性，则:Gain(D,a)=Entropy(D)-∑(i=1tok)|Di|/|D|Entropy(Di)•划分:划分后信息熵越低信息增益越大•例如：D:5个好西瓜，5个坏瓜D1:2个好瓜,1个坏瓜D2:3个好瓜,4个坏瓜Gain(D,a)=Entropy(D)-(310Entropy(D1)+710Entropy(D2))12举例色泽：D1(色泽=青绿)={1+,4+,6+,10-,13-,17-}D2(色泽=乌黑)={2+,3+,7+,8+,9-,15-}D3(色泽=浅白)={5+,11-,12-,14-,16-}=13#根节点信息熵举例同理：14举例D1={1+,2+,3+,4+,5+,6+,8+,10-,15-}15纹理=？{1+,2+,3+,4+,5+,6+,8+,10-,15-}{7+,9-,13-,14-,17-}{11-,12-,16-}清晰稍糊模糊ID3的缺陷例如：如果我们把“编号”作为一个属性，那么“编号”将会被选为最优属性。但实际上“编号”是无关属性，它对西瓜分类并没有太大作用。16ID3倾向于选择取值比较多的属性缺陷：有些属性可能会对分类任务没有太大作用，但是他们可能会被选为最优属性。C4.5信息增益比：17该项是对属性取值个数的度量属性属性的取值个数样本集合缺陷：增益率对于取值较少的属性有所偏好(与ID3的缺陷恰好相反)CART:分类回归树，既能用于分类又能用于回归回归树：(最小二乘回归树生成算法)，需要寻找最优切分变量和最优切分点。分类树（CART生成算法），使用基尼指数选择最优特征。应用算法：RandomForest.1818CART基尼指数是用来度量数据的纯度贝叶斯优化贝叶斯优化是机器学习算法模型的一种超参数选择方法，常用的还有网格搜索，随机搜索。网格搜索：对于每个模型的参数设置一个字典存储该参数的调节范围，然后以for循环嵌套的形式进行训练，虽然会获取到目标函a'a'a'a'a'a'a数的极值，但是极其消耗时间，它属于一种穷举法。随机搜索：算是网格搜索的一个进化版，当调节参数是连续的，比如aaaaaaaaaaa回归问题的正则化参数，有必要指定一个连续分布而不是aaaaaaaaaa可能值的列表，这样随机搜索就可以执行更好的网格搜索。优点是目标函数收敛快，缺点是容易陷入局部最优解。贝叶斯优化：贝叶斯优化的工作方式是通过对目标函数形状的学习，找到使结果向全局最大值提升的参数。它与前两种优化方法的差异在于它会根据前一次的优化结果来调整下一次的参数选择。19网格搜索示例20当模型参数较少，求目标函数是凸函数的时候，网格搜索效果较好贝叶斯优化•贝叶斯优化适用范围①目标函数f(x)形式未知②非凸函数•贝叶斯优点①目标函数收敛速度快②采样点的数量少•贝叶斯优化过程①高斯过程②提取函数21高斯过程•高斯分布(正态分布)22定义：高斯过程是指随机变量的一个集合，其中任意有限个样本的线性组合都有一个联合高斯分布。23网格搜索优化示意图24高斯过程通俗理解：高斯过程可以看成是一个函数，函数的输入是x(待优化参数)，函数的输出是高斯分布的均值和方差。高斯过程的具体形式m(x)是数学期望E(f(x)),k(x,x')是核函数，描述的是x的协方差。高斯过程有一个特点就是每个x都对应一个高斯分布。协方差核函数主要控制预测函数是否平滑，这里介绍一种简单的核函数。通过高斯过程这个“函数”，可以获取P(f(x)|D)25))',(),((p~)(fxxkxmgx26补充说明：贝叶斯公式27通过调节核函数来观察预测函数的抖动程度2829此处有一长图演示预测函数如何拟合目标函数30提取函数提取函数可以通俗解释为参数选择策略1.explore，尽可能的探索未知的空间，这样对f(x)的后验概率才会更接近f(x)2.exploit，强化已有的结果，在现有最大值的附近进行探索，保证找到的f(x)会更大31贝叶斯优化实例32