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