机器学习09__决策树学习.pdf

决策树学习决策树学习 决策树决策树 • 决策树是实例（表示为特征向量）的分类器。结点测 试特征试特征，，边表示特征的每个值边表示特征的每个值，，叶结点对应分类叶结点对应分类。。 • 可表示任意析取和合取范式可表示任意析取和合取范式，，从而表示任意离散函数从而表示任意离散函数 和离散特征 • 可将实例分到多个分类(≥2) • 可以重写为规则，用析取范式（DNF ）形式 red ^ circle - positive red ^ circle - A blueblue - B;B; redred ^ squaresquare - BB green - C; red ^ triangle - C 2001年6月2 日 决策树学习决策树学习 • 特点与优势 • 实例实例用用((属性属性-值值))对表示对表示。。离散值处理简单离散值处理简单，，连续值可连续值可 以划分区间。 • 输出可以是离散的分类输出可以是离散的分类，，也可以是实数也可以是实数 （（回归树回归树）。）。 • 能有效处理大量数据 • 可处理噪声数据可处理噪声数据 （（分类噪声分类噪声，，属性噪声属性噪声）） • 属性值缺失，亦可处理 2001年6月2 日 基本决策树算法基本决策树算法 • 训练数据批处理，自顶向下递归构造决策树 • DTree((examplles, attribibutes)) If 所有样本属于同一分类，返回标号为该分类的叶结点 Else if 属性值为空属性值为空，，返回标号为最普遍分类的叶结点返回标号为最普遍分类的叶结点 Else 选取一个属性，A ，作为根结点 For A的每一个可能的值vi 令令examplesexamples 为具有为具有AA=vv 的样本子集的样本子集 ii ii 从根结点出发增加分支（A=v ) i 如果examplesi为空 则创建标号为最普遍分类的叶结点则创建标号为最普遍分类的叶结点 否则递归创建子树——调用DTree(examples ,attributes-{A}) i 2001年6月2 日 根属性的选取根属性的选取 • 决策树要尽可能小 • 寻找一组数据对应的最小决策树是寻找一组数据对应的最小决策树是NP-hhardd的的 • 简单递归算法是贪婪启发式搜索，无法保证最优 • 子集应尽可能子集应尽可能 ““纯纯””，，从而易于成为叶结点从而易于成为叶结点 • 最常用的启发规则是基于信息增益(Information Gain) 2001年6月2 日 熵熵((Entropy)Entropy) • 一组样本S对于二元分类的熵(混淆度)为： Entropy (S ) −p + log2 (p +) −p − log2 (p −) 其中其中pp 和和pp 为为SS中的正例中的正例、、反例所占比例反例所占比例 ++ - • 若所有样本属于同一分类，则熵为0(定义0log0=0) • 若样本平均分布若样本平均分布((