数据挖掘学习札记之ID3算法(一)
参考：
1. Wiki上的 ID3 algorithm
2. 百度文库里的一个PPT，有算例， 决策树ID3算法
3. 百度文库，PPT，很多算例，开始有信息理论，极力推荐阅读，I
4. 用Python实现ID3和C4.5 to produce adecision tree which is stored in memory. At runtime, this decision tree is used to classify new unseen test cases by working down the decision tree using the values of this test case to arrive at a terminal node that tells you what class this test case belongs to.
基本思想：
角度1. 越是小型的决策树越优于大的决策树（尽管如此该算法也不是总是生成最小的树形结构）
角度2. 引入信息论中互信息（信息增益），作为判别因素的度量，即：以信息熵的下降速度作为选取测试属性的标准，所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性
算法描述：
Day
Outlook
Temperature
Humidity
Wind
D1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo Play ball
Table 1 We need to find which attribute will be the root node in our decision tree. The gain is calculated for all four attributes:
Gain(S, Outlook) = 0.246
Gain(S, Temperature) = 0.029
Gain(S, Humidity) = 0.151
Gain(S, Wind) = 0.048 (calculated above)
Outlook attribute has the highest gain, therefore it is used as the decision attribute in the root node.
Since Outlook has three possible values, the root node has three branches (sunny, overcast, rain). The next question is "what attribute should be tested at the Sunny branch node?" Since we‘ve used Outlook at the root, we only decide on the remaining three attributes: Humidity, Temperature, or Wind.
Ssunny = {D1, D2, D8, D9, D11} = 5 examples from table1 with outlook = sunny
Gain(Ssunny, Humidity) = 0.970
Gain(Ssunny, Temperature) = 0.570
Gain(Ssunny, Wind) = 0.019
Humidity has the highest gain; therefore, it is used as the decision node. This process goes on until all data is classified perfectly or we run out of attributes.
The final decision = tree
The decision tree can also be expressed in rule format:
IF outlook = sunny AND humidity = high THEN playball = no
IF outlook = rain AND humidity = high THEN playball = no
IF outlook = rain AND wind = strong THEN playball = yes
IF outlook = overcast THEN playball = yes
IF outlook = rain AND wind = weak THEN playball = yes
ID3 has been incorporated in a number of commercial rule-induction packages. Some specific applications include medical diagnosis,credit risk assessment of loan applications, equipment malfunctions by their cause, classification of soybean diseases, and web search classification.
