自非常高速率的数据流的水平决策树学习

摘要

本发明一般地涉及自非常高速率的数据流的水平决策树学习。这里提供了在数据处理系统中用于分布式树学习的机制。源处理实例向多个模型更新处理单元分配数据记录实例。多个模型更新处理单元基于数据记录实例确定在决策树中并行的候选叶分裂动作。多个模型更新处理单元向多个冲突解决处理单元发送候选叶分裂动作。多个冲突解决处理单元识别冲突叶分裂动作。多个冲突解决处理单元将树结构变化应用于在多个模型更新处理单元中的决策树。

说明书

技术领域

本申请一般涉及改进的数据处理装置和方法，更具体地涉及能够允许水平决策树从非常高速率的数据流中学习的机制。

背景技术

大数据是用于大到或者复杂到传统数据处理应用不足以处理的数据集合的术语。其所面临的挑战包括分析、捕获、监护(curation)、搜索、分享、存储、传送、可视化以及信息隐私。该术语常常用来指代使用预测分析或其他特定先进方法来从数据提取价值，而很少指特定尺寸的数据集合。

流计算是大数据的一个关键主题。流计算受到数据的时效性(Velocity)、数据量(Volume)、可疑性(Veracity)、多样性(Variety)的影响。流计算应用必须解决处理的低延迟性、数据流的高速度、精细的数据粒度以及潜在的无限制的数据大小。可伸缩性在流计算系统中扮演一个关键的角色。可伸缩性涉及分布式计算和并行处理的能力。

Streams是国际商业机器公司的大数据和流计算系统。Streams是允许用户开发的应用在信息从成千上万的实时源到达时快速摄取、分析和关联这些信息的高级分析平台。该解决方案可以处理非常高的数据吞吐率，高至每秒数以百万计的事件或消息。物联网(IoT)是物理对象或“事物”的网络，其嵌有电子、软件、传感器和连接，使得其通过与制造商、运营商、其他连接设备或云交换数据，实现更大的价值和服务。每个事物可以通过其嵌入的计算系统唯一地识别，但能够与现有的因特网基础架构互连互通。IoT产生大量的要实时地或者以批处理模式处理的数据。

在批处理模式和流模式大数据系统中，决策树归纳法是大规模机器学习中最流行和重要的算法之一。在流场景下对于并行化已经进行了很好的研究，但现有的解决方案并不完美。

流并行决策树(SPDT)算法是为了解决高数据到达率所进行的尝试。SPDT采用分布式数据压缩(直方图)的计算，但采用集中式模型更新，而这是一个瓶颈。由于高成本的模型更新计算，SPDT不能扩展。

可扩展高级大规模在线分析(SAMOA)是一个用于挖掘大数据流的框架。SAMOA采用垂直Hoeffding树(VHT)用于分类。VHT是为稀疏数据剪裁的决策树的分布式流版本。SAMOA从一个实例的角度提供了分布式模型更新计算。SAMOA不使用实例级的并行化，因此，它不能处理高数据到达率。大规模在线分析(MOA)是一种不可扩展的流决策树。MOA使用顺序数据输入和模型更新计算。

发明内容

在一个示意性实施例中，在数据处理系统中提供了分布式树学习的方法。该方法包括由源处理实例向多个模型更新处理单元(processing items)分配数据记录实例。该方法进一步包括由多个模型更新处理单元基于数据记录实例确定在决策树中并行的候选叶分裂动作。该方法进一步包括由多个模型更新处理单元向多个冲突解决处理单元发送候选叶分裂动作。该方法进一步包括由多个冲突解决处理单元识别冲突叶分裂动作。该方法进一步包括由多个冲突解决处理单元将树结构变化应用于在多个模型更新处理单元中的决策树。

在其它示意性实施例中，提供了包括具有计算机可读程序的计算机可用或可读介质的计算机程序产品。所述计算机可读程序在计算设备上执行时使计算设备执行以上概述的关于方法示意性实施例的各种操作之一和操作的组合。

