分類-數(shù)據(jù)挖掘-韓家煒_3教材

1、2022年5月9日星期一1本講內(nèi)容n貝葉斯分類n基于神經(jīng)網(wǎng)絡(luò)的分類2022年5月9日星期一2Bayesian Classificationn是一種基于統(tǒng)計(jì)的分類方法，用來(lái)預(yù)測(cè)諸如某個(gè)樣本屬于某個(gè)分類的概率有多大n基于Bayes理論n研究發(fā)現(xiàn)，Nave Bayes Classifier在性能上和Decision Tree、Neural Network classifiers 相當(dāng)。在應(yīng)用于大數(shù)據(jù)集時(shí)，具有較高的準(zhǔn)確率和速度nNave Bayes Classifier假設(shè)屬性值之間是獨(dú)立的，因此可以簡(jiǎn)化很多計(jì)算，故稱之為Nave 。當(dāng)屬性值之間有依賴關(guān)系時(shí)，采用Bayesian Belief Ne

2、tworks進(jìn)行分類。2022年5月9日星期一3Bayesian Theorem: Basicsn假設(shè)X是未知分類標(biāo)號(hào)的樣本數(shù)據(jù)nH代表某種假設(shè)，例如X屬于分類C nP(H|X): 給定樣本數(shù)據(jù)X，假設(shè) H成立的概率n例如，假設(shè)樣本數(shù)據(jù)由各種水果組成，每種水果都可以用形狀和顏色來(lái)描述。如果用X代表紅色并且是圓的，H代表X屬于蘋果這個(gè)假設(shè)，則P(H|X)表示，已知X是紅色并且是圓的，則X是蘋果的概率。2022年5月9日星期一4Bayesian Theorem: BasicsnP(H): 任一個(gè)水果，屬于蘋果的概率. (不管它什么顏色，也不管它什么形狀)nP(X): 任一個(gè)水果，是紅色并且是圓的概

3、率 (不管它屬于什么水果)nP(X|H) : 一個(gè)水果，已知它是一個(gè)蘋果，則它是紅色并且是圓的概率。nP(H|X) : 一個(gè)水果，已知它是紅色并且是圓的,則它是一個(gè)蘋果的概率。2022年5月9日星期一5Bayesian Theorem: Basicsn現(xiàn)在的問題是，知道數(shù)據(jù)集里每個(gè)水果的顏色和形狀，看它屬于什么水果，求出屬于每種水果的概率，選其中概率最大的。也就是要算： P(H|X)n但事實(shí)上，其他三個(gè)概率， P(H)、 P(X)、 P(X|H) 都可以由已知數(shù)據(jù)得出，而P(H|X)無(wú)法從已知數(shù)據(jù)得出nBayes理論可以幫助我們：)()()|()|(XPHPHXPXHP2022年5月9日星期一

4、6Nave Bayes Classifiern每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量表示，描述由屬性對(duì)樣本的n個(gè)度量。n假定有m個(gè)類。給定一個(gè)未知的數(shù)據(jù)樣本X（即，沒有類標(biāo)號(hào)），分類法將預(yù)測(cè)X屬于具有最高后驗(yàn)概率（條件X下）的類。即，樸素貝葉斯分類將未知的樣本分配給類Ci ，當(dāng)且僅當(dāng)： 這樣，我們最大化 。其最大的類Ci稱為最大后驗(yàn)假定。根據(jù)貝葉斯定理: .1)|()|(ijmjXCPXCPji)|(XCPi)()()|()|(XPiCPiCXPXCPi2022年5月9日星期一7Nave Bayes Classifiern由于P(X) 對(duì)于所有類為常數(shù)，只需要 最大即可。如果類的先驗(yàn)概率未知，則通常假

5、定這些類是等概率的；即， 。并據(jù)此只對(duì) 最大化。否則，我們最大化 。類的先驗(yàn)概率可以用 計(jì)算；其中，si是類C中的訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。)()|(iiCPCXP)(.)()(21mCPCPCP)|(iCXP)()|(iiCPCXPssCPii)(2022年5月9日星期一8Nave Bayes Classifiern給定具有許多屬性的數(shù)據(jù)集，計(jì)算 的開銷可能非常大。為降低計(jì)算的開銷，可以樸素地假設(shè)屬性間不存在依賴關(guān)系。這樣， 概率 , , 可以由訓(xùn)練樣本估計(jì)，其中， (a) 如果Ak是分類屬性，則 ；其中sik 是在屬性Ak 上具有值xk 的類Ci 的訓(xùn)練樣本數(shù)，而si 是Ci中的訓(xùn)練

6、樣本數(shù) (b) 如果是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而，其中，給定類Ci的訓(xùn)練樣本屬性Ak的值， 是屬性Ak的高斯密度函數(shù)高斯密度函數(shù)，而 分別為平均值和標(biāo)準(zhǔn)差。)|(iCXPnkCixkPCiXP1)|()|()|(1iCxP)|(2iCxP)|(inCxPiikikssCxP)|(222)(21),()|(iCiCiiixCCCkikexgCxP),(iiCCkxgiiCC,2022年5月9日星期一9Nave Bayes Classifiern為對(duì)未知樣本X分類，對(duì)每個(gè)類Ci，計(jì)算 。樣本X被指派到類Ci，當(dāng)且僅當(dāng)： 換言之，X被指派到其 最大的類Ci。.1)()|()()|

