一种基于粗糙集的网络故障决策表简约方法
来源:用户上传
作者:
摘要：随着计算机网络规模的扩大，网络故障诊断日趋复杂。故障诊断的决策表简约成为智能诊断领域的一个技术难点。本文提出了一种基于粗糙集的网络节点状态信息和故障报告的简约方法，定义了网络信息的条件属性和决策属性，给出了刻画基本决策属性和条件属性的核生成算法和简约算法的基本框架。文章最后给出了一个网络化电力控制系统应用的故障决策表简约结果。该结果表明，方法实用有效。
关键词：粗糙集智能诊断简约
1. 概述
随着计算机网络技术的发展，连网系统正成社会生活中必不可少的基本设施。由于网络规模的扩大，网络管理的复杂度也不断增加，简单的网络管理和网络故障诊断方法已不能胜任复杂网络的管理和诊断任务。从全球网络故障诊断和管理技术的发展目标来看，主要的技术趋势可以概括为：(1)标准化，根据国际标准化组织的相关标准进行网络管理和故障诊断；(2)集中化，集中配置、集中调度、集中监视、集中控制；(3)智能化，大量使用专家系统、多智能体结构等智能管理模型；(4)可扩展化，管理内容和方式可定制、可持续、可发展。其中，智能化是最具技术因素的趋势，使得网络管理和故障诊断的智能化技术成为一个重要的研究领域[1-3]。
智能化的管理和故障诊断体系采用基于知识的智能诊断方法[4-5]。不同于采用故障树或参数估计的解析模型方法，也不同于基于信号处理的方法，智能化处理方法依赖基于事件的推理、人工神经网络、支持向量机等技术，管理和诊断的正确性较高，扩展性较好。尤其是人工神经网络、支持向量机等统计学习技术，不但能克服知识获取瓶颈，更具有较高的鲁棒性。但是，即使使用了统计学习技术，庞杂的网络节点状态信息和故障报告仍然会带来训练数据维数的扩张，直接导致对计算资源的过高需求。因此，在复杂网络智能诊断和管理领域，如何处理庞杂的网络节点状态信息和故障报告，仍然是最具挑战性的问题。
本文提出了一种基于粗糙集的网络节点状态信息和故障报告的简约方法，定义了网络信息的条件属性和决策属性，给出了刻画基本决策属性和条件属性的核生成算法和简约算法的基本框架。在实验部分，根据一个电力控制网络的实际应用情况给出了简约的结果。
2. 粗糙集合和决策表
粗糙集(Rough Set，RS)是Z. Pawlak在上世纪80年代为开发自动规则生成系统和研究软计算提出的一个理论，是一种处理不精确，不确定和不完全数据的新的数学方法[6-7]。在粗糙集理论中，知识是一种分类模式或分类能力，直接对应于现实世界或抽象世界的分类。一种分类模式称为一种等效关系。粗糙集理论建构在一组概念之上。
定义1（决策系统）：一个决策系统是一个有序对S=（U,A），其中U是一个非空有限集合，称为论域；A是一个元素成为属性的非空有限集合。每一个属性 ，都是一个全函数 ，其中 是属性的值域。
定义2（不可辨识关系）：对于S=（U,A）中的每一个属性子集 ，我们定义一个二元关系 ，称为不可辨识关系，定义如下：
显然，该二元关系是一个等价关系（自反、对称和传递的）。 表示在关系中的所有等价类的集合。不可辨识概念的目的是选择一组属性 有效地对全域进行划分，使划分后每一个集合的对象彼此之间都不能仅仅用 中的属性区分开。
定义3（下近似和上近似）：一个对象集合 对于一个属性集合 （在 上定义了一个等价关系）的下近似 和上近似 定义如下：
定义4（决策属性在条件属性下的正域）：将决策系统中的进一步划分为条件属性 和决策属性 ，即 。定义决策属性在条件属性下的正域为
定义5（属性的不可省略和独立）：令 ，且 ，当 ，称为中可省略的，否则为中不可省略的。当都是中不可省略的，则属性使独立的，否则是依赖的。
定义6（属性的简化和核）：令 ，当 是独立的，且 ，则 为 的简化（显然， 可能有多个简化），记为 。 中所有不可省略属性的集合称为 的核，记为 。属性的核与简化的关系为：
在网络系统中，网络故障判定的过程实际上是一个决策过程，其决策依据可以是一个预先设定的、代表管理者经验知识的决策表；也可以是一个不断累积的、根据历史故障事件总结抽象生成的决策表。一个常见的决策表如表1所示，其中每一列代表了一个属性，每一行代表了一个对象。其中 表示了条件属性， 表示了决策属性。假定表1中 ， ；且 代表网络节点 的设备心跳响应状态，其中2表示正常，1表示较慢，0表示停止； 代表网络节点 的设备开通状态，其中2表示开通，1表示无信息，0表示关闭； 代表网络节点 的设备的开通状态。 代表系统工作时序是否正常，其中1表示正常，0表示不正常； 代表总供电状态是否正常，其中1表示正常，0表示不正常； 代表控制电路备用通道是否正常，其中1表示正常，0表示不正常；因此，表1的第一行表示了一个决策规则，即在在网络节点的设备心跳正常，网络节点的设备状态为开通，网络节点的设备状态为的，网络节点的设备状态的条件下，判断工作顺序正常，总供电状态正常，控制电路备用通道正常。由于实际情况下，网络集中控制单元得到的状态信息和故障报告事件往往较多，因此，条件属性较多，给后续处理带来了计算复杂度的增加。因此，需要对网络故障决策表进行简化。
表1. 网络故障决策表示意图
直观地说，简化后的属性是原属性必不可少的子集。根据定义6，每一个条件属性集都可能有多个简化，因此必须找到一个满足计算简便需求的简化。这个简化应该是一个简化后条件属性数量最小的简化，即满足条件属性维度最小的简化。由定义6可知，所有的简化都包含核，因此，本文的思路是从核出发，渐进地找到最小维度的简化。
3. 简约算法
寻找最小维度简化首先需要计算属性C的核；然后定义核相对于C的补集，计算补集的幂集，记为T，并记T(i)表示第i阶幂子集；然后从核出发，从最低阶的幂子集开始，根据定义6计算核和T(i)的合集是否是一个C的简化。找到简化后即返回。
其伪代码FindRed如下描述：
其中，ReduceRedundantAttribute(U,B)是为了消除在属性B下的重复的U中的对象；Pos的实现如定义4所示；
4. 实验
本文采用XX公司的网络化电力控制系统的6个应用项目为实验对象，进行网络故障决策表的简约。该网络化电力控制系统后端采用神经网络作为智能决策方法。简约的情况如表2所示。其中，N表示项目编号，M1表示简约前的条件属性维度，M2表示简约后的条件属性，T1表示简约前神经网络训练的时间，T2表示简约后的神经网络训练时间，D1表示简约前神经网络故障判定的平均时间，D2表示简约后神经网络故障判定的平均时间。系统集中控制单元的硬件为Intel Xeon 2.4G，1G内存，软件为WINXP操作系统和VC++。
表2：6个应用项目的简约前后性能对比
其中可以看到，简约后，故障决策表的条件属性得到了有效的减少。后端的神经网络训练时间得到了降低。故障判别时间也有较为明显的降低。
5. 结论
复杂网络的故障诊断是一个面向应用的复杂问题。由于故障决策表的维数量直接影响了计算的性能，对故障决策表的简约成为一个重要的问题。本文采用粗糙集来进行简约，提出了寻找最小简化的算法。实验表明该方法简单有效，性能良好。
参考文献：
[1] 沈俊，顾冠群，罗军舟，网络管理的研究和发展[J]. 计算机研究与发展， 2002(10):1153-1167
[2] Greg Tomsho, 网络维护和故障诊断指南（战小苏译）[M]. 北京：清华大学出版社，2003
[3] 王继龙，计算机网络管理系统发展综述[J]. 计算机科学，2000,27(9):52-55
[4] Kyas, O., Network Troubleshooting[M]. New York: Agilent Technologies, 2001
[5] 吴今培，肖建华，智能故障诊断与专家系统[M]. 北京：科学出版社，1997
[6] Pawlak Z., Rough Sets[J]. Comunications of ACM, 1995, 38(11):89-95
[7] 张文修，粗糙集理论与方法[M]. 北京：科学出版社，2001
注：文章内所有公式及图表请用PDF形式查看。
转载注明来源:https://www.xzbu.com/2/view-573607.htm
