• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 11
    • 下载费用:30 金币  

    重庆时时彩号码过滤工具: 一种基于流处理的模式更新方法.pdf

    摘要
    申请专利号:

    CN201610986675.7

    申请日:

    2016.11.09

    公开号:

    CN106570172A

    公开日:

    2017.04.19

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06F 17/30申请日:20161109|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 上海电机学院
    发明人: 杨定裕
    地址: 201100 上海市闵行区江川路690号
    优先权:
    专利代理机构: 上海申汇专利代理有限公司 31001 代理人: 翁若莹;吴小丽
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201610986675.7

    授权公告号:

    |||

    法律状态公告日:

    2017.05.17|||2017.04.19

    法律状态类型:

    实质审查的生效|||公开

    摘要

    本发明提供了一种基于流处理的模式更新方法,首先进行模式定义,然后建立模式索引,再采用流处理方法接收新模式,接着进行模式查找,最后进行模式更新。方法采用一种基于kd?tree的模式存储,这种方法可以把一系列模式分配到一个二叉树中,模式存储根据一定的规则进行排列。当需要更新时,可以遍历二叉树来进行查找模式节点,然后对模式进行状态更新。与传统的顺序查找相比,本方法在模式查找时,无需查找遍历整个模式集,只需要查找部分分支节点,因而本方法能够减少遍历的空间,从而提升模式查找的速度。该方法能够实现模式的实时状态更新,并支持快速的模式更新,具有模式更新速度快、并发性高、吞吐量高等优点。

    权利要求书

    1.一种基于流处理的模式更新方法,其特征在于,该方法由以下5个步骤组成:
    步骤1、模式定义
    模式是一系列具有一定的有序性的数据,其在历史数据中经常出现;模式P的定义如
    下:
    P=<Id,D{x1,…,xh},T{t1,t2…}>
    其中,其中,Id是模式的唯一标识码;D是一个数据集合,包含了本模式的所有数据,
    x1,...,xh表示模式的具体数值;T是模式出现时间的集合,t1、t2……表示模式出现的具体
    时间;
    步骤2、建立模式索引
    建立一个基于kd-tree的索引结构存储模式;由于一个模式具有一定的长度h,即相当
    于每个模式具有h个特征维度,因而使用h个维度对模式进行划分;每个层次划分时,先在一
    个区别最大的维度作为切分维度,并在这个维度上选择中位数的模式作为分支节点,然后
    存储在一个二叉树中,二叉树的深度为log(n),其中n是模式总个数;
    步骤3、采用流处理方法接收新模式
    采用流处理的架构处理新模式,当系统接收到一个新模式P时,动态地创建一个更新任
    务Task;当系统连续接收到多个模式时,系统将对每个更新任务进行分析,根据模式的发生
    时间进行排序后依次处理;
    步骤4、模式查找
    每个更新任务Task首先需要从所有模式中找到对应的模式P′,即满足两个模式的数据
    序列D是完全匹配的,P′.D=P.D,Task先遍历kd-tree,从根节点root开始,依次查找整个
    树,直到找到P′或者遍历完整个树;
    步骤5、模式更新
    根据步骤4的查找结果,对模式进行更新,如找到对应的模式P′,则对模式P′的状态进
    行更新,在P′.T的发生时间集合中追加当前模式的发生时间,即P′.T=P.T∪P′.T。
    2.如权利要求1所述的一种基于流处理的模式更新方法,其特征在于:所述步骤2中,模
    式创建一个kd-tree存储模式,采用一个贪恋方法构建一个索引树结构,多次迭代实现多层
    次的模式切分与树分支的构建;
    具体方法为:
    步骤2.1:在h个维度上,分别计算每个维度切片的方差δ,计算公式:
    <mrow> <mi>&delta;</mi> <mo>=</mo> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> <munderover> <mo>&Sigma;</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msubsup> <mi>x</mi> <mi>i</mi> <mn>2</mn> </msubsup> <mo>-</mo> <msup> <mrow> <mo>(</mo> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> <munderover> <mo>&Sigma;</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>x</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> <mn>2</mn> </msup> </mrow>
    其中,x是一个模式的值,n是模式的个数,i为遍历变量;
    步骤2.2:对每个维度的方差进行排序,选择方差最小的维度di作为切分维度;
    步骤2.3:从维度di中对模式进行排序,选择在维度di上的中位数的模式Pi作为切分节
    点,即把中位数模式Pi作为树的分支节点;
    步骤2.4:然后把其他模式分配到分支节点Pi的左分支或右分支:
    步骤2.4.1:如果模式在切分维度di上的值小于分支节点Pi的在维度di的值,则把模式
    分配到分支节点Pi的左子树中;
    步骤2.4.2:如果模式在切分维度di上的值大于分支节点Pi的在维度di的值,则把模式
    分配到分支节点Pi的右子树中;
    步骤2.5:对左子树重复执行步骤2.1,直至分支节点不包含子节点;对右子树重复执行
    步骤2.1,直至分支节点不包含子节点。
    3.如权利要求1所述的一种基于流处理的模式更新方法,其特征在于:所述步骤3中,流
    处理是采用流数据的方式对新的模式进行处理,当接收到一个模式时,流处理方式将自动
    触发一个处理程序,创建一个模式更新任务;在多个更新任务同时触发时,系统将对多个任
    务进行调度选择,采用的方法为优先模式的发生时间的方式:系统从任务队列中选择模式
    发生时间最早的任务。
    4.如权利要求1所述的一种基于流处理的模式更新方法,其特征在于:所述步骤4中,从
    模式查找是给定一个模式P,采用深度优先搜索的方式从kd-tree中找到一个与模式相等的
    序列,具体查找方法为:
    步骤4.1:输入一个模式P,与一个基于kd-tree模式索引node;
    步骤4.2:定义一个当前节点currentNode并赋值:currentNode=node;如果node为空,
    则返回null;
    步骤4.3:比较模式P与currentNode的数据序列D是否相等;
    步骤4.3.1:如相等,则说明已经找到目标模式,返回当前节点currentNode;
    步骤4.3.2:否则,找到当前节点currentNode的切分维度di,比较模式P在切分维度di上
    的值;
    步骤4.3.2.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,即
    currentNode=currentNode.LeftNode,然后重复执行步骤4.3;
    步骤4.3.2.2:如果模式P的值大,则把currentNode的右子树节点作为当前节点,即
    currentNode=currentNode.RightNode,然后重复执行步骤4.3。
    5.如权利要求4所述的一种基于流处理的模式更新方法,其特征在于:所述步骤5中:模
    式更新是采用流处理方式实时更新模式的状态,主要根据步骤4中模式查找的返回结果进
    行更新,其具体更新方法分为:
    如步骤4中返回的结果为一个节点node,则说明此模式在历史数据中发生过,此时更新
    只需要对node的状态进行更新,具体更新内容为在node的发生时间集合T中追加上当前模
    式P的发生时间,具体公式:
    P′.T=P.T∪P′.T
    如步骤4返回的结果为null,即说明该模式在模式集中没有找到,该模式为全新模式,
    采用模式插入方法对kd-tree进行更新,找到一个潜在的位置存储新模式。
    6.如权利要求5所述的一种基于流处理的模式更新方法,其特征在于:所述采用模式插
    入方法对kd-tree进行更新的具体方法为:
    步骤5.1:输入一个模式P,与一个基于kd-tree模式索引node;
    步骤5.2:同样,定义一个当前节点currentNode并赋值:currentNode=node;如果
    currentNode为空,则跳到步骤5.4;
    步骤5.3:将模式P与currentNode在切分维度di上的值比较;
    步骤5.3.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,即
    currentNode=currentNode.LeftNode,然后重复执行步骤4.3;
    步骤5.3.2:如果新模式P的值大,则把currentNode的右子树节点作为当前节点,即
    currentNode=currentNode.RightNode,然后重复执行步骤4.3;
    步骤5.4:此时currentNode为空时,迭代结束,即当前位置为模式P的潜在位置:
    步骤5.4.1:如currentNode是父节点的左子树:如父节点的右子树不为空,则直接把新
    模式P加入到父节点的左子树;如父节点的右子树为空,此时说明父节点为叶子节点,此时
    需要比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度di,
    然后比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分支
    节点的左子树节点;
    步骤5.4.2:如currentNode是父节点的右子树:如父节点的左子树不为空,则直接把新
    模式P加入到父节点的右子树;如父节点的左子树为空,同样父节点为叶子节点,此时需要
    比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度di,然后
    比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分支节点
    的左子树节点。

    说明书

    重庆时时彩单双窍门 www.4mum.com.cn 一种基于流处理的模式更新方法

    技术领域

    本发明涉及一种基于流处理的模式更新方法,属于数据处理、模式识别技术领域,
    尤其是金融行业、互联网行业的模式更新技术领域。

    背景技术

    模式是多个数值或词组合成的一个特征序列,一般在金融行业、互联网行业应用
    广泛,常用于时间序列预测、异常检测等。

    模式更新是指当接收到新的模式,需要对当前的模式进行状态更新,使得整个模
    式存档的数据是实时的。在现有的模式更新方法中,一般采用顺序的查找一个模式,然后对
    这个模式进行更新。这种方法在模式数量较少的时候是可行的,但是如果模式数量非常大,
    特别是具有百万千万的规模时,顺序查找更新的方法需要大量的时间查找模式,效率非常
    低。特别的是,如果模式的更新频率非???,系统需要不断地更新模式,这种顺序查找更新
    的方法将难以保证高效,无法提供实时模式结果,还会降低整个系统的性能。

    发明内容

    本发明要解决的技术问题是提供一种能够实现模式的实时状态更新,并支持快速
    的模式更新,且并发性高、吞吐量高的模式更新方法。

    为了解决上述技术问题,本发明的技术方案是提供一种基于流处理的模式更新方
    法,其特征在于,该方法由以下5个步骤组成:

    步骤1、模式定义

    模式是一系列具有一定的有序性的数据,其在历史数据中经常出现;模式P的定义
    如下:

    P=<Id,D{x1,…,xh},T{t1,t2…}>

    其中,其中,Id是模式的唯一标识码;D是一个数据集合,包含了本模式的所有数
    据,x1,...,xh表示模式的具体数值;T是模式出现时间的集合,t1、t2……表示模式出现的具
    体时间;

    步骤2、建立模式索引

    建立一个基于kd-tree的索引结构存储模式;由于一个模式具有一定的长度h,即
    相当于每个模式具有h个特征维度,因而使用h个维度对模式进行划分;每个层次划分时,先
    在一个区别最大的维度作为切分维度,并在这个维度上选择中位数的模式作为分支节点,
    然后存储在一个二叉树中,二叉树的深度为log(n),其中n是模式总个数;

    步骤3、采用流处理方法接收新模式

    采用流处理的架构处理新模式,当系统接收到一个新模式P时,动态地创建一个更
    新任务Task;当系统连续接收到多个模式时,系统将对每个更新任务进行分析,根据模式的
    发生时间进行排序后依次处理;

    步骤4、模式查找

    每个更新任务Task首先需要从所有模式中找到对应的模式P′,即满足两个模式的
    数据序列D是完全匹配的,P′.D=P.D,Task先遍历kd-tree,从根节点root开始,依次查找整
    个树,直到找到P′或者遍历完整个树;

    步骤5、模式更新

    根据步骤4的查找结果,对模式进行更新,如找到对应的模式P′,则对模式P′的状
    态进行更新,在P′.T的发生时间集合中追加当前模式的发生时间,即P′.T=P.T∪P′.r。

    优选地,所述步骤2中,模式创建一个kd-tree存储模式,采用一个贪恋方法构建一
    个索引树结构,多次迭代实现多层次的模式切分与树分支的构建;

    具体方法为:

    步骤2.1:在h个维度上,分别计算每个维度切片的方差δ,计算公式:


    其中,x是一个模式的值,n是模式的个数,i为遍历变量。

    步骤2.2:对每个维度的方差进行排序,选择方差最小的维度di作为切分维度;

    步骤2.3:从维度di中对模式进行排序,选择在维度di上的中位数的模式Pi作为切
    分节点,即把中位数模式Pi作为树的分支节点;

    步骤2.4:然后把其他模式分配到分支节点Pi的左分支或右分支:

    步骤2.4.1:如果模式在切分维度di上的值小于分支节点Pi的在维度di的值,则把
    模式分配到分支节点Pi的左子树中;

    步骤2.4.2:如果模式在切分维度di上的值大于分支节点Pi的在维度di的值,则把
    模式分配到分支节点Pi的右子树中;

    步骤2.5:对左子树重复执行步骤2.1,直至分支节点不包含子节点;对右子树重复
    执行步骤2.1,直至分支节点不包含子节点。

    优选地,所述步骤3中,流处理是采用流数据的方式对新的模式进行处理,当接收
    到一个模式时,流处理方式将自动触发一个处理程序,创建一个模式更新任务;在多个更新
    任务同时触发时,系统将对多个任务进行调度选择,采用的方法为优先模式的发生时间的
    方式:系统从任务队列中选择模式发生时间最早的任务。

    优选地,所述步骤4中,从模式查找是给定一个模式P,采用深度优先搜索的方式从
    kd-tree中找到一个与模式相等的序列,具体查找方法为:

    步骤4.1:输入一个模式P,与一个基于kd-tree模式索引node;

    步骤4.2:定义一个当前节点currentNode并赋值:currentNode=node;如果node
    为空,则返回null;

    步骤4.3:比较模式P与currentNode的数据序列D是否相等;

    步骤4.3.1:如相等,则说明已经找到目标模式,返回当前节点currentNode;

    步骤4.3.2:否则,找到当前节点currentNode的切分维度di,比较模式P在切分维
    度di上的值;

    步骤4.3.2.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,
    即currentNode=currentNode.LeftNode,然后重复执行步骤4.3;

    步骤4.3.2.2:如果模式P的值大,则把currentNode的右子树节点作为当前节点,
    即currentNode=currentNode.RightNode,然后重复执行步骤4.3。

    更优选地,所述步骤5中:模式更新是采用流处理方式实时更新模式的状态,主要
    根据步骤4中模式查找的返回结果进行更新,其具体更新方法分为:

    如步骤4中返回的结果为一个节点node,则说明此模式在历史数据中发生过,此时
    更新只需要对node的状态进行更新,具体更新内容为在node的发生时间集合T中追加上当
    前模式P的发生时间,具体公式:

    P′.T=P.T∪P′.T

    如步骤4返回的结果为null,即说明该模式在模式集中没有找到,该模式为全新模
    式,采用模式插入方法对kd-tree进行更新,找到一个潜在的位置存储新模式。

    进一步地,所述采用模式插入方法对kd-tree进行更新的具体方法为:

    步骤5.1:输入一个模式P,与一个基于kd-tree模式索引node;

    步骤5.2:同样,定义一个当前节点currentNode并赋值:currentNode=node;如果
    currentNode为空,则跳到步骤5.4;

    步骤5.3:将模式P与currentNode在切分维度di上的值比较;

    步骤5.3.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,即
    currentNode=currentNode.LeftNode,然后重复执行步骤4.3;

    步骤5.3.2:如果新模式P的值大,则把currentNode的右子树节点作为当前节点,
    即currentNode=currentNode.RightNode,然后重复执行步骤4.3;

    步骤5.4:此时currentNode为空时,迭代结束,即当前位置为模式P的潜在位置:

    步骤5.4.1:如currentNode是父节点的左子树:如父节点的右子树不为空,则直接
    把新模式P加入到父节点的左子树;如父节点的右子树为空,此时说明父节点为叶子节点,
    此时需要比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度
    di,然后比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分
    支节点的左子树节点;

    步骤5.4.2:如currentNode是父节点的右子树:如父节点的左子树不为空,则直接
    把新模式P加入到父节点的右子树;如父节点的左子树为空,同样父节点为叶子节点,此时
    需要比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度di,
    然后比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分支
    节点的左子树节点。

    本发明提供了一种基于流处理的模式更新方法,该方法采用一种基于kd-tree的
    模式存储,这种方法可以把一系列模式分配到一个二叉树中,模式存储根据一定的规则进
    行排列。当需要更新时,可以遍历二叉树来进行查找模式节点,然后对模式进行状态更新。
    与传统的顺序查找相比,本方法在模式查找时,无需查找遍历整个模式集,只需要查找部分
    分支节点,因而本刚刚能够减少遍历的空间,从而提升模式查找的速度。

    相比现有技术,本发明提供的方法具有如下有益效果:

    1、通过流处理的方式对模式进行处理,系统可以实时地把新的模式进行处理,无
    需等待,从而可以快速的响应模式更新任务,提高整个系统的实时性。

    2、采用kd-tree的方法存储模式,这种方法能够快速的提高模式的查找速度,有效
    提高了检测模式是否为新模式的性能,并快速找到新模式的潜在位置并更新模式状态。

    3、支持高并发性的模式更新,当模式的产生速度较快时,本方法可以快速找到模
    式并更新,系统使用模式发生时间的方式对模式更新任务进行调度,有效地保证模式更新
    的正确性,提高整个系统的吞吐量。

    附图说明

    图1为模式索引的构建实例示意图;

    图2为基于流处理的模式更新流程图;

    图3为模式更新实例示意图。

    具体实施方式

    下面结合具体实施例,进一步阐述本发明。应理解,这些实施例仅用于说明本发明
    而不用于限制本发明的范围。此外应理解,在阅读了本发明讲授的内容之后,本领域技术人
    员可以对本发明作各种改动或修改,这些等价形式同样落于本申请所附权利要求书所限定
    的范围。

    I、模式定义

    模式是一系列数据{x1,x2,...,xk},k为正整数,数据具有一定的有序性,在历史数
    据中经常出现。模式的定义如下:

    P=<Id,D{x1,…,xh},T{t1,t2…}>

    其中,Id是模式的唯一标识码;D是一个数据集合,包含了本模式的所有数据,
    x1,...,xh表示模式的具体数值;T是模式出现时间的集合,t1、t2……表示模式出现的具体
    时间。

    II、建立模式索引

    建立一个基于kd-tree的索引结构存储模式。由于一个模式具有一定的长度h,即
    相当于每个模式具有h个特征维度,因而使用h个维度对模式进行划分,每个层次划分时,先
    在一个区别最大的维度作为切分维度,并在这个维度上选择中位数的模式作为分支节点,
    然后存储在一个二叉树中,二叉树的深度为log(n),其中n是模式总个数;

    创建一个kd-tree存储模式,采用一个贪恋方法构建一个索引树结构,多次迭代实
    现多层次的模式切分与树分支的构建。

    具体方法为:

    步骤2.1:在h个维度上,分别计算每个维度切片的方差δ,计算公式:


    其中,x是一个模式的值,n是模式的个数,i为遍历变量。

    步骤2.2:对每个维度的方差进行排序,选择方差最小的维度di作为切分维度;

    步骤2.3:从维度di中对模式进行排序,选择在维度di上的中位数的模式Pi作为切
    分节点,即把中位数模式Pi作为树的分支节点;

    步骤2.4:然后把其他模式分配到分支节点Pi的左分支或右分支:

    步骤2.4.1:如果模式在切分维度di上的值小于分支节点Pi的在维度di的值,则把
    模式分配到分支节点Pi的左子树中;

    步骤2.4.2:如果模式在切分维度di上的值大于分支节点Pi的在维度di的值,则把
    模式分配到分支节点Pi的右子树中;

    步骤2.5:对左子树重复执行步骤2.1,直至分支节点不包含子节点;对右子树重复
    执行步骤2.1,直至分支节点不包含子节点;

    图1为一个kd-tree的构建例子,模式集包含了7个模式,每个模式包含了4个维度,
    因此在构建过程中,首先选择切分维度,即计算{X4,X3,X2,X1}中的方差,然后选择方差最大
    的维度X2,然后选择中位数(X2=11)的分支节点的模式pId=7,然后把在维度X2为比较基
    准,把小于11分配到左子树中,把大于11的模式分配到右子树中,如此迭代即完成整个kd-
    tree的构建。

    III、采用流处理方法接收新模式

    采用流处理的架构处理新模式,处理架构如图2所示,处理方式为使用流数据的方
    式对新的模式进行处理,当接收到一个模式时,流处理方式将自动触发一个处理程序,创建
    一个模式更新任务。

    在多个更新任务同时触发时,系统将对多个任务进行调度选择,其中采用的方法
    为优先模式的发生时间的方式:系统从任务队列中选择模式发生时间最早的任务。

    IV、模式查找

    每个更新任务Task首先从需要从所有模式中找到对应的模式P′,即满足两个模式
    的数据序列D是完全匹配的,P′.D=P.D,Task先遍历kd-tree,从根节点root开始,依次查找
    整个树,直到找到P′或者遍历完整个树。具体步骤如下:

    步骤4.1:输入一个模式P,与一个基于kd-tree模式索引node;

    步骤4.2:定义一个当前节点currentNode并赋值:currentNode=node;如果node
    为空,则返回null;

    步骤4.3:比较模式P与currentNode的数据序列D是否相等;

    步骤4-3.1:如相等,则说明已经找到目标模式,返回当前节点currentNode;

    步骤4.3.2:否则,找到当前节点currentNode的切分维度di,比较模式P在切分维
    度di上的值;

    步骤4.3.2.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,
    即currentNode=currentNode.LeftNode,然后重复执行4.3;

    步骤4.3.2.2:如果模式P的值大,则把currentNode的右子树节点作为当前节点,
    即currentNode=currentNode.RightNode,然后重复执行4.3。

    V、模式更新

    根据步骤IV的查找结果,对模式进行更新,如找到对应的模式P′,则对模式P′的状
    态进行更新,在P′.T的发生时间集合中追加当前模式的发生时间,即P′.T=P.T∪P′.T:

    如步骤4中返回的结果为一个节点node,则说明此模式在历史数据中发生过,此时
    更新只需要对node的状态进行更新,具体更新内容为在node的发生时间集合T中追加上当
    前模式P的发生时间,具体公式:

    P′.T=P.T∪P′.T

    如步骤4返回的结果为null,即说明该模式在模式集中没有找到,该模式为全新模
    式,采用模式插入方法对kd-tree进行更新,找到一个潜在的位置存储新模式,具体插入方
    法为:

    步骤5.1:输入一个模式P,与一个基于kd-tree模式索引node;

    步骤5.2:同样,定义一个当前节点currentNode并赋值:currentNode=node;如果
    currentNode为空,则跳到步骤5.4;

    步骤5.3:将模式P与currentNode在切分维度di上的值比较;

    步骤5.3.1:如果模式P的值小,则把currentNode的左子树节点作为当前节点,即
    currentNode=currentNode.LeftNode,然后重复执行4.3;

    步骤5.3.2:如果新模式P的值大,则把currentNode的右子树节点作为当前节点,
    即currentNode=currentNode.RightNode,然后重复执行4.3;

    步骤5.4:此时currentNode为空时,迭代结束,即当前位置为模式P的潜在位置:

    步骤5.4.1:如currentNode是父节点的左子树:如父节点的右子树不为空,则直接
    把新模式P加入到父节点的左子树;如父节点的右子树为空,此时说明父节点为叶子节点,
    此时需要比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度
    di,然后比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分
    支节点的左子树节点。

    步骤5.4.2:如currentNode是父节点的右子树:如父节点的左子树不为空,则直接
    把新模式P加入到父节点的右子树;如父节点的左子树为空,同样父节点为叶子节点,此时
    需要比较新模式P与父节点模式:首先选择两个模式的切分维度,选择方差最大的维度di,
    然后比较两个模式在维度di的值大小,以值大的模式作为分支节点,值小的模式作为分支
    节点的左子树节点。

    模式更新方法可以通过如图3的例子说明,其中第一个模式为P2,可以通过模式查
    找发现该模式之前出现过,通过模式查找后得到该模式节点,然后通过对模式P2进行更新,
    在该模式的出现时间集合T中加上当前模式的时间;而第二个模式P6为新模式,需要找到一
    个潜在位置存放模式P6,首先找到模式P3,然后比较两个模式之间的关系,选择一个切分维
    度,然后把模式P6作为分支节点,而模式P3作为模式P6的左子树。

    关 键 词:
    一种 基于 处理 模式 更新 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:一种基于流处理的模式更新方法.pdf
    链接地址://www.4mum.com.cn/p-6092789.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03