在另一个示意性实施例中，提供一种系统或装置。该系统或装置可以包括一个或多个处理器以及与所述一个或多个处理器耦接的存储器。该存储器可以包括指令，当所述指令由一个或多个处理器执行时使一个或多个处理器执行以上概述的关于方法示意性实施例的各种操作之一和操作的组合。

本发明的这些和其他特征以及优点将在下面对本发明的示例实施例的详细描述中进行描述，或者对于本领域技术人员来说将变得明显。

附图说明

通过参考下面结合附图对于例示实施例的详细描述，可以更好地理解本发明以及其优选使用方式以及进一步的目标和优点，在附图中：

图1是可以实现示意性实施例的各个方面的多处理器数据处理系统的示例图；

图2是可以实现示意性实施例的各个方面的数据处理系统芯片的示例框图；

图3描述了决策树学习的垂直并行机制；

图4描述了决策树学习的水平并行机制；

图5示出了决策树学习的节点分裂；

图6描述了典型流决策树算法；

图7A描述了根据示意性实施例的用于具有冲突解决的决策树学习的水平并行机制；

图7B-7D示出根据示意性实施例的由模型更新处理单元处理的决策树模型；

图8描述了根据示意性实施例的具有冲突解决的决策树学习的水平并行逻辑视图；以及

图9是根据示意性实施例的具有冲突解决的决策树学习的水平并行机制的操作流程图。

具体实施方式

大数据流处理的真实世界的应用存在几个挑战。数据到达速率很高。例如，在小规模连接的交通工具平台中，全球定位系统(GPS)应用每秒考虑一百万GPS数据实例。而且，数据属性数目(特征尺寸)可以很大。例如，实时文本分析考虑一万或更多个属性。随着一天二十四小时和一周七天内到达的数据，要考虑的数据量可以是无限的。

示意性实施例提供了能够使水平决策树从极高速率的数据流学习的机制。在一些应用中，例如在连接汽车或车辆对车辆(vehicle-to-vehicle)的通信场景中，属性数目不大，但是数据率非常高。示意性实施例的机制水平并行实现从高速率的数据流的水平决策树学习的计算量最大的部分。

在开始讨论例示实施例的各个方面之前，首先应该了解的是，在该描述中，术语“机制”将用于指代本发明的执行各种操作、功能等的元素。如同这里所使用的，“机制”可以是例示实施例的各个功能或方面的以装置、过程或计算机程序产品形式的实现。在过程的情况下，该过程由一个或多个设备、装置、计算机、数据处理器系统等实现。在计算机程序产品的情况下，由在计算机程序产品中包含的计算机代码或指令表示的逻辑由一个或多个硬件设备执行，以便实现与特定“机制”相关联的功能或执行相关联的操作。这样，这里所描述的机制可以实现为专用硬件、在通用硬件上执行的软件、存储在介质上以便可以由专用或通用硬件容易地执行的软件指令、用于执行功能的过程或方法以及上述的任意组合。

本说明书和权利要求中对于例示实施例中特定的特征和元素会用到术语“一”、“至少一个”和“一个或多个”。应该理解，这些术语和短语意图表明在特定的例示实施例中存在至少一个特定特征或元素，但也可以存在多于一个的特定特征或元素。也就是说，这些术语/短语并非意图将说明书或者权利要求书限制到存在单个特征/元素，或者要求存在多个这样的特征/元素。相反，这种术语/短语仅要求存在至少一个单个特征/元素，在本说明书和权利要求书的范围内，也存在着有多个这样的特征/元素的可能性。

另外，应该理解，下面的描述对于例示实施例中的各个元素使用了多个各种示例，以便进一步显示例示实施例的实现示例，并帮助理解例示实施例的机制。这些示例并非旨在限制性的，或是对于实现例示实施例的机制的各种可能性的穷举。对于所属技术领域的普通技术人员来说，在该描述的基础上，对于这些各个元素获得许多其他替代实现是显而易见的，其可以被用来附加到或者替换这里所提供的示例，而不偏离本发明的精神和范围。

