基于PCA的网络流量分析.pdf

《基于PCA的网络流量分析.pdf》由会员分享，可在线阅读，更多相关《基于PCA的网络流量分析.pdf（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北京交通大学硕士学位论文基于PCA的网络流量分析姓名：王敏申请学位级别：硕士专业：通信与信息系统指导教师：陈常嘉20060301北京交通大学硕士学位论文1。1 概述第一章引言网络流量分析一直是通信网络性能分析的一个极其重要的问题。但是目前，网络流量分析的许多工作都是集中在孤立地研究网络中单条链路的流量上。然而，当今网络研究者面临的更重要的问题是需要同时对网络所有链路的流量进行建模和分析，包括流量工程，流量矩阵估算，异常检测，攻击检测，流量预测和容量计划等。然而，同时对网络所有链路的流量进行分析是一个难题，因为仅对一条链路的流量建模都很复杂。因此，全网络流量分析仍是个复杂而重要的挑战。解决全网络

2、流量分析的一个办法是必须认识到网络中不同链路的流量不是相互独立的，实际上是由一系列o D 流和一个路由矩阵决定的。一个o D 流是流量的集合，这些流量从一个入口点进入网络，从一个出口点离开。这些由路由决定的点到点流量的重合就产生了所有链路的流量。因此，代替研究所有链路的流量，一个更直接和根本的方法是研究网络的0 D 流。然而，尽管在概念上o D 流比链路流量更接近网络的特征，研究它们也遇到同样的问题。最主要的问题是0 D 流呈现高维多交特性。这样，最主要的问题就是高维问题。通常，当要分析高维对象时，一个常用而有效的方法就是通过低维近似它的主要特性。因为，通常由于高维导致的复杂性可能由一小部分独

3、立的变量控制，因此能够很好地由这一小部分近似。维数分析和维数北京交通大学硕士学位论文降低技术就是找到这些变量，从而更好地理解原对象。而最常用的分析高维对象的方法是P c A 算法(主成分分析法，也叫K a r h u n e n L o e v e 变换或特征值分析法)。给定个高维对象和相关的坐标空间，P c A 能够找到一个适合给定对象降维的新的坐标空间。一旦将这个对象放入这个新空间，只用一部分坐标表示这个对象就可以达到误差最小。当一个高维对象能以这种方式用一部分维数近似时，我们称这小部分维数是这个对象的内在维数。1 2 论文主要工作A n u k 0 0 1L a k h i n a，M

4、a r kc r o v e ll a，C h r i s t o p h eD i o t 等人1 6 力$黾出将P c A 算法用于网络流量分析领域。因此，在这篇论文中，我将采用P c A算法来研究采样到的某个真实网络流量的内在维数和结构，而不涉及具体的采样方法。尽管我研究的这个网络有近百条流量，但是我们将看到：在很长一段时间里，它的结构也能很好地用小维数来近似。事实上，我们将发现：只要采用3 到7 维就能较好地近似网络中的所有流量。引入特征流的概念能够更好地研究这一低维特性。一个特征流捕获了网络中所有流量的某一特性，每条流量都能表示成特征流的加权，加权系数表示每个特征流的重要性。特征流的

5、这一重要特性使我接下来研究它的性质。研究发现，特征流可分为三类：(1)确定型的特征流，即反映流量中可预测的、周期的趋势的特征流。(2)脉冲型的特征流，即反映流量中一些偶然爆发的、生存时间很短的脉冲形式的流量。(3)噪声型的特征流，即反映了流量中类似高斯噪声的、相对稳定的流量。北京交通大学硕士学位论文这样，通过把流量分解成这些特征流的组合，我们就能够比较直观地看出各流量的内在结构，同时，也能够更好的了解整个网络的行为。事实上，将特征流按照这种方式进行分类，我们将发现，我们能够获得整个网络流量的重要信息。首先，我们发现每条流量都能由小部分特征流近似。这样，每条漉量都有自己相应的某些特征。其次，这些

6、特征可以以一种可预知的方式变化。特别的，我们发现网络中有的流量呈现可预见的周期性变化的趋势；有的流量是由脉冲型的和嗓声型的特征流组成；还有的流量仅仅是一些脉冲型的流量或者仅仅是一些噪声型的流量。因此，特征流的这一分类方法为我们重构和认识整个网络流量提供了个有用的工具，而其中脉冲型的流量有助于检测网络流量的突发点。然而，这篇论文对特征流的研究还有待于进一步的深入。论文还对P c A 算法对网络流量的分解在时域上的相对稳定性进行了研究。实验发现，P c A 对上一时段流量的分析结果对下一时段流量的分析也很有帮助。最后，从一个更宽的角度来说，这篇论文是对网络流量进行维数分析。这篇论文研究的网络流量的

