算法大致流程是: 1.獲得數據集 2.找到一個好的特征劃分數據集為兩部分 3.遞歸這一過程直到數據集內全部為同種類 4.打印由上述劃分確定的樹狀結構

那么如何劃分數據集，也就是如何確定最佳劃分狀態?當然是信息量大的劃分。信息量可以用香農熵刻畫。 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的一個劃分$

具體嚴格的數學推導我覺得可以用性質刻畫定義(數學上很多函數都是先給出性質再解函數方程獲得唯一定義，于是干脆用性質代替定義)。 顯然U(s)有性質信息量等于各部分信息量之和: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)即可，下面假設f(P(si))=U(si)$f(P(s_i))=U(s_i)$，只需要求出f(x)(0<x<1)表達式即可$f(x)(0<x<1)表達式即可$

先考慮一個簡單的問題，p=12k$p={1/over 2^k}$時，2k$2^k$個狀態信息量之和為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$，當然這僅僅解決了1p=2k${1/over p} =2^k$情形。

然后利用相同手法可以得到性質(函數方程)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和連續條件$f({1/over 2})={1/over 2}和連續條件$

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

可以得到信息量的表示方法，也就是香農熵，注意與熱力學熵推導過程一模一樣，除了常數不同。

決策樹代碼略