1、1,數(shù)據(jù)挖掘 第9章 分類:高級分類,2,目錄 9.1 貝葉斯信念網(wǎng)絡(luò) 9.2 用后向傳播分類,3,9.1 貝葉斯信念網(wǎng)絡(luò),樸素貝葉斯分類：假定一個(gè)屬性值在給定類上的影響?yīng)毩⒂谄渌麑傩缘闹怠?貝葉斯信念網(wǎng)絡(luò)（簡稱信念網(wǎng)絡(luò)）：說明聯(lián)合條件概率分布，它允許在變量的子集間定義類條件獨(dú)立性。它提供一種因果關(guān)系的圖形模型，練后的貝葉斯信念網(wǎng)絡(luò)可以用于分類。 本質(zhì)區(qū)別：類條件獨(dú)立,4,信念網(wǎng)絡(luò)有兩個(gè)成分定義：有向無環(huán)圖和條件概率表集（CPT）。 有向無環(huán)圖的每個(gè)節(jié)點(diǎn)代表一個(gè)隨機(jī)變量，每條弧線代表一個(gè)概率依賴。 若一條弧由節(jié)點(diǎn)X到Z，則X是Z的雙親或直接前驅(qū)，而Z是X的后代。給定其雙親，每個(gè)變量條件獨(dú)立于圖

2、中它的非后代。,X和Y是Z的雙親，而P是Y的后代。不是X的后代，即 Z 條件獨(dú)立于 P。,9.1.1 概念和機(jī)制,2020年6月27日星期六,數(shù)據(jù)挖掘：概念與技術(shù),5,圖為一個(gè)6個(gè)布爾變量的簡單信念網(wǎng)絡(luò)。由圖知，肺癌患者受其家族肺癌史和是否吸煙的影響。若已知患者得了肺癌，變量PositiveXRay獨(dú)立于該患者是否具有家族肺癌史，也獨(dú)立于他是否吸煙。換言之，一旦我們知道變量LungCancer的結(jié)果，那么變量FamilyHistory和smoker就不再提供關(guān)于PositiveXRay的任何附加信息。這些弧還表明：給定其雙親FamilyHistory和smoker，變量LungCancer條件

3、獨(dú)立于Emphysema。,2020年6月27日星期六,數(shù)據(jù)挖掘：概念與技術(shù),6,下表為變量LungCancer的CPT，給出其雙親節(jié)點(diǎn)FamilyHistory和 Smoker的每個(gè)可能值組合的條件概率。 例如左上角和右下角的表目分別代表： P(LungCancer=yes|FamilyHistory=yes,Smoker=yes)=0.8 P(LungCancer=no|FamilyHistory=no,Smoker=no)=0.9,2020年6月27日星期六,數(shù)據(jù)挖掘：概念與技術(shù),7,給定其雙親，每個(gè)變量都條件獨(dú)立于圖中它的非后代，則貝葉斯信念 網(wǎng)絡(luò)給定的變量集合上的聯(lián)合條件概率分布為：

4、 其中, 是X的值的特定組合的概率， 的值對應(yīng)于Yi的CPT的表目。 分類過程不是返回單個(gè)類標(biāo)號，而是可以返回概率分布，給出每個(gè)類的概率。,8,在訓(xùn)練網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)的變量是可觀測的或隱藏的。 1.給定可觀測變量，存在一些學(xué)習(xí)算法，從訓(xùn)練數(shù)據(jù)學(xué)習(xí)網(wǎng)絡(luò)拓?fù)洹?2.網(wǎng)絡(luò)拓?fù)湟阎⑶易兞靠捎^測，則訓(xùn)練網(wǎng)絡(luò)是直接的。該過程由計(jì)算CPT表目組成。 3.網(wǎng)絡(luò)拓?fù)浣o定，而某些變量是隱藏的，可以選擇不同的方法訓(xùn)練信念網(wǎng)絡(luò)。梯度下降法。,9.1.2 訓(xùn)練貝葉斯信念網(wǎng)絡(luò),目的：獲得各個(gè)狀態(tài)之間的相關(guān)概率，得到最佳的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。,9,設(shè)D是數(shù)據(jù)元組X1，X2，,XD的訓(xùn)練集。訓(xùn)練信念網(wǎng)絡(luò)我們必須學(xué)習(xí)CPT表目的值。設(shè)