7、内在维数和结构也许会对研究网络流量的其他行为有所帮助，这也是这篇论文的后续工作。这篇论文的结构如下。第二章中我将简单描述网络流量分析的现状。第三章中我将详细介绍P C A 算法的相关知识，通过一个简单的例子和相应的图形进行介绍。第四章将介绍在网络流量分析领域运用P c A 算法的详细步骤。在第五章中，我将给出在一组真实的网络流量数据上运用P c A算法进行处理x北京交通大学顿士学位论文2 1 概述第二章网络流量分析网络流量监测是网络管理和系统管理的一个重要组成部分，网络流量数据为网络的运行和维护提供了重要信息。这些数据对网络的资源分布、容量规划、服务质量分析、错误监测与隔离、安全管理都十分重要

8、。网管人员可以利用它们来监控网络的数据流量，分析网络的使用情况及性能，尽早发现网络的瓶颈，便于调整网络的路由，合理分配网络流量，保证网络高效、稳定、可靠地运行。传统语音业务是时分复用方式的工作机制。因此，一般说来业务流量比较平稳，突发性的流量很少，而且业务流量一般是对称的，即流入流量跟流出流量大致平衡。而目前高速发展的I P 数据业务却和传统的语音业务有着很大的不同，I P 数据业务是统计复用方式的T 作机制，所以业务流量不稳定，突发性大，而且流出流量和流入流量一般来说不平衡，差异性縤i 事j蓐弱搿篝i j 翅嚣响f霪磷争若氮委发性i鞴掩鹭弛娄鬈嫂骊量；堪尘篡型馐剖鬻一篇雪；iE 鲤瓢簿悍墀蕾

9、缁；锴天J|f)箸盂蓓薰；鬻懦毒曜；婴t|；|型l 器*i 鑫!鬻嚣罾理誊婺器i 霪#i!il i i 自d i 羹雾垂简纛臻蘩墨李偿锚篓藿薹儡氇堪型嚯j善；墓鲁8 0 年代，9 0 年代北京交通大学硕士学位论文等)，以及网络应用的使用情况，研究者可以据此研究新的协议与应用，网络提供者也可以据此更好地规划网络。四、网络用户行为监测与分析这对于网络提供者来说非常重要，通过监测访问网络的用户的行为可以了解到：1 某一段时间有多少用户在访问我的网络2 访问我的网络最多的用户是哪些3。这些用户停留了多长时间4 他们来自什么地方5 他们到过我的网络的哪些部分通过这些信息，网络提供者可以更好地为用户提供服

10、务，从而也获得更大的收益。2 3 网络流量的应用一、网络流量可用于校园之中，如学生的宿舍网络异常，网管人员将锁定其I P，并且予以警告，如规劝不听，将予以处分，以免造成网络异常，防止学校服务器挂点。二、有名木马后门程式，从网络流量也可以发现其异常状况，进而防止被侵入。三、I P 重复进入，可能是骇客侵入的征兆，也可从网络流量得知。四、伺服器网络管理，限定进入I 嘬高数目，防止网络拥挤，如：网络游戏每个伺服器都有设最高使用者进入人数，像“天堂7 这个游戏，每个伺服器的最高使用者到五千人进入。1 0北京交通大学硕士学位论文2 4 网络流量的测量I n t e r n e t 流量数据有三种形式：被

11、动数据(指定链路数据)、主动数据(端至端数据)和B G P 路由数据，由此涉及到两种测量方法：被动测量方法和主动测量方法“”。一、主动测量主动测量是指在网络上布置测试平台，主动发送测量的流量，从A到B，获得两端点之间的测量结果信息，如发送I C M P 包或U D P 包等。主动意味着测量过程中产生新的网络流量。这些流量也许是为了引起网络部件的特殊响应(如：t r a c e r o u t e)，也许是为了查看网络为流量提供服务类型的性能(如：t r e n o)。主动测量给网络增加了潜在的荷载负担，特别是如果没有仔细设计使得该方法产生的流量数最小，那么附加的流量会扰乱网络，歪曲分析结果。如

12、：为了测量在I P 网络云中瓶颈链路的带宽，定期地向测试路径发送巨大的T C P 流量，那么由此产生的附加流量可能会产生H e i s e n b e r g 效应，而拥塞通过网络云到达这点的路径，并且测量的吞吐量低于瓶颈链路的带宽。另外，主动测量至少需要多个网络部件某种形式的参与。如：p i n g命令用于估计主机A 到主机B 的R T T，需要主机B 响应I C M PE C H 0 请求信息。有几种形式的合作已经广泛应用在I n t e r n e t 上，如：响应I C M P 请求和匿名F T P 服务器允许主机A 和服务器之间进行吞吐量测量，可以将这种合作定义为被动合作。另一种合作

