System and method for efficiently generating models for targeting products and promotions using classification method by choosing points to be labeled

• US 6,937,994 B1
• Filed: 05/16/2000
• Issued: 08/30/2005
• Est. Priority Date: 02/24/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Vijay Sourirajan
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Heck, Michael C.
• Application Number:
  US09/571,917
• Time in Patent Office: 1,932 Days
• Field of Search: 705/10, 706/925, 706/20
• US Class Current: 705/7.29
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

A closed loop system is presented for selecting samples for labeling so that they can be used to generate classifiers. The sampling is done in phases. In each phase a subset of samples are chosen using information collected in previous phases and the classification model that has been generated up to that point. The total number of samples and the number of phases can be chosen by the user.

Claims

1. A method of using a computer for targeting products and promotions to candidate sets of customers having attributes, said method iteratively implementing phases with each phase comprising the steps of:

a) storing unlabeled customer data in a storage device, each unlabeled customer data having one or more customer attributes;

b) implementing a means for selecting a subset of unlabeled customer data from said storage device, said selecting means responsive to received guessed labels generated for unlabeled customer data instances in said selected subset according to a first classification method and, further responsive to weights computed for unlabeled data instances using said guessed labels;

c) implementing a means for labeling the selected subset of unlabeled customer data using external information and adding said labeled data subset to a labeled data set, said labeled data set comprising one or more labeled data instances;

d) implementing a model generator device for retrieving said labeled data set and generating one or more classification models, said customer classification model generating comprising steps of;

i) initializing an iteration index r;

ii) initializing a first set of probabilities for each labeled instance in said labeled data set;

iii) choosing a sample S(r) of labeled instances from the labeled data set using said probabilities;

iv) generating a classification model M(r) for data in S(r) using said second classification method;

v) applying said classification model M(r) to the entire labeled data set;

vi) computing a second set of probabilities for including each instance;

vii) incrementing said iteration index r;

viii) repeating steps iii)–

vii) until a predetermined termination criterion is satisfied;

f) applying one or more generated classification models M(r) and said guessed labels for unlabeled data instances to compute said weights in step b); and

utilizing said weights for selecting a next subset from remaining unlabeled data stored in said storage device in a subsequent phase; and

,

g) repeating step b) through f) in each phase until a termination criterion is satisfied; and

h) implementing a device for combining each of said generated one or more classification models M(r) into a resultant classifier model, said resultant classifier model adapted to determine suitability of potential customers for receiving targeted products and promotions, wherein said resultant classifier model is based on a reduced amount of labeled data set instances with increased classification accuracy.

2. The method as claimed in claim 1, wherein said labeling step c) is performed manually.

3. The method as claimed in claim 1, wherein said selecting step b) comprises the steps of:

normalizing the computed weights to obtain a probability measure;

utilizing said probability measure to select said subset of one or more instances from said set of unlabeled data; and

,

repeating the steps of normalizing and utilizing until a number of instances for said subset have been selected.

4. The method as claimed in claim 3, wherein said selecting step b) further comprises the step of resetting the weight utilized for the selected instance for each repeated normalizing and utilizing iteration.

5. The method as claimed in claim 1, wherein said selecting step b) comprises the steps of:

sorting instances in said unlabeled data set by weight; and

,

selecting a subset having instances with the greatest weights.

6. The method as claimed in claim 1, wherein a termination criterion is based on a final size of the labeled data set, a predetermined total number of phases and a final size of the labeled set being user specified,

whereby said number of instances to be selected in each subset for each phase is computed as a ratio of said final size to said total number of phases.

7. The method as claimed in claim 1, wherein a number of instances for each subset is user specified.

8. The method as claimed in claim 1, wherein said first classification method employed in step d) implements a nearest neighbor classification algorithm using said one or more attributes.

9. The method as claimed in method of claim 1, wherein said computing step f) includes the step of estimating a cumulative error cumul(i) for each instance i in said unlabeled data set over all said one or more classification models and utilizing said guessed labels generated by said first classification method as a reference.

10. The method as claimed in method of claim 9, wherein after estimating said cumulative error cumul(i), a step of calculating for each instance i in said unlabeled data set a weight(i) according to:

weight(i)=(1+cumul(i)³).

11. The method as claimed in claim 1, wherein said combining step h) comprises the steps of:

applying a chosen subset of classification models from said generated one or more classification models to any data instance; and

,

selecting a dominant class predicted by said classification models as the predicted class for that instance.

12. The method as claimed in claim 11, where said chosen subset of classification models comprises an entire set of generated classification models.

13. The method as claimed in claim 11, where said chosen subset of classification models comprises those one or more classification models that were generated after all the instances have been added to said labeled data set.

14. The method as claimed in claim 1, wherein said classifying step d) includes combining prior generated one or more classification models.

15. The method as claimed in claim 14, further including the step of voting across all models of said generated one or more classification models to combine said models.

