决策树

桃扇骨 2022-06-14 04:27 292阅读 0赞

1 决策树学习是以**实例为基础**的归纳学习算法，是应用最广泛的逻辑方法。

2 典型的决策树学习系统采用自顶向下的方法，在部分搜索空间中搜索解决方案。它可以确保求出一个简单的决策树，但未必是最简单的。

3 决策树常用来形成分类器和预测模型，可以对未知数据进行分类或预测、数据挖掘等。从20世纪60年代，决策树广泛应用在分类、预测、规则提取等领域。  
4 用决策树分类的步骤：  
第一步：利用训练集建立一棵决策树，建立决策树模型。这是从数据中获取知识，进行机器学习的过程。  
第二步：利用生成的决策树模型对未知的数据样本进行分类。  
从根结点开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此时叶结点代表的类即为该对象所处的类。  
5 决策树分类的步骤——建模

![Center][]

6 决策树分类的步骤——分类或预测

![Center 1][]

7 训练决策树模型的步骤：  
第一个步骤(建树)。选取部分训练数据，按广度优先递归算法建立决策树，直到每个叶子结点属于一个类为止。  
第二个步骤(剪枝)。用剩余的数据对生成的决策树进行检验，将不正确的问题进行调整，对决策树进行剪枝和增加结点，直到建立一个正确的决策树。  
建树是通过递归过程，最终得到一棵决策树，而剪枝则是为了降低噪声数据对分类正确率的影响。

8 信息论是美国数学家C.E.Shannon为解决信息传递(通信)过程问题建立的一系列理论。  
传递信息系统由三部分组成：  
信源：发送端  
信宿：接受端  
信道连接两者的通道  
9 通信过程是随机干扰环境中传递信息的过程。  
在通信前，收信者(信宿)不可能确切了解信源会发出什么样的信息；  
不可能判断信源的会处于什么样的状态，  
上述情形称为信宿对于信源状态具有不定性，又叫先验不确定性。通信结束后，信宿还仍然具有一定程度的不确定性，称为后验不确定性。  
后验不确定性总要小于先验不确定性，不可能大于先验不确定性。  
如果后验不确定性的大小等于先验不确定性的大小，表示信宿根本没有收到信息。  
如果后验不确定性的大小等于零，表示信宿收到了全部信息。  
10 信息用来消除(随机)不定性。信息的大小，由消除的不定性大小来计量。  
自信息量。在收到ai之前，收信者对信源发出ai的不确定性定义为信息符号ai的自信息量I(ai)。即I(ai)=-log2p(ai)，其中：p(ai)为信源发出ai的概率。

信息熵。自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性，定义如下：![Center 2][]  
  
其中：n为信源X所有可能的符号数，即用信源每发一个符号所提供的平均自信息量来定义信息熵。  
在随机试验之前，只了解各取值的概率分布，而做完随机试验后，就能确切地知道取值，不确定性完全消失。  
通过随机试验获得信息的数量恰好等于随机变量的熵，故熵又可作为信息的度量。  
熵从平均意义上表征信源总体信息测度。  
熵增原理：统计热力学中，熵是系统混乱度的度量。混乱度越小，熵越小。  
独裁国家、开会、上课，系统的熵小

信息不增性原理：信息学中的熵是不确定性的度量。不确定性越小，即概率越大，熵越小，信息量越小。  
在信息论中，熵H(X)表示属性X包含的信息量的多少。  
熵可以衡量属性的纯度，属性的熵越小，表明属性中的数据在属性域上的分布越不均匀。  
属性中属于某个属性值或某几个属性值的数据较多，而属于另外属性值的数据较少，则这个数据集合越纯。  
如果一个属性的所有数据都属于同一属性值，则该属性的熵为0，该属性包含的信息为0，即该属性在数据集合中不存在对数据有用的信息。  
一个属性的熵越大，说明数据在属性域上的分布越均匀，这个属性也就越不纯。  
如果属性X中的数据在属性域上均匀分布，那么属性的熵最大，其蕴含的信息越多。

11 联合熵：对于联合随机变量(X,Y)，如果每个可能的输出(x,y)对应的概率为P(x,y)，

定义(X,Y)所能提供的信息量为联合熵，公式为：

![Center 3][]

条件熵：用于衡量在属性Y己知的情况下，属性X的不确定性程度，或者说属性X对属性Y的依赖性强弱程度。  
在给定Y条件下，X的熵：  
![Center 4][]

