Method and apparatus for using cluster compactness as a measure for generation of additional clusters for stereotyping programs

• US 20040003401A1
• Filed: 06/27/2002
• Published: 01/01/2004
• Est. Priority Date: 06/27/2002
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Gutta, Srinivas, Kurapati, Kaushal
• Application Number:
  US10/183,762
• Publication Number:
  US 20040003401A1
• Time in Patent Office: Days
• US Class Current: 725/46
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data
• 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/4667 Processing of monitored end-user data, e.g. trend analysis based on the log file of viewer selections
• CPC Class Codes: H04N 7/165 Centralised control of user terminal subsequent to an upstream request signal H04N7/17345; Registering at central by two-way working H04N7/17309

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 in accordance with a measure of cluster compactness.

Claims

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

partitioning the selection history into k clusters, k having an initial value of at least two;

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

assigning each of the plurality of items to one of the k clusters based on a distance metric;

determining a measure of cluster compactness for at least one of the k clusters; and

incrementing the value of k if a predetermined criteria is not met by the measure of cluster compactness and then repeating the steps.

2. The method of claim 1, wherein the step of incrementing the value of k may be repeated until a further increment of k does not improve a classification accuracy.

3. The method of claim 1, further comprising the step of accepting a particular cluster if the predetermined criteria is met by the particular cluster.

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

5. The method of claim 1, wherein the plurality of items are programs.

6. The method of claim 1, wherein the plurality of items are content.

7. The method of claim 1, wherein the plurality of items are products.

8. The method of claim 1, wherein the 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 the symbolic feature values.

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

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

computing a variance for each of the plurality of items; and

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

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

a memory for storing computer readable code; and

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

partition the selection history into k clusters, k having an initial value of at least two;

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

assign each of the plurality of items to one of the k clusters based on a distance metric;

determine a measure of cluster compactness for at least one of the k clusters; and

increment the value of k if a predetermined criteria is not met by the measure of cluster compactness.

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

13. The system of claim 11, wherein said processor is further configured to accept a particular cluster if the predetermined criteria is met by the particular cluster.

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

15. The system of claim 11, wherein the 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.

16. The system of claim 15, wherein the distance between symbolic features is computed using a Value Difference Metric (VDM) technique.

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

computing a variance for each of the plurality of items; and

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

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

19. 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;

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

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

a step to determine a measure of cluster compactness for at least one of the k clusters; and

a step to increment the value of k if a predetermined criteria is not met by the measure of cluster compactness.