1、Ch8 特征的選擇與提取之特征選擇,特征選擇的任務：從n個特征中選擇出m(mn)個最有效的特征。 方法：根據(jù)專家的知識挑選那些對分類最有效的、最有影響的特征；用數(shù)學的方法進行篩選、比較找出對分類最有影響的特征。,特征選擇,需要解決的問題 如何確定選擇的標準（前面學習過的類別可分性準則）； 需要找到一個比較好的算法，以便在較短的時間內找出一組最優(yōu)的特征。,特征選擇,兩種最為顯見的選擇方法：單獨選擇法與窮舉法。 單獨選擇法指的是把n個特征單獨使用時的可分性準則都計算出，從大到小排序，如： 使得J較大的前m個特征作為選擇結果，但是這樣所得到的m個特征一般未必時最好的。,特征選擇,窮舉法： 從D個特征

2、中選擇d個，所有可能的組合數(shù)為 ，如D=20, d=10，這時有 種特征的組合方法。把184756種特征組合的可分性準則函數(shù)全部計算出來，然后看哪一種特征組合的準則函數(shù)值最大，我們就應該選擇這種組合的前10個特征。,特征選擇分支定界法,分支定界法：是一種自上而下的啟發(fā)式搜索算法，具有回溯功能，可使所有可能的特征組合都被考慮到。由于合理的組織了搜索過程，使得有可能不必計算某些組合，而又不影響得到最優(yōu)的結果。 分支定界法的必備條件：所使用的準則函數(shù)必須是具有單調性的。即，從D個特征中選擇d個特征組成d維特征向量，再由這d個特征中選擇k個特征組成k維向量，對應的準則函數(shù)應滿足： Ddk,特征選擇分支

3、定界法,分支定界法：整個搜索過程可以使用樹來表示，下圖表示一個從5個特征中選擇2個特征的例子，節(jié)點上的標號表示去掉的特征序號。每一級在上一級的基礎上再去掉一個特征。級數(shù)正好是已經去掉的特征數(shù)。,特征選擇分支定界法,特征選擇分支定界法,分支定界法：若某一支已經搜索到葉節(jié)點，例如，右側的第一支的葉節(jié)點，該節(jié)點的特征組為x*=(x1,x2)T，計算相應的準則函數(shù)值并將其作為界：B=J(x*)。這時，樹中的某個節(jié)點，例如節(jié)點A，節(jié)點所表示的特征組為(x1,x4,x5)T；計算出節(jié)點A相應的準則函數(shù)值JA，若JA B，則節(jié)點A以下各點都不必計算，這是由于準則函數(shù)的單調性所確定的。,特征選擇分支定界法,注

4、意：在搜索過程中，如果發(fā)現(xiàn)了某個葉節(jié)點所對應的準則函數(shù)值JB，則可以斷言：J是當前搜索到的最優(yōu)特征組，于是可以修改x*和B；繼續(xù)搜索，直到全樹搜索結束。 分支定界法，一般將其稱為最優(yōu)搜索算法。,特征選擇分支定界法,算法步驟：假設當前處于某一級i的某個節(jié)點上。對于 各級的所有后繼節(jié)點所舍棄的特征已經求出，并存在存儲器內。 表示第i級的當前所討論節(jié)點的 個后繼節(jié)點所舍棄的特征； 表示處于第i級的當前所討論節(jié)點在舍棄i個特征后所具有的特征集， 表示處于第i級的當前所討論節(jié)點的后繼節(jié)點可以舍棄的特征集合， 表示這個集合的基數(shù)。,特征選擇分支定界法,在下面的算法中，顯然 和 是已知的。算法是從0級開始的

5、，并從右邊的第一支開始計算，D是原始特征的數(shù)目，d是所要選擇出的特征數(shù)目，J是可分性準則函數(shù)，r0=D, 是全部特征集合， 。,特征選擇分支定界法,算法步驟 步驟1 利用公式 計算 ； 根據(jù)下式計算 ： 從 中去掉 ，并修改,特征選擇分支定界法,算法步驟 步驟2：檢驗和后繼節(jié)點相應的準則函數(shù)值是否小于B。 若 ，則轉向步驟4；否則，若 ，則置 ，然后轉向步驟3，否則從 中去掉 ，即 若 ，則轉向步驟5，否則置 ，然后轉向步驟1。,特征選擇分支定界法,算法步驟 步驟3 把 放回到 中，即 置 若 ，則轉向步驟2，否則轉向步驟3。,特征選擇分支定界法,算法步驟 步驟 4 回溯 置 若 ，則終止算法

