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