面向海量样本的线性可分支持向量机分组算法

2020-12-23马捍超沈杰鑫徐路强于海

微型电脑应用 2020年11期

马捍超沈杰鑫徐路强于海

摘要：传统线性可分支持向量机分组算法面对海量样本进行分组时，存在正确率较低的问题，对此提出一种面向海量样本的线性可分支持向量机分组算法。面向海量样本给定一个样本集，对其样本集进行特征提取，利用分值方法进行样本特征选择，通过线性可分支持向量机进行样本聚类，并建立线性可分支持向量机分组框架，利用该框架实现样本分组。为了验证面向海量样本的线性可分支持向量机分组算法的样本分组正确率，将该算法与传统线性可分支持向量机分组算法进行对比实验，结果证明该算法的样本分组正确率更高，说明本研究所提算法更适用于海量样本的分组。

关键词：海量样本;线性可分;支持向量机;分组算法

中图分类号：TP13

文献标志码：A

文章编号：1007-757X（2020）11-0082-04

Abstract：The traditional linear divisible support vector machine grouping algorithm has the problem of low accuracy when grouping mass samples. A mass sample set is given to be extracted， and the sample feature selection is performed by the score method. The sample clustering is carried out by the linear divisible support vector machine. In order to verify the sample grouping accuracy of the linear divisible support vector machine grouping algorithm for mass samples， the algorithm is supported with the traditional linearity. The results show that the proposed algorithm has more accuracy， which illustrates that the algorithm is more suitable for the mass sample set.

Key words：massive samples;linear separability;support vector machine;grouping algorithm

0 引言

信息技术与计算机技术的高速发展，使互联网上流动的资源与分布的内容呈现出了多元化、海量化的膨胀趋势，数据存储技术与数据收集技术的迅速发展也使各种机构组织能够积累并获取大量的数据。这些数据呈现出使用态、传输态以及静态等多种状态，既有正常可用的多元应用数据，如政府、教育、医学、市场、金融等行业数据及系统日志、安全策略、流量、即时通信、微博、新闻组、电子邮件、新闻等系统内容资源，也有网络经济犯罪、僵尸病毒网络攻击流、恶意软件、个人隐私、欺诈广告、垃圾邮件、色情网站、钓鱼网站、虚假信息等影响国家重大利益、危害社会稳定、误导公众、泄露敏感信息、影响资源以及信息可用性的内容。对于正常可用的多元应用数据，从信息数据的有效性、可用性角度，需要根据各个领域、不同行业的用户需要，高效、快速的对有用的数据进行分组，并对数据进行提取、分析;而对于影响资源以及信息可用性的内容，无论从内容安全角度，还是从合法性、道德性、可用性、真实性等角度，都有必要对这些正在或即将泄露的不安全数据进行分组，并对其进行保护与检测，对存在诱导、恶意、虚假的行为或内容进行分析、过滤、分组，能够及时对攻击源或受害者进行定位，同时利用智能处理系统对知识进行学习，并对数据进行处理[1]。然而，在资源信息高度网络化与数字化的今天，数据的分组仍然困难重重，不管是从内容安全还是从数据管理角度，都需要对各种数据迅速进行分组，以实现高效的信息安全保护，因此提出一种面向海量样本的线性可分支持向量机分组算法[2]。

1 面向海量样本的线性可分支持向量机分组算法

1.1 特征选择

首先面向海量样本进行特征选择：给定一个样本集T，对其样本集进行特征提取，如式（1）。

利用分值方法对海量样本进行特征选择。首先针对样本集X进行相似对应矩阵的构造，如式（2）。

根据分值方法的基础理论[3]，分值矩阵，如式（3）。

完成残差的获取后，独立看待各个特征，并对第i个特征的分值进行定义，如式（8）。

设需要选择的样本数据特征的总体个数为d′，对每个数据特征的分值分别进行计算，将各个数据特征对应的分值依照由小到大的次序排列，从中挑选出d′个数据分值的相应特征。具体的挑选方法如下。

首先输入需要选择的样本数据特征的总体个数r与样本集X，按照特征分值的定义公式计算出r个数据特征分值，分别记录为S1，S2，…，Sr;对这些数据特征分值进行排序：Sr（k1），Sr（k2），…，Sr（kn）;最后输出r个数据分值相应特征的特征因子S′，實现了面向海量样本的特征选择[4]。

1.2 样本聚类