各示例性实施例可以用于许多不同类型的数据处理环境。为了针对特定元素的描述和示例性实施例的功能提供上下文，在下面图1和2被提供为其中可以实现示例性实施例的各个方面的实例环境。应该理解，图1和2只是实例并且并非旨在断言或暗示有关其中可以实现本发明的各个方面或实施例的环境的任何限制。在不偏离本发明的精神和范围的情况下可以对所示环境做出许多修改。

图1示出其中可以实现示例性实施例的各个方面的实例分布式数据处理系统的图形表示。分布式数据处理系统100可以包括其中可以实现示例性实施例的各个方面的计算机网络。分布式数据处理系统100包含至少一个网络102，其是用于在分布式数据处理系统100中连接在一起的各种设备和计算机之间提供通信链路的介质。网络102可以包括连接，例如有线、无线通信链路或光缆。

在所示实例中，服务器104和服务器106以及存储单元108连接到网络102。此外，客户端110、112和114也连接到网络102。这些客户端110、112和114例如可以是个人计算机、网络计算机等。在所示实例中，服务器104为客户端110、112和114提供数据，例如引导文件、操作系统映像和应用。在所示实例中，客户端110、112和114是服务器104的客户端。分布式数据处理系统100可以包括其它服务器、客户端和其它未示出的设备。

在所示实例中，分布式数据处理系统100是因特网，同时网络102代表全球范围内使用传输控制协议/网际协议(TCP/IP)协议集来相互通信的网络和网关的集合。在因特网的核心是主节点或主机之间的高速数据通信线路的主干，它包括数以千计的商业、政府、教育以及其它路由数据和消息的计算机系统。当然，分布式数据处理系统100也可以实现为包括许多不同类型的网络，例如内联网、局域网(LAN)、广域网(WAN)等。如上所述，图1旨在作为一个实例，并非旨在作为对本发明的不同实施例的体系架构限制，因此，图1中所示的特定元素不应该被视为有关其中可以实现本发明的示例性实施例的环境的限制。

图2是其中可以实现示例性实施例的各方面的示例数据处理系统的框图。数据处理系统200是例如图1中的客户机110的计算机的实例，其中可以包括实现本发明的示例性实施例的过程的计算机可用代码或指令。

在所述示例中，数据处理系统200采用包括北桥和存储控制器中心(NB/MCH)202以及南桥和输入/输出(I/O)控制中心(SB/ICH)204的中心架构。处理单元206、主存储器208和图形处理器210连接到NB/MCH 202。图形处理器210可以通过加速图形端口(AGP)连接到NB/MCH 202。

在所示示例中，局域网(LAN)适配器212连接到SB/ICH 204。音频适配器216、键盘和鼠标适配器220、调制解调器222、只读存储器(ROM)224、硬盘驱动器(HDD)226、CD-ROM驱动器230、通用串行总线(USB)端口和其它通信端口323，以及PCI/PCIe设备234通过总线238和总线240连接到SB/ICH 204。PCI/PCIe设备例如可以包括用于笔记本计算机的以太网适配器、外接卡和PC卡。PCI使用卡总线控制器，而PCIe不使用。ROM 224例如可以是闪速基本输入/输出系统(BIOS)。

HDD 226和CD-ROM驱动器230通过总线240连接到SB/ICH 204。HDD 226和CD-ROM驱动器230例如可以使用集成驱动电子设备(IDE)或串行高级技术附件(SATA)接口。超级I/O(SIO)设备236可以连接到SB/ICH 204。

操作系统在处理单元206上运行。该操作系统协调图2中的数据处理系统200内的各种组件并提供对它们的控制。作为客户端，操作系统可以是可商购的操作系统，例如Windows诸如Java^TM程序设计系统之类的面向对象的程序设计系统可以结合操作系统运行，并提供从数据处理系统200上执行的Java^TM程序或应用到操作系统的调用。

作为服务器，数据处理系统200例如可以是eServer^TM>计算机系统、基于Power^TM的处理器的计算机系统等，其运行Advanced>操作系统或操作系统。数据处理系统200可以是对称多处理器(SMP)系统，其中在处理单元206中包括多个处理器。备选地，可以采用单处理器系统。

