Method and apparatus for partitioning a plurality of items into groups of similar items in a recommender of such items

• US 6,801,917 B2
• Filed: 11/13/2001
• Issued: 10/05/2004
• Est. Priority Date: 11/13/2001
• Status: Expired due to Term

• Current Assignee: Sisvel S.p.A. (Fineur International S.A.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Kurapati, Kaushal, Gutta, Srinivas
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US10/014,216
• Publication Number:
  US 20030097353A1
• Time in Patent Office: 1,057 Days
• Field of Search: 707/1, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data
• CPC Class Codes: H04N 21/4532 involving end-user characteristics, e.g. viewer profile, preferences monitoring of user activities for profile generation for accessing a video database G06F16/739; user profiles in network data switching protocols H04L67/306; processing of user preferences or user profiles in wireless networks H04W8/18
• CPC Class Codes: H04N 21/454 Content or additional data filtering, e.g. blocking advertisements
• CPC Class Codes: H04N 21/466 Learning process for intelligent management, e.g. learning user preferences for recommending movies services using the results of monitoring in broadcast systems H04H60/61
• CPC Class Codes: H04N 21/4662 characterized by learning algorithms
• CPC Class Codes: H04N 21/4668 for recommending content, e.g. movies
• CPC Class Codes: H04N 7/163 by receiver means only
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus are disclosed for recommending items of interest to a user, such as television program recommendations, before a viewing history or purchase history of the user is available. A third party viewing or purchase history is processed to generate stereotype profiles that reflect the typical patterns of items selected by representative viewers. A user can select the most relevant stereotype(s) from the generated stereotype profiles and thereby initialize his or her profile with the items that are closest to his or her own interests. A clustering routine partitions the third party viewing or purchase history (the data set) into clusters using a k-means clustering algorithm, such that points (e.g., television programs) in one cluster are closer to the mean of that cluster than any other cluster. The value of k is incremented until (i) further incrementing of k does not yield any improvement in the classification accuracy, (ii) a predefined performance threshold is reached, or (iii) an empty cluster is detected.

Claims

1. A method for partitioning a plurality of items into groups of similar items, said plurality of items corresponding to a selection history by at least one third party, said method comprising the steps of:

partitioning said third party selection history into k clusters of said plurality of items, said plurality of items including at least one of programs, content and products;

identifying at least one mean item for each of said k clusters; and

assigning each of said plurality of items to one of said clusters based on a distance metric.

2. The method of claim 1, further comprising the step of incrementing said value of k until a further increment of k does not improve a classification accuracy.

3. The method of claim 1, further comprising the step of incrementing said value of k until a predefined performance threshold is reached.

4. The method of claim 1, further comprising the step of incrementing said value of k until an empty cluster is detected.

5. The method of claim 1, further comprising the step of assigning a label to each of said clusters.

6. The method of claim 5, further comprising the step of receiving a user selection of at least one cluster based on said assigned labels.

7. The method of claim 1, wherein said partitioning step further comprises the step of employing a k-means clustering routine.

8. The method of claim 1, wherein said distance metric is based on a distance between corresponding symbolic feature values of two items based on an overall similarity of classification of all instances for each possible value of said symbolic feature values.

9. The method of claim 8, wherein said distance between symbolic features is computed using a Value Difference Metric (VDM) technique.

10. The method of claim 1, wherein said step of identifying at least one mean item for each of said k clusters further comprises the steps of:

computing a variance for each of said items; and

selecting said at least one item that minimizes said variance as the mean symbolic value.

11. The method of claim 1, wherein said step of identifying at least one mean item for each of said k clusters, J, further comprises the steps of:

computing a variance of each of said clusters, J, for each of said possible symbolic values, x_μ

, for each of said symbolic attributes; and

selecting for each of said symbolic attributes at least one symbolic value, x_μ

, that minimizes said variance as the mean symbolic value.

12. The method of claim 1, wherein said mean is comprised of a plurality of items and wherein said distance metric for a given item in said third party selection history is based on a distance between said given item and each item comprising said mean.

13. A method for partitioning a plurality of items into groups of similar items, said plurality of items corresponding to a selection history by at least one third party, said method comprising the steps of:

partitioning said third party selection history into k clusters of said plurality of items, said plurality of items including at least one of programs, content and products;

identifying at least one mean item for each of said k clusters;

assigning each of said plurality of items to one of said clusters based on a distance metric; and

incrementing said value of k until a predefined condition is satisfied.

14. The method of claim 13, wherein said predefined condition is a further increment of k does not improve a classification accuracy.

15. The method of claim 13, wherein said predefined condition is a predefined performance threshold is reached.

16. The method of claim 13, wherein said predefined condition is detection of an empty cluster.

17. The method of claim 13, wherein said mean is comprised of a plurality of items and wherein said distance metric for a given item in said third party selection history is based on a distance between said given item and each item comprising said mean.

18. A system for partitioning a plurality of items into groups of similar items, said plurality of items corresponding to a selection history by at least one third party, said system comprising:

a memory for storing computer readable code; and

a processor operatively coupled to said memory, said processor configured to;

partition said third party selection history into k clusters of said plurality of items, said plurality of items including at least one of programs, content and products;

identify at least one mean item for each of said k clusters; and

assign each of said plurality of items to one of said clusters based on a distance metric.

19. The system of claim 18, wherein said processor is further configured to increment said value of k until a further increment of k does not improve a classification accuracy.

20. The system of claim 18, wherein said processor is further configured to increment said value of k until a predefined performance threshold is reached.

21. The system of claim 18, wherein said processor is further configured to increment said value of k until an empty cluster is detected.

22. The system of claim 18, wherein said processor is further configured to assign a label to each of said clusters.

23. The system of claim 22, wherein said processor is further configured to receive a user selection of at least one cluster based on said assigned labels.

24. The system of claim 18, wherein said processor performs said partitioning using a k-means clustering routine.

25. The system of claim 18, wherein said distance metric is based on a distance between corresponding symbolic feature values of two items based on an overall similarity of classification of all instances for each possible value of said symbolic feature values.

26. The system of claim 25, wherein said distance between symbolic features is computed using a Value Difference Metric (VDM) technique.

27. The system of claim 18, wherein said processor identifies said at least one mean item for each of said k clusters by:

computing a variance for each of said items; and

selecting said at least one item that minimizes said variance as the mean symbolic value.

28. The system of claim 18, wherein said processor identifies said at least one mean item for each of said k clusters by:

computing a variance of each of said clusters, J, for each of said possible symbolic values, x_μ

, for each of said symbolic attributes; and

selecting for each of said symbolic attributes at least one symbolic value, x_μ

, that minimizes said variance as the mean symbolic value.

29. The system of claim 18, wherein said mean is comprised of a plurality of items and wherein said distance metric for a given item in said third party selection history is based on a distance between said given item and each item comprising said mean.

30. An article of manufacture for partitioning a plurality of items into groups of similar items, said plurality of items corresponding to a selection history by at least one third party, comprising:

a computer readable medium having computer readable code means embodied thereon, said computer readable program code means comprising;

a step to partition said third party selection history into k clusters of said plurality of items, said plurality of items including at least one of programs, content and products;

a step to identify at least one mean item for each of said k clusters; and

a step to assign each of said plurality of items to one of said clusters based on a distance metric.