13、方式是主动合作，如果要测量A 至B 路由的对称性，从B 到A 和从A 到B 同样需要进行路由测量，需要B 也要同样主动参加测量。跟踪和可视化I n t e r n e t 拓扑结构是主动测量最主要的应用，c A I D A北京交通大学硕士学位论文国际组织最近开发的s k i t t e r 动态测量工具可用于动态发现和绘制全球I n t e r n e t 拓扑。同时主动测量技术可以探测网络的特定现象，如发现许多I n t e r n e t 端至端的延迟分布具有重尾特征。I n t e r n e t 的健壮性和可靠性很大程度取决于I s P 网络有效可靠的路由，I n t e r n e

14、t 路由行为的分析直接影响下一代网络硬件、软件和操作政策。主动测量还有其它的应用领域：评估I P 地址空间的利用率，路由的不对称性和不稳定性，按网络地址前缀长度的流量分布，B G P 路由表的空间使用效率，单播和组播路由不一致的程度等。总之，主动测量的优点是灵活、方便。它是端到端之间的测量，可得到端到端之间的网络性能信息。它的不足：由于需要向网络发送流量，会增加网络负担，对网络性能产生影响。大量的流量可能会在瓶颈处产生拥塞，从而使测量值偏离实际值，有系统误差，即H e i s e n b e r g 效应，H e i s e n b e r g 测不准原理。二、被动测量被动测量是在网络中的一点

15、收集流量信息，如使用路由器或交互机收集数据或者一个独立的设各被动地监测网络链路的流量。被动测量可以完全取消附加流量和H e is e n b e r g 效应，这些优点使人们更愿意使用被动测量技术。有些测度使用被动测量获得相当困难：如决定分组所经过的路由。但被动测量的优点使得决定测量之前应该首先考虑被动测量。如果关心的不是完整的I n t e r n e t 路由，而是A S 之间的路由，那么能监测两个对等B G P 之问的流量，因为流量中包含全部的A S 之间的路由信息。被动测量技术遇到的另一个重要问题是目前提出的要求确保隐私和安全问题。网络流量是采用大小不一的报文传送，收集到的数据可以进行

16、各种北京交通大学硕士学位论文2 5 网络流量的分析网络流量的分析在网络行为学中起着一个衔接的作用，主要利用网络流量测量部分收集到的各种流量信息，通过运用一些分析和建模方法对其进行分析，以期发现流量的特性，对网络性能做出客观的评价，并以此作为对网络进行控制和优化的依据。流量分析使得人们能够识别网络中现存的问题，并能够找出问题产生的原因。另一方面，使得人们能够识别出将来会发生的些潜在问题，对网络的性能做出预测，使得网络管理员能够提前查出并解决产生问题的因素，避免网络故障的发生。流量的分析方法主要有两种，一种是基于测量的流量分析方法，一种是基于模拟仿真的流量分析方法“。一、基于测量的分析基于测量的分

17、析是对网络数据进行实时测量，然后再对测量的数据进行分析。按照处理时间的不同可以分为在线分析和离线分析两种。在线分析是从一个局部、详细的角度对流量进行实时分析。它根据客户提出的分析要求进行分析，这里的分析要求可以有范围要求(可以是通过两点之间，某个子网内部以及不同子网之问)、时间要求(可以是某一时刻，也可以是某时间段)、业务类型要求(I n t e r n e t 上现有的各种业务，比如T e l n e t 服务、F T P 服务等)、分析内容要求(延迟变化、吞吐量变化、丢包率变化、流量变化等)以及显示要求(刷新频率及各种显示方式，如表格方式、折线方式、柱状方式等)，最终产生分析结果。离线分析

18、主要是使用数学分析工具和数学模型等技术和方法对网络流量进行更进一步的分析。数学建模主要分为网络建模(网络设备、通J 4北京交通大学硕士学位论文信链路等)和流量建模。正确的模型可以使得我们能够通过模拟来研究各种模型参数对网络性能的影响，进而提高对网络属性和行为的理解。好的网络模型都是依赖于可参数化的流量模型，这些参数都是从网络测量中得来的。针对网络流量的特点，研究人员常使用A R M A(A u t oR e g r e s s i v eM o v i n gA v e r a g e)、网络流量的“分组火车”模型、基于用户行为的模型、小波基模型等1。二、基于模拟仿真的分析模拟网络行为是指模拟

19、网络流量再实际网络中传输、交换和复用的过程。网络仿真获取的网络特性参数包括网络全局性能统计量、网络节点的性能统计量、网络链路的流量和延迟等，由此既可以获取某些业务层的统计数据，也可以得到协议内部的某些特殊的参数的统计结果。网络仿真技术有两个显著的特点：首先，网络仿真能够为网络的规划设计提供可靠的定量依据。其次，网络仿真能够验证实际方案或比较多个不同的设计方案。目前世界上的网络仿真软件可以分为高端和低端两类产品。高端产品一般具有复杂的建模机制、比较完备的模型库、完善的外部接口、强大的功能并能够得到比较可靠的仿真结果。其主流产品基本上都来自美国公司，例如M I L 3 公司的o P N E T、c