7、(ijmjCPCXPCPCXPjjii)()|(iiCPCXP2022年5月9日星期一10Training datasetageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoClass:C1:buys_computer=yesC2:buys_computer=noData s

8、ample X =(age=30,Income=medium,Student=yesCredit_rating=Fair)2022年5月9日星期一11Nave Bayesian Classifier: An ExamplenCompute P(X|Ci) for each classP(buys_computer=“yes”) = 9/14=0.643P(buys_computer=“no”) = 5/14=0.357 P(age=“30” | buys_computer=“yes”) = 2/9=0.222 P(income=“medium” | buys_computer=“yes”)=

9、4/9 =0.444 P(student=“yes” | buys_computer=“yes)= 6/9 =0.667 P(credit_rating=“fair” | buys_computer=“yes”)=6/9=0.667 P(age=“30” | buys_computer=“no”) = 3/5 =0.6 P(income=“medium” | buys_computer=“no”) = 2/5 = 0.4 P(student=“yes” | buys_computer=“no”)= 1/5=0.2 P(credit_rating=“fair” | buys_computer=“

10、no”)=2/5=0.4 X=(age=30 , income =medium, student=yes, credit_rating=fair) P(X|Ci) : P(X|buys_computer=“yes”)= 0.222 x 0.444 x 0.667 x 0.667 =0.044 P(X|buys_computer=“no”)= 0.6 x 0.4 x 0.2 x 0.4 =0.019P(X|Ci)*P(Ci ) : P(X|buys_computer=“yes”) * P(buys_computer=“yes”)=0.044 x 0.643=0.028 P(X|buys_comp

11、uter=“no”) * P(buys_computer=“no”)= 0.019 x 0.357=0.007Therefore, X belongs to class “buys_computer=yes”2022年5月9日星期一12Nave Bayesian Classifier: Commentsn優(yōu)點(diǎn)n易于實(shí)現(xiàn) n多數(shù)情況下結(jié)果較滿意n缺點(diǎn)n假設(shè): 屬性間獨(dú)立, 丟失準(zhǔn)確性n實(shí)際上, 屬性間存在依賴 n處理依賴nBayesian Belief Networks 2022年5月9日星期一13Bayesian Belief NetworksnBayesian belief network

12、允許屬性間存在依賴關(guān)系n用一個(gè)有向無(wú)環(huán)圖來(lái)表示n每個(gè)結(jié)點(diǎn)代表一個(gè)隨機(jī)變量n每條弧代表一個(gè)概率依賴 XYZPqX,Y are the parents of Z, and Y is the parent of PqNo dependency between Z and PqHas no loops or cycles2022年5月9日星期一14Bayesian Belief Network: An ExampleFamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLCLC(FH, S)(FH, S)(FH, S) (FH, S)0.80

13、.Bayesian Belief NetworksThe conditional probability table for the variable LungCancer:Shows the conditional probability for each possible combination of its parentsniZParentsiziPznzP1)(|(),.,1(2022年5月9日星期一15本講內(nèi)容n貝葉斯分類n基于神經(jīng)網(wǎng)絡(luò)的分類2022年5月9日星期一16神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)最早是由心理學(xué)家和神經(jīng)學(xué)家提出的，旨在尋求開發(fā)和測(cè)試神經(jīng)的計(jì)

14、算模擬。n粗略地說，神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元，其中每個(gè)連接都與一個(gè)權(quán)相關(guān)聯(lián)。在學(xué)習(xí)階段，通過調(diào)整權(quán)值，使得神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)準(zhǔn)確性逐步提高。由于單元之間的連接，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)又稱連接者學(xué)連接者學(xué)習(xí)習(xí)。2022年5月9日星期一17神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)是以模擬人腦神經(jīng)元的數(shù)學(xué)模型為基礎(chǔ)而建立的，它由一系列神經(jīng)元組成，單元之間彼此連接。n從信息處理角度看，神經(jīng)元可以看作是一個(gè)多輸入單輸出的信息處理單元，根據(jù)神經(jīng)元的特性和功能，可以把神經(jīng)元抽象成一個(gè)簡(jiǎn)單的數(shù)學(xué)模型。2022年5月9日星期一18神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)有三個(gè)要素：拓?fù)浣Y(jié)構(gòu)、連接方式、學(xué)習(xí)規(guī)則n可以從這三方面對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行分類2022

