﻿ 基于不等距超平面距离的模糊支持向量机
 计算机系统应用  2020, Vol. 29 Issue (10): 185-191 PDF

Fuzzy Support Vector Machine Algorithm Based on Inequality Hyper-Plane Distance
LI Cun-He, JIANG Yu, LI Shuai
Computer Science and Technology, China University of Petroleum, Qingdao 266580, China
Foundation item: Natural Science Foundation of Shandong Province (ZR2014FQ018)
Abstract: In the age of the big data and artificial intelligence, Support Vector Machine (SVM) has been successfully applied in many aspects and becomes one of the common methods to solve classification problems. But the real world data is usually imbalanced, making its performance of classification significantly decreased. This study proposes to improve original standard Fuzzy Support Vector Machine (FSVM) by using inequality hyper-plane distance. The algorithm introduces parameter λ to controls the distance between hyper-plane and categories, and constructs fuzzy membership function by calculating sample mutually center distance, which can improve the falling precision of classification caused by imbalanced distribution of sample and noise data. The effectiveness of the proposed algorithm is verified by experiments, and the result shows that the proposed algorithm has a better effect of imbalanced data.
Key words: Support Vector Machine (SVM)     imbalanced data     inequality hyper-plane distance     membership function

1 相关工作

2 不等距超平面距离改进的模糊支持向量机(IFD-FSVM)

 $\min\;\;\;\frac{1}{2}||\omega |{|^2} + C\sum\limits_{i = 1}^l {{u_i}} {\varepsilon _i}$ (1)

 $\left\{ {\begin{array}{*{20}{l}} {{y_i}({\omega ^{\rm{T}}}{x_i} + b) \ge 1 - {\varepsilon _i}}\\ {{\varepsilon _i} \ge 0,\;i = 1, \cdots ,l} \end{array}} \right.$ (2)

 $f({\rm{x}}) = sign\left\{ {\displaystyle\sum\limits_{i = 1}^m {\alpha _i^*{y_i}K\left( {x,{x_i}} \right) + {b^*}} } \right\}$ (3)
 $0 \le {a_i} \le {\mu _i}C\;\;\;i = 1,\cdots,l$ (4)

$K\left( {x,{x_i}} \right)$ 为核函数, 常见的核函数有线性核函数、多项式核函数、高斯核函数等, 在求解过程中核函数的选择要视数据集性质而定.

 $\min\;\;\;\frac{1}{{1 + \lambda }}||\omega |{|^2} + C\sum\limits_{i = 1}^l {{u_i}} {\varepsilon _i}$ (5)

 $\left\{ \begin{array}{l} {y_i}[({\omega ^{\rm T}}{x_i}) + b] - \lambda + {\varepsilon _i} \ge 0\;\;\;{y_i} = 1 \\ {y_i}[({\omega ^{\rm T}}{x_i}) + b] + 1 + {\varepsilon _i} \le 0\;\;\;{y_i} = - 1 \\ {\varepsilon _i} \ge 0\;\;\;i = 1,\cdots,l \\ \end{array} \right.$ (6)

 $\begin{split} L(\omega ,b,\varepsilon ,a,\beta ) = & \frac{1}{{1 + \lambda }}||\omega |{|^2} + C \displaystyle \sum\limits_{i = 1}^l {{u_i}} {\varepsilon _i} \\ &- \left\{ { \displaystyle \sum\limits_{{{\rm{y}}_i} = 1}^{} {{a_i}} {y_i}[({\omega ^{\rm T}}{x_i} + b) - \lambda + {\varepsilon _{\rm{i}}}] } \right.\\ &+\left. {\displaystyle \sum\limits_{{y_i} = - 1} {{a_i}{y_i}[({\omega ^{\rm T}}x{}_i + b) - } {1 \rm{ + }}{\varepsilon _i}]} \right\} - \displaystyle \sum\limits_{i = 1}^l {{\beta _i}} {\varepsilon _i} \\ \end{split}$ (7)

 $\left\{ \begin{array}{l} \dfrac{{\partial L(\omega ,b,\varepsilon ,a,\beta )}}{{\partial \omega }} = \dfrac{1}{{2(1 + \lambda )}}\omega - \displaystyle\sum\limits_{i = 1}^l {{a_i}} {x_i}{y_i} = 0\\ \dfrac{{\partial L(\omega ,b,\varepsilon ,a,\beta )}}{{\partial b}} = \displaystyle\sum\limits_{i = 1}^l {{a_i}} {y_i} = 0\\ \dfrac{{\partial L(\omega ,b,\varepsilon ,a,\beta )}}{{\partial {\varepsilon _i}}} = {u_i}C - {a_i} - \beta = 0 \end{array} \right.$ (8)

 $\max\;\;\;\sum\limits_{{y_i} = 1} {\lambda {a_i}} + \sum\limits_{{y_i} = - 1} {{a_i}} - \frac{{1 + \lambda }}{4}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {{y_i}} } {y_j}{a_i}{a_j}({x_i},{x_j})$ (9)

$\displaystyle \sum\limits_{i = 1}^l {{y_i}} {a_i} = 0$ 得到于 $\displaystyle \sum\limits_{j = 1} {{a_i}} = \sum\limits_{j = - 1} {{a_i}}$ , 化简式(9)得到:

 $\begin{split} & \displaystyle\sum\limits_{{y_i} = 1} {\lambda {a_i}} + \displaystyle \sum\limits_{{y_i} = - 1} {{a_i}} - \frac{{1 + \lambda }}{4}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {{y_i}} } {y_j}{a_i}{a_j}({x_i}*{x_j}) = \\ & \frac{{1 + \lambda }}{2}\left\{ \displaystyle \sum\limits_{i = 1}^l {{a_i}} - \frac{1}{2}\sum\limits_{i = 1}^l {\sum\limits_{j = 1}^l {{y_i}} } {y_j}{a_i}{a_j}{\rm{(}}{x_i}*{x_j}{\rm{)}}\right\} \\ \end{split}$ (10)

 $f(x) = sign\left\{ \frac{{1 + \lambda }}{2}[\sum\limits_{{x_i} \in SV} {{a_i}} {y_i}K({x_i},x) + {b^{\rm{*}}}]\right\}$ (11)
 $0 \le {a_i} \le {u_i}C\;\;\;i = 1,\cdots,l$ (12)

$\lambda$ 的值影响超平面与类之间的空间距离, 若0< $\lambda$ <1, 则超平面与正类间的空间距离较小; 若 $\lambda$ >1, 则超平面与负类之间的空间距离较小; 若 $\lambda$ =1该算法等同于标准的模糊支持向量机.

3 确定隶属度函数

 图 1 样本的空间分布

 $m = \frac{1}{n}\sum\limits_{i = 1}^n {\varphi ({x_i})}$ (13)
 $\begin{array}{*{20}{l}} {d = |{m_ + } - {m_ - }| = {{\left( {\left| {\displaystyle\sum\nolimits_{{x_ + } \in {X_ + }} {\varphi ({x_ + })} /{n_ + } - \displaystyle\sum\nolimits_{{x_ - } \in {X_ - }} {\varphi ({x_ - })} /{n_ - }} \right|_2^2} \right)}^{\dfrac{1}{2}}} }\\ ={{{\left( {{\displaystyle\sum _{\begin{array}{*{20}{c}} {{x_{ + i}} \in {X_ + }}\\ {{x_{ + j}} \in {X_ + }} \end{array}}}K({x_{ + i}},{x_{ + j}})/n_ + ^2 + {\displaystyle\sum _{\begin{array}{*{20}{c}} {{x_{ - p}} \in {X_ - }}\\ {{x_{ - q}} \in {X_ - }} \end{array}}}K({x_{ - p}},{x_{ - q}})/n_ - ^2 - 2{\displaystyle\sum _{\begin{array}{*{20}{c}} {{x_{ + m}} \in {X_ + }}\\ {{x_{ - n}} \in {X_ - }} \end{array}}}K({x_{ + m}},{x_{ - n}})/{n_ + }{n_ - }} \right)}^{\dfrac{1}{2}}}} \end{array}$ (14)
 $\begin{array}{l} d_{ip}^ + = |\varphi ({x_ + }) - {m_ + }| = {\left( {\left| {\varphi ({x_ + }) - \displaystyle \sum\limits_{{x_{_ + }} \in {X_ + }} {\varphi ({x_ + })} /{n_ + }} \right|_2^2} \right)^{\dfrac{1}{2}}} {\rm{ = }} \left( {K({x_ + },{x_ + }) + \displaystyle \sum\limits_{\begin{array}{*{20}{c}} {{x_{ + p}} \in {X_ + }}\\ {{x_{ + q}} \in {X_ + }} \end{array}} {K({x_{ + p}},{x_{ + q}})} /n_ + ^2 - 2 \displaystyle \sum\limits_{{x_{ + m}} \in {X_ + }} {K({x_ + },{x_{ + m}})} /{n_ + }} \right)^{\dfrac{1}{2}} \end{array}$ (15)
 $\begin{array}{l} d_{ip}^ - = |\varphi ({x_ + }) - {m_ - }| = {\left( {\left| {\varphi ({x_ + }) - \displaystyle \sum\limits_{{x_{_ + }} \in {X_ - }} {\varphi ({x_ - })} /{n_ - }} \right|_2^2} \right)^{\dfrac{1}{2}}} {\rm{ = }} \left( {K({x_ + },{x_ + }) + \displaystyle \sum\limits_{\begin{array}{*{20}{c}} {{x_{ - p}} \in {X_ - }}\\ {{x_{ - q}} \in {X_ - }} \end{array}} {K({x_{ - p}},{x_{ - q}})} /n_ - ^2 - {{2 \displaystyle \sum\limits_{{x_{ - m}} \in {X_ - }} {K({x_ + },{x_{ - m}})} } / {{n_ - }}}} \right)^{\dfrac{1}{2}} \end{array}$ (16)
 $\begin{array}{l} d_{in}^ - = |\varphi ({x_ - }) - {m_ - }| = {\left( {\left| {\varphi ({x_ - }) - \displaystyle \sum\limits_{{x_{_ - }} \in {X_ - }} {\varphi ({x_ - })} /{n_ - }} \right|_2^2} \right)^{\dfrac{1}{2}}} {\rm{ = }} \left( {K({x_ - },{x_ - }) + \displaystyle \sum\limits_{\begin{array}{*{20}{c}} {{x_{ - p}} \in {X_ - }}\\ {{x_{ - q}} \in {X_ - }} \end{array}} {K({x_{ - p}},{x_{ - q}})} /n_ - ^2 - 2 \displaystyle \sum\limits_{{x_{ - m}} \in {X_ - }} {K({x_ - },{x_{ - m}})} /{n_ - }} \right)^{\dfrac{1}{2}} \end{array}$ (17)
 $\begin{array}{l} d_{in}^ + = |\varphi ({x_ - }) - {m_ + }| = {\left( {\left| {\varphi ({x_ - }) - \displaystyle \sum\limits_{{x_{_ + }} \in {X_ + }} {\varphi ({x_ + })} /{n_ + }} \right|_2^2} \right)^{\dfrac{1}{2}}} {\rm{ = }} \left( {K({x_ - },{x_ - }) + \displaystyle \sum\limits_{\begin{array}{*{20}{c}} {{x_{ + p}} \in {X_ + }}\\ {{x_{ + q}} \in {X_ + }} \end{array}} {K({x_{ + p}},{x_{ + q}})} /n_ + ^2 - 2\displaystyle \sum\limits_{{x_{ + m}} \in {X_ + }} {K({x_ - },{x_{ + m}})} /{n_ + }} \right)^{\dfrac{1}{2}} \end{array}$ (18)

1) 计算样本中心点之间的距离 $\scriptstyle d$ ,计算正类样本的互距离 $\scriptstyle d_{ip}^ -$ ;

