第五章　資料分類法

第五章 資料分類法 簡介 以決策樹為基礎之分類法 非決策樹為基礎之分類法

何謂分類 根據已知資料及其分類屬性值，建立資料的分類模型，接著利用此分類模型預測新資料的類別 範例：顧客是否會購買筆記型電腦的分類模型 婚姻 年齡 收入 否 是 單身 已婚 < 30 >= 30 低 中 高

分類法的特性與分類演算法 分類法特性 常用的分類演算法 屬於機器學習(machine learning) 一種監督式的學習法(supervised learning) 常用的分類演算法 以決策樹為基礎的分類法 包括ID3, PRISM, 以及Gini索引 非決策樹為基礎的分類法 貝氏分類法、記憶基礎推論法、類神經分類法

分類的目的與應用 分類目的 分類應用 分析影響資料歸類的因素 預測資料所屬的類別 (class label) 信用額度核准(credit approval) 例如：根據預測的信用等級決定核卡額度 目標行銷(target marketing) 例如：找出會購買筆記型電腦的顧客屬性 醫療診斷(medical diagnosis) 例如：依病人的症狀判斷是否罹患SARS ．．．

分類所需的資料前置處理 資料一般化 特徵屬性選取(feature selection) 注意 將連續性資料離散化，資料的數值分布精簡化 避免分類的品質不佳 特徵屬性選取(feature selection) 找出具有關鍵影響的屬性，將無關屬性去除 提高分類的精準度 注意 每筆建立分類模型的資料樣本，一定要有已知的分類標記(class label) ，包含這個已知分類標記的屬性稱之為標記屬性 是否購買筆記型電腦標記屬性

分類的程序 建立模型 評估模型 使用模型 利用現有資料找出分類模型 模型的表示方式有： 分類規則(classification rules) 決策樹(decision trees) 數學公式(mathematical formulas) 評估模型 將資料分成訓練樣本(training samples) 及測試樣本(testing samples) 第一階段利用訓練樣本來建立模型 第二階段測試樣本評估準確性 使用模型 找出資料分類的原因 預測新進資料類型

分類程序的範例 (1) 步驟1：建立模型

分類程序的範例 (2) 步驟2：評估模型

分類程序的範例 (3) 步驟3：使用模型 假設有一位新會員陳建成前來註冊，其基本資料為35歲，單身，低收入 依分類模型所預測的結果為 “是”，也就是此會員有可能會購買筆記型電腦 該線上購物商店可對此會員進行一連串筆記型電腦的廣告行銷活動，例如寄送電子報，以促使顧客下單購買筆記型電腦

分類法的準確性 訓練測試法(training-and-testing) 交互驗證法 (cross-validation) 資料樣本分為訓練和測試資料集，訓練資料集建立分類模型，利用測試資料集測試準確性 適合用在樣本空間非常大的情況 交互驗證法 (cross-validation) 資料樣本分成k個子樣本，輪流將k-1個子樣本當作訓練樣本，剩下一個子樣本當作測試樣本，重複做k次建立模型的工作之後，找出準確度最高的分類模型，也稱作k疊交互驗證法 (k-fold cross validation) 適合用在樣本空間不多的情況 自助法 (bootstrap method) 只留一筆資料當做測試樣本，其他全部拿來當訓練樣本，這是交互驗證法的特例 適合用在樣本空間非常小的情況

分類演算法的評估 (1) 準確度 速度 品質 可詮釋性 (interpretability) 建立分類模型的速度 使用分類模型預測的速度 藉由事後修剪 (postpruning) 降低分類模型複雜度 可詮釋性 (interpretability) 能不能從建立出來的分類模型去歸納、解釋 分類的原因

分類演算法的評估 (2) 其他的評估觀點 健全性 (robustness) 考量分類法對於雜訊以及遺缺值 (missing value) 的處理能力 擴展性 (scalability)，考量分類法在資料樣本規模擴大時是否仍能在可容忍的時間內求得探勘的結果

