算法大致流程是: 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)熵刻畫。 U(s)=?Σ(pi?logpi2)，其中P(s=si)=pi，且{si}為s的一個劃分$U (s)= -/Sigma(p_i*log_2^{p_i})，其中P(s=s_i)=p_i，且/{s_i/}為s的一個劃分$

具體嚴(yán)格的數(shù)學(xué)推導(dǎo)我覺得可以用性質(zhì)刻畫定義(數(shù)學(xué)上很多函數(shù)都是先給出性質(zhì)再解函數(shù)方程獲得唯一定義，于是干脆用性質(zhì)代替定義)。 顯然U(s)有性質(zhì)信息量等于各部分信息量之和:U(s)=ΣU(si)$U(s)=/Sigma{U(s_i)}$ 并定義初值條件U(B(1，12))=1(bit)$U(B(1，{1 /over 2})) = 1(bit)$ 那么，只需要求出U(s_i)即可，下面假設(shè)f(P(si))=U(si)$f(P(s_i))=U(s_i)$，只需要求出f(x)(0<x<1)表達(dá)式即可$f(x)(0<x<1)表達(dá)式即可$

先考慮一個簡單的問題，p=12k$p={1/over 2^k}$時，2k$2^k$個狀態(tài)信息量之和為U=2kf(p)=k(bit)$U=2^kf(p)=k(bit)$，因為由定義1bit信息可以解決一個二分問題。那么f(p)=k2k=?p?logp2$f(p)={k/over{2^k}}=-p*log_2^p$，當(dāng)然這僅僅解決了1p=2k${1/over p} =2^k$情形。

然后利用相同手法可以得到性質(zhì)(函數(shù)方程)f(x)x+f(f)y=f(x+y)x+y${f(x)/over x}+{f(f)/over y}={f(x+y)/over x+y}$且有初值條件f(12)=12和連續(xù)條件$f({1/over 2})={1/over 2}和連續(xù)條件$

這就是一個中規(guī)中規(guī)中矩的函數(shù)方程了，依次解決1p${1/over p}$是整數(shù)，有理數(shù)情況，最后用連續(xù)條件(Cauchy法)推廣到實數(shù)即可。

可以得到信息量的表示方法，也就是香農(nóng)熵，注意與熱力學(xué)熵推導(dǎo)過程一模一樣，除了常數(shù)不同。

決策樹代碼略