基于香農(nóng)熵的決策樹算法
《機(jī)器學(xué)習(xí)實戰(zhàn)》一書中有介紹構(gòu)造決策樹的算法。 所謂決策樹就是已知一些項特征的信息和項最終分類,求通過特征判斷項最終分類的遞歸決策樹。例如書中的例子是判斷一個動物是不是魚類,下面為一個數(shù)據(jù)集。
def createDataSet(): dataSet = [/ [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels = ['no surfacing', 'fl書里舉的另一個例子是隱形眼鏡的問題。書里提供了繪圖引擎用于繪制決策樹。算法大致流程是: 1.獲得數(shù)據(jù)集 2.找到一個好的特征劃分?jǐn)?shù)據(jù)集為兩部分 3.遞歸這一過程直到數(shù)據(jù)集內(nèi)全部為同種類 4.打印由上述劃分確定的樹狀結(jié)構(gòu)
那么如何劃分?jǐn)?shù)據(jù)集,也就是如何確定最佳劃分狀態(tài)?當(dāng)然是信息量大的劃分。信息量可以用香農(nóng)熵刻畫。
具體嚴(yán)格的數(shù)學(xué)推導(dǎo)我覺得可以用性質(zhì)刻畫定義(數(shù)學(xué)上很多函數(shù)都是先給出性質(zhì)再解函數(shù)方程獲得唯一定義,于是干脆用性質(zhì)代替定義)。 顯然U(s)有性質(zhì)信息量等于各部分信息量之和:
先考慮一個簡單的問題,
然后利用相同手法可以得到性質(zhì)(函數(shù)方程)
這就是一個中規(guī)中規(guī)中矩的函數(shù)方程了,依次解決
可以得到信息量的表示方法,也就是香農(nóng)熵,注意與熱力學(xué)熵推導(dǎo)過程一模一樣,除了常數(shù)不同。
決策樹代碼略
新聞熱點
疑難解答