System and method for building decision trees in a database
Decision trees are efficiently represented in a relational database. A computer-implemented method of representing a decision tree model in relational form comprises providing a directed acyclic graph comprising a plurality of nodes and a plurality of links, each link connecting a plurality of nodes, encoding a tree structure by including in each node a parent-child relationship of the node with other nodes, encoding in each node information relating to a split represented by the node, the split information including a splitting predictor and a split value, and encoding in each node a target histogram.
1. A computer-implemented method of representing a decision tree data mining model in relational form comprising:
accepting a structured query language query referencing a table function, the table function implemented inside a Relational Database Management System and the table function encapsulating creating a decision tree data mining model based on at least one input dataset that is output from at least a portion of the query, wherein the table function receives the input dataset and directly forms a decision tree data mining model, said decision tree data mining model being created, stored and applied inside a database within said Relational Database Management System, wherein application of said decision tree data mining model does not require moving a dataset to a separate data mining engine, by performing steps that are encapsulated in the table function comprising:
processing the at least one input dataset to the table function;
logically providing a directed acyclic graph based on the at least one input dataset comprising a plurality of nodes and a plurality of links, each link connecting said plurality of nodes;
encoding a tree structure by including in each node a parent-child relationship of the node with other nodes;
encoding in each node information relating to a split represented by the node, the split information including a splitting predictor and a split value or values; and encoding in each node a target histogram; and
generating an output of the directed acyclic graph to form the decision tree data mining model.
2. The method of claim 1 , further comprising: encoding in each node surrogate split information including a surrogate splitting predictor and a split value.
3. The method of claim 1 , further comprising:
encoding in each node cost values used for pruning the decision tree data mining model.
4. The method of claim 1 , further comprising:
encoding binning partitions.
5. The method of claim 1 , further comprising:
encoding in each node:
an identifier of the node;
an identifier of a parent node;
an indicator of a split number of the split represented by the node; an indicator of a quality of the split represented by the node; an identifier of a splitting attribute; and
information relating to at least one value of the split represented by the node.
6. The method of claim 5 , wherein the split represented by the node is a numerical split and the information relating to the value of the split represented by the node comprises a high value and a low value.
7. The method of claim 5 , wherein the split represented by the node is a categorical split and the information relating to the value of the split represented by the node comprises a set of categorical attribute values.
8. The method of claim 1 , further comprising:
encoding the decision tree data mining model in tabular format within the database.
9. A database system 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 represent a decision tree data mining model in relational form by:
accepting a structured query language query referencing a table function, the table function implemented inside a Relational Database Management System and the table function encapsulating creating a decision tree data mining model based on at least one input dataset that is output from at least a portion of the query, wherein the table function receives the input dataset and directly forms a decision tree data mining model, said decision tree data mining model being created, stored and applied inside a database within said Relational Database Management System, wherein application of said decision tree data mining model does not require moving a dataset to a separate data mining engine, by performing steps that are encapsulated in the table function comprising:
processing the at least one input dataset to the table function;
logically providing a directed acyclic graph based on the at least one input dataset comprising a plurality of nodes and a plurality of links, each link connecting said plurality of nodes;
encoding a tree structure by including in each node a parent-child relationship of the node with other nodes; and
encoding in each node information relating to a split represented by the node, the split information including a splitting predictor and a split value or values; and encoding in each node a target histogram to form the decision tree data mining model.
10. The system of claim 9 , further comprising: encoding in each node surrogate split information including a surrogate splitting predictor and a split value.
11. The system of claim 9 , further comprising:
encoding in each node cost values used for pruning the decision tree data mining model.
12. The system of claim 9 , further comprising:
encoding binning partitions.
13. The system of claim 9 , further comprising:
encoding in each node:
an identifier of the node;
an identifier of a parent node;
an indicator of a split number of the split represented by the node; an indicator of a quality of the split represented by the node; an identifier of a splitting attribute; and
information relating to at least one value of the split represented by the node.
14. The system of claim 13 , wherein the split represented by the node is a numerical split and the information relating to the value of the split represented by the node comprises a high value and a low value.
15. The system of claim 13 , wherein the split represented by the node is a categorical split and the information relating to the value of the split represented by the node comprises a set of categorical attribute values.
16. The system of claim 9 , further comprising:
encoding the decision tree data mining model in tabular format within the database.
17. A computer program product comprising:
a computer readable storage medium; and
computer program instructions, recorded on the computer readable storage medium, executable by a processor, for representing a decision tree data mining model in relational form by:
accepting a structured query language query referencing a table function, the table function implemented inside a Relational Database Management System and the table function encapsulating creating a decision tree data mining model based on at least one input dataset that is output from at least a portion of the query, wherein the table function receives the input dataset and directly forms a decision tree data mining model, said decision tree data mining model being created, stored and applied inside a database within said Relational Database Management System, wherein application of said decision tree data mining model does not require moving a dataset to a separate data mining engine, by performing steps that are encapsulated in the table function comprising:
processing the at least one input dataset to the table function;
logically providing a directed acyclic graph based on the at least one input dataset comprising a plurality of nodes and a plurality of links, each link connecting said plurality of nodes;
encoding a tree structure by including in each node a parent-child relationship of the node with other nodes; and
encoding in each node information relating to a split represented by the node, the split information including a splitting predictor and a split value or values; and encoding in each node a target histogram to form the decision tree data mining model.
18. The computer program product of claim 17 , further comprising: encoding in each node surrogate split information including a surrogate splitting predictor and a split value.
19. The computer program product of claim 17 , further comprising:
encoding in each node cost values used for pruning the decision tree data mining model.
20. The computer program product of claim 17 , further comprising:
encoding binning partitions.
21. The computer program product of claim 17 , further comprising: encoding in each node:
an identifier of the node;
an identifier of a parent node;
an indicator of a split number of the split represented by the node; an indicator of a quality of the split represented by the node; an identifier of a splitting attribute; and
information relating to at least one value of the split represented by the node.
22. The computer program product of claim 21 , wherein the split represented by the node is a numerical split and the information relating to the value of the split represented by the node comprises a high value and a low value.
23. The computer program product of claim 21 , wherein the split represented by the node is a categorical split and the information relating to the value of the split represented by the node comprises a set of categorical attribute values.
24. The computer program product of claim 17 , further comprising:
encoding the decision tree data mining model in tabular format within the database.
25. A representation of a decision tree data mining model comprising:
a directed acyclic graph stored in a memory of a computer-implemented database system, the graph comprising:
a plurality of nodes and a plurality of links, each link connecting said plurality of nodes;
a tree structure in each node indicating a parent-child relationship of the node with other nodes;
information in each node relating to a split represented by the node, the split information including a splitting predictor and at least one split value; and a target histogram in each node;
wherein the representation of the decision tree data mining model is generated by accepting a structured query language query referencing a table function, the table function implemented inside a Relational Database Management System and the table function encapsulating creating a decision tree data mining model based on at least one input dataset that is output from at least a portion of the query, wherein the table function receives the input dataset and directly forms a decision tree data mining model, said decision tree data mining model being created, stored and applied inside a database within said Relational Database Management System, wherein application of said decision tree data mining model does not require moving a dataset to a separate data mining engine, by performing processing steps that are encapsulated in the table function.
26. The representation of claim 25 , further comprising: surrogate split information in each node including a surrogate splitting predictor and a split value.
27. The representation of claim 25 , further comprising: cost values in each node used for pruning the decision tree data mining model.
28. The representation of claim 25 , further comprising:
binning partitions.
29. The representation of claim 25 , further comprising, in each node: an identifier of the node; an identifier of a parent node;
an indicator of a split number of the split represented by the node; an indicator of a quality of the split represented by the node; an identifier of a splitting attribute; and
information relating to at least one value of the split represented by the node.
30. The representation of claim 29 , wherein the split represented by the node is a numerical split and the information relating to the value of the split represented by the node comprises a high value and a low value.
31. The representation of claim 29 , wherein the split represented by the node is a categorical split and the information relating to the value of the split represented by the node comprises a set of categorical attribute values.
32. The representation of claim 29 , wherein the decision tree data mining model is encoded in tabular format within the database.