资料探勘方式.ppt

1、第 14 章：資料探勘方式,k-Means 族群推算法 k-近鄰法 決策樹 關聯法 神經網路系統,本章學習重點,族群推算法的目的是將資料歸類為不同的族群，而k為族群的數目。 k-Means 族群推算法的步驟如下： 1. 決定要找出多少個族群。換句話說，決定 k 值。 2. 隨意選出 k 個資料來當做這 k 個族群的中心點。,14-1 k-Means 族群推算法,k-Means 族群推算法的步驟(續)： 3. 由這 k 個資料點為起頭，建立出首輪的 k 族群。在這個時候，每一筆資料都暫時屬於某一個族群。 4. 找出每一個族群新的中心點。 5. 重複步驟3及步驟4，直到終止條件成立。,k-Mean

2、s 族群推算法,最常被用到的終止條件有兩種： 每個族群的中心點不再改變。 某種收斂標準已經達到。 一種常見的收斂標準是Sum of Squared Errors (SSE)： 代表在族群i中的每一個資料點， 是族群 i 的中心點，而 代表每一個資料點和它所屬族群中心點的距離。,k-Means 族群推算法,SSE =,k-Means 族群推算法-範例,9個點分成3群,k-Means 族群推算法-範例-續,步驟1: k=3 步驟2:隨意選出3個資料來當作這3個族群的中心點 步驟3:由這3個資料點為起點，建立出首輪的3個族群,k-Means 族群推算法-範例-續,步驟4:找出每一個族群新的中心點 族

3、群1=(1+4+2)/3, (3+1+2)/3=(2.33,2) 族群2=(2+1)/2, (5+6)/2=(1.5,5.5) 族群3=(3+5+6+6)/4, (5+2+2+3)/4=(5,3),k-Means 族群推算法-範例-續,步驟3(第二次疊代):由新的資料中心點為起點，建立出第二輪的 3個族群,k-Means 族群推算法-範例-續,步驟4(第二次疊代):找出每一個族群新的中心點 族群1=(1+4+2)/3, (3+1+2)/3=(2.33,2) 族群2=(2+3+1)/3, (5+5+6)/3=(2,5.33) 族群3=(5+6+6)/3, (2+2+3)/3=(5.67,2.33

4、),k-Means 族群推算法-範例-續,步驟3(第三次疊代):由新的資料中心點為起點，建立出第二輪的 3個族群,k-Means 族群推算法-範例-續,步驟4(第三次疊代):找出每一個族群新的中心點 族群1=(1+4+2)/3, (3+1+2)/3=(2.33,2) 族群2=(2+3+1)/3, (5+5+6)/3=(2,5.33) 族群3=(5+6+6)/3, (2+2+3)/3=(5.67,2.33),這種方式的目的是要由已知的屬性來找出未知屬性的值。 它的概念是類似的資料會有類似的值。 如果兩筆資料的已知屬性很接近，那它們未知屬性的值也會很接近。,k-近鄰法,k-近鄰法的步驟如下： 決定

5、要以多少個最接近的資料點來決定我們要求的數值。換句話說，決定k值。 加入訓練集的資料。 當有新的資料時，我們就找出訓練資料集中k個與這筆新資料最近的資料值。由於這k個資料的值是已知的，我們就可以由這些已知的值中來推算新資料這個屬性的值。,k-近鄰法,距離函數是被用來找出不同筆資料之間的距離。 在計算距離時，需要能夠將不同維度的距離用同一種標準顯現出來。 最常用的有以下兩種方式：,距離函數,Min-Max Normalization：,Z-Score Standardization：,在找出 k-近鄰之後，有以下兩種方式決定未知資料值： 假設每 k 筆接近的資料都是一樣的重要。 假設與新資料越接

6、近的資料值比重應該越大。 一個資料的重要性是跟它和新資料的距離成反比。,決定資料值的方式,k-近鄰法-範例,一個43歲，受過15年教育的人，應該被歸類於哪一個收入族群?,k-近鄰法-範例-續,一個43歲，受過15年教育的人，應該被歸類於哪一個收入族群?,k-近鄰法-範例-續,標準化計算方式: 年齡為2070歲，教育年數為622年 標準化年齡距離公式=(年齡-20)/50 標準化受教育年數距離公式(受教育年數-6/16),k-近鄰法-範例-續,計算與新資料點的距離: (xi, yi)為各資料點，(x0, y0)為新資料點 距離=,選擇最接近的一筆資料 答案是B，而B代表中收入，因此結論是一個43

