算法概要 ID3(Examples, Target_attribute, Attributes) 创建树的 root 节点如果 Examples 都为正,返回 label=+ 的单节点树 root 如果 Examples 都为反,返回 label=- 的单节点树 root 如果 Attributes 为空,那么返回单节点 root , label=Examples 中最普遍的 Target_attribute 值否则开始? A? Attributes 中分类 examples 能力最好的属性? root 的决策属性?A?对于 A的每个可能值 vi ?在 root 下加一个新的分支对应测试 A=vi ?令 Examples vi为 Examples 中满足 A属性值为 vi的子集?如果 Examples vi为空?在这个新分支下加一个叶子节点,节点的 label=Examples 中最普遍的 Target_attribute 值?否则在新分支下加一个子树 ID3 ( Examples vi ,Target_attribute,Attributes -{A} ) 结束返回 root 2017-1-27 9最佳分类属性信息增益?用来衡量给定的属性区分训练样例的能力? ID3 算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性?熵刻画了任意样例集的纯度?给定包含关于某个目标概念的正反样例的样例集 S,那么 S相对这个布尔型分类的熵为 Entropy(S)=-p+log 2 p+ - p-log 2 p- ?信息论中对熵的一种解释,熵确定了要编码集合 S中任意成员的分类所需要的最少二进制位数?更一般地,如果目标属性具有 c个不同的值,那么 S相对于 c个状态的分类的熵定义为 Entropy(S)= ??? ci iipp 1 2 log 2017-1-27 10
全文预览