資料探勘方式.ppt

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

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

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 族群推算法-範(fàn)例-續(xù),步驟3(第二次疊代):由新的資料中心點(diǎn)為起點(diǎn)，建立出第二輪的 3個(gè)族群,k-Means 族群推算法-範(fàn)例-續(xù),步驟4(第二次疊代):找出每一個(gè)族群新的中心點(diǎn) 族群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 族群推算法-範(fàn)例-續(xù),步驟3(第三次疊代):由新的資料中心點(diǎn)為起點(diǎn)，建立出第二輪的 3個(gè)族群,k-Means 族群推算法-範(fàn)例-續(xù),步驟4(第三次疊代):找出每一個(gè)族群新的中心點(diǎn) 族群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),這種方式的目的是要由已知的屬性來找出未知屬性的值。 它的概念是類似的資料會(huì)有類似的值。 如果兩筆資料的已知屬性很接近，那它們未知屬性的值也會(huì)很接近。,k-近鄰法,k-近鄰法的步驟如下： 決定

5、要以多少個(gè)最接近的資料點(diǎn)來決定我們要求的數(shù)值。換句話說，決定k值。 加入訓(xùn)練集的資料。 當(dāng)有新的資料時(shí)，我們就找出訓(xùn)練資料集中k個(gè)與這筆新資料最近的資料值。由於這k個(gè)資料的值是已知的，我們就可以由這些已知的值中來推算新資料這個(gè)屬性的值。,k-近鄰法,距離函數(shù)是被用來找出不同筆資料之間的距離。 在計(jì)算距離時(shí)，需要能夠?qū)⒉煌S度的距離用同一種標(biāo)準(zhǔn)顯現(xiàn)出來。 最常用的有以下兩種方式：,距離函數(shù),Min-Max Normalization：,Z-Score Standardization：,在找出 k-近鄰之後，有以下兩種方式?jīng)Q定未知資料值： 假設(shè)每 k 筆接近的資料都是一樣的重要。 假設(shè)與新資料越接

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

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

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

9、CART的做法是在每一個(gè)節(jié)點(diǎn)上，都找出所有可能的條件，然後再依照以下的方式來決定哪一個(gè)條件是最適當(dāng)?shù)?CART,CART,為在節(jié)點(diǎn) t 上條件 s 的適合度。,tL 為節(jié)點(diǎn) t 的左子節(jié)點(diǎn)， tR 為節(jié)點(diǎn) t 的右子節(jié)點(diǎn)。,節(jié)點(diǎn)tL中屬於 j 類別的資料數(shù) 節(jié)點(diǎn) t 所有的資料數(shù),節(jié)點(diǎn)tR中屬於 j 類別的資料數(shù) 節(jié)點(diǎn) t 所有的資料數(shù),用來找出信用度的訓(xùn)練資料集,CART-範(fàn)例,在根節(jié)點(diǎn)中可能被用到的規(guī)則,CART-範(fàn)例-續(xù),計(jì)算每一個(gè)規(guī)則的(s|t),CART-範(fàn)例-續(xù),規(guī)則1計(jì)算方式: 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,經(jīng)過初步選擇的CART決策樹,CART-範(fàn)例-續(xù),月收入=高的訓(xùn)練資料集,CART-範(fàn)例,在左邊的子節(jié)點(diǎn)中可能被用到的規(guī)則,CART-範(fàn)例-續(xù),計(jì)算每一個(gè)規(guī)則的(s|t),CART-範(fàn)例-續(xù),規(guī)則4計(jì)算方式: 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,經(jīng)過初步選擇的CART決策樹,CART-範(fàn)例-續(xù),C4.5 和 CART 有以下的不同： 在 C4.5 中，每一個(gè)決定點(diǎn)可以有不只兩個(gè)結(jié)果。在CART，每一個(gè)決定點(diǎn)只

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

13、，就是我們要採(cǎi)用的規(guī)則。,C4.5,用來找出信用度的訓(xùn)練資料集,C4.5-範(fàn)例,在根節(jié)點(diǎn)中可能被用到的規(guī)則,C4.5-範(fàn)例-續(xù),計(jì)算每一個(gè)規(guī)則的G(S),C4.5-範(fàn)例-續(xù),規(guī)則1計(jì)算方式: 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,經(jīng)過初步選擇的CART決策樹,C4.5-範(fàn)例-續(xù),月收入？,高,低,中,關(guān)聯(lián)法,目的是在找出哪些屬性之間有關(guān)。 這種關(guān)係通常的表達(dá)法是如果A，然後B，以及與這個(gè)規(guī)則相關(guān)的支持度 (Support) 和信心 (Confidence)。 支持度的定義是在所有的資料中，有多少

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

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

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

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