ch7_4_數(shù)據(jù)挖掘算法--神經(jīng)網(wǎng)絡

1、人工神經(jīng)網(wǎng)絡（Artificial Neural Network，簡稱ANN）是指由簡單計算單元組成的廣泛并行互聯(lián)的網(wǎng)絡，能夠模擬生物神經(jīng)系統(tǒng)的結構和功能。 組成神經(jīng)網(wǎng)絡的單個神經(jīng)元的結構簡單，功能有限，但是，由大量神經(jīng)元構成的網(wǎng)絡系統(tǒng)可以實現(xiàn)強大的功能。 人工神經(jīng)網(wǎng)絡在模式識別、計算機視覺、智能控制、信號處理、語音識別、知識處理、機器學習、數(shù)據(jù)挖掘等領域有著廣泛的應用前景。,第七章 數(shù)據(jù)挖掘算法人工神經(jīng)網(wǎng)絡,最早的形式化神經(jīng)元數(shù)學模型是M-P模型，由美國心理學家McCulloch和數(shù)理邏輯學家Pitts合作于1943年提出。 1949年，心理學家Hebb提出Hebb學習規(guī)則。 1958年，計

2、算機科學家Rosenblatt提出感知器(Perception)的概念，掀起人工神經(jīng)網(wǎng)絡研究的第一次高潮。 1982年，美國加州工學院的生物物理學家Hopfield提出Hopfield網(wǎng)絡模型，這標志著神經(jīng)網(wǎng)絡研究高潮的再次興起。,神經(jīng)網(wǎng)絡由許多基本單元構成，這些基本單元模仿了人腦的神經(jīng)元。 如果將多個基本單元以適當?shù)姆绞竭B接起來，就構成了神經(jīng)網(wǎng)絡。基本單元之間的連接相當于人腦中神經(jīng)元的連接?；締卧g的連接方式有多種，從而形成了多種神經(jīng)網(wǎng)絡。 神經(jīng)網(wǎng)絡可以模仿人的頭腦，通過向一個訓練數(shù)據(jù)集學習和應用所學知識來生成分類和預測的模式。 在數(shù)據(jù)沒有任何明顯模式的情況下，這種方法很有效。,神經(jīng)網(wǎng)絡

3、,使用神經(jīng)網(wǎng)絡模型近似多變量函數(shù)，如 此處，函數(shù)f()是未知的。Xi代表輸入變量，wi代表系數(shù)。,如果至少有兩個變量輸入為1，那么輸出y的結果就是1。,人工神經(jīng)元是對生物神經(jīng)元的抽象與模擬。1943年，心理學家麥克洛奇（WMcMulloch）和數(shù)理邏輯學家皮茨（ W Pitts）根據(jù)生物神經(jīng)元的功能和結構，提出了一個將神經(jīng)元看作二進制閾值元件的簡單模型，即M-P模型，如圖所示。,人工神經(jīng)元網(wǎng)絡模型,在圖中，x1，x2，xn表示某一神經(jīng)元的n個輸入；i表示第i個輸入的連接強度，稱為連接權值，正數(shù)權值表示興奮性輸入，負數(shù)權值表示抑制性輸入；為神經(jīng)元興奮時的閾值，當神經(jīng)元輸入的加權和大于時，神經(jīng)元處

4、于興奮狀態(tài)；y為神經(jīng)元的輸出。可以看出，人工神經(jīng)元是一個具有多輸入，單輸出的非線性器件。,M-P神經(jīng)元模型的輸入是 i* xi (i=1,2,n) 輸出是 y=f()=f(i*xi ) 其中f 稱之為神經(jīng)元功能函數(shù)或作用函數(shù)。,Y=sign(0.3x1+0.3x2+0.3x3-0.4) 其中，,常用的人工神經(jīng)元模型功能函數(shù)f是表示神經(jīng)元輸入與輸出之間關系的函數(shù)，根據(jù)功能函數(shù)的不同，可以得到不同的神經(jīng)元模型。常用的神經(jīng)元模型有以下幾種。 （1）閾值型（Threshold）這種模型的神經(jīng)元沒有內部狀態(tài)，作用函數(shù)f是一個階躍函數(shù)，它表示激活值和其輸出f()之間的關系，如圖所示。,閾值型神經(jīng)元是一種最

