SITUATION RECOGNITION FOR RECOMMENDATION USING MERGE-SPLIT APPROACH

• US 20090106304A1
• Filed: 04/16/2008
• Published: 04/23/2009
• Est. Priority Date: 10/22/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: JEONG, Sangoh, CHENG, Doreen, SONG, Yu, KALASAPUR, Swaroop
• Granted Patent: US 8,166,052 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds

Abstract

In one embodiment, data relating to usage patterns of the user is stored, wherein the data includes information as to items which were used and the context in which they were used. The data is then clustered into input clusters of data points. It is determined if there are any input clusters that are similar to each other. Similar clusters are merged if there are any input clusters similar to each other. Any non-merged input clusters are divided into split clusters if the split clusters would not be similar to each other. The determining, merging, and dividing are then repeated using the merged, divided, and remaining unmerged and undivided clusters as input clusters.

Claims

1. A method for making recommendations to a user, the method comprising:

storing data relating to usage patterns of the user, wherein the data includes information as to items which were used and the context in which they were used;

clustering the data into input clusters of data points;

determining if there are any input clusters that are similar to each other;

merging the similar clusters if there are any input clusters similar to each other;

dividing any non-merged input clusters into split clusters if the split clusters would not be similar to each other; and

repeating the determining, merging, and dividing using the merged, divided, and remaining unmerged and undivided clusters as input clusters.

2. The method of claim 1, further comprising not repeating the determining, merging, and dividing if there are no input clusters that are similar to each other.

3. The method of claim 1, wherein the dividing is performed before the determining and the merging.

4. The method of claim 1, further comprising:

determining a centroid for each of the input clusters;

selecting clusters similar to a current context of the user by comparing a data point representing the current context of the user to one or more of the centroids;

computing, for each of one or more items, a probability that the user wishes to use the corresponding item, based on the selected similar clusters; and

recommending one or more of the items having based on the probability that the user wishes to use them.

5. The method of claim 1, wherein the clustering is performed using a K-means technique.

6. The method of claim 1, wherein the clustering is performed using a co-clustering technique.

7. The method of claim 1, wherein the clustering is performed using a hierarchical technique.

8. The method of claim 1, wherein the context includes the user'"'"'s location.

9. The method of claim 1, wherein the user is operating a mobile device.

10. An apparatus comprising:

an interface; and

one or more processors configured to;

store data relating to usage patterns of the user, wherein the data includes information as to items which were used and the context in which they were used;

cluster the data into input clusters of data points;

determine if there are any input clusters that are similar to each other;

merge the similar clusters if there are any input clusters similar to each other;

divide any non-merged input clusters into split clusters if the split clusters would not be similar to each other; and

repeat the determining, merging, and dividing using the merged, divided, and remaining unmerged and undivided clusters as input clusters.

11. The apparatus of claim 10, wherein the apparatus is a mobile device.

12. A system for making recommendations to a user, the system comprising:

means for storing data relating to usage patterns of the user, wherein the data includes information as to items which were used and the context in which they were used;

means for clustering the data into input clusters of data points;

means for determining if there are any input clusters that are similar to each other;

means for merging the similar clusters if there are any input clusters similar to each other;

means for dividing any non-merged input clusters into split clusters if the split clusters would not be similar to each other; and

means for repeating the determining, merging, and dividing using the merged, divided, and remaining unmerged and undivided clusters as input clusters.

13. A program storage device readable by a machine tangibly embodying a program of instructions executable by the machine to perform a method for making recommendations to a user, the method comprising:

storing data relating to usage patterns of the user, wherein the data includes information as to items which were used and the context in which they were used;

clustering the data into input clusters of data points;

determining if there are any input clusters that are similar to each other;

merging the similar clusters if there are any input clusters similar to each other;

dividing any non-merged input clusters into split clusters if the split clusters would not be similar to each other; and

repeating the determining, merging, and dividing using the merged, divided, and remaining unmerged and undivided clusters as input clusters.