第五章 資料分類法 簡介 以決策樹為基礎之分類法 非決策樹為基礎之分類法

何謂決策樹 決策樹(Decision tree ) 類似流程的樹狀結構。 樹的中間節點 (non-leaf nodes) 代表測試的條件 樹的分支 (branches) 代表條件測試的結果 樹的葉節點 (leaf nodes) 代表分類後所得到的分 類標記，也就是表示分類的結果

決策樹的產生程序與用途 決策樹的產生程序 決策樹的用途：分類未知的樣本 步驟1:建立樹狀結構 步驟2:修剪樹狀結構 開始時，所有的訓練樣本都在根節點 依據選取的屬性，重複地將樣本分隔開來 步驟2:修剪樹狀結構 辨識並且移除導致雜訊或特例的分支 決策樹的用途：分類未知的樣本 靠著決策樹測試樣本的屬性值

決策樹推論演算法 (1) 基本演算法(貪婪演算法，greedy algorithm) 運作方式 樹結構是以由上而下，遞迴(recursive)各個擊破 (divide-and-conquer)方式建立 無法處理連續性的數值，數值屬性必須先轉換 運作方式 一開始，所有的訓練樣本都在根節點。 屬性都是類別型態（若是連續型數值，事先做離散化） 依據選取的屬性，反複地將樣本分隔開來。 測試各屬性是不是以嘗試性或統計性測量 （例如資訊獲利information gain）為基礎，而挑選出來的

決策樹推論演算法 (2) 停止分支的條件 類別時 樣本數較多的類別來代表此葉節點 當某分支子集合內的所有樣本都屬於同一個 可能所有的屬性都用完了 ，用多數投票法以 樣本數較多的類別來代表此葉節點 選取屬性之後產生某分支完全沒有測試樣本 的情況

屬性選取量測法 資訊獲利(Information gain) ID3/C4.5/PRISM 假設所有的屬性都是類別型態(categorical) 可修改用在連續型數值的屬性 Gini索引(Gini index , IBM IntelligentMiner) 假設所有的屬性都是連續型數值型態 假設每個屬性都存在數個可能的切割值 適用於連續性的數值型態屬性 可能需要其他工具(例如分群)，來得到可能的分群值 可修改用在類別型態的屬性

由決策樹採掘分類規則 從根節點到葉節點的每一條路徑，便代表一條分類規則 範例(圖5-1的決策樹為例 ) 從根節點到最左邊的葉節點，所得之分類規則為 IF 婚姻狀態＝單身 AND 年齡＜30歲 THEN 購買筆記型電腦＝否 完整規則 IF 婚姻狀態=單身 AND 年齡<30歲 THEN 購買筆記型電腦=否 IF 婚姻狀態=單身 AND 年齡>=30歲 THEN 購買筆記型電腦=是 IF 婚姻狀態=已婚 AND 收入=低 THEN 購買筆記型電腦=否 IF 婚姻狀態=已婚 AND 收入=中 THEN 購買筆記型電腦=否 IF 婚姻狀態=已婚 AND 收入=高 THEN 購買筆記型電腦=是

分類結果過度遷就 過度遷就 (over-fitting) 問題 有時會出現決策樹只對某一訓練資料集有效， 更換另一組訓練資料集，預測結果產生錯誤 雜訊或特例所造成的，分支太多必須適當修剪 預先修剪(prepruning) ：分支過程中進行品質量測 事後修剪：先讓決策樹自由發展，再將多餘分支修剪

應用分類法的資料樣本範例 表5-1 年齡 婚姻 收入 購買筆記型電腦 24 單身 80k 否 28 45k 35 25k 是 32 已婚 40 20k 42 22k 38 35k 29 60k 22 18k 33 38k 25 55k 50 42k 36k 45 28k 37 44k 18 表5-1

經前置處理之分類法資料樣本範例 年齡 婚姻 收入 購買筆記型電腦 <30 單身 高 否 中 >=30 低 是 已婚 表5-2