操作系统、面向对象的程序设计系统以及应用或程序的指令位于HDD 226之类的存储器件上，并且可以加载到主存储器208内以便由处理单元206执行。本发明的示例性实施例的过程可以由处理单元206使用计算机可用程序代码执行，该计算机可用程序代码可位于存储器(例如主存储器208、ROM 224，或者一个或多个外围器件226和230)中。

诸如图2所示的总线238或总线240之类的总线系统可以由一个或多个总线构成。当然，该总线系统可以使用任何类型的通信组织或架构实现，这些通信组织或架构提供与这些通信组织或架构相连的不同组件或设备之间的数据传输。诸如图2的调制解调器222或网络适配器212之类的通信单元可以包括一个或多个用于发送和接收数据的装置。存储器例如可以是主存储器208、ROM 224或例如在图2的NB/MCH 202中找到的高速缓冲存储器。

所属技术领域中的普通技术人员将理解，图1和2中的硬件可以根据实现而改变。除了图1和2所示的硬件之外，还可以额外地使用诸如闪存、等效的非易失性存储器或光盘驱动器等之类的其它硬件或外围器件，或者使用这些器件作为备选。另外，在不偏离本发明的精神和范围的情况下，示例性实施例的过程可应用于多处理器数据处理系统，而非上面所述的SMP系统。

而且，数据处理系统200可以采取若干种不同数据处理系统中的任何一种的形式，包括客户端计算设备、服务器计算设备、平板计算机、膝上型计算机、电话或其它通信设备、个人数字助理(PDA)等。在某些说明性示例中，数据处理系统200可以是便携式计算设备，其被配置为带有闪存以提供非易失性存储器来存储例如操作系统文件和/或用户生成的数据。本质上，数据处理系统200可以是任何已知的或以后开发的数据处理系统，而没有任何架构限制。

图3描述了决策树学习的垂直并行机制。源处理单元305接收多个数据实例310。处理单元(processing item)(PI)可以是诸如图1中的分布式数据处理系统100的分布式计算环境中的计算机、处理节点、处理器、处理核、虚拟化处理硬件等。每个数据实例310包含多个属性(A,B,C,D等)。垂直并行是通过向多个局部统计的处理单元315之中的每一个分发属性的子集获得的。该机制将局部统计信息聚集到全局决策树。当维度(属性的数目)很高时垂直并行是适合的。然而﹐并行级别在一个实例级别受O(属性的数目)的限制。在可扩展的高级大量在线分析(SAMOA)中的垂直Hoeffding树(VHT)遵循这个范式类型，但一次只能处理一个实例。

图4描述了用于决策树学习的水平并行机制。源PI 405接收多个数据实例410。水平并行是通过向局部统计PI 415分发数据实例获得的，这产生了用于决策树学习的局部统计。模型聚合器PI 420执行周期性的局部统计聚集。当数据到达速率较高时水平并行是合适的。并行级别不受限制。流并行决策树(SPDT)遵照这个范式类型，然而，树模型学习被集中化，其限制了整体的可伸缩性。

图5示出决策树学习的节点分裂。决策树具有分支出多个子节点的根节点。每个节点基于属性的值进行分支，直到树到达叶节点，这确定了数据实例的类。树可以通过基于属性值测试将源集分裂为子集来进行“学习”。以称作递归分割的递归方式对每个获得的子集重复这个过程。当节点的子集具有相同的目标变量值时或者当分裂不再向预测添加值时，递归完成。在描述的例子中，节点针对样本问题ATTR_ONE>5？进行分裂。

图6描述了典型的流决策树算法。算法600是Hoeffding树归纳的实例，其中E是一个训练实例以及HT是决策树的当前状态。在步骤4-8，对于每个属性，算法600计算是用于在该属性上分裂的信息增益。在步骤6和7，算法600发现具有最高的属性以及具有第二高的属性。算法600在步骤4-8的部分是决策树学习计算量最大的部分。