12 可证：H(X|Y)<H(X)，H(Y|X)<H(Y)  
上式表明，由于事物总是有联系的，因此，在平均意义上，对随机变量X的了解总能使随机变量Y的不确定性减少。

同样，对Y的了解也会减少X的不确定性。  
互信息：已知随机变量Y后，X的不确定度的减少量为H(X)-H(X|Y)，它是己知Y的取值后所提供的有关X的信息。

13 两个离散随机变量X和Y之间的互信息为：

![Center 5][]

性质：  
I(X,Y)=I(Y,X)，I(Y,X)=H(X)+H(Y)-H(X,Y)  
0≤I(X,Y)≤min(H(X),H(Y))  
当随机变量X和Y之间相互独立时，有I(X,Y)=0。  
由于事物之间总是相互联系的，在己知一个随机变量的某个数值的条件下，其余事物之间也仍然存在着相互联系。

14 条件互信息：在随机变量Z的一个己知值z的条件下，随机变量X和随机变量Y之间的互信息定义为：

![Center 6][]

可证：I(X,Y|z)=H(X|z)+H(Y|z)-H(X,Y|z)

15条件互信息：在随机变量Z的一个己知值z的条件下，随机变量X和随机变量Y之间的互信息定义为：

![Center 7][]

可证：I(X,Y|z)=H(X|z)+H(Y|z)-H(X,Y|z)

16 ID3学习算法  
ID3决策树学习算法是贪心算法，采用自顶向下的递归方式构造决策树。  
（1）针对所有训练样本，从树的根节点处开始，选取一个属性来分区这些样本。  
（2）属性的每一个值产生一个分枝。按属性值将相应样本子集移到新生成的子节点上。  
（3）递归处理每个子节点，直到每个节点上只包含同类样本。  
分类规则：从根到达决策树的叶节点的每条路径。  
关键问题：节点属性选择。  
ID3属性选择假设：决策树的复杂度和所给属性值表达的信息量密切相关。

算法：Decision\_Tree（samples,attribute\_list）  
输入：由离散值属性描述的训练样本集samples；候选属性集合atrribute\_list。  
输出：一棵决策树。  
方法：  
(1)创建节点N；  
(2)if samples都在同一类C中then 返回N作为叶节点，以类C标记；  
(3)if attribute\_list为空 then  
(4) 返回N作为叶节点，以samples中最普遍的类标记；//多数表决  
(5)选择attribute\_list中具有最高信息增益的属性test\_attribute；  
(6)test\_attribute标记节点N；  
(7)for each test\_attribute的已知值v //划分samples  
(8) 由节点N分出一个对应test\_attribute=v的分支；  
(9) 令Sv为samples中test\_attribute=v的样本集合； //一个划分块  
(10) if Sv为空 then 加上一个叶节点，以samples中最普遍的类标记；  
(11) else 加入一个由Decision\_Tree(Sv,attribute\_list–test\_attribute)返回的节点。

设S是n个数据样本的集合，将样本集划分为k个不同的类Ci(i=1,2,…,k)，每个类Ci含有的样本数目为ni，则S划分为k个类的信息熵或期望信息为：

![Center 8][]

其中：pi为S中的样本属于第i类Ci的概率，即pi＝ni/n。信息以二进制编码，熵以二进制位的个数来度量编码的长度，因此，对数的底为2。  
当样本属于每个类的概率相等时，即对任意第i类有pi=1/k时，上述的熵取到最大值log2k。而当所有样本属于同一个类时，S的熵为0。其他情况的熵介于0～log2k之间。

图4.1是k=2时布尔分类的熵函数随pi从0到1变化时的曲线。

熵反映对S分类的不确定性。熵值越小，划分的纯度越高，不确定性越低。

![Center 9][]

信息增益：指用这个属性对样本分类而导致的熵的期望值下降。  
假设属性A的所有不同值的集合为Values(A)，Sv是S中属性A的值为v的样本子集，即Sv=\{sSA(s)=v\}，在选择属性A后的每一个分支节点上，对该节点的样本集Sv分类的熵为E(Sv)。选择A导致的期望熵定义为每个子集Sv的熵的加权和，权值为属于Sv的样本占原始样本S的比例，即期望熵为：

![Center 10][]

