Page 343 - 《软件学报》2025年第10期

4740 软件学报 2025 年第 36 卷第 10 期

如果 x 1 ,..., x s 是已知的, 那么公式 (11) 仅包含优化变量 (α k ,b 1 ,ξ i ). 为了有效地求解公式 (11) 和公式 (12), 需要探

索 X 中的适当离散点. 不同于求解 SFM 的算法, 本文利用采样策略取得 x 1 ,..., x s 和 ¯ x 1 ,..., ¯ x s . 常用的采样方式是
s
从集值对象 A i (i = 1,...,n) 中采样 个数据点. 在后面的实验部分, 通过实验验证了这种采样策略可取得令人满意
s
的结果. 因为 α 和 β 采用了 L1 范数的约束, 所以 α 和 β 中的元素是稀疏的. 当 个采样点给定时, 本文采用下面的
优化问题取得巴拿赫空间的超平面:

  s  2
 1 l ∑ ∑  n ∑ s ∑
  
  
 min w i   σ i (x k )α k +b 1 +c 1 w i ξ i +c 2 |α k |



 α k ,b 1 ,ξ i 2  

 i=1 k=1 i=l+1 k=1
 (13)
  

 s

 ∑  ξ i
    
  σ i (x k )α k +b 1 ⩽ 1+ , i = l+1,...,n

 s.t. 1−ξ i ⩽ y i 
  
 τ
k=1


  2
 n ∑ s l ∑ s ∑
 1 ∑ 
  
 min     |β k |

 w i  σ i (¯ x k )β k +b 2 +c 3 w i ξ i +c 4
 β k ,b 2 ,ξ i 2  


 i=l+1 k=1 i=1 k=1
(14)

  

 s
 ∑ 
 ξ i
  
  σ i (¯ x k )β k +b 2 ⩽ 1+ , i = 1,...,l

 s.t. 1−ξ i ⩽ y i   

  
 τ
k=1
从公式 (13) 和公式 (14) 可知它们是凸优化模型. 如果 α k , 0, 将相应的采样点 x k 称为公式 (13) 的支持向量.
如果 β k , 0, 将相应的采样点 ¯ x k 称为公式 (14) 的支持向量. 与 TSVM 不同, TSFM 的支持向量取决于采样点. 由于
公式 (13) 和公式 (14) 有相似的形式, 下面主要讨论公式 (13) 的优化问题. 为了处理公式 (13) 中的绝对值符号, 这
里引入了非负优化变量 ¯ α k 和 ˆ α k . 设 ¯ α k + ˆα k = |α k | 和 ¯ α k − ˆα k = α k , 其中, ¯ α k ⩾ 0, ˆα k ⩾ 0, k = 1,..., s. 这样公式 (13) 被转
化成下面形式:

  s  2
 1 l ∑ ∑  n ∑ s ∑
  
  
 min w i   σ i (x k )(¯α k − ˆα k )+b 1 +c 1 w i ξ i +c 2 (¯α k + ˆα k )


 ¯α k ,ˆα k ,b 1 ,ξ i 2  


 i=1 k=1 i=l+1 k=1
 (15)

  s 

 ∑ 
   ξ i
  
  σ i (x k )(¯α k − ˆα k )+b 1 ⩽ 1+ , i = l+1,...,n

 s.t. 1−ξ i ⩽ y i 
  
 τ
k=1
公式 (15) 是一个二次规划问题. 利用二次规划的优化算法可求解凸优化问题公式 (15). 对于凸优化问题, 可通
过探索对偶解来验证原问题解的最优性, 这需要推导出 公式 (15) 的对偶形式. 首先公式 (15) 被转化成下面形式:

 l ∑ n ∑ s ∑
 1
 2
 min w i (u i ) +c 1 w i ξ i +c 2 (¯α k + ˆα k )


 ¯α k ,ˆα k ,b 1 ,ξ i ,u i 2


 i=1 i=l+1 k=1





 
 s ∑
 
 
 u i =

 σ i (x k )(¯α k − ˆα k )+b 1
 
 
 
 (16)
  k=1

 
 
 
   
  s

∑ 
   ξ i
 s.t. 
   
 1  σ i (x k )(¯α k − ˆα k )+b 1 ⩽ 1+ , i = l+1,...,n

 −ξ i ⩽ y i 

   
  τ
 
  k=1
 
 
 
 
 
 
  ¯ α k ⩾ 0, ˆα k ⩾ 0
根据公式 (16) 定义下面的拉格朗日函数:

  s 
1 l ∑ n ∑ s ∑ n ∑   ∑ 
2



L(¯α k , ˆα k ,b 1 ,ξ i ,u i ) = w i (u i ) +c 1 w i ξ i +c 2 (¯α k + ˆα k )+ ¯ γ i 1−ξ i −y i    σ i (x k )(¯α k − ˆα k )+b 1



2   
i=1 i=l+1 k=1 i=l+1 k=1
     
n s s
s ∑ s ∑
 ∑  ∑   ∑
l ∑ 
     ξ i 
+ γ i u i − σ i (x k )(¯α k − ˆα k )+b 1+ ˆ γ i y i  σ i (x k )(¯α k − ˆα k )+b 1−1−   − ˆ θ k ˆα k − ¯ θ k ¯α k (17)

 





 

     τ 
i=1 k=1 i=l+1 k=1 k=1 k=1
, ,
,
其中, γ i (i = 1,...,l) ¯γ i ˆγ i (i = l+1,...,n) ¯ θ, ˆ θ k (k = 1,..., s) 是拉格朗日乘子. 将公式 (17) 的拉格朗日函数关于 ¯ α k , ˆα k ,
ξ i ,u i 和 b 1 的导数设定为 0, 那么可取得: