人工智能算法與實踐-第5章 支持向量機

5.4算法總結5.1算法概述5.2算法原理5.3算法案例目錄第五章支持向量機人工智能算法與實踐—1

—

01算法概述PartTHREE—2

—

支持向量機線性可分支持向量機非線性支持向量機二分類模型線性支持向量機支持向量機（SupportVectorMachine，SVM）是一種二分類模型，它的基本模型是定義在特征空間上的間隔最大的線性分類器。它分為線性可分支持向量機、線性支持向量機、非線性支持向量機。5.1算法概述算法概述—3

—

線性可分支持向量機線性支持向量機非線性支持向量機1線性可分支持向量機當訓練數(shù)據(jù)線性可分時，通過硬間隔最大化。則需要對數(shù)據(jù)使用線性可分支持向量機。2線性支持向量機當訓練數(shù)據(jù)線性近似可分時，通過軟間隔最大化，則需要對數(shù)據(jù)使用線性支持向量機。3非線性支持向量機當訓練數(shù)據(jù)線性不可分時，通過硬間隔最大化和核技巧，則需要對數(shù)據(jù)使用非線性支持向量機。5.1算法概述算法概述—4

—

02算法原理PartTHREE—5

—

算法原理246531線性可分支持向量機拉格朗日乘子法對偶問題和KKT條件。SMO算法原理非線性支持向量機線性支持向量機5.2算法原理算法原理—6

—

找出無數(shù)條線將兩類分開如圖所示，有很多個分離超平面可以將數(shù)據(jù)分為兩類。究竟哪一個分離超平面的分類效果最好呢？在SVM中，假設擁有最大“間隔”的超平面效果最好。計算出最大間隔最終將如何計算出最佳分離超平面轉換為如何計算最大間隔。隨機找一條線將兩類分開通俗來講，為了將兩類數(shù)據(jù)分開，最簡單的辦法就是求解一個分離超平面，該平面能夠?qū)嵗值讲煌念悇e。尋找出三條直線為了找到最佳的一個分離超平面，需要假設三條直線，其中有兩條直線會穿過K、U兩點，這兩個點叫做支持向量并且分別是這兩類中的一個點。5.2.1線性可分支持向量機線性可分支持向量機—7

—

最大間隔d最終通過轉換，即是求解：5.2.1線性可分支持向量機線性可分支持向量機—8

—

假設三條直線的方程為：求解:010203無約束條件這是最簡單的情況，解決方法通常是函數(shù)對變量求導，令求導函數(shù)等于0的點可能是極值點。將結果帶回原函數(shù)進行驗證即可。等式約束條件有等式約束條件的：不等式約束條件5.2.2拉格朗日乘子法拉格朗日乘子法—9

—

如何求出

？這里，我們需要引入一種方法叫做拉格朗日乘子法（LagrangeMultiplier），這種方法的目的就是將有n個變量和一個或k約束條件的最優(yōu)解問題轉換為一個有n+k個變量的方程組的極值問題，其變量不受任何約束（n和k為自然數(shù)）需要通過消元求解，或拉格朗日法求解。最終能求出f(x)的最小值。有不等式約束條件的：最終將原問題轉換為：對偶問題對偶問題就是實質(zhì)相同但從不同角度提出不同提法的一對問題，通過這種方法來求得最終的答案

。定義對偶問題：KKT條件KKT條件就是滿足：（1）5.2.3對偶問題和KKT條件對偶問題和KKT條件—10

—

強對偶定理：（1）原函數(shù)是凸函數(shù)（2）約束條件f(x),g(x)是線性式子

（3）滿足KKT條件（3）最終將問題轉換為：（2）（4）SMO算法原理為了解決等式5.2.4

SMO算法SMO算法原理—11

—

需要引入SMO原理，SMO算法是一個啟發(fā)式避免了二次規(guī)劃數(shù)值解法的復雜迭代過程。這不但大大節(jié)省了計算時間，而且不會牽涉到迭代法造成的誤差積累（其它一些算法中這種誤差積累帶來了很大的麻煩）。理論上SMO的每一步最小優(yōu)化都不會造成任何誤差積累，而如果用雙精度數(shù)計算，舍入誤差幾乎可以忽略，于是所有的誤差只在于最后一遍檢驗時以多大的公差要求所有拉格朗日乘子滿足KKT條件?？梢哉fSMO算法在速度和精度兩方面都得到了保證。算法。為了計算的最大值。需要先給它們一個初始值，然后固定其他n-1個值然后再求其中一通過對所有的求解，最終可以求得原問題的最優(yōu)解：則求解出了一個最佳分離超平面。個。同理所有的都是這樣求出來的。SMO的最大特色在于它可以采用解析的方法而完全非線性支持向量機非線性分類問題中，我們不能在二維空間上找到一條線去區(qū)分這兩類數(shù)據(jù)集，而是需要對這些數(shù)據(jù)進行變換。將數(shù)據(jù)從低維向高維做映射，這樣做的目的是將非線性問題轉換為線性問題，但是做這樣轉換勢必會增大處理問題的規(guī)模。為了避免這個問題的發(fā)生，可以使用一個叫做核函數(shù)的東西，它既不會使維度上升又可以使問題變?yōu)榫€性問題求解。求解非線性支持向量機的對偶問題為：5.2.5非線性支持向量機非線性支持向量機—12

—

非線性支持向量機常見的核函數(shù)有兩種：5.2.5非線性支持向量機非線性支持向量機—13

—

（1）多項式核函數(shù)：（2）高斯核函數(shù)：每個核函數(shù)中的參數(shù)對于SVM都有著不同的影響，在這里僅拿高斯核函數(shù)中的