5、wijk是具有雙親Ui=uik的變量Yi=yij的CPT的表目，其中wijk=P(Yi=yij|Ui=uik)。wijk可以看做權(quán)重，其集合記作W。這些權(quán)重被初始化為隨機(jī)概率值。梯度下降策略執(zhí)行貪心爬山法，在每次迭代或每一步，算法向當(dāng)時(shí)看上去是最優(yōu)解的方向移動(dòng)而不回溯。每次迭代都更新權(quán)重，最終收斂于一個(gè)局部最優(yōu)解。 假定wijk的每種可能設(shè)置都是等可能的，梯度下降策略用于搜索能最好的對數(shù)據(jù)建模的wijk值，這種策略是迭代的，他沿著準(zhǔn)則函數(shù)的負(fù)方向搜索解。我們要找到最大化該函數(shù)的權(quán)重的集合W。,10,我們最大化 。通過按 的梯度來做，使得問題更簡單。給定網(wǎng)絡(luò)的wijk的初值，計(jì)算按下步驟計(jì)算：

6、1)梯度計(jì)算：對每個(gè)i，j，k，計(jì)算 右端的概率要對D中的每個(gè)訓(xùn)練元組Xd計(jì)算。當(dāng)Yi和Ui表示的變 量對某個(gè)Xd是隱藏的時(shí)，對應(yīng)的概率可由貝葉斯網(wǎng)絡(luò)推理的標(biāo)準(zhǔn)算法，由元組的觀察變量計(jì)算。 2)沿梯度方向前進(jìn)一小步：可由式 更新權(quán)重。其中，l是步長的學(xué)習(xí)率，被設(shè)置為一個(gè)小常數(shù)，有助于收斂。 3)重新規(guī)格化權(quán)重：由于權(quán)重wijk是概率值，在0.0-1.0之間，對于所有的i，k， 必須為1。 遵循這種學(xué)習(xí)形式的算法稱作自適應(yīng)概率網(wǎng)絡(luò)(adaptive probabilistic networks)。信念網(wǎng)絡(luò)是計(jì)算密集的。信念網(wǎng)絡(luò)提供了因果結(jié)構(gòu)的顯示表示，可以用網(wǎng)絡(luò)拓?fù)浜?或條件概率值的形式提供先驗(yàn)

7、知識。這可以顯著地提高學(xué)習(xí)效率。,11,后向傳播(BackPropagation Network，簡稱BP網(wǎng)絡(luò))是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法。在眾多不同類型的神經(jīng)網(wǎng)絡(luò)和神經(jīng)網(wǎng)絡(luò)算法中，最流行的的神經(jīng)網(wǎng)絡(luò)就是后向傳播。 神經(jīng)網(wǎng)絡(luò)最早是由心理學(xué)家和神經(jīng)學(xué)家提出的，旨在尋求開發(fā)和測試神經(jīng)的計(jì)算模擬。粗略地說，神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元，其中每個(gè)連接都與一個(gè)權(quán)重相關(guān)聯(lián)。在學(xué)習(xí)階段，通過調(diào)整這些權(quán)重，能夠正確預(yù)測輸入樣本的類標(biāo)號。,9.2 用后向傳播分類,12,缺點(diǎn)：神經(jīng)網(wǎng)絡(luò)需要很長的訓(xùn)練時(shí)間，因而對于有足夠長訓(xùn)練時(shí)間的應(yīng)用更合適。它需要大量的參數(shù)，這些通常主要靠經(jīng)驗(yàn)確定，如網(wǎng)絡(luò)拓?fù)浠颉敖Y(jié)構(gòu)”。神經(jīng)網(wǎng)

