數(shù)據(jù)挖掘算法(共15頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上分類Classification:分類是指將目標對象按照不同的標記進行分組，所有的標記都是已知的，這些對象往往都具有不同的特點。也就是說對于一個 classifier ，通常需要你告訴它“這個東西被分為某某類”這樣一些例子。理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數(shù)據(jù)進行分類預(yù)測的能力，這種提供訓練數(shù)據(jù)的過程通常叫做(監(jiān)督學習)。應(yīng)用場景：銀行貸款安全和風險、信用卡持卡用戶進行分類KNN算法：K最鄰近分類算法（K-Nearest Neighbor），最簡單的機器學習算法之一。思路是：如果一個樣本在特征空間中的k個最相似的

2、樣本中的大多數(shù)屬于某個類，則該樣本也屬于某個類別。如上圖所示，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。決策樹分類算法ID3：ID3算法是由Quinlan首先提出的。該算法是以為基礎(chǔ)，以和度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。具體流程如下：輸入：樣本集合S,屬性集合A輸出：ID3決策樹若所有種類的屬性都處理完畢，返回：否則執(zhí)行2計算出信息增益最大屬性a，把該屬性作為一個節(jié)點，如果僅憑屬性a就可以對樣本進行分類，則返回；否則執(zhí)行3。對屬性

3、a的每個可能的取值v，執(zhí)行下一操作：將所有屬性a的值是v的樣本作為S的一個子集Sv；生產(chǎn)新的屬性集合AT=A-a以樣本集合Sv和屬性集合AT為輸入，遞歸執(zhí)行id3算法。分類系統(tǒng)的信息熵和信息增益：對分類系統(tǒng)來說，類別C是變量，可能的取值是C1，C2，C3.Cn，而每個類別出現(xiàn)的概率為P(C1),P(C2),P(C3).P(Cn)，N就是系統(tǒng)的類別，因此分類系統(tǒng)的熵代表包含系統(tǒng)所有特征屬性時系統(tǒng)的信息量（熵），就可以表示為：HC=-i=1nP(Ci)log2P(Ci) ; P(Ci)即類別Ci出現(xiàn)的概率對分類系統(tǒng)來說，一個特征屬性，系統(tǒng)有它和沒它時信息量將發(fā)生變化，而前后信息量的差值就是這個特征

4、給系統(tǒng)帶來的信息量，即信息增益。系統(tǒng)包含特征屬性時的信息量有了，那么就要求系統(tǒng)不包含該特征屬性時的信息量，這個問題等價于系統(tǒng)包含了特征屬性X，但特征屬性X已經(jīng)固定不能變化時的信息量，此時的信息量即條件熵需要用特征屬性X每個可能的值出現(xiàn)的概率來表示：HCX=P1HCX=x1+P2HCX=x2+PnHCX=xn=i=1nPiH(C|X=Xi)具體到分類系統(tǒng)，分類系統(tǒng)的特征屬性T的固定值t只可能取兩個值（即t出現(xiàn)或t不出現(xiàn)），例如濕度這個特征屬性的固定值（高）只可能取兩個值，即高要么出現(xiàn)，要么不出現(xiàn)。HCT=PtHCt+PtHCt=-Pti=1nP(Ci|t)log2P(Ci|t)-Pti=1nP(

5、Ci|t)log2P(Ci|t)因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：IG(C)=H(C)-H(C|T)應(yīng)用舉例：使用ID3分類算法預(yù)測未知樣本的類標號。給定球隊球類比賽結(jié)果的訓練樣本集見下表。根據(jù)天氣（Outlook），溫度（Temperature），濕度（Humidity），風強度（Windy）來判斷該球隊比賽結(jié)果是否會贏。類標號屬性比賽結(jié)果具有兩個不同值Win, Lose。設(shè)C1對應(yīng)于類 Result=“Win”,而C2 對應(yīng)于類Result =“Lose”。使用ID3分類算法來預(yù)測樣本為Outlook=Sunny, Temperature=Ho

6、t, Humidity=High, Wind=Strong的情況下，比賽的輸贏結(jié)果。首先，類別是（輸贏結(jié)果）。取值yes的記錄有9個，取值為no的記錄有5個，那么P(C1)=9/14，P(C2)=5/14，那么計算分類系統(tǒng)的熵:Entropy(S)=-(9/14)*log2(9/14) -(5/14)*log2(5/14);然后分別計算以各個屬性作為根節(jié)點的信息增益Outlook的信息增益：Entropy(Sunny)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971Entropy(Rain)=-(2/5)*log2(2/5)-(3/5)*log2(3/5) =0.

7、971Entropy(Overcast)=-(4/4)*log2(4/4)=0Gain(Outlook)=Entropy(S)-(5/14)*Entropy(Sunny)-(5/14)*Entropy(Rain)- (4/14)* Entropy(Overcast)=0.247Temperature的信息增益：Entropy(Hot)=-(2/4)*log2(2/4)-(2/4)*log2(2/4)=1Entropy(Mild)=-(4/6)*log2(4/6)-(2/6)*log2(2/6)=0.918Entropy(Cool)=-(3/4)*log2(3/4)-(1/4)*log2(1/4

8、)=0.811Gain(Temperature)= Entropy(S)-(4/14)*Entropy(Hot)-(6/14)* Entropy(Mild) -(4/14)* Entropy(Cool)=0.247Humidity的信息增益： Entropy(High)=-(3/7)*log2(3/7)-(4/7)*log2(4/7)=0.985Entropy(Normal)=-(6/7)*log2(4/6)-(6/7)*log2(1/7)=0.592Gain(Humidity)= Entropy(S)-(7/14)*Entropy(High)-(7/14)* Entropy(Normal)

9、=0.151Wind的信息增益：Entropy(Strong)=-(3/6)*log2(3/6)-(3/6)*log2(3/6)=1Entropy(Weak)=-(6/8)*log2(6/8)-(2/8)*log2(2/8)=0.811Gain(Wind)= Entropy(S)-(6/14)*Entropy(Strong)-(8/14)* Entropy(Weak) =0.048這樣我們就得到以上4個屬性相應(yīng)的信息增益值，最后安裝信息增益值最大的原則選擇outlook為根節(jié)點。子節(jié)點也重復(fù)以上的步驟。就可以建立下以下這可決策樹：OutlookHumidityWindWinWinWinLose

10、WinSunnyOvercastRainHighNormalStrong掃描所有的交易記錄對每個候選計數(shù)Weak因此，將樣本X 指派給類C1：Result =“Win”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情況下這場比賽會贏。 樸素貝葉斯分類算法： 樸素貝葉斯分類基于貝葉斯定理,假設(shè)一個屬性值對給定類的影響?yīng)毩⒂谄渌麑傩缘闹怠ＴO(shè)X是類標號未知的數(shù)據(jù)樣本。設(shè)H為某種假定，如，數(shù)據(jù)樣本X屬于某特定的類C。因此我們希望確定P(H|X)，即給定觀測數(shù)據(jù)樣本X,假定H成立的概率（后驗概率）。貝葉斯定理（公