决策树学习(即，叶节点分裂的模型更新)不是严格水平并行的，这是由于树结构学习通常对实例顺序敏感。在SPDT，中心化的模型更新的瓶颈限制了水平并行级别和整体可伸缩性。示意性实施例基于如下确定，即数据流中的实例顺序改变可以导致不同的树结构，但是预测性能可能对顺序不敏感。

在一个试验中，一个机制利用随机树产生100,000个数据记录实例。前50,000个是训练样本，其余是测试样本。该机制应用MOA训练流决策树。机制通过基线(Baseline)指示性能(纠正预测百分比)。

然后该机制随机指定50％的实例作为训练样本以及其余作为测试样本以在测试中重新训练流决策树。该机制重复5次来看是否预测的性能发生变化。结果如下：基线＝90.19％，测试1＝90.25％，测试2＝90.14％，测试3＝90.14％，测试4＝90.28％，测试5＝90.39％，并且5次测试的平均值＝90.25％。这意味着在数据流中的实例顺序变化可以导致不同的树结构，但是如果基于“独立和相同分布”(i.i.d.)的假设，预测性能对顺序不敏感。大多数时候，预测性能是机器学习的目标，模型结构不是目标。这允许示意性实施例的机制能够设计从流数据的水平决策树学习。

图7A描述了根据示意性实施例的用于具有冲突解决的决策树学习的水平并行机制。源处理单元(PI)705接收多个数据实例710。水平并行通过将数据实例分配到执行局部决策树学习的模型更新PI 715来实现。在每个模型更新PI715，树学习是局部的。这种同时发生的学习范式等同于将顺序变化应用于训练实例。每个模型更新PI 71 5并行地计算信息增益或者其它测量来获得候选叶分裂动作。每个模型更新PI 715确定必须被分裂的候选树节点。在一个实施例中，模型更新PI 715使用哈希函数来向冲突解决PI 720发送叶节点标识。

冲突解决PI 720检测冲突。冲突解决PI 720划分优先次序并决定执行哪个分裂动作。冲突解决PI 720标记被阻碍的分裂动作的“from_MUPI_id”。冲突解决PI 720聚合相同叶的统计信息来确保信息一致性并且将树变化应用到模型更新PI 715。

图7B-7D示出根据示意性实施例由模型更新处理单元处理的决策树模型。图7B示出由模型更新PI A处理的决策树模型；图7C示出由模型更新PI B处理的决策树模型；以及图7D示出由模型更新PI C处理的决策树模型。图7B中的决策树模型为叶节点A1和A2产生统计信息；图7C中的决策树模型为叶节点B1和B2产生统计信息；以及图7D中的决策树模型为叶节点C1和C2产生统计信息。

每个模型更新PI 715能够访问决策树副本或者能够访问共享存储器的决策树。模型更新PI 715执行以下函数：

Map<leaf_id,(splt_attr_id,splt_point,stat_info,from_MUPI_id)>

这里leaf_id是叶节点(例如图7B中的A1和A2)的标识，splt_attr_id是引起分裂的属性的标识，splt_point是发生分裂的属性值，stat_info是统计信息(例如信息增益)，from_MUPI_id是模型更新PI的标识。在描述的实例中，冲突解决PI 720识别涉及叶节点C2的冲突并决定不进行与叶节点C2相关的叶分裂动作。

在下一轮中，与在通常情况下一样，其标识被标记为from_MUPI_id的模型更新PI715不读取新数据而是保持旧数据批次来计算信息增益。唯一的区别是在最后一轮分裂的节点将不再接受数据批次中的实例，称之为这些节点的“关闭阀”。这防止相同的数据在相同的节点被学习多次。

随着树长大，实例的不同小集变得越来越不可能落入相同的叶节点。这意味着观察到的冲突的可能性随着时间而减小。在实践中，流决策树可以有数千个(10³或更多)叶节点，但是只有很小一部分会在每个周期分裂(10⁰～10¹)。

