10决策树学习.ppt

CLS算法问题 在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。 举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含。 学生 鸡肉 猪肉 牛肉 羊肉 鱼肉 鸡蛋 青菜 番茄 牛奶 健康情况 1 0 1 1 0 1 0 1 0 1 不缺钙 2 0 0 0 0 1 1 1 1 1 不缺钙 3 1 1 1 1 1 0 1 0 0 缺钙 4 1 1 0 0 1 1 0 0 1 不缺钙 5 1 0 0 1 1 1 0 0 0 缺钙 6 1 1 1 0 0 1 0 1 0 缺钙 7 0 1 0 0 0 1 1 1 1 不缺钙 8 0 1 0 0 0 1 1 1 1 缺钙 9 0 1 0 0 0 1 1 1 1 不缺钙 10 1 0 1 1 1 1 0 1 1 不缺钙 学生膳食结构和缺钙调查表 采用不同的测试属性及其先后顺序将会生成不同的决策树 鸡肉 猪肉 猪肉 牛肉 牛肉 牛肉 不缺钙（2） 缺钙（3，6） 不缺钙（4） 不缺钙（10） 缺钙（5） 不缺钙（1） 鱼肉 缺钙（5） 不缺钙（7，9） 是 否 是 否 否 否 否 否 否 是 是 是 是 是 牛奶 不缺钙 （1，2，4， 7，9，10） 缺钙 （3，5，6，8） 在上例中，显然生成的两种决策树的复杂性和分类意义相差 很大由此可见，选择测试属性是决策树学习算法中需要研究的重 要课题。 ID3 ID3算法主要针对属性选择问题。是决策树学习方法中最 具影响和最为典型的算法。 该方法使用信息增益度选择测试属性。 当获取信息时，将不确定的内容转为确定的内容，因此信 息伴着不确定性。 从直觉上讲，小概率事件比大概率事件包含的信息量大。 如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。 如何度量信息量的大小？ ID3 –信息量大小的度量 Shannon1948年提出的信息论理论。事件ai的信息量I（ ai ）可 如下度量： 其中p(ai)表示事件ai发生的概率。 假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个 发生，则其平均的信息量可如下度量： ID3 –信息量大小的度量 上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。 通常取2，并规定当p(ai)=0时 =0 公式1 在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本 划分为n个不同的类C1,C2,….Cn，这些类的大小分别标记为|C1|， |C2|，…..,|Cn|。则任意样本S属于类Ci的概率为： ID3 –信息量大小的度量 Entropy（S，A）=∑（|Sv|/|S|）* Entropy（Sv）公式2 ∑是属性A的所有可能的值v,Sv是属性A有v值的S子集 |Sv|是Sv 中元素的个数；|S|是S中元素的个数。 上面的信息熵就是利用公式1来求 ID3 –信息量大小的度量 Gain（S，A）是属性A在集合S上的信息增益 Gain（S，A）= Entropy（S） -Entropy（S，A） 公式3 Gain（S，A）越大，说明选择测试属性对分类提供的信息越多 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 64 青 高 否 优 不买 128 中 高 否 良 买 60 老 中 否 良 买 64 老 低 是 良 买 64 老 低 是 优 不买 64 中 低 是 优 买 128 青 中 否 良 不买 64 青 低 是 良 买 132 老 中 是 良 买 64 青 中 是 优 买 32 中 中 否 优 买 32 中 高 是 良 买 63 老 中 否 优 不买 1 老 中 否 优 买 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 64 青 高 否 优 不买 128 中 高 否 良 买 60 老 中 否 良 买 64 老 低 是 良 买 64 老 低 是 优 不买 64 中 低 是 优 买 128 青 中 否 良 不买 64 青 低 是 良 买 132 老 中 是 良 买 64 青 中 是 优 买 32 中 中 否 优 买 32 中 高 是 良 买 63 老 中 否 优 不买 1 老 中 否 优 买 第1步计算决策属性的熵 决策属性“买计算机？”。该属性分 两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024 P1=6