投影尋蹤方法及其應用.ppt

投影尋蹤方法及其應用 金 菊 良 合肥工業(yè)大學土木建筑工程學院水利系 (郵編 230009，電話JINJL66126.com),報告內容,1 投影尋蹤方法的基本原理與建模步驟,4 總結與討論,3 基于加速遺傳算法的投影尋蹤等級評價模型,2 基于加速遺傳算法的投影尋蹤聚類模型,1 投影尋蹤方法的基本原理與建模型步驟,1.1 投影尋蹤方法的基本原理 投影尋蹤(projection pursuit，PP)方法屬于直接由樣本數(shù)據(jù)驅動的探索性數(shù)據(jù)分析方法。它把高維數(shù)據(jù)x(i,j)通過某種組合投影到低維子空間上z(i)，對于投影到的構形，采用投影指標函數(shù)Q(z(i)來描述投影暴露原系統(tǒng)某種分類排序結構的可能性大小，尋找出使投影指標函數(shù)達到最優(yōu)（即能反映高維數(shù)據(jù)結構或特征）的投影值z(i)，然后根據(jù)該投影值來分析高維數(shù)據(jù)的分類結構特征（如投影尋蹤聚類評價模型），或根據(jù)該投影值與研究系統(tǒng)的實際輸出值之間的散點圖構造適當?shù)臄?shù)學模型以模擬系統(tǒng)輸出（如投影尋蹤等級評價模型）。,1 投影尋蹤方法的基本原理與建模步驟,1.2 投影尋蹤方法的建模步驟 步驟1：高維樣本數(shù)據(jù)的預處理，確定系統(tǒng)輸入。 步驟2：構造投影指標函數(shù)。 步驟3：優(yōu)化投影指標函數(shù)。 步驟4：建立系統(tǒng)模型。,2 基于加速遺傳算法的投影尋蹤聚類模型AGA-PPCE,2.1 基于加速遺傳算法的投影尋蹤聚類模型的建立 步驟1：評價指標值的歸一化處理。設樣本集為x*(i,j)| i =1n, j=1p。其中x*(i,j)為第i個樣本第j個指標值。為消除各指標值的量綱和統(tǒng)一各指標值的變化范圍，可采用下式進行極值歸一化處理：,式中，xmin(j)、xmax(j)分別為樣本集中第j個指標值的最小值和最大值。,2 基于加速遺傳算法的投影尋蹤聚類模型AGA-PPCE,2.1 基于加速遺傳算法的投影尋蹤聚類模型的建立 步驟2：構造投影指標函數(shù)。PP方法就是把p維數(shù)據(jù)x(i,j)| j=1p綜合成以a=(a(1),a(2), ,a(p)為投影方向的一維投影值z(i),然后根據(jù)z(i)| i=1n 的一維散布圖進行分類。式(2.2)中a為單位長度向量。在綜合投影值時，要求投影值z(i)的散布特征應為：局部投影點盡可能密集，最好凝聚成若干個點團；而在整體上投影點團之間盡可能散開。據(jù)此投影指標函數(shù)可構造為 Q(a)= Sz Dz (2.3) 式中，Sz為投影值z(i)的標準差，Dz為投影值z(i)的局部密度，即,2 基于加速遺傳算法的投影尋蹤聚類模型AGA-PPCE,2.1 基于加速遺傳算法的投影尋蹤聚類模型的建立 步驟3：優(yōu)化投影指標函數(shù)。當各指標值的樣本集給定時，投影指標函數(shù)Q(a)只隨投影方向a的變化而變化?？赏ㄟ^求解投影指標函數(shù)最大化問題來估計最大可能暴露高維數(shù)據(jù)某類特征結構的最佳投影方向 ： max Q(a)= Sz Dz (2.4),這是一個以a(j)|j=1p為優(yōu)化變量的復雜非線性優(yōu)化問題，用模擬生物優(yōu)勝劣汰規(guī)則與群體內部染色體信息交換機制的加速遺傳算法（AGA）來求解上述問題較為簡便和有效。,加速遺傳算法（AGA） 步驟1：模型參數(shù)的編碼。設碼長為e，第j個參數(shù)的變化區(qū)間為aj，bj，j=1p。把這些區(qū)間等分成2e-1個子區(qū)間： cj=aj+Ijdj (2) 式中子區(qū)間長度dj=(bj-aj)/(2e-1)是常數(shù)；搜索步數(shù)Ij為小于2e的十進制整數(shù)，是變數(shù)；j=1p(下同)。把Ij轉化成e位二進制數(shù)ia(j, k)，k=1e(下同)，即式(3) ：,步驟2：初始父代群體的隨機生成。 生成n組各p個均勻隨機數(shù)(簡稱隨機數(shù))u(j,i)，i=1n，經(jīng)下式轉換成十進制整數(shù)。 Ij(i)=INTu(j,i)2e (4) 式中INT為取整函數(shù)。由式(3)得對應二進制數(shù)ia(j,k,i)，它們與n組模型參數(shù)cj(i)對應，并把它們作為初始父代個體群。 編碼與解碼的邏輯過程：cj(i) Ij(i) ia(j, k,i),步驟3：父代個體適應能力評價。 把第i組參數(shù)代入式(1)得目標函數(shù)值fi，fi越小表示模型與觀測值擬合得越好，適應能力越強，設第i個個體的適應能力與fi成反比。 構造選擇概率序列pi，把0，1區(qū)間分成n個子區(qū)間：(0，p1)，(p1，p2)，pn-1，pn，它們與n個個體一一對應，fi越小的個體對應的子區(qū)間長度越大。,步驟4：父代個體的概率選擇。 生成n個隨機數(shù) ui |i=1n，若 uipi-1，pi， 則選取第i個父代個體，其二進制數(shù)記為ia1(j,k,i)。同理可得另外的n個父代個體ia2(j,k,i)。選擇是遺傳算法的關鍵，它體現(xiàn)了優(yōu)勝劣汰的思想。,步驟5：父代個體的雜交。 由步4得到的父代個體配對成n對雙親。生成兩隨機數(shù)u1和u2，再轉成十進制整數(shù)：IU1=INT(1+u1e)，IU2=INT(1+u2e)，設IU1IU2（否則互換其值）。雜交是指第i對雙親ia1(j,k,i)和ia2(j,k,i)隨機變換一段二進制數(shù)，從而生成第i對子代個體： 0 1 1 0 10 0 1 0 1 (5) 1 0 1 0 01 1 1 0 0 (6) (雜交前) (雜交后),步驟6：子代個體的變異。 生成隨機數(shù)u1，u2，u3和u4。當u10.5時子代個體取式(5)，否則取式(6)，記其二進制數(shù)為ia(j, k,i) 。把u2、u3轉換為十進制整數(shù)： IU1=INT(1+eu2)，IU2=INT(1+eu3) 設子代變異的概率(稱為變異率)為pm。變異是當u4pm時對子代個體的IU1位和IU2位的值進行翻轉操作： 0 1 1 0 10 0 1 1 1 (變異前) (變異后),步驟7：進化迭代。 第i個子代個體經(jīng)式(3)、式(2)轉化成第i組模型參數(shù)。這n個子代個體作為新的父代，算法轉入步3，進入下一輪進化過程，重新評價、選擇、雜交、變異，如此反復進化，使個體的適應能力不斷提高，直到最優(yōu)個體的優(yōu)化準則值小于某一指定值或最優(yōu)個體的優(yōu)化準則值不再改善，則終止進化迭代，算法結束。,(a)初始分布 (b)第20次進化迭代后的分布 (c)第60次進化迭代后的分布,步驟8：加速循環(huán)。 用第一次、第二次進化迭代所產(chǎn)生的優(yōu)秀個體的變量變化區(qū)間作為變量新的初始變化區(qū)間，算法進入步驟1，重新運行SGA算法，如此加速循環(huán)，優(yōu)秀個體的變化區(qū)間將逐步調整和收縮，與最優(yōu)點的距離將越來越近，直到最優(yōu)個體的優(yōu)化準則函數(shù)值小于某一設定值或算法運行達到預定加速(循環(huán))次數(shù)，結束整個算法的運行。此時，就把當前群體中最佳個體或優(yōu)秀個體的平均值指定為AGA的結果。,AGA的主要特點 利用標準遺傳算法演化過程中的優(yōu)秀個體子群體來逐步調整、壓縮算法的搜索空間。 控制參數(shù)設置：二進制編碼長度e、雜交概率和變異率分別固定設置為10、1.0和1.0；群體規(guī)模n與優(yōu)秀個體數(shù)目s關系：s/nn/(e2e)，(n,s)的常用配置有(300,10)、(400,20)和(500,30)；每次加速循環(huán)中AGA只進行兩次SGA的進化迭代。 p個變量、加速循環(huán)q次，優(yōu)秀個體包圍最優(yōu)點的概率為(1-0.52s)pq,步驟4：建立聚類模型。把由步驟3求得的最佳投影方向a*代入式(2.2)后，得各樣本點的投影值z*(i)。投影值z*(i) 與z*(j)越接近，表示樣本i與樣本j越傾向于分為同一類。按z*(i)值從大到小排序，據(jù)此可把各指標的樣本集進行分類。,2 基于加速遺傳算法的投影尋蹤聚類模型AGA-PPCE,2.2 基于加速遺傳算法的投影尋蹤聚類模型在氣候區(qū)劃中的應用 氣候區(qū)劃就是把研究區(qū)域劃分成若干個分區(qū)，在同一分區(qū)內具有相似的氣候條件，以便調整種植結構，因地制宜地發(fā)展農(nóng)業(yè)生產(chǎn)。 表2.1 氣候樣本集及其投影值 氣候因子j j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 j=10 樣本 年平均 極端最高 極端最低 10年 年降水 年日照 年均相對 無霜 海拔 凌凍天 投影值 氣溫/C 氣溫/C 氣溫/C 積溫/C 量/mm 數(shù)/h 濕度/% 期/d 高度/m 數(shù)/d z*(i) 1畢節(jié) 12.9 33.6 10.1 3672.0 904.3 1236.0 82 250 1510.6 15.2 1.295 2大方 11.8 31.5 8.8 3332.8 1176.9 1265.9 84 256 1700.0 33.2 1.283 3黔西 14.1 35.4 8.6 4047.4 964.1 1263.6 81 274 1272.1 14.6 1.722 4金沙 15.1 36.0 6.2 4703.3 1049.7 1091.6 81 304 920.0 7.5 2.191 5織金 14.2 33.1 9.5 4264.2 1432.6 1165.6 82 280 1319.0 11.8 1.728 6納雍 13.7 33.5 8.4 4005.6 1234.3 1447.7 81 268 1457.1 14.2 1.625 7威寧 10.4 31.1 14.5 2572.8 943.5 1960.3 80 190 2234.5 63.9 0.271 8赫章 13.4 35.7 11.6 3948.9 892.8 1400.8 79 244 1534.9 12.4 1.282,圖2.1 氣候樣本投影值z*(i)的散布圖 由表2.1和圖2.1可知：該樣本集按投影值z*(i)從大到小排序的樣本序號依次為樣本點4、5、3、6、1、2、8和7。其中，樣本4可單獨分為A類，樣本5、3、6、1、2和8可分為B類，樣本7可單獨分為C類，該分類結果與文獻“劉崇欣. 黔西北林木氣候區(qū)劃的聚類分析. 農(nóng)業(yè)系統(tǒng)科學與綜合研究,1997,13(3) ”的模糊聚類結果和根據(jù)表2.1各樣本的對比分析結果都是一致的。 B類可進一步細分為由樣本5、3和6組成的B-1類和由樣本1、2和8組成的B-2類。 根據(jù)文獻所示各樣本的地理位置可知，以上分類具有明確的地理意義：A類、B類和C類分別位于研究區(qū)域的東部、中部和西部，B-1類和B-2類分別位于研究區(qū)域的中南部和中北部。,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.1 AGA-PPGE的建立 步驟1：評價指標值的標準化處理。設樣本集為x*(i,j)| i =1n, j=1p。其中x*(i,j)為第i個樣本第j個指標值。為消除各指標值的量綱和統(tǒng)一各指標值的變化范圍，可采用下式進行標準化處理：,式中，Ex(j)、Sx(j)分別為原第j個評價指標x*(j,i)|i=1n的均值和標準差。,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.1 AGA-PPGE的建立 步驟2：構造投影指標函數(shù)。PP方法就是把p維數(shù)據(jù)x(i,j)| j=1p綜合成以a=(a(1),a(2), ,a(p)為投影方向的一維投影值z(i),式中，a為單位長度向量。在綜合投影值時，要求投影值z(i)應盡可能多地提取x(j,i)中的變異信息，即z(i)的標準差Sz達到盡可能大，同時要求z(i)與已知標準等級值y(i)的相關系數(shù)的絕對值|Rzy|達到盡可能大。為此，投影指標函數(shù)可構造為 Q(a)= Sz |Rzy| 式中，Sz和Rzy分別為,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.1 AGA-PPGE的建立 步驟3：優(yōu)化投影指標函數(shù)。當給定標準等級及其評價指標的樣本數(shù)據(jù)y(i)|i=1n和x*(j,i)|j=1p,i=1n時，投影指標函數(shù)Q(a)只隨投影方向a的變化而變化。不同的投影方向反映不同的數(shù)據(jù)結構特征，最佳投影方向就是最大可能暴露高維數(shù)據(jù)某類特征結構的投影方向?？赏ㄟ^求解投影指標函數(shù)最大化問題來估計最佳投影方向 ： max Q(a)= Sz |Rzy| 這是一個以a(j)|j=1p為優(yōu)化變量的復雜的非線性優(yōu)化問題，用AGA可方便地求解上述優(yōu)化問題。,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.1 AGA-PPGE的建立 步驟4：建立投影尋蹤等級評價模型。把由步驟3求得的最佳投影方向的估計值a*代入投影值公式后，得第i個樣本投影值的計算值z*(i)，根據(jù)z*(i)y(i)的散點圖建立相應的等級評價模型。z*(i)與y(i)之間一般呈單調非降關系，當z*(i)值超過某門限值時就判定為最高等級(N級)，當指標值低于另門限值時就判定為最低等級(1級)，當z*(i)值介于這兩門限值之間時則為中等等級，可用邏輯斯諦曲線來描述：,式中y*(i)為第i個樣本等級的計算值；模型參數(shù)c(1)、c(2) 分別為積分常數(shù)和增長率，可通過求解如下優(yōu)化問題來確定：,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.2 AGA-PPGE在洪水災情等級評價中的應用 表3.1 河南省洪水災情等級標準 災情等級指標 一般災 較大災 大災 特大災 成災面積(hm2) 283.3 直接經(jīng)濟損失(億元) 85.0 根據(jù)表3.1，可用如下方法隨機產(chǎn)生各災情指標值及其對應的標準災情等級樣本系列：四個災情等級值一般災、較大災、大災、特大災分別對應標準災情等級值1、2、3、4。 確定一般災的左端點值和特大災的右端點值，這里分別取為一般災的右端點值的0.5倍和特大災的左端點值的3倍，這樣，所有災級都有一個范圍。 利用均勻隨機數(shù)在每個災級范圍內產(chǎn)生5個值，考慮到直接經(jīng)濟損失一般與成災面積具有正相關性，同一樣本點的直接經(jīng)濟損失的隨機數(shù)應與成災面積的隨機數(shù)相同。 在災情等級標準表中取邊界值各一次，災情等級值取與該邊界值有關的兩個災級值的算術平均值。這樣得到的樣本點如表3.2序號123所示。,表3.2 洪水災情等級的標準值和PPGE模型的計算值的對比結果 序號 災情指標 投 影 洪水災情等級 序號 災情指標 投 影 洪水災情等級 i x*(1,i) x*(2,i) 值z*(i) 標準值 計算值 i x*(1,i) x*(2,i) 值z*(i) 標準值 計算值 1 38.70 7.900 -1.178 1.0 1.369 17 157.30 38.600 - 0.469 3.0 2.486 2 38.50 7.800 -1.180 1.0 1.366 18 283.30 85.000 0.422 3.5 3.498 3 32.10 6.500 -1.215 1.0 1.315 19 556.90 167.100 2.171 4.0 3.967 4 24.20 4.900 -1.257 1.0 1.256 20 649.50 194.900 2.763 4.0 3.987 5 36.40 7.400 -1.191 1.0 1.350 21 602.30 180.700 2.461 4.0 3.979 6 46.70 9.500 -1.135 1.5 1.432 22 446.50 134.000 1.466 4.0 3.897 7 97.60 21.700 -0.840 2.0 1.895 23 694.90 208.500 3.053 4.0 3.992 8 60.40 12.800 -1.056 2.0 1.552 1950 72.92 9.900 -1.042 2.0 1.574 9 112.60 25.200 -0.755 2.0 2.033 1954 148.13 20.656 -0.679 2.0 2.156 10 56.20 11.800 -1.080 2.0 1.515 1956 203.92 27.521 -0.421 3.0 2.559 11 80.60 17.600 -0.939 2.0 1.736 1957 179.10 24.858 -0.532 3.0 2.389 12 136.70 31.000 -0.615 2.5 2.258 1963 375.46 94.927 0.834 4.