【正文】 n(A4) 選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn) 49 A1公司職員 A3收入 A4信譽(yù)度 C買保險(xiǎn) 否 高 良 c2 否 高 優(yōu) c2 否 中 良 c2 是 低 良 c1 是 中 優(yōu) c1 第 5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集 年齡 41~50的子集 該子集中所有樣本的類別標(biāo)號都一樣，所以無需繼續(xù)劃分 可將它標(biāo)注為一個(gè)葉節(jié)點(diǎn)，而且葉節(jié)點(diǎn)的類標(biāo)號為 c1 50 A1公司職員 A3收入 A4信譽(yù)度 C買保險(xiǎn) 否 高 良 c1 是 低 優(yōu) c1 否 中 優(yōu) c1 是 高 良 c1 第 5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集 年齡 50的子集 在此子集內(nèi)繼續(xù)檢查 Gain(A1)、 Gain(A3)、 Gain(A4) 選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn) 51 A1公司職員 A3收入 A4信譽(yù)度 C買保險(xiǎn) 否 中 良 c1 是 低 良 c1 是 低 優(yōu) c2 是 中 良 c1 否 中 優(yōu) c2 ID3算法小結(jié) ?使用 ID3算法的基本思想是 ? 采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣本空間 ? 再對他們單獨(dú)進(jìn)行處理 ? 其中，選擇哪一個(gè)描述屬性作為新建節(jié)點(diǎn)，依據(jù)是考察該描述屬性的信息增益是否最大 52 53 ID3的不足（ 1/2） ?使用信息增益作為屬性選擇依據(jù) ? 帶有傾向性，傾向于選擇取值較多的屬性 ? 為什么？ ? 一種可能的解釋是：對于較難分類的集合，優(yōu)先將樣本分割到盡可能多的分支中將極大簡化分類工作 54 ID3的不足（ 2/2） ?無法處理未知值的樣本 ? 對于個(gè)別樣本缺失了某項(xiàng)描述屬性的情況，無法處理 ?無法處理連續(xù)值的樣本 ? 對于描述屬性是連續(xù)值的情況，無法處理 55 變化一：使用信息增益比 56 ??????qsssfffffjsjssssffsqfqfffftot alntot alnAspli tAspli tAGainArati oGainXAcXnXnaAXXXXqXAaaadfA122121)(log)()()()(_},{},{q),2,1(其中所得的信息增益比為：劃分則描述屬性的樣本數(shù)量中屬于類別表示子集中的樣本數(shù)量表示子集設(shè)上具有相同取值中的樣本在其中個(gè)子集劃分為可以將利用個(gè)不同的取值具有設(shè)描述屬性???變化二：處理未知值的訓(xùn)練樣本（ 1/2） ?思想 ? 將未知值用最常用的值來替代（較容易） ? 或，依據(jù)現(xiàn)有取值的概率分布來估計(jì)未知值（較真實(shí)） ?顯然：依據(jù)思想一，在已知樣本中年齡的三個(gè)區(qū)間分布是 ? =40， 4人 ? 41~50， 4人 ? 50， 5人 ? 則可以直接指定未知值為“ 50” 57 A2年齡 C買保險(xiǎn) =40 c2 =40 c2 41~50 c1 50 c1 50 c1 50 c2 41~50 c1 =40 c2 =40 c1 50 c1 ？ c1 41~50 c1 41~50 c1 50 c2 變化二：處理未知值的訓(xùn)練樣本（ 2/2） ?思想 ? 將未知值用最常用的值來替代（較容易） ? 或，依據(jù)現(xiàn)有取值的概率分布來估計(jì)未知值（較真實(shí)） ?顯然：依據(jù)思想二，在已知樣本中年齡的三個(gè)區(qū)間分布是 ? =40， 4人 ? 41~50， 4人 ? 50， 5人 ?考慮未知值樣本后，分布更新為 ? =40， 4+4/13人 ? 41~50， 4+4/13人 ? 50， 5+5/13人 58 A2年齡 C買保險(xiǎn) =40 c2 =40 c2 41~50 c1 50 c1 50 c1 50 c2 41~50 c1 =40 c2 =40 c1 50 c1 ？ c1 41~50 c1 41~50 c1 50 c2 變化三：處理連續(xù)值的訓(xùn)練樣本（ 1/10） ?思想 ? 將所有數(shù)據(jù)樣本按照連續(xù)型描述屬性 Ac的具體取值，由小到大進(jìn)行升序排列，得到的屬性值取值序列 {A1c,A2c,...,Atotalc} ? 在 {A1c,A2c,...,Atotalc}中生成 total1個(gè)分割點(diǎn)，第 i個(gè)分割點(diǎn)的取值設(shè)置為 vi=(Aic+A(i+1)c)/2或者 vi=Aic ? 該分割點(diǎn)將數(shù)據(jù)集劃分為兩個(gè)子集，即描述屬性 Ac的取值在區(qū)間[A1c,vi]的數(shù)據(jù)樣本和在區(qū)間 (vi,Atotalc]的數(shù)據(jù)樣本，顯然劃分共有total1種方式 ? 從 total1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。 ?是 N次交叉驗(yàn)證的一個(gè)特例。 12 D的 規(guī)模非常小時(shí) ?每次交叉驗(yàn)證時(shí)，只選擇一條測試數(shù)據(jù)，剩余的數(shù)據(jù)均作為訓(xùn)練集。數(shù)據(jù)分類 決策樹 目錄 ?基本概念 ?決策樹 ID3算法 ?決策樹 2 學(xué)習(xí)目標(biāo) 3 4 定義 ?數(shù)據(jù)分類 ? 是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過程 ? 即給定一組輸入的屬性向量及其對應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類 ? 分類問題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如何更精確、更有效地分類一直是人們追求的目標(biāo) ?數(shù)據(jù)分類的任務(wù) ? 通過學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù) f，把每個(gè)屬性集 x映射到一個(gè)預(yù)先定義的類標(biāo)號 y 5 分類的示例 ?兩類分類示例 ? 銀行業(yè)：區(qū)分高端信用卡和低端信用卡 ? 醫(yī)療診斷：區(qū)分正常細(xì)胞和癌細(xì)胞 ? 互聯(lián)網(wǎng)：區(qū)分正常郵件和垃圾郵件 ?多類分類示例 ? 油氣傳輸：區(qū)分行人走過、汽車碾過、鎬刨、電鉆等行為 ? 文字識(shí)別：區(qū)分不同的字符 （其中漢字識(shí)別是一個(gè)大類別問題） ? 社會(huì)網(wǎng)絡(luò)：區(qū)分中心用戶、活躍用戶、不活躍用戶、馬甲用戶等 6 示例數(shù)據(jù)集 ?數(shù)據(jù)集包含多個(gè)描述屬性和一個(gè)類別屬性 ?一般來說 ? 描述屬性：連續(xù)值或離散值 ? 類別屬性：只能是離散值 （目標(biāo)屬性連續(xù)對應(yīng)回歸問題） 7 Age Salary Class 30 high c1 25 high c2 21 low c2 43 high c1 18 low c2 33 low c1 ...... ...... ...... 分類問題的形式化描述 8 },{m,d,),(d),2,1(},2,1|),{(21212121miiididiiidiiiiiicccyxyAAAxxxxxxxtot alixtot aliyxX???????????個(gè)類別，則假設(shè)給定數(shù)據(jù)集包含的類標(biāo)號表示數(shù)據(jù)樣本的具體取值個(gè)描述屬性分別對應(yīng)表示維特征向量用其中數(shù)據(jù)樣本數(shù)據(jù)集分類的過程 9 獲取數(shù)據(jù) 預(yù)處理 分類決策 分類器設(shè)計(jì) 獲取數(shù)據(jù) ?數(shù)值型數(shù)據(jù) ? 病例中的各種化驗(yàn)數(shù)據(jù) ? 空氣質(zhì)量監(jiān)測數(shù)據(jù) ?描述性數(shù)據(jù) ? 人事部門檔案資料 ?圖片型數(shù)據(jù) ? 指紋、掌紋 ? 自然場景圖片 ?很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換