16. The method as claimed in claim 1, wherein said initializing step j) includes the step of assigning a uniform distribution for each instances in said labeled data set.

17. The method as claimed in claim 1, wherein said second classification method employed in step l) implements a decision tree classifier.

18. The method as claimed in claim 1, wherein said termination criterion comprises a predetermined upper limit for said index r.

19. The method as claimed in claim 1, wherein said computing step n) comprises utilizing a probability measure prob(i) for each instance i in said second set of probabilities according to:

$\mathrm{prob}<br><br>\left(i\right)=\left(1+{\mathrm{error}<br><br>\left(i\right)}^3\right)/\underset{j}{\sum <br><br>}<br><br>\left(1+{\mathrm{error}<br><br>\left(j\right)}^3\right)$

where error(i) is a cumulative error for each instance i over all said models M(r) and $\underset{j}{\sum <br><br>}<br><br>\left(1+{\mathrm{error}\left(j\right)}^3\right)$

is a cumulative error over all the labeled data j.

20. The method as claimed in claim 1, wherein a resultant labeled data set functions as a training set of data to be used in the generation of other classification models.

21. A closed-loop system for generating a classifier model to be used for marketing applications including the targeting of products and promotions to potential customers, each customer having one or more associated attributes, said closed-loop system comprising:

selector mechanism for iteratively selecting a subset of said customers to which a marketing application is to be targeted from an unlabeled data set, said mechanism sampling a subset of unlabeled data in a first iteration, and selecting further subsets of unlabeled data in subsequent iterations based on computed weights;

mechanism for collecting responses from said customers related to said targeted marketing application at each iteration;

a model generator for receiving collected responses, generating labeled data instances by labeling said customers according to their responses, and building one or more classification models using said one or more attributes for classifying other subsets of potential customers in each iteration based on said labeled data instances, said selector mechanism receiving said one or more classification models and said collected responses for a current iteration and computing a new set of weights for selecting the next subset for the next iteration, said step including utilizing said weights for selecting a next subset from remaining unlabeled data and said weights representing an importance of a subset to be selected in said next iteration, wherein said model generator comprises;

a first classification device for generating guessed labels used for classifying unlabeled data instances in each iteration;

a second classification device employing a decision tree classifier for generating an ensemble comprising said one or more classification models based on selected labeled data instances in each iteration, said selector mechanism further receiving said guessed labels from said first classification device and said ensemble of classification models output from said second classification device for computing a new set of weights; and

,

a device for combining each one or more classification models generated at each iteration into a resultant classifier model after a predetermined condition is satisfied, wherein said resultant classifier model is applied to said potential customers to determine their suitability for receiving said products and promotions of said marketing application.

22. The closed-loop system as claimed in claim 21, wherein said second classification device for generating an ensemble employs adaptive resampling techniques using said one or more attributes.

23. The closed-loop system as claimed in claim 21, wherein said selector mechanism comprises:

mechanism for normalizing the computed weights to obtain a probability measure at each iteration;

mechanism for utilizing said probability measure to select said subset of customers.

24. The closed-loop system as claimed in claim 23, wherein said selector mechanism comprises the step of resetting the weights utilized for selecting said customers at each iteration.

25. The closed-loop system as claimed in claim 21, wherein said selector mechanism comprises a mechanism for sorting instances in said unlabeled data set of customers by weight such that said instances are selected in each iteration with the greatest weight.

26. The closed-loop system as claimed in claim 21, further including mechanism for receiving user input for specifying a total number of iterations and a final size of the labeled set, a number of instances to be selected in each phase being computed as a ratio of said final size to said total number of phases.

27. The closed-loop system as claimed in claim 21, wherein a number of instances for each subset is user specified.

28. The closed-loop system as claimed in claim 21, wherein said first classification device for generating guessed labels implements a nearest neighbor classification algorithm.

29. The closed-loop system as claimed in method of claim 21, wherein said selector mechanism comprises mechanism for estimating a cumulative error cumul(i) for each instance i in the unlabeled data set over all said one or more classification models based on said guessed labels generated by said first classification device as a reference.

30. The closed-loop system as claimed in method of claim 29, wherein said estimating mechanism further calculates for each instance i in said unlabeled data set a weight(i) according to:

weight(i)=(1+cumul(i)³).

31. The closed-loop system as claimed in claim 21, wherein said combining device comprises a mechanism for applying a chosen subset of classification models from said ensemble of one or more generated classification models to any data instance,

whereby a dominant class predicted by said classification models is selected as the predicted class for that instance.

32. The closed-loop system as claimed in claim 31, where said chosen subset of classification models comprises an entire set of generated classification models.

33. The closed-loop system as claimed in claim 31, where said chosen subset of classification models comprises those one or more classification models that were generated after all the instances have been added to said labeled data set.