15、年5月9日星期一19神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)：神經(jīng)網(wǎng)絡(luò)的單元通常按照層次排列，根據(jù)網(wǎng)絡(luò)的層次數(shù)，可以將神經(jīng)網(wǎng)絡(luò)分為單層神經(jīng)網(wǎng)絡(luò)、兩層神經(jīng)網(wǎng)絡(luò)、三層神經(jīng)網(wǎng)絡(luò)等n結(jié)構(gòu)簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)，在學(xué)習(xí)時(shí)收斂的速度快，但準(zhǔn)確度低。n神經(jīng)網(wǎng)絡(luò)的層數(shù)和每層的單元數(shù)由問題的復(fù)雜程度而定。問題越復(fù)雜，神經(jīng)網(wǎng)絡(luò)的層數(shù)就越多。n例如，兩層神經(jīng)網(wǎng)絡(luò)常用來(lái)解決線性問題，而多層網(wǎng)絡(luò)就可以解決多元非線性問題2022年5月9日星期一20神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)的連接：包括層次之間的連接和每一層內(nèi)部的連接，連接的強(qiáng)度用權(quán)來(lái)表示。n根據(jù)層次之間的連接方式，分為：n前饋式網(wǎng)絡(luò)：連接是單向的，上層單元的輸出是下層單元的輸入，如反向傳播網(wǎng)絡(luò)，K

16、ohonen網(wǎng)絡(luò)n反饋式網(wǎng)絡(luò)：除了單項(xiàng)的連接外，還把最后一層單元的輸出作為第一層單元的輸入，如Hopfield網(wǎng)絡(luò)n根據(jù)連接的范圍，分為：n全連接神經(jīng)網(wǎng)絡(luò)：每個(gè)單元和相鄰層上的所有單元相連n局部連接網(wǎng)絡(luò)：每個(gè)單元只和相鄰層上的部分單元相連2022年5月9日星期一21神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)n根據(jù)學(xué)習(xí)方法分：n感知器：有監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本的類別是已知的，并在學(xué)習(xí)的過程中指導(dǎo)模型的訓(xùn)練n認(rèn)知器：無(wú)監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本類別未知，各單元通過競(jìng)爭(zhēng)學(xué)習(xí)。n根據(jù)學(xué)習(xí)時(shí)間分：n離線網(wǎng)絡(luò)：學(xué)習(xí)過程和使用過程是獨(dú)立的n在線網(wǎng)絡(luò)：學(xué)習(xí)過程和使用過程是同時(shí)進(jìn)行的n根據(jù)學(xué)習(xí)規(guī)則分：n相關(guān)學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)連接間的