8、絡(luò)的可解釋性差。對于數(shù)據(jù)挖掘，這些特點(diǎn)并不理想。 優(yōu)點(diǎn)：神經(jīng)網(wǎng)絡(luò)對噪音數(shù)據(jù)有高承受能力，對未經(jīng)訓(xùn)練的數(shù)據(jù)有較強(qiáng)的分類能力。在缺乏屬性與類之間的聯(lián)系的知識時(shí)可以使用它們。適合連續(xù)值得輸入和輸出。 已經(jīng)成功地應(yīng)用于廣泛的現(xiàn)實(shí)世界的數(shù)據(jù)，包括手寫字符識別、病理和實(shí)驗(yàn)醫(yī)學(xué)、訓(xùn)練計(jì)算機(jī)朗讀英文課本。,13,后向傳播算法在多層前饋神經(jīng)網(wǎng)絡(luò)上學(xué)習(xí)。它迭代地學(xué)習(xí)用于元組類標(biāo)號預(yù)測的一組權(quán)重。多層前饋神經(jīng)網(wǎng)絡(luò)由一個(gè)輸入層、一個(gè)或多個(gè)隱藏層和一個(gè)輸出層組成。下圖為一個(gè)多層前饋神經(jīng)網(wǎng)絡(luò)。,9.2.1 多層前饋神經(jīng)網(wǎng)絡(luò),14,每層由一些單元組成，網(wǎng)絡(luò)的輸入對應(yīng)于對每個(gè)訓(xùn)練元組的觀測屬性。輸入通過輸入層，加權(quán)提供給隱藏

9、層的“類神經(jīng)元”第二層。該隱藏層加權(quán)重輸出作為構(gòu)成下一個(gè)隱藏層或輸出層的單元的輸入。輸出層發(fā)布給定元組的網(wǎng)絡(luò)預(yù)測。 輸入層的單元稱作輸入單元，隱藏層和輸出層的單元稱為神經(jīng)節(jié)點(diǎn)或輸出單元。網(wǎng)絡(luò)是前饋的，因?yàn)槠錂?quán)重都不回送到輸入單元，或前一層的輸出單元。網(wǎng)絡(luò)是全連接的，如果每個(gè)單元都向下一層的每個(gè)單元提供輸入。 網(wǎng)絡(luò)的輸入對應(yīng)于對每個(gè)訓(xùn)練元組的觀測屬性，每個(gè)輸出單元取前一層單元輸出的加權(quán)和作為輸入。隱藏層的數(shù)量是任意的，給定足夠多的隱藏單元和足夠的訓(xùn)練樣本, 多層前饋神經(jīng)網(wǎng)絡(luò)可以逼近任意函數(shù)。,15,在開始訓(xùn)練之前，用戶必須說明輸入層的單元數(shù)、隱藏層數(shù)（如果多于一層）、每一隱藏層的單元數(shù)和輸出層的

10、單元數(shù)，以確定網(wǎng)絡(luò)拓?fù)洹?對訓(xùn)練樣本中每個(gè)屬性的值進(jìn)行規(guī)格化，將有助于加快學(xué)習(xí)過程。通常，對輸入值規(guī)格化，使得它們落入 0.0 -1.0 之間。 神經(jīng)網(wǎng)絡(luò)可以用于分類（預(yù)測給定元組的類標(biāo)號）和數(shù)值預(yù)測（預(yù)測連續(xù)值輸出）。對于分類，一個(gè)輸出單元可以用來表示兩個(gè)類（其中值1代表一個(gè)類，而值0代表另一個(gè)類）。如果多于兩個(gè)類，則每個(gè)類使用一個(gè)輸出單元。 對于最好的隱藏層單元數(shù)，沒有明確的規(guī)則。網(wǎng)絡(luò)設(shè)計(jì)是一個(gè)實(shí)驗(yàn)過程，并可能影響訓(xùn)練結(jié)果網(wǎng)絡(luò)的準(zhǔn)確性。權(quán)的初值也可能影響結(jié)果的準(zhǔn)確性。一旦網(wǎng)絡(luò)經(jīng)過訓(xùn)練，并且其準(zhǔn)確率不能被接受，則通常用不同的網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌某跏紮?quán)值，重復(fù)訓(xùn)練過程。,9.2.2 定義網(wǎng)絡(luò)拓

