【文章內(nèi)容簡(jiǎn)介】 變成,i=1,2,…l 314求廣義的最優(yōu)分類面(最大限度將樣本分開，同時(shí)使分類間隔最大)的問題可以表示為下面的二次規(guī)劃問題 315約束性條件變?yōu)?314)，其中這里可看作訓(xùn)練樣本關(guān)于分離超平面的偏差，時(shí)問題變?yōu)榫€性可分情形，C為某個(gè)指定的常數(shù)，它實(shí)際上起控制對(duì)錯(cuò)分樣本懲罰程度的作用，是錯(cuò)分樣本的比例與算法復(fù)雜度之間的折衷。求解這一優(yōu)化問題的方法與求解最優(yōu)分類面時(shí)的方法相同，一樣轉(zhuǎn)化為一個(gè)二次函數(shù)極值問題，其結(jié)果與可分情況下得到的幾乎完全相同，但是條件(39b)變?yōu)?i=1,2,…l 316對(duì)比式(316)和式(39b)，可以看出，由于C的引入，的值受到限制，C越小，的值也就越小，又由式(312)可知，日也變小，而是兩類之間的間隔，變大。間隔越大，泛化能力越強(qiáng)，所以C越小，SVM泛化能力越強(qiáng)，但顯然這時(shí)SVM的分類準(zhǔn)確率要降低。同理，C越大，兩類之間的間隔越小，SVM泛化能力就越差，但這時(shí)的SVM分類準(zhǔn)確率可以得到提高。從上面的分析知道，懲罰系數(shù)C可以控制SVM的泛化性能和錯(cuò)分率之間的折衷。C不宜太大，也不宜太小。C的值太大時(shí)，雖然此時(shí)對(duì)訓(xùn)練樣本的識(shí)別率高，SVM的分類學(xué)習(xí)性能很好(如果不出現(xiàn)過適應(yīng)的話)，但此時(shí)的泛化性能較低。再看看對(duì)偶問題，懲罰系數(shù)C的值越大，Lagrange算子的約束力就越大，這就意味著要花更長(zhǎng)的訓(xùn)練時(shí)間，過長(zhǎng)的訓(xùn)練時(shí)間，往往意味著過適應(yīng)和低下的泛化能力，其解決辦法就是減小C，但是C的值也不宜太小，注意到線性不可分的情況下，C的值太小時(shí)，所有的自然也會(huì)很小，泛化能力雖然高，但準(zhǔn)確率無法保證。2．線性不可分SVM在現(xiàn)實(shí)世界中，很多分類問題都是線性不可分的，也就是說在原來的樣本空間中無法找到一個(gè)最優(yōu)的線性分類函數(shù)，但是根據(jù)廣義最優(yōu)超平面的思想，可以設(shè)法通過非線性變換將原樣本空間的非線性問題轉(zhuǎn)化為另一個(gè)空間中的線性問題。SVM就是基于這一思想的，即首先通過非線性變換將輸入空間變換到一個(gè)高維特征空間，在這個(gè)高維空間中樣本變得線性可分，然后在這個(gè)新的特征空間中構(gòu)造最優(yōu)線性分類面。在輸入空間數(shù)據(jù)不能通過線性函數(shù)分開，但在特征空間卻是線性可分的。支持向量機(jī)的基本思想是通過選擇訓(xùn)練集中的一組特征子集(稱為支持向量，SV)，使得對(duì)SV集的線性劃分等價(jià)于對(duì)整個(gè)數(shù)據(jù)集的分割，實(shí)現(xiàn)了在保證分類精度的同時(shí)降低運(yùn)算的復(fù)雜度。SVM方法的訓(xùn)練運(yùn)算速度和對(duì)內(nèi)存容量的大量占用是限制它的應(yīng)用的主要方面，近年來人們針對(duì)方法本身的特點(diǎn)提出了許多算法來解決對(duì)偶尋優(yōu)問題。大多數(shù)算法的一個(gè)共同的思想就是循環(huán)迭代:將原問題分解成為若干子問題，按照某種迭代策略，通過反復(fù)求解子問題，最終使結(jié)果收斂到原問題的最優(yōu)解。根據(jù)子問題的劃分和迭代策略的不同，又可以大致分為兩類。著名的有Vapnik的Chunking方法、Osuna的分解算法、Platt的SMO算法等。第一類是所謂的“塊算法”(Chunking Algorithm)，是郵Boser，Guyon，Vapnik提出的。Chunk就是塊，也就是工作集，chunking就是通過某種方法，得到一個(gè)由支持向量組成的支持向量集，因?yàn)樽詈蟮某矫媸怯芍С窒蛄繘Q定的，和非支持向量無關(guān)。即去掉Lagrange乘子等于零的訓(xùn)練樣本，不會(huì)影響原問題的解。因此“塊算法”的目標(biāo)就是通過某種迭代方式逐步排除非支持向量。具體的作法是，選擇一部分樣本構(gòu)成工作樣本集進(jìn)行訓(xùn)練，剔除其中的非支持向量，并用保留的支持向量對(duì)剩余樣本進(jìn)行檢驗(yàn)，將不符合訓(xùn)練結(jié)果(一般是指違反KKT條件)的樣本(或其中的一部分)與本次結(jié)果的支持向量合并成為一個(gè)新的工作樣本集，然后重新訓(xùn)練。如此重復(fù)下去直到獲得最優(yōu)結(jié)果。實(shí)際求解QP問題中的Hessian矩陣的規(guī)模由Z*l下降到最多SV*SV，SV為支持向量的數(shù)目。所以當(dāng)支持向量的數(shù)目遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣本數(shù)目時(shí)，“塊算法”顯然能夠大大提高運(yùn)算速度。然而，如果支持向量的數(shù)目本身就比較多，隨著算法迭代次數(shù)的增多，工作樣本集也會(huì)越來越大，算法依舊會(huì)變得十分復(fù)雜。因此第二類方法也就是分解算法，把問題分解成為固定樣本數(shù)的子問題:工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，迭代過程中只是將剩余樣本中部分“情況最糟的樣本”與工作樣本集中的樣本進(jìn)行等量交換，即使支持向量的個(gè)數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對(duì)支持向量中的一部分進(jìn)行優(yōu)化。 Osuna等人提出了分解算法的基本框架。將a的分量分成兩個(gè)集合，工作集B和非工作集N，其中B的大小和N的大小都是固定的。因此在每次迭代中，該方法首先確定B，然后求解關(guān)于B的子QP問題，而保持N中變量不變。每次用N中不滿足優(yōu)化條件的變量替換B中任意變量。但是在該方法中工作集的確定采用了隨機(jī)選取的方法，這將大大影響算法的收斂速度，同時(shí)Osuna關(guān)于算法收斂性的證明是錯(cuò)誤的。針對(duì)Osuna提出的分解算法的收斂速度慢的不足，Joachims提出用可行方向策略來選擇工作集，并依此為基礎(chǔ)設(shè)計(jì)了一種支持向量機(jī)分解學(xué)習(xí)算法稱為SVM。算法是基于Zoutendijk可行方向法，選擇一個(gè)最陡的可行解下降方向d，d僅含q個(gè)非零成員，對(duì)應(yīng)的q個(gè)變量組成工作集，使得每一步尋優(yōu)獲得更大的幅度，從而在當(dāng)前迭代中取得最大的進(jìn)展，進(jìn)而加快收斂速度。同時(shí)，針對(duì)許多問題中支持向量數(shù)遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣本數(shù)，Joachims提出了Shrinking方法，該方法是基于這樣的事實(shí):在優(yōu)化過程中，某個(gè)變量最終不能夠成為支持向量或者成為邊界支持向量在很早就能夠清楚。因此，該方法通過提前估計(jì)哪些變量最終可能成為非支持向量或邊界支持向量，從而在進(jìn)一步優(yōu)化過程中刪除這些變量，使優(yōu)化規(guī)模減少，進(jìn)而提高優(yōu)化速度。第三，針對(duì)每次迭代中最耗時(shí)的是Hessian矩陣Q的計(jì)算，為了避免重復(fù)計(jì)算，Joachims提出了Caching方法來減少每次迭代中的計(jì)算量。這是一種在內(nèi)存耗費(fèi)和訓(xùn)練時(shí)間上的折衷方法。對(duì)于分解算法，Osuna等證明了一個(gè)關(guān)鍵定理：如果存在不滿足KKT條件的樣本，那么在把它加入到上一個(gè)子問題的集合中后，重新優(yōu)化這個(gè)子問題，則可行點(diǎn)依然滿足約束條件，且性能嚴(yán)格地改進(jìn)。因此，如果每一步至少加入一個(gè)不滿足KKT條件的樣本，一系列的二次規(guī)劃子問題可保證最后單調(diào)收斂。這對(duì)于下面的序列最小優(yōu)化算法提供了理論依據(jù)。(SMO)Platt提出了SMO算法。該算法可以說是Osuna分解算法的一個(gè)特例，工作集B中只有2個(gè)乘子，也就是q=2，其優(yōu)點(diǎn)是針對(duì)2個(gè)乘子的二次規(guī)劃問題可以有解析解的形式，從而避免了每次迭代中調(diào)用標(biāo)準(zhǔn)的優(yōu)化算法。盡管由于工作集規(guī)模的減小，使得迭代次數(shù)增加了很多，但每次迭代所需時(shí)間非常短，因此整體訓(xùn)練時(shí)間大大降低。同時(shí)其工作集的選擇不是傳統(tǒng)的最速下降法，而是通過啟發(fā)式方法來分別尋找待優(yōu)化乘子。外層循環(huán)在某個(gè)乘子集合中遍歷，將第一個(gè)不滿足優(yōu)化條件的乘子作為第一個(gè)被優(yōu)化對(duì)象，一旦找到第一個(gè)乘子，內(nèi)層循環(huán)尋找第二個(gè)乘子，使其在當(dāng)前迭代步中具有最大的改變量。完成一次優(yōu)化再循環(huán)進(jìn)行下一次優(yōu)化直到全部樣本都滿足最優(yōu)條件，這種啟發(fā)式策略大大加快了算法的收斂速度。這種算法不需要大的矩陣存儲(chǔ)空間，特別適合稀疏樣本，算法避開了復(fù)雜的數(shù)值求解優(yōu)化問題的過程。SMO算法主要耗時(shí)在最優(yōu)條件的判斷上，所以應(yīng)尋求最合理即計(jì)算代價(jià)最低的最優(yōu)條件判別式，同時(shí)對(duì)常用的計(jì)算量進(jìn)行緩存。隨著對(duì)支持向量機(jī)研究的深入，許多研究人員提出了－些針對(duì)標(biāo)準(zhǔn)支持向量機(jī)C－SVM的變形算法，如v－SVM、One－class SVM、RSVM(reduced SVM)、WSVM(weighted svM)和Ls－svM(reast－square SVM)等算法。這些變形算法主要是通過增加函數(shù)項(xiàng)，變量或系數(shù)等方法使公式變形，產(chǎn)生出各種有某－方面優(yōu)勢(shì)或者－定應(yīng)用范圍的算法。例如，針對(duì)C－SVM算法中唯－可以調(diào)節(jié)的參數(shù)C沒有直觀解釋，在實(shí)際應(yīng)用中很難選擇合適的值的缺陷，v－SVM算法中用參數(shù)v取代C，該參數(shù)可以控制支持向量的數(shù)目和誤差，也易選擇。針對(duì)C－SVM算法無法解決只要求對(duì)某－類樣本正確分類，而其它類樣本信息不全的問題的缺陷，one－class SVM算法提出了超球面的概念，克服了超平面無法解決的問題。針對(duì)C－SVM算法不適合處理大規(guī)模問題的缺陷，RSVM算法通過限制支持向量的選擇范圍來控制每次解方程的規(guī)模，擅長(zhǎng)處理海量數(shù)據(jù)或者支持向量多的數(shù)據(jù)。針對(duì)C－SVM算法不能根據(jù)每個(gè)采樣點(diǎn)數(shù)據(jù)的重要性區(qū)別對(duì)待的缺陷，WSVM算法通過給每個(gè)樣本采用不同的懲罰系數(shù)來反映各自的重要性。另外，為了提高小樣本的識(shí)別率，也可以給他們賦予較高的懲罰系數(shù)。LS－SVM算法主要是解決計(jì)算復(fù)雜性問題，把C－SVM算法的二次規(guī)劃問題轉(zhuǎn)變成了線性方程組來求解。第四章 啟發(fā)式特征選擇系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)序列前向選擇方法 ( Sequential Forward Selection，SFS )，每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得J值為最大，直到特征數(shù)增加到d為止，該過程可以描述為：設(shè)所有的特征集合為Q，假設(shè)有一個(gè)已有個(gè)特征的特征集 ，對(duì)每一個(gè)未入選特征 ( 即中的特征) 計(jì)算其準(zhǔn)則函數(shù)。選擇使最大的那個(gè)特征，并把它加入到集合中。實(shí)際上，在算法的每一步，都選擇一個(gè)特征加入到當(dāng)前集合，使得特征選擇準(zhǔn)則最大。當(dāng)最佳改進(jìn)使特征集性能變壞或達(dá)到最大允許的特征個(gè)數(shù)的時(shí)候，該算法認(rèn)為已經(jīng)選擇出最佳特征子集。該算法的運(yùn)算量相對(duì)較小，但是特征之間的統(tǒng)計(jì)相關(guān)性沒有得到充分考慮。從這個(gè)角度出發(fā)的搜索方式僅能適合一小部分滿足特殊條件的特征集合。例如算法第一步選出的必然是使準(zhǔn)則函數(shù)最大的一個(gè)特征，而后來每步選出的都是對(duì)前一個(gè)特征集合作為最佳補(bǔ)充的一個(gè)特征。在實(shí)際過程中，最佳特征集合極有可能并不包括單獨(dú)貢獻(xiàn)率(準(zhǔn)則函數(shù)值)最大的那個(gè)特征，僅僅只是一些單獨(dú)貢獻(xiàn)率極為普通的特征組合。在該算法中每步都可能出現(xiàn)這樣的現(xiàn)象。序列后向選擇方法 ( Sequential Backward Selection，SBS )。從全體特征開始每次剔除一個(gè)，所剔除的特征應(yīng)使仍然保留的特征組的J值最大。設(shè)已剔除了k個(gè)特征，剩下的特征組為，將中的各特征按下述J值大小排隊(duì)，j=1,2,…Dk。若 則和序列前向選擇方法比較，序列后向選擇方法有兩個(gè)特點(diǎn)：一是在計(jì)算過程中可以估計(jì)每去掉一個(gè)特征所造成可分性的降低，二是由于該方法在一個(gè)較大的變量集上計(jì)算準(zhǔn)則函數(shù) J，所以該算法相對(duì)于SFS計(jì)算量要大。增l去r選擇方法(lr法)。為避免前面方法的一旦被選入(或剔除)就不能再剔除（或選入）的缺點(diǎn)，可在選擇過程中加入局部回溯過程。在第k步可先用SFS法一個(gè)個(gè)加入特征到k+l個(gè)，然后再用SBS法一個(gè)個(gè)剔去r個(gè)特征。具體步驟如下（假設(shè)已經(jīng)選了k個(gè)特征，得出了特征組）：步驟1 用SBS算法在未入選特征組中逐個(gè)選入特征l個(gè)，形成新特征組，置。步驟2 用SBS法從中逐個(gè)剔除r個(gè)最差的特征，形成新特征組，置。若則終止算法，否則，置，轉(zhuǎn)向第一步。這里要說明一下，當(dāng)時(shí)，lr法是自下向上的算法，先執(zhí)行第一步，然后執(zhí)行第二步，起始時(shí)應(yīng)置k=0,。當(dāng)lr時(shí)，lr法是自下而上的算法，先執(zhí)行第二步，然后執(zhí)行第一步，起始時(shí)應(yīng)置k=D。本文的特征選擇算法是在增l減r選擇算法上改進(jìn)的，實(shí)現(xiàn)方法為：先把特征分組，在算法的每一步，都選擇一組特征加入到當(dāng)前集合，使得特征選擇準(zhǔn)則最大，當(dāng)最佳改進(jìn)使特征集性能變壞或達(dá)到最大特征組個(gè)數(shù)時(shí)，開始回溯過程，就是在算法的每步運(yùn)行過程中刪除一組對(duì)準(zhǔn)則函數(shù)無貢獻(xiàn)的特征組，直到剩余特征個(gè)數(shù)符合集合基數(shù)要求。，該算法相對(duì)于lr算法計(jì)算量要小。大多數(shù)基于封裝器模型的特征選擇方法中,采用某些分類器模型對(duì)所選擇的特征集合進(jìn)行評(píng)價(jià),并利用得到的分類精度或分類錯(cuò)誤率作為適應(yīng)度函數(shù)。本文采LIBSVM支持向量機(jī)模型作為分類模型。將樣本數(shù)據(jù)按隨機(jī)的原則,以它們作為訓(xùn)練集和測(cè)試集,應(yīng)用訓(xùn)練集訓(xùn)練支持向量機(jī),然后在測(cè)試集上進(jìn)行驗(yàn)證其分類的正確率(即模型的推廣能力)。利用得到的分類精度作為評(píng)價(jià)函數(shù)。算法流程圖：圖41 基于本文的特征選擇算法執(zhí)行流程支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯(cuò)誤地識(shí)別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(Generalizatin Ability)。從本質(zhì)上講，入侵檢測(cè)實(shí)際上是一個(gè)分類問題，就是要通過檢測(cè)把正常數(shù)據(jù)和異常數(shù)據(jù)分開。在綜合分析目前所能獲得的SVM軟件包基礎(chǔ)上，, 它是臺(tái)灣大學(xué)林智仁(chihJen Lin)博士等開發(fā)設(shè)計(jì)的一個(gè)快速有效的通用支持向量機(jī)算法研究平臺(tái)，可以解決分類問題(包括CSVC、nSVC)、回歸問題(包括eSVR、nSVR)以及分布估計(jì)(oneclassSVM)等問題，提供了線性、多項(xiàng)式、徑向基和S形函數(shù)四種常用的核函數(shù)供選擇，可以有效地解決多類問題、交叉驗(yàn)證選擇參數(shù)、對(duì)不平衡樣本加權(quán)、多類問題的概率估計(jì)等，其訓(xùn)練算法和分類算法都比較先進(jìn)，效率也比較高。本設(shè)計(jì)中數(shù)據(jù)集則采用KDD99數(shù)據(jù)集，它來源于數(shù)據(jù)采集是入侵檢測(cè)系統(tǒng)中第一步要做的工作，但對(duì)于現(xiàn)在網(wǎng)絡(luò)中數(shù)據(jù)量極大的數(shù)據(jù)流的獲取，以及將數(shù)據(jù)流處理為SVM能處理的數(shù)據(jù)格式，如果完全采用軟件來做的話，將消耗系統(tǒng)大量的資源，從而對(duì)于決策分類系統(tǒng)的處理分類將帶來一定的影響，因此在一般的入侵檢測(cè)系統(tǒng)中網(wǎng)絡(luò)數(shù)據(jù)流的獲得都是通