34. The closed-loop system as claimed in claim 21, wherein said first classification device for generating said guessed labels used for classifying further combines prior generated one or more classification models.

35. The closed-loop system as claimed in claim 34, further including mechanism for voting across all models of said ensemble of generated one or more classification models to combine said models.

36. The closed-loop system as claimed in claim 21, wherein a resultant labeled data set functions as a training set of data to be used in the generation of other classification models.

37. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for iteratively generating a classifier model for classifying data with increased accuracy, said method steps iteratively implementing phases with each phase including the steps of:

a) retrieving a set of unlabeled data, each unlabeled data having one or more attributes;

b) sampling a subset of unlabeled data from said retrieved set in a first iteration, and, selecting a subset from remaining unlabeled data of said retrieved unlabeled data set in each subsequent iteration;

c) labeling the subset of data using external information and transferring said subset of labeled data to a set of labeled data, said labeled data comprising one or more labeled data instances;

d) classifying the unlabeled data in said retrieved set by employing a first classification method to generate guessed labels;

e) generating one or more classification models employing a second classification method, said second classification method performing steps of;

i) initializing an iteration index r;

ii) initializing a firs set of probabilities for each labeled instance in said labeled data set;

iii) choosing a sample S(r) of labeled instances from the labeled data set using said probabilities;

iv) generating a classification model M(r) for data in S(r) using said second classification method;

v) applying said classification model M(r) to the entire labeled data set;

vi) computing a second set of probabilities for including each instance;

vii) imcrementing said iteration index r;

viii) repeating steps iii)–

vii) until a predetermined termination criterion is satisfied;

f) computing weights using said guessed labels and utilizing said weights for selecting a next subset from remaining unlabeled data in step b) in a next iteration;

g) repeating steps b) through f) in each phase until a termination criterion is satisfied; and

h) combining each of said generated one or more classification models into a resultant classifier model, wherein said resultant classifier model is based on a reduced amount of labeled data set instances with increased classification accuracy.

38. The program storage device readable by a machine as claimed in claim 37, wherein said generating step e) employs an adaptive resampling technique using said one or more attribute.

39. The program storage device readable by a machine as claimed in claim 37, wherein said selecting step b) comprises the steps of:

normalizing the computed weights to obtain a probability measure;

utilizing said probability measure to select said subset of one or more instances from said set of unlabeled data; and

,

repeating the steps of normalizing and utilizing until a number of instances for said subset have been selected.

40. The program storage device readable by a machine as claimed in claim 37, wherein said selecting step b) comprises the steps of:

sorting instances in said unlabeled data set by weight; and

,

selecting a subset having instances with the greatest weights.

41. The program storage device readable by a machine as claimed in claim 37, wherein said first classification method employed in step d) implements a nearest neighbor classification algorithm.

42. The program storage device readable by a machine as claimed in method of claim 37, wherein said computing step f) includes the step of estimating a cumulative error cumul(i) for each instance i in said unlabeled data set over all said one or more classification models and utilizing said guessed labels generated by said first classification method as a reference for said estimating.

43. The program storage device readable by a machine as claimed in method of claim 42, wherein after estimating said cumulative error cumul(i), a step of calculating for each instance i in said unlabeled data set a weight(i) according to:

weight(i)=(1+cumul(i)³).

44. The program storage device readable by a machine as claimed in claim 37, wherein said combining step h) comprises the steps of:

applying a chosen subset of classification models from said generated one or more classification models to any data instance; and

,

selecting a dominant class predicted by said classification models as the predicted class for that instance.

45. The program storage device readable by a machine as claimed in claim 37, wherein said initializing step j) includes the step of assigning a uniform distribution for each instance in said labeled data set.

46. The program storage device readable by a machine as claimed in claim 37, wherein said second classification method employed in step l) implements a decision tree classifier.

47. The program storage device readable by a machine as claimed in claim 37, wherein said termination criterion comprises a predetermined upper limit for said index r.

48. The program storage device readable by a machine as claimed in claim 37, wherein said computing step n) comprises utilizing a probability measure prob(i) for each instance i in said second set of probabilities according to:

$\mathrm{prob}<br><br>\left(i\right)=\left(1+{\mathrm{error}<br><br>\left(i\right)}^3\right)/\underset{j}{\sum <br><br>}<br><br>\left(1+{\mathrm{error}<br><br>\left(j\right)}^3\right)$

where error (i) is a cumulative error for each instance i over all said models M(r) and $\underset{j}{\sum <br><br>}<br><br>\left(1+{\mathrm{error}<br><br>\left(j\right)}^3\right)$

is a cumulative error over all the labeled data j.

49. The program storage device readable by a machine as claimed in claim 37, wherein said resultant classifier model is utilized for marketing products and promotions to potential purchasing customers.

50. The program storage device readable by a machine as claimed in claim 37, wherein a resultant labeled data set functions as a training set of data to be used in the generation of other classification models.