机器学习之决策树学习-ID3算法-原理分析与C语言代码实现

机器学习之决策树学习-ID3算法原理分析与C语言代码实现作者：wxh5055保留所有版权本文先通过一个被经常使用的实例来简单说明决策树学习中ID3算法的基本原理，然后详细介绍ID3算法以及用C语言实现的方法，文章的最后给出ID3算法的完整的C语言代码。该实例的训练样本数据如表1所示。该训练样例的目标属性是PlayTennis(打网球)，即根据各属性类型Outlook(天气)、Temperature(温度)、Humidity(湿度)和Wind(风强度)的属性值判断某一天是否打网球(YesorNo)。DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesDl0RainMildNormalWeakYesDl1SunnyMildNormalStrongYesDl2OvercastMildHighStrongYesDl3OvercastHotNormalWeakYesDl4RainMildHighStrongNo表1：ID3算法使用的训练样例ID3算法即是根据上面的训练样例，自顶向下构造出一棵决策树。该决策树的最终形式如图1(TomM.Mitchell,MachineLearning)：图1:ID3算法生成的决策树现在的问题是，如何确定决策树的根结点是Outlook，而不是其他的属性类型？这就是本文介绍的ID3算法需要详细说明的问题，也是ID3算法的核心问题，即选择哪个属性作为决策树的根结点。为了确定选择哪个属性作为决策树的根结点，我们需要引入一个叫“信息增益(informationgain)”的概念，ID3算法就是选择信息增益最大的属性作为决策树的根结点。我们先给出信息增益的计算公式，然后再进一步说明公式中每个成员的含义：Gain(S,A)：属性A在训练样例S中的信息增益，在表1中A的取值为Outlook、Temperature、Humidity和Wind。Entropy(S)：训练样例的熵，稍后会进一步说明熵的计算方法。v∈Values(A)：属性A的所有可能取值的集合，比如表1中对于属性Outlook，v的取值为Sunny、Overcast和Rain。|Sv|：属性A中属性值为v的样本数，比如表1中属性Outlook的属性值等于Sunny的样本数是5，属性值等于Overcast的样本数是4，属性值等于Rain的样本数是5。|S|：训练样例的样本总数，表1中|S|等于14。Entropy(Sv)：训练样例里属性A中属性值为v的训练样本的熵，稍后会进一步详细说明其计算方法。现在我们介绍训练样例的熵的计算方法，还是先给出熵的计算公式，然后再进一步说明公式中每个成员的含义：p⊕：训练样例中目标属性为正(Yes)的样本数的比例，在表1中样本总数为14，目标属性为正(Yes)的样本数为9，所以p⊕等于9/14。pΘ：训练样例中目标属性为负(No)的样本数的比例，在表1中样本总数为14，目标属性为负(No)的样本数为5，所以pΘ等于5/14。所以该训练样例的熵Entropy(S)=-(9/14)×log2(9/14)-(5/14)×log2(5/14)=0.940。接下来我们详细介绍信息增益公式中Entropy(Sv)的计算方法，以计算属性类型为Outlook的信息增益来进行说明。属性Outlook的属性值v的取值范围为{Sunny,Overcast,Rain}，所以计算熵Entropy(Sv)就相当于要分别计算Entropy(SSunny)、Entropy(SOvercase)和Entropy(SRain)，每个代表v取不同的值时的熵。先介绍v取值Sunny时Entropy(SSunny)的计算方法。在表1的训练样例中，v=Sunny的训练样本包括{D1,D2,D8,D9,D11}，提取出来如表2所示：DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesDl1SunnyMildNormalStrongYes表2：属性Outlook中v取值Sunny的训练样本计算Entropy(SSunny)也就是把表2当成是一个完整的训练样例来计算它对应的熵，其正样本数(目标属性为Yes)等于2，负样本数(目标属性为No)等于3，总样本数等于５，所以Entropy(SSunny)=-(2/5)×log2(2/5)-(3/5)×log2(3/5)=0.971。同理，v取值Overcast时的正样本数等于4，负样本数等于0，总样本数等于４，所以(规定log20=0)Entropy(SOvercase)=-(4/4)×log2(4/4)-(0/4)×log2(0/4)=0。v取值Rain时的正样本数等于3，负样本数等于2，总样本数等于５，所以Entropy(SRain)=-(3/5)×log2(3/5)-(2/5)×log2(2/5)=0.971。至此，我们已经介绍完了属性类型为Outlook时信息增益公式中的所有成员，现在就可以计算属性Outlook的信息增益了：𝐺𝑎𝑖𝑛𝑆,𝑂𝑢𝑡𝑙𝑜𝑜𝑘=EntropyS−SvSEntropy(Sv)𝑣∈{𝑆𝑢𝑛𝑛𝑦,𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡,𝑅𝑎𝑖𝑛}Gain(S,Outlook)=0.940-((5/14)×0.971+(4/14)×0+(5/14)×0.971)=0.246。同理，属性类型为Temperature的v的取值也有3个，分别为Hot、Mild和Cool，它们对应的熵分别为：Entropy(SHot)=-(2/4)×log2(2/4)-(2/4)×log2(2/4)=1，Entropy(SMild)=-(4/6)×log2(4/6)-(2/6)×log2(2/6)=0.918，Entropy(SCool)=-(3/4)×log2(3/4)-(1/4)×log2(1/4)=0.811，Gain(S,Temperature)=0.940-((4/14)×1+(6/14)×0.918+(4/14)×0.811)=0.029。属性类型为Humidity的v的取值有两个，分别为High和Normal，它们对应的熵分别为：Entropy(SHigh)=-(3/7)×log2(3/7)-(4/7)×log2(4/7)=0.985，Entropy(SNormal)=-(6/7)×log2(6/7)-(1/7)×log2(1/7)=0.592，Gain(S,Humidity)=0.940-((7/14)×0.985+(7/14)×0.592)=0.151。属性类型为Wind的v的取值有2个，分别为Weak和Strong，它们对应的熵分别为：Entropy(SWeak)=-(6/8)×log2(6/8)-(2/8)×log2(2/8)=0.811，Entropy(SStrong)=-(3/6)×log2(3/6)-(3/6)×log2(3/6)=1，Gain(S,Wind)=0.940-((8/14)×0.811+(6/14)×1)=0.048。到这里，我们已经计算出了训练样例集中所有属性类型的信息增益，如下：Gain(S,Outlook)＝0.246，Gain(S,Temperature)=0.029，Gain(S,Humidity)=0.151，Gain(S,Wind)=0.048。所以，我们就选择了信息增益最大的属性即Outlook作为决策树的根结点。至此，我们已经比较详细的介绍了用ID3算法生成图1的决策树的根结点的整个过程。现在介绍在生成根结点之后，它的子结点的生成的详细过程。ID3算法已经计算出根结点是属性Outlook，而属性Outlook有3个属性值(Sunny,Overcast,Rain)，所以根结点有3个分支(子结点)，每个分支对应一个属性值(如图1)。现在ID3算法根据信息增益最大的属性Outlook的3个属性值，把表1的训练样例分解成3个子表，每个子表对应一个属性值。子表的生成过程就是把属性类型为Outlook下属性值为Sunny、Overcast或Rain的训练样例单独列出来，重新存储到独立的表中，如下表3、表4、表5所示。DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesDl1SunnyMildNormalStrongYes表3：信息增益最大的属性Outlook中v取值Sunny的训练样本DayOutlookTemperatureHumidityWindPlayTennisD3OvercastHotHighWeakYesD7OvercastCoolNormalStrongYesDl2OvercastMildHighStrongYesDl3OvercastHotNormalWeakYes表4：信息增益最大的属性Outlook中v取值Overcast的训练样本DayOutlookTemperatureHumidityWindPlayTennisD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoDl0RainMildNormalWeakYesDl4RainMildHighStrongNo表5：信息增益最大的属性Outlook中v取值Rain的训练样本在生成新的独立的3个子表之后，把属性类型为Outlook的列的数据(表中标示为红色的数据)全部剔出，目的是为了使任何给定的属性在决策树的任意路径上仅出现一次。以v取值Sunny为例，得到下表6的训练样例。DayTemperatureHumidityWindPlayTennisDlHotHighWeakNoD2HotHighStrongNoD8MildHighWeakNoD9CoolNormalWeakYesDl1MildNormalStrongYes表6：训练样例把表3中属性Outlook的数据剔除后的新的训练样例(v=Sunny)现在，根结点Outlook在属性值v=Sunny下的子结点就是通过递归调用ID3算法，把表6作为训练样例，得到信息增益最高的属性作为其子结点(属性Humidity的信息增益最大)。其他两个子结点也是采用同样的方法得到。依次类推，就可以得出图1所示的整颗决策树。到这里，我们已经介绍了用ID3算法生成一棵完整的决策树的过程，现在在把整个流程做个简单的总结如下：第一步：ID3算法根据表1的训练样例，利用公式计算出每个属性的信息增益，Gain(S,Outlook)＝0.246，Gain(S,Temperature)=0.029，Gain(S,Humidity)=0.151，Gain(S,Wind)=0.048。第二步：选择信息增益最大的属性Outlook作为决策树的根结点。第三步：根据根结点的属性类型Outlook的属性值个数确定其子结点数等于n=3，v={Sunny,Overcast,Rain}。第四步：根据根结点的属性的每个属性值，把训练样例的数据分解成n个独立的子表，如表3、4、5所示。第五步：把子表的属性类型为根结点属性类型的数据全部