決策樹(shù)學(xué)習(xí)算法概要(編輯修改稿)
2025-01-30 21:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 P)是 P的連續(xù)函數(shù) (0≤P≤1)； ②對(duì)稱(chēng)性： H(P1， … ， Pn)與 P1， … ， Pn的排列次序無(wú)關(guān)； ③可加性：若 Pn＝ Q1+Q2＞ 0，且 Q1， Q2≥0，則有H(P1， … ， Pn1， Q1， Q2)＝ H(P1， … ， Pn1)+PnH；則一定有下列唯一表達(dá)形式： H(P1， … ， Pn)＝ CP(i)logP(i) 其中 C為正整數(shù)，一般取 C＝ 1，它是信息熵的最基本表達(dá)式。 ? 信息熵除了上述三條基本性質(zhì)外，還具有一系列重要性質(zhì)，其中最主要的有： ①非負(fù)性： H(P1， … ， Pn)≥0； ②確定性： H(1， 0)＝ H(0， 1)＝ H(0， 1， 0， …) ＝ 0； ③擴(kuò)張性： Hn1(P1， … ， Pnε， ε)＝ Hn(P1， … ， Pn)； ④極值性： P(xi)logP(xi)≤P(xi)logQ(xi)；這里 Q(xi)＝ 1； ⑤上凸性： H[λP +(1λ)Q]＞ λH(P)+(1λ)H(Q)，式中 0＜ λ＜ 1。 屬性選擇 ? 熵 (entropy)：給定有關(guān)某概念的正例和負(fù)例的集合 S。對(duì)此 BOOLEAN分類(lèi)的熵為： Entropy(S)= pos log2(pos) – neg log2(neg) “ pos”和” neg”分別表示 S中正例和負(fù)例的比例。并定義： 0log2(0)=0 ? 如果分類(lèi)器有 c個(gè)不同的輸出，則： Entropy(S)= ?ci=1pi log2(pi) pi表示 S中屬于類(lèi) i的比例 ?例 1： p1 = p2 = 1/2 H1 = (1/2)*log2(1/2) (1/2)*log2(1/2) = 1 ?例 2： p1 = 1/4 p2 = 3/4 H2 = (1/4)* log2(1/4) (3/4)*log2(3/4)= ?例 3： p1 = 1 p2 = 0 H3 = 1 * log21 = 0 屬性選擇 ? 構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的屬性。對(duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。人們研究出，一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)膶傩?。由于?gòu)造最小的樹(shù)是 NP難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的屬性 。 ? ID3算法的本質(zhì)： 就是構(gòu)造一棵熵值下降平均最快的決策樹(shù) 。 最佳分類(lèi)屬性 ? 用 信息增益 度量期望的熵降低 ? 屬性的信息增益，由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低 ? Gain(S,A)是在知道屬性 A的值后可以節(jié)省的二進(jìn)制位數(shù) ????)()(||)(),(AValu esvvv SEntr opy
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1