6、； 否則，把 放入到當前的特征集，即 置 ，轉向步驟3。,特征選擇分支定界法,算法步驟 步驟 5 修改界值 置 ，把 作為當前最好的特征組 ，置 ，轉向步驟3。,特征選擇分支定界法,分析 優(yōu)點：該算法可以求出最優(yōu)解。 缺點：在很多情形，該算法的計算量太大，難以實現(xiàn)。,特征選擇次優(yōu)搜索算法,單獨最優(yōu)特征組合 順序前進法 順序后退法,特征選擇次優(yōu)搜索算法,單獨最優(yōu)特征組合 最為簡單的方法，是計算各個特征單獨使用時的準則函數(shù)值，并將其排序，取前d個作為所要選擇的特征。但是，一般為而言即使各特征是單獨使用的，這一結論也不是最優(yōu)的。要保證所選則的特征的最優(yōu)性，必須使得可分性準則函數(shù)值滿足：,特征選擇次優(yōu)

7、搜索算法,順序前進法(Sequential Forward Selection, SFS) 這是一種簡單的自下而上的搜索算法，每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時，對應的J值最大，直到特征數(shù)增加到d為止。 設已經選擇了k個特征的特征組為 ，未入選的D-k個特征 ， ，按照它們與已入選的特征組合后的J值的大小排序： 則下一步的特征組選為 注意：算法開始時,特征選擇次優(yōu)搜索算法,順序前進法(Sequential Forward Selection, SFS) 該算法考慮了所選特征與已入選特征之間的相關性。一般來說，比前面所提出的單獨選擇方法要好。 缺點：對于已經入選的

8、特征無法刪除或替換。 注意：上述的SFS算法每次增加一個特征，實際上可以每次增加多(r)個特征。,特征選擇次優(yōu)搜索算法,順序后退選擇法(Sequential Backward Selection,SBS) 該算法是一種自上而下的方法。從全體特征中每次舍棄一個特征，所刪除的特征應該使得仍然保留特征組的J值最大。 假設已刪除了k個特征，得到特征組 ，將 中的各個特征 ， 按照下述的J值進行排序： 則,特征選擇次優(yōu)搜索算法,順序后退選擇法與順序前進選擇法的比較 在計算過程中，可以估計每次去掉一個特征時，所造成的可分性的降低； 順序后退法是在高維空間中進行的，所以計算量較大。,特征選擇的幾種新算法,模

9、擬退火算法 Tabu(禁忌)搜索算法 遺傳算法,Tabu搜索算法,Tabu(禁忌)搜索算法 算法的基本思想：一個解的某個“鄰域”中一般存在性能更好的解。因此，Tabu搜索算法僅僅在一些解的鄰域中進行。為了避免搜索過程的重復，從而能夠搜索更大的解空間，因此該算法要求記錄近期的搜索過的解。 使用一個表，Tabu表，記錄這一搜索過程的解。 如果一個解在Tabu表中，說明該解在近期被訪問過。一旦被收入Tabu表中，在某個時間段內禁止訪問該解。,Tabu搜索算法,Tabu(禁忌)搜索算法的基本框架 步驟 1 令迭代步數(shù) ，Tabu 表為 ，給出初始解為x，并令最優(yōu)解； 步驟 2 從x的鄰域中選擇一定數(shù)量

10、的解構成候選集合N(x)； 步驟 3 若N(x) ，則轉2，否則從N(x)中找出最優(yōu)解x； 步驟 4 若 ，并且 不滿足激活條件，則令 ，轉3，否則，令。,Tabu搜索算法,步驟 5 如果 的性能比 的性能好，則令 ； 步驟 6 如果Tabu表的長度等于規(guī)定長度，則刪去表中最早搜索過的解； 步驟 7 令 ； 步驟 8 若滿足終止條件，則算法結束， 為最終解，否則，令 ，轉2。,Tabu搜索算法,Tabu(禁忌)搜索算法的分析pp:208,遺傳算法(進化計算),遺傳算法(進化計算) 遺傳算法主要是從達爾文的生物進化論得到啟示。生物在漫長的進化過程中，經過遺傳和變異，按照“物競天澤，適者生存”這一