11、式）：PHX=PXHP(H)P(X)樸素貝葉斯分類的工作過程如下： 1、用n 維特征向量X=x1, x2, xn表示每個數(shù)據(jù)樣本，用以描述對該樣本的n 個屬性A1, A2, , An 的度量。2、假定數(shù)據(jù)樣本可以分為m 個類C1, C2, , Cm。給定一個未知類標號的數(shù)據(jù)樣本X，樸素貝葉斯分類將其分類到類Ci ，當且僅當P(Ci|X) P(Cj|X) 1jm，ji P(Ci|X)最大的類Ci 稱為最大后驗假定。由貝葉斯公式可知PCiX=PXCiP(Ci)P(X) 3、由于P(X) 對于所有類都為常數(shù)，只需要P(X|Ci)P(Ci )最大即可。如果類的先驗概率未知，通常根據(jù)貝葉斯假設(shè)，可取P(

12、C1)=P(C2)=P(Cm)，從而只需P(X|Ci)最大化。也可以用P(Ci )=si /s 計算，其中si 是類Ci 中的訓練樣本數(shù)，s 是訓練樣本總數(shù)。4. 當數(shù)據(jù)集的屬性較多時，計算P(X|Ci)的開銷可能非常大。如果假定類條件獨立，可以簡化聯(lián)合分布，從而降低計算P(X|Ci)的開銷。給定樣本的類標號，若屬性值相互條件獨立，即屬性間不存在依賴關(guān)系，則有：PXCi=k=1nP(Xk|Ci)其中，概率P(x1|Ci), P(x2|Ci), P(xn|Ci)可以由訓練樣本進行估值。如果Ak 是離散值屬性，則P(xk|Ci)=sik/si 。其中，sik 是類Ci 中屬性Ak 的值為xk 的訓

