System for constructing decision tree classifiers using structure-driven induction

• US 6,269,353 B1
• Filed: 11/26/1997
• Issued: 07/31/2001
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• Current Assignee: Mandala Biosciences LLC
• Original Assignee: Ishwar K. Sethi, Jae H. Yoo
• Inventors: Yoo, Jae H., Sethi, Ishwar K.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Khatri, Anil
• Application Number:
  US08/978,681
• Time in Patent Office: 1,343 Days
• Field of Search: 706/15, 706/16, 706/20, 706/25, 706/45-47, 706/55, 706/56, 706/52
• US Class Current: 706/20
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 3/02 Neural networks

Abstract

A computer-implemented apparatus and method for designing decision tree classifiers for use in artificial applications. A tree structure of fixed size with empty internal nodes, i.e. nodes without any splitting function, and labeled terminal nodes is first constructed. Using a collection of training vectors of known classification, a neural learning scheme combining backpropagation and soft competitive learning is then used to simultaneously determine the splits for each decision tree node. Compact trees are generated that have multifeature splits at each internal node which are determined on global rather than local basis. The computer-implemented apparatus and method consequently produces decision trees yielding better classification and interpretation of the underlying relationships in the data.

Claims

1. A computer-implemented method for constructing a decision tree for computer-implemented information processing, comprising the steps of:

constructing a tree structure of a predetermined size with empty internal nodes, including at least one terminal node and at least one internal node;

using training vectors of predetermined classification to substantially simultaneously determine splits for each decision tree node, wherein;

(a) said training vectors include a back propagation component that determines said splits for each internal node, and

(b) said training vectors include a competitive learning component that controls the number of terminal nodes thereby determining the effective size of said decision tree.

2. The computer-implemented method of claim 1 further comprising the step of:

using a computer-implemented neural learning scheme to determine the splits for each internal node through back propagation and to control the number of terminal nodes through competitive learning.

3. The computer-implemented method of claim 1 further comprising the step of:

generating a map between components of a neural network and the nodes of the decision tree for use in constructing the decision tree.

4. The computer-implemented method of claim 1 further comprising the steps of:

generating the training vectors through the neural network;

transforming a plurality of the neural network components into nodes of the decision tree based upon the generated map.

5. A computer-implemented apparatus for constructing a decision tree for computer-implemented information processing, comprising:

a tree structure data structure of a predetermined size with empty internal nodes, including at least one terminal node and at least one internal node;

a neural network for generating training vectors,

said training vectors include a back propagation component that determines said splits for each internal node, and

said training vectors include a competitive learning component that controls the number of terminal nodes thereby determining the effective size of said decision tree.

6. The computer-implemented apparatus of claim 5 further comprising:

a computer-implemented neural learning scheme to determine the splits for each internal node through back propagation and to control the number of terminal nodes through competitive learning.

7. The computer-implemented apparatus of claim 5 further comprising:

a map between components of a neural network and the nodes of the decision tree for use in constructing the decision tree.