5、簡單的人工神經(jīng)元，也就是我們前面提到的M-P模型。這種二值型神經(jīng)元，其輸出狀態(tài)取值1或0，分別代表神經(jīng)元的興奮和抑制狀態(tài)。某一時刻，神經(jīng)元的狀態(tài)由功能函數(shù)f 來決定。 當激活值0時，即神經(jīng)元輸入的加權總和超過給定的閾值時，該神經(jīng)元被激活，進入興奮狀態(tài)，其狀態(tài)f()為1； 否則，當激活值0時，即神經(jīng)元輸入的加權總和不超過給定的閾值時，該神經(jīng)元不被激活，其狀態(tài)f()為0。,（2）分段線性強飽和型（Linear Saturation） 這種模型又稱為偽線性，其輸入輸出之間在一定范圍內滿足線性關系，一直延續(xù)到輸出為最大值1為止。但當達到最大值后，輸出就不再增大。如圖所示。,（3）S型（Sibmoid）

6、這是一種連續(xù)的神經(jīng)元模型，其輸出函數(shù)也是一個有最大輸出值的非線性函數(shù)，其輸出值是在某個范圍內連續(xù)取值的，輸入輸出特性常用指數(shù)、對數(shù)或雙曲正切等S型函數(shù)表示。它反映的是神經(jīng)元的飽和特性，如圖所示。,（4）子閾累積型（Subthreshold Summation）這種類型的作用函數(shù)也是一個非線性函數(shù)，當產(chǎn)生的激活值超過T值時，該神經(jīng)元被激活產(chǎn)生一個反響。在線性范圍內，系統(tǒng)的反響是線性的，如圖所示。,神經(jīng)元模型的六個基本特征： 1）神經(jīng)元及其聯(lián)接； 2）神經(jīng)元之間的聯(lián)接強度決定信號傳遞的強弱； 3）神經(jīng)元之間的聯(lián)接強度是可以隨訓練改變的； 4）信號可以是起刺激作用的，也可以是起抑制作用的； 5）一個

7、神經(jīng)元接受的信號的累積效果決定該神經(jīng)元的狀態(tài)； 6) 每個神經(jīng)元可以有一個“閾值”。,圖 一個典型的三層神經(jīng)網(wǎng)絡結構,人工神經(jīng)網(wǎng)絡的學習方式,死記式學習：網(wǎng)絡連接權值根據(jù)特殊記憶模式設計而成，其值不變。在網(wǎng)絡輸入相關模式時，喚起對記憶模式的回憶，對輸入模式進行相應處理。 有監(jiān)督學習：網(wǎng)絡將實際輸出和教師指定的輸出加以比較，得到在一定范數(shù)意義下的誤差，由誤差函數(shù)決定連接權值的調整，目的是使誤差函數(shù)達到最小值。 無監(jiān)督學習：網(wǎng)絡的學習是自我調整的過程，不存在教師示教來指示網(wǎng)絡輸出是否正確。 有監(jiān)督與無監(jiān)督的混合學習：混合學習過程首先采用無監(jiān)督學習抽取輸入模式的特征，然后利用有監(jiān)督學習方式對其進行處

