第二章决策树(ID3分类算法)

第二章决策树(ID3分类算法)为解决上述问题必须进行分类分类是数据挖掘中的一种主要分析手段分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：根据瓦斯状态、开采技术条件、煤层赋存状况等对危险进行分类评估根据核磁共振的结果区分肿瘤是恶性还是良性的根据星系的形状对它们进行分类划分出交易是合法或欺诈将新闻分类金融、天气、娱乐体育等主要分类方法决策树分类方法贝叶斯分类方法K-最近邻分类方法神经网络分类方法支持向量机组合学习方法不平衡数据分类问题分类模型的评价回归方法研究生学院举例说明分类任务应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法研究生学院有房婚姻状况年收入是否否否是没有已婚单身,离婚<80K>80K极快的属性训练数据模型:决策树Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

研究生学院婚姻状况有房年收入是否否否是没有已婚单身,离异<80K>80KTid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

测试数据申请模型到测试数据研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K开始从树.的根测试数据研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法研究生学院有房婚姻状况年收入是否否否是没有已婚单身,离婚<80K>80K极快的属性训练数据模型:决策树Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

决策树的例子研究生学院婚姻状况有房年收入是否否否是没有已婚单身,离异<80K>80KTid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

决策树的例子研究生学院应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根研究生学院有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根举例说明分类任务研究生学院应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法决策树在构建过程中需重点解决2个问题：(1)如何选择合适的属性作为决策树的节点去划分训练样本；(2)如何在适当位置停止划分过程，从而得到大小合适的决策树。虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益(informationgain)和Gini系数。信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性。Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度。二、DI3分类算法1.ID3分类算法提出：由Quinlan于1986年提出，它使用信息增益(informationgain)作为属性的选择标准。首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。2.ID3分类算法相关的基本概念：1）信息熵2）信息增益熵(entropy,也称信息熵)用来度量一个属性的信息量。假定S为训练集，S的目标属性C具有m个可能的类标号值，C={C1,C2,…,Cm}，假定训练集S中，Ci在所有样本中出现的频率为(i=1,2,3,…,m)，则该训练集S所包含的信息熵定义为：熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoOvercast（阴天）coolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno信息熵例题演示考虑数据集weather如下,求weather数据集关于目标属性playball的熵。目标属性解答：令weather数据集为S，其中有14个样本,目标属性playball有2个值{C1=yes,C2=no}。14个样本的分布为：9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14，C2=no在所有样本S中出现的概率为5/14。因此数据集S的熵为：信息增益：是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度(熵)的差值。假设划分前样本数据集为S,并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S,A)为样本集S的熵减去按属性A划分S后的样本子集的熵：按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集{S1,S2,…,Sk}，则按属性A划分S后的样本子集的信息熵为:其中|Si|(i,=1,2,…k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的信息增益。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno解：(1)首先由前例计算得到数据集S的熵值为0.94；(2)属性wind有2个可能的取值{weak,strong}，它将S划分为2个子集：{S1,S2},S1为wind属性取值为weak的样本子集，共有8个样本；S2为wind属性取值为strong的样本子集，共有6个样本；下面分别计算样本子集S1和S2的熵。对样本子集S1，playball=yes的有6个样本，playball=no的有2个样本，则：对样本子集S2，playball=yes的有3个样本，playball=no的有3个样本，则：利用属性wind划分S后的熵为：按属性wind划分数据集S所得的信息增益值为：函数：DT(S,F)输入：训练集数据S，训练集数据属性集合F输出：ID3决策树(1)if

样本S全部属于同一个类别Cthen(2)创建一个叶结点，并标记类标号为C；(3)return；(4)else(5)计算属性集F中每一个属性的信息增益，假定增益值最大的属性为A；(6)创建结点，取属性A为该结点的决策属性；(7)for结点属性A的每个可能的取值Vdo(8)为该结点添加一个新的分支，假设SV为属性A取值为V的样本子集；(9)if

样本SV全部属于同一个类别Cthen(10)为该分支添加一个叶结点，并标记类标号为C；(11)else(12)递归调用DT(SV,F-{A})，为该分支创建子树；(13)endif(11)endfor(12)endif以weather数据集为例，讲解ID3的建立过程。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno数据集具有属性：outlook,temperature,humidity,wind.outlook={sunny,overcast,rain}temperature={hot,mild,cool}humidity={high,normal}wind={weak,strong}首先计算总数据集S对所有属性的信息增益，寻找根节点的最佳分裂属性:Gain(S,outlook)=0.246Gain(S,temperature)=0.029Gain(S,humidity)=0.152Gain(S,wind)=0.049显然，这里outlook属性具有最高信息增益值，因此将它选为根结点.以outlook做为根结点，继续往下：思想是，以outlook的可能取值建立分支，对每个分支递归建立子树。因为outlook有3个可能值,因此对根结点建立3个分支{sunny,overcast,rain}.那么，哪个属性用来最佳划分根结点的Sunny分支？overcast分支？Rain分支？outlooksunnyovercastrain???首先对outlook的sunny分支建立子树。找出数据集中outlook=sunny的样本子集Soutlook=sunny，然后依次计算剩下三个属性对该样本子集Ssunny划分后的信息增益：Gain(Ssunny,humidity)=0.971Gain(Ssunny,temperature)=0.571Gain(Ssunny,wind)=0.371显然humidity具有最高信息增益值，因此它被选为outlook结点下sunny分支下的决策结点。outlooksunnyovercastrain?Humidity采用同样的方法，依次对outlook的overcast分支、rain分支建立子树，最后得到一棵可以预测类标号未知的样本的决策树。ID3决策树对未知样本进行预测下面利用决策树对类标号未知的样本X进行预测：X={rain,hot,normal,weak,?}ID3算法总结ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。ID3搜索的假设空间是可能的决策树的集合，搜索目的是构造与训练数据一致的一棵决策树，搜索策略是爬山法，在构造决策树时从简单到复杂，用信息熵作为爬山法的评价函数。ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每个非叶节点进行测试时能获得关于