2) 比较样本距离与样本互距离的大小:若 $\scriptstyle d_{ip}^ - > d$ , 样本大都位于图1深色区域外部分,若 $\scriptstyle d_{ip}^ - \le d$ , 样本大都位于图1深色区域内部分;

3) 取 $\scriptstyle d_{ip}^ - \le d$ 的样本点计算其 $\scriptstyle d_{ip}^ +$ , 将其中的最大值记为 $\scriptstyle {R^ + }$ .

4) 同理得到负类样本的 $\scriptstyle {R^ - }$ .

 $\left\{ \begin{array}{l} {s_{ip}} = {{d_{ip}^ + } / {{R_ + }}},d_{ip}^ - \le d\\ {s_{ip}} = \delta ,d_{ip}^ - > d \end{array} \right.{y_i} = 1$ (19)
 $\left\{ \begin{array}{l} {s_{in}} = {{d_{in}^ - } / {{R_ - }}},d_{in}^ + \le d\\ {s_{in}} = \delta ,d_{in}^ + > d \end{array} \right.{y_i} = - 1$ (20)
4 实验结果与分析

TN代表实为负类且分类结果为负类的样本, FN代表实为负类但分类结果为正类的样本,FP代表实为正类但分类结果为负类的样本.

SVM算法: 等距超平面且没有将隶属度函数应用于支持向量机.

FSVM算法: 等距超平面线性隶属度函数的模糊支持向量机.

IFD-FSVM算法: 应用不等距超平面距离的改进模糊支持向量机.

 图 2 负类样本分类准确率对比

 图 3 负类样本回归率对比

 图 4 正类样本分类准确率对比

5 结论与展望

 [1] Vapnik VN. Statistical Learning Theory. New York: Wiley, 1998. [2] Bhalla VK, Kumar N. An efficient scheme for automatic web pages categorization using the support vector machine. New Review of Hypermedia and Multimedia, 2016, 22(3): 223-242. DOI:10.1080/13614568.2016.1152316 [3] Zeng M, Zou BJ, Wei FR, et al. Effective prediction of three common diseases by combining SMOTE with Tomek links technique for imbalanced medical data. Proceedings of 2016 IEEE International Conference of Online Analysis and Computing Science (ICOACS). Chongqing, China. 2016. 225–228. [4] 于巧, 姜淑娟, 张艳梅, 等. 分类不平衡对软件缺陷预测模型性能的影响研究. 计算机学报, 2018, 41(4): 809-824. DOI:10.11897/SP.J.1016.2018.00809 [5] Elleuch M, Maalej R, Kherallah M. A new design based-SVM of the CNN classifier architecture with dropout for offline Arabic handwritten recognition. Procedia Computer Science, 2016, 80: 1712-1723. DOI:10.1016/j.procs.2016.05.512 [6] 魏鑫, 张雪英, 李凤莲, 等. 面向非平衡数据集分类的改进模糊支持向量机. 计算机工程与设计, 2019, 40(11): 3124-3129. [7] Han H, Wang WY, Mao BH. Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning. Proceedings of 2005 International Conference on Advances in Intelligent Computing. Hefei, China. 2005. 878–887. [8] 李勇, 刘战东, 张海军. 不平衡数据的集成分类算法综述. 计算机应用研究, 2014, 31(5): 1287-1291. DOI:10.3969/j.issn.1001-3695.2014.05.002 [9] 鞠哲, 曹隽喆, 顾宏. 用于不平衡数据分类的模糊支持向量机算法. 大连理工大学学报, 2016, 56(5): 525-531. DOI:10.7511/dllgxb201605013 [10] Elkan C, Noto K. Learning classifiers from only positive and unlabeled data. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, NV, USA. 2008. 213–220. [11] Dal Pozzolo A, Caelen O, Johnson RA, et al. Calibrating probability with undersampling for unbalanced classification. Proceedings of 2015 IEEE Symposium Series on Computational Intelligence. Cape Town, South Africa. 2015.159–166. [12] 魏力, 张育平. 一种改进型的不平衡数据欠采样算法. 小型微型计算机系统, 2019, 40(5): 1094-1098. DOI:10.3969/j.issn.1000-1220.2019.05.032 [13] 张菲菲, 王黎明, 柴玉梅. 一种改进过采样的不平衡数据集成分类算法. 小型微型计算机系统, 2018, 39(10): 2162-2168. DOI:10.3969/j.issn.1000-1220.2018.10.006 [14] Li BY, Hu JL, Hirasawa K. Support vector machine classifier with WHM offset for unbalanced data. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2008, 12(1): 94-101. DOI:10.20965/jaciii.2008.p0094 [15] 刘艳, 钟萍, 陈静, 等. 用于处理不平衡样本的改进近似支持向量机新算法. 计算机应用, 2014, 34(6): 1618-1621. DOI:10.11772/j.issn.1001-9081.2014.06.1618 [16] Wang Z, Zhu YW, Chen ZZ, et al. Multi-view learning with fisher kernel and bi-bagging for imbalanced problem. Applied Intelligence, 2019, 49(8): 3109-3122. DOI:10.1007/s10489-019-01428-1 [17] Malyscheff AM, Trafalis TB. Kernel classification using a linear programming approach. Annals of Mathematics and Artificial Intelligence, 2020, 88(1): 39-51. [18] Wang F, Liu SJ, Ni WC, et al. Imbalanced data classification algorithm with support vector machine kernel extensions. Evolutionary Intelligence, 2019, 12(3): 341-347. DOI:10.1007/s12065-018-0182-0 [19] Li YJ, Guo HX, Liu X, et al. Adapted ensemble classification algorithm based on multiple classifier system and feature selection for classifying multi-class imbalanced data. Knowledge-Based Systems, 2016, 94: 88-104. DOI:10.1016/j.knosys.2015.11.013 [20] Abdi L, Hashemi S. To combat multi-class imbalanced problems by means of over-sampling and boosting techniques. Soft Computing, 2015, 19(12): 3369-3385. DOI:10.1007/s00500-014-1291-z [21] Lin Cf, Wang SD. Fuzzy support vector machines. IEEE Transactions on Neural Networks, 2002, 13(2): 464-471. DOI:10.1109/72.991432 [22] Zhang JJ, Zhong P. Learning biased SVM with weighted within-Class scatter for imbalanced classification. Neural Processing Letters, 2020, 51(1): 797-817. DOI:10.1007/s11063-019-10096-8 [23] Liu KM, Wu XJ. Fuzzy support vector machines based on collaborative representation. Proceedings of the 11th International Conference on Natural Computation. Zhangjiajie, China. 2015. 64–68. [24] Zhou XL, Jiang PY, Wang XX. Recognition of control chart patterns using fuzzy SVM with a hybrid kernel function. Journal of Intelligent Manufacturing, 2018, 29(1): 51-67. DOI:10.1007/s10845-015-1089-6 [25] 杨志民, 王甜甜, 邵元海. 面向不均衡分类的隶属度加权模糊支持向量机. 计算机工程与应用, 2018, 54(2): 68-75. DOI:10.3778/j.issn.1002-8331.1609-0112