【正文】 fo ???? )(||||)(1jvjjA DIDDDInf o ?? ?? (D)InfoInfo(D)G ai n(A ) A??使用屬性 A得到準(zhǔn)確分類所需信息 思考： 如果考慮充當(dāng)唯一識(shí)別的屬性，如 product_ID。當(dāng)?shù)竭_(dá)節(jié)點(diǎn) m的所有實(shí)例都不屬于 類時(shí)， 為 0，當(dāng)?shù)竭_(dá)節(jié)點(diǎn) m的所有實(shí)例都屬于 類時(shí)， 為 1。通過(guò)屬性選擇度量，選擇出最好的將樣本分類的屬性。 簡(jiǎn)介 決策樹(shù)的結(jié)構(gòu) 決策樹(shù)算法以樹(shù)狀結(jié)構(gòu)表示數(shù)據(jù)分類的結(jié)果。 一種度量不純性的可能函數(shù)是熵函數(shù) （ entropy)。對(duì)product_ID的分裂結(jié)果？ Infoproduct_ID(D)=0 Gain(product_ID)最大 有無(wú)實(shí)際意義？ 標(biāo)識(shí)屬性被選為分裂屬性，但標(biāo)識(shí)屬性的分支對(duì)預(yù)測(cè)未知實(shí)例的類別并無(wú)任何幫助 ? ： 使用 “分裂信息（ split information） ”值將 gain規(guī)范化 表示屬性 A第 j個(gè)劃分的權(quán)重。 (2) 為了處理大數(shù)據(jù)集或連續(xù)量的種種改進(jìn)算法（離散化、取樣）不僅增加了分類算法的額外開(kāi)銷，而且降低了分類的準(zhǔn)確性，對(duì)連續(xù)性的字段比較難預(yù)測(cè)，當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快，對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作。 首先將連續(xù)型屬性離散化 ， 把連續(xù)型屬性的值分成不同的區(qū)間 ， 依據(jù)是比較各個(gè) 分裂點(diǎn) Gian值的大小 。 ? 平均信息量 若一個(gè)系統(tǒng)中存在多個(gè)事件 E1,E2,… En 每個(gè)事件出現(xiàn)的概率是 p1,p2,… pn 則這個(gè)系統(tǒng)的平均信息量是 ? 指的是系統(tǒng)的混亂的程度 ! (bits) ? 系統(tǒng)越無(wú)序、越混亂，熵就越大。 根節(jié)點(diǎn) 非葉子節(jié)點(diǎn)（決策點(diǎn)） 葉子節(jié)點(diǎn) 分支 決策樹(shù)的結(jié)構(gòu) 4 根部節(jié)點(diǎn) (root node) 非葉子 節(jié)點(diǎn) (nonleaf node) (代表測(cè)試的條件 ，對(duì) 數(shù)據(jù)屬性的測(cè)試 ) 分支 (branches)(代表測(cè)試的結(jié)果 ) 葉節(jié)點(diǎn) (leaf node) (代表分類后所獲得 的分類標(biāo)記 ) 2023/2/10 單變量樹(shù) 每個(gè)內(nèi)部節(jié)點(diǎn)中的測(cè)試只使用一個(gè)輸入維。 ?貪心算法：在每一步選擇中都采取在當(dāng)前狀態(tài)下最好 /優(yōu)的選擇。對(duì)于節(jié)點(diǎn) m，令 為到達(dá)節(jié)點(diǎn) m的訓(xùn)練實(shí)例數(shù)， 個(gè)實(shí)例中 個(gè)屬于 類，而 。 ? 可能無(wú)法達(dá)到這種結(jié)果，因?yàn)闊o(wú)法避免訓(xùn)練集包含兩個(gè)具有相同屬性集，但具有不同類的實(shí)例。一個(gè)例子：在 Irvine 機(jī)器學(xué)習(xí)知識(shí)庫(kù)中，最大可以允許的數(shù)據(jù)集僅僅為 700KB ， 2023 條記錄。 例子 ： 60 70 75 85 90 95 100 120 125 220 60 70 75 85 90 95 100 120 125 220 分割成 TaxIn=80 和 TaxIn80 分割成 TaxIn= 和 TaxIn ? 實(shí)際上 , 這就是 “離散化 ”過(guò)程 連續(xù)值的處理 Ti d Re f un d M ar italS t atu sT ax ableIne Chea t1 Y es S i n gl e 12 5 K No2 No M arr i ed 10 0 K No3 No S i n gl e 70K No4 Y es M arr i ed 12 0 K No5 No Di v orc ed 95K Y es6 No M arr i ed 60K No7 Y es Di v orc ed 22 0 K No8 No S i n gl e 85K Y es9 No M arr i ed 75K No10 No S i n gl e 90K Y es102. 對(duì) 每個(gè) 候選的分界點(diǎn)，分別計(jì)算熵 例子 : 測(cè)試以 80分界的情形 e ntr op y ( ) 0 bitsc he at ?37I nf o( T a xI n|80) 0 5 0 bit s10 10? ? ? ? ?(1). TaxIn=80 (2). TaxIn80 223 3 4 4e ntr opy ( ) l og l og =0 .985 bit s7 7 7 7c he at ? ? ?(3). 加權(quán)平均 同理 , 測(cè)試以 95分界的情形 , Info(TaxIn|95)= bits 3. 比較取 每個(gè) 分界點(diǎn)的信息增益，選擇最大的一個(gè) ：有未知值的樣本是按照已知值的相對(duì)頻率隨機(jī)分布的。 ? 如果一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)類值在可能的類值上均勻分布，則稱節(jié)點(diǎn)的熵（無(wú)序性）最大。如果 是數(shù)值的（有序的），則測(cè)試函數(shù)是比較： 其中 是適當(dāng)選擇閾值。 非參數(shù)學(xué)習(xí)算法。 y = DecisionTree( x ) Example of a Dec