7、歲而且受過15年教育的人，是屬於中收入族群。 選擇最接近的兩筆資料 答案是B、F，但B代表中收入，F代表高收入，因此無法做出確定的結論。 (3) 選擇最接近的三筆資料 答案是B、F、A，而B、A代表中收入，F代表高收入，因此結論屬於中收入族群。,k-近鄰法-範例-續,假設每k筆接近的資料都一樣重要時 利用資料重要性與其距離的平方成反比的特性，做為其權重值,(4) 選擇最接近的三筆資料 中收入: 1/(0.07)2+1/(0.20)2=229 高收入: 1/(0.09)2=123 因此結論是屬於中收入族群。 (5) 選擇最接近的兩筆資料 中收入: 1/(0.07)2=204 高收入: 1/(0.

8、09)2=123 因此結論是屬於中收入族群。,14-3 決策樹,決策樹例子：根據月收入、申請信用卡頻率、繳錢紀錄、有無背負循環利息這四個因素，判斷一個人的信用。,決策樹的特性如下： 能夠很清楚地描述一筆資料是如何被歸類。 這個目標屬性需要是類別性的，而不能是連續性的。 有的時候，決策樹已經無法再做任何的分割，可是那一個節點上資料的目標屬性並不是完全一樣的。 這個時候的規則會以下方式敘述：X 規則有 y % 的可能會成立。,決策樹,在建立決策樹時，我們的目的是要決定哪一個條件適用於決策樹的哪個節點。 最常見的方式有： CART C4.5,決策樹方式,CART 的特性是每一個決定點都有兩個結果。

9、CART的做法是在每一個節點上，都找出所有可能的條件，然後再依照以下的方式來決定哪一個條件是最適當的,CART,CART,為在節點 t 上條件 s 的適合度。,tL 為節點 t 的左子節點， tR 為節點 t 的右子節點。,節點tL中屬於 j 類別的資料數 節點 t 所有的資料數,節點tR中屬於 j 類別的資料數 節點 t 所有的資料數,用來找出信用度的訓練資料集,CART-範例,在根節點中可能被用到的規則,CART-範例-續,計算每一個規則的(s|t),CART-範例-續,規則1計算方式: tL=4 tR=6 PL=tL/N=4/10=0.4 PR=tR/N=6/10=0.6 P(j|tL)

10、=P(佳|tL)=2/4=0.5 P(j|tL)=P(不佳|tL)=2/4=0.5 P(j|tR)=P(佳|tR)=4/6=0.67 P(j|tR)=P(不佳|tR)=2/6=0.33 (s|t)=2*PL*PR*|P(j|tL)-P(j|tR)| =2*0.4*0.6*(|0.5-0.67|+|0.5-0.33|) =0.48*(0.17+0.17) =0.1632,經過初步選擇的CART決策樹,CART-範例-續,月收入=高的訓練資料集,CART-範例,在左邊的子節點中可能被用到的規則,CART-範例-續,計算每一個規則的(s|t),CART-範例-續,規則4計算方式: tL=1 tR=2

11、 PL=tL/N=1/3=0.33 PR=tR/N=2/3=0.67 P(j|tL)=P(佳|tL)=1/1=1.0 P(j|tL)=P(不佳|tL)=0/0=0.0 P(j|tR)=P(佳|tR)=2/2=1.0 P(j|tR)=P(不佳|tR)=0/0=0.0 (s|t)=2*PL*PR*|P(j|tL)-P(j|tR)| =2*0.33*0.67*(|1.0-1.0|+|0.0-0.0|) =0.44*(0.0) =0.0,經過初步選擇的CART決策樹,CART-範例-續,C4.5 和 CART 有以下的不同： 在 C4.5 中，每一個決定點可以有不只兩個結果。在CART，每一個決定點只

12、能有兩個結果。 在 C4.5 中，類別屬性的每一個可能的值都會有自己的結果。 舉例來說，如果收入族群是分為高、中、低三等，那任何用到這個屬性來做規則的節點就會有三個子節點。 C4.5 的目標是找出哪一個規則最能夠減低資料的亂度 (Entropy)。,C4.5,對一個屬性而言，亂度的定義是： j 代表所有可能的值，而 pj 代表每一個 j 值發生的可能性。 整個資料集的亂度為： T 代表整個資料集，Ti 代表被規則 S 分割過後的子資料集，而 Pi 代表資料在 i 子資料集的比例。,C4.5,要找出哪一個規則最能夠減低資料的亂度，我們計算 G(S) = H(T) HS(T) G(S)值最高的規則

