《数据挖掘算法》由会员分享，可在线阅读，更多相关《数据挖掘算法（9页珍藏版）》请在金锄头文库上搜索。
1、Timeweaver: a Genetic Algorithm for Identifying Predictive Patterns in Sequences of EventsAbstract从过去的序列事件学习预测未来事件是非常重要的。本文描述了Timeweaver,一个基于遗传算法的机器学习系统，可以通过识别数据中的预测性的临时和序列模 式来解决事件预测问题。Timeweaver系统被用来预测通信设备故障。Introduction本文的重点是从时间标记事件序列中预测特定类型的未来事件，称之为目标事 件。从告警信息日志中预测通信设备故障就是其中的一个例子。由于机器学习和统 计方法不太适用
2、于此类问题，本文采用遗传算法来解决事件预测问题。本文给出 Timeweaver的详细描述，其可以通过识别数据中预测模式来解决罕见事件预测问 题。The general approach解决事件预测问题包括两个步骤：第一步，使用遗传算法来寻找预测模式的空间，为了确定一套模式，可以很好地独 立预测目标事件的子集和全面地预测大多数目标事件。第二步，从最好到最坏对模式进行排序，主要根据它们预测的精度，并且除去冗余 的模式。The genetic algorithmThis section describes a genetic algorithm that searches fbr patterns
3、that successfully predict the future occurrence of target events. The basic steps in our steady-state GA are shown below:1. Initialize population2. while stopping criteria not met3. select 2 individuals from the population4. apply the crossover operaior with probability P匚 and mutation operator with
4、 probability PM5. evaluate the 2 newly fonned individuals6. replace 2 existing individuals with the new ones7. done对于事件预测的评估方法口 # Target Events Predicted 门 一TPRecall = , Precision =Total Target EventsTP + FP., n# Target Events PredictedNormalized Precision =# Target Events Predicted + FPr, j一# Targe
5、t Events PredictedReduced Precision =# Target Events Predicted + Discounted FPTP = True Positive Prediction FP = False Positive PredictionFigure 2: Evaluation Measures for Event Prediction使用信息检索度量其称为F-measure其定义如下式。P的值，是控制回召精确性的 相对重要性，其随着GA的每次迭代而改变，以便在0和1值之间循环使用。Htness-(炉 + 1)Precson - recall precis
6、ion + recallCreating prediction rule 建立预测规则描述了一个有效的算法，用来对通过遗传算法得到的预测模式进行排序和去除 冗余模式。r2.3.5.6.1.8.9.10.11.12,GA for each paltcnr The algorithm for tor mi ng a solution, S, from a set of candidate patterns, C, is shown below:C = patterns returned from the GA; S = Q;while C 0 dofor c eC doif (increase_r
7、ecall(S+c, S) x.score)S = S | best; C = C - best;recompute S.precision on training set; doneResults本文研究了从时间序列数据中预测带有分类特征的罕见事件。说明了罕见事件预测问题如何配置成机器学习问题。解释了怎样通过Timeweaver,基于遗传算法的机器学习系统来解决这一类问题，其通过未修改的事件序列数据来识别预测时间和 序列模式。Predicting Telecommunication Equipment Failures from Sequencesof Network AlarmsAbstr
8、act本文描述了一个时间数据挖掘系统称为Timeweaver,用于从网络告警信息日志中识别通信设备的故障。Project Overview在数据挖掘技术出现之前，用来在故障发生前识别该故障的系统有：AT&T sANSWER（Automated Network Surveillance with Expert Rules） system,但是其知识获 取过程费时并且昂贵、通常不能获取重要的定量关系。数据挖掘技术的出现极大的帮助了自动识别数据中的模式， 进而有利于网络性能 的监控管理，作者介绍了一个数据挖掘系统Timeweaver从网络告警日志信息中 识别预测通信设备故障。本文提到的数据挖掘就是要
9、识别网络告警日志里面的模式，可以被用来预测通讯设备的故障。KDD过程（Knowledge Discovery Database识发现数据库 ）理解数据挖掘问题KDD过程的第一步包括理解应用领域以及 KDD任务的目标。在本例中，我们需要理解以前的相关工作 （ANSWER expert system）,目标是预 测个体组件的故障。对某个部件失效的正确预测，是指这个预测结果在警告时间至监控时间内发生。 警告时间是指在真正的失效发生前，用户可以对预测的失效进行足够的响应的时间； 监控时间让用户对预测到的特征进行控制和处理。模式语言：1）因为告警可以被一些不相关的问题引起，所以模式语言应该能够具体说明告
10、 警和模式的正确匹配。2）因为某些故障会在不同的时间以不同的方式表现出来，所以模式语言应该保证在模式中，所有的告警顺序不会被改变。3）因为时间是一个重要的因素，并且系统行为会因为错误的响应而发生改变， 所以一个模式应该与一个时间段关联起来。选择目标数据集目标数据集由通过系统的两个数据控制中心之一的数据库中收集的两周的告警 数据组成。因为告警数量很多，并且每个告警的属性也很多，因此经过筛选选择了 其中5个属性：1）告警产生的时间2）产生告警的设备的ID3）设备的类型4）告警的特征码5）告警的严重程度预处理及转化数据因为不用区别不同类型的故障，各种的故障告警被一个通用的故障告警替换。 由于日常维护
11、测试会引起失败的组件，从而产生额外的故障告警。因此使用一个简 单程序应用到目标数据集来去除冗余的故障告警。数据挖掘主要包括选择数据挖掘任务和适用的挖掘算法，数据挖掘任务就是预测任务， 而选择的算法是时态数据挖掘算法（temporal data mining algorithmi）选择挖掘算法时需要注意，有些设备故障很少产生并且不容易预测，考虑到这 些特征，数据挖掘算法需要寻找很少发生的模式并且具有相当低的预测精度。基于 遗传的数据挖掘算法可以解决这一问题。结果解释数据挖掘会产生一系列模式来预测组件故障，比如pattern x可以导出y devicefailureo模式回召率是其预测的故障所占百
12、分比，模式精度是预测正确的时间所占的百分比。为了帮助选择所生成模式的最适当子集，我们的数据挖掘软件从最高到最低的 精确度将模式进行排序，然后使用该排序来生成精度/召回率曲线。Recall知识合并KDD的最后一步就是将发现的知识进行合并，这是通过记录和分发关键结果来 实现的。最重要的是还将结果以规则的形式合并到了ANSWER系统中。数据挖掘算法本文开发了 Timeweaver数据挖掘软件包。Timeweaver是一个基于遗传算法的 数据挖掘系统，为了解决事件预测问题而促进了预测模式的发展。采用遗传算法的 一个重要因素是，大多数已有的方法都不适用于此处的数据挖掘任务。例如，规则 和决策树不适用，是
13、因为这两种方法主要用在分类的实例上，而本文方法却包含了 事件流。发现事件间的模式，需要考虑可以直接在可能模式的空间内搜索的方法。 考虑到数据挖掘任务的本质以及关于模式语言的需求，模式的空间是巨大的。考虑 到预测任务的困难性以及告警之间的关系在鉴别错误中至关重要，我们认为贪婪算 法不能充分地探索搜索空间。综上，选择了遗传算法，该方法具有在大范围搜索空 间内高效的搜索能力。设计遗传算法的第一个问题是如何在总量中编码每个个体（The first issue indesigning a genetic algorithm is how to encode each individual in the
14、population。在这 个例子中，每个个体代表一个模式。Timeweaver中的模式由一序列的模式-事件（pattern-events表示，每个模式-事件大体上相当于数据集中的一个事件（ie,这个 项目中提到的告警）。模式也有以下扩展：1）每个模式-事件的特征值可能采用一个通配符值（wildcard value）,2） 连续的 pattern-events问指定了有序的约束（ordering constraint3） 一个模式的持续时间与每一个模式相关联一个模式是匹配一个序列的事件的，如果 1）模式中每个的模式-事件能够匹配 这个序列中的事件，2）服从了模式中指定的有序的约束，3）在这个匹配中涉及到 的所有事件都在一个时间段内发生，且没有超过模式持续时间。例如：在这个通信领域， 每个 pattern-event形 Timeweaver产生的一个样例模式如：351: * *如果在同样的TMSP设备上，在351秒内，两个major级别的告警发生，接着 一个minor级别的告警发生，那么以上样例模式被匹配。 ”代表通配符，表面诊 断码不重要，”代表after约束，指定了事件的相对顺序。新的模式是由已有模式结合一个交叉（crossover操作符产生的，或者通过一
