Data Mining: Concepts and Techniques 資料探勘: 概念與技術 — 第六章 — March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 判別與預測 判別 預測類別類形 (離散或類別值) 根據訓練資料及其判斷屬性類別值來判別資料, 並將其應用於判別新資料 預測 對連續值函數建立模型 例., 預測未知或遺失值 典型應用 信用核准 目標市場 醫學分析 詐騙檢測 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 判別—兩個步驟的程序 模型建立: 描述一組事先定義的類別 每個值組 (tuple) 均屬於某個類別，而類別由類別屬性 (class label attribute) 決定 構成訓練集合的值組集合稱為訓練值組集 模型用判別規則、決策樹或數學公式來表示 模型使用: 用於判別未來或未知個體 預估模型的正確性 使用已知類別測試資料來預估模型的正確性 正確率是指測試資料被正確分類的百分比 測試資料與訓練資料獨立, 否則會產生過適(over-fitting)的現象 如果測試正確率是可接受的，模型將用來判別未知的資料 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 步驟 (1): 模型建立 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 步驟 (2): 使用模型進行判別 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 監督與非監督學習 監督式學習 (判別) 監督:從訓練資料學習哪個值組屬於哪個類別 根據訓練資料判斷新資料類別 非監督式學習 (分群) 訓練資料的類別是無法事先知道或是未知 將資料依照相似值組進行群組 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 議題:資料準備 資料清除 用於移除雜訊與設定遺失值 相關分析 (屬性選擇) 移除多餘或不相關的屬性 資料轉換 一般或正規化資料 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 議題: 評估判別方法 正確率 判別正確率: 預測類別標籤 預測正確率: 猜測預測屬性值 速度 建立模型時間 (訓練時間) 使用模型時間(判別/預測時間) 穩固性:在雜訊與不存在值的資料中正確判別或預測的能力 可量度性:對於龐大資料有效的建立判別與預測模型 解釋力 對判別或預測所提供的了解程度 其他的研究包含發掘屬性與其相關判別的關係 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 決策樹歸納: 訓練資料集 沿用Quinlan’s ID3 (Playing Tennis)範例 March 1, 2017 Data Mining: Concepts and Techniques

輸出: “buys_computer” 決策樹 age? overcast student? credit rating? <=30 >40 no yes 31..40 fair excellent March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 決策樹歸納方法 基本方法 (貪婪式方法) 決策樹是用由上而下 (top-down) 遞迴式 (recursive) 的分割與克服 (divide-and-conquer) 的方式建立 一開始根節點包含所有的資料 屬性為類別資料 (如果為連續資料必須進行離散化) 根據類別值來選擇最好的屬性進行值組的區別 套用屬性選擇指標如資訊獲利 (information gain) 或吉尼係數 停止分割條件 所有值組屬於相同類別 沒有屬性在屬性列可繼續進行分割 –在這種例子要套用多數決 分割中不包含任何值組 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 屬性選擇指標:資訊獲利 (ID3/C4.5) 選擇屬性中擁有最高資訊獲利 pi為任一D中的值組被歸類為類別Ci的機率，它可由|Ci, D|/|D|得之 期望訊息 (熵) 用於判別D中值組: 在分割後，為了達到一致的判別我們仍需要下列的訊息: 分割屬性A的訊息獲利 I : the expected information needed to classify a given sample E (entropy) : expected information based on the partitioning into subsets by A March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 屬性選擇: 資訊獲利 Class P: buys_computer = “yes” Class N: buys_computer = “no” 代表 “age <=30” 在14樣本中佔了 5 個, 其中有 2 yes’es and 3 no’s. 因此 相同的, March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 用連續值來計算訊息獲利 當屬性A為連續值 對屬性A決定最佳的分割點 將屬性A的值進行遞增排序 一般來說兩個相鄰屬性值的中點 (midpoint) 會被設為可能分割點 (ai+ai+1)/2 為 ai 與 ai+1的中點 擁有最小期望訊息值的可能分割點會被設為屬性A的分割點 分割: D1 包含D中滿足 A ≤ 分割點值組, D2 包含D中滿足 A > 分割點值組 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 訊息獲利會傾向於選擇擁有許多不同類別的屬性 C4.5 (ID3延續)利用獲利比率克服問題 (資訊獲利正規化) GainRatio(A) = Gain(A)/SplitInfo(A) 例. gain_ratio(i收入) = 0.029/0.926 = 0.031 擁有最大獲利比例的屬性被設為分割屬性 March 1, 2017 Data Mining: Concepts and Techniques