20、 A C I 公司的C 0 I N E T、U CB E R K E L E y N S等。低端产品一般只有简单的建模机制、较小的模型库、简单的外部接口，功能单一并且仿真结果的可靠性较差。比较知名的产品也大都来自美国。北京交通大学硕士学位论文(4)可解决回归分析里共线性问题。(5)可咀用来作为一组变量的综合指标，如物价指数等。在这篇论文中，我将采用PcA主要是为了发现和降低数据的维数，发现高维数据背后更丰富的内涵。因为多维空间通常都很难通过视图表示，最主要的研究手段就是降维，然后分析这些合成的结果，它们反映了原对象多方面的特性。通过二到三个变量组成的视图可萋酝馨莽商笛幽￥妻霍茸糍簸藏割新矧擀瞬

21、静 F。磨#虬争雾翮矧酝群鼙晋莲弹擘二量剖l：彗裂陛簪鞫剖塑量眷“嚼确蹦。瓣l 蠢描瞧努进行盹帮鑫侩媸淄j；型，薯l i；引葛名雌氆刑堰厘l，|冀审豢n 鸯鲞F 董蓟誊霎|；：E i。i；萋；斟掣望幂氍掣r；了j 一：j 耍。；i 囊*s 斌-r 尹舻岂i c l l 鞲群罐堕i；川，。；豁l；髦鍪瑟精囊挚净是v。对应的特征值。注意到，矩阵x 7 z的特征向量是正交的，相应的特征值是非负实数。按惯例，特征向量是单位向量，特征值由大至0 _、扫F 歹0，即 2 ：2 A。由于计算矩阵x 的主成分也就相当于计算x 7 x 的特征向量，因此我们来考虑第一主成分。令p 维向量h 代表矩阵x 的第一主成

22、分。正如前所述，第一主轴v，捕获了原测量数据最大的能量“1：V t。a r g 黹I 陋8北京交通大学硕士学位论文盖-k L。一k(1 1 一，工(p)】为推导方便，且不失一般性，设盖是经标准化的(即E b，J o，坛r k，)；1)。现要求一个综合变量r。，f。是z，工)的线性组合，即f。-劫。，恢忙1要使得f 能携带最多的原变异信息，即要求r。的方差取到最大值，f，的方差为妇r(f。)。三肛，1 1 2：!p：z 坳，。p：吻；一九这里，记矿。三。x 是x 的协方差矩阵。当z 中的变量均是标准化变量时，y 就是x 的相关系数矩阵。得把上面的问题写成数学表达式，即求优化问题罂瞀p z 场。H

23、，1 4 _ 1采用拉格朗日算法求解，记 是拉格朗日系数，令一P i p p，一 扫：p，一1)对分别求p。和 的偏导，并令其为零，有皂O儿_!4rp吻戗=I丝慨堕魄北京交通大学硕士学位论文A：t p：坳：=I 么，O：)由于有约束p：P，=o，因此九只能是矩阵y 的第二大特征值，p：是对应于矿第二大特征值的标准化特征向量。依次类推，可求得x 的第 主轴，它是协方差矩阵y 的第 个特征值九对应的标准化特征向量。而第 主成分为f ；p 砌，“)。三P：z 物。九由此有，沈，(f。)z 妇r(f：)z z 妇r(f。)。所以，用数据变异大小来反映数据中的信息，则第一主成分f。携带的信息量最大，f：

24、次之如果抽取了m 个主成分，这m 个主成分所携带的信息量总和为荟妇，荟九综上所述，x 的第 主轴p，它是协方差矩阵y 的第 个特征值九所对应的标准化特征向量，又称为负载向量(1 0 a d i n gv e c t o r)。而第A 主成分f 为原样本点集合在主超平面的第 主轴上的投影构成综合变量，又称为主元、主元得分向量(S c o r ev e c t o r)并且有：娩r 扛。)z 赡r f：)z 砌r f。)定义如下变量：P c A 分析负载阵为P，P p，p 2，p。】北京交通大学硬士学位论文P c A 分析主成分得分矩阵为r，r-f。，f：，则有，T=即或气一净。另外，可以严格证明

25、，主成分I 的样本均值等于零，样本方差等于z阵协方差阵y 的第i 大特征根，并且主成分之间以及主成分所对应的负载向量A 之问都是正交的。3 4P C A 算法分析大。主成分分析的方法即为找出原有变量的线性组合并使其变异数最1 算出协方差矩阵s，或相关矩阵尺2 求s 或月的特征值及单位特征向量3-将特征值依大小顺序排列，设分别为，A：，A。4 求出对应的单位特征向量V，V：，v。，其中v；v，=1，且V 以=o，则_)，1 三V 1。J=V 1 1 x 1+V 1 2 工2+V 1 P 工Py 2=V 2 z 幂V 2 l x l+V 2 2 工2+。+V 2 p 工Pj!y p _ V P。z