8、理，形成輸入輸出的某種映射。,多層前饋神經(jīng)網(wǎng)絡,最流行的神經(jīng)網(wǎng)絡算法是20世紀80年代提出的后向傳播算法。 這種算法是在多層前饋神經(jīng)網(wǎng)絡基礎上運行的。,前饋神經(jīng)網(wǎng)絡是分層網(wǎng)絡模型，具有一個輸入層、一個輸出層，輸入層和輸出層之間有一個或多個隱藏層。每個層具有若干個單元，前一層單元與后一層單元之間通過有向加權邊相連。,輸入層 節(jié)點的數(shù)據(jù)與訓練樣本的非類別屬性數(shù)目對應，通常一個連續(xù)屬性對應一個輸入層單元，一個p值離散屬性對應p個輸入層單元； 輸出層 節(jié)點的數(shù)據(jù)與訓練樣本的類別數(shù)目對應； 隱藏層 層數(shù)及隱藏層節(jié)點的數(shù)目目前尚無理論指導，憑經(jīng)驗選取。 但是，至今也沒有一個明確的理論來指導我們如何確定每個

9、隱含層的節(jié)點數(shù)和網(wǎng)絡的層數(shù)。在實踐中通常用試錯法。,紅,紫,綠,圓,長,番茄,茄子,黃瓜,一個隱藏或輸出單元j: j的輸入是來自前一層的輸出；這些輸出與對應的權相乘，形成加權和；加權和加到與單元j相連的閾值（偏置）上；一個非線性的激活函數(shù)作用于凈輸入,在實踐中發(fā)現(xiàn)logistic函數(shù)（s形函數(shù)） 效果最好。,Output nodes,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,BP網(wǎng)絡,BP算法是目前應用最廣泛的一種人工神經(jīng)網(wǎng)絡模型。 1986年，Rumelhart和 McCelland提出了誤差后向傳播（Error

10、Back Propagation）算法，通常稱為后向傳播或反向傳播算法，簡稱BP算法，標志著BP算法的產(chǎn)生， 成功地解決了多層網(wǎng)絡中隱含層神經(jīng)元連接權值的學習問題。 基本的BP算法采用有監(jiān)督學習方式，基于梯度下降算法，極小化誤差函數(shù)。其主要思想是將學習過程分為信號正向傳播過程和誤差后向傳播過程兩個階段。,BP神經(jīng)網(wǎng)絡是一種具有三層或三層以上結構的神經(jīng)網(wǎng)絡，包括輸入層、隱層和輸出層。層與層之間多采用全互連方式，但同一層的節(jié)點之間不存在相互連接。,圖 BP神經(jīng)網(wǎng)絡模型,BP網(wǎng)絡的各層之間具有不同的功能： 輸入層節(jié)點上的神經(jīng)元接受外部環(huán)境的輸入模式，并由它傳遞給相連隱層上的各個神經(jīng)元。 隱層是神經(jīng)元

11、網(wǎng)絡的內部處理層，這些神經(jīng)元在網(wǎng)絡內部構成中間層，由于它們不直接與外部輸入、輸出打交道，故稱隱層。人工神經(jīng)網(wǎng)絡所具有的模式變換能力主要體現(xiàn)在隱層的神經(jīng)元上。 輸出層用于產(chǎn)生神經(jīng)網(wǎng)絡的輸出模式。,向后傳播方法 通過迭代地處理一組訓練樣本，將每個樣本的網(wǎng)絡預測與實際指導的類標號比較，進行學習。對于每個訓練樣本，修改權，使得網(wǎng)絡預測和實際類之間的均方誤差最小。這種修改“后向”進行。即由輸出層，經(jīng)由每個隱藏層，到第一個隱藏層。一般地，權將最終收斂，學習過程停止。 反向傳播算法的速度使得神經(jīng)網(wǎng)絡成為一個實際的工具，正是因為反向傳播算法的有效性，才使得80年代中期，對神經(jīng)網(wǎng)絡的強烈興趣復蘇。,BP神經(jīng)網(wǎng)絡

