[發明專利]一種基于迭代聚集網格搜索算法的支持向量回歸模型

在審

• 申請號: 202011286631.6
• 申請日: 2020-11-17
• 公開（公告）號: CN112330044A
• 公開（公告）日: 2021-02-05
• 發明（設計）人: 車金星;冼華鋒;劉娜;葉雨
• 申請（專利權）人: 南昌工程學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/06;G06N20/10
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 楊采良

1.一種基于迭代聚集網格搜索算法的支持向量回歸模型，其特征在于，包括以下步驟：

S1：支持向量回歸的函數定義為：

f(x)＝ωψ(x)+b (1)

其中，ω為權重向量,b為常數，以下表達式被定義為優化函數；

稱為ε-不敏感損失函數，ε為管道寬度，C是懲罰因子，因此，引入兩個松弛因子ξ和ξ^*，可以得到如下表達式：

上述優化函數是一個二次規劃問題，根據前面的算法，將此二次規劃問題引入Lagrange乘子，并轉化為其對偶空間進行求解：

因此，原優化問題可以轉化為無約束形式，優化目標滿足KKT條件，即利用Lagrange對偶將優化問題轉化為等價對偶問題，求解過程是：首先求優化函數L對ω,b,ξ,ξ^*的最小值，接著求優化函數L對拉格朗日乘子α,α^*,β,β^*的最大值；以上過程需要滿足KKT條件；最終，得到了支持向量回歸的解為

S2：使用RBF核函數：K(x_i,x_j)＝exp(-γ||x_i-x_j||²) (7)

在建模之前需要確定三個參數(C，γ，ε)；

S3：網格搜索法：在網格搜索法中，設網格中參數C、γ和ε的所有可能取值的數量為K、L和M，則三維網格的點數量為K*L*M，因此，網格搜索法的參數優化的時間復雜度可由以下表達式給出：

T₁(n)＝O(K*L*M) (8)

假設K＝L＝M,則等式(8)可以轉換為：

T₁(n)＝O(K³) (9)

為了得到一個好的參數組合，K，L，M通常設置得非常大，因此網格搜索法的時間復雜度是一個非常大的值；

S4：迭代聚集網格搜索：在首次迭代中，算法在一個相對較大的網格區域內搜索最優子區域。然后，隨著算法的迭代，在最優子區域中再次搜索最優子區域，從而實現了有網格區域的動態聚集。由于這種搜索策略沒有在整個網格范圍內執行精細搜索，因此可以顯著降低算法的時間復雜度。

2.根據權利要求1所述的基于迭代聚集網格搜索算法的支持向量回歸模型，其特征在于：所述步驟S4的迭代聚集網格搜索算法包括以下步驟：

輸入：

訓練數據集：D；

參數搜索區間：a^h≤(C,γ,ε)≤b^h；

每個維度的網格點數：g；停止閾值：δ

輸出：

SVR模型的全局最優參數組合：(C^*,γ^*,ε^*)

算法的總迭代次數：T

步驟1：計算參數的取值間隔(步長)：λ

步驟2：生成參數的所有取值；

步驟3：以三個參數的所有取值構建一個三維網格；

步驟4：使用網格中的點建立SVR模型；

步驟5：計算適應度；

步驟6：獲取最優適應度；

步驟7：獲取最優適應度對應的參數組合；

步驟8：計算誤差變化量：e；

步驟9：If e＜δ,Then返回全局最優參數組合(C^*,γ^*,ε^*)和總迭代次數；

Else,更新搜索區間:(a^h+1,b^h+1),回到步驟1。

3.根據權利要求2所述的基于迭代聚集網格搜索算法的支持向量回歸模型，其特征在于：所述迭代聚集網格搜索算法中需要確定網格搜索區域中的網格點個數，即確定每個維度的網格點數，用g表示，則整個網格搜索區域中的網格點總數為g³；將g參數設置為10，因此，網格點總數為10³＝1000。因此，迭代聚集網格搜索算法的參數優化的時間復雜度可以得到如下：

T₂(n)＝O(T*g³) (10)

其中，T是算法的總迭代次數；一般來說，g＜＜K；這樣我們就可以得到：

T₂(n)＝O(T*g³)＜＜T₁(n)＝O(K³) (11)

因此，迭代聚集網格搜索可以大大降低時間復雜度，并且得到最優解；假設在第h次迭代中，搜索區間如下：

根據給定的g參數，我們可以計算參數的取值間距(步長)，如下式所示：

根據步長可以生成參數的所有取值，分別保存到數組里；參數的所有取值如下所示：

這樣，以參數γ的所有取值為x軸，參數C的所有取值為y軸，參數ε的所有取值為z軸建立一個三維網格，這樣每個網格點代表一個參數組合。網格中的每個參數組合均被用來建立SVR模型，然后計算參數組合的適應度。當遍歷了所有的網格點后，也就得到了一個g×g×g的三維適應度矩陣。為了方便展示，我們在此只以參數C和參數γ的二維矩陣為例。經過一次迭代，我們可以得到一個適應度矩陣，用M表示；

上標h表示第h次迭代。這樣，通過min()函數就可以得到適應度矩陣中的最優適應度，用minMAE表示。當前最優適應度對應的參數組合用(C′,γ′,ε′)表示，稱為局部最優參數組合。也就是說，在本次迭代中，用該參數組合所建立的SVR模型的性能最好，則表明(C′,γ′,ε′)是最好的參數。獲取矩陣中最小的值可以用式(16)表示；min()函數由Python自帶的工具包提供；

minMAE^h＝min(M^h) (16)

同理，再經過一次迭代，可以得到在該次迭代中的最優適應度。這樣，誤差變化量可以由式(17)給出；注意，算法在第二次迭代后才開始計算誤差變化量；

e＝|minMAE^h+1-minMAE^h| (17)

更新搜索區間：

在計算出誤差變化量后，需要判斷是否滿足停止條件。如果滿足停止條件，則全局最優參數組合，用(C^*,γ^*,ε^*)表示，為局部最優參數組合，即

(C^*,γ^*,ε^*)＝(C′,γ′,ε′) (18)

如果不滿足停止條件，則需要更新搜索區間。分為三種情況：假如C′剛好落于搜索區間的上界，則參數C的搜索區間上界b_c不變。假如C′剛好位于搜索區間的下界，則參數C的搜索區間下界a_c不變。假如C′位于搜索區間的內部，則新的搜索區間將以步長λ_c為單位聚集到C′的周圍，式給出了新的搜索區間；

同理，參數γ和參數ε的新的搜索區間也可以得到，如式所示；

這樣，隨著算法的迭代，網格區域朝著全局最優參數組合的方向逐漸聚集。因為g參數是一個常數，所以步長將會變得越來越小，從而實現精細的搜索。