特征選擇法與蟻群算法簡介

1、特征選擇法與蟻群算法簡介簡介什么叫特征選擇？ 經(jīng)典的特征選擇方法是從多個特征中選取一些特征，這個方法可以說包括特征選擇和特征提取兩個方面。特征提取廣義上指的是一種變換，將處于高維空間的樣本通過映射或變換的方式轉(zhuǎn)換到低維空間，達到降維的目的；特征選擇指從一組特征中去除冗余或不相關(guān)的特征來降維。這兩者常聯(lián)合使用，一般先通過變換將高維特征空間映射成低維特征空間，然后再去除冗余和不相關(guān)的特征來進一步達到降維的目的。簡介為什么要用特征選擇算法為什么要用特征選擇算法? ? 獲取最優(yōu)特獲取最優(yōu)特征組合征組合提高測試數(shù)據(jù)提高測試數(shù)據(jù)的效率的效率減少系統(tǒng)計減少系統(tǒng)計算時間算時間更高的檢測率更高的檢測率更低的虛警

2、率更低的虛警率簡介特征選擇的步驟特征選擇的步驟原始特征集原始特征集產(chǎn)生特征集產(chǎn)生特征集評估子集評估子集停止準則停止準則結(jié)果驗證結(jié)果驗證不滿意特征組合滿意特征組合通過特征算法子集優(yōu)劣特征選擇分類根據(jù)特征子集形成方式分類：根據(jù)特征子集形成方式分類：特征選擇分類根據(jù)特征集合的評價策略方式分類：根據(jù)特征集合的評價策略方式分類：基于濾波(Filter)評價策略的特征選擇算法?；谇度胧?Wrapper)評價策略的特征選擇算法。常見的特征選擇算法1.1.遺傳算法遺傳算法 3 3. .螞蟻算法螞蟻算法2 2. .粒子群算法粒子群算法遺傳算法 遺傳算法（Genetic Algorithm）： 是模擬達爾文生物

3、進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。每個個體實際上是染色體是染色體帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)是某種基因組合，它決定了個體的形狀的外部表現(xiàn)。遺傳算法 遺傳算法的基本運算過程如下： （1)初始化：設(shè)置進化代數(shù)計數(shù)器t=0，設(shè)置最大進化代數(shù)T，隨機生成M個個體作為初始群體P(0)。 （2）個體評價：計算群體P(t)中各個個體的適應(yīng)度。 （3）選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的

4、個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。 （4）交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。 （5）變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。 群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t+1)。 （6）終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。粒子群算法粒子群算法：也稱粒子群優(yōu)化算法（Particle Swarm Optimization，PSO），是由Eberhart 博士和kennedy 博士

5、提出，源于對鳥群捕食的行為研究 。該算法最初是受到飛鳥集群活動的規(guī)律性啟發(fā)，進而利用群體智能建立的一個簡化模型。這個算法基于迭代的優(yōu)化算法。粒子群的每個個體都代表優(yōu)化問題的候選解，每個粒子具有位置x和速度v兩個特征，位置代表候選解的值，速度用于決定粒子在搜素空間迭代的位移。粒子對應(yīng)的目標函數(shù)值作為粒子的適應(yīng)度f，候選解的優(yōu)劣程度由該適應(yīng)度決定。粒子群算法 基于粒子群優(yōu)化算法的特征選擇的算法步驟如下： （1）粒子群初始化。 （2）對粒子群每個粒子計算適應(yīng)值，適應(yīng)值與最優(yōu)解的距離直接有關(guān)。 （3）種群根據(jù)適應(yīng)值進行復制。 （4）如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟（2）。蟻群算法蟻群算法-蟻群