17、激活水平改變權(quán)系數(shù)n糾錯(cuò)學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)輸出單元的外部反饋改變權(quán)系數(shù)n自組織學(xué)習(xí)網(wǎng)絡(luò)：對(duì)輸入進(jìn)行自適應(yīng)地學(xué)習(xí)2022年5月9日星期一22常用的神經(jīng)網(wǎng)絡(luò)n神經(jīng)網(wǎng)絡(luò)種類很多，常用的有如下四種nHopfield網(wǎng)絡(luò)，典型的反饋網(wǎng)絡(luò)，結(jié)構(gòu)單層，有相同的單元組成n反向傳播網(wǎng)絡(luò)，前饋網(wǎng)絡(luò)，結(jié)構(gòu)多層，采用最小均方差的糾錯(cuò)學(xué)習(xí)規(guī)則，常用于語(yǔ)言識(shí)別和分類等問題nKohonen網(wǎng)絡(luò)：典型的自組織網(wǎng)絡(luò)，由輸入層和輸出層構(gòu)成，全連接nART網(wǎng)絡(luò)：自組織網(wǎng)絡(luò)2022年5月9日星期一23基于神經(jīng)網(wǎng)絡(luò)的分類方法n神經(jīng)網(wǎng)絡(luò)（主要是感知器）經(jīng)常用于分類n神經(jīng)網(wǎng)絡(luò)的分類知識(shí)體現(xiàn)在網(wǎng)絡(luò)連接上，被隱式地存儲(chǔ)在連接的權(quán)值中。n神經(jīng)網(wǎng)絡(luò)的

18、學(xué)習(xí)就是通過迭代算法，對(duì)權(quán)值逐步修改的優(yōu)化過程，學(xué)習(xí)的目標(biāo)就是通過改變權(quán)值使訓(xùn)練集的樣本都能被正確分類。2022年5月9日星期一24基于神經(jīng)網(wǎng)絡(luò)的分類方法n神經(jīng)網(wǎng)絡(luò)特別適用于下列情況的分類問題：n數(shù)據(jù)量比較小，缺少足夠的樣本建立模型n數(shù)據(jù)的結(jié)構(gòu)難以用傳統(tǒng)的統(tǒng)計(jì)方法來(lái)描述n分類模型難以表示為傳統(tǒng)的統(tǒng)計(jì)模型2022年5月9日星期一25基于神經(jīng)網(wǎng)絡(luò)的分類方法n缺點(diǎn)：n需要很長(zhǎng)的訓(xùn)練時(shí)間，因而對(duì)于有足夠長(zhǎng)訓(xùn)練時(shí)間的應(yīng)用更合適。n需要大量的參數(shù)，這些通常主要靠經(jīng)驗(yàn)確定，如網(wǎng)絡(luò)拓?fù)浠颉敖Y(jié)構(gòu)”。n可解釋性差。該特點(diǎn)使得神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘的初期并不看好。 2022年5月9日星期一26基于神經(jīng)網(wǎng)絡(luò)的分類方法n優(yōu)

19、點(diǎn)：n分類的準(zhǔn)確度高n并行分布處理能力強(qiáng)n分布存儲(chǔ)及學(xué)習(xí)能力高n對(duì)噪音數(shù)據(jù)有很強(qiáng)的魯棒性和容錯(cuò)能力n 最流行的基于神經(jīng)網(wǎng)絡(luò)的分類算法是80年代提出的后向傳播算法。 2022年5月9日星期一27后向傳播算法n后向傳播算法在多路前饋多路前饋神經(jīng)網(wǎng)絡(luò)上學(xué)習(xí)。 2022年5月9日星期一28定義網(wǎng)絡(luò)拓?fù)涠x網(wǎng)絡(luò)拓?fù)?n在開始訓(xùn)練之前，用戶必須說明輸入層的單元數(shù)、隱藏層數(shù)（如果多于一層）、每一隱藏層的單元數(shù)和輸出層的單元數(shù)，以確定網(wǎng)絡(luò)拓?fù)洹?2022年5月9日星期一29定義網(wǎng)絡(luò)拓?fù)涠x網(wǎng)絡(luò)拓?fù)?n對(duì)訓(xùn)練樣本中每個(gè)屬性的值進(jìn)行規(guī)格化將有助于加快學(xué)習(xí)過程。通常，對(duì)輸入值規(guī)格化，使得它們落入0.0和1.0之間。

20、n離散值屬性可以重新編碼，使得每個(gè)域值一個(gè)輸入 單 元 。 例 如 ， 如 果 屬 性 A 的 定 義 域 為(a0 ,a1 ,a2)，則可以分配三個(gè)輸入單元表示A。即，我們可以用I0 ,I1 ,I2作為輸入單元。每個(gè)單元初始化為0。如果A = a0，則I0置為1；如果A = a1，I1置1；如此下去。2022年5月9日星期一30定義網(wǎng)絡(luò)拓?fù)涠x網(wǎng)絡(luò)拓?fù)?n一個(gè)輸出單元可以用來(lái)表示兩個(gè)類（值1代表一個(gè)類，而值0代表另一個(gè)）。n如果多于兩個(gè)類，則每個(gè)類使用一個(gè)輸出單元。2022年5月9日星期一31定義網(wǎng)絡(luò)拓?fù)涠x網(wǎng)絡(luò)拓?fù)鋘隱藏層單元數(shù)設(shè)多少個(gè)“最好” ，沒有明確的規(guī)則。n網(wǎng)絡(luò)設(shè)計(jì)是一個(gè)實(shí)驗(yàn)過程，