11、撲,16,后向傳播通過迭代地處理訓(xùn)練元組數(shù)據(jù)集, 將每個(gè)元組的網(wǎng)絡(luò)預(yù)測與實(shí)際知道的類標(biāo)號相比較進(jìn)行學(xué)習(xí)，對于每個(gè)訓(xùn)練樣本, 修改權(quán)重使得網(wǎng)絡(luò)預(yù)測和實(shí)際類之間的均方誤差最小。這種修改“后向”進(jìn)行，即由輸出層，經(jīng)由每個(gè)隱藏層，到第一個(gè)隱藏層（因此稱作后向傳播）。盡管不能保證，一般地，權(quán)重將最終收斂，學(xué)習(xí)過程停止。,9.2.3 后向傳播,17,算法：后向傳播。使用后向傳播算法，分類或預(yù)測的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。 輸入：訓(xùn)練樣本 D，學(xué)習(xí)率 l，多層前饋網(wǎng)絡(luò) network。 輸出：訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)。 方法： 1) 初始化 network 的權(quán)重和偏倚。 2) while 終止條件不滿足 3) for D中的

12、每個(gè)訓(xùn)練樣本 X 4) / 向前傳播輸入 5) for 每個(gè)輸入層單元 j 6) Oj=Ij； /輸入單元的輸出是它的實(shí)際輸入值 7) for 隱藏或輸出層每個(gè)單元 j 8) / 關(guān)于前一層 i，計(jì)算單元 j 的凈輸入 9) Oj= 1/(1+eIj) / 計(jì)算單元 j 的輸出 10) / 后向傳播誤差 11) for 輸出層每個(gè)單元 j 12) Errj=Oj(1-Oj)(Tj-Oj) / 計(jì)算誤差 13) for 由最后一個(gè)到第一個(gè)隱藏層，對于隱藏層每個(gè)單元 j 14) Errj=Oj(1-Oj) / 計(jì)算關(guān)于下一個(gè)較高層 k 的誤差 15) for networ中每個(gè)權(quán) wij 16)

13、wij=(l) ErrjOi / 權(quán)重增量 17) wij = wij+ wij / 權(quán)重更新 18) for networ中每個(gè)偏倚j 19) j=(l)Errj / 偏倚增量 20) j=j+j / 偏倚更新 21) ,18,步驟解釋如下：,1)初始化權(quán)重：網(wǎng)絡(luò)的權(quán)重被初始化為很小的隨機(jī)數(shù)（例如，由-1.0 到 1.0，或由-0.5 到 0.5）。每個(gè)單元有一個(gè)相關(guān)聯(lián)的偏倚。 每個(gè)樣本 X按以下步驟處理。 2)向前傳播輸入：訓(xùn)練元組提供給網(wǎng)絡(luò)的輸入層，然后計(jì)算各層的凈輸入和輸出： 對于輸入層的單元 ：它的輸出等于它的輸入；即Oj = Ij 對于隱藏層和輸出層的凈輸入：等于連接該單元的每個(gè)輸

14、入乘以其對應(yīng)的權(quán)重，然后求和，再加上偏倚。 其中, Wij是上一層的單元i到單元j的連接權(quán)重；Oi是上一層的單元i的輸出；而j是單元j的偏倚。,19,隱藏層和輸出層的每個(gè)單元取其凈輸入，然后將激活函數(shù)作用于它， 激活函數(shù)使用邏輯斯諦(logistic)或S型（sigmoid）函數(shù)。給單元 j的輸入Oj用下式計(jì)算： Oj =,該函數(shù)又稱擠壓函數(shù), 因?yàn)樗鼘⒁粋€(gè)較大的輸入值域映射到較小的區(qū)間0到1。邏輯斯蒂函數(shù)是非線性的且可微的，使得后向傳播算法可以對非線性可分的問題建模。 對于對于每個(gè)隱藏層，直到輸出層，我們計(jì)算輸出值Oj，給出網(wǎng)絡(luò)預(yù)測。,20,3)后向傳播誤差：通過更新權(quán)重和反映網(wǎng)絡(luò)預(yù)測誤差的