吉尼係數 (CART, IBM IntelligentMiner) 資料集 D 包含n類別資料, 吉尼係數, gini(D) 定義為 pj為在D中的值組屬於類別j的機率 利用屬性A分割D為D1與D2。則根據此分割D的吉尼係數為 不純粹度的減少值為: 屬性擁有最大不純粹度的降低值，則選為分割屬性(對每個屬性的所有可能分割點進行測試) March 1, 2017 Data Mining: Concepts and Techniques

吉尼係數 (CART, IBM IntelligentMiner) 例. D 有9筆購買電腦(buy_computer)為yes，剩下5筆為no 假設收入屬性分割 D 中 10 筆資料到 D1: {低, 中} 剩下 4 筆到 D2 但是 gini{中,高} 為 0.30所以屬性收入的{中, 高}被選為分割條件因為它擁有最小的吉尼係數值 假設所有屬性為連續值 需要其他工具, 例., 分群, 取得可能分割值 修改後可套用至類別屬性 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 屬性選擇指標比較 三種常用指標 訊息獲利: 趨向於包含多個值的屬性 獲利比例: 會產生不平均的分割，也就是分割的一邊會非常小於另一邊 吉尼係數: 傾向於包含多個值的屬性 當類別個數很多時會有困難 傾向那些會導致平衡切割並且兩邊均為純粹的測試 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 過適與樹修剪 過適: 歸納樹會對訓練資料產生過適問題 許多分枝會導致異常, 這些是由於資料中的雜訊與離異值所引起 導致未知樣本的低正確率 兩種常用的方式 事前修剪:透過決策樹不再增長的方式來達到修剪的目的, 例佈在分割當指標低於某個界限值 很難選擇適當界限值 事後修剪:從全部的決策樹中移除子樹 要使用不同於訓練資料的資料來決定最佳修剪樹 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 決策樹的可量度性 SLIQ (EDBT’96 — Mehta et al.) 使用儲存在記憶體的屬性列 與類別列 SPRINT (VLDB’96 — J. Shafer et al.) 使用不同屬性列的資料結構 RainForest (VLDB’98 — Gehrke, Ramakrishnan & Ganti) 建立 AVC-set (屬性, 值, 類別標籤) BOAT (PODS’99 — Gehrke, Ganti, Ramakrishnan & Loh) 使用統計技巧自助法來建立許多小樣本 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 貝氏理論: 基礎 假設X為資料值組或稱為事證: 類別未知 假設 H 為X屬於某個類別C 在判別問題我們想要決定P(H|X)，而P(H|X)代表在事證X之下假設H成功的機率 P(H) (事前機率) 例.,它代表不管任何訊息，X會買電腦的機率 P(X): X在樣本資料出現機率 P(X|H) (事後機率),當假設H成立下, 樣本X出現的機率 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 貝氏理論 假設X為訓練資料, 透過貝式理論假設H的事後機率為 非正式的, 上式可表示為 posteriori = likelihood x prior/evidence 預測 X 屬於 Cj 若且為若機率 P(Ci|X) 在所有k個類別機率P(Ck|X)中為最高 實際困難: 需要許多機率的起始知識及大量運算成本 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 單純貝氏判別 假設D為包含類別標籤的訓練資料值組集，每個值組用n 維屬性向量X = (x1, x2, …, xn)表示 假設有個m類別 C1, C2, …, Cm. 希望能將一個已知X屬於某個類別的事後機率最大化, 也就是最大化 P(Ci|X) 可以透過貝式理論獲得 因為對所有的類別P(X)為常數, 所以僅需最大化 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 單純貝氏判別推演 簡化假設:假設屬性為條件獨立 (也就是說., 屬性間沒有關係): 大大降低計算成本: 僅需計算類別分佈 如果 Ak為類別值屬性, P(xk|Ci)則為在D中類別Ci 之屬性Ak的值為xk的個數除以|Ci, D| (Ci 在 D的值組數目) 如果 Ak為連續值屬性, P(xk|Ci)用均值為μ, 標準差為σ的高斯分佈計算得之 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 單純貝氏判別: 訓練資料 類別: C1:購買電腦 = ‘是’ C2:購買電腦 = ‘否’ 資料樣本 X = (年齡 =青年, 收入 = 中, 學生 = 是 信用評等 = 一般) March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 單純貝氏判別: 範例 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 避免0-機率問題 單純貝氏判別中每個條件機率必須是不為0, 否則預測機率為0 例.假設資料集有 1000 值組, 收入=低 (0), 收入= 中 (990), 收入 = 高 (10), 使用拉普拉斯修正 (或拉普拉斯預估) 對所有狀況加上1 Prob(收入=低) = 1/1003 Prob(收入= 中) = 991/1003 Prob(收入 = 高) = 11/1003 修正過的機率非常接近原來機率 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 單純貝氏判別: 提議 優點 容易執行 在大部分案例中都有不錯的結果 缺點 假設: 類別條件讀例, 失去正確性 事實上變數間存在相依 如何處理相依? 貝式信賴網路 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 貝氏信賴網路 允許定義變數間的類別條件獨立的關係 用圖示的方式來表達這種關係 表示變數間相依 給予特定聯合機率分佈 節點: 隨機變數 箭頭: 相依 X 與 Y 為 Z父親, 並且 Y 為 P父親 Z 與 P無相依 無迴路 Y Z P X March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 貝氏信賴網路: 範例 肺癌變數的條件機率表 (CPT) CPT包含每個已知值與其父節點值所有排列組合的條件機率值 假設資料值組X=x1,…,xn而屬性變數為Y1,…,Yn, 則從CPT中X的結合機率為: 貝氏信賴網路 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 訓練貝氏信賴網路 許多方式: 當網路結構與所有變數都是已知: 從CPT中學習 網路結構已知, 某些變數隱藏:梯度降低 (貪婪爬坡式)法, 如同類神經網路 網路結構未知,所有變數都是已知: 搜尋模型空間來重建網路拓樸 未知結構, 所有變數均隱藏: 沒有方法 參考 D. Heckerman: Bayesian networks for data mining March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 使用IF-THEN規則進行判別 知識以 IF-THEN 規則形式表式 R1: IF 年齡青年 AND 學生是 THEN 購買電腦=是 規則前提 對應規則結論 規則評估:涵蓋率 (coverage) 與正確率 (accuracy) ncovers =規則R所涵蓋值組的個數 ncorrect =規則R能正確判別值組的個數 coverage(R) = ncovers /|D| /* D: 訓練資料集 */ accuracy(R) = ncorrect / ncovers 如果超過一個以上的規則被啟動，我們就需要衝突調解策略 大小排序:計算滿足規則的前提大小，並利用這個大小為指標，擁有最大指標值的規則將被執行 類別式排序:將規則按照類別種類遞減分組，擁有最大類別個數的規則被執行 規則式排序:使用規則排序時，我們產生決策清單 (decision list)，在決策清單中擁有最高指標值的規則才會被執行 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 從決策樹找出規則 規則比大樹狀圖容易了解 從根節點到葉節點的方式建立規則 從根節點到葉節點的每一對屬性值形成一個結合關係: 葉節點包含類別預測 規則彼此是互斥 (mutually exclusive) 而且完全 (exhaustive) 範例: 從決策樹擷取規則 IF 年齡=青年 AND 學生=否 THEN 購買電腦=否 　　IF 年齡=青年 AND 學生=是 THEN 購買電腦=是 　　IF 年齡=中年 THEN 購買電腦=是 　　IF 年齡=老年 AND 信用評等=極佳 THEN 購買電腦=是 　　IF 年齡=老年 AND 信用評等=一般 THEN 購買電腦=否 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 從訓練資料擷取規則 順序涵蓋法: 直接從訓練資料擷取規則 典型順序涵蓋法: FOIL, AQ, CN2, RIPPER 規則在每個類別順序被產生，從一個類別Ci產生規則，我們會希望規則能包含所有Ci的值組，並且不包含其他類別的值組 步驟: 一次產生一個規則 被這個規則涵蓋的值組會被移除 接下來對剩下的值組繼續產生新的規則直到滿足終止 決策樹歸納: 同時學習一組規則 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques Learn-One-Rule? 從規則前提為空集合開始: condition = empty 使用貪婪深度優先法加入新屬性 選擇最能改善規則品質的屬性 規則品質指標: 同時考慮正確率與涵蓋率 Foil-gain (in FOIL & RIPPER):根據訊息獲利來進行一次邏輯規則學習 會傾向於包含許多正向值組，並擁有高正確率的規則 根據獨立的測試資料值組集進行規則修剪 Pos代表規則所涵蓋正向值組的個數，neg代表規則所涵蓋負向值組的個數. 如果FOIL_Prune的值在移除R後比較大，我們就會移除規則R March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 利用倒傳遞進行判別 倒傳遞:一種類神經網路 (neural network) 的學習方法 類神經網路是由心理學家與神經學家為了發展與神經元 (neurons) 類似的計算方式而產生的 類神經網路:一組互相連接的輸入輸出單元 (input/output units)，而每個單元都附帶有一個權重 (weight) 在學習的過程，權重會被更新以便能正確預測輸入值的類別 類神經網路也被稱為連接式學習 (connectionist learning)，因為它將所有的單元連接起來 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 用類神經網路進行判別 劣勢 需要長的訓練時間 需要一些經由實驗才能找出最好值的參數項網路拓撲 低理解度及一般很難去理解學習權重與隱藏單元背後的意義 優勢 對雜訊值的容許度 對未知資料樣式的判斷力 非常適用於連續值的資料 成功的應用於真實世界資料 與生俱來的平行化 最近有一些方法被用來對類神經網路產生規則 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 多層前授型網路 輸出向量 輸出層 隱藏層 wij 輸入層 輸入向量r: X March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 多層前授型網路如何工作? 利用值組的每個屬性值進行輸入 一個值組的所有屬性值同時輸入至輸入單元，而所有的輸入單元構成輸入層 輸入層中的輸入值陪同權重值同步的傳給第二層的單元，而第二層則被稱為隱藏層 隱藏層的數目是不固定的，經常是由實驗決定 最後一層隱藏層將權重輸出至輸出層 (output layer)，然後由輸出層決定值組預測的類別 一個網路稱為前授型 (feed-forward)，當權重不會繞回至輸入層或是比自己更前面的層 從統計的觀點，類神經網路執行一個非線性迴歸:只要能給予足夠的隱藏單元與訓練樣本，多層前授型網路可以相當接近地估計任何函數 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 設計網路拓撲 決定網路拓撲:決定輸入層的單元數、隱藏層的層數、每一層隱藏層的單元數以及輸出層的單元數 將輸入值正規化至0.0到1.0 一個輸入單元代表一個輸入值, 每個從0開始 當類別超過兩個以上，一般是以一個輸出單元代表一個類別 當網路訓練後結果不理想，經常會利用不同的網路拓撲與不同起始值的權重重新進行訓練 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 倒傳遞 不斷的對每個資料值組的預測類別與實際類別的比較進行學習 對於每個值組，依照網路預測類別與實際類別平均誤差值平方 (mean squared error) 的最小化來調整權重 調整是倒傳 (backward) 的方式:從輸出層，到最後一層的隱藏層，一直到第一層的隱藏層，所以稱為倒傳遞 步驟 起始網路權重與偏差值 向前傳遞輸入值 (套用活化函數) 倒傳遞錯誤值 (對權重與偏差值進行更新) 結束條件 (例當錯誤非常小時) March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 倒傳遞與理解 倒傳遞計算效能:假設有|D|的值組與w個權重，每次訓練需時間O(|D| * w),但是最差的狀況訓練次數會是輸入變數個數的冪次方 從網路擷取規則: 網路修剪 權重可以被移除，如果移除它不會降低網路的判別正確率 進行連結、單元與活化值的群組 規則根據這些活化值與相對應類別的組合產生，相同的輸入值與活化值的規則也會產生 敏感度分析:評估一個輸入變數對於輸出的影響.透過分析所產生的知識可以以規則表示 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—支持向量機 一個在判別線性與非線性資料有效的新方法 利用一個非線性轉換將原始資料對應至較高維度資料 在較高維度中進行最佳線性超平面分隔 透過適當非線性轉換至較高維度，兩種類別的資料都可以透過超平面進行分割 支持向量機利用支持向量 (support vectors) 與邊界 (margins) 來尋找超平面 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—歷史與應用 由Vladimir Vapnik、Bernhard Boser與Isabelle Guyon在1992年提出 特色:訓練時間需要很久，但是由於能夠描述複雜非線性決策邊界，支持向量機具有很高的正確率 可用於判別或預測 應用: 手寫數字辨識 物體辨識 時間序列預測 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—一般原理 支持向量 大間距 小間距 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—間距與支持向量 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—資料為線性分隔 m 假設資料集D包含值組 (X1, y1), …, (X|D|, y|D|), Xi代表具有類別yi的值組 分割兩個類別的直線會有無限多條，但是我們希望找到一條能對於未知值組有最小的判別誤差 SVM的方法是尋找最大邊距的超平面(maximum marginal hyperplane (MMH)) March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—線性可分隔 一個線性可分隔的超平面可以表示為 W ● X + b = 0 W={w1, w2, …, wn}代表權重向量，n代表屬性個數，b為一個常數(偏差) 一個 2-維超平面可以表示為 w0 + w1 x1 + w2 x2 = 0 超平面可以用於定義邊界方向: H1: w0 + w1 x1 + w2 x2 ≥ 1 for yi = +1 H2: w0 + w1 x1 + w2 x2 ≤ – 1 for yi = –1 落在超平面H1與H2上的值組稱為支持向量(support vectors) 有條件(凸面)二次方程式最佳化的問題:二次目標方程式與線性限制  二次線性規畫 (QP) 拉格朗日公式乘數 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 為何 SVM 對高維度資料有效? 複雜度是取決於支持向量的個數而不是資料的維度 支持向量是非常重要的訓練值組，因為它們就在最大邊距的超平面 (MMH) 如果我們移除其他訓練值組再重新訓練SVM，我們會得到相同的最大邊距的超平面 支持向量的個數可以用來計算SVM的判別期望錯誤率 (expected error rate)，而錯誤率與資料維度無關 一個擁有少數支持向量的SVM，即使是高維度資料，其通用性仍然很好 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—非線性分割 將原始資料轉換至較高維度資料 在較高維度中進行最佳線性超平面分隔 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques SVM—核心函數 核心函數用來取代點乘積,非線性轉換的點乘積在數學上我們可以用核心函數 (kernel function) K(Xi, Xj) 來代表, 也就是說., K(Xi, Xj) = Φ(Xi) Φ(Xj) 典型核心函數 SVM 也可用於判別多個類別(> 2) 與迴歸分析 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 關聯判別 關聯判別 它產生關聯規則並利用關聯規則進行判別 尋找頻繁樣式集與類別的有效關聯 判別: 根據分析一組像下列規則 P1 ^ p2 … ^ pl  “Aclass = C” (信賴度, 支持度) 為何有效? 由於關聯規則尋找高信賴度多個屬性間的關聯，因此它可以避免一些方法產生的限制。例如決策樹一次只考慮一個屬性 在許多研究中顯示，關聯判別比一些傳統的方法要來的正確，如C4.5 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 典型關聯判別方法 CBA (Classification By Association: Liu, Hsu & Ma, KDD’98) 探勘下列可能關連規則 條件集 (屬性-屬性值集合)  類別標籤 將規則按照其信賴度 (confidence) 與支持度 (support) 遞減排序 CMAR (Classification based on Multiple Association Rules: Li, Han, Pei, ICDM’01) 判別: 對多個規則進行統計分析 CPAR (Classification based on Predictive Association Rules: Yin & Han, SDM’03) 產生預測規則 (類似FOIL分析) 高效率, 正確率類似 CMAR March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 偷懶與期待學習 偷懶與期待學習 偷懶學習 (也稱為事例學習):將測試資料與訓練資料進行比對，並找出最相似的訓練資料類別 期待學習:先利用訓練資料建立一個判別模型以便進行測試 偷懶:不會花很多時間在事先利用訓練資料建立判別模型，反而是花很多時間在進行測試資料的判別上 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 偷懶學習:事例學習 事例學習: 儲存值組或事例並直到有新值組或事例產生才進行判別 典型方法 k-最近鄰判別法 值組或事例貝表示為歐幾里得空間上點. 案例式推理 使用象徵性代表與知識推論 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques k-最近鄰判別法 每個值組代表n-維空間上的一點 最近鄰是以歐幾里得距離來表示, dist(X1, X2) 目標函數可以是離散或實數值 離散值, k-NN 傳回在k訓練範例中最接近xq的最普遍值 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 案例式推理(CBR) CBR:使用問題解答的資料庫來解決新的問題 CBR將解決問題的值組或案例儲存成複雜的敘述 應用:顧客服務 (產品相關的診斷問題),法律判例 方法 將解決問題的值組或案例儲存成複雜的敘述 (例., 功能圖) 尋找類似案例, 可整合多個案例 套用背景知識與問題解決策略 挑戰 尋找好的相似指標 如何選擇顯著的特性對訓練個案進行索引與有效率的索引技術 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 基因運算法 (GA) 基因運算法:套用自然進化 (evolution) 的想法 隨機產生一組規則被設為起始群體 每個規則用一串位元表示 例., if A1 and ¬A2 then C2 可表示為 100 如果屬性有k個值而且，我們可以用k位元來代表一個屬性值 根據自然最適生存的方式，每個規則都會有一個最適值 (fitness value)，接下來利用起始群體產生新的群體，新群體稱為後代(offsprings) 規則的最適值通常為訓練資料的正確性 後代是經由基因運算如繁衍 (crossover) 與突變 (mutation) 產生 整個程序利用新的群體再繼續產生新的群體，一直到新群體的規則滿足預設的限制 執行緩慢但是容易被平行化 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 粗糙集合 粗糙集合用於大概定義相等類別 給定類別C, 粗糙集合定義兩個近似值:最小近似值 (類別一定為C的值組) 與最大近似值 (類別可能為C的值組) 尋找所有最小屬性集合 (reducts) 為 NP-hard 但是區別矩陣(discernibility matrix)可用於降低計算 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 模糊集合 利用介於0.0到1.0的真實值 來代表隸屬於某個類別的程度(如同模糊隸屬圖) 將屬性值轉換為模糊值 例., 將受入對應至 具有模糊值的類別{低, 中, 高} 對於一個新樣本會套用一個以上模糊值 每一個規則對類別的隸屬會產生貢獻 每個預測類別的真實值會被加總起來 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 何謂預測? (數值) 預測類似於判別 建立模型 對一個輸入值進行一個連續或順序值值結果的預測 預測不同於判別 判別域余預測類別式類別 預測連續值函數 預測主要方法: 迴歸 建立一個或多個獨立或預測變數 (independent or predictor variables) 與相依或回應變數 (dependent or response variable) 間的關係 迴歸分析 線性迴歸與多變量線性迴歸分析 非線性迴歸 其他迴歸分析:通用線性模型,波松迴歸, log線性模型,迴歸樹 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 線性迴歸 線性迴歸:包含一個回應變數 y與一個預測變數x y = w0 + w1 x W0為Y截距 (Y-intercept) 與w1為迴歸係數代表上述迴歸直線的斜率 最小平方法:預估線性函數錯誤最小化的方法 多元線性迴歸:包含超過一個以上的預測變數 訓練資料包含|D|點, 以 (X1, y1), (X2, y2),…, (X|D|, y|D|) 表示 例. 2-維資料, 可表示為: y = w0 + w1 x1+ w2 x2 可以使用如SAS、SPSS或S-Plus等軟體 許多非線性函數可轉換成上述方程式 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 非線性迴歸 某些非線性模型可用多項式函數表示 透過變數轉換將非線性模型轉換為線性模型, 例, y = w0 + w1 x + w2 x2 + w3 x3 利用新變數: x2 = x2, x3= x3 可轉換為 其他函數如冪次方函數也可轉換為線性模型 某些非線性模型無法轉換為線性函數，如指數加總函數 (sum of exponential) 可以透過最小平方差的方法來進行預估 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 其他迴歸模型 通用線性模型: 依據線性迴歸可用於建立類別回應變數模型的假設 回應變數y的變異數不是一個常數，而是變數y均值的函數 邏輯斯迴歸:將回應變數與預測變數間的關係視為一線性函數 波松迴歸:如果資料分佈為波松分佈 對數線性模型: (類別資料) 用於預估離散多維機率分佈 對資料壓縮 (data compression) 與資料平滑化 (data smoothing) 非常有用 迴歸樹與模型樹 用於預測連續值函數 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 判別正確指標 acc(M):為模型M的正確率 模型M的錯誤率為 = 1 – acc(M) 混亂矩陣CMi,j表示類別 i 被歸類為類別 j 的值組個數 其它正確指標 (例., 癌症檢測) 敏感度 = t-pos/pos /*衡量真實正向在正向值組的比例*/ 特定性 = t-neg/neg /*衡量真實負向在負向值組的比例*/ 精確性 = t-pos/(t-pos + f-pos) 正確率 =敏感度 * pos/(pos + neg) +特定性 * neg/(pos + neg) 可用於評估成本 (costs) 與效益 (benefits) March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 預測錯誤指標 衡量預測正確: 衡量預測值離已知值多遠 損失函數:衡量yi與yi’之間的誤差 絕對誤差: | yi – yi’| 平方差: (yi – yi’)2 測試錯誤率 :測試資料損失函數值的平均 均值絕對誤差: 均值平方差: 相對絕對誤差: 相對平方差: 當離異值存在時，均值平方差會有極大影響而均值絕對誤差則否。如果我們將均值平方差取平方根，則它被稱為平方根均值平方差 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 測試(Holdout)法 將資料隨機切成兩個獨立部分 訓練資料 (例., 2/3) 用於建立模型 測試資料 (例., 1/3) 用於評估模型的正確率 隨機取樣: 另一種測試法 進行k次測試，正確率為k次的平均 交叉驗證 (k-fold, k = 10 為最普遍) 隨機將原始資料分割成k個不重疊的部分 (folds), 每個大小相近 當執行第次i的時候，將Di設為測試資料，剩下的當作訓練資料。 捨去1 : k folds 當 k =值設為資料值組的個數 分層交叉驗證:對原始資料進行分割，而每個不重疊部分的資料類別分佈大約相似 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 衡量判別或預測模型的正確性(II) 自助法 適用於小資料集 使用均勻取出放回 (uniformly with replacement) 的方式從原始資料選取訓練樣本 每一次被選為當作訓練資料的值組都具有相同的機率 有許多不同的自助法，而最常用的是.632自助 假設資料包含個d值組，我們會利用均勻取出放回的方式從原始資料選擇d個值組，這個值組當作訓練資料，而不在訓練資料的值組當作測試資料。假設我們重複許多次這樣的步驟，63.2%的原始資料值組會在自助 (bootstrap) 區域中，而剩下的36.8%的原始資料會在測試資料中(因為 (1 – 1/d)d ≈ e-1 = 0.368) 重複執行k次，則模型的平均正確率為: March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 組合方法:增加正確率 組合方法 組合多個模型來改善整體的正確率 組合k個學習模型M1, M2, …, Mk 來改善整體的正確率 常用組合方法 掛袋法:將所有預測模型的平均預測值當作未知值組的預測值 推進法:對每個訓練值組設定一個權重 組合: 整合一組不同質判別模型 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 掛袋法: 自助法聚合 如同:根據多數決診斷 訓練 在第i次執行時，我們從原始資料D中利用均勻取出放回法 (sampled with replacement) 找出d的訓練值組Di (如同., boostrap) 利用訓練值組Di 產生判別模型Mi 判別: 判別未知樣本 X 將未知值組X代入判別模型 M1, M2, …,Mk ，出現最多次數的判別類別會當作未知X值組的類別 預測:將所有預測模型的平均預測值當作未知值組X的預測值 正確率 會比在原始資料中僅僅產生一個判別模型的正確率來的高 雜訊資料對它的影響也比較小 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 推進法 如同: 參考許多醫生, 對每個診斷設權重, 結果根據這些具權重診斷組合 執行方式? 對每個訓練值組設定一個權重 產生k個判別模型進行學習 第i次模型Mi 會對模型判別錯誤的值組進行權重的調整，讓下一個判別模型Mi+1能對這些判別錯誤的值組能多注意 將未知值組代入k個模型，並對這些模型設定不同權重進行判別 推進法可延伸至預測連續值 與掛袋法比較:正確率一般會比掛袋法高,但具有過適的風險 March 1, 2017 Data Mining: Concepts and Techniques