6、算法起源蟻群算法起源 螞蟻屬于群居昆蟲單個螞蟻的行為極其簡單,但由這樣的單個簡單的個體所組成的蟻群群體卻表現(xiàn)出極其復雜的行為,能夠完成復雜的任務(wù)。蟻群算法起源蟻群算法起源 螞蟻覓食螞蟻沒有發(fā)育完全的視覺感知系統(tǒng)，甚至很多種類完全沒有視覺，他們在尋找食物的過程中是如何選擇路徑的呢？蟻群是如何完成這些復雜的任務(wù)的呢? 人們經(jīng)過大量研究發(fā)現(xiàn),螞蟻個體之間是通過一種稱之為外激素(pheromone) 的物質(zhì)進行信息傳遞. 從而能相互協(xié)作,完成復雜的任務(wù). 蟻群之所以表現(xiàn)出復雜有序的行為,個體之間的信息交流與相互協(xié)作起著重要的作用.蟻群算法起源蟻群算法起源螞蟻在運動過程中, 能夠在它所經(jīng)過的路徑上留下外

7、激素,而且螞蟻在運動過程中能夠感知外激素的存在及其強度,并以此指導自己的運動方向, 螞蟻傾向于朝著外激素強度高的方向移動.由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象: 某一路徑上走過的螞蟻越多,則后來者選擇該路徑的概率就越大. 螞蟻個體之間就是通過這種信息的交流達到搜索食物的目的。蟻群算法起源蟻群算法起源 20世紀50年代中期創(chuàng)立了仿生學，人們從生物進化的機理中受到啟發(fā)。提出了許多用以解決復雜優(yōu)化問題的新方法，如進化規(guī)劃、進化策略、遺傳算法等，這些算法成功地解決了一些 實際問題。1991年意大利米蘭理學院M. Dorigo提出Ant System, 用于求解TSP等組合優(yōu)化問題。

8、1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的聯(lián)系。1996年二人又提出Ant Colony System1997年有人提出Max-Min Ant System1999年Dorigo等人把先前各種算法歸結(jié)為Ant Colony Optimization meta-heuristic的統(tǒng)一框架下，給出抽象而規(guī)范的算法描述.目前，被較廣泛的應(yīng)用DorigoDorigo蟻群算法-雙橋?qū)嶒炞罱K最終有有80%-100%的螞蟻選擇較短的橋。的螞蟻選擇較短的橋。簡化的螞蟻尋食過程螞蟻從A A點出發(fā)，速度相同，食物在D D點，可能隨機選擇路線ABDABD

9、或ACDACD。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步， 本圖為經(jīng)過9 9個時間單位時的情形：走ABDABD的螞蟻到達終點，而走ACDACD的螞蟻剛好走到C C點，為一半路程。簡化的螞蟻尋食過程本圖為從開始算起，經(jīng)過1818個時間單位時的情形：走ABDABD的螞蟻到達終點后得到食物又返回了起點A A，而走ACDACD的螞蟻剛好走到D D點。 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過3636個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D D點取得了食物，此時ABDABD的路線往返了2 2趟，每一處的信息素為4 4個單位，而ACDACD的路線往返了一趟，每一處的信息

10、素為2 2個單位，其比值為2 2：1 1。 尋找食物的過程繼續(xù)進行，則按信息素的指導，蟻群在ABDABD路線上增派一只螞蟻（共2 2只），而ACDACD路線上仍然為一只螞蟻。再經(jīng)過3636個時間單位后，兩條線路上的信息素單位積累為1212（4+44+4* *2 2）和4 4（2 2* *2 2），比值為3 3：1 1。 若按以上規(guī)則繼續(xù)，蟻群在ABDABD路線上再增派一只螞蟻（共3 3只）， 而ACDACD路線上仍然為一只螞蟻。再經(jīng)過3636個時間單位后，兩條線路上的信息素單位積累為2424（4+44+4* *2+42+4* *3 3）和6 6（2 2* *3 3），比值為4 4：1 1。 若

11、繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACDACD路線而選擇ABDABD路線。簡化的螞蟻尋食過程簡化的螞蟻尋食過程 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 人工蟻群和自然蟻群的區(qū)別：人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點； 人工蟻群選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目

