ASSISTED CLUSTERING

• US 20110295773A1
• Filed: 05/26/2010
• Published: 12/01/2011
• Est. Priority Date: 05/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lu, Hao, Drucker, Steven, Basu, Sumit, Fisher, Danyel A., Ramos, Gonzalo A.
• Granted Patent: US 8,359,279 B2
• Time in Patent Office: Days
• US Class Current: 706/11
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

Assisted clustering systems and methods are described herein that provide a user interface by which a user can easily create clusters and selectively associate data items with such clusters. Information regarding data item-cluster associations made by the user is processed by a recommendation engine to learn a clustering model. The clustering model is then be used to generate recommendations for the user regarding which unassociated data items should be associated with which clusters. In certain embodiments, after the user has determined that the clustering model is performing at a satisfactory level based on the quality of the recommendations, the user can cause the system to automatically cluster a large quantity of remaining unassociated data items. In accordance with further embodiments, a user can specify arbitrary data item types for clustering as well as features of such data types that should be considered in generating the clustering model.

Claims

1. An assisted clustering system, comprising:

a user interface that enables a user to selectively associate each of a plurality of data items with any one of a plurality of clusters; and

a computer-implemented recommendation engine that receives input regarding data item-cluster associations made by the user via the user interface and that generates recommendations for provision to the user regarding additional data item-cluster associations based on the input.

2. The system of claim 1, wherein the recommendations comprise at least one recommendation regarding which data item(s) to associate with a user-selected cluster.

3. The system of claim 1, wherein the recommendations comprise at least one recommendation regarding which cluster to associate a user-selected data item with.

4. The system of claim 1, wherein the user interface enables a user to specify data items of arbitrary data types for selective association with clusters.

5. The system of claim 1, wherein the recommendation engine comprises a machine learning system that that is trained to generate the recommendations based on the input.

6. The system of claim 5, wherein the machine learning system comprises one of a metric learner, a classifier, a hybrid metric learner and classifier, or a clustering algorithm.

7. The system of claim 5, wherein the user interface enables a user to specify features associated with the data items that are to be used by the machine learning system to build a model for generating the recommendations.

8. The system of claim 1, further comprising a computer-implemented cluster manager that maintains a record of user-created associations between data items and clusters.

9. A system comprising a processing unit, one or more input devices, and a display, the processing unit being configured to implement a graphical user interface by processing user input provided via the input device(s) and by rendering images to the display, the graphical user interface enabling a user to associate each of a plurality of data items with any one of a plurality of clusters in a system-assisted manner and comprising:

a visual representation of each of the data items;

a visual representation of each of the clusters;

means for enabling the user to selectively associate each data item representation with any one of the cluster representations; and

means for outputting a user-perceivable indication that a particular data item representation should be associated with a particular cluster representation based on a system-generated recommendation.

10. The system of claim 9, wherein each cluster representation is selectable by the user and wherein the means for outputting the user-perceivable indication that the particular data item representation should be associated with the particular cluster representation comprises:

means for outputting a user-perceivable indication that the particular data item representation should be associated with a cluster representation that has been selected by the user.

11. The system of claim 9, wherein each data item representation is selectable by the user and wherein the means for outputting the user-perceivable indication that the particular data item representation should be associated with the particular cluster representation comprises:

means for outputting a user-perceivable indication that a data item representation that has been selected by the user should be associated with the particular cluster representation.

12. The system of claim 9, wherein the user-perceivable indication that the particular data item representation should be associated with the particular cluster representation comprises:

a visual indication that the particular data item representation should be associated with the particular cluster representation.

13. The system of claim 12, wherein the visual indication that the particular data item representation should be associated with the particular cluster representation comprises:

a line connecting the particular data item representation to the particular cluster representation.

14. The system of claim 12, wherein the visual indication that the particular data item representation should be associated with the particular cluster representation comprises:

a repositioning of one or both of the particular data item representation and the particular cluster representation.

15. The system of claim 9, wherein the graphical user interface further comprises:

a visual representation of a group of data items that the user has determined should not be associated with any cluster representation; and

a means for enabling the user to associate any of the data item representations with the visual representation of the group.

16. The system of claim 9, wherein the data items contain textual elements and wherein the graphical user interface further comprises:

a means for inputting a text query to be executed against each of the data items; and

a means for visually identifying one or more of the data items representations that correspond to data items that are determined to match the text query.

17. The system of claim 9, wherein the input device(s) comprise a multi-touch-capable touch screen.

18. The system of claim 9, wherein the means for enabling the user to selectively associate each data item representation with any one of the cluster representations comprises:

means for enabling multiple users to contemporaneously and selectively associate each data item representation with any one of the cluster representations.

19. The system of claim 10, wherein a visual representation of a cluster comprises a visual representation of a container that encompasses one or more data item representations.

20. An assistive clustering system comprising:

a user interface that enables a user to selectively associate each of a plurality of data items with any one of a plurality of clusters;

a machine learning system that learns a clustering model based on input received from the user interface regarding data item-cluster associations made by the user; and

an automatic clustering module that applies the clustering model to selectively associate unassociated data items in the plurality of data items with corresponding clusters in the plurality of clusters.