決策樹演算法 - ID3 昆蘭 (Quinlan) 1979年所提出的決策樹演算法 使用雪南 (Shannon) 於 1949年所提出的 資訊理論作為選擇測試屬性的依據

資訊理論 (information theory) 假設一個事件有n種結果，發生的機率分別為P(v1), …, P(vｎ)，這些機率都是已知的，則定義這個事件發生後所得到的資訊量為 ： 各種結果發生機率愈平均，所求資訊量也愈大 資訊量可以當作亂度 (Entropy) 的指標，資訊量愈大，表示亂度愈大 解決屬性選擇的問題

資訊獲利 (1) 假設分類結果為P (正例，positive instance)和N(反例，negative instance ) X代表屬性測試前的樣本集合 X1,…, Xv代表屬性測試後的樣本子集合 p代表Ｘ中正例的個數 n代表反例的個數 pi代表Ｘi中正例的個數 ni代表Ｘi中反例的個數

資訊獲利 (2) 根據屬性A的值將X分為X1,…, Xv所得到的資訊獲利為： 其中 ，當p, n皆不為0 ，當p或n任一為0

利用資訊獲利做屬性選取 資訊獲利即 “測試前的資訊量” 減 “測試後的資訊量” 分類的目的 將訓練樣本分成亂度最小的子集合 也就是所有樣本都屬於同一分類標記的子集合 ID3中以測試後資訊量最小的屬性為優先選取，也就是選擇資訊獲利最大的屬性。

利用資訊獲利做屬性選取之範例(1) 假設：P會購買筆記型電腦；N不會購買筆記型電腦 以表5-2為例，16筆顧客資料中，曾購買NB有4筆，未曾買NB有12筆 I (p, n) = I (4, 12) =0.8113 依照年齡將16位顧客分成兩群組 ： 小於30歲：曾買NB有1筆，未買NB有5筆 大於或等於30歲：曾買NB有3筆，未買NB有7筆

利用資訊獲利做屬性選取之範例(2) 同理 三個屬性的資訊獲利都計算出來之後，發現婚姻屬性的資訊獲利最大，因此選擇婚姻作為第一個分類的依據。 Gain (婚姻) = I (4,12) – (I (3,4) +I (1,8)) =0.0972 Gain (收入) = I (4,12) – (I (1,5) +I (2,5) +I (1,2) ) =0.0177 三個屬性的資訊獲利都計算出來之後，發現婚姻屬性的資訊獲利最大，因此選擇婚姻作為第一個分類的依據。 接下來根據婚姻的屬性值將資料樣本分成單身以及已婚兩個子集合分別考慮。用同樣的方法來分別決定左右分支下一個要選取的屬性。

決策樹演算法 - PRISM (1987) 以屬性值配對做為分類的依據 定義A=x的資訊獲利公式 非如ID3般單純以屬性做為分類的依據 決策樹中間節點代表一種屬性與值的配對 例如：婚姻＝單身，性別＝男，年齡<30等 定義A=x的資訊獲利公式 ，當p (A=x｜P)  0 　　　　　 PRISM_Gain(A = x) = 0，當p (A=x｜P) = 0 適用於屬性較少的分類問題

決策樹演算法 – PRISM範例 以表5-2為例，屬性值配對共有七種：年齡小於30歲、年齡大於或等於30歲、婚姻狀態為單身、婚姻狀態為已婚、收入為低、收入為中、收入為高。 分別計算此七種屬性值配對的資訊獲利得到： = -2.5850 = -1.7370 = -1.2224 = -3.1699 = -1.5850 資訊獲利最大！

pj 為屬於類別j的樣本在D 中出現的相對頻率 決策樹演算法 – Gini 索引法 (1) IBM Intelligent Miner使用的分類法 針對數值型態的屬性來做分類 假設一包含N個樣本的集合D，其中某數值屬性的值域為Ｔ Gini索引值: 若樣本集合D中包含 n 類樣本，則Gini索引法將樣本集合D的Gini索引值定義為 pj 為屬於類別j的樣本在D 中出現的相對頻率

