投影尋蹤方法及其應(yīng)用.ppt

投影尋蹤方法及其應(yīng)用 金 菊 良 合肥工業(yè)大學土木建筑工程學院水利系 (郵編 230009，電話JINJL66126.com),報告內(nèi)容,1 投影尋蹤方法的基本原理與建模步驟,4 總結(jié)與討論,3 基于加速遺傳算法的投影尋蹤等級評價模型,2 基于加速遺傳算法的投影尋蹤聚類模型,1 投影尋蹤方法的基本原理與建模型步驟,1.1 投影尋蹤方法的基本原理 投影尋蹤(projection pursuit，PP)方法屬于直接由樣本數(shù)據(jù)驅(qū)動的探索性數(shù)據(jù)分析方法。它把高維數(shù)據(jù)x(i,j)通過某種組合投影到低維子空間上z(i)，對于投影到的構(gòu)形，采用投影指標函數(shù)Q(z(i)來描述投影暴露原系統(tǒng)某種分類排序結(jié)構(gòu)的可能性大小，尋找出使投影指標函數(shù)達到最優(yōu)（即能反映高維數(shù)據(jù)結(jié)構(gòu)或特征）的投影值z(i)，然后根據(jù)該投影值來分析高維數(shù)據(jù)的分類結(jié)構(gòu)特征（如投影尋蹤聚類評價模型），或根據(jù)該投影值與研究系統(tǒng)的實際輸出值之間的散點圖構(gòu)造適當?shù)臄?shù)學模型以模擬系統(tǒng)輸出（如投影尋蹤等級評價模型）。,1 投影尋蹤方法的基本原理與建模步驟,1.2 投影尋蹤方法的建模步驟 步驟1：高維樣本數(shù)據(jù)的預(yù)處理，確定系統(tǒng)輸入。 步驟2：構(gòu)造投影指標函數(shù)。 步驟3：優(yōu)化投影指標函數(shù)。 步驟4：建立系統(tǒng)模型。,2 基于加速遺傳算法的投影尋蹤聚類模型AGA-PPCE,2.1 基于加速遺傳算法的投影尋蹤聚類模型的建立 步驟1：評價指標值的歸一化處理。設(shè)樣本集為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：構(gòu)造投影指標函數(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)的散布特征應(yīng)為：局部投影點盡可能密集，最好凝聚成若干個點團；而在整體上投影點團之間盡可能散開。據(jù)此投影指標函數(shù)可構(gòu)造為 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ù)某類特征結(jié)構(gòu)的最佳投影方向 ： max Q(a)= Sz Dz (2.4),這是一個以a(j)|j=1p為優(yōu)化變量的復雜非線性優(yōu)化問題，用模擬生物優(yōu)勝劣汰規(guī)則與群體內(nèi)部染色體信息交換機制的加速遺傳算法（AGA）來求解上述問題較為簡便和有效。,加速遺傳算法（AGA） 步驟1：模型參數(shù)的編碼。設(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轉(zhuǎn)化成e位二進制數(shù)ia(j, k)，k=1e(下同)，即式(3) ：,步驟2：初始父代群體的隨機生成。 生成n組各p個均勻隨機數(shù)(簡稱隨機數(shù))u(j,i)，i=1n，經(jīng)下式轉(zhuǎn)換成十進制整數(shù)。 Ij(i)=INTu(j,i)2e (4) 式中INT為取整函數(shù)。由式(3)得對應(yīng)二進制數(shù)ia(j,k,i)，它們與n組模型參數(shù)cj(i)對應(yīng)，并把它們作為初始父代個體群。 編碼與解碼的邏輯過程：cj(i) Ij(i) ia(j, k,i),步驟3：父代個體適應(yīng)能力評價。 把第i組參數(shù)代入式(1)得目標函數(shù)值fi，fi越小表示模型與觀測值擬合得越好，適應(yīng)能力越強，設(shè)第i個個體的適應(yīng)能力與fi成反比。 構(gòu)造選擇概率序列pi，把0，1區(qū)間分成n個子區(qū)間：(0，p1)，(p1，p2)，pn-1，pn，它們與n個個體一一對應(yīng)，fi越小的個體對應(yīng)的子區(qū)間長度越大。,步驟4：父代個體的概率選擇。 生成n個隨機數(shù) ui |i=1n，若 uipi-1，pi， 則選取第i個父代個體，其二進制數(shù)記為ia1(j,k,i)。同理可得另外的n個父代個體ia2(j,k,i)。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了優(yōu)勝劣汰的思想。,步驟5：父代個體的雜交。 由步4得到的父代個體配對成n對雙親。生成兩隨機數(shù)u1和u2，再轉(zhuǎn)成十進制整數(shù)：IU1=INT(1+u1e)，IU2=INT(1+u2e)，設(shè)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轉(zhuǎn)換為十進制整數(shù)： IU1=INT(1+eu2)，IU2=INT(1+eu3) 設(shè)子代變異的概率(稱為變異率)為pm。變異是當u4pm時對子代個體的IU1位和IU2位的值進行翻轉(zhuǎn)操作： 0 1 1 0 10 0 1 1 1 (變異前) (變異后),步驟7：進化迭代。 第i個子代個體經(jīng)式(3)、式(2)轉(zhuǎn)化成第i組模型參數(shù)。這n個子代個體作為新的父代，算法轉(zhuǎn)入步3，進入下一輪進化過程，重新評價、選擇、雜交、變異，如此反復進化，使個體的適應(yīng)能力不斷提高，直到最優(yōu)個體的優(yōu)化準則值小于某一指定值或最優(yōu)個體的優(yōu)化準則值不再改善，則終止進化迭代，算法結(jié)束。,(a)初始分布 (b)第20次進化迭代后的分布 (c)第60次進化迭代后的分布,步驟8：加速循環(huán)。 用第一次、第二次進化迭代所產(chǎn)生的優(yōu)秀個體的變量變化區(qū)間作為變量新的初始變化區(qū)間，算法進入步驟1，重新運行SGA算法，如此加速循環(huán)，優(yōu)秀個體的變化區(qū)間將逐步調(diào)整和收縮，與最優(yōu)點的距離將越來越近，直到最優(yōu)個體的優(yōu)化準則函數(shù)值小于某一設(shè)定值或算法運行達到預(yù)定加速(循環(huán))次數(shù)，結(jié)束整個算法的運行。此時，就把當前群體中最佳個體或優(yōu)秀個體的平均值指定為AGA的結(jié)果。,AGA的主要特點 利用標準遺傳算法演化過程中的優(yōu)秀個體子群體來逐步調(diào)整、壓縮算法的搜索空間。 控制參數(shù)設(shè)置：二進制編碼長度e、雜交概率和變異率分別固定設(shè)置為10、1.0和1.0；群體規(guī)模n與優(yōu)秀個體數(shù)目s關(guān)系：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ū)劃中的應(yīng)用 氣候區(qū)劃就是把研究區(qū)域劃分成若干個分區(qū)，在同一分區(qū)內(nèi)具有相似的氣候條件，以便調(diào)整種植結(jié)構(gòu)，因地制宜地發(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類，該分類結(jié)果與文獻“劉崇欣. 黔西北林木氣候區(qū)劃的聚類分析. 農(nóng)業(yè)系統(tǒng)科學與綜合研究,1997,13(3) ”的模糊聚類結(jié)果和根據(jù)表2.1各樣本的對比分析結(jié)果都是一致的。 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：評價指標值的標準化處理。設(shè)樣本集為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：構(gòu)造投影指標函數(shù)。PP方法就是把p維數(shù)據(jù)x(i,j)| j=1p綜合成以a=(a(1),a(2), ,a(p)為投影方向的一維投影值z(i),式中，a為單位長度向量。在綜合投影值時，要求投影值z(i)應(yīng)盡可能多地提取x(j,i)中的變異信息，即z(i)的標準差Sz達到盡可能大，同時要求z(i)與已知標準等級值y(i)的相關(guān)系數(shù)的絕對值|Rzy|達到盡可能大。為此，投影指標函數(shù)可構(gòu)造為 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ù)結(jié)構(gòu)特征，最佳投影方向就是最大可能暴露高維數(shù)據(jù)某類特征結(jié)構(gòu)的投影方向?？赏ㄟ^求解投影指標函數(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)的散點圖建立相應(yīng)的等級評價模型。z*(i)與y(i)之間一般呈單調(diào)非降關(guān)系，當z*(i)值超過某門限值時就判定為最高等級(N級)，當指標值低于另門限值時就判定為最低等級(1級)，當z*(i)值介于這兩門限值之間時則為中等等級，可用邏輯斯諦曲線來描述：,式中y*(i)為第i個樣本等級的計算值；模型參數(shù)c(1)、c(2) 分別為積分常數(shù)和增長率，可通過求解如下優(yōu)化問題來確定：,3 基于加速遺傳算法的投影尋蹤等級評價模型AGA-PPGE,3.2 AGA-PPGE在洪水災(zāi)情等級評價中的應(yīng)用 表3.1 河南省洪水災(zāi)情等級標準 災(zāi)情等級指標 一般災(zāi) 較大災(zāi) 大災(zāi) 特大災(zāi) 成災(zāi)面積(hm2) 283.3 直接經(jīng)濟損失(億元) 85.0 根據(jù)表3.1，可用如下方法隨機產(chǎn)生各災(zāi)情指標值及其對應(yīng)的標準災(zāi)情等級樣本系列：四個災(zāi)情等級值一般災(zāi)、較大災(zāi)、大災(zāi)、特大災(zāi)分別對應(yīng)標準災(zāi)情等級值1、2、3、4。 確定一般災(zāi)的左端點值和特大災(zāi)的右端點值，這里分別取為一般災(zāi)的右端點值的0.5倍和特大災(zāi)的左端點值的3倍，這樣，所有災(zāi)級都有一個范圍。 利用均勻隨機數(shù)在每個災(zāi)級范圍內(nèi)產(chǎn)生5個值，考慮到直接經(jīng)濟損失一般與成災(zāi)面積具有正相關(guān)性，同一樣本點的直接經(jīng)濟損失的隨機數(shù)應(yīng)與成災(zāi)面積的隨機數(shù)相同。 在災(zāi)情等級標準表中取邊界值各一次，災(zāi)情等級值取與該邊界值有關(guān)的兩個災(zāi)級值的算術(shù)平均值。這樣得到的樣本點如表3.2序號123所示。,表3.2 洪水災(zāi)情等級的標準值和PPGE模型的計算值的對比結(jié)果 序號 災(zāi)情指標 投 影 洪水災(zāi)情等級 序號 災(zāi)情指標 投 影 洪水災(zāi)情等級 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.