NO IMAGE

ID3演算法的核心思想

資訊熵的下降速度作為選取測試屬性的標準,所選的測試屬性是從根節點到當前節點的路徑上尚未被考慮的具有最高資訊增益的屬性。

維基百科上對ID3演算法有比較詳細的介紹:ID3維基

計算過程相關公式

  1. xx是一個離散型的隨機變數,其概率分佈為

    p(x)=P(X=x),x∈X

    p(x)=P(X=x),x∈X
    則X的熵為

    H(X)=−∑i=0np(xi)log2p(xi)

    H(X)=-\sum_{i=0}^np(x_i)log_2p(x_i)
    約定0log20=00log_20=0。
    n 表示有多少個分類,可以理解為所選測試屬性下有多少個不同值,H越大,資訊的不確定性越大,H越小,資訊的不確定性越小,H等於0時最具確定性,這種情況是所有元素都歸為同一類,每個值的發生都有相同的概率。

  2. 參考至資訊理論中的通道的數學模型 ,有
    U=[u1,u2,u3,…,ur]U=[u_1,u_2,u_3,…,u_r],信源所發訊息,離散隨機變數;
    V=[v1,v2,v3,…,vq]V=[v_1,v_2,v_3,…,v_q],新宿所收訊息,離散隨機變數;
    P(V|U)P(V|U):轉移概率表示發生為U,接收為V的概率,存在

    ∑(vj|ui)=1,i=1,2,…,r;j=1,2,…,q

    \sum(v_j|u_i)=1,i=1,2,…,r;j=1,2,…,q

    P(V|U)P(V|U)可以這樣理解,當一個屬性中取值為UU時,對另一個屬性取值
    為VV的影響程度

  3. 先驗概率P(U)P(U):信源傳送訊息前,UU的概率分佈。其實就是上面的p(x)p(x)。

  4. 後驗概率P(U|vj)P(U|v_j) : 信宿端收到訊息vjv_j後,U的概率分佈。
  5. 後驗熵:信宿端收到vjv_j後,關於U的平均不確定性為:
    H(U|vj)=−∑i=0rP(ui|vj)log2P(ui|vj),j=1,2,…,q

    H(U|v_j)=-\sum_{i=0}^rP(u_i|v_j)log_2P(u_i|v_j),j=1,2,…,q

  6. 條件熵:
    H(U|V)=−∑j=0q∑i=0rP(ui|vj)log2P(ui|vj)

    H(U|V)=-\sum_{j=0}^q\sum_{i=0}^rP(u_i|v_j)log_2P(u_i|v_j)
    條件熵即通道疑異度,對後驗熵在輸出VV集合中求期望值,表示在信宿端收到全部輸出vv後,對信源端UU尚存在的不確定性。

  7. H(U|V)<H(U)H(U|V)<H(U)
  8. 資訊增益:衡量通過通道傳輸進行通訊後所消除的不確定性的大小,定義為:
    I(U,V)=H(U)−H(U|V)

    I(U,V)=H(U)-H(U|V)
    表示收到VV後獲得關於UU的資訊量,是不確定性的消除是信宿端所獲得的資訊量,其中:

    H(U)=−∑i=0rP(ui)log2P(ui)

    H(U)=-\sum_{i=0}^rP(u_i)log_2P(u_i)

    H(U|V)=−∑j=0q∑i=0rP(ui|vj)log2P(ui|vj)

    H(U|V)=-\sum_{j=0}^q\sum_{i=0}^rP(u_i|v_j)log_2P(u_i|v_j)

ID3演算法步驟

計算各屬性的資訊增益,找出最大者為根節點
1. 先驗熵:沒有接收到其他屬性時的平均不確定性
2. 後驗熵:接收到輸出符號Vj時關於信源的不確定性
3. 條件熵:對後驗熵在輸出符號集V中求期望,接收到全部符號後對信源的不確定性
4. 資訊增益:先驗熵與條件熵的差,是信宿端所獲得資訊量
對剩餘屬性重複上述步驟。遞迴思想。

例子後續補充