Semantic clustering and user interfaces

• US 8,694,304 B2
• Filed: 03/26/2010
• Issued: 04/08/2014
• Est. Priority Date: 03/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: VirtuOz SA (Microsoft Corporation)
• Inventors: Larcheveque, Jean-Marie Henri Daniel, Powers, Elizabeth Ireland, Recksiek, Freya Kate, Teodosiu, Dan
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US12/748,150
• Publication Number:
  US 20110238410A1
• Time in Patent Office: 1,474 Days
• Field of Search: 704/1, 704/9, 704/10, 704/257
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Semantic clustering techniques are described. In various implementations, a conversational agent is configured to perform semantic clustering of a corpus of user utterances. Semantic clustering may be used to provide a variety of functionality, such as to group a corpus of utterances into semantic clusters in which each cluster pertains to a similar topic. These clusters may then be leveraged to identify topics and assess their relative importance, as for example to prioritize topics whose handling by the conversation agent should be improved. A variety of utterances may be processed using these techniques, such as spoken words, textual descriptions entered via live chat, instant messaging, a website interface, email, SMS, a social network, a blogging or micro-blogging interface, and so on.

Claims

1. A method implemented by one or more computer processors configured to perform semantic clustering, the method comprising:

comparing a first set of semantic clusters, formed from a first corpus of user utterances using a computational linguistic analysis, with a second set of semantic clusters formed from a second corpus of user utterances using a computational linguistic analysis;

identifying semantic clusters having topics that are common to the first and second sets of corpora of user utterances; and

outputting a result of the identifying of semantic clusters having topics that are common to the first and second sets of corpora of user utterances.

2. A method as described in claim 1, wherein the identifying is performed using a centroid-based heuristic.

3. A method as described in claim 2, wherein the centroid-based heuristic includes:

defining a centroid of a said semantic cluster comprised of one or more semantic graphs produced as a result of linguistic analysis, as a point having coordinates that are averages of coordinates of each said semantic graph in the semantic cluster, wherein the coordinates are defined within a vector space in which semantic concepts are considered dimensions;

computing a distance between the centroids of two said semantic clusters; and

considering the two said semantic clusters as having a common said topic when the computed distance is below a specified threshold.

4. A method as described in claim 1, wherein the identifying is performed using a center-based heuristic.

5. A method as described in claim 4, wherein the center-basded heuristic includes:

defining a center of a said semantic cluster based on a specificity of a semantic graph in the semantic cluster;

computing a proximity between the centers of two said semantic clusters; and

considering the two said semantic clusters as having a common said topic when the computed proximity is above a specified threshold.

6. A method as described in claim 1, wherein the identifying is performed using a binary comparison heuristic that is used to identify the semantic clusters that relate to a similar topic.

7. A method as described in claim 1, wherein the result includes the set of semantic clusters that correspond to topics that occur in both the first corpus and the second corpus.

8. A method as described in claim 1, wherein the result includes a set of semantic clusters that correspond to topics that occur in the first corpus but not in the second corpus.

9. A method as described in claim 1, wherein the first corpus and the second corpus correspond to different time intervals, respectively.

10. A method as described in claim 1, wherein at least one said topic is expressed by at least two semantic graphs formed by linguistic analysis and from the first and second sets of semantic clusters, respectively, using different words and grammatical structures.

11. A method as described in claim 1, wherein at least one of the first or second corpora described utterances from a natural language dialog with a conversational agent.

12. A method as described in claim 1, wherein at least one of the first or second corpora describe utterances from a log of conversations with a human agent.

13. A method as described in claim 1, wherein at least one of the first or second corpora describe utterances from an instant messaging conversation, or a feed from a SMS, social networking, blogging, or micro-blogging service.

14. A method as described in claim 1, wherein the identifying includes identifying a particular said semantic cluster that is in the second set of semantic clusters but is not in the first set of semantic clusters.

15. A method as described in claim 14, wherein the particular said semantic cluster identifies a new topic.

16. A method as described in claim 15, wherein the outputting of the result of the identifying includes displaying, in a user interface, the new topic.

17. A method as described in claim 14, wherein the particular said semantic cluster identifies a topic that has disappeared.

18. A method as described in claim 1, wherein the identifying includes outputting, in a user interface, a suggested allocation of resources.

19. A method as described in claim 18, wherein the resources are customer support personnel.

20. A method implemented by one or more computer processors configured to perform semantic clustering, the method comprising:

processing a corpus by computationally clustering a plurality of semantic graphs of user utterances formed form the corpus such that each said cluster corresponds to similar topics; and

outputting a result of the processing in a user interface that indicates prominence of one or more said topics in the corpus.

21. A method as described in claim 20, wherein the processing is performed using one or more proximity metrics by taking a ratio of aggregate specificity of semantic objects that are common to two said semantic graphs that are compared to an aggregate specificity of at least two said semantic objects found in both of the two said semantic graphs.

22. A method as described in claim 20, wherein the clustering is performed through the use of the one or more proximity metrics that includes a concept-set proximity metric.

23. A method as described in claim 20, wherein the clustering is performed through the use of the one or more proximity metrics that includes a graph-intersection proximity metric.

24. A method as described in claim 20, wherein the clustering is performed through using a graph-intersection proximity metric and using a concept-set proximity metric.

25. A method as described in claim 20, wherein the radius proximity is defined as the proximity of the at least one utterance to the center of the one said semantic cluster.

26. A method implemented by one or more computer processors configured to perform semantic clustering, the method comprising:

clustering a plurality of semantic graphs that were formed based on a computational linguistic analysis of a corpus of user utterances into a plurality of semantic clusters through use of one or more proximity metrics; and

calculating to which of the plurality of clusters at least one utterance is to be attached.

27. A method as described in claim 26, further comprising determining a topic frequency of the at least one utterance from the corpus with respect to one or more of the plurality of semantic clusters.

28. A method as described in claim 26, wherein:

the calculating is performed by computing a diameter proximity of the at least one utterance to one said semantic cluster; and

the computing of the diameter proximity is performed by computing the average proximity of the at least one utterance to at least one semantic graph that is a member of one said semantic cluster.

29. A method as described in claim 28, wherein the calculating is performed so that the at least one utterance is attached to the one said semantic cluster that maximizes the diameter proximity.

30. A method as described in claim 29, wherein if more than one said semantic cluster is satisfied, the cluster among these said clusters that maximizes the topic frequency is defined to be the attachment cluster.

31. A method as described in claim 26, wherein the calculating is performed using radius proximity.

32. A method implemented by one or more computer processors configured to perform semantic clustering, the method comprising:

clustering a plurality of semantic graphs that were formed based on a computational linguistic analysis of a corpus of user utterances into a plurality of semantic clusters through use of one or more proximity metrics; and

correlating analytics data with one or more of the semantic clusters of semantic graphs formed based on a computational linguistic analysis of a corpus of user utterances.

33. A method as described in claim 32, wherein the analytics data pertains to conversation success.

34. A method as described in claim 32, wherein the analytics data pertains to commercial orders and correlating results in identification of which topics that correspond to the semantic clusters are conductive to the commercial orders.

35. A method as described in claim 32, wherein the analytics data pertains to web analytics.