（计算机软件与理论专业论文）数据挖掘技术在网络故障诊断中的应用研究.pdf

捅要 摘要 随着数据库技术的成熟应用和i n t e m e t 的迅速发展，人类积累的数据量正在 以指数速度增长。对于这些数据，不能只应用传统的查询、统计分析手段，而 是应发现更深层次的规律，对决策或科研工作提供更有效的决策支持。正是为 了满足这种要求，将机器学习应用于大型数据库的数据挖掘( d a t am i n i n g ) 技 术得到了长足的发展。网络数据挖掘就是数据挖掘技术在网络信息处理中的应 用。在网络故障诊断中应用数据挖掘是网络数据挖掘的一个方向，它针对网络 故障信息数据的特点，采用特定的数据挖掘技术对网络故障进行智能化的诊断。 本文的主要研究内容如下。 1 讨论了数据挖掘中分类的基本技术，包括数据分类的过程，分类数据 所需的数据预处理技术，以及分类方法的比较和评估标准；探讨了如何将数据 挖掘技术应用到网络故障管理中去，对常见网络故障进行了深入的分析和分类， 并基于这种分析展开对网络故障诊断的智能化方法的研究。 2 研究了网络故障诊断系统的体系结构和诊断方法。详细阐述了在网络 环境下，如何构建故障信息诊断系统，以对专用网络运行过程中产生的故障进 行自动诊断。 3 重点研究并实现了一种网络故障诊断模型。根据对网络故障诊断系统 的需求和总体设计，采用代理一服务器的方式收集故障信息，并通过引入数据挖 掘中的决策树分类技术，对网络故障进行模式分类，达到简化故障诊断的过程。 整个模型在实验环境下加以实现，提高了网络故障诊断效率。为提高网络故障 诊断率，减轻故障诊断成本、减少网络传输提供了一种新的解决方法。 关键词网络管理；故障诊断；数据挖掘；决策树 a b s t r a c t a b s t r a c t w i t ht h ea p p l i c a t i o no fd a t a b a s ea n dd e v e l o p m e n to f t h ei n t e r a c t ，a c c u m u l a t e d d a t aa r ee x p o n e n t i a l l yi n c r e a s i n g f o rt h e s ed a t ap e o p l ea r cn o ts a t i s f i e dw i t ht h e t r a d i t i o n a lm e t h o d so f q u e r i e sa n ds t a t i s t i c s ，b u tl o n g i n g t of i n dd e e p e r r e g u l a t i o n st o p r o v i d ee f f e c t i v ed e c i s i o nt os c i e n c ea n dr e s e a r c hw o r k s s od a t am i n i n gt e c h n o l o g y i s d e v e l o p e d ，w h i c ha p p l ym a c h i n el e a r n i n g t o l a r g ed a t a b a s et oa c q u i r eu s e f u l i n f o r m a t i o nf r o mal o to fd a t a n e t w o r kd a t am i n i n gi st h ea p p l i c a t i o no fd a t am i n i n g i ni n f o r m a t i o n p r o c e s s o fn e t w o r ks y s t e m t h e a p p l i c a t i o n o fd a t a m i n i n g o n n e t w o r kf a u l td e t e c t i n gi so n eb r a n c ho ft h en e t w o r kd a t am i n i n g i ti s u s i n gt h e c e r t a i nd a t am i n i n gm e t h o dt od i a g n o s et h en e t w o r kf a u l t sa c c o r d i n gt ot h en e t w o r k f a u l ti n f o i t n a t i o n t h em a i nw o r k so f t h ed i s s e r t a t i o na r ea sf o l l o w s 1 t h eb a s i ct e c h n o l o g i e so fc l a s s i f i c a t i o ni nd a t am i n i n ga r ed i s c u s s e d t h e s e t e c h n o l o g i e s i n c l u d et h e p r o c e d u r e o f c l a s s i f i c a t i o n ，t h ep r e p r o c e s s i n g o f c l a s s i f i c a t i o nd a t a ，a n dt h ee v a l u a t i o no fc l a s s i f i c a t i o nm e t h o d sa sw e l l t h e c l a s s i f i c a t i o no ft h en e t w o r kf a u l t sa n dt h ea p p l i c a t i o no fd a t am i n i n gi n f a u l t d e t e c t i n go f n e t w o r k a r ea l s od i s c u s s e d 2 t h e s y s t e mo f n e t w o r kd e t e c t i o ni ss t u d i e d a n dt h ew a yt oc o n s t r u c tt h em o d e l o f f a u l td e t e c t i n go f n e t w o r ks y s t e mi sa l s od i s c u s s e d t h e s et e c h n o l o g i e si n c l u d e h o wt og e ta n ds e n dt h er e l a t e di n f o r m a t i o n ，h o wt op r e p r o c e s sa n dc l a s s i f yt h e d e t e c t i n gi n f o r m a t i o n ，a n dh o w t oc o n s t r u c tt h ek n o w l e d g ed a t a b a s ea n do u t p u t t h er e s u l t s 3 t h em o d e lo ff a u l td e t e c t i n gs y s t e ma n dt h ea p p l i c a t i o no fd a t am i n i n gi nf a u l t d e t e c t i n g o fn e t w o r ka r es t u d i e dt o o ，t h em o d e li sa n e m p h a s i s o ft h i s d i s s e r t a t i o n t h ec r e a t i o no ft h i sm o d e la n di t s g e o m e t r i c a lp r e s e n t a t i o n a r e e x p a t i a t e d ，s oan e wm e t h o d i si n t r o d u c e dt oi m p r o v et h er a t eo fn e t w o r kf a u l t d e t e c t i n g k e y w o r d s n e t w o r k m a n a g e m e n t ： f a u l td e t e c t i n g ；d a t a m i n i n g ；d e c i s i o n t r e e i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 虢壅筮铆签幺竺日期 。 k l 上一 第l 章绪论 1 1 课题的来源背景 第1 章绪论 随蓿网络技术与应用的不断发展，计算机网络在我们的日常生活中已经变 得越来越普遍。特别是2 0 世纪9 0 年代以来，随着i n t e r n e t 在世界范围的普及， 计算机网络逐渐成为人们获取信息、发布信息的重要途径，与此同时，基于计 算机网络的应用也越来越多，许多人们生活中的重要环节都可以利用网络方便、 快捷地实现。金融网络、邮电网络等等各种专业大型网络的发展使得大到国家 经济命脉小到个人日常生活严重依赖于计算机网络，因此网络运行的稳定性、 可靠性就显得至关重要，于是网络管理就应运而生。 网络管理是计算机网络发展的必然产物，它随着计算机网络的发展而发展。 i n t e r n e t 的出现打破了网络的地域限制，跨地域的广域网络得到飞速发展，网 络管理不再局限于保证文件的传输，而是保障连接网络的网络对象( 路由器、交 换机、线路等) 的正常运转，同时监测网络的运行性能，优化网络的拓扑结构。 网络管理系统也因此越来越独立，越来越复杂，功能也越来越完备，网络管理 也发展成为计算机网络中的个重要分支，国际上各种网络管理的标准也相继 制定，网络管理逐步变得规范化、制度化。根据国际标准组织( i s o ) 的开放系 统互联( o s i ) 模型的定义，网络管理的主要功能划分为五个功能域：配置管理、 性能管理、故障管理、安全管理和计费管理。 而作为五大功能之一的故障管理主要是对影响网络及其组件正常工作的网 络失效、软件故障以及其他故障和问题的定位和处理。在网络运行中可能出现 的异常多种多样，这些异常有的不引起故障、可以置之不理，而有的会引起故障 发生，如果不及时采取措施则会带来不可挽回的损失。异常产生的随机性很大， 究竟哪些可以不予理睬，哪些必须迅速处理，往往需要由人工根据经验进行判断 处理，效率不高。同时解决一个复杂的网络故障需要广泛的网络知识与丰富的工 作经验。这也是为什么把专家系统和人工智能技术引进到网络故障管理中来的 原因。网络的故障诊断是网络管理研究中最适宜实现智能的地方，是国际上研 究的热点之一啪1 。 应用数据挖掘方法，网络故障诊断系统可以通过分析已有的异常信息的正 北京工业大学硕士学位论文 确处理方法以及各种异常之间的前后关系的记录，得到其间的关联规则，这些有 价值的信息可用于网络故障的定位检测和严重故障的预测等任务。并能根据当 前的诊断信息，就可以得到其后续发生各种情况的可能性，对危险事件可以起到 预防的作用，从而使通信网络得以安全运转。 随着数据库和数据仓库技术的迅速发展，大量的数据得以存储并可以连续 访问。据估计，全世界的数据总量每1 6 个月就要翻一番，以目前社会的信息化 自动化发展趋势未看，这个速度还会更快。但是，要对如此海量的数据进行存 储、分析，并从中挖掘出知识，无论是数据库技术，计算机的并行处理技术和 数据挖掘技术都是热门之一。面向主题的、集成的、非易失的数据仓库的出现， 使得数据挖掘技术得以成功应用。大容量内存加之并行处理技术，将使数据的 处理更为灵活、快速和实时。以自动化、智能化为特征，具有自学习能力的决 策树技术，特别是分类预测树模型，成为了新一代故障诊断、分类和预测的工 具。 数据挖掘的任务是从大量的数据中发现模式或知识。模式按其作用可分为 两类：一类称为描述型模式，它是对数据中存在的规律做出描述。如泛化模式、 聚类模式、关联模式及时问序列模式。另一类是预测型模式，它依据从已有数 据挖掘获得的知识对未知数据的某些性质进行预测。包括分类模式和回归模式。 其中，分类模式是一种重要的预测型模式。 抽象地说，挖掘分类模式的步骤如下：首先，要对待挖数据库进行预处理： 包括整理数据库中的记录，去除一些不全的记录和无关的属性，主要是确定一 个类别属性并确保每一个记录的类别属性都已给出。然后，从待挖数据集中抽 取出一定数量的记录形成训练样本集。对训练样本集运用一种或多种分类挖掘 方法进行挖掘，最终输出某种形式的分类模式。分类模式的形式有决策树，数 学公式，分类规则等。用于挖掘分类模式的方法有很多，如决策树方法，贝叶 斯网络，遗传算法，基于关联的分类方法，粗糙集，k 最临近方法等等。其中 决策树方法以其易被人理解、需要信息量少、效率及准确率较高等优点占据着 重要地位。决策树方法自产生至今，先后涌现出多种算法，包括i d 3 ，c 4 5 ， c a r t ，s l i q ，s p i u n t ，p u b l i c ，基于人机交互的方法等。他们的共同特点是对 训练样本集进行挖掘后都会生成一棵形如二叉树或多叉树的决策树。树的叶子 2 第1 章绪论 节点代表某一类别，非叶节点，包括根节点及内节点代表某个一般属性( 非类 别属性) 的一个测试，测试的一个结果形成非叶节点的一个分枝。从根节点到 叶子节点的一条路径形成一条分类规则。一棵决策树能够很方便的转化为若干 条分类规则。人们可以依据分类规则直观地对未知类别的样本进行预测。综上 所述，分类模式挖掘技术作为数据挖掘的重要分支将对电信、银行、保险、零 售、医疗等诸多行业提供决策支持，对未来商业和人们的生活也将产生深远的 影响。挖掘分类模式的算法有很多，其中，决策树算法因其卓越的优点在分类 挖掘算法中占有重要地位。 网络数据挖掘就是数据挖掘技术在网络信息处理中的应用，是从网络中的 数据发掘关系和规则。网络上的每一个站点就是一个数据源，每一个站点之间 的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。网络数据挖 掘要针对网络数据的特点，来采用特定的数据挖掘技术。本文作者选择分类挖 掘方法作为网络故障诊断的智能化工具，建立网络故障诊断模型，并着重研究 了基于决策树的网络故障分类挖掘方法。 1 2 论文的内容安排 本论文在对网络故障诊断中需要应用的数据进行分析的基础上，采用了适 合于在网络环境下的数据挖掘算法，提出了应用数据挖掘技术的网络故障诊断 系统模型，并进行了需求分析和总体设计，主要包括以下内容： 对网络故障诊断所需的故障信息数据进行了特点分析，提取出与故障分类 有关的数据，分析了网络故障信息的特点，并针对这些特点采用了数据挖掘中 的相应决策树算法，并对实际网络运行中出现的各种故障进行了分类。 对如何构造网络故障诊断系统进行了功能分析和总体设计，而一个网络故 障诊断数据挖掘系统主要分为三个部分：数据采集、数据分析和数据挖掘、用 户界面。 在实验环境下实现的网络故障诊断系统，在网络节点机上通过代理一管理 者的网管技术来实现故障数据收集，验证了建立智能化网络故障诊断的关键技 术( 数据采集，数据存储、数据挖掘、数据呈现) ，实现了在专用网络环境下对 网络故障的有效诊断，为建立智能化的网络故障诊断系统奠定了理论基础，积 北京工业大学硕士学位论文 累了实际经验。 本论文共分五章。 第一章：对论文的主要内容进行了简明概要的阐述，包括：网络管理技术 和数据挖掘技术的发展，建立网络故障诊断系统的背景及应用数据挖掘技术的 网络故障诊断系统研究思想。 第二章：主要介绍数据挖掘理论和网络故障诊断理论，包括：数据挖掘产 生的背景和定义，数据挖掘技术的分类，决策树算法原理，决策树技术在故障 诊断中的应用和网络管理和故障诊断的基本理论。 第三章：对网络故障诊断需求进行深入分析，对网络故障进行了分类，分 析了网络故障数据的特征和在网络故障诊断中应用数据挖掘技术的必要性，以 及如何确定待收集的诊断数据。 第四章：在第三章对网络故障诊断的分析的基础上，对网络故障诊断系统 进行了总体设计，包括：设计目标、设计思想、设计方案、网络故障诊断系统 的框架结构和各模块的主要功能。 第五章：针对某专用网络的运行，建立采用数据挖掘技术的故障诊断模型， 并在实验环境下实现。详细介绍了诊断系统模型的各模块组成和功能，并对各 个模块的主要函数和工作原理加以解释。应用代理一管理者的网络管理技术来 采集有用的诊断数据，对这些诊断数据经过预处理后，再应用决策树来分类。 应用改进后的c 4 5 算法，即c 5 算法来构造决策树，并对产生的结果进行解释。 4 第2 章数据挖掘及网络故障诊断 第2 章数据挖掘及网络故障诊断理论 2 1 数据挖掘理论与数据挖掘技术中的分类 2 1 1数据挖掘基本理论与背景 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。例如：商品条形码的广泛使用，企业的信息化程度的提高，科 学研究和政府部门中电子化事务处理技术的运用，以及数据收集工具和技术的 多元化( 从文本扫描到卫星遥感) 等等。除此之外，互联网的发展更是为我们 带来了海量的数据和信息。但存储在各种数据媒介中的海量的数据，在缺乏强 有力的工具的情况下，己经远远的超出了人的理解和概括的能力。为此，这种 大量的原始数据和对功能强大的数据分析工具的需求共存的局面，被有的人描 述为“数据丰富，但信息贫乏”( d a t ar i c hb u ti n f o r m a t i o np o o r ) 。许多 的数据库也就成了“数据坟墓”( d a t at o m b ) 换句话说，这些数据很少被 再访问。激增的数据背后隐藏着许多重要的信息，拥有这些数据库的决策者们， 在做决策时不是基于数据库中蕴含的大量信息，而是基于决策者的直觉。因为 决策者缺乏从海量数据中提取有价值知识的工具。传统的数据库管理系统可以 高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和 规则，无法根据现有的数据预测未来的发展趋势，缺乏发现数据背后隐藏的知 识的手段“3 。数据与信息之间的鸿沟要求有更强用力的数据分析工具，将数据 坟墓转换成知识“金块”。在数据库技术飞速发展的同时，人工智能领域的一 个分支机器学习的研究自5 0 年代开始以来也取得了很大进展。用数据库管 理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识， 这两者的结合促成了数据库中的知识发现( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ，简记k d d ) 的产生。 所谓数据挖掘( d a t am i n i n g ，简记d m ) ，就是从大量的、不完全的、有 噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知 道的。但又是潜在有用的信息和知识的过程。这个定义包括好几层含义：数据 源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知 s 北京工业大学硕士学位论文 识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特 定的发现问题。 数据挖掘可以视为k d d 的一个步骤，如下图所示。 i 数据规范化：包括去掉异常数据和不相关数据 上 l 数据集成：将不同数据源中的数据集成到单个系 l统中 土 l 数据转化：如将数据转变成统一的表现形式以方 l便挖掘算法的实现 上 l 数据挖掘d m ：一些智能的被用来发现目标数据 l库中的一些模式 上 模式评价：识别上一步得到的模式中真正有价值 的模式 上 知识的表示：将上一步得到的模式或知识以用户 可接受的方式表现出来 图2 - 1k d d 流程图 f i g u r e2 - 1k d df l o wc h a r t 数据挖掘是一个交叉学科领域，受多个学科的影响，包括数据库系统、统 计学、机器学习、可视化和信息科学等。它从大量的，不完全的，有噪声的， 模糊的或随机的数据中提取出人们事先不知道的但是又有用的信息和知识。它 第2 章数据挖掘及网络故障诊断 的主要任务是能高度自动分析数据，归纳推理，从中挖掘出潜在的模式，预测 未来的行为，帮助决策者做出正确的决策0 1 。 数据挖掘是信息技术自然演化结果。信息技术的发展大致可以描述为如下 的过程：初期的是简单的数据收集和数据库的构造；后未发展到对数据的管理， 这包括：数据存储、检索以及数据库事务处理；再后来发展到对数据的分析和 理解，这时候出现了数据仓库技术和数据挖掘技术。3 。早期的数据收集和数据 库的建造为数据存储、检索、和事务处理的技术的发展创造了必要条件，随着 查询、事务处理等成熟技术被频繁的应用在大量的数据库系统上，数据的分析 和理解也就当然的成为了信息技术要发展的下一个目标。数据挖掘是涉及数据 库和人工智能等学科的一门当前相当活跃的研究领域，同时又由于有广泛可用 的存在于各种数据库中的海量数据“3 。因此，从大量的数据中智能地、自动地 提取出有价值的知识和信息的研究，即数据挖掘，具有十分重要的理论及现实 意义和广泛的应用前景。目前，数据挖掘已成为一个具有迫切实现需要的很有 前途的热点研究课题，国内外许多研究工作者对此领域投入了极大的热情。 2 1 2数据分类基本理论 数据挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提 取具有潜在应用价值的知识或模式。模式按其作用可分为两类：描述型模式和 预测型模式。分类模式是一种重要的预测型模式。挖掘分类模式的方法有多种， 如决策树方法、贝叶斯网络、遗传算法、基于关联的分类方法、粗糙集和k 一最 临近方法等等。1 。 数据分类是数据挖掘中的一个重要课题。在统计学、机器学习、神经网络、 专家系统中得到了较早的研究。数据分类实际上就是从数据库对象中发现共性， 并将数据对象分成不同几类的一个过程。 在数据分类中，一个样本数据库被当作训练集，训练集中的每个元组都保 持总数据库的所有属性，并且都有一个类的标识符与之联系。分类的目标首先 是对训练数据进行分析。使用数据的某些特征属性，给出每个类的准确描述， 然后使用这些描述，对总数据库中的其它数据进行分类或为每个类产生更好的 描述，即分类规则嘲。分类的目的是学会一个分类函数或分类模型( 也常常称 北京工业太学硕士学位论文 作分类器) ，该模型能把数据库中的数据项映射到给定类别中的某一个。分类 可用于提取描述重要数据类的模型或预测数据趋势”3 。可描述如下： 输入数据，或称训练集，是一条条的数据库纪录组成的。每一条纪录包含 若干条属性，组成一个特征向量。训练集的每条记录还有一个特定的类标签与 之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本 的形式可表示为样本向量：( v ，v 。，v 。；c ) ，在这里v 。表示属性字段值， c 表示类别“1 。 分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为 每一个类找到一种准确的描述或模型。这种描述常常用谓词表示。由此生成的 类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是 未知的，仍可以由此预测这些新数据所属的类。1 ，也可以由此对数据中的每一 个类有更好的理解“。 有三种分类器评价或比较尺度1 ： 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测分 类任务。 计算复杂度：计算复杂度信赖于具体的实现细节和硬件环境，在数据挖掘 中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重 要的一个环节m 3 。 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎； 例如，采用规则表示的分类器构造法就更有用“”。 大部分分类算法是内存驻留算法，最近出现了一些可伸缩的分类技术，能 够处理大量的、驻留在磁盘的数据。分类技术有很多，如决策树、贝叶斯网络、 神经网络、遗传算法、k _ 最临近分类等等“”。本文重点讨论了决策树中相关算 法。 2 2 决策树算法及其应用 2 2 1决策树算法简介 决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的 第2 苹数据挖掘及网络故障诊断 归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出决策树表示形 式的分类规则。它采用自顶向下的递归分式，在决策树的内部节点进行属性值 的比较并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。 所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规 则。 决策树又分为分类树和回归树两种，分类树对离散变量做决策树，回归树 对连续变量做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则， 以及控制参数( 最小节点的大小，最大树的深度等等) ，来限制决策树的 o v e r f i t t i n g ( 过度吻合) 。决策树构造过程可图示如下： 图2 2 决策树的构造 f i g u r e2 - 2t h ec o n s t r u c t i o no fd e c i s i o nt r e e 决策树生成算法分成两个步骤：树的生成和树的修剪。树的修剪主要是去 掉一些可能是噪音或者异常的数据“”。 决策树有很多实现算法。这其中有著名的i d 3 学习算法，它通过选择容器 来形成决策树，是利用信息论中的互信息( 信息增益) 寻找数据库中具有最大 信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建 立树的分支；在每个分支子集中重复建立树的下层节点和分支过程。这种方法 的优点是描述简单，分类速度快，特别适合大规模的数据处理“。 较典型的决策树学习系统有i d - 3 及c 4 5 ，i d 3 算法是在所有可能的决策树 空间中一种自顶向下、贪婪的搜索方法。i d 3 算法的关键是确定属性表中可对 训练例集进行的最佳分类的属性，即在树的每一个节点上确定一个候选属性， 它的测试对训练例的分类最有利。i d 3 搜索的假设空间是可能的决策树的集合， 而i d 3 搜索目的是构造与训练数据一致一棵决策树。它的搜索策略是爬山法， 9 北京工业大学硕士学位论文 在构造决策树时从简单到复杂，用信息赢取作为指导爬山法的评价函数。”。i d 3 算法在实际应用中解决了许多问题，对于非增量式学习任务，i d 3 算法常常是 建立决策树的很好的选择。但对于增量式学习任务来说，由于i d 3 不能增量地 接受训练例，这就使得每增加一次实例都必须抛弃原来决策树，重新构造新的 决策树，造成了极大的开销。而c 4 5 算法是机器学习中广为人知的算法，是 i d 3 算法的改进，并继承了i d 3 的全部优点“。在归纳学习中，它代表着基于 决策树的方法，通过对一组训练数据的，构造出决策树形式的知识表示，在决 策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分 支，在决策树叶结点得到结论，所以从根到叶结点的一条路径就对应着一条规 则，整棵决策树就对应着一组析取表达式规则，基于决策树学习算法的一个最 大的优点是它在学习过程中不需要使用者了解很多的背景知识。这样只要训练 事例能够用属性一结论式的方式表达出来，就能使用该算法来进行学习“。虽 然c 4 5 算法存在一些不足，但由于它思想简单，实现高效，结果可靠，使其在 归纳学习中的地位依旧十分显著。 2 2 2i d 3 算法基本原理 决策树算法i d 3 基本原理和步骤可以简介如下： 设e = f 。f z f 。是n 维有穷向量空间，其中f ，是有穷离散符号集，e 中 的元素e = 称为例予。其中v 。e f ，j = l ，2 ，n 。设p e 和n e 是e 的两个例子集，分别叫正例集和反例集。 假设向量空间e 中的正例集p e 和反例集n e 的大小分别为p 和n ，i d 3 基于 如下两种假设： 1 ) 在向量空间e 上的一棵正确决策树，对任意例子的分类概率同e 中正、 反例的概率一致。 2 ) 一棵决策树对一个例子做出正确类别判断所需的信息量为： 砌川一去l o g ：焘一熹1 0 9 z 熹( 2 - 1 ) n pppp + + n+ n+ 胛 如果属性a 作为决策树的根，a 具有v 个值 v 。，v 。，v ，) ，它将e 分成 v 个子集 e 。，e ：，e v ) ，假设e i 中含有p 。个正例和n ；个反例，那么子集 l o 第2 章数据挖掘及网络故障诊断 e 。所需的期望信息是i ( p ，n 。) ，以属性a 为根分类所需的期望熵( e n t r o p y ，平均 信息量，用于表示节点信息的重要程度) 是： 刚) 2 喜号等心r ) ( 2 - z ) 以a 为根的信息增益是：g a i n ( a ) = i ( p ，n ) - - e ( a ) 。i d 3 选择使g a i n ( a ) 最大 ( 即e ( a ) 最小) 属性r 的子结点，对a + 的不同取值对应的e 的v 个子集b 递归调 用上过程生成r 的结点b l ，b 2 i 一，b 。，最后生成整个决策树。 创建决策树的过程如下图所示： ( 1 ) 创建根节点n ； ( 2 )i f 样本集t 都属于同一类c ，则返回n 为叶节点，标记为类c ； ( 3 )i f 属性集t _ a t t r i b u t e l i s t 为空 则返回n 为叶节点，标记n 为t 中出现最多的类； ( 4 )f o re a c ht 中的属性_attributelist 计算信息增益g a i m ( 5 ) n 的测试属性t e s t _ a t t r i b u t e = t _ a t t r i b u t e l i s t 中具有最高g a i n 的属性 ( 6 )f o re a c ht e s ta t t r i b u t e 的取值( 由节点n 长出一个新的叶子节点； i f 新叶节点对应的样本子集t 为空 则不再分裂此叶子节点，将其标记为t 中出现最多的类： e l s e 在该叶节点上执行f o r m t r e e ( t ，t _ a t t r i b u t e l i s t ) ，继续对它分裂； ) 图2 - 3i d 3 的f o r m t r e e 算法 f i g u r e2 - 3f o r m t r e eo fi d 3 2 3 网络故障诊断的基本理论 故障诊断是人工智能的一个重要研究内容。人工智能在故障诊断领域中的 应用，实现了基于人类专家经验知识的设备故障诊断技术，并将其提高到智能 化诊断水平“。智能诊断是故障诊断领域的前沿学科之一，目前正处于研究热 点之中。与人工智能技术发展紧密相连的智能诊断理论和方法主要有：基于规 则的方法、基于模型知识的方法、基于人工神经网络的方法、基于案例的方法、 北京i 业大学硕士学位论文 基于行为的方法等。这些方法虽各具特点和优势，但均存在各自的局限性“1 。 网络管理是计算机网络发展的必然产物，它随着计算机网络的发展而发展。 i n t e r n e t 的出现打破了网络的地域限制，跨地域的广域网络得到飞速发展，网 络管理不再局限于保证文件的传输，而是保障连接网络的网络对象( 路由器、交 换机、线路等) 的正常运转，同时监测网络的运行性能，优化网络的拓扑结构。 网络管理系统也因此越来越独立，越来越复杂，功能也越来越完备，网络管理 也发展成为计算机网络中的一个重要分支，国际上各种网络管理的标准也相继 制定，网络管理逐步变得规范化、制度化1 。 根据o s i 定义，网络管理主要功能划分为五个功能域：配置管理、性能管 理、故障管理、安全管理和计费管理。故障管理主要是对影响网络及其组件正 常工作的网络失效、软件故障以及其他故障和问题的定位和处理。 网络管理协议提供了网络管理系统和网络设备相互通信的途径，它可以网 络管理系统访问网络上的任何设备，并获得一系列标准值。反过来，网络设备 通过网管系统发送非请求信息给管理系统，加强了网管系统对网络信息的获取 和对网络状态的监控。当前，在各种网络并存、交叉互联、共同管理的情况下， 随着w e b 技术的发展，在网管协议方面加强集成、网络管理体系结构趋于分布 化已是大势所趋，加强对s n m p 研究，有利于网络管理功能的进一步扩展，有利 于新的网络体系结构的发展。s n m p 是当前的主流网络管理协议之一，是 i n t e r n e t 组织为适应i n t e r n e t 的发展而制定的基于t c p i p 的网络管理协议， 基于s n m p 的网络管理解决方案已经成为事实上的工业标准“。 s n m p 包括三个部分：即s n m p 主体，管理信息库m i b 和管理信息结构定义 s m i ，s n m p 网络管理软件遵循传统的客户n 务器模式，管理者一般是一个单机 设备或者是一个共享网络中的一员，无论是哪一种情况下管理者都是作为网络 管理员与网络管理系统的接口。管理代理则是在网络设备上的服务器应用程序， 管理代理对来自管理站的信息查询和动作执行的请求做出响应，同时还能异步 地向管理站提供一些重要的非请求信息。s n m p 协议精确定义了管理员如何与代 理之间进行通信，比如，s n m p 定义了管理员传送给代理的请求格式以及代理响 应的格式等，还定义了每种可能的请求和响应的确切含义。m i b 定义了与t c p i p 协议相关的参数、系统地址、接口表与系统标识信息。“。s n m p 没有指定m i b 变 第2 章数据挖掘及网络故障诊断 量集，它的设计比较灵活，只要需要，就可以定义新的m i b 变量，通信协议和 对象定义之间的独立性允许用户可以自定义m i b 变量。设计者可以定义相应协 议或设备的m i b 变量，以便对它们实行监控，目前已经定义了许多新的m i b 变 量，诸如对应于协议的u d p 、t c p 、i p 、a r p 和对应于网络硬件的以太网、令牌 环网、f d d i 等，诸如路由器、桥接器、交换机、打印机等硬件设备都有相应的 m i b 变量o 。 网络管理系统一般采用两种机制实现网络数据的收集一轮询机制和t r a p 机制。轮询机制通过网络管理进程主动地去逐个轮流查询整个网络设备或设施 的工作状态和参数，并等待响应。由于网络规模的扩大，轮询一次花费的时间 比较长，并且增加了网络带宽，这样故障时延比较长，影响了故障信息的实时 收集。t r a p 机制是另外一种数据采集的方法，驻留在节点计算机上的代理进程 一旦发现设备的状态或参数发生变化以后及时地向网络管理监听进程报告，时 延比较短，同时减少了网络带宽”。 网络数据挖掘就是数据挖掘技术在网络信息处理中的应用，是从网络中的 数据发掘关系和规则。网络上的每一个站点就是一个数据源，每一个站点之间 的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。网络数据挖 掘要针对网络数据的特点，来采用特定的数据挖掘技术。”。网络数据挖掘的类 型可以分为以下三种： 1 )网络内容挖掘 即从网络的内容、数据、文档中发现有用信息的过程，这是搜索引擎在网 络搜索时的访问对象，包括g o p h e r 、f t p 等已经隐藏到w w w 形式之后的资源， w w w 信息资源，无法索引的私人数据。从网络资源的形式来看，包括文本、图 像、音频、视频等形式的数据。 2 )网络结构挖掘 即挖掘w e b 潜在的链接结构模式。这种思想源于引文分析，即通过分析一 个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。这种模式 可以用于网页归类，并且可以由此获得有关不同网页相似度及关联度的信息。 网络结构挖掘有助于用户找到相关主题的权威站点，并且可以找到指向相关主 题的站点。 北京工业大学硕士学位论文 3 ) 网络用法挖掘 主要用来了解用户的网络行为数据所具有的意义。网络用法挖掘面对的是 在用户和网络交互的过程中抽取出来的第二手数据，包括网络服务器访问记录、 代理服务器记录、浏览器同志记录、用户简介、注册信息、用户对话或交易信 息、用户提问等。网络故障诊断数据挖掘就是属于这一种类型。 将数据挖掘应用于网络故障诊断中，可以在网络故障诊断过程中消除干扰 因素，使得网络故障诊断过程更为系统化、客观化。应用数据挖掘方法，网络 故障诊断系统可以通过分析已有的异常信息的正确处理方法以及各种异常之间 的前后关系的记录，得到其间的关联规则，这些有价值的信息可用于网络故障的 定位检测和严重故障的预测等任务。并能根据当前的诊断信息，就可以得到其后 续发生各种情况的可能性，对危险事件可以起到预防的作用，从而使通信网络得 以安全运转”1 。 网络故障管理的主要任务是负责检测和解决网络运行中存在的各种故障， 目前网络管理软件所采用的技术主要是基于阈值的判断，即当某一性能指标超 过某一阈值时，就认为是一个故障、这种故障检测机制过于简单，无法满足需 要，误判率和漏判率很高，因此本文提出了一套基于决策树的故障管理策略。 即结合分布式代理技术，应用数据挖掘技术，实现了一个具有较强故障识别能 力的网络故障管理系统模型。 2 4 本章小结 本章主要介绍数据挖掘和网络故障诊断相关理论。 数据挖掘部分详细阐述了数据挖掘产生的背景和意义，研究了数据挖掘的 分类技术和各种分类算法，其中重点是决策树算法，详细介绍了决策树算法中 的典型算法：i d 3 算法及其改进算法c 4 5 。 网络故障管理部分主要介绍了网络管理技术以及故障诊断的含义和作用， 重点论述了数据挖掘技术在网络故障诊断中的应用。 1 4 第3 章需求分析 3 1 项目需求 第3 章需求分析 网络故障诊断系统的目标主要是解决在网络环境下，如何构建网络故障诊 断系统的模型，以对专用网络运行过程中产生的故障进行自动诊断，为产生的大 量数据进行即时诊断，并为管理员提供方便。根据实际环境，所待研究的网络 故障诊断系统是一个实时对发生的网络软件故障进行诊断的系统，它应具有以 下几个特点： 1 ) 诊断系统所要诊断的网络是专用的，具有完成特定功能的软件环境。 2 ) 对象特性数据的采集分布于网络各节点。 3 ) 可以定时更新，也可主动查询。 4 ) 对网络上的软件系统运行情况进行诊断。 5 ) 诊断过程是自动的，智能的，不用多作干预。 3 2 诊断数据和挖掘算法的选择 要对经过净化的数据分类，就要选择一种分类算法，应用于样本库中的训 练例，生成模式或规则。正确选择挖掘算法是数据挖掘技术在网络诊断应用中 成败的关键。诊断数据挖掘可以采用多种方法。主要有：时间序列分析、模糊 逻辑方法、神经网络、多源数据溶合、可能性推理、混杂方法、基于案例的推 理( c b r ) 和决策树方法1 。数据挖掘算法主要是根据网络故障诊断信息自身的 特点进行的。 3 2 1诊断数据分析及其特点 网络故障以某种症状表现出来，故障症状包括一般性的( 如用户不能接入 某个服务器) 和较特殊的( 如某个网卡收不到包) 。建立故障诊断系统的目的 是对实验网络的每一个症状都能查找出一个或多个故障原因。“。当网络的规模 较大时，故障检测需要处理的数据量也较大。为了使系统能够承担更大的处理 负载，可将系统的收集分布在网络中的各个部分，由各代理收集所需信息，中 北京工业大学硕士学位论文 央控制节点负责综合各个探测节点的信息。数据挖掘算法主要是根据网络故障 诊断信息自身的特点进行的。 一般而言，常用网络的故障诊断数据主要有以下特点： 1 ) 数据量大。 2 ) 数据定时更新。 3 ) 可以以数值的形式存储到中央服务器上的数据库。 4 ) 各类信息之间有一定的关系。 根据以上分析及对实验环境网络的具体分析，在本故障诊断系统中，主要 考虑采用的数据有： 1 i 系统信息 系统信息主要采用信息分为：网卡信息、处理器信息、内存信息、进程信 息、磁盘信息。分别介绍如下： ( 1 ) 网卡信息( 主机i p 、网卡编号、网卡d o w no ru p 、网卡r u n n i n go r ( 2 ) ( 3 ) ( 4 ) ( 5 ) n o t 、网卡p r o m i s co rn o t 、网卡每秒捕到的字节数、网卡每秒收包 e r r o r s 包数、网卡每秒收包d r o p s 包数等) 处理器信息( 处理器编号、处理器利用率等) 内存信息( 内存占用率、空闲内存总数等) 进程信息( 进程总数、僵尸进程数目、占c p u 过多进程数、占内存 过多进程数等) 磁盘信息( 磁盘总空间、空闲节点总数、节点占用率、空闲磁盘总 数、磁盘占用率等) 2 服务信息 服务信息是与被管设备提供的网络服务或其它服务相关的信息，比如邮件 服务器提供的电子邮件服务，担任防火墙作用的服务器，服务信息因不同的服 务而异。例如与网络服务器的进程协议( f t p 、t e l n e t 、s m t p 、t i m e 、h t t p 、 p o p 3 、w e b m a i l 、u d p 等) 有关的信息。 要对经过净化的数据分类，就要选择一种分类算法，应用于样本库中的训 练例，生成模式或规则。正确选择挖掘算法是数据挖掘技术在网络诊断应用中 成败的关键。诊断数据挖掘可以采用多种方法。主要有：时间序列分析、模糊 1 6 第3 章需求分析 逻辑方法、神经网络、多源数据溶合、可能性推理、混杂方法、基于案例的推 理( c b r ) 和决策树方法。数据挖掘算法主要是根据网络故障诊断信息自身的特 点进行的。在以上几种方法中，最终采用决策树算法，主要是因为： 1 ) 可以生成可理解的规则，可以方便管理人员对故障的管理和处理。 2 ) 计算量相对来说不大。由于故障信息收集的范围广，频率高，产生的数 据量也相当大，因此适合采用决策树方法。 3 ) 可以处理连续和类型字段。故障信息中的一些数据，如时间数