基于分形插值核函數的支持向量機算法

梁禮明 郭 凱 盛校棋

(江西理工大學電氣工程與自動化學院 江西 贛州 341000)

0 引 言

分形理論[1]是1973年由Mandelbrot為研究復雜無序而又具有某種規律的事物提出的。1986年，Bamsley提出了分形插值的概念，為分形的具體化提供了新的思想。分形插值理論將處理數據的復雜性與數據本身可規律化結合起來，來預測數據的走向、數據實值與區間值，已經獲得較多成果并得到應用[2]。數據的這些屬性具有不確定性和復雜性，分形插值利用已知數據點之間的關系，學習分析出潛在規律進行自相似性延拓，經過多次仿射系統迭代，可大大縮小樣本數據預測值與真實數據值之間的差距[3]，從而避免固定形式函數圖像偏離真實數據而引起的較大誤差。

對于分形插值的研究內容主要是分形插值方法與分形維數。分形插值方法[1,3]不像傳統的數學插值函數或擬合函數是通過一組基函數的線性組合來表示，常用的基函數有多項式、有理函數和三角函數等初等函數，常用的分形插值方法是利用迭代函數系統[1,3](Iteration Function System,IFS)來實現的。擺脫傳統函數具有固定函數公式與圖像的形式，使得函數形式與圖像更加逼近數據的真實值，同時函數及圖像的形式具有較強的可塑性，有利于其在數據處理和擬合中的應用。

核方法[4]利用內積運算將通過非線性映射到高維空間的低維線性不可分特征向量，轉化為低維輸入空間的核函數問題，巧妙避免了低維數據線性不可分與高維空間計算復雜度高的問題。隨著核方法研究的不斷深入，核方法不再局限于固定的核函數，核函數也被引入插值函數來擬合對象間的相似關系[5]。文獻[6]研究了核函數與插值函數的關系，Mercer定理要求核矩陣的半正定性，Shepard插值[7]利用距離倒數與統計學的原理確定核矩陣大大縮短了真實值與函數值的差距。對于插值擬合方法，訓練樣本數據越大通過該方法確定的函數值越準確。插值函數[8-10]在核方法中的應用得到持續研究，通過插值的方法不斷擬合出與數據特性相近的核函數，但是這些方法局限性大。將初等函數設為基函數，其組合方式變化性太大，并且當數據復雜度過大時，計算難度加大。然而分形插值利用數據間的自相似性，通過對已知數據訓練得到迭代系統進行經驗數據擬合。當已知數據越多獲得的數據的自相似性越貼近事實，同時分形插值在函數擬合中對于越復雜的數據擬合效果越好[1]。小樣本數據由于特征的多樣性具有較高的復雜性，利用分形插值擬合出來的核函數可以最大限度貼合數據本身屬性。但是由于分形插值具有對數據的依賴性，每一個訓練樣本需要確定一個分形函數，能夠使用滿足自身數據集要求的核函數。

1 理論基礎

1.1 支持向量機

定理1Mercer[4]定理。函數K是Rn×Rn→R的映射，且訓練樣本{x1,x2,…,xn}通過函數K得到的核函數矩陣為對稱半正定矩陣，則函數K為有效核函數。

對于數據集D={(x1,y1),(x2,y2),…,(xn,yn)}，其中xn∈RN為輸入特征向量；yn為數據標簽，即算法的評判指標。

將上述數據集特征向量通過非線性函數φ由低維特征向量空間映射到高維空間。在高維空間中利用風險最小化原理與分類間隔最大化思想，通過二次規劃對高維空間特征向量進行處理可表示為：

(1)

s.t.yi·(ω·φ(xi)+b)≥1-ζi

(2)

ζi≥0i=1,2,…,n

(3)

式中：ω為分類超平面的權值；b為分類超平面的偏值；ζi為非負松弛變量；C為懲罰參數。

