一种基于规则合并的数据流预测方法

摘要

本发明提出的一种基于规则合并的数据流预测方法，基于区间最小发生的数据流预测过程分为匹配和预测两个阶段，在匹配阶段通过情节规则的合并与重组，以及非确定自动机的引入，可有效降低匹配复杂度；在预测阶段，通过引入区间最小发生的概念，将最小发生与发生区间关联，并采用概率叠加的方法，预测未来情节在区间内的发生概率。本发明对含有相同的事件类型的情节规则进行合并与重组，有效降低了匹配的复杂度，将最小发生与发生区间关联，避免了最近最小非重叠发生的不精确以及最小发生的“过匹配”问题，采用概率叠加的方法，提高了预测未来情节的准确性。

主权项

1.一种基于规则合并的数据流预测方法，其特征在于步骤如下：步骤1、基于非确定自动机的规则合并重组：对一个含有五元组(l,r,s,c,w)的情节规则γ进行合并与重组，其中l,r,s,c,w分别称为γ的前件、后件、支持度、置信度和宽口宽度；步骤2、搜索规则前件的区间最小发生：步骤1）根据截止时刻减去给定的区间大小得到预测区间；步骤2）比较状态j与规则重度r.rep的大小，如果j≤r.rep，则搜索下一个窗口，j+1；步骤3）比较状态j与情节规则γ的前件大小|γ.l|，如果相等，则令情节规则γ的前件在数据流上出现一次最小发生的起始时间等于记录γ[1]在数据流上出现时间的循环队列的起始时间γ.ts＝γ.tq[1]；令在数据流上出现一次最小发生的终止时间等于状态i发生时间γ.te＝t_i；γ.l与γ.r串接后的情节中各事件类型的序号等于状态j,γ.ind＝j；步骤4）继续寻找情节规则γ的下一状态，找到所有的前件状态为止；步骤3、根据规则前件，预测未来情节的后件发生：采用概率叠加的方法，预测未来情节在多个区间内的发生概率，具体的步骤为：步骤1）根据滑动窗口的大小找出所有区间最小发生的规则前件；步骤2）对于每一个区间最小发生的规则前件，在规定窗口大小下，找到其对应的后件发生区间；步骤3）在这些后件发生区间内，根据概率叠加发生，对每一个窗口下出现规则后件求其发生概率期望：其中n_i表示窗口大小减去第i个区间最小发生的大小，m表示所有的区间最小发生的个数；步骤4）比较截止时间以后最大的E_j所对应的窗口即为发生情节规则γ的最大概率窗口。