Patent ID: 8306942

Claim:
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, where {circumflex over (x)} i ε D and ŷ 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 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, 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, 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 ε m , 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 T x′+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 T x′+b≧0 and the other child node with the samples of the parent node for which f(x′)=w T x′+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.