通過求解上述問題的拉格朗日對偶，問題簡化為：

(4)

(5)

0≤ci≤Ci=1,2,…,n

式中：K(xi·xj)為滿足Mercer條件的核函數。因此可得最優分類面的決策函數為：

(6)

上述分析可知，支持向量機利用核函數來表示數據集通過非線性函數φ將低維空間向量映射到高維空間向量之間的關系，進而得到最優分類面與決策函數并產生影響。

1.2 分形插值

分形插值函數同初等函數一樣，是具有幾何特征與科學的“公式”，但是與初等函數相比，分形插值關注的是集合，而不是單純的點。分形插值的整體思想更能切合數據本身特性。該方法擺脫了初等函數的固定形式，能夠更好地擬合出與數據特征相近的函數。對于分形插值的定義及分形插值的確認方法如下。

定義1任意數據集{(xi,yi)∈R2|i=1,2,…,N}，其中x0

定理2對于給定數據集{(xi,yi)|i=0,1,…,N}建立迭代函數系統IFS。IFS={R2;Wn,n=1,2,…,N}，其中Wn的仿射變換如下：

(7)

并且

(8)

即：

(9)

式(9)有四個方程五個參數，依據文獻[1]可設dn為自由參量，|dn|<1，令L=xN-x0，則：

(10)

定理3設{N>1|N∈N*}，{R2;Wn,n=1,2,…,N}是數據集{(xn,yn)|n=0,1,…,N}的IFS，垂直定比因子dn滿足0≤dn<1(n=1,2,…,N)，則存在R2上等價于Euclid的度量d，使得這個IFS對應于d是壓縮的。特別地，存在唯一一個非空緊集G?R2，使得：

(11)

式中：f:[x0,xN]→R是連續函數且滿足：

f(xn)=ynn=0,1,…,N

(12)

對于二維數據分形插值通過對已知點的分析建立迭代系統，利用迭代系統建立連續函數f。該方法通過已知點找到數據集的相似關系通過擴展迭代找到集合內其他點的值，充分發揮已知點的作用并能夠更好地找到符合條件的分形曲線。

1.3 基于分形插值核函數的構造

1.3.1訓練樣本內積的確定

訓練樣本內積值在保障能夠反映同類樣本與異類樣本間的區別的同時要滿足Mercer性質。文獻[6]證明了訓練樣本的內積值確定的矩陣K只需滿足半正定的要求即可，并且訓練樣本間內積值的大小對實驗結果的影響并不大。因此本文選用1-0原則來區分同異類樣本，即同類樣本間的內積標記為1，異類樣本間的內積標記為0。該方法能夠有效地區分同異類樣本同時將同異類差距最大化。在分類超平面的角度分析，理論上可以將兩類超平面間的距離最大化進而保證分類的準確性。訓練樣本間的內積公式如下：

(13)

根據子空間原理與矩陣的基本原則，任意由訓練樣本獲得的訓練樣本內積值矩陣K均可變成如下形式：

很明顯該矩陣為半正定矩陣，滿足Mercer性質。傳統的核方法利用核函數確定核矩陣，例如線性核函數：K(x,y)=xTy+c，它是利用向量間的內積及近鄰原則來確定向量間關系的。在理論上分析，該方法會因為存在較大的交叉區域導致錯分的可能性。而利用本文內積值確定方法大大縮短了同類樣本的距離，同時拉大了異類樣本的距離，可以最大限度地避免錯分的可能性。

核方法從本質上是利用統計學的原理、近鄰原則與概率事件的結合。核方法通過核函數的形式對向量間的內積進行不定比例的縮放(即相似性度量)達到放大問題區域、縮小穩定空間的目的，以更好地使用近鄰原則，再通過概率事件(即每一個訓練樣本前的系數ω)與統計學原理對向量的類別進行預測分類。因此如何選擇合適的核函數以達到預期目的至關重要。