图8描述了根据示意性实施例的用于具有冲突解决的决策树学习的水平并行逻辑视图。为了确定可伸缩性优点，考虑以下各项：D是在单位时间内到达的数据大小，d_i是模型更新PI的并行级别，d_c是冲突解决PI的并行级别，n_tree是当前决策树的节点数目，n_attr是属性的数目，L是stat_info被改变的叶的数目，U是最后分裂用于模型更新的叶的数目，以及T是针对一个属性的信息增益的平均计算时间，该平均计算时间在实践中可以很大。

一个周期的顺序计算复杂性如下所示：

D·O(logn_tree)+L·n_attr·T

对于SPDT，计算复杂性如下所示：

$>\frac{1}{d_i}D·O\left({\mathrm{logn}}_{tree}\right)+L·n_{attr}·T$>

对于示意性实施例的机制，计算复杂性的最坏情况如下所示：

$>\frac{1}{d_i}[D·O\left({\mathrm{logn}}_{tree}\right)+L·n_{attr}·T]+\frac{1}{d_c}O(L·d_i)$>

对于示意性实施例的机制，计算复杂性的最好情况如下所示：

>

本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Java、Smalltalk、C++等，以及常规的过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

图9是根据示意性实施例的具有冲突解决的决策树学习的水平并行机制的操作流程图。操作开始(块900)，并且该机制水平分割流实例并将数据记录实例提供给分布的模型更新处理实例(块901)。每个模型更新处理单元(PI)并行地计算信息增益或其它测量来获得候选叶分裂动作(块902)。

在冲突解决PI，该机制聚合所有候选叶分裂动作(块903)。该冲突解决PI检测冲突动作、划分优先次序并且决定执行哪个动作(块904)。冲突解决PI标记被阻碍的分裂动作的模型更新PI标识符(from_MUPI_id)(块905)。在冲突解决PI中，该冲突解决PI对来自模型更新PI的所有候选页分裂动作的局部统计信息进行聚合(块906)。然后，冲突解决PI将树变化(结构和统计信息)应用到该树模型中(块907)。

该机制确定是否到达数据流的终端(块908)。如果到达数据流的终端，那么操作结束(块909)。如果在块908未到达数据流的终端，那么操作返回块901。在数据填充(datafeed)的下一轮，与在通常情况下一样，其标识被标记为from_MUPI_id的模型更新PI不读取新数据而是保持旧数据批次来计算信息增益。唯一的区别是在最后一轮分裂的节点将不再接受数据批次中的实例，称之为这些节点的“关闭阀”。这防止相同的数据在相同的节点被学习多次。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

如上所述，应该理解，示例性实施例可以采取完全的硬件实施例、完全的软件实施例或同时包含硬件和软件元素的实施例的形式。在一个实施例示例中，示例性实施例的机制通过软件或程序代码实现，这些软件或程序代码包括——但不限于——固件、驻留软件、微代码等。

适合于存储和/或执行程序代码的数据处理系统将包括至少一个通过系统总线直接或间接地连接到存储元件的处理器。这些存储元件可以包括在程序代码的实际实现期间采用的本地存储器、大容量存储装置以及提供至少某些程序代码的临时存储以减少必须在执行期间从大容量存储装置检索的次数的高速缓存存储器。

输入/输出或I/O设备(包括——但不限于——键盘、显示器、指点设备等)可以直接地或通过中间I/O控制器连接到系统。网络适配器还可以连接到系统以允许数据处理系统变得通过中间专用或公共网络与其它数据处理系统或远程打印机或存储器件相连。电话调制解调器、电缆调制解调器和以太网只是一些当前可用的网络适配器类型。

出于说明和描述的目的给出了对本发明的描述，但所述描述并非旨在是穷举的或是将本发明限于所公开的形式。对于所属技术领域的普通技术人员来说,许多修改和变化都将是显而易见的。实施例的选择和描述，旨在最佳地解释本发明的原理、实际应用，并且所属技术领域的其它普通技术人员能够理解适合于所构想的特定使用的具有各种修改的各种实施例。