Data Mining: Concepts and Techniques

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

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

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

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

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

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

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

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

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

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

屬性選擇: 資訊獲利 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

用連續值來計算訊息獲利當屬性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

訊息獲利會傾向於選擇擁有許多不同類別的屬性 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

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

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

貝氏理論: 基礎假設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

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

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

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

單純貝氏判別: 範例 March 1, 2017 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

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

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

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

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

從決策樹找出規則規則比大樹狀圖容易了解從根節點到葉節點的方式建立規則從根節點到葉節點的每一對屬性值形成一個結合關係: 葉節點包含類別預測規則彼此是互斥 (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

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

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

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

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

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

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

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

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

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

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

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

SVM—間距與支持向量 March 1, 2017 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

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

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

SVM—非線性分割將原始資料轉換至較高維度資料在較高維度中進行最佳線性超平面分隔 March 1, 2017 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

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

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

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

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

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

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

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

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

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

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

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

衡量判別或預測模型的正確性(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

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

推進法如同: 參考許多醫生, 對每個診斷設權重, 結果根據這些具權重診斷組合執行方式? 對每個訓練值組設定一個權重產生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

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

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

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

Data Mining: Concepts and Techniques

Similar presentations

Presentation on theme: "Data Mining: Concepts and Techniques"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Data Mining: Concepts and Techniques

Similar presentations

Presentation on theme: "Data Mining: Concepts and Techniques"— Presentation transcript:

Similar presentations

About project

反馈