21、并可能影響準(zhǔn)確性。權(quán)的初值也可能影響準(zhǔn)確性。如果某個(gè)經(jīng)過訓(xùn)練的網(wǎng)絡(luò)的準(zhǔn)確率太低，則通常需要采用不同的網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌某跏紮?quán)值，重復(fù)進(jìn)行訓(xùn)練。 2022年5月9日星期一32后向傳播算法n后向傳播算法學(xué)習(xí)過程：n迭代地處理一組訓(xùn)練樣本，將每個(gè)樣本的網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際的類標(biāo)號(hào)比較。n每次迭代后，修改權(quán)值，使得網(wǎng)絡(luò)預(yù)測(cè)和實(shí)際類之間的均方差最小。n這種修改“后向”進(jìn)行。即，由輸出層，經(jīng)由每個(gè)隱藏層，到第一個(gè)隱藏層（因此稱作后向傳播）。盡管不能保證，一般地，權(quán)將最終收斂，學(xué)習(xí)過程停止。 n算法終止條件：訓(xùn)練集中被正確分類的樣本達(dá)到一定的比例，或者權(quán)系數(shù)趨近穩(wěn)定。2022年5月9日星期一33后向傳播算法n后

22、向傳播算法分為如下幾步：n初始化權(quán) n向前傳播輸入 n向后傳播誤差 2022年5月9日星期一34后向傳播算法n初始化權(quán)初始化權(quán)n網(wǎng)絡(luò)的權(quán)通常被初始化為很小的隨機(jī)數(shù)（例如，范圍從-1.0到1.0，或從-0.5到0.5）。n每個(gè)單元都設(shè)有一個(gè)偏置（bias），偏置也被初始化為小隨機(jī)數(shù)。 2022年5月9日星期一35后向傳播算法n對(duì)于每一個(gè)樣本X，重復(fù)下面兩步：n向前傳播輸入n向后傳播誤差2022年5月9日星期一36向前傳播輸入n計(jì)算各層每個(gè)單元的輸入和輸出。n輸入層：n輸出=輸入=樣本X的屬性；n即，對(duì)于單元j，Oj = Ij = Xj n隱藏層和輸出層：n輸入=前一層的輸出的線性組合,n即，對(duì)于

23、單元j， Ij =wij Oi + j n輸出=jIjeO112022年5月9日星期一37向后傳播誤差n計(jì)算各層每個(gè)單元的誤差。n向后傳播誤差，并更新權(quán)和偏置2022年5月9日星期一38向后傳播誤差n計(jì)算各層每個(gè)單元的誤差。n輸出層單元j，誤差 nOj是單元j的實(shí)際輸出，而Tj是j的真正輸出。n隱藏層單元j，誤差n wjk是由j到下一層中單元k的連接的權(quán)nErrk是單元k的誤差)(1 (jjjjjOTOOErrkjkkjjjwErrOOErr)1 (2022年5月9日星期一39向后傳播誤差更新權(quán)和偏差，以反映傳播的誤差。權(quán)由下式更新：其中，wij是權(quán)wij的改變。l是學(xué)習(xí)率學(xué)習(xí)率，通常取0和1

24、之間的值。 偏置由下式更新：其中，j是偏置j的改變。 n ijijOErrlw)(ijijijwwwjjErrl)(jjj后向傳播算法Output nodesInput nodesHidden nodesOutput vectorInput vector: xiwijijiijjOwIjIjeO11)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1 (ijijijOErrlww)(jjjErrl)(2022年5月9日星期一41Examplen設(shè)學(xué)習(xí)率為0.9。訓(xùn)練樣本X = 1,0,1 類標(biāo)號(hào)為1x1x2x3w14w15w24w25W34w35w46w564561010.2--0.50.2-0.3-0.2-單元j凈輸入Ij輸出Oj4 45 56 60.2+0-0.5-0.4 = -0.70.2+0-0.5-0.4