Decision Tree learning

梦里梦外; 2021-12-19 15:53 127阅读 0赞

[Decision Tree learning][]

Target output is discrete(i.e. binary, or multiple classes)...

What decision trees:

![2010050702105725.jpg][]

The expression is:

![2010050702162766.jpg][]

How to learn? Learn from the table below.

![2010050703320790.jpg][]

The ID3 Algorithm

At each node:

select the feature that results in the largest expected reduction in entorpy for the target label.

select the feature with largest information gain.

D = THE TRAINING DATA

T = the random variable corresponding to play tennis.

p(T = yes) = 9/14

p(T = no) = 5/14

--------------------

The definition of entropy:

From:(http://zhidao.baidu.com/question/454628)

假设在不改变宏观物质的表现的情况下，微观分子的可能排列的总数为W, 则熵S=lgW
    譬如，一个很乱的书架，共有3层，上面随机放着十本书。那么，W=10^3,S=lgW=3
    实际上熵是一个表明系统混沌程度的状态量.
    From: (http://tieba.baidu.com/f?kz=66299285)

<table> 
 <tbody> 
  <tr> 
   <td><p>&nbsp;只有当你所使用的那个特定系统中的能量密度参差不齐的时候，能量才能够转化为功，这时，能量倾向于从密度较高的地方流向密度较低的地方，直到一切都达到均匀为止。正是依靠能量的这种流动，你才能从能量得到功。<br>　　江河发源地的水位比较高，那里的水的势能也比河口的水的势能来得大。由于这个原因，水就沿着江河向下流入海洋。要不是下雨的话，大陆上所有的水就会全部流入海洋，而海平面将稍稍升高。总势能这时保持不变。但分布得比较均匀。<br>　　正是在水往下流的时候，可以使水轮转动起来，因而水就能够做功。处在同一个水平面上的水是无法做功的，即使这些水是处在很高的高原上，因而具有异常高的势能，也同样做不了功。在这里起决定性作用的是能量密度的差异和朝着均匀化方向的流动。<br>　　不管对哪一种能量来说，情况都是如此。在蒸汽机中，有一个热库把水变成蒸汽，还有一个冷库把蒸汽冷凝成水。起决定性作用的正是这个温度差。在任何单一的、毫无差别的温度下——不管这个温度有多高——是不可能得到任何功的。<br>　　“熵”是德国物理学家克劳修斯在１８５０年创造的一个术语，他用它来表示任何一种能量在空间中分布的均匀程度。能量分布得越均匀，熵就越大。如果对于我们所考虑的那个系统来说，能量完全均匀地分布，那么，这个系统的熵就达到最大值。<br>　　在克劳修斯看来，在一个系统中，如果听任它自然发展，那么，能量差总是倾向于消除的。让一个热物体同一个冷物体相接触，热就会以下面所说的方式流动：热物体将冷却，冷物体将变热，直到两个物体达到相同的温度为止。如果把两个水库连接起来，并且其中一个水库的水平面高于另一个水库，那么，万有引力就会使一个水库的水面降低，而使另一个水面升高，直到两个水库的水面均等，而势能也取平为止。<br>　　因此，克劳修斯说，自然界中的一个普遍规律是：能量密度的差异倾向于变成均等。换句话说，“熵将随着时间而增大”。<br>　　对于能量从密度较高的地方向密度较低的地方流动的研究，过去主要是对于热这种能量形态进行的。因此，关于能量流动和功－能转换的科学就被称为“热力学”，这是从希腊文“热运动”一词变来的。<br>　　人们早已断定，能量既不能创造，也不能消灭。这是一条最基本的定律；所以人们把它称为“热力学第一定律”。　　克劳修斯所提出的熵随时间而增大的说法，看来差不多也是非常基本的一条普遍规律，所以它被称为“热力学第二定律”。</p> </td> 
  </tr> 
 </tbody> 
</table>

In this case, the definition of entropy is:  
![2010050703153473.jpg][]  
For example:  
![2010050703154653.jpg][]  
The ID3  
Algorithm (Training data D, Features F):  
if all examples in D have the same label:  
　　return a leaf node with that label  
let x belogn to F be the feature with the largest information gain  
let T be a tree root lableled with feature X  
let D1, D2,...Dk be the partition produced by splitting D on feature X  
for each Di belong to \{D1,D2,...Dk\}  
　　let Ti = ID3(Di, F-\{X\})  
　　add Ti as a new branch of T  
return T  
  
How to erazor the tree?(reduced error pruning)  
Will follow up on next Tuesday(May 11)

Refereneces:

\[1\] http://ir.hit.edu.cn/qinbing\_01.ppt

\[2\]http://zhidao.baidu.com/question/454628

\[3\]http://tieba.baidu.com/f?kz=66299285

posted on 2010-05-07 03:42 [Zhu Qing][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

转载于:https://www.cnblogs.com/Qing\_Zhu/archive/2010/05/07/1729366.html

[Decision Tree learning]: https://www.cnblogs.com/Qing_Zhu/archive/2010/05/07/1729366.html
[2010050702105725.jpg]: /images/20211219/0ab554d9909948e99d137785fa923029.png
[2010050702162766.jpg]: /images/20211219/0f7e90353877474784381da2c7eefaf6.png
[2010050703320790.jpg]: /images/20211219/937ebe35269c4bb1adcc8c1916880fcc.png
[2010050703153473.jpg]: /images/20211219/c3a3879a899c4a9c8b82bbadc9372ca1.png
[2010050703154653.jpg]: /images/20211219/3905830512494cc5bf375bbc50c128cf.png
[Zhu Qing]: https://www.cnblogs.com/Qing_Zhu/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=1729366