Course 4 分類與預測 Classification and Prediction

 分類 VS. 預測 分類︰ 預測︰ 典型應用 預測分類標號（或離散值） 根據訓練資料集和類標號屬性，構建模型來分類現有資料，並用來分類新資料 預測︰ 建立連續函數值模型，比如預測空缺值 典型應用 信譽證實 目標市場 醫療診斷 性能預測

分類(Classification) 分類的意義 分類模型 資料庫 預測 瞭解類別屬性與 特徵

 資料分類: 一個兩步過程 第一步，建立一個模型，描述預定資料類集和概念集 假定每個元組屬於一個預定義的類，由一個類標號屬性確定 基本概念 訓練資料集︰由為建立模型而被分析的資料元組形成 訓練樣本︰訓練資料集中的單個樣本（元組） 學習模型可以用分類規則、決策樹或數學公式的形式提供

第二步，使用模型，對將來的或未知的對象進行分類 首先評估模型的預測準確率 對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較 模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比 測試集要獨立於訓練樣本集，否則會出現“過分適應資料”的情況

第一步: 建立模型 分類演算法 訓練資料集 分類規則 IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’

第二步: 用模型進行分類 分類規則 測試集 未知資料 (Jeff, Professor, 4) Tenured?

2.模型評估(Model Evaluation) 3.使用模型(Use Model) 1.模型建立(Model Building) 2.模型評估(Model Evaluation) 3.使用模型(Use Model) 性別 年齡 婚姻 否 是 Female Male <35 ≧35 未婚 已婚 分類規則 IF 性別=Female AND 年齡<35 THEN 購買RV房車=否 IF 性別=Female AND 年齡≧35 THEN 購買RV房車=是 IF 性別=Male AND 婚姻=未婚 THEN 購買RV房車=否 IF 性別=Male AND 婚姻=已婚 THEN 購買RV房車=是 資料庫 訓練樣本(training samples) 建立模型 測試樣本(testing samples) 評估模型

X Example 2. 模型評估 1.建立模型 婚姻 年齡 否 是 未婚 已婚 低 高 小康 資料 訓練樣本 錯誤率為 66.67% 家庭 所得 否 是 未婚 已婚 <35 ≧35 低 高 小康 資料 訓練樣本 測試樣本 X 錯誤率為 66.67% 3.使用模型 修改模型

分類的目的 1.尋找影響某一重要變項的因素。 2.了解某一族群的特徵。 3.建立分類規則。 例如: 行銷策略(市場區隔) 銀行(核卡額度) 醫療診斷(肝癌,SARS)

 有指導的學習 VS. 無指導的學習 有指導的學習（用於分類） 無指導的學習（用於聚類） 模型的學習在被告知每個訓練樣本屬於哪個類別的“指導”下進行 新資料使用訓練資料集中得到的規則進行分類 無指導的學習（用於聚類） 每個訓練樣本的類別編號是未知的，要學習的類別集合或數量也可能是事先未知的 透過一系列的度量、觀察來建立資料中的類別編號或進行聚類

1.監督式(supervised learning)的機器學習法------ 決策樹(Decision Tree) 資料庫 分類標記 性別 Female Male 年齡 婚姻 <35 ≧35 未婚 已婚 否 是

2.非監督式(unsupervised learning)的機器學習法----- 集群分析法(Cluster Analysis)

 準備分類和預測的資料 透過對資料進行預處理，可以提升分類和預測過程的準確性、有效性和可伸縮性 資料清理 相關性分析 資料變換 消除或減少噪音，處理空缺值，從而減少學習時的混亂 相關性分析 資料中的有些屬性可能與當前任務不相關；也有些屬性可能是冗餘的；刪除這些屬性可以加快學習步驟，使學習結果更精確 資料變換 可以將資料概化到較高層概念，或將資料進行規範化

 比較分類方法 使用下列標準比較分類和預測方法 預測的準確率︰模型正確預測新資料的類編號的能力 速度︰產生和使用模型的計算花銷 訓練測試法(training-and-testing) 交互驗證法(cross-validation) 速度︰產生和使用模型的計算花銷 健壯性︰給定噪音資料或有空缺值的資料，模型正確預測的能力 可伸縮性︰對大量資料，有效的構建模型的能力 可解釋性︰學習模型提供的理解和洞察的層次

 用決策樹歸納分類 什麼是決策樹？ 決策樹的生成由兩個階段組成 決策樹的使用︰對未知樣本進行分類 類似於流程圖的樹架構 每個內部節點表示在一個屬性測試 每個分枝代表一個測試輸出 每個樹葉節點代表類別或類別分佈 決策樹的生成由兩個階段組成 決策樹構建 開始時，所有的訓練樣本都在根節點 遞迴的透過選定的屬性，來劃分樣本 （必須是離散值） 樹剪枝 許多分枝反映的是訓練資料中的噪音和孤立點，樹剪枝試圖檢測和剪去這種分枝 決策樹的使用︰對未知樣本進行分類 透過將樣本的屬性值與決策樹相比較

