【正文】 student? credit rating? no yes fair excellent =30 40 no no yes yes yes 30..40 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 15 決策樹(shù)算法 ? 基本算法（貪心算法） ? 自上而下分而治之的方法 ? 開(kāi)始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn) ? 屬性都是種類(lèi)字段 (如果是連續(xù)的，將其離散化 ) ? 所有記錄用所選屬性遞歸的進(jìn)行分割 ? 屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量 (如 , information gain) ? 停止分割的條件 ? 一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類(lèi)別 ? 沒(méi)有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 16 屬性選擇的統(tǒng)計(jì)度量 ? Information gain (ID3/) ? 所有屬性假設(shè)都是種類(lèi)字段 ? 經(jīng)過(guò)修改之后可以適用于數(shù)值字段 ? Gini index (IBM IntelligentMiner) ? 能夠適用于種類(lèi)和數(shù)值字段 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 17 Information Gain (ID3/) ? 選擇屬性的標(biāo)準(zhǔn)：具有最高 Information Gain ? 假設(shè)有兩個(gè)類(lèi) , P 和 N ? 假設(shè)集合 S中含有 p個(gè)類(lèi)別 P的記錄 ,n個(gè)類(lèi)別 N的記錄 ? 決定任意一個(gè)記錄屬于類(lèi)別 P或者 N所需要的 information. npnnpnnppnppnpI??????? 22 l o gl o g),(2020年 10月 5日星期一 Data Mining: Concepts and Techniques 18 Information Gain 在決策樹(shù)中的使用 ? 假設(shè)使用屬性 A將把集合 S分成 V份 {S1, S2 , …, Sv} ? 如果 Si 中包含 pi 個(gè)類(lèi)別為 P的記錄 , ni 個(gè)類(lèi)別為 N,的記錄。 ? 典型應(yīng)用 ? 信用評(píng)分 ? Direct Marketing ? 醫(yī)療診斷 ? ………… 分類(lèi)和預(yù)測(cè) 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 4 分類(lèi)的兩個(gè)步驟 ? 模型創(chuàng)建 : 對(duì)一個(gè)類(lèi)別已經(jīng)確定的模型創(chuàng)建模型 ? 沒(méi)一條記錄都屬于一個(gè)確定的類(lèi)別，我們使用類(lèi)標(biāo)簽屬性記錄類(lèi)別。 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 5 分類(lèi)過(guò)程：模型創(chuàng)建 訓(xùn)練集 N A M E RANK Y E A R S T E N U R E DM ik e A s s is t a n t P r o f 3 noM a r y A s s is t a n t P r o f 7 y e sB il l P r o f e s s o r 2 y e sJ im A s s o c ia t e P r o f 7 y e sD a v e A s s is t a n t P r o f 6 noA n n e A s s o c ia t e P r o f 3 no分類(lèi)算法 IF rank = ‘professor’ OR years 6 THEN tenured = ‘yes’ 模型 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 6 分類(lèi)過(guò)程 (2): 使用模型 模型 測(cè)試集 N A M E RANK Y E A R S T E N U R E DT o m A s s i s t a n t P r o f 2 noM e r l i s a A s s o c i a t e P r o f 7 noG e o r g e P r o f e s s o r 5 y e sJ o s e p h A s s i s t a n t P r o f 7 y e s未知數(shù)據(jù) (Jeff, Professor, 4) Tenured? 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 7 有監(jiān)督和無(wú)監(jiān)督學(xué)習(xí) ? 有監(jiān)督學(xué)習(xí) (分類(lèi) ) ? 訓(xùn)練集是帶有類(lèi)標(biāo)簽的 ? 新的數(shù)據(jù)是基于訓(xùn)練集進(jìn)行分類(lèi)的。 X2檢驗(yàn) 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 22 從樹(shù)中生成分類(lèi)規(guī)則 ? 用 IFTHEN 這種形式來(lái)表現(xiàn)規(guī)則 ? 每個(gè)葉子節(jié)點(diǎn)都創(chuàng)建一條規(guī)則 ? 每個(gè)分割都成為一個(gè)規(guī)則中的一個(gè)條件 ? 葉子節(jié)點(diǎn)中的類(lèi)別就是 Then的內(nèi)容 ? 規(guī)則對(duì)于人來(lái)說(shuō)更容易理解 ? 例子 IF age = “=30” AND student = “no” THEN buys_puter = “no” IF age = “=30” AND student = “yes” THEN buys_puter = “yes” IF age = “31…40” THEN buys_puter = “yes” IF age = “40” AND credit_rating = “excellent” THEN buys_puter = “yes” IF age = “=30” AND credit_rating = “fair” THEN buys_puter = “no” 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 23 在分類(lèi)中避免過(guò)度適應(yīng) (Overfit) ? 在訓(xùn)練集中生成的會(huì)可能會(huì) Overfit ? 太多的分支 , 有些可能是對(duì)異常例外的反映 ? 在進(jìn)行預(yù)測(cè)的時(shí)候準(zhǔn)確率比較差 ? 兩種 ? 預(yù)修剪 : ? 難點(diǎn)：選擇一個(gè)域值比較困難 ? 后修建 : 先生成完整的樹(shù)，然后進(jìn)行修剪 ? 使用另外一個(gè)的一個(gè)測(cè)試集來(lái)決定哪個(gè)樹(shù)最好 2020年 10月 5日星期一 Data Mining: Concepts and Techniques 24 決定最終樹(shù)大小的方法 ? 使用部分?jǐn)?shù)據(jù)： ? 使用全部數(shù)據(jù)： ? 使用一個(gè)統(tǒng)計(jì)測(cè)試 (., chisquare) 來(lái)估計(jì)保留或者修剪掉一個(gè)分支的影響 ? 使用最小描述長(zhǎng)度 (MDL) 原則 : ? 當(dāng)樹(shù)的 Coding最小的時(shí)候最佳。即可以任取其中一種狀態(tài)編碼為 1或者 0 對(duì)于對(duì)稱(chēng)的二員變量，采用 簡(jiǎn)單匹配系數(shù) 來(lái)評(píng)價(jià)兩個(gè)對(duì)象之間的相異度 dcba cb jid ??? ??),(2020年 10月 5日星期一 Data Mining: Concepts and Techniques 53 二元變量 ? 非對(duì)稱(chēng)的 如果變量的兩個(gè)狀態(tài)不是同樣重要的，則稱(chēng)該變量是不對(duì)稱(chēng)的