26、=V P I 工J+V P 2 工2+V 伊工P分北京交通大学硕士学位论文细描述P C A 算法的各个步骤。3 4 1 获取数据为了便于下面的说明，构造下面两个变量“1：膏霉(2 5o 52 21 93 12 3211 51 1)ry=(2 4o 72 92 23 o2 71，61 11 6o 9 尸它们构成矩阵d=0y)。这是一组二维数据，之所以选择它作为例子，是为了能够采用图形来说明P c A 算法每一步的结果。这组数据的图形如图3 2 所示。图3 2P C A 算法示例图形北京交通大学硕士学位论文3 4 2 数据处理为了使P c A 能更有效的工作，必须首先对数据矩阵进行处理，所谓的处理

27、也就是将代表数据各维数的变量减去其对应的均值，即使各变量均值为零。这样在以下步骤的坐标变换中，坐标空间的原点位置将保持不变。因此在我们的这个示例中，也就是将变量z 减去其均值i，变量y 减去其均值歹，处理后的数据如下所示：D f o 6 9 1 3 1o 3 9o 0 91 2 9o 4 9o 1 9一o 8 1 一o 3 1 一o 7 1 1 7I o 4 9 一1 2 1o 9 9o 2 91 0 9o 7 9 一o，3 l o 8 1 一o 3 1 1 叭I其图形如图3 3 所示。图3 3 数据处理后的图形北京交通大学硕士学位论文3 4 3 计算协方差矩阵就是计算代表原数据各维数的变量间

