【正文】 簡(jiǎn)化分類工作 54 ID3的不足（ 2/2） ?無法處理未知值的樣本 ? 對(duì)于個(gè)別樣本缺失了某項(xiàng)描述屬性的情況，無法處理 ?無法處理連續(xù)值的樣本 ? 對(duì)于描述屬性是連續(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)。數(shù)據(jù)分類 決策樹 目錄 ?基本概念 ?決策樹 ID3算法 ?決策樹 2 學(xué)習(xí)目標(biāo) 3 4 定義 ?數(shù)據(jù)分類 ? 是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過程 ? 即給定一組輸入的屬性向量及其對(duì)應(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)號(hà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ù)對(duì)應(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)號(hào)表示數(shù)據(jù)樣本的具體取值個(gè)描述屬性分別對(duì)應(yīng)表示維特征向量用其中數(shù)據(jù)樣本數(shù)據(jù)集分類的過程 9 獲取數(shù)據(jù) 預(yù)處理 分類決策 分類器設(shè)計(jì) 獲取數(shù)據(jù) ?數(shù)值型數(shù)據(jù) ? 病例中的各種化驗(yàn)數(shù)據(jù) ? 空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù) ?描述性數(shù)據(jù) ? 人事部門檔案資料 ?圖片型數(shù)據(jù) ? 指紋、掌紋 ? 自然場(chǎng)景圖片 ?很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列，即形成特征向量（ 特征提取 ） 10 預(yù)處理 ?為了提高分類的準(zhǔn)確性和有效性，需要對(duì)分類所用的數(shù)據(jù)進(jìn)行預(yù)處理 ? 去除噪聲數(shù)據(jù) ? 對(duì)空缺值進(jìn)行處理 ? 數(shù)據(jù)降維（ 特征選擇 ） （ PCA、 LDA） 主成分分析 （ Principal Component Analysis ， PCA ） 線性鑒別分析 (Linear Discriminant Analysis, LDA)，有時(shí)也稱 Fisher線性判別 (Fisher Linear Discriminant ,FLD)， 這種算法是Ronald Fisher 于 1936年發(fā)明的，是模式識(shí)別的經(jīng)典算法。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，計(jì)算其信息增益比，從中選擇信息增益比最大的分割點(diǎn)來劃分?jǐn)?shù)據(jù)集 59 變化三：處理連續(xù)值的訓(xùn)練樣本（ 2/10） ?示例 ? 求利用 A上的 最佳分割點(diǎn) ?解： ? 第 0步，將 A的取值升序排列 {65,70,70,70,75,78,80,80,80,85,90,90,95,96} ? 第 1步，計(jì)算 vi=65時(shí)的信息增益比 60 A C 85 c2 90 c2 78 c1 96 c1 80 c1 70 c2 65 c1 95 c2 70 c1 80 c1 70 c1 90 c1 75 c1 80 c2 ))145(log145)149(log149())((log)(),(2221221?????? ??jjjcPcPnnI變化三：處理連續(xù)值的訓(xùn)練樣本（ 3/10） ?解： ? 第 1步，計(jì)算 vi=65時(shí)的信息增益比 61 A C 85 c2 90 c2 78 c1 96 c1