13、，就是我們要採用的規則。,C4.5,用來找出信用度的訓練資料集,C4.5-範例,在根節點中可能被用到的規則,C4.5-範例-續,計算每一個規則的G(S),C4.5-範例-續,規則1計算方式: P佳=4/10=0.4 P不佳=6/10=0.4 H(T)=- Pj log2 Pj = -0.4 log2 0.4 0.6 log2 0.6 = 0.971 Hs(T)= Pi PH(Ti) = P高H高 + P中H中 + P低H低 P高= 4/10 = 0.4 P中= 3/10 = 0.3 P低= 3/10 = 0.3 H高= -2/4 log2(2/4) 2/4 log2(2/4) =1 H中= -

14、3/3 log2(3/3) 0/3 log2(0/3) =0 H低= -1/3 log2(1/3) 2/3 log2(2/3) =0.9183 Hs(T)= Pi PH(Ti) = (0.4*1)+(0.3*0)+(0.3*0.9183)=0.676 G(S)=H(T) - Hs(T)= 0.971 0.676 = 0.295,經過初步選擇的CART決策樹,C4.5-範例-續,月收入？,高,低,中,關聯法,目的是在找出哪些屬性之間有關。 這種關係通常的表達法是如果A，然後B，以及與這個規則相關的支持度 (Support) 和信心 (Confidence)。 支持度的定義是在所有的資料中，有多少

15、比例的資料包含A和B。 信心的定義是在所有包含A的資料中，有多少比例的資料也同時包含B。,關聯法可以是監督性的或非監督性的。 最常用來尋找資料中關聯的方式有A Priori方式及GRI方式這兩種。,關聯法,在做關聯分析時的一個最大的問題，就是有可能的規則數量太大。 A Priori 方式是一種能夠降低可能規則數目的方式。 A Priori 的原理是如果一個組合，Z，是不常發生的，那 Z 加上任何別的組合仍然是不常發生的。 A Priori 方式只能接受類別性的輸入值。,A Priori 方式,A Priori方式的步驟如下： 由所有的組合中，找出所有常發生的組合。常發生組合的定義是這個組合至少

16、發生次。 從所有常發生的組合中，找出符合最低標準支持度及信心的組合。,A Priori 方式,GRI 方式能夠接受類別性或數值性的輸入值。 GRI 方式的輸出結果是類別性。 GRI 的做法是由 J-計量來測量一個規則的有趣性。J-計量越高的規則就越有意義。,GRI方式,GRI的步驟為： 決定最低的支持度和信心。 決定總共要找出幾個規則 (以 n 代表)。 GRI找出所有單一前例的規則，然後算出各個規則的 J-計量。GRI保留前 n 個最高 J-計量的規則。 算完單一前例的規則後，GRI就重複計算更複雜規則的 J-計量，直到所有的可能都計算完畢。,GRI方式,J-計量的定義是： p(x) 是 x

17、 發生的可能性 p(y) 是 y 發生的可能性 p(y|x) 是當我們知道 x 已發生時，y 發生的可能性。,J-計量定義,在如果買柴，然後就有買鹽的規則中，x是柴，y是鹽； 假設p(x)=0.6, p(y)=0.7, p(y|x)=0.66，則,J-計量定義-範例,神經網路做法的起源，就是希望能夠以類似人腦的運作方式，來找出資料中的訊息。 系統分為三個層次： 輸入層次：這個層次將資料送入神經網路。 隱藏層次：這個層次處理輸入的資料。 輸出層次：這個層次輸出神經網路系統算出的結果。,神經網路系統,神經網路系統,運用神經網路系統的步驟如下： 決定神經網路系統的構造。 找出訓練資料集。 以訓練資料

18、集來讓系統學習。所謂系統學習，就是讓系統找到節點與節點間最佳的係數。 在我們對學習的成果滿意之後 (通常這代表某種結束條件成立)，就可以將這個系統用在新的資料上。,神經網路系統,在人腦中，當一個神經細胞接收到的信號高過於某一個門檻時，這個神經細胞就會發出信號給與它相連的神經細胞。 激發函數就是用來模擬這個過程。 一個激發函數需要滿足以下的特性： 必須是連續的 必須是可以取微分的。 當x值增加時，f(x)值不能降低。,激發函數,係數調整的公式如下： 代表誤差函數 (Error Function) 在這個值時的坡度。 代表在調整 w 值時，應該要往坡度的反方向。,激發函數,是學習速率，它的值介於 0 和 1 之間。 當大的時候，每一次的調整幅度就比較大。這可以增加學習的速度，可是可能會造成震盪。 所謂震盪，就是在學習的過程中，w值一直遊蕩於w*（誤差函數的最低點）的兩邊，而無法越來越接近w*。 當小的時候，學習速度就比較