12、的地的距離。自然界螞蟻覓食行為自然界螞蟻覓食行為蟻群優(yōu)化算法蟻群優(yōu)化算法覓食空間覓食空間問題的搜索空間問題的搜索空間搜索空間的一組搜索空間的一組有效解有效解一個有效解一個有效解問題的最優(yōu)解問題的最優(yōu)解蟻群蟻群蟻巢到食物的一條路徑蟻巢到食物的一條路徑找到的最短路徑找到的最短路徑對對應(yīng)應(yīng)關(guān)關(guān)系系信息素信息素信息素濃度變量信息素濃度變量蟻群優(yōu)化算法基本流程 TSPTSP問題的人工蟻群算法中，假設(shè)m m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1 1 信息素值也稱信息素痕跡。2 2 可見度，即先驗值。 信息素的更新方式有2 2種，一是

13、揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值“好”( (有螞蟻走過) )的邊增加信息素。 螞蟻向下一個目標的運動是通過一個隨機原則來實現(xiàn)的，也就是運用當前所在節(jié)點存儲的信息，計算出下一步可達節(jié)點的概率，并按此概率實現(xiàn)一步移動，逐此往復，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。蟻群優(yōu)化算法基本流程 對于每只螞蟻k，路徑記憶向量Rk按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當前所在城市為i，則其選擇城市j作為下一個訪問對象的概率如上式。J

14、k(i)表示從城市i可以直接到達的、且又不在螞蟻訪問過的城市序列Rk中的城市集合。h(i, j)是一個啟發(fā)式信息（信息素濃度變量），通常由 h (i, j)=1/dij直接計算。t(i, j)表示邊(i, j)上的信息素量。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui uthth蟻群優(yōu)化算法基本流程 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui uthth為了模擬螞蟻在較短路徑上留下更多的信

15、息素，當所有螞蟻到達終點時，必須把各路徑為了模擬螞蟻在較短路徑上留下更多的信息素，當所有螞蟻到達終點時，必須把各路徑的信息素的信息素濃度濃度重新更新一次，信息素的更新也分為重新更新一次，信息素的更新也分為兩個步驟：兩個步驟： (1) (1)每每一輪過后，問題空間中的所有路徑上的信息素都會發(fā)生一輪過后，問題空間中的所有路徑上的信息素都會發(fā)生蒸發(fā)蒸發(fā) (2) (2)所有所有的螞蟻根據(jù)自己構(gòu)建的路徑長度在它們本輪經(jīng)過的邊上釋放信息素的螞蟻根據(jù)自己構(gòu)建的路徑長度在它們本輪經(jīng)過的邊上釋放信息素11( , )(1)( , )( , ),(), if ( , ) ( , ) 0, otherwisemkkk

16、kki ji ji jCi jRi jtttt信息素更新的作用信息素揮發(fā)（evaporation）信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，這個揮發(fā)過程主要用于避 免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。信息素增強（reinforcement）增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現(xiàn) 由單個螞蟻無法實現(xiàn)的集中行動?；鞠伻核惴ǖ碾x線更新方式是 在蟻群中的m只螞蟻全部完成n城市的訪問后，統(tǒng)一對殘留信息進行更新處理。TSPTSP問題的蟻群優(yōu)化算法偽代碼for for each edgeset t0 = m/

17、Cnn (initial pheromone value )while while not stopfor for each ant krandomly choose an initial cityfor for i = 1 to nchoose next city j with probabilitycompute the length Ck of the tour constructed by the kth antfor for each edge update the pheromone valueprint resultTSP舉例四個城市的TSPTSP問題，距離矩陣和城市圖示如下：假

18、設(shè)共m m=3=3只螞蟻，參數(shù)=1=1，=2=2，=0.5=0.5312354152242ijWdABDC241523步驟1首先使用貪婪算法得到路徑的(ACDBA), 則Cnn =1+2+4+3=10，求得0 =m/Cnn =0.3。初始化所有邊上的信息素含量。步驟2 .1為每個螞蟻隨機選擇出發(fā)城市，假設(shè)螞蟻1選擇城市A，螞蟻2選擇城市B，螞蟻3選擇城市D。為每個螞蟻選擇下一訪問城市，僅以螞蟻1為例，當前城市i=A，可訪問城市集合j1 (i)=B,C,D，計算螞蟻1訪問各個城市的概率。312354152242ijWdABDC241523121212:0.3(1/3)0.033:0.3(1/1)0.3:0.3(1/2)0.075ABABACACADADBACDththth3123