Method for constructing segmentation-based predictive models

• US 7,451,065 B2
• Filed: 03/11/2002
• Issued: 11/11/2008
• Est. Priority Date: 03/11/2002
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Natarajan, Ramesh, Pednault, Edwin Peter Dawson
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): OSBORNE, LUKE R
• Application Number:
  US10/096,474
• Publication Number:
  US 20030176931A1
• Time in Patent Office: 2,437 Days
• Field of Search: 703/2, 707/101, 707/103.R
• US Class Current: 703/2
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The present invention generally relates to computer databases and, more particularly, to data mining and knowledge discovery. The invention specifically relates to a method for constructing segmentation-based predictive models, such as decision-tree classifiers, wherein data records are partitioned into a plurality of segments and separate predictive models are constructed for each segment. The present invention contemplates a computerized method for automatically building segmentation-based predictive models that substantially improves upon the modeling capabilities of decision trees and related technologies, and that automatically produces models that are competitive with, if not better than, those produced by data analysts and applied statisticians using traditional, labor-intensive statistical techniques. The invention achieves these properties by performing segmentation and multivariate statistical modeling within each segment simultaneously. Segments are constructed so as to maximize the accuracies of the predictive models within each segment. Simultaneously, the multivariate statistical models within each segment are refined so as to maximize their respective predictive accuracies.

Claims

1. A method for a process performed on a computer for constructing segmentation-based predictive models, the method comprising:

1) accessing a collection of training data records comprising examples of input values that are available to the segmentation-based predictive model, together with corresponding desired output value(s) that the segmentation-based predictive model is intended to predict;

2) generating a plurality of data segments defined by tests on some, all, or none of the available inputs, and generating one or more segment models for each generated data segment, the generation method comprising;

a) for at least one generated data segment, generating a plurality of candidate data segments and associated segments models, wherein at least one segment model for at least one candidate data segment comprises a multivariate segment model; and

b) selecting, from among the plurality of candidate data segments and associated segments models for that generated data segment, a best candidate data segment and at least one associated segment model that optimizes a degree of fit measure with respect to the segment models associated with the candidate segment models; and

3) pruning the plurality of generated data segments and associated segment models by selecting a subset of generated data segments, together with one generated segment model for each data segment selected, so as to optimize a predictive accuracy of the resulting segmentation-based predictive model.

2. The method of claim 1, wherein said generating said plurality of data segments comprises at least one of:

a top-down decision-tree-like segmentation;

a bottom-up agglomerative-clustering-like segmentation;

a hybrid of said top-down decision-tree-like segmentation and said bottom-up agglomerative-clustering-like segmentation; and

a nearest-neighbor approach wherein a new data segment is defined based on a shortest distance between sets of seed records.

3. The method of claim 1, wherein an object-oriented embodiment is used for a module executing at least one of:

said generating said segments;

said generating said segment model; and

said pruning.

4. The method of claim 1, wherein said generating of the plurality of associated segments models comprises:

varying degrees of freedom of a segment model.

5. The method of claim 1, wherein said pruning so as to optimize the predictive accuracy of the resulting segmentation-based predictive model comprises:

simultaneously considering both a number of generated data segments and degrees of freedom of the generated segment models.

6. The method of claim 1, wherein said pruning comprises:

selecting a subset of tree nodes and alternative models for each selected node so as to minimize a sum of said degrees of fit.

7. The method of claim 6, wherein said degrees of fit comprise statistical confidence intervals for true expected values of said degrees of fit and said selecting further comprises consideration of upper confidence bounds for said true expected values.

8. The method of claim 4, wherein optimum degrees of freedom are determined using said training data alone and holdout validation data is used for making a globally optimal choice among alternative segmentations and segment models.

9. The method of claim 1, wherein said selecting of alternative segment models is based upon only said training data, said selecting of alternative segment models comprising one of:

a cross validation of said training data; and

Bayesian scores as a measure of degree of fit.

10. The method of claim 2, wherein said generating said plurality of data segments comprises at least one constraint placed on how said data segments are generated.

11. A digital processing apparatus configured with a program of machine-readable instructions to perform the method of claim 1.

12. A method for a process performed on a computer for constructing segmentation-based predictive models, the method comprising:

generating a plurality of data segments from training data;

generating one or more segment models for each generated data segment, wherein, for at least one generated data segment, a plurality of candidate data segments and associated segments models are generated and at least one segment model for at least one candidate data segment comprises a multivariate segment model; and

selecting, from said plurality of candidate data segments, data segments for a predictive model, as based on which associated segments'"'"' models best fit said training data in view of;

varying a number of said data segments; and

using different degrees of freedom for a multivariate modeling.