決策樹(Decision Tree)之介紹 根部節點(root node) 中間節點(non-leaf node) (代表測試的屬性) 分支(branches) (代表測試的結果) 葉節點(leaf node) (代表分類後所獲得的分類標記)

age income student credit_rating buys_computer <=30 high no fair excellent 31…40 yes >40 medium low

概念“buys_computer”的決策樹 age? overcast student? credit rating? no yes fair excellent <=30 >40 30..40

基本的決策樹學習演算法 基本的演算法概念: 採用自頂端向下的貪婪搜索遍歷可能的決策樹空間 ID3是這種演算法的代表 將原始資料分成兩組，一部分為訓練資料，一部分為測試資料 使用訓練資料來建立決策樹，而在每一個內部節點，則依據資訊理論(Information Theory)來評估選擇哪個屬性繼續做分支的依據，又稱節點分割 (Splitting Node) 使用測試資料來進行決策樹修剪 將以上1~3步驟不斷遞迴進行，直到所有的新內部節點都是樹葉節點為止，且: 該群資料中，每一筆資料都已經歸類在同一類別下 該群資料中，已經沒有辦法再找到新的屬性來進行節點分割 該群資料中，已經沒有任何尚未處理的資料 採用自頂端向下的貪婪搜索遍歷可能的決策樹空間 ID3是這種演算法的代表

決策樹歸納策略 樹以代表訓練樣本的單個節點開始 如果樣本都在同一個類別，則該節點成為樹葉，並用該類別標記 否則，算法使用基於熵的度量: 資訊獲利作為指導訊息，選擇能夠最好的將樣本分類的屬性；該屬性成為節點的“測試”或“判定”屬性。（使用分類屬性） 對測試屬性每個已知的值，創建一個分支，並以此劃分樣本

算法使用同樣的過程，遞迴的形成每個劃分上的樣本決策樹。一旦一個屬性出現下一個節點上，就不在該節點的任何子節點上出現 遞迴劃分步驟停止的條件 給定節點的所有樣本屬於同一類 沒有剩餘屬性可以用來進一步劃分樣本: 使用多數表決 沒有剩餘的樣本

ID3演算法的核心問題是選取樹中的每個節點所要測試的屬性。 我們希望選擇的是最有助於分類Instance的屬性，那麼好的評定標準是什麼？ 最佳分類屬性 ID3演算法的核心問題是選取樹中的每個節點所要測試的屬性。 我們希望選擇的是最有助於分類Instance的屬性，那麼好的評定標準是什麼？ 資訊獲利 (Information Gain) ID3在建構決策樹過程中，以資訊獲利為準則，並選擇最大的資訊獲利值作為分類屬性。

用熵 (Entropy)來衡量範例的一致性 熵，可當作資訊量的凌亂程度 (不確定性) 指標，當熵值愈大，則代表資訊的凌亂程度愈高。(又可稱為期望資訊量) 【說明範例】丟銅板 若銅板是公平的，則丟出正面與反面的機率是一樣的 若銅板是動過手腳的，則丟出正面與反面的機率不會是樣的 給定包含關於此範例的範例集S，那麼S相對這個布林分類的熵為 Entropy(S)=-p+log2p+ - p-log2p- 若丟了14次銅板，出現了9個正面與5個反面(記為[9+, 5-])，則對於這個範例的熵為: Entropy([9+, 5-])= -(9/14)log2 (9/14) – (5/14) log2 (5/14) = 0.94 若銅板丟出正面與反面的數量是一樣，則熵為1 若銅板是動過手腳的，不論怎麼丟都只會出現正面 (或反面)，則熵為0

