香農(nóng)熵
變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。例如货邓，在一個(gè)數(shù)據(jù)集dataset中，dataset = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],][0,1,'no'],[0,1,'no']],在數(shù)據(jù)集dataset中隨機(jī)挑一個(gè)實(shí)例四濒，挑出標(biāo)簽值為'yes'的概率為0.4换况，挑出標(biāo)簽值為‘no’的概率為0.6,這個(gè)數(shù)據(jù)集的熵值計(jì)算為
-0.6*log(0.6,2)-0.4*log(0.4,2) = 0.9709505944546687
下面有個(gè)函數(shù)可以用于計(jì)算給定數(shù)據(jù)集的香農(nóng)熵：
香農(nóng)熵主要是作為一個(gè)指標(biāo)用于指導(dǎo)劃分?jǐn)?shù)據(jù)集职辨，以下函數(shù)用于按照特定特征劃分?jǐn)?shù)據(jù)集
信息增益（ID3）
基于香農(nóng)熵的概念和以上兩個(gè)函數(shù)，我們可以再寫一個(gè)函數(shù)用于計(jì)算如何給一個(gè)數(shù)據(jù)集進(jìn)行劃分复隆，通過對(duì)數(shù)據(jù)集的每一個(gè)特征屬性進(jìn)行劃分拨匆，然后計(jì)算劃分后的所有數(shù)據(jù)集熵值與其概率的乘積之和姆涩，并與數(shù)據(jù)集劃分前原始數(shù)據(jù)集的熵值相比較挽拂，計(jì)算降低的熵值。這部分降低的熵值就被成為‘信息增益’（用ID3表示）骨饿，通過比較各特征屬性的信息增益后亏栈，可以推算出按照哪種特征屬性分類信息增益最大，就用這種方式進(jìn)行分類宏赘。
這種分類方法看似很厲害绒北，但是仍存在一個(gè)BUG：例如，你給每個(gè)值標(biāo)一個(gè)ID察署，然后將ID作為一個(gè)特征項(xiàng)劃分?jǐn)?shù)據(jù)集后得出的熵值是零闷游，而對(duì)應(yīng)的信息增益則最大，這顯然是不對(duì)的贴汪，為了規(guī)避在個(gè)問題脐往，我們引入了另一個(gè)概率，信息增益率（C4.5）扳埂。
信息增益率（C4.5）
信息增益率 = 信息增益值／數(shù)據(jù)集本身的熵值
例如：接著上面的例子业簿，數(shù)據(jù)集dataset = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],][0,1,'no'],[0,1,'no']]的熵值為
-0.6*log(0.6,2)-0.4*log(0.4,2) = 0.9709505944546687
然后給數(shù)據(jù)集每個(gè)實(shí)例添加一個(gè)特征屬性ID，dataset = [[1,1,1,'yes'],[2,1,1,'yes'],[3,1,0,'no'],][4,0,1,'no'],[5,0,1,'no']]阳懂，如果按照ID劃分?jǐn)?shù)據(jù)集得出的熵值增益是0.97095059445466870 - 0 = 0.9709505944546687
但是數(shù)據(jù)集本身按照ID作為標(biāo)簽計(jì)算的熵值則是-1/5log(1/5,2)*5 = log(5,2),所以信息增益率為
0.9709505944546687／log(5,2) = 0.41816566007905165
決策樹
決策樹的基本邏輯就是基于以上算法的：得到原始數(shù)據(jù)集后梅尤，基于各種特征屬性的信息增益（ID3）的判斷下一步通過哪個(gè)屬性值劃分?jǐn)?shù)據(jù)集，由于特征值可能多于兩個(gè)岩调，因此可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分巷燥。經(jīng)過一次劃分之后，數(shù)據(jù)將被向下傳遞到樹分支的下一個(gè)節(jié)點(diǎn)号枕，這個(gè)節(jié)點(diǎn)上缰揪，我們可以再次劃分?jǐn)?shù)據(jù)。我們利用這個(gè)邏輯堕澄，遞歸的處理數(shù)據(jù)集邀跃，直到程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個(gè)分支下的所有實(shí)例都具有相同的分類蛙紫。
連續(xù)值的處理邏輯
我們?cè)谇懊嫣幚淼臄?shù)值都是離散了拍屑，但是如果我們需要處理連續(xù)值又該怎樣處理呢
隨機(jī)森林
好了，在引入決策樹算法以后坑傅，我們可以擴(kuò)展出一個(gè)新概念僵驰，叫“隨機(jī)森林”
