Binning predictors using per-predictor trees and MDL pruning

A method of generating a decision tree model comprising:

• generating a plurality of bitmaps in a database system, the bitmaps generated from data stored in a database table in the database system, the database table comprising a plurality of rows of data, the plurality of bitmaps comprising a bitmap for each unique value of each predictor and target and indicating whether or not that unique value of each predictor and target is present in each row of the database table;
• binning values of at least one predictor;
• counting predictor-target pairs for each combination of binned predictor value and target value using the bitmaps;
• determining a splitter value for the data in the database table using the counts of the predictor-target pairs so as to split the data in the database table into a plurality of child nodes, each child node comprising a portion of the data in the database table;
• generating child bitmaps for the data in each child node;
• and
• recursively counting predictor-target pairs for each child node using the bitmaps, determining a splitter value for the data in each child node so as to split each child node into a plurality of new child nodes, and generating child bitmaps for the data in each new child node;
• whereby a decision tree model is formed.

A database system for performing data mining modeling comprising:

• a processor operable to execute computer program instructions;
• a memory operable to store computer program instructions executable by the processor and operable to store data in a database table in the database system, the data mining modeling having selected at least one predictor and one target for the data, the data including a plurality of values of the predictor and a plurality of values of the target, and
• computer program instructions stored in the memory and executable to perform the steps of:
• constructing a binary tree for the predictor that splits the values of the predictor into a plurality of portions;
• pruning the binary tree;
• and
• defining as bins of the predictor leaves of the tree that remain after pruning, each leaf of the tree representing a portion of the values of the predictor.

A system for generating a decision tree model comprising:

• a processor operable to execute computer program instructions;
• a memory operable to store computer program instructions executable by the processor;
• and
• computer program instructions stored in the memory and executable to perform the steps of:
• generating a plurality of bitmaps in a database system, the bitmaps generated from data stored in a database table in the database system, the database table comprising a plurality of rows of data, the plurality of bitmaps comprising a bitmap for each unique value of each predictor and target and indicating whether or not that unique value of each predictor and target is present in each row of the database table;
• binning values of at least one predictor;
• counting predictor-target pairs for each combination of binned predictor value and target value using the bitmaps;
• determining a splitter value for the data in the database table using the counts of the predictor-target pairs so as to split the data in the database table into a plurality of child nodes, each child node comprising a portion of the data in the database table;
• generating child bitmaps for the data in each child node;
• and
• recursively counting predictor-target pairs for each child node using the bitmaps, determining a splitter value for the data in each child node so as to split each child node into a plurality of new child nodes, and generating child bitmaps for the data in each new child node;
• whereby a decision tree model is formed.

A computer program product for binning data in a database for data mining modeling in a database system, the data stored in a database table in the database system, the data mining modeling having selected at least one predictor and one target for the data, the data including a plurality of values of the predictor and a plurality of values of the target, the computer program product comprising:

• a computer readable medium;
• computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of
• constructing a binary tree for the predictor that splits the values of the predictor into a plurality of portions;
• pruning the binary tree;
• and
• defining as bins of the predictor leaves of the tree that remain after pruning, each leaf of the tree representing a portion of the values of the predictor.

A computer program product for generating a decision tree model comprising:

• a computer readable medium;
• computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of
• generating a plurality of bitmaps in a database system, the bitmaps generated from data stored in a database table in the database system, the database table comprising a plurality of rows of data, the plurality of bitmaps comprising a bitmap for each unique value of each predictor and target and indicating whether or not that unique value of each predictor and target is present in each row of the database table;
• binning values of at least one predictor;
• counting predictor-target pairs for each combination of binned predictor value and target value using the bitmaps;
• determining a splitter value for the data in the database table using the counts of the predictor-target pairs so as to split the data in the database table into a plurality of child nodes, each child node comprising a portion of the data in the database table;
• generating child bitmaps for the data in each child node;
• and
• recursively counting predictor-target pairs for each child node using the bitmaps, determining a splitter value for the data in each child node so as to split each child node into a plurality of new child nodes, and generating child bitmaps for the data in each new child node;
• whereby a decision tree model is formed.