Decision tree representation for big data

Patent metadata

Field	Value
Publication number	US-9147168-B1
Application number	US-201213722780-A
Country	US
Kind code	B1
Filing date	Dec 20, 2012
Priority date	Dec 20, 2012
Publication date	Sep 29, 2015
Grant date	Sep 29, 2015

Abstract

A method, system, and process for representing a decision tree in a tabular format is discussed. The format may contain all the necessary information to traverse the nodes in parallel on a distributed system while consuming an efficient amount of resources. In some embodiments, the tree may be stored in a relational database as a table.

First claim

What is claimed is:

1. A method for representing a decision tree in a table, comprising:
receiving a training dataset;
building a decision tree from the training dataset, wherein the decision tree comprises a plurality of nodes;
storing each node as an individual row in the table on a non-transitory computer readable medium, wherein the row comprises a leftmost child id, a split criterion value (“SCV”), and a path from a root node;
distributing the decision tree to multiple nodes in a massive parallel processing (“MPP”) database cluster;
receiving a classification dataset to be classified using the decision tree;
dividing the classification dataset into a plurality of segments; and
distributing the segments to the multiple nodes in the MPP database cluster.

2. The method of claim 1 , further comprising assigning each node a node id and storing the node id in the table.

3. The method of claim 1 , further comprising determining the leftmost child id for each node having children and storing the leftmost child id with the node in the table.

4. The method of claim 1 , further comprising determining a predicted class for each node and storing the predicted class in the table.

5. The method of claim 4 , further comprising calculating the probability that a decision made on a node will result in the predicted class, and storing the probability in the table.

6. The method of claim 1 , further comprising calculating the SCV for a decision node in the decision tree and storing the SCV in the table.

7. The method of claim 1 , further comprising storing the path from the root node and storing the path as an array in the table.

8. The method of claim 1 , wherein the training dataset comprises an attribute, an attribute value, and a class value.

9. A computer program product for representing a decision tree in a database, comprising a non-transitory computer readable medium having program instructions embodied therein for:
receiving a training dataset;
building a decision tree from the training dataset, wherein the decision tree comprises a plurality of nodes;
storing each node as an individual row in the table on a non-transitory computer readable medium, wherein the row comprises a leftmost child id, a split criterion value (“SCV”), and a path from a root node;
distributing the decision tree to multiple nodes in a massive parallel processing (“MPP”) database cluster;
receiving a classification dataset to be classified using the decision tree;
dividing the classification dataset into a plurality of segments; and
distributing the segments to the multiple nodes in the MPP database cluster.

10. The computer program product of claim 9 , further comprising assigning each node a node id and storing the node id in the table.

11. The computer program product of claim 9 , further comprising determining the leftmost child id for each node having children and storing the leftmost child id with the node in the table.

12. The computer program product of claim 9 , further comprising determining a predicted class for each node and storing the predicted class in the table.

13. The computer program product of claim 12 , further comprising calculating the probability that a decision made on a node will result in the predicted class, and storing the probability in the table.

14. The computer program product of claim 9 , further comprising the SCV for a decision node in the decision tree and storing the SCV in the table.

15. The computer program product of claim 9 , further comprising storing the path from a root node to each node and storing the path as an array in the table.

16. The computer program product of claim 9 , wherein the training dataset comprises an attribute, an attribute value, and a class value.

17. A system for representing a decision tree in a database comprising a non-transitory computer readable medium and a processor configured to:
receive a training dataset;
build a decision tree from the training dataset, wherein the decision tree comprises a plurality of nodes;
store each node as an individual row in the table on a non-transitory computer readable medium, wherein the row comprises a leftmost child id, a split criterion value (“SCV”), and a path from a root node;
distribute the decision tree to multiple nodes in a massive parallel processing (“MPP”) database cluster;
receive a classification dataset to be classified using the decision tree;
divide the classification dataset into a plurality of segments; and
distribute the segments to the multiple nodes in the MPP database cluster.

18. The system of claim 17 , further comprising determining the leftmost child id for each node having children and storing the leftmost child id with the node in the table.

19. The system of claim 17 , further comprising determining a predicted class for each node and storing the predicted class in the table.

20. The system of claim 19 , further comprising calculating the probability that a decision made on a node will result in the predicted class, and storing the probability in the table.

Assignees

• Emc Corp

Inventors

• Ao Jianwang
• Ren Yi
• Yang Guangxin
• Welton Caleb

Classifications

• G06F16/9027

  Trees · CPC title

• G06N99/005 Primary

  Physics · mapped topic

• G06N20/00 Primary

  Machine learning · CPC title

• G06N20/20

  Ensemble learning · CPC title