談談它對SVM的影響。當時，兩類的區(qū)分度下降，會出現(xiàn)欠擬合現(xiàn)象。當時，兩類的區(qū)分度會上升，但是如果選擇不當也會出現(xiàn)過擬合現(xiàn)象。線性支持向量機

若數(shù)據(jù)集在線性可分且存在一些噪點，則需要使用線性支持向量機進行求解。在線性支持向量機中，通過加入松弛變量，讓噪點也滿足構建的方程。再進行方程的求解。5.2.6線性支持向量機線性支持向量機—14

—

線性支持向量機

需要說明的一點是稱為損失函數(shù)。應滿足的條件是：5.2.6線性支持向量機線性支持向量機—15

—

式中C為懲罰系數(shù)，當時，會出現(xiàn)過擬合現(xiàn)象。C越小則會出現(xiàn)欠擬合現(xiàn)象。所以C的合理選取是至關重要的。

對偶問題和KKT條件

線性可分支持向量機拉格朗日乘子法

非線性支持向量機5.2算法原理算法原理—16

—

SMO原理

線性支持向量機03算法案例-手寫體數(shù)字識別PartTHREE—17

—

算法案例-手寫體數(shù)字識別雖然數(shù)字的筆畫簡單，類別較少。但是由于不同的人寫出來的數(shù)字總帶有著個人特色，數(shù)字相較于文字來說沒有一些上下文的關系更是少了一些相關性。最重要的是，由于數(shù)字總是與金融、財會掛鉤，所以數(shù)字的準確性關系到事情的成敗問題。所以正確識別手寫體數(shù)字的重要性不言而喻。左圖為未經(jīng)處理的部分數(shù)據(jù)。5.3算法案例-手寫體數(shù)字識別算法案例-手寫體數(shù)字識別—18

—

算法案例-手寫體數(shù)字識別

針對此次實驗，前期我們收集了近1000張來自不同人手寫的數(shù)字集。將該數(shù)據(jù)集作為此次實驗的實驗數(shù)據(jù)集。再通過降維、取特征值等預處理的方法將該數(shù)據(jù)集進行前期的處理，得到想要的數(shù)據(jù)集。將處理好的數(shù)據(jù)集進行分割，將80%的數(shù)據(jù)集作為訓練集，再用剩余20%作為測試集。左圖是該算法的流程圖。由于收集到的數(shù)據(jù)都是一些大小不一的圖片。所以第一步需要對圖片進行一些預處理，通過二值化的操作將圖片像素全部處理為0或1。使用0或1來描述圖像中的信息。5.3算法案例-手寫體數(shù)字識別算法案例-手寫體數(shù)字識別—19

—

算法案例-手寫體數(shù)字識別

本份數(shù)據(jù)集共有2000條數(shù)據(jù)，1600條數(shù)據(jù)會作為訓練集，剩下的400條數(shù)據(jù)會作為測試集去評判該模型的準確率。接下來就是上述提到的將圖片進行二值化處理。

二值化處理即為每個像素只有兩個可能值得數(shù)字圖像。簡單來講就是將圖像中其將大于某個臨界灰度值的像素灰度設為灰度極大值，小于這個值的為灰度極小值，從而實現(xiàn)二值化。這樣做的目的就是減少不必要的信息量，提高后期對數(shù)據(jù)的處理速度。最后將處理過后的數(shù)據(jù)存成文本形式，以便于模型的使用，處理后的部分數(shù)據(jù)如左圖所示。5.3算法案例-手寫體數(shù)字識別算法案例-手寫體數(shù)字識別—20

—

算法案例-手寫體數(shù)字識別

在本次試驗中選用的核函數(shù)為高斯核函數(shù)。對于模型準確率的影響最大的兩個參數(shù)分別是前面所介紹的懲罰系數(shù)C和高斯核函數(shù)中的

。通過對兩個參數(shù)的調(diào)整，確定最終的SVM模型。我們使用了控制變量法來對兩個參數(shù)進行調(diào)整，懲罰系數(shù)C調(diào)整的結果圖如左圖所示（縱軸為模型的準確率，橫軸分別表示兩個參數(shù)）。不難發(fā)現(xiàn)，當C=2.4時，模型的準確率最高。5.3算法案例-手寫體數(shù)字識別算法案例-手寫體數(shù)字識別—21

—

算法案例-手寫體數(shù)字識別在本次試驗中選用的核函數(shù)為高斯核函數(shù)。對于模型準確率的影響最大的兩個參數(shù)分別是前面所介紹的懲罰系數(shù)C和高斯核函數(shù)中的

。通過對兩個參數(shù)的調(diào)整，確定最終的SVM模型。我們使用了控制變量法來對兩個參數(shù)進行調(diào)整，懲罰系數(shù)C調(diào)整的結果圖如左圖所示（縱軸為模型的準確率，橫軸分別表示兩個參數(shù)）。不難發(fā)現(xiàn)，當=0.006時，模型的準確率最高。5.3算法案例-手寫體數(shù)字識別算法案例-手寫體數(shù)字識別—22

—

算法案例-手寫體數(shù)字識別通過綜合兩個圖中的信息，我們發(fā)現(xiàn)兩個參數(shù)并不是取值越大越理想，兩個參數(shù)都有各自的最優(yōu)取值。最終得出當C=2.4，=0.006時，該模型的準確率最高。準確率在98.6%左右。因為手寫體自身因為出自不同的人所以本身所帶的噪點就會有很多，能訓練出如此高的準確率是比較理想的狀態(tài)