5.6 决策树 -- CART算法
CART是二叉结构树。多叉可以转换成二叉，表示是和非
在CART算法中分类树是怎么形成的，要先确定特征选择的标准，之前是信息熵，引申出信息增益，都是表示不同特征下的分类能力，CART算法用的是基尼指数，同样是度量不同特征的分类能力
基尼指数
机器学习中用来度量不确定性，基尼指数越大，不确定性越高
现实中不知道样本属于某个类别的概率pk是多少，是估计值：pk^ = |Ck|（表示属于Ck这个类的个数）/ |D|（样本量），得到了第k类的概率估计值
如果给定某个特征，基尼指数怎么定义
如果给定特征A后，将样本划分为两类（D1和D2），可以分别计算D1和D2的基尼指数，加权求和，就可以得到特征A下D的基尼指数。权重是小样本集占总样本集的比例。
不考虑任何特征的基尼指数：Gini（D）= kpq（q=1-p）
但现在的关注点事哪个特征有助于分类，选择特征（甜度），取值范围有大于和小于0.2的
特征A下D的基尼指数
根据硬度的特征分：
0.17（甜度特征）< 0.48（硬度特征）
表明甜度特征更有利于桃子的分类。基尼指数小，不确定性小，分的彻底
CART算法 -- 分类树算法
停止条件：阈值ε
在年龄这个特征A下用青年ag1（ag2为非青年）得到的基尼指数，划分成D1和D2
在年龄这个特征A下用中年和老年得到的基尼指数
gini青年=老年=0.44，中年=0.48，青年和老年都可以作为划分点。
记：年龄：Gini（D1，A1）=0.44。划分点：青年/老年
同理计算其他特征下不同取值的基尼指数，取最小值作为那个特征的基尼指数。
有工作这个特征，因为可以直接完全划分是否贷款，确定性唯一，所以基尼指数为0
CART算法 -- 回归树算法
将连续的变量划分为小区间
将输入划分为M个单元，输出为Cm，当x在R1，输出为代表值C1
划分为M个单元，与CART是二叉树的思想不矛盾：
问题：
如何划分？ 比较平方误差大小找到划分点
C1…CM如何计算？ 用“最优输出”，CM是Rm上yi的平均值，是最优输出结果
划分：
任取值s，作为切分点，将区间划分为R1和R2，可以计算平方误差：每个区间里的样本点 - 代表值C1，取平方和。
如果想使在R1这个区间的平方和最小，C1应该取R1上的平均值，求平方和就是平方误差
将两个平方误差加起来就是在切分点s下的平方误差
计算每一个切分点下的平方误差，找平方误差小的s，就是最优切分点，就知道怎么找最优切分变量：每一个变量的最优切分点，得到每个变量下的平方误差，比较这个平方误差，选出最小的，就是最优切分变量
s=0.1，将数据划分为R1=0.05和R2（右边4个）
C1^ =5.5
C2^ =7.6+9.5+9.7+8.2/4=8.75
R1=(5.5-5.5)^2=0
R2=(7.6-8.75)2+(9.5-8.75)2+...=3.09
对于s1=0.1的平方误差是0+3.09
依次可以写出s2=0.2的平方误差=3.53，s3、s4时的平方误差
最小的平方误差是s1时，所以最优切分点是s1。
然后改变变量，比较每个变量下的最优切分点，最小的就是最优变量
决策树怎么表示呢？
可以在R2上找到最优切分点，划分R2
CART树的剪枝
用代价复杂度这个一个损失函数
C(T)是代价，|T|是复杂度
α是调整、惩罚参数
α越小，比如取0，是代价部分，代价是模型的拟合程度；
完整的树，没有进行剪枝，仅是由拟合的损失决定的
α取∞，更多是复杂度决定的损失函数，反映泛化能力
单结点树，泛化能力很强，拟合效果差，针对性差
在0到∞划分n个区间，每个区间都对应一棵决策树。T0是α取0时对应完整的决策树，只要确定α就确定决策树。
怎么从这些决策树选最优决策树？选好就完成了剪枝，要判断剪枝前后的损失函数
CART可以解决回归和分类问题，分类问题用基尼指数，回归问题用平方误差的形式
问题：
①α怎么用？
②区间怎么找到？
6.1 逻辑回归 -- logistic distribution
F(x)三个特征：非减、有界[0,1]、连续
既然分布函数（中心对称）是连续的，可以求导函数，得到概率密度函数：（和正态分布像，因为属于指数分布族，如t分布）
尾部和正态分布不同
正态分布是在给定均值和方差的时候，具有最大熵的概率分布，所以很多例子要假设在正态分布下，使数据携带信息量最大，应用广泛
logistics分布时假设在生长趋势，t分布是假设不知道标准差的情况
f（x）对应增长率，x取0，增长率最大
这个f（x）是标准logistics分布
标准正态分布是关于x=0对称，logistics也是
N（0,1）中0反映位置，1（方差）反映形状
6.3 逻辑回归 -- 回归模型
大自然控制人类身高不会向两级分化，在中心状态。regress（退回）
ε是误差项，α是截距项
多元时x和β是向量
若要将ε简化，取期望形式，就是期望方程，左右两边同时求期望，左边是y的期望，ε期望是0
若y和x不是线性关系？转化成线性，就可以用已知模型去解决非线性问题。
函数g（y），作用在y上，得到线性的形式，那么g（y）称为广义线性模型
将logistics分布作为连接函数g
得到新模型
之前的β用ω表示，代表权重参数，α用b表示，作为偏置项
6.4 逻辑回归模型
如果给样本点（xi，yi），xi和ω是n+1维的向量，x·ω是一个数值，所以yi也是一个数值
如果给N个样本点，x可以通过向量的形式输入，x·ω是一个N维的向量，对应概率是N维，每一维都对应yi
逻辑回归的好处，不局限输入和输出是否存在线性关系，用连续函数代替阶跃函数
6.5 逻辑回归：参数估计
方法：极大似然估计
逻辑回归模型是二值概率分布，可以写作二项分布
样本点（xi，yi）取Y这个类的概率：
每一个样本点对应概率
数据集的概率就是每一个样本点的概率相乘，如果关注点在参数ω，概率可以记作似然函数
求参数：
①遍历
②显式解（求导）
③迭代：牛顿法（泰勒公式二阶展开）、梯度上升法（求最大值）
7.1 最大熵模型：原理 -- 离散分布
最大熵是要找到使H最大的概率分布pi
最简单的离散分布：两点分布（伯努利分布）
多项分布：随机变量x有多个取值
二项分布的时候，x取0.5熵最大，**多项分布时，x和p取什么的时候有最大熵？
pi-1/k时熵最大，熵最小是0**
0<=k<=log2k 等号成立条件就是等概率的时候
古典概率中，随机现象由有限个样本点组成，每个样本点发生的概率都相同
这个多项分布有5个取值，pi=1/5时有最大熵
想得到最大熵，就是分布在两部分上都得到最大熵结果
就是让两者都等概率的时候
7.1最大熵模型：原理 -- 连续分布
连续的概率分布，熵就是积分的形式，也就是求积分最大的时候的p（x）
需要满足几个约束条件：
第一个是常规约束，既然是概率分布，在整个取值范围内积分是1（积分理解为连续函数的累加），∫p(x)dx=1
第二个关于均值：μ=∫xp(x)dx
第三个关于方差：σ^2 =∫(x-μ)^2 p(x)dx
7.2 最大熵模型：模型简介
模型关注点是集合，是选择只满足约束条件的模型
第一个式子表示模型集合，也就是模型的备选集
第二个式子H表示熵，但是条件熵，条件是x，输入变量。
最大熵模型是一个有针对性的判别方法，判别方法最后得到的就是条件概率分布，已知x情况下y的分布函数P(Y|X)，自然要求条件熵，
模型的标准：使条件熵H(P)最大的模型
求每个x在不同类别y的概率，概率最大的就是属于的类。如果概率相同，随意取
要得到集合，需要若干约束条件，i取1到n表示有n个约束条件
花体P代表所有概率分布，从这里面找满足约束条件的模型
在例子：“打做量词时发音为二声”中，x和y之间的事实是“做量词时前面有数词”，引入特征函数
f1是x前面有数词
f2是x来自西游记（三打白骨精）
这样n=2，两个约束条件
什么是经验分布？上帝视角抛硬币是1/2的概率，真实的。而训练数据集可能是0.48的概率，是经验分布，估计值
而我们希望经验分布尽可能接近上帝视角。不妨考虑期望，也就是平均意义下相同
对应每一个特征函数，在真实和经验分布下求期望值，使其相等，等号左边是真实分布，波浪线是经验分布。
