Segmenting information records with missing values using multiple partition trees

• US 20020174088A1
• Filed: 05/07/2001
• Published: 11/21/2002
• Est. Priority Date: 05/07/2001
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Liu, Tongwei, Beyer, Dirk M.
• Application Number:
  US09/851,066
• Publication Number:
  US 20020174088A1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A method and system for predicting the class membership of a record where information for one or more variables in the record is missing. Multiple classification trees are generated. A first classification tree is computed using a substantially complete set of information for all of the variables. Other classification trees are computed for different subsets of the variables. Variables are selected for inclusion in a subset based on how strongly they influence the prediction of class membership. The first classification tree (based on the substantially complete set of information) is applied to a record with missing information. If missing information is needed by this tree in order to classify the record, another classification tree that is not based on the missing variable is selected. The class membership for a record with information missing is predicted more accurately without substantially increasing the complexity of the prediction.

Claims

1. A method for classifying an information record when said record is incomplete, said method comprising the steps of:

a) receiving a record comprising a plurality of variables, wherein said record comprises information for a first portion of said variables and wherein information for a second portion of said variables is incomplete;

b) using a first classification tool to classify said record according to said information from said first portion of said variables; and

c) using a second classification tool to classify said record when said first classification tool requires a particular item of information that is missing from said second portion of said variables.

2. The method as recited in claim 1 wherein said first classification tool and said second classification tool are a first classification tree and a second classification tree, respectively.

3. The method as recited in claim 2 wherein said first classification tree is computed using a substantially complete set of information for said plurality of variables and wherein said second classification tree is computed using information for a subset of said plurality of variables, wherein said subset does not include said particular item of information that is missing.

4. The method as recited in claim 3 further comprising the steps of:

ranking said plurality of variables according to their respective influence on said classifying; and

grouping said plurality of variables into subsets of variables using said ranking.

5. The method as recited in claim 4 comprising the step of:

computing a classification tree for each one of said subsets.

6. The method as recited in claim 1 wherein said record comprises customer information for a client, wherein content is selected for delivery to a customer according to said classifying of said record.

7. The method as recited in claim 1 comprising the step of:

substituting a default value for said particular item of information that is missing.

8. A computer system comprising:

a bus;

a memory unit coupled to said bus; and

a processor coupled to said bus, said processor for executing a method for classifying an information record when said record is incomplete, said method comprising the steps of;

a) receiving a record comprising a plurality of variables, wherein said record comprises information for a first portion of said variables and wherein information for a second portion of said variables is incomplete;

b) using a first classification tool to classify said record according to said information from said first portion of said variables; and

c) using a second classification tool to classify said record when said first classification tool requires a particular item of information that is missing from said second portion of said variables.

9. The computer system of claim 8 wherein said first classification tool and said second classification tool are a first classification tree and a second classification tree, respectively.

10. The computer system of claim 9 wherein said first classification tree is computed using a substantially complete set of information for said plurality of variables and wherein said second classification tree is computed using information for a subset of said plurality of variables, wherein said subset does not include said particular item of information that is missing.

11. The computer system of claim 10 wherein said method further comprises the steps of:

ranking said plurality of variables according to their respective influence on said classifying; and

grouping said plurality of variables into subsets of variables using said ranking.

12. The computer system of claim 11 wherein said method comprises the step of:

computing a classification tree for each one of said subsets.

13. The computer system of claim 8 wherein said record comprises customer information for a client, wherein content is selected for delivery to a customer according to said classifying of said record.

14. The computer system of claim 8 wherein said method comprises the step of:

substituting a default value for said particular item of information that is missing.

16. The computer-usable medium of claim 15 wherein said first classification tool and said second classification tool are a first classification tree and a second classification tree, respectively.

17. The computer-usable medium of claim 16 wherein said first classification tree is computed using a substantially complete set of information for said plurality of variables and wherein said second classification tree is computed using information for a subset of said plurality of variables, wherein said subset does not include said particular item of information that is missing.

18. The computer-usable medium of claim 17 wherein said computer-readable program code embodied therein causes a computer system to perform the steps of:

ranking said plurality of variables according to their respective influence on a classification of said record; and

grouping said plurality of variables into subsets of variables using said ranking.

19. The computer-usable medium of claim 18 wherein said computer-readable program code embodied therein causes a computer system to perform the steps of:

computing a classification tree for each one of said subsets.

20. The computer-usable medium of claim 15 wherein said record comprises customer information for a client, wherein content is selected for delivery to a customer according to a classification of said record.

21. The computer-usable medium of claim 15 wherein said computer-readable program code embodied therein causes a computer system to perform the steps of:

substituting a default value for said particular item of information that is missing.

15. A computer-usable medium having computer-readable program code embodied therein for causing a computer system to perform the steps of:

a) receiving a record comprising a plurality of variables, wherein said record comprises information for a first portion of said variables and wherein information for a second portion of said variables is incomplete;

b) using a first classification tool to classify said record according to said information from said first portion of said variables; and

c) using a second classification tool to classify said record when said first classification tool requires a particular item of information that is missing from said second portion of said variables.

22. A method for classifying an information record when said record is incomplete, wherein said record comprises a plurality of variables, said method comprising the steps of:

a) ranking said plurality of variables according to their respective influence on said classifying;

b) grouping said plurality of variables into subsets of variables using said ranking, wherein a classification tree is computed for each of said subsets;

c) receiving a record comprising information for a first portion of said variables, wherein information for a second portion of said variables is incomplete;

d) using a first classification tree to classify said record according to said information from said first portion of said variables, wherein said first classification tree is based on a substantially complete set of information for said plurality of variables; and

e) using a second classification tree to classify said record when said first classification tool requires a particular item of information that is missing from said second portion of said variables, wherein said second classification tree is based on information for one of said subsets of variables of said step b), wherein said one of said subsets does not include said particular item of information that is missing.