15、偏倚，向后傳播誤差。 對于輸出層單元 j的誤差 Errj用下式計(jì)算： Errj=Oj(1-Oj)(Tj-Oj) 其中，Oj是單元 j 的實(shí)際輸出，而 Tj是 j 基于給定訓(xùn)練元組的已知目標(biāo)值。Oj(1-Oj)是邏輯斯諦函數(shù)的導(dǎo)數(shù)。 對于隱藏層單元 j 的誤差為： Errj=Oj(1-Oj) 其中，wjk是由下一較高層中單元 k到單元 j 的連接權(quán)，而 Errk是單元 k的誤差。,21,更新權(quán)重和偏倚，反映傳播的誤差，權(quán)重由下式更新： wij=(l) ErrjOi wij = wij+ wij 其中： wij是權(quán)重wij的改變，變量 l 是學(xué)習(xí)率，通常取 0 和1 之間的值。后向傳播用梯度下降法

16、搜索權(quán)重的集合。這些權(quán)值可以對給定的分類問題建模，使得樣本的網(wǎng)絡(luò)類預(yù)測和實(shí)際的目標(biāo)值間的均方距離最小。 學(xué)習(xí)率幫助避免陷入判定空間的局部最?。礄?quán)值看上去收斂，但不是最優(yōu)解），并有助于找到全局最小。如果學(xué)習(xí)率太小，學(xué)習(xí)將進(jìn)行得很慢。如果學(xué)習(xí)率太大，可能出現(xiàn)在不適當(dāng)?shù)慕庵g擺動(dòng)。一種調(diào)整規(guī)則是將學(xué)習(xí)率設(shè)置為1/t，其中t是已對訓(xùn)練樣本集迭代的次數(shù)。,22,偏倚由下式更新： j=(l)Errj j= j+ j 其中，j是偏倚j的改變。 實(shí)例更新: 每處理一個(gè)樣本就更新權(quán)值和偏倚。 周期更新: 權(quán)重和偏倚的增量累積到變量中，處理完訓(xùn) 練集中的所有樣本之后再更新權(quán)值和偏倚。其中，掃描訓(xùn)練集的一次迭代是

17、一個(gè)周期。而在實(shí)踐中，實(shí)例更新更常見。 終止條件: 1)前一周期所有的wij都小于某個(gè)指定的閾值； 2)前一周期未正確分類的樣本百分比小于某個(gè)閾值； 3)超過預(yù)先指定的周期數(shù)。 后向傳播的有效性依賴于訓(xùn)練網(wǎng)絡(luò)所用的時(shí)間。網(wǎng)絡(luò)收斂所需的時(shí)間是不確定的，存在一些加快訓(xùn)練速度的技術(shù)，例如：模擬退火技術(shù)，可確保收斂到全局最優(yōu)。,23,BP網(wǎng)絡(luò)學(xué)習(xí)算法-例題,例 通過后向傳播算法學(xué)習(xí)的樣本計(jì)算。圖 1 給出了一個(gè)多層前饋神經(jīng)網(wǎng)絡(luò)。設(shè)學(xué)習(xí)率為 0.9。該網(wǎng)絡(luò)的初始權(quán)重和偏移值由以下表給出，第一個(gè)訓(xùn)練元組為 X = 1,0,1（其類標(biāo)號為 1）。,24,網(wǎng)絡(luò)的初始權(quán)重和偏倚值在表1中給出。 給定第一個(gè)訓(xùn)練元

