Discriminant Forest Classification Method and System

• US 20090281981A1
• Filed: 05/06/2009
• Published: 11/12/2009
• Est. Priority Date: 05/06/2008
• Status: Active Grant

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Inventors: Mugge, Marshall J., Hiller, Lawrence J., Knapp, David A., Lemmond, Tracy D., Chen, Barry Y., Hanley, William G.
• Granted Patent: US 8,306,942 B2
• Time in Patent Office: Days
• US Class Current: 706/56
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning

Abstract

A hybrid machine learning methodology and system for classification that combines classical random forest (RF) methodology with discriminant analysis (DA) techniques to provide enhanced classification capability. A DA technique which uses feature measurements of an object to predict its class membership, such as linear discriminant analysis (LDA) or Andersen-Bahadur linear discriminant technique (AB), is used to split the data at each node in each of its classification trees to train and grow the trees and the forest. When training is finished, a set of n DA-based decision trees of a discriminant forest is produced for use in predicting the classification of new samples of unknown class.

Claims

1. A hybrid random forest (RF) and discriminant analysis (DA) method of training a computerized system to predict the class membership of a sample of unknown class, comprising:

providing a forest training set to the computerized system comprising N feature vector ({circumflex over (x)}_i) and class label (ŷ

_i) pairs, ({circumflex over (x)}_iε

,ŷ

_iε

{0,1}) for i=1 to N, and from D available features; and

controlling the computerized system to repeat the following set of steps until a desired forest size having n decision trees has been reached;

adding a decision tree to the forest,

creating a tree training set associated with the added decision tree, said tree training set comprising N bootstrapped training samples randomly selected with replacement from the forest training set, and

using the tree training set to train the added decision tree by using hierarchical DA-based decisions to perform splitting of decision nodes and thereby grow the added decision tree as a DA-based decision tree,

whereby, upon reaching the desired forest size, the computerized system may predict the classification of a sample of unknown class using the n DA-based decision trees.

2. The method of claim 1,

wherein the step of using the tree training set to train the added decision tree uses hierarchical Linear Discriminant Analysis (LDA)-based decisions to perform splitting of decision nodes and thereby grow the added decision tree as an LDA-based decision tree.

3. The method of claim 2,

wherein the step of training the added decision tree using hierarchical LDA-based decisions comprises:

creating a root node containing all samples in the tree training set associated with the added decision tree; and

starting with the root node level as a current level, controlling the computerized system to repeat the following set of steps until all decision nodes at the current level are terminal;

(a) for each non-terminal decision node of the current level of the added decision tree;

1. selecting m features at random from. D available features and projecting samples contained by the node onto the m features, where (x_i′

ε

,y_iε

{0,1}) for i=1 to N_node

2. computing LDA coefficients, w and b, over all N_node samples, x_i, contained in the non-terminal decision node projected onto the m features, x_i′

, to form a linear decision boundary, f(x′

)=w^Tx′

+b defined by the LDA coefficients,

3. splitting the samples of the non-terminal decision node (“

parent node”

) into two new decision nodes of a next level (“

child nodes”

) by populating one of the child nodes with the samples of the parent node for which f(x)=w^Tx′

+b≧

0 and the other child node with the samples of the parent node for which f(x′

)=w^Tx′

+b<

0,

(b) for each terminal decision node of the current level of the added decision tree, recording the class of the terminal decision node as positive if its samples lie on the positive side of the linear decision boundary used to split its parent node, and as negative otherwise, and

(c) setting the current level to the level of the child nodes, if any, whereby the added decision tree is grown as a LDA-based decision tree.

4. The method of claim 3, wherein

5. The method of claim 3,

wherein for a large condition number, κ

, greater than a predetermined threshold value, the linear decision boundary is a perpendicular bisector fitted between the class means, where

6. The method of claim 2,

further comprising controlling the computerized system to report statistics associated with the n LDA-based decision trees to a user.

7. The method of claim 2,

further comprising controlling the computerized system to provide the n LDA-based decision trees as machine-readable code capable of being executable by a second computerized system for predicting the classification of a sample of unknown class on the second computerized system.

8. The method of claim 1,

