人工智能导论课件人工智能导论——第四章_97470852章节幻灯片.pptVIP

经验风险容易引起过拟合，结构风险是在经验风险的基础上加上体现模型复杂度的正则化项 * 强化学习：指的是动作序列的学习 * 本科，2016.4.19 * * X(j)上标，表示X的第j个分量 * K是类别数，Sj是第j个特征的取值数。 * * * 本科 2015.5.12 * * 本科。2016.4.26 * 本科。2016.4.26 * 注意与线性可分的差别在于ai的限制 * 注意与线性可分的差别在于ai的限制 * * Yiboxinong是函数间隔，线性可分时，最大间隔是取函数间隔为1，软划分时，是1-yiboxinong * GRAM矩阵：{xi}为N个样本，[K(xi,xj)]N*N，即对所有的样本点用fai(xi).fai(xj) * 求min W(α) * Ei可以认为是误差， * 当y1=y2同理 黄线为α2的取值范围，可以从截距得到 * * 本科 2016.5.10 * 完全无矛盾的决策树可能不存在，或者过拟合 * * * 一个属性有很多取值，划分成很多不同的子集，就说明该属性的熵大。除以HA(D)以避免划分太细的特征。 * * * * 身高？ 体重？ 高 可用的特征： 身高 体重 鞋的式样 头发长度 衣服颜色 …… 衣服颜色？ 矮 重 轻 决策树学习 决策树学习就是从训练集中归纳出一组分类规则，得到一个与训练集矛盾较小的决策树 * 对于给定的训练集，可以构造出多个决策树，一般以损失函数最小化作为优化目标 从所有决策树中选取最优决策树是一个NPC问题，所以一般采用启发式方法，得到一个近似解 * 决策树学习包括 特征选择 决策树生成 决策树剪枝 * 特征选择 一个问题中可能有不同的特征，不同的特征具有不同的分类能力，特征选择就是如何选取出那些分类能力强的特征。 决策树中一般按照信息增益选择特征 所谓的信息增益就是某个特征A对数据集D进行分类的不确定性减少的程度 * 信息增益 * 特征A对数据集D的信息增益定义为： 表示特征A对数据集D的分类的不确定性减少的程度 信息增益大的特征具有更强的分类能力 * 设训练集D，K个类Ck，特征A有n个不同的取值{ai,…,an}，A的不同取值将D划分为n个子集D1…Dn，Di中属于类Ck的样本的集合为Dik，|·|表示样本个数。 信息增益计算如下： * 决策树的生成 两个常用的算法 ID3 一个基本的决策树生成算法 C4.5 对ID3的改进 * ID3算法 输入：训练集D，特征集A，阈值e 输出：决策树T 1，若D中所有实例属于同一类Ck，则T为单节点树，将Ck作为该节点的类标记，返回T 2，若A为空，则T为单节点树，将D中实例数最大的类Ck作为该节点的类标记，返回T 3，否则计算A中各特征对D的信息增益，选择信息最大的特征Ag 4，如果Ag的信息增益小于阈值e，则置T为单节点树，将D中实例数最大的类Ck作为该节点的类标记，返回T * 5，否则对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T 6，对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归地调用步1~步5，得到子树Ti，返回Ti * 例：贷款申请样本如下表所示，试用ID3算法构建决策树。 * * ID 年龄 A1 有工作 A2 有房子 A3 信贷情况 A4 类别 1 青年 否 否 一般 否 2 青年 否 否 好 否 3 青年 是 否 好 是 4 青年 是 是 一般 是 5 青年 否 否 一般 否 6 中年 否 否 一般 否 7 中年 否 否 好 否 8 中年 是 是 好 是 9 中年 否 是 非常好 是 10 中年 否 是 非常好 是 11 老年 否 是 非常好 是 12 老年 否 是 好 是 13 老年 是 否 好 是 14 老年 是 否 非常好 是 15 老年 否 否 一般 否 * * 生成的决策树如下： ID3只有树的生成，所以容易产生过拟合 * 是 是 是 是 否 否 否 有房子 有工作 ID3存在的问题 信息增益倾向于选择分枝比较多的属性 比如前面贷款的例子中，如果用ID做属性，将获得最大的信息增益值 * 信息增益比 其中A为属性，A的不同取值将D划分为n个子集D1…Dn * C4.5的生成算法 C4.5与ID3的唯一不同，就是根据信息增益比选择特征，其他与ID3完全一样。 同时C4.5增加了对连续值属性的处理，对于连续值属性A，找到一个属性值a0，将≤a0的划分到左子树，＞a0的划分到右子树 * 信息增益比的问题： 倾向于选择分割不均匀的特征 解决办法 先选择n个信息增益大的特征，再从这n个特征中选择信息增益比最大的特征 * 过拟合问题 * 决策树的剪枝 为了