11、規(guī)則演變，逐漸從最簡單的低級生物發(fā)展到復雜的高級生物。基于這種思想，發(fā)展了用于優(yōu)化的遺傳算法。,遺傳算法,遺傳算法發(fā)展的簡要回顧 1950s，將進化原理應用于計算機科學的初步努力。 50年代末到60年代初，Holland應用模擬遺傳算子研究適應性。 1967年，Bagley的論文中首次提出了遺傳算法這一術語。 1975年，Holland的經典著作自然和人工系統(tǒng)中的適應性出版，系統(tǒng)闡述了遺傳算法的基本理論和方法。 1975年，DeJong的博士論文遺傳自適應系統(tǒng)的行為分析，將Holland的模式理論與他的計算試驗結合起來。 1983年，Holland的學生Goldberg將遺傳算法應用于管道煤氣

12、系統(tǒng)的優(yōu)化，取得了很好的效果。,遺傳算法的應用,遺傳算法,幾個常用的術語(這些術語來自于生物學，但是與其在生物學中的含義有所不同) 基因鏈碼 生物的性狀是由生物的遺傳基因的鏈碼所確定的。一個基因鏈碼就代表問題的一個解，每個基因鏈碼有時也稱為一個個體。在遺傳算法中有時也把基因鏈碼稱為染色體。 群體 由若干個個體構成的集合，稱為一個群體。每個個體都代表了問題的一個解，因此群體表示的是問題的一些解的集合。,遺傳算法,交叉 許多生物體的繁衍是通過染色體的交叉完成的。在遺傳算法中沿用了這一概念，并把交叉作為一個操作算子。對該算子的操作如下：選擇群體中的兩個個體x1,x2，以這兩個個體為雙親作基因鏈碼的交

13、叉，從而產生兩個新個體,pp:209. 變異 在生物體的繁衍過程中，變異是一個重要的步驟。通過在染色體上的某些基因位置產生突變使得新產生的的個體與其他有所不同。該算子的實現(xiàn)方法如下：對于群體中的某個個體，即基因鏈碼，隨機選取某一位，將該基因翻轉（0改為1，1改為0）如： 100011000110 100011010110,遺傳算法,適應度 生物體對環(huán)境的適應程度的不同而表現(xiàn)出不同的生命力。在此，每個個體對應于優(yōu)化問題的一個解xi,每個解對應于一個函數(shù)值fi。這個函數(shù)值越大，表明它所對應的解xi越好，也表明對環(huán)境的適應能力越高，因而可以用每個個體的函數(shù)值fi作為它對環(huán)境的適應度。 選擇 選擇的目

14、的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代產生后代個體。判斷個體優(yōu)良的準則就是它們各自的適應度。顯然這一操作借用了一種進化原則：個體的適應度越高，其被選擇的機會就越大。作為一種算子，選擇操作在遺傳算法中存在多種實現(xiàn)方法，最簡單的一種方法就是采用和適應度值成比例的概率方法進行選擇。,遺傳算法,遺傳算法的基本算法（標準算法） 令進化代數(shù) g=0, 并給出初始化群體P(g); 對P(g)中的每個個體給出估計值； 從P(g)中選擇兩個個體，并對這兩個個體完成交叉和變異操作，得到新一代的群體P(g+1)。令g=g+1。 如果終止條件滿足，則算法結束，否則轉到2)。,遺傳算法,說明 由上述的

15、基本算法可見，遺傳算法的流程很簡單，選擇、交叉和變異是遺傳算法的主要操作算子，它們使得遺傳算法具有了與其他傳統(tǒng)算法所不同的特性。遺傳算法中包含了如下5個基本要素(1)參數(shù)編碼；(2)初始群體的設定；(3)適應度函數(shù)的設定；(4)控制參數(shù)的設定(指群體大小和使用遺傳操作的概率等)；(5)遺傳操作設計。,遺傳算法,遺傳算法的基本過程是：首先采用某種編碼方式將解空間映射到編碼空間，每個編碼對應問題的一個解，稱為染色體或個體。一般通過隨機方法確定起始的一群個體，稱為種群，在種群中根據(jù)適應值或某種競爭機制選擇個體（適應值就是解的滿意程度，可以由外部顯式適應度函數(shù)計算，也可以由系統(tǒng)本身產生，如由協(xié)同演化時不同對策的博奕確定，或者由個體在群體中的存活量和繁殖量確定。），使用各種遺傳操作算子（包括雜交，變異，倒位等等）產生下一代（下一代可以完全替代原種群，即非重疊種群；也可以部分替代原種群中一些較差的個體，即重疊種群），如此進化下去，直到滿足期望的終止條件。,遺傳算法,關于遺傳算法中的編碼 可以是位串、實數(shù)、有序串、樹或圖，Holland最初的遺傳算法是基于二進制串的，類似于生物染色體結構，易于用生物遺傳理論解釋，各種遺傳操作也易于實現(xiàn)。