Adaboost (Freund and Schapire, 1997) D個包含類別資料值組 (X1, y1), …, (Xd, yd), I一開始每個值組權重設為 (1/d) 在第次i產生判別模型時 利用取出放回的方法從原始資料產生d個值組的訓練資料Di 根據每個值組的權重進行選取 利用Di產生判別模型Mi 將Di中的值組當作測試資料代入判別模型Mi,並計算錯誤率 當值組被判斷錯誤時，我們增加該值組的權重，否則我們降低它的權重 錯誤率: err(Xj)為值組Xj的錯誤率.判別模型Mi的錯誤率計算如下: 判別模型Mi的權重如下 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 模型選擇: ROC 曲線 ROC (Receiver Operating Characteristics) 曲線:利用圖式比較兩個判別模型 源自訊號偵測理論 顯示真實正向正確率 (true positive rate) 與錯誤正向正確率 (false positive rate) 的折衷程度 ROC曲線下方區域代表模型正確率的指標 將測試值組遞減排序: 最屬於真實正向排最上面 越接近對角線區域的模型愈不正確 (也就是, 愈接近0.5區域) 縱軸代表真實正向 橫軸代表錯誤正向 對角線表示模型預測每個值組真實正向的機率與錯誤正向相同 最好的模型區域應為1.0 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 第六章.判別與預測 何謂判別? 何謂預測? 判別與預測議題 決策樹判別 貝氏判別 規則判別 倒傳遞判別 支持向量機 (SVM) 關連判別 偷懶學習 (從鄰居學習) 其他判別方法 預測 正確與錯誤指標 組合方法 模型選擇 總結 March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 判別與預測為兩種資料分析的形式，它們可以建立模型來描述重要類型或預測未來資料趨勢. 有效與可量度方法: 決策樹歸納,單純貝氏判別,貝氏信賴網路,規則式判別,支持向量機,關聯判別,最近鄰法與案例式推論法,基因運算法, 粗糙集合, 模糊集合. 線性、非線性與通用線性迴歸可用於預測，許多非線性的問題可以透過預測變數轉換將其轉換為線性問題。不同於決策樹，迴歸樹與模型樹也可用於預測. March 1, 2017 Data Mining: Concepts and Techniques

Data Mining: Concepts and Techniques 總結 (II) 分層交叉驗證 (stratified -fold cross-validation) 法在正確性預估是被推薦使用的，掛袋法與推進法套用不同模型來改善整體正確性. 顯著檢定 與 ROC曲線 在模型選擇非常有用 有許多比較判別與預測模型的研究 沒有一個特定的模型是優於所有的模型 在尋求方法時，正確率、訓練時間、一致性、解釋性與可量度性之間的折衷必須加以考量 March 1, 2017 Data Mining: Concepts and Techniques