wherein the training of the added decision tree uses hierarchical Anderson-Bahadur Linear Discriminant (AB)-based decisions to perform splitting of decision nodes and thereby grow the added decision tree as an AB-based decision tree.

9. The method of claim 8,

wherein the step of training the added decision tree using hierarchical AB-based decisions comprises:

creating a root node containing all samples in the tree training set associated with the added decision tree; and

starting with the root node level as a current level, controlling the computerized system to repeat the following set of steps until all decision nodes at the current level are terminal;

(a) for each non-terminal decision node of the current level of the added decision tree;

1. selecting m features at random from D available features and projecting samples contained by the node onto the m features, where (x_i′

ε

,y_iε

{0,1}) for i=1 to N_node

2. computing AB coefficients, w and b, over all N_node samples, x_i, contained in the non-terminal decision node projected onto the m features, x_i′

, to form a linear decision boundary, f(x′

)=w^Tx′

+b defined by the AB coefficients,

3. splitting the samples of the non-terminal decision node (“

parent node”

) into two new decision nodes of a next level (“

child nodes”

) by populating one of the child nodes with the samples of the parent node for which f(x′

)=w^Tx′

+b≧

0 and the other child node with the samples of the parent node for which f(x′

)=w^Tx′

+b<

0,

(b) for each terminal decision node of the current level of the added decision tree, recording the class of the terminal decision node as positive if its samples lie on the positive side of the linear decision boundary used to split its parent node, and as negative otherwise, and

(c) setting the current level to the level of the child nodes, if any, whereby the added decision tree is grown as a LDA-based decision tree.

10. The method of claim 9, wherein

11. The method of claim 9,

wherein for a large condition number, κ

, greater than a predetermined threshold value, the linear decision boundary is a perpendicular bisector fitted between the class means, where

12. The method of claim 8,

further comprising controlling the computerized system to report statistics associated with the n AB-based decision trees to a user.

13. The method of claim 8,

further comprising controlling the computerized system to provide the n AB-based decision trees as machine-readable code capable of being executable by a second computerized system for predicting the classification of a sample of unknown class on the second computerized system.

14. A hybrid random forest (RF) and discriminant analysis (DA) method of predicting the classification of a sample of unknown class, comprising:

providing a forest-trained computerized system trained according to claim 1 with n DA-based decision trees;

causing the forest-trained computerized system to;

receive as input one or more samples of unknown class, characterized as sample feature vector(s) x;

for each of the n DA-based decision trees and beginning with the root node of each decision tree,

(a) determining if the current decision node is terminal;

(b) if the current decision node is terminal, assigning x to the class of the current decision node and returning to step (a) for the next decision tree;

(c) if the current decision node is not terminal, computing f(x′

)=w^Tx′

+b for the current decision node, determining if f(x′

) is greater than or equal to 0, selecting the left child node as the new current decision node if f(x′

)≧

0, selecting the right child node as the new current decision node if f(x′

)<

0, and returning to step (a) for the current decision tree;

computing the relative frequency of class assignments for x in the n DA-based decision trees;

based on a predetermined threshold value, determining a final class prediction based on the relative frequency of class assignments in the n DA-based decision trees; and

providing the final class prediction to a user.

15. A hybrid random forest (RF) and discriminant analysis (DA) method-based computerized system for predicting the classification of a sample of unknown class, comprising:

computer input means for receiving one or more samples of unknown class, characterized as sample feature vector(s) x;

computer processor means trained according to claim 1 with n DA-based decision trees, wherein for each of the n DA-based decision trees and beginning with the root node of each decision tree the computer processor means is adapted to;

(a) determine if the current decision node is terminal;

(b) if the current decision node is terminal, assigning x to the class of the current decision node and returning to step (a) for the next decision tree;

(c) if the current decision node is not terminal, computing f(x′

)=w^Tx′

+b for the current decision node, determining if f(x′

) is greater than or equal to 0, selecting the left child node as the new current decision node if f(x′

)≧

0, selecting the right child node as the new current decision node if f(x′

)<

0, and returning to step (a) for the current decision tree;

computer processor means for computing the relative frequency of class assignments for x in the n DA-based decision trees;

computer processor means for, based on a predetermined threshold value, determining a final class prediction based on the relative frequency of class assignments in the n DA-based decision trees; and

computer output means for providing the final class prediction to a user.