完成面向海量样本的特征选择后，利用线性可分支持向量机进行样本聚类。线性可分支持向量机的样本聚类流程主要分为两个阶段：首先利用线性可分支持向量机的训练集对海量样本的特征进行聚类训练，从而构建支持函数;确认线性可分支持向量机的超平面边界长度，在超平面边界中进行簇的标定，也就是在海量样本的特征中任选两个作为样本，对它们之间的线段实施采样，并判断数据集合中心与采样点之间的距离，以对两个样本进行簇的分类，判断其是否属于相同的簇[5]。

样本聚类的实施涉及到簇的标定、对偶问题的求解以及参数的选择等，具体实施步骤如下：利用线性可分支持向量机的训练集对海量样本的特征进行聚类训练首先需要对数据特征样本进行类别标签的设定，并寻找一个可以对所有数据特征样本进行包围，并且尽可能远离原点的超平面作为训练的分界面，并利用这个分界面对数据特征样本的簇轮廓进行描述[6]。由于在聚类训练中普遍存在一些线性不可分状况，因此必须将数据特征样本在特征空间中映射并对其进行分析。在特征空间中对数据特征样本进行数据轮廓描述，并对新样本或外点进行聚类训练，寻找一个最小的并且可以对所有数据特征样本进行包围的超平面，对其进行逆向映射操作，使其映射到输入空间中，从而获得可以描述数据特征样本轮廓的边界[7]。聚类步骤流程图，如图1所示。

根据图1可进行具体操作如下。

给定N个数据特征样本的数据集，并对超平面中心进行设定，从而获取聚类训练的目标函数[8]。在聚类训练的目标函数中，训练样本中有一部分是允许出现在超平面标准半径外的，并且在该函数中，利用惩罚因子C对松弛因子和半径的比重进行平衡，并对噪声数据点进行抑制以及对外点规模进行控制，通常惩罚因子C的取值范围在零到一之间。在聚类训练的目标函数中引入分值方法中的乘子，可以得到聚类训练的对偶式。通过聚类训练的对偶式可以对样本和超平面边界长度与超平面中心的距离进行精准的判断，并且便于进行簇的标定。在对聚类训练的对偶式进行求解的过程中，即可获得可以描述数据特征样本轮廓的边界。当对偶式的解等于零时，则在特征空间中可以判断样本处于超平面外部，可以称之为孤立点或外点[9]，但该样本对超平面的构造是有贡献的，因此也将其称为受限线性可分支持向量，如图2所示。

当对偶式的解大于零时，则在特征空间中可以判断样本处于超平面表面，称之为线性可分支持向量。

当对偶式的解等于零时，则在特征空间中可以判断样本处于超平面内部，称之为内点[10]。

通过外点、线性可分支持向量与内点即可获得可以描述数据特征样本轮廓的边界。可以发现这个边界是闭合的，并且上面的样本点与超平面中心的距离相同。处于边界内部的那些样本点由于同时位于超平面内部，其与超平面中心的距离比超平面边界长度的距离要小，因此这些样本点可以归类在一个簇中。通过聚类簇标定算法对各个样本点的簇标号进行确定，实现海量样本特征的样本聚类。

1.3 实现样本分组

完成海量样本特征的样本聚类后，建立线性可分支持向量机分组框架，利用样本特征的样本聚类结果对数据特征样本的训练分组信息进行获取，并将训练分组信息引入线性可分支持向量机分组框架中，从而获取最佳的分划超平面。其中训练样本的分组步骤如下：首先通过分值方法对其重要特征进行选取，接着以选取的样本聚类技术为依据对分组信息进行获取[11]。获取训练分组信息后，在线性可分支持向量机分组框架中引入训练分组信息，并利用迭代算法实现线性可分支持向量机分组框架，具体实现步骤如下。

输入核函数K（x，x′）与Kr（x，x′）、样本集的总体特征个数r、权衡参数μ、惩罚因子C、特征因子S′，进行初始化，如式（9）。

通过特征选择方法的执行在样本集X上对特征因子S′进行获取，并对初始化结果进行更新，如式（10）。

在特征子集上對聚类技术进行执行，从而将训练集T划分为相关组。

对优化问题进行求解，获取决策函数。重复迭代步骤，直至j0=n。

对最佳决策函数进行选取并对其进行输出，从而实现线性可分支持向量机分组框架[12]。

利用线性可分支持向量机分组框架分组样本，实现面向海量样本的线性可分支持向量机分组算法。