28、的协方差组成的矩阵，即：c=(=吲=黝我们的数据是二维的，因此其协方差矩阵将是2 x 2 维的。其协方差矩阵如下：O 6 1 6 5 5 5 5 5 6 O 6 1 5 4 4 4 4 4 4、刚。lo _ 6 1 5 4 4 4 4 4 4o 7 1 6 5 5 5 5 5 6J从上面的协方差矩阵可以看出，非对角线上的元素都是正数，这说明变量x 和y 是同增长或同减小的。3 4 4 计算特征值和特征向量因为协方差矩阵是方阵，因此我们可以计算它的特征值和特征向量。这一点很重要，因为我们可以从中获取反映原数据矩阵的重要的信息。以下是计算得到的特征值和特征向量：A；P 4 9 0 8 3 3 9

29、8 9 1I1 2 8 4 J 0 2 7 7 lJv：f o 7 3 5 1 7 8 6 5 6 一o 6 7 7 8 7 3 3 9 9 1Io 6 7 7 8 7 3 3 9 9一o 7 3 5 1 7 8 6 5 6 J注意到，这些特征向量都是单位向量，即它们的模为1。这一点在P C A 算法中很重要，许多数学工具也能直接得到单位长度的特征向量的结果。北京交通大学硕士学位论文，?，+。，-，图3。4 处理后的数据和其特征向量这些特征向量说明什么呢?让我们来看看图3 4。从图3 4 中我们可以看出特征向量所反映出来的原数据矩阵内在的明显特征。从协方差矩阵可以看出，变量x 和y 是同增长或

30、同减小的。在图3 4 中，我以虚线的形式画出了特征向量的方向。这两个特征向量是相互正交的，且都经过原点，更重要的一点是，它们提供了反映原数据矩阵内在特征的重要信息。我们看到其中一个特征向量穿过原数据的各个点的附近，就像画了一条最匹配的直线，即原数据各个点都分布在这个特征向量的两侧。这个特征向量告诉我们原数据矩阵的两个变量间的关系。另一个特征向量给我们提供的原数据矩阵内在特征的信息量较第一个少。因此，通过计算协方差矩阵的特征向量，我们就能提取原数据矩阵的内在特征。o堪，怄o北京交通大学硕士学位论文3 4 5 选择主成分这一步是数据压缩和降维的所在。如果你仔细观察了上一步骤得到的特征向量和特征值，

31、你就会发现这些特征值差别很大。事实上，对应的特征值大的特征向量也就是原数据矩阵的主成分。在我们的例子中，对应的特征值较大的那个特征向量也就是穿过原数据点的那条直线的方向。通常，一旦从协方差矩阵得到特征向量，下一步就是按照它们对应的特征值的大小进行排序，这一步正反映了各个成分的重要程度。现在，只要你喜欢，你可以忽略那些重要性小的成分。这样做你确实损失了些信息，但是只要那些特征值足够小，你损失的信息量也就足够小。假如你删除了一些成分，那么最后的数据矩阵的维数将小于原数据矩阵的维数。也就是说，假如你原来的数据矩阵是，l 维，这样你就会得到n 个特征值和特征向量，然后你仅选择了前p 个特征向量，那么最

32、后的数据矩阵就是p 维的。现在我们需要做的就是选择主成分。这就是要求我们从特征向量列表中选择我们需要留下的那些特征向量，并组成一个新的特征向量矩阵。结合我们的例子，我们只有2 个特征向量，因此我们只有2 个选择。我们或者可以将这两个特征向量都保留：矿=怯需黧器1 I O 7 3 5 1 7 8 6 5 6O 6 7 7 8 7 3 3 9 9J一或者删除其中重要性小的成分，仅保留其中一个：矿。(：罢鬻嚣)I 一0 7 3 5 1 7 8 6 5 6J(2)2 8北京交通大学硕士学位论文我们将在下步骤中看到这两个选择的结果。3 4 6 导出新数据矩阵这是P c A 算法的最后一步，也是最容易的一

33、步。一旦我们选定了主成分并组成新的特征矩阵，只要将其转置并左乘原处理的数据矩阵，即：D f。y D这个式子告诉我们什么呢?它告诉我们原数据可以由这些向量表示。我们原来的数据是2 维的，即x 和y，它们由z 和y 构成的坐标空问决定。我们可以由任意两个正交的坐标轴构成的空间来表示这组数据。通过P C A 变换，我们将原数据从由x 和y 构成的空间转变成由这些特征向量构成的空间。假如我们为了降维，如删除了一部分特征向量，则重构的数据只决定于剩余的特征向量构成的空间。回到我们的例子，上一步骤中，我们选择了两个新的特征向量矩阵，下面我将给出如何由这两个特征矩阵重构原数据，以及两者之间的区别。由矩阵(1

34、)进行转换，我们得到重构的数据如下：D lcO 8 2 7 9 7 0 1 8 61 7 7 7 5 8 0 3 30 9 9 2 1 9 7 4 9 40 2 7 4 2 1 0 4 1 61 6 7 5 8 0 1 4 2一o 9 1 2 9 4 9 1 0 30 0 9 9 1 9 0 4 3 7 51 1 4 4 5 7 2 1 6o 4 3 8 0 4 6 1 3 71 2 2 3 8 2 0 5 6一O 1 7 5 1 1 5 3 0 7O 1 4 2 8 5 7 2 2 70 3 8 4 3 7 4 9 8 9O 1 3 0 4 1 7 2 0 70 2 0 9 4 9 8 4

35、6 10 1 7 5 2 8 2 4 4 40 3 4 9 8 2 4 6 9 8O 0 4 6 4 1 7 2 5 8 20 0 1 7 7 6 4 6 2 9 70 1 6 2 6 7 5 2 8 7北京交通大学硕士学位论文其图形如图3 5 所示。p_+十+十H一_图3 5 由2 个特征向量重构的数据从图3 5 中可以看出，重构的数据即是原数据，只是进行了坐标轴翻转，两个特征向量变成了原来的x 和y 坐标轴。这一点是很容易理解的，因为在我们采用矩阵(1)进行数据重构的时候，我们并没有删除任何特征向量，因此重构后，也就没有任何信息损失，而仅仅是坐标轴进行了翻转，即两个特征向量变成了原来的z

36、和v 坐标轴。另一个转换就是采用矩阵(2)，即只保留了第一个特征向量的那个矩阵，那么重构后结果会如何呢?采用矩阵(2)重构后的数据如下：协，o蛄一之北京交通大学硕士学位论文那么这一步到底有什么用昵?通常，我们通过数据之间的内在特征来表示数据，它们很好的反映了数据之问的关系。这一点很有用，因为这样我们能更好的分类我们的数据。起初，我们通过x 和y 坐标来表示数据，这样当然也没问题。但是每一点的x 和y 坐标并不能很好的说明这些数据之间的关系。通过转换后，我们就能很容易的看出每一点在新的坐标轴上的位置关系(坐标轴上方或下方)。在使用矩阵(1)，即保留所有特征向量的矩阵进行转换时，我们仅仅将原数据进

37、行了翻转，即只是将原数据从由x 和)，构成的空间变换到由特征向量构成的空间。而由矩阵(2)，即只保留了一个特征向量的矩阵进行转换时，我们损失了由被删除的特征向量贡献的信息。3 5 找回原数据在使用P C A 算法进行数据压缩的时候，如何找回原数据显然是最关心的问题。那么，我们如何找回原数据昵?在进行之前，我们必须明确，在我们的转换过程中，只有将所有的特征向量都包含在特征相量矩阵里，我们才可能精确的得到原数据。如果在转换过程中，我们删除了一部分特征向量，那么找回的数据将会有一定的信息损失。在上一小节P c A 算法的步骤中，最后的变换式子如下：D|=y D j将上式进行变换以雩导到原数据：D=杪

