2. 东南大学 计算机科学与工程学院, 南京 210096
2. School of Computer Science and Engineering, Southeast University, Nanjing Jiangsu 210096, China
随着互联网发展,生产应用中产生了大量的数据,诸如来自于金融市场、网络监控、电信数据、传感器网络等场景。由于此类数据,亦称之为流(data stream),具有实时、高速、连续和动态等特性,加之协议的形式和种类繁多,以及新协议不公开且不遵守已有的协议规范,使得经典的数据管理和分析技术乏力甚至失效,因而该领域的研究极具挑战性,针对此类研究现已逐渐演变成为新的研究热点[1-3]。有别于一般数据,针对流数据的研究,困难主要表现在:1) 计算机有限的存储容量无法存储和计算海量数据;2) 网络数据流的高维易造成维数灾难问题;3) 数据在采集和传输过程的数据受噪声污染问题;4) 因为数据流的变化实时且连续,极易造成学习算法的欠学习问题;5) 数据类别多,仅通过一对一(one-vs-one)或一对多(one-vs-all)扩展的两分类学习方法难以胜任此类问题。
已有的研究方法中,机器学习被认为最具有研究潜力[4],研究成果表明,由于人工神经网络具有诸如全局逼近性、网络结构简单、可直接用于多分类或回归问题,在网络流分类方法应该具有更好的应用前景,如Bayes、径向基函数(Radial Basis Function, RBF)和反向传播(Back-Propagation, BP)网络等,但以上网络存在训练时间过长等问题,自极限学习机(Extreme Learning Machine, ELM)问世以来[5-7],现已引起普遍关注,ELM采用随机的方法设置网络权及阈值,具有全局逼近能力,采用伪逆方法计算输出层权矩阵,相对于BP网络,训练时间大幅度缩短。Plane-Gaussian (PG)网络[8]是先进行平面聚类[9],获得PG激活函数的参数,再采用伪逆的方式计算网络输出权矩阵。该网络同样具有全局逼近能力。实验证明,该网络与BP、RBF具有相当的分类能力,对于平面型分布的数据,该网络的分类性能显著优于前二者,而训练速度与RBF相当,但比BP快得多。鉴于ELM的随机选取输入权值和阈值策略,本文拟在PG网络中放弃平面聚类方法,对PG激活函数的权参数和阈值采用随机方法,并据此发展出一个新的神经网络RandPG(Random PG)。由于PG神经网络在训练过程中需要先聚类,训练时间较长;而ELM虽然先随机抽取再优化网络权值,但在几何上缺乏明确的模型解释,同时,两种方法在隐层节点数的选择上,目前还只能依赖经验。本文拟结合两种方法,借鉴ELM中网络参数随机选择的方式,克服PG网络训练过程中的需要聚类的缺点,在PG网络中引入了随机投影的思想,提出了基于随机投影的平面高斯神经网络RandPG,它同样具有全局逼近能力。与PG网络相比较:1) 它避免了聚类,训练时间大幅度缩短;2) 随机选择投影,有利于突破陷入局部最优解的限制;3) 不需要随机选择隐节点个数,与类别个数相同。与ELM相比较:1) RandPG网络几何意义明确;2) 能够胜任多分类问题,且无需考虑隐节点个数选择问题;3) 继承了PG网络对平面型分布数据的分类能力,效果显著优于ELM。最后,本文将三种算法分别在平面型数据集和网络流数据集上进行对比实验,并测试和分析该方法在网络数据流上的性能。
1 相关工作 1.1 极限学习机ELM是一种新的机器学习方法,具备以下四个特点[7]:1) 极限学习机从理论上探讨了神经网络在学习过程中隐节点是否需要调整的问题;2) 该方法既可用于单隐层前馈网络,又适用于多隐层前馈网络;3) 超限学习机的学习构架可拓展到特征学习、聚类、回归和分类等问题;4) 相比于超限学习机,支持向量机(Support Vector Machine, SVM)和最小二乘支持向量机(Least Square Support Vector Machine, LS-SVM)趋向于得到次优解。
定理 1 函数逼近定理。给定任何激活函数(非常数的分段函数),若通过调整隐层参数可让单层前馈网络逼近任何连续的目标函数g(x), 那么{hi(aiTx+bi)}i=1n可以根据任何连续的概率分布生成,并且以合适的输出权值α,使:
$\underset{n\to \infty }{\mathop{\lim }}\,\|\sum\limits_{i=1}^{n}{{{\alpha }_{i}}{{h}_{i}}(\mathit{\boldsymbol{a}}_{i}^{\rm{T}}\mathit{\boldsymbol{x}}+{{b}_{i}})-g\left( \mathit{\boldsymbol{x}} \right)}\|=0$ | (1) |
以概率1的可能性成立。其中的hi(aiTx+bi)为激活函数,它有能力分隔具有任何形状的不连通区域,ai为输入网络权向量,bi为对应的阈值。
对于分类问题,式(1) 可修改为如下最小化问题:
$\min ~\left\| \sum\limits_{i=1}^{n}{{{\alpha }_{i}}{{h}_{i}}(\mathit{\boldsymbol{a}}_{i}^{\rm{T}}\mathit{\boldsymbol{x}}+{{b}_{i}})-y} \right\|_{2}^{2}$ | (2) |
其中y
在平面聚类方法(k-Plane Clustering, kPC)[9]基础上,采用“平面原型”代替RBF网络的“点原型”的一种人工神经网络模型(Plane-Gaussian NN)。该网络具有全局的万能逼近能力,同时还有自身的特点,如局部性等。由于兼有多层感知机(Multi-layer Perceptron, MLP)与RBF网络的部分特点,PG网络为这两种不同类型的网络建立了联系的桥梁。从对先验知识的适用性而言,RBF网络更适合高斯分布的数据,而PG网络则更适合子空间分布的数据。
kPC聚类方法需要不断迭代计算k个聚类超平面,即随机产生k个平面,将n个样本归为k个簇(样本归簇),每个簇计算出超平面(聚类更新),再进行样本归簇,再计算簇的超平面,直到每个簇内的样本不再变化为止。如此,存在如下两个问题:1) 聚类超平面的求解方法仅能保证次优;易于陷入局部极小解;2) 反复迭代过程需要耗费大量的训练时间。
ELM和PG网络存在如下异同点。相同的是:1) 类别标号采用0-1编码方式;2) 输出层权矩阵计算方法一样,都是计算矩阵伪逆来获得输出矩阵。不同点在于:1) 输入权值不同,ELM采用随机方式;而PG网络与RBF一样,权值均置为1;2) 激活函数不同,ELM方法可采用多种激活函数,常用sigmoid函数,而PG网络用的是“平面原型”思想,采用的激活函数称之为平面高斯函数(Plane-Gaussian Function), 该函数的参数需要通过kPC聚类方法计算。
鉴于以上分析,本文拟将随机投影技术与PG网络结合起来,即放弃PG激活函数的权值不再通过聚类获得,而是采用随机投影方法来完成。下文中将从网络模型构造、全局逼近能力、性能分析等方面来介绍随机PG网络。
2 RandPG:随机PG网络模型为方便表述,先给出符号说明。设给定训练集{(xi, yi}i=1n,共有c类,xi∈Rd,yi∈{1, 2, …, c}为其类别标号。Plane-Gaussian函数[7]定义如下:
${{\mathit{\Phi }}^{\rm{PG}}}=\rm{exp}(-{{\mathit{\boldsymbol{w}}}^{\rm{T}}}\mathit{\boldsymbol{x}}-{{\gamma }^{2}}/{{\sigma }^{2}})$ | (3) |
其中在‖w‖=1时,|wTx-γ|可解释为样本点x到平面wTz-γ=0的距离,w, γ分别表示超平面的权向量和阈值,σ为带宽参数。该函数描述的激活区域为带状区域,一个方向上有界,另一方向上可无限伸展,为MLP和RBF两种网络模型建立起了联系桥梁[7]。
2.1 RandPG网络模型由PG网络结构定义,该类型网络的数学模型描述如下:
$\mathit{\boldsymbol{o}}=\sum\limits_{i=1}^{c}{{{\mathit{\boldsymbol{u}}}_{i}}G({{\mathit{\boldsymbol{w}}}_{i}},{{\gamma }_{i}},\mathit{\boldsymbol{x}})}$ | (4) |
其中:c为类别个数。由式(4) 知,wi, γi为隐层的学习参数,在PG网络中该参数由kPC聚类算法解得,因而在训练网络时需要耗费大量的时间。RandPG将放弃聚类方法获得网络权值,借鉴类似于ELM的随机选择的方法。
在训练阶段,当式(4) 中j取遍{1, 2, …, n}时,可得线性方程组,以矩阵记录如下:
$\mathit{\boldsymbol{O}} = {U^{\rm{T}}}\mathit{\boldsymbol{ \boldsymbol{\varPhi} }}$ | (5) |
其中:Φ=[Φ1, Φ2, …, Φn],Φi=[Φ1PG(xi), Φ2PG(xi), …, ΦcPG(xi)]T,i=1, 2, …, n,ΦjPG(xi) =exp(-|wjTxi-γj|2/σ2),j=1, 2, …, c。U为待求的输出权矩阵,O为输出,对多分类问题,常采用0-1编码形式表示类标。
2.2 RandPG的全局逼近性文献[7]的全局逼近定理描述如下。
定理 2 形如式(4) 的连续光滑函数G, 在线性空间Rd的有界闭区域C(Id)内是稠密的,即对任给的非平凡连续函数f∈C(Id)和任给的ε>0,总存在一组合适的ui,使式(6) 成立:
$|\sum\limits_{i = 1}^l {{\mathit{\boldsymbol{u}}_i}G({\mathit{\boldsymbol{w}}_i},{\rm{ }}{\gamma _i},{\rm{ }}\mathit{\boldsymbol{x}}) - f} | \le \varepsilon $ | (6) |
从定理的证明过程可知,逼近中只与u的选择有关,与函数G的参数选择无关。当然,此结论在隐节点个数趋于无穷时成立。可立得如下推论。
推论1 式(6) 中随机选择一组参数{(wi, γi)|wi∈Rd, γi∈R},亦能保证存在一组合适的ui,使得不等式成立。
2.3 RandPG算法以上内容总结为一个学习算法,描述如下。
输入: 样本类别数c,训练样本集{(xi, yi}i=1n,将yi按0-1编码形式生成输出类标矩阵Y;
输出: 输出权矩阵U。
步骤1 随机产生一组{(wi, γi)},i=1, 2, …, c;
步骤2 按式(5) 计算矩阵Φ;
步骤3 计算U,通常采用矩阵伪逆形式,即U=(YΦ+)T,Φ+为Φ的伪逆,实验部分采用Φ+=(ΦTΦ)-1ΦT来计算。按RandPG算法,PG网络的输出连接权,它是通过随机指定激活函数参数完成的,无需要像PG网络采用聚类方法获得,因此,按此方式的训练神经网络,学习速度较大幅度提高。
测试阶段,对于待归类样本z,连同训练算法中的{(wi, γi)},代入式(3) 、(5) ,计算出输出向量,重新整理为0-1编码形式,得出归类结果。
2.4 RandPG性能分析RandPG算法的实质是训练神经网络来逼近类别标记(如采用0-1编码的向量形式,以方便区别多个类别),即期望网络输出与0-1编码的类别标记一一对应,因此可在最小平方误差(Minimum Square Error, MSE)的优化目标下完成,向量矩阵形式为:
${\rm{min}}\left\| {\mathit{\boldsymbol{o}} - \mathit{\boldsymbol{y}}} \right\|_2^2$ | (7) |
将式(4) 整理,并代入式(7) 得:
$\mathop {{\rm{min}}}\limits_\mathit{\boldsymbol{u}} \left\| {\mathit{\boldsymbol{ \boldsymbol{\varPhi} u}} - \mathit{\boldsymbol{y}}} \right\|_2^2$ | (8) |
可令式(8) 的目标函数对u的导数为0,可立得:
$\mathit{\boldsymbol{u}} = {({\mathit{\boldsymbol{ \boldsymbol{\varPhi} }}^{\rm{T}}}\mathit{\boldsymbol{ \boldsymbol{\varPhi} }})^{ - 1}}{\mathit{\boldsymbol{ \boldsymbol{\varPhi} }}^{\rm{T}}}\mathit{\boldsymbol{y}}$ | (9) |
而且式(9) 不仅是唯一解,而且形式上与矩阵伪逆的结果一样,与ELM形式上也是一致的。
ELM采用随机的方法来训练前馈神经网络,一举突破了以往必须通过优化计算出网络连接权,较之BP网络,训练速度提升了千百倍,现已在很多领域中取得了成功应用。然而PG网络的训练方法仍沿用经典的神经网络,沿用RBF网络训练方法,用“平面原型”聚类代替换“点原型”聚类,都有着清晰的几何解释。依据随机投影理论,ELM的网络的构造权向量(矩阵)及阈值随机选择方法,提出了PG网络随机版本RandPG,期望该方法一样能够大幅度提高PG网络的训练速度,下文中将从测试精度和训练时间两个方面,测试RandPG的真实性能。
3 实验验证实验数据分为两个部分:一是人工数据,用于验证PG和RandPG网络的几何特征,数据采用人工生成平面型分布数据;二是国际标准的网络流数据集。因为RandPG算法思想来自于PG网络,激活函数参数的随机选择方式与ELM相同,因此,将ELM和PG网络作为实验参照对象。如前文所述,期望在测试精度相当的前提下,能够提高PG型网络的学习速度。评价指标主要有两个:测试精度和训练时间,考虑到模型是否存在欠学习问题,把训练精度和测试时间也一并列入评价指标。
3.1 人工数据集两类的人工数据集PlaneLine,数据分布如图 1所示,共有200个样本,3维,分别抽样于相互交叉的直线(标记为“+”)和平面(记为“º”),其中,直线分布的样本抽样于线段z1=(10z2)/17=(-10z3)/17, z1∈[-3, 4],取100个样本并在第二、三维分量上注入均匀分布噪声,大小为[-0.3, 0.3]。平面分布的样本抽样于矩形区域z1+z2+z3+1=0,z1∈[-3, 3],z2∈[-2, 3],抽取100个样本点,并在第三维分量上加入均匀分布噪声,范围为[-0.3, 0.3],zi是第i维分量。
PlaneLine数据集,随机选择一半为训练集,剩下一半为测试集,重复50次,取平均结果。因数据量小,训练时间上看不出显著差异。PG的训练和测试精度均在95%以上,RandPG次之,而ELM的测试精度仅为86%。值得一提的是,ELM和PG网络的隐节点数可以自由选择,而RandPG的隐节点数对应类别个数,因而是固定值。
本数据来源于伦敦玛丽女王大学的计算机科学研究组[10],是通过高性能网络监视器收集得来的,汇集了约1 000个用户连接互联网的研究设备,采用全双工千兆比特以太网链接连接互联网。该网络流数据共包括10个数据集,每条记录有249项特征属性。以24 h为时间单位,记录该时段内进出设备(全双工)的数据包记录,并记入10个文本文件中。表 1简要描述其特征属性。10个数据集,类别数不完全一样。每条记录对应不同的网络应用,分为WWW、EMAIL、TCP、GAME等10多个类别。
由于三种方法中都需要计算矩阵伪逆,其阶数等于训练样本个数,所以批处理方式的样本训练集不宜过大,否则会导致实验上计算内存不足的问题,因此本节实验的训练集规模采用样本集的百分比表示,从训练集的20%开始,直到训练样本数达到50%为止,记录三种方法的训练精度、测试精度、训练时间、测试时间,时间单位采用CPUTIME,限于篇幅,仅列出50%时的实验结果。由于RandPG无需选择隐节点数,为公平比较,实验中,将三种网络的隐节点个数设置为相等。实验重复50轮,结果取平均,训练时间是计算每种方法的50次平均时间。
表 2中的数据是在固定了隐层节点数(节点数等于类别数)情况下的实验结果。
从表 2的实验结果可知,PG网络的精度高于ELM和RandPG,由文献[7]可知,在已知类别数下,PG网络激活函数的参数由kPC聚类算法获得,较之随机选取更为可靠,但其训练时间却是另外两种方法的百千倍,而模型训练完成以后的测试时间,三者差别并不明显。随机权值选择上,ELM和RandPG方法,大多数网络流数据结果中,RandPG要略弱于ELM方法,本质问题可能出现在激活函数平面参数选择上。PG网络中kPC计算得出的参数具有明显的几何解释,即按平面拟合本类样本的方式获得,在迭代完成后,所得的拟合平面一定程度上更能反映出代表该类的样本的能力,实验效果上应该优于RandPG的随机选择方法。在实验过程中,也发现了一种现象,50轮中偶尔会出现分类精度优于PG的情况,但在报告的平均结果中此现象被淹没了。对此现象的解释可能是局部最优解的问题,kPC算法的初始聚类平面是随机产生的,迭代过程中仅能保证次优,存在陷入局部最小解问题;而RandPG采用随机方法产生平面参数,有可能跳出局部最小解的限制。ELM算法与PG网络一样,每一轮的迭代过程中,分类精度都比较平稳,但RandPG变化幅度较大,此处报告的平均结果(为了符合实验结果汇报习惯),在50轮的迭代过程中,至少有一半的分类精度应该高于此外报告的结果。另一方面,尽管也有研究结果表明,神经网络训练过程中更应该关注网络结构而不是隐节点个数[11],然而,在实验过程中,特别是对类别数较少情形,隐节点的个数对分类精度的影响仍然严重。
4 结语在网络流数据的多分类任务中,神经网络方法具有独特优势,如它可以直接实现多分类任务,且无分类盲区,这些特点是扩充版本的二分类方法无法比拟的。本文提出了一种随机的基于PG神经网络的分类方法,以提高PG网络的训练速度。平面型数据上的实验结果表明,相对于PG网络,RandPG网络不需要聚类,明显缩短了训练时间;RandPG网络一定程序上也继承了PG网络的适用于平面型数据分类的特性。此外,由于RandPG存在诸如无需选择隐节点个数、训练速度快、可突破局部最小解限制等优点,该方法在网络流数据分类任务中,仍值得推崇。
[1] | ZHANG J, XIANG Y, WANG Y, et al. Network traffic classification using correlation information[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24 (1) : 104-117. doi: 10.1109/TPDS.2012.98 |
[2] | 赵国锋, 吉朝明, 徐川. Internet流量识别技术研究[J]. 小型微型计算机系统, 2010, 31 (8) : 1514-1520. ( ZHAO G F, JI C M, XU C. Survey of techniques for Internet traffic identification[J]. Journal of Chinese Computer Systems, 2010, 31 (8) : 1514-1520. ) |
[3] | YAN Z, TRACY C, VEERARAGHAVAN M, et al. A network management system for handling scientific data flows[J]. Journal of Network and Systems Management, 2016, 24 (1) : 1-33. doi: 10.1007/s10922-014-9336-2 |
[4] | ALSHAMMARI R, ZINCIR-HEYWOOD A N. How robust can a machine learning approach be for classifying encrypted VoIP[J]. Journal of Network and Systems Management, 2015, 23 (4) : 830-869. doi: 10.1007/s10922-014-9324-6 |
[5] | FRANCFORT S, LIU T, GHAFARI J, et al. Extreme learning machines for Internet traffic classification[EB/OL].[2016-01-02]. https://www.researchgate.net/publication/261985712_Extreme_Learning_Machines_for_Internet_Traffic_Classification. |
[6] | HUANG G B, CHEN L, SIEW C K. Universal approximation using incremental constructive feedforward networks with random hidden nodes[J]. IEEE Transactions on Neural Networks, 2006, 17 (4) : 879-892. doi: 10.1109/TNN.2006.875977 |
[7] | HUANG G B. What are extreme learning machines? Filling the gap between Frank Rosenblatt's dream and John von Neumann's puzzle[J]. Cognitive Computation, 2015, 7 (3) : 263-278. doi: 10.1007/s12559-015-9333-0 |
[8] | YANG X, CHEN S, CHEN B. Plane-Gaussian artificial neural network[J]. Neural Computing and Applications, 2012, 21 (2) : 305-317. doi: 10.1007/s00521-011-0546-1 |
[9] | BRADLEY P S, MANGASARIAN O L. k-plane clustering[J]. Journal of Global Optimization, 2000, 16 (1) : 23-32. doi: 10.1023/A:1008324625522 |
[10] | MOORE A, ZUEV D, CROGAN M. Discriminators for use in flow-based classification[EB/OL].[2016-02-03]. https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/5050/RR-05-13.pdf?sequence=1. |
[11] | BARTLETT P L. The sample complexity of pattern classification with neural networks:the size of the weights is more important than the size of the network[J]. IEEE Transactions on Information Theory, 1998, 44 (2) : 525-536. doi: 10.1109/18.661502 |