Gini 索引法 (2) 在T 內找到一個分割點 t，將樣本分成小於 t 以及大於等於 t 兩個子集合，令其為D1及D2，分別包含N1及N2個樣本 集合Ｄ依分支點 t 切割成D1及D2後之Gini索引值定義為 樣本的類別分佈愈平均，Gini索引值愈大；分佈愈不平均，Gini索引值愈小 決定屬性值的分割點時，應選取可使分割後的Gini索引值最小的數值

Gini 索引法範例 (1) 假設第一個選取的屬性為年齡 考慮分割點為年齡＝30 則年齡<30的子集合當中有1個正例、5個反例，故 　p1 =1/16、 p2=5/16，Gini索引值為 年齡 30的子集合當中有3個正例、7個反例，故 　p1 =3/16、p2=7/16，此子集合之Gini索引值為 　　　　　　　　　　　　= 1 (3/16)2 (7/16)2=0.773

Gini 索引法範例 (2) 考慮分割點為年齡＝40 = 1 (4/16)2 (8/16)2 = 0.6875 則年齡<40的子集合當中有4個正例、8個反例，故 　p1 =4/16、 p2=8/16，Gini索引值為 = 1 (4/16)2 (8/16)2 = 0.6875 年齡 40的子集合當中有0個正例、4個反例，故 　p1 =0/16、p2=4/16，此子集合之Gini索引值為 　　　　　　　　　　　　= 1 (0/16)2 (4/16)2 = 0.9375 由於Gini’(40)<Gini’(30)，因此將分割點設定在”年齡 = 40”會比設定在”年齡 = 30”好

第五章 資料分類法 簡介 以決策樹為基礎之分類法 非決策樹為基礎之分類法

貝氏分類法- 簡介 或然率學習法 (Probabilistic learning) 漸增性 (incremental) 一種以機率、統計學為基礎的分類 漸增性 (incremental) 逐步將資料加入 適合資料會不斷成長的應用 利用事件發生機率來推測未知資料類別 不易解釋分類原因的缺點 適合用在預測未知樣本的類別，而不適合用來找出資料分類的原因

貝氏定理 (Bayesian Theorem) (1) 公式： X代表某個未知案例，Ｃ代表某一類別 公式的意義： X案例屬於Ｃ類別的機率= (Ｃ類別中出現X案例的機率) × (Ｃ類別出現的機率) / (X案例出現的機率)

貝氏定理 (2) 舉例：欲計算某顧客會購買筆記型電腦的機率 X案例即是這位顧客 Ｃ類別即是會購買筆記型電腦的顧客類別 Ｘ會購買筆記型電腦的機率 ＝ (購買筆記型電腦者中出現Ｘ的機率) × (購買筆記型電腦者的機率) / (Ｘ出現的機率) 有實行上的困難，因為購買筆記型電腦者中出現Ｘ的機率並無法從已知樣本的資料中計算而得

貝氏分類法 引進條件獨立的假設 : 貝氏分類法 P (X=< x1,…,xk>|C)  P(x1 |C)P(xk |C) x1,…,xk為案例 X 的 k 個屬性值 則P(C|X) = P(x1|C)P(xk|C)P(C) / P(X) ………….(5.2) 貝氏分類法 利用公式 (5-2) 計算出未知案例屬於各個類別的機率 取機率值最大的類別作為該案例的類別預測 亦即取使P(x1|C)P(xk|C)P(C) 值極大化的類別Ｃ即是案例X的預測類別（因P(X) 均相同）

貝氏分類範例 (1) 問題：某顧客年齡大於三十歲、已婚、中等收入，請問此顧客是否會買筆記型電腦? 表5-3 所有樣本 P N 總數 4 12 < 30 1 5 >= 30 3 7 婚姻 單身 已婚 8 收入 低 中 2 高 表5-3

