劃分數(shù)據(jù)集是決策樹算法的關(guān)鍵。劃分的方法也多種多樣，有ID3，C4.5，CART等。

ID3：基于信息熵來選擇最佳的測試屬性，其選擇了當(dāng)前樣本集中具有最大信息增益值的屬性作為測試屬性；

C4.5：相對ID3 來說避免了采用信息增益度量存在的一個缺點 ， 而C4.5 采用了信息增益比率來選擇分支的準(zhǔn)則；

CART：與 C4.5 算法類似，只是屬性選擇的指標(biāo)采用的是基尼系數(shù)；

無論哪種方式，都是與信息熵強關(guān)聯(lián)的，因此，我們先來看下什么是信息熵。

劃分數(shù)據(jù)的大原則是將無序的數(shù)據(jù)變得更加有序。我們在劃分數(shù)據(jù)集前后，信息發(fā)生的變化稱為信息增益。我們只要計算出信息增益，通過對比每個特征值劃分數(shù)據(jù)集獲得的信息增益，就能找出最好的方式，即獲得信息增益最高的特征。

集合信息的度量方式叫做香農(nóng)熵或者簡稱為熵。為什么叫做熵呢？因為誰也不知道這玩意兒代表什么意思，所以它是最合適的名字。香農(nóng)是二十世紀(jì)最聰明的人之一，我一方面是在讀大學(xué)的時候見到了信息的定義的時候知道了香農(nóng)，另一方面應(yīng)該是在讀《圖靈傳》的時候。這個概念挺匪夷所思的，熵定義為信息的期望值，信息的定義公式是，如果待分類的事務(wù)可能劃分在多個分類之中，則符號Xi的信息定義為：

那我們來看下，如果集合只有1個元素，信息量為多少呢？當(dāng)1個元素時，概率是100%，經(jīng)計算，信息量為0。這就代表，當(dāng)一件事情為確信的時候，信息定義是0。

如果一件事的概率有兩種可能，每種可能是50%，如何計算呢？

log2(0.5)=-1，再取符號就是1，即每一項的信息定義為1。

我們對整個集合的信息量進行評估，就需要將每一項的信息量加到一起，即：

這個式子比之前面的，多了一個概率相乘，那么如剛才說的場景，即0.5*1+0.5*1=1。二分的場景，信息總量從0增加到了1。

想象一個極端的場景，即集合有無數(shù)多的可能，這個時候假設(shè)p(x)=1/(2^x)（這個時候，如果每個可能性都是差不多的，那實際n=2^x），x為一個接近無窮大的數(shù)，那么log2(p(x))就為-x，x*2^x/(2^x)=x，則得出當(dāng)可能性足夠多的時候，熵會大到一個接近無窮大的數(shù)（我們不去考慮無窮大的場景，因為這個場景下也許啥事都能發(fā)生，我的數(shù)學(xué)基礎(chǔ)還不足以去考慮無窮的場景）。

因此，熵越大，代表的就是無序（即可能性太多），而反之則是有序。生命產(chǎn)生及維持的過程，就是一個局部區(qū)域的熵減過程，人要做到專注，進入心流狀態(tài)，也是個減熵的過程。冥想也是……好吧，扯遠了。

我們規(guī)劃決策樹，目的就是要從無序走向有序，并且找到能讓熵減最大化的特征。在這里，可能會有點理解上的問題，因為我們剛才在討論信息增益，但實際上這個增益，是用：

劃分前的信息熵- 劃分后的信息熵

劃分前會更無序，所以這個值更大一些，而劃分后會變的有序，從而這個值變的小一些。而這兩者的差，其實越大就代表劃分后的熵減越大。這個一定要注意。雖然我認為確實如此，但是還是動手檢測了一下（用《機器學(xué)習(xí)實戰(zhàn)》第三章的數(shù)據(jù)集和代碼），打印截圖如下：

數(shù)據(jù)集的定義為：

def createDataSet():

????dataSet = [[1, 1, 'yes'],

???????????????[1, 1, 'yes'],

???????????????[1, 0, 'no'],

???????????????[0, 1, 'no'],

???????????????[0, 1, 'no']]

????labels = ['no surfacing', 'flippers']

????#change to discrete values

????return dataSet, labels

如上代碼太簡單，就不解釋了。

可見，在第一輪劃分中，最初的香農(nóng)熵為0.97，而兩種不同的劃分（以特征1和特征2；是否屬于魚類屬于標(biāo)簽就不作為特征）后計算出的香農(nóng)熵分別為0.42和0.17，都比原先的要小。而越小，信息增益就越大，所以一定要搞清楚這個關(guān)系。

下一篇，我們就來看看信息熵以及選出能夠帶來最大信息增益的特征的代碼實現(xiàn)。