1.3.2分形插值核函數

核函數在一定層面可以看作兩個數據點的相似度量[11]。核函數本質是表達低維空間的數據映射到高維空間后的數據點之間的關系，而支持向量機通過計算已知數據點之間的關系建立分類面，再對未知數據點進行預測。核函數主要是通過改變數據點之間關系來增大預測的準確度。常用的核函數[12]有線性核函數、高斯核函數、多項式核函數和Sigmoid函數等，均通過擴大局部數據點關系差，縮短另一部分數據點關系差。理論上數據的親疏關系越明確則數據的分類精度越高，因此核函數主要是擴大易錯分空間的數據點的關系，核函數的選擇與參數的調節都是為了調節交叉空間數據與核函數坡度較大區域的關系[13]。本文針對交叉空間易錯分構建使用分形插值函數的分形插值核函數。

文獻[6]指出核矩陣的構建只要滿足核矩陣半正定即可，不需要有固定的核函數。因此本文的分形插值核函數沒有固定的核函數，屬于隱性核函數。

在疾病診斷技術逐漸發展的形勢下，臨床針對胃部疾病檢查患者在進行診斷期間，口服速溶胃腸超聲助顯劑超聲造影方法獲得廣泛應用，其憑借無痛苦、無創以及便捷有效的優點，使得臨床應用接受度以及滿意度極為顯著，并且在應用后通常可以獲得顯著胃部疾病診斷效果。胃部疾病檢查患者在選擇超聲助顯劑進行口服后，于其胃腸道內部會表現出點狀中等回聲的現象，并且形態分布均勻，從而可以將胃腸道超聲偽像顯著減少，針對胃壁病變具體程度、范圍、生長方式、腫物大小以及內部結構等可以進行清晰顯示，并且同附近臟器表現出的系列關系可以進行充分明確，此外針對胃腸功能加以動態觀察后，最終可以就患者病情表現展開評估工作[4]。

對于給定的數據集{(x1,y1),(x2,y2),…,(xn,yn)}隨機選取一定量的訓練樣本，要保證訓練樣本中不同類別樣本的數量，進而保證構建的分形插值函數的準確性。具體分段分形插值[14-15]公式如下：

(14)

式中：r為待測數據點與訓練數據點的距離；rφ為異類標簽對應的最短距離；rφ′為同類標簽對應的最長距離；fIFS為通過訓練樣本建立的分形插值函數。

分形插值函數的建立，訓練樣本中任意數據點(xk,yk)與其他數據點建立距離同異類關系(ri,fi)，其中：

(15)

ri為數據點xi與數據點xk的距離。

以ri的大小值對距離關系進行排序，找出rφ、rφ′的值對處于rφ、rφ′之間的距離關系利用式(7)-式(12)為每一個訓練樣本構建分形插值函數。

(16)

式中：r表示數據點x到數據點xj的距離。

(17)

2 實 驗

本節對本文算法的性能與有效性進行驗證，實驗仿真環境為MATLAB R2018a，運行于Intel(R) Core(TM) i5-700/2.50 GHz、8 GB內存，Windows 2007。本文實驗隨機選取每組樣本的80%為訓練樣本，其余為測試樣本。

2.1 算法比較

本節利用高斯核函數、線性核函數與本文算法通過UCI數據集進行實驗，驗證本文算法的有效性。用于驗證算法的數據集包括Breast Cancer Wisconsin(Diagnostic) Data Set、Wine Data Set、Glass Identification Data Set、User Knowledge Modeling Data Set、Iris Plants Data Set、Tic-Tac-Toe Endgame Data Set、Liver Disorders Data Set和Ionosphere Data Set八組數據集。實驗結果均采用十折交叉驗證，高斯核函數[16]和線性核函數[17]的公式分別為：

K(x,xi)=e(-‖x-xi‖2/2σ2)

(18)

K(x,xi)=xTxi+c