13、練樣本數(shù)，而si 是Ci 中的訓練樣本數(shù)。如果Ak 是連續(xù)值屬性，通常假定該屬性服從高斯分布（正態(tài)分布）。從而有PXkCi=gXk,Ci,Ci=12Ciexp(-12Ci2(Xk-Ci)2)其中，給定類 Ci的訓練樣本屬性 Ak的值，gXk,Ci,Ci是屬性 Ak的高斯密度函數(shù)，Ci,Ci分別為均值和標準差。5. 對每個類Ci ，計算P(X|Ci)P(Ci)。把樣本X指派到類Ci 的充分必要條件是P(X|Ci)P(Ci)P(X|Cj)P(Cj) 1jm，ji 也就是說，X 被分配到使P(X|Ci)P(Ci)最大的類Ci中。應(yīng)用舉例：使用樸素貝葉斯分類預(yù)測未知樣本的類標號。給定PlayTenni

14、s 的訓練樣本集見下表。使用樸素貝葉斯分類來預(yù)測樣本為Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong的情況下，是否打球。要分類的未知樣本為：X =Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong。根據(jù)樸素貝葉斯分類方法，需要最大化P(X|Ci)P(Ci)，i =1, 2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算：P(PlayTennis=“Yes”) = 9/14 = 0.643P(PlayTennis=“No”) = 5/14 = 0.357為計算P

15、(X |Ci)，i=1, 2，先計算下面的條件概率：P(Outlook=“Sunny”| PlayTennis =“Yes”) = 2/9 = 0.222P(Outlook=“Sunny”| PlayTennis =“No”) = 3/5 = 0.600P(Temperature=“Hot”| PlayTennis =“Yes”) = 2/9 = 0.222P(Temperature=“Hot”| PlayTennis =“No”) = 2 /5 = 0.400P(Humidity=“High”| PlayTennis =“Yes”) = 3/9 = 0.333P(Humidity=“High

16、”| PlayTennis =“No”) = 4/5 = 0.800P( Windy=“Strong”| PlayTennis =“Yes”) = 3/9 = 0.333P( Windy=“Strong”| PlayTennis =“No”) = 3/5 = 0.600利用以上概率，可以得到：P(X | PlayTennis =“Yes”) = 0.2220.2220.3330.333 = 0.005P(X | PlayTennis =“No”) = 0.6000.4000.8000.600 = 0.115P(X | PlayTennis =“Yes”) P(PlayTennis =“Yes”

17、) = 0.0050.643 = 0.003P(X | PlayTennis =“No”) P(PlayTennis =“No”)= 0.1150.357 = 0.041因此，將樣本X 指派給類C2：PlayTennis =“No”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情況下不去打球。支持向量機（SVM）算法： 支持向量機（support vector machine），是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉(zhuǎn)化為一個凸二次規(guī)劃問題

18、的求解。支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。因此最大化幾何間隔成了我們訓練階段的目標。如下圖所示：為了簡化問題，我們用二維空間來解釋這個分類問題。要將圖中黑白圓圈分類，中間的直線就是一個分類函數(shù)，它可以完全將這些樣本分開。一般的，如果一個線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。實際上，一個線性函數(shù)是一個實值函數(shù)（即函數(shù)的值是連續(xù)的實數(shù)），而我們的分類問題（例如這里的二

19、元分類問題回答一個樣本屬于還是不屬于一個類別的問題）需要離散的輸出值，例如用1表示某個樣本屬于類別C1，而用0表示不屬于，這時候只需要簡單的在實值函數(shù)的基礎(chǔ)上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個閾值來確定類別歸屬。 例如我們有一個線性函數(shù)g(x)=wx+b我們可以取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)0，就判別為類別C1，若g(xi)B=PBA=support_count(AB)support_count(A)其中，support_count(AB)和support_count(A)表示包含項集AB、A的事務(wù)計數(shù)，根據(jù)以上公

20、式，可以產(chǎn)生關(guān)聯(lián)規(guī)則如下：1、對于每個頻繁項集L，產(chǎn)生L的所有非空子集2、對于每個非空子集S，如果support_count(L)support_count(S)min_conf，則輸入規(guī)則：“S=(L-S)”那么例子中的頻繁項集將產(chǎn)生以下關(guān)聯(lián)規(guī)則：I1I2= I5confidence=2/4I1I5= I5confidence=2/2I2I5= I5confidence=2/2I1=I2 I5confidence=2/6 I2=I1 I5confidence=2/7I5=I1 I2confidence=2/2假設(shè)置信度為70%，那么只有第2,3,6條滿足強關(guān)聯(lián)規(guī)則。聚類Clustering分

