AUTOMATED CLUSTERING OF RECORDS, BIASED BY SUPERVISED CLASSIFICATION PROCESSING

• US 20080097820A1
• Filed: 10/18/2006
• Published: 04/24/2008
• Est. Priority Date: 10/18/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Shanbhag, Amit Umesh, Burgess, David A., Ames, Glen Anthony, Koran, Joshua Ethan Miller, Henderson, Nicholas Wayne
• Granted Patent: US 7,849,027 B2
• Time in Patent Office: Days
• US Class Current: 705/7.33
• 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
• CPC Class Codes: G06Q 30/0204 Market segmentation

Abstract

An unsupervised classification approach is improved by imposing some order into the treatment of the records and their attributes, which otherwise would be treated as random variables. A method is provided to identify particular attributes that are most associated with the “good” records within each of the plurality of groups of records within a data set. Based on a supervised scoring method, the records of the data set are processed to indicate their measure of “goodness”. There are various ways by which the records can be processed to indicate a bias during unsupervised clustering processing.

Claims

1. A method of targeting particular service users, wherein characteristics of the users are represented in a plurality of records of a data set, the method comprising:

identifying records of the data set representing users who have exhibited particular desirable characteristics, based on supervised classification processing;

based on identification of the records, processing the records of the data set to indicate a bias for application in unsupervised clustering processing; and

clustering the records, processed to indicate a bias, using the unsupervised clustering process; and

targeting particular service users based on the result of the clustering step.

2. The method of claim 1, wherein:

the step of processing the records to indicate a bias includes replicating particular ones of the records in the data set.

3. The method of claim 2, wherein:

replicating or weighting particular ones of records in the data set includes replicating or weighting particular ones of the records a number of times that is a function of the exhibited particular desirable characteristics represented by the replicated records.

4. The method of claim 1, wherein:

the step of processing the records to indicate a bias includes altering or removing at least one dimension of a data space to which the records correspond.

5. The method of claim 4, wherein:

altering at least one dimension of a data space to which the records correspond includes altering at least one dimension corresponding to one of the particular desirable characteristics.

6. The method of claim 1, wherein:

the step of processing the records to indicate a bias includes deriving a plurality of data subsets, each data subset including a plurality of records such that a relationship between the records of that data subset indicates the bias; and

the clustering step including separately clustering the records of the data subsets using an unsupervised clustering process and combining the clusters to achieve clustering of the records of the data set.

7. The method of claim 6, wherein the data subsets are clustered in a distributed manner on a plurality of computing devices.

8. The method of claim 1, wherein:

targeting particular service users based on the result of the clustering step includes determining a particular cluster of records and targeting the particular service users represented by the records of the determined particular cluster.

9. The method of claim 1, wherein:

the clustering step includes determining a particular clustering among alternate possible clusterings of the records of the data set.

10. The method of claim 9, wherein:

for each possible clustering of records, processing, for each cluster of that possible clustering of records of the data set, a comparison of records of the data set representing users who have exhibited the particular desirable characteristics versus records of the data set representing users who have not exhibited the particular desirable characteristics and, based thereon, determining one of the possible clustering of records to be the particular clustering.

11. The method of claim 10, wherein:

determining the particular clustering of records includes determining which of the possible clustering of records exhibits optimum comparisons for the clusters of that possible clustering.

12. The method of claim 11, wherein:

determining which of the possible clustering of records exhibits optimum comparisons for the clusters of that possible clustering includes, for the comparisons for each possible clustering, considering an overall property of each cluster of that possible clustering.

13. The method of claim 12, wherein:

the overall property of a cluster of a possible clustering includes a number of records of that cluster that exhibit the desirable characteristics.

14. The method of claim 12, wherein:

the overall property of a cluster of a possible clustering includes a number of records of that cluster that do not exhibit the desirable characteristics.

15. The method of claim 1, wherein:

targeting particular service users based on the result of the clustering step includes ranking the clusters of records and, based thereon, determining one or more of the clusters of records and targeting particular service users represented by the records of the determined one or more clusters of records.

16. The method of claim 15, wherein:

ranking the clusters of records includes

for each cluster, comparing records of the data set representing users who have exhibited the particular desirable characteristics versus records of the data set representing users who have not exhibited the particular desirable characteristics; and

processing an indication of results of the records comparing for each cluster, to determine the ranking of the clusters.

17. A computing system configured to execute the method of claim 1.

18. A computer program product for targeting particular service users, wherein characteristics of the users are represented in a plurality of records of a data set, the computer program product comprising at least one computer-readable medium having computer program instructions stored therein which are operable to cause at least one computing device to:

identify records of the data set representing users who have exhibited particular desirable characteristics, based on supervised classification processing;

based on identification of the records, process the records of the data set to indicate a bias for application in unsupervised clustering processing; and

cluster the records, processed to indicate a bias, using the unsupervised clustering process; and

target particular service users based on the result of the clustering step.

19. The computer program product of claim 18, wherein:

the computer program instructions operable to cause the at least one computing device to process the records to indicate a bias include computer program instructions operable to cause the at least one computing device to replicate particular ones of the records in the data set.

20. The computer program product of claim 19, wherein:

the computer program instructions operable to cause the at least one computing device to replicate particular ones of records in the data set includes computer program instructions operable to cause the at least one computing device to replicate or weight particular ones of the records a number of times that is a function of the exhibited particular desirable characteristics represented by the replicated or weighted records.

21. The computer program product of claim 18, wherein:

the computer program instructions operable to cause the at least one computing device to process the records to indicate a bias includes computer program instructions operable to cause the at least one computing device to alter at least one dimension of a data space to which the records correspond.

22. The computer program product of claim 21, wherein:

computer program instructions operable to cause the at least one computing device to alter at least one dimension of a data space to which the records correspond includes computer program instructions operable to cause the at least one computing device to alter at least one dimension corresponding to one of the particular desirable characteristics.

23. The computer program product of claim 18, wherein:

computer program instructions operable to cause the at least one computing device to process the records to indicate a bias includes computer program instructions operable to cause the at least one computing device to derive a plurality of data subsets, each data subset including a plurality of records such that a relationship between the records of that data subset indicates the bias; and

computer program instructions operable to cause the at least one computing device to cluster includes computer program instructions operable to cause the at least one computing device to separately cluster the records of the data subsets using an unsupervised clustering process and combine the clusters to achieve clustering of the records of the data set.

24. The computer program product of claim 23, wherein:

the computer program instructions are operable to cause the at least one computing device to process the data subsets clustered in a distributed manner on a plurality of computing devices.

25. The computer program product of claim 18, wherein:

the computer program instructions operable to cause the at least one computing device to target particular service users based on the result of the clustering includes computer program instructions operable to cause the at least one computing device to determine a particular cluster of records and target the particular service users represented by the records of the determined particular cluster.

26. The computer program product of claim 25, wherein:

the computer program instructions operable to cause the clustering at least one computer device to cause the clustering includes computer program instructions operable to cause the computer to determine a particular clustering among alternate possible clusterings of the records of the data set.

27. The computer program product of claim 26, wherein the computer program instructions operable to cause the at least one computing device to determine the particular clustering includes:

for each possible clustering of records, computer program instructions operable to cause the at least one computing device to process, for each cluster of that possible clustering of records of the data set, a comparison of records of the data set representing users who have exhibited the particular desirable characteristics versus records of the data set representing users who have not exhibited the particular desirable characteristics and, based thereon, to determine one of the possible clustering of records to be the particular clustering.

28. The computer program product of claim 27, wherein:

the computer program instructions operable to cause the at least one computing device to determine the particular clustering of records includes computer program instructions operable to cause the at least one computing device to determine which of the possible clustering of records exhibits optimum comparisons for the clusters of that possible clustering.

29. The computer program product of claim 28, wherein:

the computer program instructions operable to cause the at least one computing device to determine which of the possible clustering of records exhibits optimum comparisons for the clusters of that possible clustering includes, for the comparisons for each possible clustering, computer program instructions operable to cause the at least one computing device to consider an overall property of each cluster of that possible clustering.

30. The computer program product of claim 29, wherein:

the overall property of a cluster of a possible clustering includes a number of records of that cluster that exhibit the desirable characteristics.

31. The computer program product of claim 29, wherein:

the overall property of a cluster of a possible clustering includes a number of records of that cluster that do not exhibit the desirable characteristics.

32. The computer program product of claim 18, wherein:

the computer program instructions operable to cause the at least one computing device to target particular service users based on the result of the clustering step includes computer program instructions operable to cause the at least one computing device to rank the clusters of records and, based thereon, determine one or more of the clusters of records and targeting particular service users represented by the records of the determined one or more clusters of records.

33. The computer program product of claim 32, wherein:

the computer program instructions operable to cause the at least one computing device to rank the clusters of records includes computer program instructions operable to cause the at least one computing device to

for each cluster, comparing records of the data set representing users who have exhibited the particular desirable characteristics versus records of the data set representing users who have not exhibited the particular desirable characteristics; and

process an indication of results of the records comparing for each cluster, to determine the ranking of the clusters.