其中：E(Sv)是将Sv中的样本划分到k个类的信息熵。

属性A相对样本集合S的信息增益Gain(S,A)定义为：  
Gain(S,A)=E(S)–E(S,A)  
因知道属性A的值后导致的熵的期望压缩。Gain(S,A)越大，说明选择测试属性A对分类提供的信息越多。  
Quinlan的ID3算法就是在每个节点选择信息增益Gain(S,A)最大的属性作为测试属性。  
  
17 例4.1 决策树归纳学习。表4.1给出训练样本集，类标号属性PlayTennis有两个不同值\{yes,no\}，即有两个不同的类。设C1对应于yes，有9个样本；C2对应于no，有5个样本。  
![Center 11][]

解：现计算每个属性的信息增益。  
对给定样本分类所需的期望信息为：  
E(S)=–(9/14)log2(9/14)–(5/14)log2(5/14)=0.940  
Values(Outlook)=\{Sunny,Overcast,Rain\}，  
SSunny=\{D1,D2,D8,D9,D11\}，|Ssunny|=5，其中2个属于类C1，3个属于类C2，故有：  
E(SSunny)=–(2/5)log2(2/5)–(3/5)log2(3/5)=0.971  
同理，E(SOvercast)=–(4/4)log2(4/4)–(0/4)log2(0/4)=0  
E(SRain)=–(3/5)log2(3/5)–(2/5)log2(2/5)=0.971

因此属性Outlook的期望熵为：E(S,Outlook)=(5/14)E(SSunny)+(4/14)E(SOvercast)  
\+(5/14)E(SRain)=0.694  
故A的信息增益为：Gain(S,Outlook)=E(S)–E(S,A)=0.940–0.694=0.246  
同理：Gain(S,Humidity)=0.151  
Gain(S,Wind)=0.048  
Gain(S,Temperature)=0.029

Outlook的信息增益最大，令属性Outlook为根节点的测试属性，并对应每个值（Sunny,Overcast,Rain）

在根节点向下创建分支，形成如图4.2的部分决策树。

![Center 12][]

在Outlook=Sunny节点SSunny=\{D1,D2,D8,D9,D11\}，对应的训练样本集，Gain(Ssunny,Humidity)=0.970，

Gain(SSunny,Temperature)=0.570，Gain(SSunny,Wind)=0.019  
因此，在该节点应选取的测试属性是Humidity。其余类同。  
如果从根结点到当前结点的路径己包括所有属性，或者当前结点的训练样本同属一类时，算法结束。

由ID3算法返回的关于playTennis的最终决策树如图4.3所示。  
从决策树的树根到树叶的每条路径对应一组属性测试的合取，决策树代表这些合取式的析取。

例如，图4.3中的决策树对应的表达式为：(Outlook=SunnyHumidity=Normal)(Outlook=Overcast)  
(Outlook=RainWind=Weak)

if-then形式的分类规则。例如图4.3中最左侧的路径对应的据测规则：  
if (Outlook=SunnyHumidity=High) then PlayTennis=No  
  
![Center 13][]

[Center]: /images/20220614/fc7d79acf69e4cfb87e4cfb0c3fbd583.png
[Center 1]: /images/20220614/64056d9384b24737b68caae2dcb7a5d2.png
[Center 2]: /images/20220614/00abf82525b74309bcb4d577decc5fab.png
[Center 3]: /images/20220614/2355243a224d4c038539ee024b989a57.png
[Center 4]: /images/20220614/5f17bbbca1b14757b81657bfa1a93530.png
[Center 5]: /images/20220614/80d2e9fd5cd04c5fbd6e1610b1beefbe.png
[Center 6]: /images/20220614/6698e2d5207946a69ddaabd26d2efa96.png
[Center 7]: /images/20220614/9a5ee17090ff45b59841ae5565dc0562.png
[Center 8]: /images/20220614/0ffbe745f24f4f1096362fdcbb3c5660.png
[Center 9]: /images/20220614/4f6d9d825dbc4054bf01267d21ac3376.png
[Center 10]: /images/20220614/fd9d832e8a254a4593f682a7d466df2a.png
[Center 11]: /images/20220614/162dd13fe2e24895bad24b912043efb6.png
[Center 12]: /images/20220614/2ba2055960634061b9a2f357aa20e965.png
[Center 13]: /images/20220614/db7b850b35374f588efc16dcb2fa26ff.png