双最小二乘支持向量数据描述
张仙伟 邢佳瑶
摘 要：为了提高标准支持向量数据描述的分类精度和分类时间，构造双最小二乘支持向量数据描述，并对比分析在不同样本集上的分类性能以及分类性能随参数和样本规模的变化。在训练阶段，双最小二乘支持向量数据描述应用等式约束代替标准算法中的不等式约束，通过求解线性方程组而非凸二次规划得到正负2类样本的超球形描述边界，进而设计一个分段函数作为分类规则;在测试阶段，计算待测样本到正负2类样本的最小包围超球球心的距离，并根据距离的最小值选取相应的分类规则。数值试验结果表明双最小二乘支持向量数据描述的有效性和优越性。在基准数据集上，双最小二乘支持向量数据描述的分类精度比标准算法高1.68%，而分类时间仅为标准算法的16.51%;在正态分布数据集上，双最小二乘支持向量数据描述具有比标准算法高的分类精度和短的分类时间，而分类时间上的优势在大规模样本集上更加明显，其在2 000个和10 000个样本集上的分类时间为标准算法的78.06%和18.69%。
关键词：双最小二乘支持向量数据描述;等式约束;线性方程组;超球形边界;分段分类规则;最小距离
中图分类号：TP 301
文献标志码：A
文章编号：1672-9315（2021）03-0559-07
DOI：10.13800/j.cnki.xakjdxxb.2021.0322
Abstract：To improve the performances of standard support vector data description，this paper constructs the double least square support vector data description（DLSSVDD）and makes a comparison with the standard algorithm with respect to the classification accuracies and time on various data sets，as well as an analysis of the variances with the data scale.In the training process，DLSSVDD utilizes the equality constraints to substitute the inequality constraints，figures out two hyperspheres description boundaries for the positive and negative class by solving a linear equation system instead of the convex program，with a piece-wise function as the classification rule designed.In the testing process，the distances are calculated of the test sample to the minimum enclosing hyperspheres center for the positive and negative class，and the classification rules are selected corresponding to the minimum value.Numerical results demonstrate the effectiveness and superiority of DLSSVDD.On the benchmark data set，DLSSVDD has a classification accuracy 1.68% higher than SVDD，which has the training time 16.51% of SVDD.On the normal distribution data，DLSSVDD has higher accuracies and lower training time than SVDD，and the advantages are more significant on large scale data;DLSSVDD has the classification time 78.06% and 18.69% of the standard algorithm on the sample sets with a scale of 2 000 and 10 000.
Key words：double least square support vector data description;equality constraint;linear system of equation;hypersphere boundary;piece-wise classification rule;minimum distance
0 引 言
TAX提出支持向量數据描述（support vector data description，SVDD）[1]算法，在单值分类领域得到了广泛应用。陆从德将SVDD推广至分类领域，根据数据的描述边界进行分类并采用乘性规则求解[2]。从提高SVDD求解速度入手，ZHAO F等构造一种简化算法，寻求特征空间中支持向量的基函数以提高测试速度[3]。LAN J C将SVDD算法拓宽应用于在模拟电路，并通过独立成分分析进行特征选择以提高训练速度[4]。NIAZMARDI S等利用SVDD改进模糊C均值聚类算法，并用于无监督高光谱数据分类[5]。PENG X J等设计避免矩阵求逆的运算方法，提高传统SVDD的分类精度[6]。刘富等从提高分类精度角度，设计根据位置分布构造可变惩罚参数的方法[7]。CAO J等拓宽SVDD用于癌症多分类的快速基因选择方法[8]。REKHA A G等根据SVDD目标函数的梯度下降方向找到球心的近似原像，避免了拉格朗日乘子的计算问题并降低了复杂度[9]。陶新民等设计密度敏感最大间隔SVDD算法，根据样本在空间的分布，解决不均衡的数据分类问题[10]。
GUO Y等将SVDD与多核学习结合构造多分类器[11]。引入集成学习理念，Pranjal利用斜二叉树和SVDD构造改进的多分类算法[12]。
GORNITZ N进一步应用集成学习思想[13]，利用SVDD和K均值聚类构造单值分类算法。YIN L L等将SVDD应用于奇异值检测，构造具有较好鲁棒性的积极学习算法[14]。在无线传感器网络领域，HUAN Z等设计SVDD算法进行奇异值检测[15]，而SHI P等在此基础上设计改进的SVDD算法[16]。陶新民等针对故障检测设计一种不均衡的最大间隔SVDD模型[17]。WANG K Z等设计针对污染数据的鲁棒支持向量域描述算法[18]。为了进一步提高SVDD的训练速度和降低计算复杂度，ZHANG L等利用超球球心和半径之比选择特征[19]。ZHENG S F修改SVDD模型的拉格朗日函数为可微凸函数，并设计一种迭代算法求解，更加快速有效且分类精度较高[20]。高罗莹等在室内无线局域网中引入SVDD算法[21]，解决了已有检测技术的适应性较差和检测性能较低的问题。吕国俊等学者结合蚁群优化算法进行相似重复记录检测[22]。这些研究取得了一定的进展，拓宽了SVDD的应用领域，或提高SVDD的分类精度，或降低SVDD的复杂度，或增加SVDD的鲁棒性。然而，设计过程中往往需要借助其余算法，例如独立成分分析、多核学习、K均值聚类、粒子群优化等，计算较为复杂。
如果构造出既能够缩短运行时间、提高可处理问题的规模，又能够保证较高的分类精度的分类算法，则能有效提高算法在各个领域的运算效率。最小二乘支持向量机将标准算法的不等式约束改为等式约束，具有计算简单、分类精度高的优点[23];对SVDD进行分片[24]和对SVM进行分区域处理[25]的思想，有效提高了相应算法的分类精度。笔者受最小二乘思想和分块处理思想的启发，构造双最小二乘支持向量数据描述DLSSVDD;将支持向量数据描述中的不等式约束修改为等式约束，同时结合样本到2个最小包围超球的距离设计分区域的分类准则。DLSSVDD仅需求解一个线性方程组而非凸二次规划，训练仅对一类样本进行且考虑样本在空间的位置分布;预计DLSSVDD具有较低复杂度、较短的分类时间、较高的分类精度。
1 双最小二乘支持向量数据描述
简要给出最小二乘支持向量機和支持向量数据描述的工作原理。
2 数值试验
为验证DLSSVDD的性能，选取不同规模的基准数据集和正态分布数据集进行实验。所有实验均在P4CPU，3.06 GHz，内存为0.99 GB的PC机上进行;所有程序均采用Matlab 7.01编写。
例1 正态分布数据集
在二维空间中，调用Matlab中的mvnrnd 函数生成满足正态分布的正类和负类样本各250个。正负类样本的均值分别取为 μ1=[0.4，0.8]和μ2=[0.8，0.4]，协方差矩阵均取为单位矩阵;数据集利用r=mvnrnd（mu，SIGMA，250）生成，其中mu为均值，SIGMA为协方差矩阵，250为样本总数。
为了验证DLSSVDD的分类精度，选取径向基核函数
K（x，y）=exp（-‖x-y‖2/σ2）进行数值实验，取径向基核参数σ=0.5，并取惩罚参数为C=1。视正类样本作为目标类（Target），其余样本作为奇异值类（Outlier）。图1给出了样本集的分布，以及算法DLSSVDD对目标类和奇异值类的分类精度。
例2 Diabetics数据集
Diabetics为含有768个样本的8维数据集。随机选取468个样本参与训练，其余300个参与测试。为避免随机性，进行10次随机抽取实验，并列出训练集和测试集上的平均结果。
实验选取径向基核函数，惩罚参数取为C=1;随着径向基核参数的变化，以分类精度和运行时间作为评价指标，对比DLSSVDD和SVDD的分类表现，并列出相应结果见表1。
从表1可以看出，对于不同的核参数取值，DLSSVDD的分类精度和分类时间均比SVDD要低。同时可以看到，当核宽参数从σ=0.1增加到σ=0.5时，2种算法的分类精度均随核参数的增加而降低，只是变化幅度不同;SVDD分类精度的变化幅度约为5.6%;而DLSSVDD分类精度的变化幅度约为2.3%。
例2 Breast Cancer和Banana数据集另取UCI数据集中的Breast Cancer和Banana数据集进行测试。前者为包含277个样本的9维数据集，随机选取200个参与训练，其余77个参与测试。后者为包含5 300个样本的2维数据集，随机抽取400个样本参与训练，其余参与测试。
为便于比较，对不同算法设置相同的参数，均取径向基核函数，取惩罚参数为C=1，核宽参数为σ=0.1;列出不同算法在训练集和测试集上的平均分类精度和分类时间见表2，并将最优分类结果加黑表出。
由表2看出，DLSSVDD在不同的数据集上均具有最高的分类精度和最短的分类时间。由于Banana数据集的测试集规模较大，在其上的分类精度可以代表算法的泛化能力;不妨以Banana数据集为例展开分析。DLSSVDD的分类精度分别比SVM、LSSVM和SVDD高1.76%，2.64%和0.22%;而分类时间依次是三者的16.51%，49.30%和77.43%。显见，DLSSVDD对训练精度提高的幅度较低，在分类时间上具有著优势。
例3 大规模数据集
本例依旧调用Matlab中的Mvnrnd 函数生成满足正态分布的二维空间数据集，并保持正类和负类样本的的数据均等。为了验证算法在大规模数据集上的分类表现，依次增加正类和负类样本的数目，并随机交换部分样本的正负号，使得有5%的重合。正类和负类样本的均值分别取为μ1=[0.2，0.6]和μ2=[0.6，0.2]，协方差矩阵依旧取单位矩阵，正态分布数据集的规模为2 000，4 000，8 000和10 000。
随机选取50%的样本参与训练，其余参与测试;取10次随机抽取实验的平均结果。设置惩罚参数C=1，取径向基核函数并取核宽参数σ=1;表2对比给出不同算法的分类性能。
由表3显见：DLSSVDD的分类精度与SVDD的相当，而分类时间远远低于SVDD的分类时间;同时这种分类精度和分类时间上的优势在样本规模较大时，也即参与训练的样本集数目较多时，体现的更为明显。
以2 000个数据集为例，DLSSVDD的分类时间9.57 s是SVDD分类时间12.26 s的78.06%;当样本数目增加到10 000时，DLSSVDD的分类时间60.08 s是后者12.26 s的18.69%。
3 结 论
1）DLSSVDD具有比SVDD更短的分类时间。DLSSVDD在分类时间上具有明显优势，一方面是因为DLSSVDD减少了参与训练的样本规模，仅需带入单一类别的样本进行训练，而不需要像SVDD那样带入全体样本参与训练;另一方面是因为DLSSVDD将支持向量数据描述中的不等式约束改为等式约束，采用类似最小二乘支持向量机的思想，通过求解一个线性方程组得到最优解。
2）DLSSVDD具有比SVDD略高的分类精度。这是因为DLSSVDD同时考虑了正类样本和负类样本，根据待测样本与2个最小包围超球修心的距离，通过一个分段函数来判断类别标签。这样更符合样本的空间分布。
3）与SVDD相比，DLSSVDD分类时间方面的优势在大规模样本集上体现的更为明显。以正态分布数据集上的数值实验为例，DLSSVDD保持了较高的分类精度，而分类时间随样本规模的变化而增加的幅度并不明显。这得益于DLSSVDD仅通过求解一个线性方程组得到最优解，而避免了传统SVDD算法对凸二次规划的求解。鉴于DLSSVDD在这3个方面的优势，下一步研究方向将拓宽DLSSVDD在大规模样本集的分类问题以及奇异值检测等实际问题中的应用。
参考文献（References）：
[1] ZHOU F D，HOU W W，ALLINSON G，et al.A feasibility study of ECBM recovery and CO2，storage for a producing CBM field in Southeast Qinshui Basin，China[J].International Journal of Greenhouse Gas Control，2013，19（19）：26-40.[2]陸从德，张太镒，胡金燕.基于乘性规则的支持向量域分类器[J].计算机学报，2004，27（5）：690-694.LU Congde，ZHANG Taiyi，HU Jinyan.Support vector domain classifier based on multiplicative updates[J].Chinese Journal of Computers，2004，27（5）：690-694.[3]ZHAO F，YAN L，ZHEN H，et al.Simplified solution for support vector domain description[J].International Journal of Digital Content Technology and Its Applications，2011，5（2）：292-299.
[4]LAN J C.Research on the fast ICA and SVDD based fault feature extraction algorithm for analog circuit[J].International Journal of Digital Content Technology and Its Applications，2012，6（6）：107-115.
[5]NIAZMARDI S，HOMAYOUNI S，ABDOLREZA S.An improved FCM algorithm based on the SVDD for unsupervised hyperspectral data classification[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2013，6（2）：831-839.
[6]PENG X J，XU D.Twin support vector hypersphere（TSVH）classifier for Pattern Recognition[J].Neural Computing and Applications，2014，24（5）：1207-1220.
[7]刘富，侯涛，刘云，等.可变惩罚因子的支持向量数据描述算法[J].吉林大学学报（工学版），2014，44（2）：440-445.
LIU Fu，HOU Tao，LIU Yun，et al.A variable trade-off parameter support vector domain description[J].Journal of Jilin University（Engineering and Technology Edition），2014，44（2）：440-445.
[8]CAO J，ZHANG L，WANG B J.A fast gene selection method for multi-cancer classification using multiple support vector data description[J].Journal of Biomedical Informatics，2015，53（1）：381-389.
[9]REKHA A G，ABDULLA M S，ASHARAF S.Lightly tr-ained support vector data description for novelty detection[J].Expert Systems With Application，2017，85（1）：25-32.[10]陶新民，李晨曦，沈微，等.基于密度敏感最大軟间隔SVDD不均衡数据分类算法[J].电子学报，2018，46（11）：2725-2732.TAO Xinmin，LI Chenxi，SHEN Wei，et al.The SVDD classifier for unbalanced data based on density-sensitive and maximum soft margin[J].Acta Electronica Sinica，2018，46（11）：2725-2732.[11]GUO Y，XIAO H T.Multiclass multiple kernel learning using hypersphere for pattern recognition[J].Applied Intelligence 2018，48（1）：2746 2754.[12]BOGAWAR P S，BHOYAR K K.An improved multiclass support vector machine classifier using reduced hyper-plane with skewed binary tree[J].Applied Intelligence 2018，48（1）：4382-4391.[13]GORNITZ N，ALBERTO L L，MULLER K R，et al.Support vector data descriptions and k-means clustering：One class？[J].IEEE Transactions on Neural Networks and Learning Systems，2018，29（9）：3994-4006.[14]YIN L L，WANG H G，FAN W H.Active learning based support vector data description method for robust novelty detection[J].Knowledge Based System，2018，153（1）：40-52.[15]HUAN Z，WEI C，LI G H.Outlier detection in wireless sensor networks using model selection-based support vector data descriptions[J].Sensors，2018，18（12）：4328-4342.[16]SHI P，LI G H，YUAN Y M，et al.Outlier detection using improved support vector data description in Wireless Sensor Networks[J].Sensors，2019，19（21）：1-13.[17]陶新民，李晨曦，李青，等.不均衡最大软间隔SVDD轴承故障检测模型[J].振动工程学报，2019，32（4）：718-729.TAO Xinmin，LI Chenxi，LI Qing，et al.Rolling bearings fault detection model using imbalanced maximum soft margin support vector domain description[J].Journal of Vibration Engineering，2019，32（4）：718-729.[18]WANG K Z，LAN H B.Robust support vector data description for novelty detection with contaminated data[J].Engineering Applications of Artificial Intelligence，2020，91（1）：1-26.[19]ZHANG L，LU X N.Feature extraction based on support vector data description[J].Neural Processing Letters，2019，49（2）：643-659.[20]ZHENG S F.A fast iterative algorithm for support vector data description[J].International Journal of Machine Learning and Cybernetics，2019，10（5）：1173-1187.[21]高罗莹，田增山，李玲霞，等.一种基于SVDD的WLAN室内被动入侵检测方法[J].重庆邮电大学学报（自然科学版），2020，32（4）：200-209.GAO Luoying，TIAN Zengshan，LI Lingxia，et al.A SVDD-based method for WLAN indoor passive intrusion detection[J].Journal of Chongqing University of Posts and Telecommunications（Natural Science Edition），2020，32（4）：200-209.[22]吕国俊，曹建军，郑奇斌，等.基于多目标蚁群优化的单类支持向量机相似重复记录检测[J].兵工学报，2020，41（2）：324-331.LYU Guojun，CAO Jianjun，ZHENG Qibin，et al.Detection of similar duplicate records based on OCSVM and multi-objective ant colony optimization[J].Acta Armamentarii，2020，41（2）：324-331.[23]王安义，郭世坤.最小二乘支持向量机在信道均衡中的应用[J].西安科技大学学报，2014，34（5）：591-595.WANG Anyi，GUO Shikun.Application of least squares support vector machine in channel equalization[J].Journal of Xian University of Science and Technology，2014，34（5）：591-595.[24]梁锦锦，吴德.聚类分片双支持向量域分类器[J].控制与决策，2015，30（7）：1298-1302.LIANG Jinjin，WU De.Clustering piecewise double support vector domain classifier[J].Control and Decision，2015，30（7）：1298-1302.[25]查翔，倪世宏，张鹏.基于多区域划分的模糊支持向量机方法[J].中南大学学报（自然科学版），2015，46（5）：1680-1687.ZHA Xiang，NI Shihong，ZHANG Peng.Fuzzy support vector machine method based on multi-region partition[J].Journal of Central South University（Science and Technology），2015，46（05）：1680-1687.
猜你喜欢 向量精度样本 近似边界精度信息熵的属性约简华东师范大学学报（自然科学版）(2018年3期)2018-05-14直击高考中的用样本估计总体中学生数理化·高一版(2017年2期)2017-04-25随机微分方程的样本Lyapunov二次型估计数学学习与研究(2017年3期)2017-03-09电力系统短期负荷预测方法与预测精度电子技术与软件工程(2016年24期)2017-02-23向量垂直在解析几何中的应用高中生学习·高三版(2016年9期)2016-05-14向量五种“变身” 玩转圆锥曲线新高考·高二数学(2015年11期)2015-12-23基于支持向量机的测厚仪CS值电压漂移故障判定及处理计算技术与自动化(2014年1期)2014-12-12船舶制造精度管理及过程控制技术探究中国信息化·学术版(2013年7期)2013-09-03浅谈ProENGINEER精度设置及应用职业·中旬(2009年12期)2009-06-01