18、組X，該例展示向后傳播計(jì)算。首先把該元組提供給網(wǎng)絡(luò)，計(jì)算每個(gè)單元的凈輸入和輸出，其值顯示在表2中。 計(jì)算每個(gè)單元的誤差，并向后傳播，誤差值顯示在表3中。 權(quán)重和偏倚的更新顯示在表4中。 為了對未知元組X分類，把該元組輸入到訓(xùn)練過的網(wǎng)絡(luò)，計(jì)算每個(gè)單元的凈輸入和輸出（不需要計(jì)算誤差和/或它們的后向傳播）。如果每個(gè)類有一個(gè)輸出結(jié)點(diǎn)，則具有最高輸出值的結(jié)點(diǎn)決定X的預(yù)測類標(biāo)號，如果只有一個(gè)輸出結(jié)點(diǎn)，則輸出值大于或等于0.5可以視為正類，而值小于0.5可以視為負(fù)類。,25,26,27,9.2.4 黑盒內(nèi)部：后向傳播和可解釋性,神經(jīng)網(wǎng)絡(luò)就像一個(gè)黑盒。其缺點(diǎn)是知識表示。用加權(quán)鏈連接單元的網(wǎng)絡(luò)表示的知識讓人很難

19、理解。這激發(fā)了提取隱藏在訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)中的知識及象征性地表示這些知識的研究。解決方法：由網(wǎng)絡(luò)提取規(guī)則和靈敏度分析。 網(wǎng)絡(luò)提取規(guī)則： 第一步，網(wǎng)絡(luò)剪枝，可簡化網(wǎng)絡(luò)結(jié)構(gòu)，剪去對訓(xùn)練后的網(wǎng)絡(luò)影響最小的加權(quán)鏈。 第二步，通過進(jìn)行鏈、單元或活化值的聚類在網(wǎng)絡(luò)中提取規(guī)則，以得到表達(dá)明確的分類規(guī)則。 靈敏度分析：用于評估一個(gè)給定的輸入變量對網(wǎng)絡(luò)輸出的影響。改變該變量的輸入，而其它輸入變量值固定。期間，監(jiān)測網(wǎng)絡(luò)輸出的改變。,28,在一種方法中，對訓(xùn)練過的兩層神經(jīng)網(wǎng)絡(luò)中的每個(gè)隱藏單元，使用聚類發(fā)現(xiàn)公共活化值集合。對每個(gè)隱藏單元分析這些活化值得組合。導(dǎo)出涉及這些活化值和對應(yīng)的輸出單元值組合規(guī)則。類似地，研究輸入

20、值和活化值的集合，導(dǎo)出描述輸入和隱藏單元聯(lián)系的規(guī)則。最后將兩個(gè)規(guī)則集合可以結(jié)合在一起。形成IF-THEN規(guī)則。,BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的MATLAB實(shí)現(xiàn),例 下表為某藥品的銷售情況，現(xiàn)構(gòu)建一個(gè)如下的三層BP神經(jīng)網(wǎng)絡(luò)對藥品的銷售進(jìn)行預(yù)測：輸入層有3個(gè)結(jié)點(diǎn)，隱含層5個(gè)結(jié)點(diǎn)，隱含層的激活函數(shù)為tansig；輸出層結(jié)點(diǎn)數(shù)為1個(gè)，輸出層的激活函數(shù)為logsig，并利用此網(wǎng)絡(luò)對藥品的銷售量進(jìn)行預(yù)測，預(yù)測方法采用滾動(dòng)預(yù)測方式，即用前三個(gè)月的銷售量來預(yù)測第四個(gè)月的銷售量，如用1、2、3月的銷售量為輸入預(yù)測第4個(gè)月的銷售量，用2、3、4月的銷售量為輸入預(yù)測第5個(gè)月的銷售量.如此反復(fù)直至滿足預(yù)測精度要求為止。,源程序：,%以每三個(gè)月的銷售量經(jīng)規(guī)格化處理后作為輸入 %歸一化方法：P=(X-min(X(:)/(max(X(:)-min(X(:) P=0.5152 0.8173 1.0000 ; 0.8173 1.0000 0.7308; 1.0000 0.7308 0.1390; 0.7308 0.1390 0.1087; 0.1390 0.1087 0.3520; 0.1087 0.3520 0.0000; %以第四個(gè)月的銷售量歸一化處理后作為目標(biāo)向量 T=0.7308 0.1390 0.1087 0.3520 0.0000 0.3761; %創(chuàng)建一個(gè)BP神經(jīng)網(wǎng)絡(luò)，每一個(gè)輸入