(19)

實驗數據集信息如表1所示。本文算法與兩種對比方法的比較結果如表2所示。圖1所示為不同算法在八個數據集上的分類效果，其中x軸的1-8分別代表數據集Breast Cancer Wisconsin(Diagnostic)、Wine、Glass Identification、User Knowledge Modeling、Iris Plants、Tic-Tac-Toe Endgame、Liver Disorders和Ionosphere。

表1 數據集

表2 3種算法的分類比較

圖1 不同算法分類效果比較

對表1和表2分析可知，當數據的特征數量越多時，本實驗的精度提升越大，相反特征數量越少精度提升越不明顯，由此論證了本文之前提到的分形插值的特點：數據的復雜度越高，分形插值函數越逼近真實函數。由圖1可以明顯地看出，本文算法相較于高斯核函數和線性核函數有較大的精度優勢，并且不同類型的核函數，其度量特征各異，本文算法可克服核函數選擇與參數設置的影響。

2.2 同數據對比實驗

本實驗通過對同一數據下不同數量的訓練樣本進行實驗。比較不同數量的訓練樣本對實驗結果的影響。本實驗數據來自UCI的Iris Plants Data Set，本實驗將鳶尾花的訓練樣本數量分別設為10、20、30、40和50，測試數量為100，通過5次實驗取平均值的方法來測試比較本文算法與高斯核函數、線性核函數在同等的條件下，隨著訓練樣本數量變化，分類準確率的變化，結果如表3和圖2所示。

表3 鳶尾花分類準確率結果

圖2 鳶尾花不同數量訓練樣本分類精度

由圖2可以看出，隨著訓練樣本的增多，高斯核函數與線性核函數先增長后逐漸持平，而本文算法緩慢增長且精度高于另兩個算法。該實驗的結果表明，隨著訓練樣本數據的增多，通過分形插值方法擬合的數據集的分形插值函數與數據本身特性更貼切。因此本文算法優于傳統核函數算法。

2.3 與相關文獻比較

本實驗在近幾年支持向量機核函數文獻中隨機選取文獻的數據集及實驗結果。選取文獻[18-19]的部分數據集并利用本文算法進行仿真實驗。其中使用的數據集有Haberman Data Set、Ionosphere Data Set、Energy Efficiency、Sonar Data Set、Cancer Data Set，通過本文算法為各個樣本數據建立分段分形插值，然后得到分類結果。本文算法與其他文獻方法的分類結果比較見表4。

表4 算法分類精度比較

可以看出，在上述五組數據集中本文算法的實驗結果皆優于文獻[18-19]的分類精度，故本文算法有很好的參考意義。

3 結 語

本文利用分形插值思想、分段函數和概率分布，并結合相似度量特性充分發揮數據集本身度量特性，提出了一種基于分形插值的支持向量機核函數構造的方法。通過每個訓練樣本與其他樣本之間的關系，為每一個訓練樣本建立合適的核函數，打破了固定核函數的模式與Shepard插值核函數大數統計學概率的模式。通過建立數據間的關系擬合出合適的函數關系圖像，擺脫了核函數選擇與參數設置的繁瑣與影響。通過對UCI數據的仿真實驗對比，論證了本文算法的可行性。但是本文算法仍有不足之處，由于沒有固定函數公式，訓練樣本時需要確定每個樣本的迭代系統，在確定測試樣本值時需要通過IFS迭代仿射確定，因此本文算法計算的復雜度較高，運行時間較長。此外，本文利用特征向量間的距離為相似度量關系，在傳統核函數中線性核函數和多項式核函數是通過對特征向量內積的度量方式來衡量數據間的關系。同時多核核函數多是以線性核函數、高斯核函數和多項式核函數為基核函數。因此使用不同的特征向量間的相似度量關系進行核函數分類實驗及多種度量關系結合在一起的方式進行仿真實驗是未來研究的主要任務。