38、)-1 D。北京交通大学硕士学位论文下面，我将给出由上面两个特征向量矩阵(1)和(2)重构原数据的结果。由矩阵(1)重构的结果如图3 7 所示。从图中我们可以发现，这就是原数据的图形。为什么呢?原因很简单，因为我们保留了所有的特征向量，即保留了所有的信息，因此在重构的过程中没有任何信息损失。因此重构后的数据也就是原来的数据。接着，我将给出删除了一些特征向量后重构的数据的图形，即采用矩阵(2)进行重构，以展示信息如何损失。图3 8 给出了这一结果。+，+t一一+图3 8 使用1 个特征向量重构的数据将其与图3 7 所示的数据进行比较，你将发现沿着第一个特征向量方向上的信息被保留了，而沿着第二个特

39、征向量方向上的信息被删除了。北京交通大学硕士学位论文其中l 陋0 表示原测量数据沿着V 轴上的能量。上面的公式也可以写为如下的形式：h2 鹕帮：鹕m 积掣oV Vv Z 7 m，。盯g 珊3 忑一依此递推，一旦前t 一1 个主成分确定后，第t 个主成分就对应于剩余能量中最大的方向。剩余能量就是原数据的减去前七一1 个主成分的能量后剩余的能量。这样，我们将第t 个主成分咋表示如下：”唱黹卜寸1|相同的原因，由于计算第女个主成分相当于寻找矩阵x 7 z 的第t 个特征向量，因此，计算所有的主成分组成的集合和i k。就相当于计算矩阵z 7 x 的所有特征向量。经过如此计算得到的主成分v，v：，v。具

40、有如下几个性质：(1)各主成分间互不相关，即对任意的f 和J，u 和v j 的相关系数c o r，h)一仁；二?(2)组合系数k n，口。：，n。)构成的向量也是单位向量。V=d f l V l+i 2 V 2+口中V P北京交通大学硕士学位论文o D 流最大的特征信息，“：提取了次大的特征信息，依此类推。正因为岳j k。能捕获原网络流量数据中所有o D 流中共同的时变趋势，我们将其定义为原数据矩阵x 的特征流。主成分集合饥乜依照列的次序构成主成分矩阵y，其为p xp 型。同样，我们也能够以；为列构成r p 型矩阵U。结合y 和u，我们可以得到每条O D 流j：x i：u 妒7 lf=1，p其

41、中x；是第f 条o D 流的时问序列，妒7 l 是矩阵y 的第f 行。上面的公式表明：每条O D 流z。都可以表示成特征流的线性组合，组合系数为妒l。图4 2 和图4 3 显示的是分解后的某个特征流“和它对应的主成分v，的典型例子a 从图中可以看出，特征流H。捕获了网络流量中的某一时变特性，而主成分H 则确定了这一时变所发生的方向。图4 2 分解后的一个特征流4 0北京交通大学硕士学位论文在进行下一章前，我将利用一小节的篇幅描述一个很重要的概念：0 D 流。4 3O D 流研究全网络流量时，我们必须认识到，一个网络中不同链路的流量不是相互独立的，而这个网络的流量事实上是由个o D 流集合和一个

42、路由矩阵决定的。那么，什么是O D 流昵?所谓0 D(0 r i g i n D e s t i n a t i o n)流，就是一些流量的集合，这些流量从网络的一个节点(称入口点)进入网络，从一个节点(称出口点)离开网络。这些由路由决定的点到点之间的流量的重叠，就构成了整个网络中所有链路的流量。因此，研究网络流量的一个更直接、更基本的方法不是研究所以链路的流量，而是研究网络中的o D 流集合。我们平时接触最多的是链路流，比较容易获取的数据也是链路流的数据。那么，链路流和o D 流之间的关系如何呢?它们之间通过路由矩阵一关联。矩阵爿的大小是链路流o D 流，其中，如果0 D 流j 经过链路f，

43、则=1，否则=o。因此，o D 流向量(z)和链路向量(y)之间存在如下关系：)，=爿z流量工程就是调整路由矩阵一的过程，也就是给定些O D 流x，在定的程度上影响链路流y。因此，精确的流量工程和链路容量规划等领域都依赖于更好的理解0 D 流的特性。北京交通大学硕士学位论文第五章分析网络流量数据5 1 概述这篇论文中采用P c A 算法对0 D 流的分析是基于一个真实的网络的数据。这组数据是实验室从中国最大的I P 网络的骨干链路上获取的M R T G(f u l t i R o u t e rT r a f f i cG r a p h e r)数据。由于保密的原因，在此不便公布这个网络的真

44、实名字。M R T G 是一种基于s N M P 的监控网络链路流量负载的工具，它能记录一个路由器各个接口流入和流出的流量信息。从M R T G 数据中，以1 8 0 0 秒(即半小时)的间隔滤出连续1 0 天的记录，即从2 0 0 1 年4 月2 8 日0 0：o o 到2 0 0 1 年5 月7 日2 4：o o。这些是链路流的数据，然后实验室利用路由矩阵爿将其转换为0 D 流矩阵。因此，这个网络共有6 3 条O D 流，而每条o D 流均采样了4 8 1 个点，因此P c A 算法研究的数据矩阵J 是一个4 8 1 6 3 的矩阵。这是一个高维的数据矩阵，在采用P C A 算法进行处理前

