论文研究-基于半监督自动谱聚类算法的网络故障检测.pdf

所需积分/C币:6 2019-09-10 11:22:02 643KB .PDF
收藏 收藏
举报

针对网络故障检测中利用先验知识不足和多数谱聚类算法需事先确定聚类数的问题,提出一种新的基于成对约束信息传播与自动确定聚类数相结合的半监督自动谱聚类算法。通过学习一种新的相似性测度函数来满足约束条件,改进NJW聚类算法,对非规范化的Laplacian矩阵特征向量进行自动谱聚类,从而提高聚类性能。在UCI标准数据集和网络实测数据上的实验表明,该算法较相关比对算法聚类准确率更高,可满足网络故障检测的实际需要。
姜大庆,夏士雄,周勇:基于半监督自动谱聚类算法的网络故障检测 2012,48(30) K表示,其元素K。为: 因此,一般谱聚类算法中需要预先聚类分组数k。聚 类分组数k的估计实质上是选择对数据进行准确划 分的最佳特征数。日前自动估计聚类分组数的谱聚 K (1)类算法在一些公共数据集上的实验结果不太令人满 意。本文借鉴文献2的方法,通过改进 k-means算 (i,)∈C 法中划分数据点到聚类中心的方法,在未经规范化 0, otherwise 的 Laplacian矩阵的特征向量上多次运行 k-means算 其中,尺度参数c表示 Must-link约束和 Cannot-link法以搜索并确定最佳的分组数。自动确定聚类分组 约東的严格程度,取值范围均为(0,+∞),其值越小表数的算法的基本步骤如下 示约束性越强,木文在实验中取8=103。 步骤1令q=2。 定义2(约東对传播相似度矩阵)假设数据集X 步骤2利用 Laplacian矩阵的前q个最大特征向 {xx2…,x}的相似度矩阵为W,W=exp(da(x 量构造矩阵F=[,υ2,…,ya∈R"。 x,)2a2),k为数据集中点对的约束信息矩阵构造 步骤3将矩阵Y的每一行看成是R空间内的 一个新的相似度矩阵作为约束对传播相似度矩阵: 点,初始化q+1个中心点,其中第q+1个中心点 w=O+K=w-w(+KwKw (2 位于原点,使用改进的k- means算法对其聚类。 其中,Ⅰ为单位矩阵。 步骤4如果第q+1个聚类不为空,则令q=q+1, 可以证明,矩阵W满足对称性和非负性,有效融 并转到步骤2;否则,确定的聚类数目即为q,算法结 合了数据集原有相似度及其约束信息的基本特征叫。 束,输出聚类数据。 用它所蕴含的新的相似性测度函数重新度量数据集 上述算法的关键在于对k- means算法中数据点 样本的相似性。但是由于矩阵形的某些元素可能为 与聚类中心的距离计算方法的改进。本文通过以下 负值(主要归因于 Cannot-link约東),且部分样本的 的方法计算数据点v与聚类中心c的距离 中度也可能为负(即∑币<0),无法计算规范化的图的 (1)若he,说明聚类中心点c距离原点 Laplacian矩阵,因此本文将这些元素统·替换为0。 较远,则数据点ν与聚类中心c的距离 dist(v, ci) 基于相似性传播调整相似度矩阵的算法步骤λ 如下 步骤1利用公式(1)基于 Must-link约東集构造 (2)若cc<p,即聚类中心点c距离原点较近 矩阵K,再用公式(2)计算矩阵W"=+K")。则使用欧氏距离(,.)=|p-cP。 步骤2假设 Cannot-link集包含n个元素,利用 上式中,尺度参数ρ一般取0.01,λ可根据经验 公式(1)基于 Cannot-link约束集中的第个元素构造确定。根据数据聚类中心的特点来计算数据点与聚 矩阵K",={1,2,…n},并利用公式(2)计算W=类中心的距离,可使得在同一类中的数据点与聚类 (")+K“) 中心更近,而不同类中的数据点与聚类中心更远。 步骤3求出新的相似度矩阵A,其元素A=随着给定的特征向量数的增大,数据点越来越远离 max(o, min(w C,I c2 )) 原点,当达到一定程度的聚类数日后,没有数据点再 位于以原心为中心的聚类中,从而使算法收敛。 算法首先通过 Must-link约束集信息传播修改相 似度矩阵,然后施加 Cannot-link约束集信息对相23平监督自动谱聚类算法小结 度矩阵进行局部修正。成对约束先验信息起到直接 本文设计的半监督自动谱聚类算法与经典NJW 修改相似度的作用。由于新的相似性测度同吋反映谱聚类算法的区别就在于不仅能自动确定聚类数 了成对约束先验信息和数据自身相似性关系,因而日,而且能够充分有效地利用成对点的约束信息,优 可以有效地避免由于提供了信息含量少的约束所造化相假性矩阵,提高聚类的性能。现将木文的半监 成的对聚类的误导作用 督自动谱聚类算法步骤归纳如下: 22自动确定聚类的数日 步骤1对数据集X={x1,x2,…,xn}构造相似度 谱聚类算法主要是用特征分解的谱特征再以传矩阵W,矩阵元素W用高斯核函数构造,N 统的聚类方法(如 k-means算法等)完成聚类任务的。cxp(dis(xx)20),尺度参数a的值可根据经验或 92 2012,48(30) Computer Engineering and Applications计算机工程与应用 先验知识 训练数据数据 预处 数据 分 故障故障 类别报告 网络 聚类 故障 理 器学习知识库 分析处理 数据 采集 实时状态数据 是 故障检测→<安生故障? 图1基于半监督自动谱聚类的网络故障检测模型 采用网络搜索的方法自动确定。 3半监督自动谱聚类算法在网络故障检测中 步骤2根据成对点约束信息将相似度矩阵W变的应用 换为新的相似度矩阵A。 网络故障检测的日的是通过对网络设备的性能 步骤3计算度矩D,其中D=∑4,并构造数据及产生的事件(如网络状态变化SNMP临阱或 通告等)的特征进行分析,找出可能的故障类型和原 矩阵L=D12AD2,令 因。图1为一种基于半监督自动谱聚类算法的网络 步骤4利用L的前q个最大特征向量(重复特征故障检测模型。 值选择正交的特征向量),构造矩阵Y=[,y2,…,y引e 由图1可知,数据聚类是网络故障检测过程中的 R 关键步骤之一。通过网络数据采集器采集到的训练 步骤5将矩阵y的每一行看成是R"空间内的一数据经预处理后进行聚类分析,获取数据样本的聚 点初始化q+1个中心点Cc…,Cn+1,其中第q+1类特性,输入分类器进行学丬并将故障学习结果放 个中心点位于原点。 入故障知识库;故障检测时将从网络实时采集的数 步骤6对每一个聚类中 用改进的距离计据输入故障知识库进行比对,得出故障类型及原因 4算方法计算每个点和它之间的距离把每个点分配并进行处理与报警。先验知识及对于聚类结果的准 到离它最近的中心。 确性具有十分重要的作用,同时由于故障现象的复 步7计算新划分类的平均值作为新的聚类中杂性和多变性,导致故障类别个数难以通过人为方 法确定。基于半监督的自动谱聚类方法应用于网终 q+1 故障检测过程的具体描述为:(1)对经过预处理的网 步骤8如果|c2 c2…c-≥络状态数据用成对约束信息进行相似度矩阵的调 δ一般取001),即中心位置仍在改变,则转向步骤6,整;(2)运用改进的NJW谱聚类算法进行数据聚类, 否则,进入下一步。 自动得出聚类数日及结果。 步骤9如果第q+1个聚类不为空,则令q=q+1 并转到步骤4;否则,输出聚类数据。 4实验结果与分析 步骤10当且仅当矩阵Y的第i行为第/类,则将 为了验证本文方法的聚类性能,分别在一组UCI 数据点x,划分到第j类。算法结束。 标准数据集和某校园网的实测数据卜进行实验,选择 从算法描述中可以看出,其运算时间主要消耗的比对算法包括与本文相类似的SAP算法門、DS-SSC 在相似度矩阵构造和调整(步骤1-步骤2)、 Laplacian算法和 ASFSC算法叫。 矩阵的特征分解(步骤4)和多次k- means迭代确定聚类4.1实验方法 个数(步骤6~步骤8)上,这里:(1)构造和调整相似度 对每个数据集,采用5折交叉检验成对约束对聚 矩阵的时间复杂度为O(2n);(2)n阶 Laplacian矩阵的类结果的影响,每次从原始数据集中选取80%作为训 特征分解的时间复杂度为O(n2);(3)k-1次 k-means练数据集,其余的20%作为测试数据集,每次只对测 聚类循环的时问复杂度为O(k2+k-2)xn×12),t为试数据集进行聚类结果的评估。约束对从训练数据 k- means收敛时所需的迭代次数,<<n,k≤n。综上集中随机产生,数目为0~200之间,在每确定数量 分析,本文算法总的时间复杂度近似为O(2n2+n3+的成对约束下,对每一数据集重复实验50次,输出平 (k2+k-2)×n×2)=O(n2),虽与经典NJW算法为同均结果。为了反映成对约束信息对算法性能的影 量级,但解决了半监督学习和自动确定聚类数的响,即通过判断不同类之间的点对是否被划分到不 问题 同类中,同一类的点对是否仍被划分在同一类中对 姜大庆,夏士雄,周勇:基于半监督自动谱聚类算法的网络故障检测 2012,48(30) 聚类结果评价,采用 Klein等人提出的CRI指标表示余算法在所有数据集上的CR/都有不同程度的提高, 聚类精确度1。 这说明多数算法随着约束对数目的不断增加,其聚 CR=划分正确的点对数目一约束对数目(3)类性能都逐渐得到改善。同时也说明经过本文方法 n×(n-1)2-约束对数目 改进后的NJW算法较经典的NJW算法的聚类性能 其中,n为数据集中的样本数,对于一个具有m个提高。 样本的数据集,存在n(n-1)/2个样本。实验在内存 (2)除了在 New-thyroid数据集上 DS-SSO算法 为2GB,CPU为 Pentium dual-core32GHz,操作系的性能高于本文算法外,在其余数据集上,本文算法 统为 Windows Xp平台上进行。 的性能都要高于其他算法,其屮尤以 Glass数据集最 4.2UCI标准数据集 为明显。这也说明本文算法对数据集的敏感度很 实验中用到的数据UCI标准数据集包括:Iono-小,算法的稳定性和鲁棒性较高。 sphere数据集、 Glass数据集、New- thyroid数据集和 (3) ASFSC算法在大部分数据集上都呈现较好 Diabetes数据集。表1给出相关数据集的数据特征。的聚类结果,但New- thvroid数据集上随着约束对数 图2分别给出SAP、 DS-SSC、 ASFSO和本文算法在这目的增加,其CR先升后降,说明单纯只利用约束信息 4个数据集上的CR聚类结果评价(对其中涉及到参时,可能造成约束的错误传播,使约束对对数据划分 数选择的算法,采用网格搜索的方法来自动选择最起不到应有的指导作用,从而导致聚类性能的下降。 优参数)。 实验结果表明,在UCI标准数据集上,随着约束 表1实验数据集的数据特征 对数量的增加,本文算法的聚类性能呈上升趋势,且 据集 样本数维数回有类数 在约東信息比较充分的条件下,本文算法相对于其 lonosphcrc 他比对算法具有一定的优越性 214 43网络实测数据 New-thyroid 215 2632 下面再以某高校校园网实测数据对本文算法进 Diabetes 行进一步验证。网络拓扑图如图3所示。 从图2可以观察到 采用SNMP轮询的方法对核心交换机下联的3 (1)当不提供成对约束(约東对数为0)时,所有个子网端口及与路由器相联端口平均出、入流量、CRC 算法的CR均较小;随着约束对数量的增加,除了校验错、丢包率、端口协议、端口管理状态、端口当前 ∧SFSC算法在New- thyroid数据集上有所下降外,其状态端口检测等数据进行集,采样间隔为60s,获 1.0 0.9 0.9 0.8 0.8 0.7 吾本文算法 本文算法 0.6+ SAP DS-SSC 0.5 DS-SSC ASFSC ASFSC 0.4 0.4 020406080100120140160180200 020406080100120140160180200 约束对数量 约束对数量 ( a)lonoshpere (b)Glass 10 -,?21 0.9 0.8 普本文算法 0.7 本文算法 0.6 H - SAP DS-SSC DS-SSC ASFSC 0.5 ASFSC 0.4 0.4 020406080100120140160180200 020406080100120140160180200 约束对数量 约束对数量 (c)New-thyroid (d)Diabetes 图2各种聚类算法聚类结果的CRI指标对比 942012,48(30) Computer Engineering and Applications计算机工程与应用 得1044条样本数据,每个样本包含10个属性变量。检测的实际需要。但本文方法在数据维数过高及大 进行预处理,取其屮对故障状态有较大影响的3个属规模样本数据集上与其他谱聚类算法一样存在计算 性(即端口管理状态、端口当前状态、端口检测),并时间过长的问题,如何适应网络规模和复杂性的增 对其进行数值化。然后使用本文算法进行故障聚类大,缩短本文算法的运行时间,是下一步的研究方向。 实验(加入成对约束数为200),实验过程中人为设置 链路通断状态及网络阻塞等故障现象。实验结果如参考文献 表2所示。其屮,故障号1为适配器故障,2为物理链 [1 Chiang L H, Russell E L, Braatz R D Fault detection and 路故障,3为管理性关闭,4为协议故障。 diagnosis in industrial systems[M]. Great Britain: Sprin er-Verlag London Limited, 2001 Internet [2] Verma D, Meila M.A comparison of spectral clustering 子网1 algorithms[R].2003-05-01 3]张育林,庄健,王娜,等.一种自适应局部线性嵌入与谱聚 类融合的故障诊断方法门西安交通大学学报,2010,44 子网2 路由器核心交换机 1):77-82 「41王娜,杜海峰,庄主健,等用于故障诊断的网络分割谱聚类 服务器群 方法门机械工程学报,2008,44(10):228-233 图3实验网络拓扑图 5]肖宇,于剑基于近邻传播算法的半监督聚类软件学报 2008,19(11):2803-2813 表2网络故障实验结果(成对约束数-200) [6]王玲,薄列峰,焦李成密度敏感的半监督谱聚类[]软件学 检測集样本总数检出数准确率/(%) 报,2007,l8(10):2412-2422 正常样本 562 528 92.2 [7]王会青,陈俊杰基于图划分的谱聚类方法的研究[计算 故障号1 123 99.2 机工程与设计,2011,32(1):289-292 故障号2 99.0 故障号3 100.0 [8] Ng A Y, Jordan M L, Weiss Y On spectral clustering anal- 枚障号4 210 201 95.6 ysis and an algorithm[C]//Advances in Neural Informa- 总计10441001959 tion Processing Systems. USA: MIT Press, 2002: 849-856 [9 Wagstaff K, Cardie C Clustering with instance-level 从实验结果可以看出,除故障号4由丁与正常样 straints[C]/Pat L. Proc of the 17th Int'l Conf on Ma 本之间重叠严重导致检出率较低外,其他均有很好 chine Learning(ICML 2000).Stanford: Morgan Kaufmann 的检测效果,本文提出的算法在实际网络环境中故 Publishers,2000:1103-1110 障检测率达到95%以上,显示出该算法可以满足网络[10 Klein D, Kamyar s d, Manning C D From instance-level 故障检测的实际需要。 constraints to space-level constraints making the most of prior know ledge in data clustering [C]/Sammut C 5结论 Hoffmann a G. proc of the 19th Int'I Conf on machine 在网络故障管理中易于获得各种成对约束先验 Learning. Sydney: Morgan Kaufmann Publishers, 2002 信息,有效地利用成对约束信息可以提高算法的聚 307-314. 类性能。本文将谱聚类方法引入网络故障诊断中 [11 Lu 7, Perpinan M A Constrained spectral clustering through 提出半监督的自动谱聚类算法将成对约東信息和数 affinity propagation[C]/Proceedings of the Compuler Vi- 据样本本身的特征信息进行融合,构造新的相似度 sion and Pattern Recognition, 2008 [12 Sanguinetti G, Laidler J, Lawrence N D Automatic de 矩阵以度量具有约東关系的数据样本之间的相似 termination of the number of clusters using spectral al- 性,然后利用自动谱聚类方法进行数据聚类。在UCI gorithms[C]/Proc of IEEE Machine Learning for Signal 标准数据集上对该算法与相关比对算法进行了准确 Processing, USA, 2005: 28-30 性比较实验,结果表明该方法的优越性;在网络实测[13]戴月明,高倩自适应半监督模糊谱聚类算法门计算机工 数据上进行的实验也证明该方法可以满足网络故障 程与应用,2010,46(33):212-214

...展开详情
试读 6P 论文研究-基于半监督自动谱聚类算法的网络故障检测.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744435 欢迎大家使用并留下宝贵意见
    2019-09-10
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于半监督自动谱聚类算法的网络故障检测.pdf 6积分/C币 立即下载
    1/6
    论文研究-基于半监督自动谱聚类算法的网络故障检测.pdf第1页
    论文研究-基于半监督自动谱聚类算法的网络故障检测.pdf第2页

    试读已结束,剩余4页未读...

    6积分/C币 立即下载 >