貝氏分類範例 (2) P(P|X) P(X) = P(“年齡30”|P)P(“婚姻＝已婚”|P)P(“收入＝中”|Ｐ) P(P) P(N|X) P(X) =P(“年齡30”|N)×P(“婚姻＝已婚”|N)×P(“收入＝中”|N) P(N) 因P(N|X) > P(P|X)，故測該未知樣本的類別為N：不會購買筆記型電腦

記憶基礎推論法-簡介 (Memory-Based Reasoning，MBR) Bradley在1994根據 1982 年Roger Schank的動態記憶法所提出 從過去經驗知識中擷取相似案例解決問題 處理各種資料型態 成功關鍵 選取合適的訓練資料集(前置處理 ) 正確的資料精簡處理(前置處理 ) 決定適當的距離函數、組合函數以及鄰近樣本個數(關鍵 )

記憶基礎推論步驟 (1) 步驟一：選擇適當的訓練資料集 步驟二：設定距離函數，決定每個屬性距離 將原始資料分類，每個類別中選出具代表性的記錄來代表整個類別 步驟二：設定距離函數，決定每個屬性距離 即定義兩筆基本資料間之距離 明確定義：兩點之間的距離一定可以找出，即 d(A,B)≧ 0。 符合同一律 (identity)：從一點到它本身距離一定是0，即 d(A,A)=0。 符合交換率：距離並沒有方向性，所以 A 到 B 的距離就是 B 到 A 的距離，即 d(A,B)=d(B,A)。 符合三角不等式：找到A和B中間的一點C，則d(A,B)≦d(A,C)+d(C,B)。

記憶基礎推論步驟 (2) 步驟二(續) 數值型態常用的距離函數 類別型態 絕對差：|A-B| 平方差：(A-B)*(A-B) 先轉換成數值型態，再依數值型態處理 例如：學歷這個屬性值有小學、國中、高中、大學、研究所，可將小學用數值1來表示、國中用2表示…依此類推，研究所用5表示。

記憶基礎推論步驟 (3) 步驟二(續) 總和： 標準化總和 ： 歐基里德距離： 計算屬性距離後，接著要組合成一個數值來代表兩個資料紀錄之間距離 總和： 標準化總和 ： 歐基里德距離：

記憶基礎推論步驟 (4) 步驟三：設定欲選取的鄰近資料數量。 步驟四：設定組合函數，決定未知樣本類別 選擇距離較近的數個資料樣本，以多數決方式 決定未知樣本所屬類別。 避免發生平手情況，有 (k＋1) 個類別時， 可選取 k 個鄰近點。 步驟四：設定組合函數，決定未知樣本類別 民主選舉法： 選出現頻率最高類別做為投票結果 加權選舉法 距離愈近權重愈大，距離愈遠則權重愈小

記憶基礎推論範例 (1) 步驟一：選擇適當的訓練資料集 表5-1當中選取相同數量的正例和反例做為訓練資料集，假設各選取四筆如表5-4 年齡 婚姻 收入 購買筆記型電腦 24 單身 80k 否 35 25k 是 32 已婚 40k 42 22k 25 55k 36k 37 44k 18 表5-4

記憶基礎推論範例 (2) 步驟二:決定每一個屬性的距離 將單身轉為0，已婚轉為1，以標準差來計算各屬性的距離 以歐基里德距離公式將各屬性的距離組合得表5-5

記憶基礎推論範例 (3) 步驟三：設定欲選取的鄰近資料數量。 步驟四：設定組合函數，決定未知樣本類別 假設選取3個鄰近點，則選出編號3, 4, 5等三筆記錄。 步驟四：設定組合函數，決定未知樣本類別 假設依民主選舉法決定樣本類別。由於編號 3, 4, 5這三筆鄰近記錄中有兩筆為反例，只有一筆為正例，因此決定該未知樣本為一反例，也就是這位顧客可能不會購買筆記型電腦

記憶基礎推論法的優點 不需訓練 可處理任何資料型態 簡單易用 結論容易推測 節省建立分類模型的時間。 任何型態均可轉換到數值空間進行距離計算。 簡單易用 無需繁複的演算法。 結論容易推測 以選舉法決定類別，淺顯易懂。