45、，我们只能用图形孤立的显示每条0 D 流的状况。在前面的章节已经强调过每条0 D 流的流量不是相互独立的，因此这种图形显示并没有多大的意义。采用P c A 算法分析这组链路流量，将得到一个6 3 6 3 的主成分矩阵y 和个4 8 l x 6 3 的特征流矩阵u。这一处理是在t l a b 中完成的。下面，我将给出P C A 算法作用于网络流量数据的仿真结果，并进行详细的讨论。5 2 仿真结果及讨论正如前面的章节说明的那样，这篇论文的基础就是采用P c A 算法将一个网络中的所有o D 流分解成相应的主成分和特征流。在这一章中，我将给出这一处理的结果。首先，我们将看到一部分特征流就足够很好的重

46、建o D 流了也就是说，o D 流呈现低维性质。然后，我将研究每条o D 流的组成，也就是说，每条o D 流究竟是由那些特征流组成的。这一问题又引出对特征流的考察上来。最后，我又探讨了P c A 对o D 流的分解在时域上的相对稳定性问题。5 2 1o D 流的低维特性及重构P c A 算法运用于网络流量数据的主要作用就是降维。降维也就是要删除一部分维数，即删除一部分信息。在前面的章节中已经描述过，特征值A 的一个重要性质就是反映了对应的特征向量，即主成分v 所携带的信息，即01 02 0加卯印7 0图5 1 主成分的累积贡献率，987654000000北京交通大学硕士学位论文D 2；其图形如

47、图3 6 所示。一0 8 2 7 9 7 0 1 8 61 7 7 7 5 8 0 3 3一O 9 9 2 1 9 7 4 9 40 2 7 4 2 1 0 4 1 61 6 7 5 8 0 1 4 20，9 1 2 9 4 9 1 0 30 0 9 9 1 9 0 4 3 7 51 _ 1 4 4 5 7 2 1 6O 4 3 8 0 4 6 1 3 7北京交通大学硕士学位论文那么，o D 流的这一低维性质是如何产生的呢?至少有两方面的原因导致这一低维性质。首先，在原数据中，如果各维数间的差异非常大，那么数据就可能存在低维性质。这也就是说，原数据中一部分维数的方差占据了很大的比重。其次，如果

48、这些时间序列在维数上有共同的趋势或特征，那么它们将可能存在低维特性也就是说，如果维数问存在不可忽视的相关性，那么就存在这一低维性质。5 2 20 D 流的结构下面我们来研究每条0 D 流具体由哪些特征流组成的，也就是研究上一章的公式：z，=u 杪7 lf=1，p前面提到，这一公式表明：每条O D 流x 都可以表示成特征流的线性组合，组合系数即为妒7 j。也就是说：主成分矩阵y 的第行亍即表明各个特征流对第翻隆0 D 流的贡献率。这一点很重要，这样我们就可以通过矩阵y 的每行来研究0 D 流的组成每条o D 流是由哪些特征流组成的，两条o D 流可以通过转化成特征流的表示找出相似点和不同点。观察

49、矩阵y 的每行，我们将发现在特征流如何构成o D 流方面的一些结果。首先，我们将看到每个o D 流都仅仅由一小部分特征流组成。我们来考察矩阵矿的任意一行。我们关心的是这一行中到底有多少个值是显著非零的。因此，我们可以设置一个门限值来计算这一行中有多少个值的绝对值大于此门限值。理论上，通常此门限值取为1 i，其中p 是代表我们研究的网络中所有0 D 流的数量。将矩阵y 的每一行减去4 8北京交通大学硕士学位论文这一门限值1 i。注意，在运算前，保证矩阵矿的每一列是单位向量。图5 3 就是主成分矩阵y 的每个元素与门限值i 比较的结果。图5 3 主成分矩阵矿各元素与门限值的比较图5 3 中，圆点是

50、代表矩阵矿中绝对值大于此门限值的元素。我们看到，处理后矩阵y 的大多数行都在1 0 个点左右。对于o D 流来说，这意味着任意一条o D 流都由1 0 个左右的特征流组成，通常更少。这结果也意味着我们可以认为每条0 D 流都有相应的一部分特征。这样，我们可以通过这些特征来研究每条0 D 流的性质。、其次，我们来研究0 D 流间的差异。强调一点，图5 3 中，特征流的索引按照对应的特征值的大小排序。我们看到，图5 3 中，有的o D 流主要由前几个特征流组成，有的o D 流主要由中间部分的特征流组成，而有的O D北京交通丈学硕士学位论文流却主要由后面部分的特征流组成。将图5 3 矩阵各行的顺序调