21、析算法：一種無監(jiān)督的機器學習算法，對沒有標記（分類）的訓練樣本進行學習，以發(fā)現(xiàn)訓練樣本集中的結(jié)構(gòu)性知識。這里，所有的標記（分類）是未知的。而聚類則是指將物理或抽象對象的集合分到不同組的分析過程。這些組內(nèi)成員具有很大的相似性，而組間成員具有很大的相異性。同分類（Classification）不同，聚類不依賴事先預(yù)定義的類標記，而需要自己標識。K-Means算法：K-means算法是很典型的基于距離的算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。算法過程如下：1）從N個集合對象隨機選取K個對象作為；2）對剩余的每個集合對象測量其到每個的距離，并把它歸到最近的圓心的類

22、；3）重新計算已經(jīng)得到的各個類的圓心；4）迭代23步直至新的圓心與原圓心相等或小于指定閾值，即算法收斂結(jié)束。PageRank算法：Google的網(wǎng)頁排名算法，是一種由根據(jù)之間相互的計算等級（PR值）的排序算法。其基本思想如下：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的連接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/L(T)。其中PR（T）為T的PageRank值，L(T)為T的出鏈數(shù)。即一個頁面的得票數(shù)由所有鏈向它的頁面的重要性來決定，到一個頁面的相當于對該頁投一票。一個頁面PageRank值是由所有鏈向它的頁面（鏈入頁面）的重要性經(jīng)過算法得到的。簡

23、單的PageRank模型如下，A,B,C,D分別代表網(wǎng)頁節(jié)點，如果網(wǎng)頁A存在鏈接到網(wǎng)頁B，則存在一條有向邊A-B（有向圖如下：）。 BCCDA 如上圖的話，我們可以得到4個網(wǎng)頁的PR值如下：PRA=PRB2+PRCPRB=PRA3+PRD2PRC=PRA3+PRD2 PRD=PRA3+PRB2也可以用n*n的矩陣表示該有向圖，其中每行代表的是元素指向的節(jié)點，如第一行表示存在A節(jié)點指向B、C和D的鏈接。列表示對于指定的節(jié)點有多少個指向該節(jié)點的節(jié)點，如第一列則表示指向A節(jié)點的有B和C節(jié)點。 M=00110因為PR值要平均到每個鏈接，因此將矩陣每行除以每行的鏈接數(shù)可以得到新的矩陣如下： M=0將矩陣

24、M轉(zhuǎn)置后得到MT M=0由此我們可以得到PageRank的計算公式： PR(i)=(1-d)/n+dj=1nPR(j)L(j)用矩陣的形式表示如下：PR=(1-d)/n(1-d)/n+dL(1,1)L(1,n)L(n,1)L(n,n)PR（PR代表PageRank值，這里引入了d阻尼因素，是為了解決終止點和陷阱問題）PageRank算法的計算是一個迭代的過程，遞歸直到最后兩次的結(jié)果近似或者相同，即PR最終收斂，算法結(jié)束。人工神經(jīng)網(wǎng)絡(luò)：人工神經(jīng)網(wǎng)絡(luò)（ANN）簡稱神經(jīng)網(wǎng)絡(luò)，是由具有適應(yīng)性的簡單單元組成的廣泛并行互聯(lián)的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對真實世界物體做出的交互反應(yīng)?？梢哉f人工神經(jīng)網(wǎng)絡(luò)是利用人工的方式對生物神經(jīng)網(wǎng)絡(luò)的模擬。最早的神經(jīng)元模型M-P模型如下圖所示：其中Ii-1,1表示輸入，Y-1,1輸出，權(quán)值Wi-1,1表示輸入的連接強度，證書權(quán)值表示興奮性輸入，負數(shù)權(quán)值表示抑制性輸入。表示神經(jīng)元興奮時的閾值，當神經(jīng)元輸入的加權(quán)和大于時，神經(jīng)元處于興奮狀態(tài)。單輸出神經(jīng)元（感知器）的工作過程：1、從輸入端接受輸入信息Xi2、根據(jù)連接權(quán)值i，求出所有輸入的加權(quán)和=i