US 2015/0032674 A1Published application

Parallel decision or regression tree growing

AssigneeInternational Business Machines Corporation

InventorsPawel Cichosz, Mieczyslaw Klopotek, Krzysztof Skowronski

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments relate to growing a plurality of trees in parallel. An aspect includes creating, for each of a plurality of trees, a data bag based on a training data set comprising a plurality of data records. Another aspect includes splitting the training data set into disjoint data sub-sets; and storing each of the sub-sets in a respective data slice. Another aspect includes performing a single pass through the data records stored in a data slice, thereby identifying one or more of the current nodes that are assigned data records; calculating an intermediate result for each identified current node based on all data records of said data slice; and merging intermediate results into a combined intermediate result. Another aspect includes, for each of the current nodes: calculating a split criterion from the combined intermediate result; and creating two or more child nodes of the current node based on the split criterion.

Claims20

Dependent claims

A computer implemented method for growing a plurality of decision or regression trees in parallel, the method comprising:

creating, for each of a plurality of trees to be grown, a data bag, each data bag being a derivative of a training data set, the training data set comprising a plurality of data records, the data bags acting as data basis for a respective one of the trees to be grown in a database management system that is in control of a plurality of processing units and of a plurality of data slices, the database management system being operable to process data stored in any one of the data slices by a respective one of the processing units;
splitting the training data set into disjoint data sub-sets, each sub-set comprising zero, one or more of the data records of each of the data bags;
storing each of the sub-sets in a respective one of the data slices;
for each one of the plurality of trees to be grown, creating a respective root node;
for each one of the data bags, assigning its data records to the root node of the tree to be grown on said data bag;
and
growing each of the plurality of trees by:
designating the root node as a set of current nodes;
for each one of the data slices in parallel, by a respective one of the processing units, performing a single pass through the data records stored in said data slice, thereby identifying one or more of the current nodes having assigned one or more of the data records in said data slice, the identified current nodes belonging to one or more of the trees, and calculating an intermediate result for each of said identified current nodes based on all data records of said data slice assigned to said current node;
merging, for each of the identified current nodes, any intermediate results that were calculated for said current node, into a combined intermediate result for said current node;
and
for each one of the current nodes:
calculating a split criterion from the combined intermediate result of said current node;
creating two or more child nodes of the current node based on the calculated split criterion;
dividing the data records assigned to the current node in dependence on the split criterion;
de-assigning each one of the data records from the current node and assigning said data record to one of the child nodes according to said division;
and
designating the child nodes that were generated by the data-slice-parallel execution as the set of current nodes.

15 more elements

A computer program product for growing a plurality of decision or regression trees, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing circuit to cause the processing circuit to:

create, for each of a plurality of trees to be grown, a data bag, each data bag being a derivative of a training data set, the training data set comprising a plurality of data records, the data bags acting as data basis for a respective one of the trees to be grown in a database management system that is in control of a plurality of processing units and of a plurality of data slices, the database management system being operable to process data stored in any one of the data slices by a respective one of the processing units;
split the training data set into disjoint data sub-sets, each sub-set comprising zero, one or more of the data records of each of the data bags;
store each of the sub-sets in a respective one of the data slices;
for each one of the plurality of trees to be grown, create a respective root node;
for each one of the data bags, assign its data records to the root node of the tree to be grown on said data bag;
and
grow each of the plurality of trees by:
designating the root node as a set of current nodes;
for each one of the data slices in parallel, by a respective one of the processing units, performing a single pass through the data records stored in said data slice, thereby identifying one or more of the current nodes having assigned one or more of the data records in said data slice, the identified current nodes belonging to one or more of the trees, and calculating an intermediate result for each of said identified current nodes based on all data records of said data slice assigned to said current node;
merging, for each of the identified current nodes, any intermediate results that were calculated for said current node, into a combined intermediate result for said current node;
and
for each one of the current nodes:
calculating a split criterion from the combined intermediate result of said current node;
creating two or more child nodes of the current node based on the calculated split criterion;
dividing the data records assigned to the current node in dependence on the split criterion;
de-assigning each one of the data records from the current node and assigning said data record to one of the child nodes according to said division;
and
designating the child nodes that were generated by the data-slice-parallel execution as the set of current nodes.

15 more elements

A computer system for growing a plurality of decision or regression trees in parallel, the system comprising:

a memory;
and
a processor, communicatively coupled to said memory, the computer system configured to perform a method comprising:
creating, for each of a plurality of trees to be grown, a data bag, each data bag being a derivative of a training data set, the training data set comprising a plurality of data records, the data bags acting as data basis for a respective one of the trees to be grown in a database management system that is in control of a plurality of processing units and of a plurality of data slices, the database management system being operable to process data stored in any one of the data slices by a respective one of the processing units;
splitting the training data set into disjoint data sub-sets, each sub-set comprising zero, one or more of the data records of each of the data bags;
storing each of the sub-sets in a respective one of the data slices;
for each one of the plurality of trees to be grown, creating a respective root node;
for each one of the data bags, assigning its data records to the root node of the tree to be grown on said data bag;
and
growing each of the plurality of trees by:
designating the root node as a set of current nodes;
for each one of the data slices in parallel, by a respective one of the processing units, performing a single pass through the data records stored in said data slice, thereby identifying one or more of the current nodes having assigned one or more of the data records in said data slice, the identified current nodes belonging to one or more of the trees, and calculating an intermediate result for each of said identified current nodes based on all data records of said data slice assigned to said current node;
merging, for each of the identified current nodes, any intermediate results that were calculated for said current node, into a combined intermediate result for said current node;
and
for each one of the current nodes:
calculating a split criterion from the combined intermediate result of said current node;
creating two or more child nodes of the current node based on the calculated split criterion;
dividing the data records assigned to the current node in dependence on the split criterion;
de-assigning each one of the data records from the current node and assigning said data record to one of the child nodes according to said division;
and
designating the child nodes that were generated by the data-slice-parallel execution as the set of current nodes.

18 more elements

Dependencies are inferred from the claim text.