更一般地，如果目標屬性具有c個不同的值，那麼S相對於c個狀態的分類的熵定義為 Entropy(S)= 其中pi 為每個狀態出現的機率

用資訊獲利 (Information Gain) 衡量期望的熵降低 【說明範例】天氣評估 假設有一套天氣評估系統S，它有一些評估屬性 (如: 風力、濕度、…)。 以風力 (Wind)為例，它在所有的訓練資料中所會出現的值為: weak, strong 若目前有14個範例資料，其中有9個正例與5個反例(記為[9+, 5-]) 這14個範例資料中，關於風力的資料: Wind = weak在所有範例中有6個正例與2個反例 [6+, 2-] Wind = strong在所有範例中有3個正例與3個反例 [3+, 3-] 我們想要得知風力這個屬性的資訊獲利為多少。

因此，一個評估屬性A相對於範例集合S的資訊獲利Gain(S, A)被定義為:

ID3演算法舉例 挑出具最大資訊獲利的屬性，因此以Outlook為根節點 (root) Sunny Overcast Rain Yes = 2 No = 3 Yes = 4 No = 0 Yes = 3 No = 2 Temp. Hot Mild Cool Yes = 2 No = 2 Yes = 4 Yes = 3 No = 1 Gain(S, Outlook) = 0.246 Gain(S, Temperature) = 0.029 Humidity High Normal Yes = 3 No = 4 Yes = 6 No = 1 Wind Weak Strong Yes = 6 No = 2 Yes = 3 No = 3 Gain(S, Humidity) = 0.151 Gain(S, Wind) = 0.048 挑出具最大資訊獲利的屬性，因此以Outlook為根節點 (root) 由於Outlook的三個評估值中，Overcast(多雲)的這個評估值得到4個正例 (Yes)，沒有任何反例，因此Outlook = Overcast可得到一個葉子節點 “Yes”。

Outlook Temp. Humidity Wind Sunny Overcast Rain Yes = 2 No = 3 Yes = 3 No = 2 Yes NO Yes Temp. Hot Mild Cool Yes = 0 No = 2 Yes = 1 No = 1 No = 0 Humidity High Normal Yes = 0 No = 3 Yes = 2 No = 0 Wind Weak Strong Yes = 1 No = 2 No = 1 Gain( SSunny , Temp.) = 0.57 Gain( SSunny , Humidity) = 0.97 Gain( SSunny , Wind) = 0.019

分類規則: If Outlook = Sunny and Humidity = High Then Play Tennis = No If Outlook = Sunny and Humidity = Normal Then Play Tennis = Yes If Outlook = Overcast Then Play Tennis = Yes If Outlook = Rain and Wind = Strong Then Play Tennis = No If Outlook = Rain and Wind = Weak Then Play Tennis = Yes

 防止分類中的過分適應 產生的決策樹會出現過分適應資料的問題 防止過分適應的兩種方法 決策樹學習可能遭遇模型過度配適（overfitting）的問題 過度配適是指模型過度訓練，導致模型記住的不是訓練集的一般性，反而是訓練集的局部特性。 由於資料中的噪音和孤立點，許多分枝回應的是訓練資料中的異常 對新樣本的判定很不精確 Data Mining的主要目的，是為了協助企業追求最高利潤而非追求最高準確度。 防止過分適應的兩種方法 先剪枝︰透過提前停止樹的構造──如果在一個節點劃分樣本將導致低於預定義臨界值的分裂（e.g. 使用資訊獲利度量） 選擇一個合適的臨界值往往很困難 後剪枝︰由“完全生長”的樹剪去分枝──對於樹中的每個非樹葉節點，計算該節點上的子樹被剪枝可能出現的期望錯誤率 使用一個獨立的測試集來評估每顆樹的準確率，就能得到具有最小期望錯誤率的決策樹

其他分類方法 k-最臨近分類 基於案例的推理 貝氏分類 神經網路學習 遺傳算法 結合生物進化思想的算法 模糊集方法

什麼是預測？ 預測是構造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。 預測和分類的異同 相同點 不同點 兩者都需要構建模型 都用模型來估計未知值 預測當中主要的估計方法是回歸分析 線性回歸和多元回歸 非線性回歸 不同點 分類法主要是用來預測類標號（分類屬性值） 預測法主要是用來估計連續值（量化屬性值）