12、是對人類神經(jīng)系統(tǒng)的一種模擬。盡管人類神經(jīng)系統(tǒng)規(guī)模宏大、結構復雜、功能神奇，但其最基本的處理單元卻只有神經(jīng)元。BP神經(jīng)系統(tǒng)的功能實際上是通過大量神經(jīng)元的廣泛互連，以規(guī)模宏偉的并行運算來實現(xiàn)的。,相關概念,設(Xp, Tp) 表示輸入樣本，p1, 2, N，N為輸入樣本的個數(shù)。W表示網(wǎng)絡權向量。 誤差函數(shù)：E (W)=g ( f (W, Xp, Tp) )，E稱為誤差（測度）函數(shù)。用誤差函數(shù)來判別網(wǎng)絡的實際輸出向量Yp與教師信號向量Tp的誤差。常采用二乘誤差函數(shù)加以判別（m為輸出向量的維數(shù)）：,映射：對于給定的一組數(shù)據(jù)(Xp, Tp)，神經(jīng)網(wǎng)絡通過一組特定的權值W，實現(xiàn)一定精度的映射。訓練目的是希

13、望得到的權值能產(chǎn)生最小的誤差和最好的精度。從XpRn到TpRm的映射記為： f : XpRnTpRm 誤差曲面：若隱層與輸出層間的權值數(shù)目記為mn2，對于給定的訓練樣本(Xp, Tp)，網(wǎng)絡權向量W(W1, W2, Wmn2)，通過誤差函數(shù)E(W)計算出來的映射誤差可描述為mn2+1空間的一個曲面，稱為誤差曲面。不同的E (W)對應不同的誤差曲面形狀。,網(wǎng)絡學習：是指按照某種學習規(guī)則選取新的W，使E(W)E(W)，即使E(W)對應的誤差曲面上的點總是向山下移動，最終移到最深的谷底（全局最小）。若曲面有多個谷底，移動的過程可能陷入局部極小。 移動步長：也稱學習率，步長較小時移動軌跡較慢且平滑，易

14、陷入局部極??；步長較大時移動速度快，可能跳過局部極小，也可能跳過全局最小點，易產(chǎn)生振蕩。一般情況下，開始時取較大步長，后期取較小步長。 梯度下降算法：如果移動是在誤差曲面最陡的方向，或梯度下降的方向上進行，這樣下山的速度快，稱作最速梯度下降法。,BP算法權值的修正量,BP算法基于梯度下降算法。在梯度下降算法中，權值的修正量正比于誤差函數(shù)E(W)對W的負梯度，即： W (t+1)= W (t) +W (t),BP學習原理,工作信號正向傳播/前向傳播 誤差信號反向傳播/后向傳播,正向傳播：當給定網(wǎng)絡一組輸入模式時，BP網(wǎng)絡將依次對這組輸入模式中的每個輸入模式按如下方式進行學習：把輸入模式從輸入層傳

15、到隱含層單元，經(jīng)隱含層單元逐層處理后，產(chǎn)生一個輸出模式傳至輸出層，這一過程稱為正向傳播。 反向傳播：如果經(jīng)正向傳播在輸出層沒有得到所期望的輸出模式，則轉為誤差反向傳播過程，即把誤差信號沿原連接路徑返回，并通過修改各層神經(jīng)元的連接權值，使誤差信號為最小。 重復正向傳播和反向傳播過程，直至得到所期望的輸出模式為止。,Output nodes,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,信號正向傳播,反向傳播求誤差,Output nodes,Input nodes,Hidden nodes,Output vector,Inp

16、ut vector: xi,wij,通過迭代地處理一組訓練樣本，將每個樣本的網(wǎng)絡預測與實際指導的類標號比較，進行學習。對于每個訓練樣本，修改權，使得網(wǎng)絡預測和實際類之間的均方誤差最小。這種修改“后向”進行。即由輸出層，經(jīng)由每個隱藏層，到第一個隱藏層。一般地，權將最終收斂，學習過程停止。,向后傳播:,訓練的最終目的 利用訓練集獲得權重的集合，使得網(wǎng)絡能夠正確地將訓練集分類 步驟 利用隨機數(shù)初始化權重（-1.01.0，或-0.50.5） 將訓練集樣本逐一的輸入到網(wǎng)絡中 對于每一個樣本 利用單元全部輸入的線性組合和單元的偏置計算單元的凈輸入 將變換函數(shù)作用于單元的凈輸入，得到單元輸出。 計算誤差 修

