Method and apparatus for recommending television programming using decision trees

• US 6,727,914 B1
• Filed: 12/17/1999
• Issued: 04/27/2004
• Est. Priority Date: 12/17/1999
• Status: Expired due to Term

• Current Assignee: Contemporary Display LLC (IPValuation Partners, LLC)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Gutta, Srinivas
• Primary Examiner(s): Luu, Sy D.
• Application Number:
  US09/466,406
• Time in Patent Office: 1,593 Days
• Field of Search: 345/719-722, 345/853, 725/39, 725/45-47
• US Class Current: 715/719
• CPC Class Codes: H04N 21/25891 being end-user preferences retrieval of video data in a video database based on user preferences G06F16/739; arrangements for recognizing users' preferences H04H60/46; 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/44222 Analytics of user selections, e.g. selection of programs or purchase activity monitoring of user selections in data processing systems G06F11/34; arrangements for monitoring the user's behaviour or opinions in broadcast systems H04H60/33
• 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/4665 involving classification methods, e.g. Decision trees
• CPC Class Codes: H04N 21/4667 Processing of monitored end-user data, e.g. trend analysis based on the log file of viewer selections
• CPC Class Codes: H04N 21/4668 for recommending content, e.g. movies
• CPC Class Codes: H04N 7/163 by receiver means only

Abstract

A method and apparatus are disclosed for recommending television programming using decision trees. Inductive principles are utilized to identify a set of recommended programs that may be of interest to a particular viewer, based on past viewing behavior. A user'"'"'s viewing history is monitored and the shows that are actually watched by a user (positive examples) and the shows that are not watched by the user (negative examples) are analyzed. For each positive and negative program example (i.e., programs watched and not watched), a number of program attributes are classified in the user profile. The various attributes are then positioned in a hierarchical decision tree based on a ranking of the entropy of each attribute. Each node and sub-node in the decision tree corresponds to a given attribute from the user profile. Each leaf node in the decision tree corresponds to either a positive or negative recommendation for a program mounted at the corresponding leaf node. The decision tree is built using a decision tree process that implements a “top-down divide and conquer” approach. The decision tree can thereafter be applied to an electronic program guide to make program recommendations.

Claims

1. A method for obtaining a recommendation for a television program for a user, said program having attributes, said method comprising the steps of:

obtaining a user profile;

obtaining a viewing history for said user;

analyzing positive and negative examples of training programs that are liked by said user;

generating, using the user profile and viewing history, a new user profile containing a number of attributes for said positive and negative examples;

positioning said attributes in a hierarchical decision tree; and

determining a recommendation for said television program based on a location of said television program in said decision tree.

2. The method of claim 1, wherein said new profile also includes information provided by said user.

3. The method of claim 1, wherein said recommendation is a positive or negative recommendation.

4. The method of claim 1, wherein said positive or negative examples are scored by said user.

5. The method of claim 4, wherein said score is utilized to bias the processing of examples that are misclassified in said decision tree.

6. The method of claim 1, wherein placement of said attributes in said decision tree is based on a ranking of an entropy of each of said attributes.

7. The method of claim 6, wherein said entropy, H, of each of said attributes is obtained using the following expression:

8. The method of claim 1, wherein said positioning step further comprises the steps of selecting an attribute that minimizes an entropy function, H, categorizing said training data into subsets by this attribute;

and repeating said method recursively until each subset contains instances of one kind or a predefined statistical criterion is satisfied.

9. The method of claim 1, further comprising the step of applying said decision tree to additional positive and negative examples to identify a misclassified example.

10. The method of claim 9, wherein said positioning step further comprises the step of inserting said misclassified example into said original positive and negative examples and repeating said positioning step until a predefined threshold is satisfied.

11. A method for obtaining a recommendation for a television program for a user, said program having attributes, said method comprising the steps of:

obtaining a user profile;

obtaining examples of programs that are liked and disliked by said user;

generating, using the user profile and the examples programs, a hierarchical decision tree having nodes comprised of said attributes, said hierarchy based on a ranking of the entropy of each of said attributes; and

recommending said television program based on a location of said television program in said decision tree.

12. The method of claim 11, wherein said profile also includes information provided by said user.

13. The method of claim 11, wherein said recommendation is a positive or negative recommendation.

14. The method of claim 11, wherein said positive or negative examples are scored by said user.

15. The method of claim 14, wherein said score is utilized to bias the processing of examples that are misclassified in said decision tree.

16. The method of claim 11, wherein the placement of said attributes in said decision tree is based on a ranking of the entropy of each of said attributes.

17. The method of claim 16, wherein said entropy, H, of each of said attributes is obtained using the following expression:

18. The method of claim 11, wherein said positioning step further comprises the steps of selecting an attribute that minimizes said entropy function, H, categorizing said training data into subsets by this attribute;

and repeating said method recursively until each subset contains instances of one kind or a predefined statistical criterion is satisfied.

19. The method of claim 11, further comprising the step of applying said decision tree to additional positive and negative examples to identify a misclassified example.

20. The method of claim 19, wherein said positioning step further comprises the step of inserting said misclassified example into said original positive and negative examples and repeating said positioning step until a predefined threshold is satisfied.

21. A system for obtaining a recommendation for a television program for a user, said program having attributes, comprising:

a memory for storing computer readable code; and

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

obtain a user profile;

obtain a viewing history for said user;

analyze positive and negative examples of training programs that are liked by said user;

generate, using the user profile and the positive and negative examples, a new user profile containing a number of attributes for said positive and negative examples;

position said attributes in a hierarchical decision tree; and

determine a recommendation for said television program based on a location of said television program in said decision tree.

22. A system for obtaining a recommendation for a television program for a user, said program having attributes, comprising:

a memory for storing computer readable code; and

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

obtain a user profile;

obtain examples of programs that are liked and disliked by said user;

generate, using the user profile and examples of programs, a hierarchical decision tree having nodes comprised of said attributes, said hierarchy based on a ranking of the entropy of each of said attributes; and

recommend said television program based on a location of said television program in said decision tree.