記憶基礎推論法的缺點 需記錄大量訓練資料集： 耗費較多時間： 高度依賴距離函數和組合函數： 無法解釋分類的原因： 佔用大量的硬體資源。 每當有新資料需預測時，必須與訓練資料集所有欄位比對，需要大量的計算，必須建立索引來加速工作。 高度依賴距離函數和組合函數： 尋找距離和組合函數難度不高，但要確定最佳解就比較困難。 無法解釋分類的原因： 此法只能應用在預測上

類神經網路演算法 模擬大腦神經細胞的運作方式 透過不斷地自我調整 具有部分容錯的功能 由一些高度連結的處理單元（稱做節點或是神經元，neuron )組成一動態的運算系統 透過不斷地自我調整 使得輸入的資訊在經過神經元的運算之後能得到預設的輸出結果 具有部分容錯的功能

類神經網路的運作 訓練階段： 測試階段： 內部結構包含三層(圖5-6) 調整網路內部各節點連結的權重值，使得輸入值經過網路計算之後能得到目標的輸出值。 測試階段： 驗證網路的準確度或是利用訓練完成的網路進行預測。 內部結構包含三層(圖5-6) 輸入層：接收外來的訊號並將此訊號傳入類神經網路中， 以便進行處理。 隱藏層：對輸入層接收的訊號進行處理，但使用者看不 見整個處理過程。 輸出層：將隱藏層處理後的訊號傳送到外界

類神經網路之三層式架構圖 X1 X2 : Xn Y1 Y2 Yn 輸入層 隱藏層 輸出層

類神經網路訓練 訓練的最終目的 步驟 獲得一組權重值，使得幾乎每筆訓練資料都能被正確分類。 預設或是以亂數值初始權重。 一筆一筆的將輸入每組訓練資料。 進行回授 (feedback) 調整權重值，使得輸出與目標值吻合 反覆進行同樣步驟，直到每筆訓練樣本均可得到目標輸出值為止

輸入向量及輸出值範例 表5-2為例 範例 表5-6 0代表 “＜30”，1代表 “≧30”； 婚姻0代表 “單身”，1代表 “已婚” 收入用 -1代表 “低”，0代表 “中”，1代表 “高” 輸出值0代表 “否”（未曾購買NB） 輸出值1代表 “是”（曾購買NB） 範例 則第一筆訓練樣本的屬性值 (“＜30”, “單身”, “高”) 將轉換成(0,0,1) 向量輸入，目標輸出值是0 表5-6

權重值調整 以內積運算做說明 設輸入向量為Xi= (xi1, xi2, .., xik)，輸出為yi，i=1, ..,n 使得 類神經網路訓練將找出權重向量Ｗ＝ (w1, w2, .., wk) 使得 為了使權重值調整更容易進行，假設輸出值yi為非0即1的二元值，則可令Xi 與 W的內積小於等於0時輸出0，大於0時輸出1。

權重向量調整範例 設初始權重向量W0= (0, 0, 0)，將表5-6的樣本逐一輸入神經網路進行訓練 每次輸入可視為一個調整權重向量的循環

權重向量調整注意事項 停止訓練時機 當訓練樣本數量很多時，訓練將會花相當高的時間成本 當前後兩次循環所得之權重向量變化十分微小時，代表權重向量已收斂，此時即可停止訓練 當訓練樣本數量很多時，訓練將會花相當高的時間成本 可改以隨機抽樣的方式進行訓練

總結 分類法可說是資料探勘當中最廣為使用的技術之一 分類法在統計學、人工智慧、機器學習、以及類神經網路等方面都有許多相關研究 分類法仍需解決的重要問題 擴展性 (scalability) 不同資料型態的分類問題 例如：如何針對非格式化的資料，像是文章、新聞、多媒體資料、音訊、圖片等等，進行分類將是一個非常值得延伸探討的問題