17、改權重和偏置值,更新方法： 實例更新：每處理一個樣本就更新權和偏置。 周期更新：權和偏置的增量也可以累積到變量中，使得可以在處理完訓練集中的所有樣本之后再更新權和偏置。 終止條件： 前一周期所有的wij的變化量都很小，小于某個指定的閾值 前一周期未正確分類的樣本百分比小于某個閾值 超過預先指定的周期數(shù) 實踐中，權收斂可能需要數(shù)十萬個周期。,BP網(wǎng)絡的學習算法思想： 初始化網(wǎng)絡及學習參數(shù)，即將隱含層和輸出層各節(jié)點的連接權值、神經(jīng)元閾值賦予1，1區(qū)間的一個隨機數(shù)。 提供訓練模式，即從訓練模式集合中選出一個訓練模式，將其輸入模式和期望輸出送入網(wǎng)絡。 正向傳播過程，即對給定的輸入模式，從第一隱含層開始

18、，計算網(wǎng)絡的輸出模式，并把得到的輸出模式與期望模式比較，若有誤差，則執(zhí)行第（4）步；否則，返回第（2）步，提供下一個訓練模式； 反向傳播過程，即從輸出層反向計算到第一隱含層，逐層修正各單元的連接權值。 返回第（2）步，對訓練模式集中的每一個訓練模式重復第（2）到第（3）步，直到訓練模式集中的每一個訓練模式都滿足期望輸出為止。,在BP算法學習過程中，對于每一個輸入樣本逐次修正權值向量，若有N個輸入樣本，一次學習過程將對權值向量修正N次。這種逐次不斷修正權值向量的方法稱為逐次修正法。 BP算法學習過程：確定和選擇網(wǎng)絡結構，包括確定輸入層和輸出層的節(jié)點數(shù)，選擇隱層數(shù)和各隱層內的節(jié)點數(shù)。確定節(jié)點的轉移

19、函數(shù)、誤差函數(shù)類型，并選擇各個可調參數(shù)值。,訓練樣本x=1,0,1 類標號為1,實例1,本例只有一個訓練樣本，只示例了網(wǎng)絡學習過程中的一次迭代過程。,神經(jīng)網(wǎng)絡的學習過程雖然漫長，但分類速度卻很快。學習結束后，網(wǎng)絡得到一組固定的權值及偏值。未知類別的樣本到來后，將其屬性送入輸入層各節(jié)點，從輸入層到輸出層正向傳播，計算輸出層各單元的值，輸出值最大的單元所代表的類就是該樣本所屬的類別。,實例2,通過實例歸納算法的基本流程,假設某汽車銷售公司希望對購買不同檔次汽車的客戶進行分類，分類的依據(jù)是客戶的年齡、收入和學歷。公司希望通過這三個分類標準，推斷出客戶會購買哪種檔次的汽車。,年齡劃分成四檔：30歲以下

20、，31-40歲， 41-50歲，50歲以上。 收入劃分成四檔：1500元以下，1501-2500元， 2501-3500元，3500元以上。 學歷也劃分成四檔：大學及大學以上，大專， 高中及中專，初中及初中以下。 車的檔次分為兩檔：高檔和低檔。,1、輸入數(shù)據(jù)的預處理 輸入到神經(jīng)網(wǎng)絡中的數(shù)據(jù)必須是在0，1閉區(qū)間內的數(shù)字，所以需要用0，1上的數(shù)字形式來表示分類數(shù)據(jù)。 30歲以下用0，0表示，31-40歲用0，1表示，41-50歲用1，0表示，50歲以上用1，1表示。 1500元以下用0，0表示，1501-2500元用0，1表示，2501-3500元用1，0表示，3500元以上用1，1表示。 大學及