2 实验研究

为了检测本研究提出的面向海量样本的线性可分支持向量机分组算法，设计了对比实验。

2.1 实验过程

本研究所有算法均基于仿真软件MATLAB 20I2a进行实验，仿真计算机系统为Windows 7，处理器为Intel i5-7500，内存为16.00 GB，处理器频率为2.93 GHz。在海量样本中进行实验样本的选取，共选取十个实验样本数据集，包括Tonosphere样本数据集、WPBC样本数据集、Seed样本数据集、Diabetes样本数据集、BUPA样本数据集、Teaching样本数据集、Haberman样本数据集、Breast样本数据集、Heartstatlog样本数据集和Hepatitis样本数据集，而各个样本数据集在非线性情形与线性情形中，其最优样本分类精度所分别对应的样本特征个数，如图3所示。

本次实验通过网格搜索法获取最优参数，在参数的选取中，根据K值自适应的SA-KNN算法对样本参数中的的计算结果[13]将近邻参数设定为5;将权衡参数的取值范围设定为10-3-10-1;将惩罚参数的取值范围设定为10-1-102;将高斯核参数的取值范围设定为2-2-22。而对于聚类时截断距离的取值则要遵循训练样本与平均近邻点数的比值为2%的原则。

为了保证本次实验的有效性，使用基于网格搜索的线性可分支持向量机分组算法、基于特征数据集的线性可分支持向量机分组算法、基于结构信息的线性可分支持向量机分组算法与本研究提出的面向海量样本的线性可分支持向量机分组算法进行比较，并分别进行15次实验，比较各个算法样本分组正确率的高低。

2.2 实验结果

实验样本分组正确率结果，如表1所示。

根据表1的样本分组正确率数据可知，面向海量样本的线性可分支持向量机分组算法的样本分组正确率始终高于传统线性可分支持向量机分组算法。

3 总结

本研究所提算法通过线性可分支持向量机分组框架实现了样本的分组，仿真实验结果显示其样本分组正确率高于传统线性可分支持向量机分组算法，可突出海量样本的线性可分支持向量机分组算法优势，对线性可分支持向量机分组领域具有重要意义。但是本研究所提算法尚未进行深入研究和应用，应扩展研究角度、落实应用实践，以期为线性可分支持向量机分组领域做出更大贡献。

参考文献

[1] 冉琼，于浩洋，高连如. 结合超像元和子空间投影支持向量机的高光谱图像分类[J]. 中国图象图形学报， 2018， 23（31）：1195-1205.

[2] 杨志民，王甜甜，邵元海. 面向不均衡分类的隶属度加权模糊支持向量机[J]. 计算机工程与应用， 2018， 11（22）：1168-1175.

[3] 乐琦. 直觉模糊环境下考虑匹配意愿的双边匹配决策[J]. 中国管理科学， 2017， 25（6）：161-168.

[4] 薛章鹰，刘兴权. 结合ReliefF、GA和SVM的面向对象建筑物目标识别特征选择方法[J]. 测绘工程， 2017， 26（32）：2152-2156.

[5] 岳鹏程，张林梁，马阅军. 基于模糊时序和支持向量机的高速公路SO_2浓度预测算法[J]. 计算机系统应用， 2017， 26（36）：2241-2248.

[6] 业巧林，闫贺. 基于最小二乘的孪生有界支持向量机分类算法[J]. 华中科技大学学报（自然科学版）， 2018， 46（53）：2213-2213.

[7] 王石，蒋宁宁，杨舒卉. 基于压缩K近邻边界向量的支持向量预抽取算法[J]. 海军工程大学学报， 2018， 30（36）：2278-2283.

[8] 李振，曹慶贵，杨涛. 基于支持向量机与连续蚁群算法建立的煤矿企业安全投入模型研究[J]. 矿业安全与环保， 2019， 46（51）：1109-1113.

[9] 何宏炜，吴志航，于召新. 四进制自由空间激光通信信号的支持向量机检测算法[J]. 光学学报， 2018， 38（41）：1414-1421.

[10] 赵彩云，吴长勤，葛华. 基于有效迭代算法的鲁棒L1范数非平行近似支持向量机[J]. 计算机应用， 2017， 37（41）：3069-3074.

[11] 刘治超，李侍林，黄毅，等. 基于支持向量机的机载吊舱故障诊断优化算法[J]. 计算机测量与控制， 2018， 26（31）：2171-2175.