21、大學以上用0，0表示，大專用0，1表示，高中及中專用1，0表示，初中及初中以下用1，1表示。,實現(xiàn)步驟：,2、確定網(wǎng)絡拓撲圖 1） 輸入數(shù)據(jù)有三個：年齡、收入和學歷。,2） 設網(wǎng)絡中只有一個隱層，而且隱層中包含兩個結點。,3 ）輸出層中有一個輸出結點。若輸出值為1，則表示購買高檔車，若輸出值為0，則表示購買低檔車。,3、BP算法的具體流程,（1）權重閾值初始化,一般初始化權重的范圍在一個較小的區(qū)間內，如-1.0，1.0或-0.5，0.5。,結點的初始閾值,結點的初始權重,（2）正向傳播 計算各個層次的每個結點的輸入及輸出情況。 輸入層：對于輸入層中的結點i來說，其輸出值等于輸入值，即Oi=Ii

22、。 設有一個樣本是：年齡在41-50歲之間，收入在3500元以上，學歷是大學水平，已知的輸出是它會購買高檔汽車。此樣本的輸入為：,期望的輸出是：1。 隱層、輸出層：每個結點的輸入都與上一層的輸出有關，是上一層的輸出與相應權值的復合。 其中，Wij表示從上一層的結點i到當前層中的結點j的連接權重。Oi表示i結點的輸出，j表示結點j的閾值。,根據(jù)公式計算得到(隱層的輸入) ： I7=0.25*1+0.1*0+0.2*1+0.3*1+0.4*0+0.5*0-0.1=0.65 I8=-0.2*1-0.1*0-0.15*1+0.2*1+0.3*0+0.1*0-0.5=0.2,對于結點j，若給定其輸入為I

23、j，則其輸出為,根據(jù)公式計算得到：,I9=0.15*0.657+0.05*0.55-(-0.2)=0.326,（3）反向傳播 反向傳播過程實際上是一個誤差反向傳播修正的過程。在這個過程中，根據(jù)輸出層的實際輸出和期望輸出之間的誤差，修改權重及相應的閾值以減少網(wǎng)絡預測中存在的誤差。,對于輸出層誤差的計算公式： Errj=f(Ij) (Tj-Oj) 其中，Ij表示j結點的輸入， Tj表示目標輸出， Oj表示j結點的實際輸出，f(Ij)是S型函數(shù)的一階導數(shù)。 S型函數(shù)在Ij的導數(shù)可以方便地計算為Oj (1-Oj)。 Errj= Oj (1-Oj) (Tj-Oj),對于隱層誤差的計算公式為：,權值的修正

24、公式為： wij=ErrjOi wij=wij+wij 閾值的修正公式為： j=Errj j=j+j 其中，01，表示學習率。在BP網(wǎng)絡的收斂過程中，一個明顯的缺點就是容易導致局部最優(yōu)解，而的作用就是避免BP網(wǎng)絡的局部最優(yōu)解問題。,根據(jù)公式計算得到： Err9= O9 (1-O9)(T9-O9) =0.581*(1-0.581)*(1-0.581)=0.102 Err7=O7(1-O7)*Err9*W79 =0.657*(1-0.657)*0.102*0.15=0.0035 Err8=O8(1-O8)*Err9*W89 =0.55*(1-0.55)*0.102*0.05=0.0013,Errj

25、= Oj (1-Oj) (Tj-Oj),設=0.5，則對權值的修正為： W17=Err7O1=0.5*0.0035*1=0.0018 W27 =0.5*0.0035*0=0 W37 =0.5*0.0035*1=0.0018 W47 =0.5*0.0035*1=0.0018 W57 =0.5*0.0035*0=0 W67 =0.5*0.0035*0=0,wij=ErrjOi,wij=wij+wij,W17=W17+W17=0.25+0.0018=0.2518 W27= 0.1+0=0.1 W37= 0.2+0.0018=0.2018 W47= 0.3+0.0018=0.3018 W57= 0.4+0=0.4 W67= 0.5+0=0.5,wij=ErrjOi,