Method and system for data mining of short message streams

• US 9,558,165 B1
• Filed: 08/19/2012
• Issued: 01/31/2017
• Est. Priority Date: 08/19/2011
• Status: Expired due to Fees

• Current Assignee: Emicen Corporation
• Original Assignee: Emicen Corporation
• Inventors: Marsten, Roy, Caldwell, Russell, Subramanian, Radhika
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Le, Thuykhanh
• Application Number:
  US13/589,147
• Time in Patent Office: 1,626 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

A method and system for summarizing messages from a message stream is disclosed in which association analysis is applied to stream of short data messages comprising words in a spoken language, such as English. Clusters of words are identified that provide a summary of the several conversations (short data messages originating from different human sources) that are imbedded in the message stream. Each word cluster may represent a set of messages that are its instances. The word clusters may collectively constitute a summary of the entire message stream. The word clusters that have been extracted from message stream may also be grouped into topics. Also, an identity of one or more message originators may be listed based on their influence on the messages being analyzed. The short data messages may also be sorted based on a geographical location of one or more originators of messages.

Claims

1. A computer-implemented method for summarizing a message stream, method comprising the steps of:

defining a communications channel with one or more key words, wherein defining the communications channel comprises specifying one or more key words that are used to extract a message from the message stream, the message stream comprising at least two messages;

extracting one or more messages from the message stream based on the defined channel, wherein extracting one or more messages from the message stream based on the defined channel comprises filtering one or more messages from the message stream using the defined channel as a filter for selecting a message to be extracted for additional processing;

removing common words from the one or more extracted messages;

building a word order graph for the one or more extracted messages, the word order graph tracking sequencing of words found within each extracted message;

using an algorithm to find commonly occurring word clusters within each extracted message, wherein the algorithm reviews each extracted message for at least two-word clusters with a predetermined pair-frequency, the pair-frequency comprising a number of times that words appear together in an extracted message;

pruning the word clusters to reduce a total number of word clusters;

ranking one or more surviving clusters to determine an order of presentation;

arranging each word cluster into a natural order based on the word order graph; and

displaying the word clusters as a summary of the message stream.

2. The computer-implemented method of claim 1, further comprising grouping the word clusters that have been extracted from message stream into topics.

3. The computer-implemented method of claim 1, further comprising listing an identity of one or more message originators based on their influence on the messages being analyzed.

4. The computer-implemented method of claim 1, further comprising defining a communications channel based on a geographical location of one or more originators of messages.

5. The computer-implemented method of claim 4, further comprising displaying a map that is selectable for restricting messages based on a selected location from the map.

6. The computer-implemented method of claim 1, wherein pruning the word clusters to reduce their size comprises a plurality of pruning levels.

7. The computer-implemented method of claim 1, wherein pruning the word clusters to reduce their size comprises at least one of subset pruning, superset pruning, and bipartite pruning.

8. The computer-implemented method of claim 1, wherein building a word order graph comprises determining a frequency of a number of times a pair of words and their sequence exist in a set of messages being analyzed.

9. The computer-implemented method of claim 1, where messages of the message stream have a predefined length.

10. The computer-implemented method of claim 9, wherein the predefined length comprises about two-hundred words or less.

11. A computer-implemented system comprising:

means for defining a communications channel with one or more key words, wherein the means for defining the communications channel with one or more key words comprises means for specifying one or more key words that are used to extract a message from the message stream, the message stream comprising at least two messages;

means for extracting one or more messages from the message stream based on the defined channel, wherein the means for extracting the one or more messages from the message stream based on the defined channel comprises means for filtering one or more messages from the message stream using the defined channel as a filter for selecting a message to be extracted for additional processing;

means for removing common words from the one or more extracted messages;

means for building a word order graph for the one or more extracted messages, the word order graph tracking sequencing of words found within each extracted message;

means for using an algorithm to find commonly occurring word clusters within each extracted message, wherein the algorithm reviews each extracted message for at least two-word clusters with a predetermined pair-frequency, the pair-frequency comprising a number of times that words appear together in an extracted message;

means for pruning the word clusters to reduce a total number of word clusters;

means for ranking one or more surviving clusters to determine an order of presentation;

means for arranging each word cluster into a natural order based on the word order graph; and

means for displaying the word clusters as a summary of the message stream.

12. The computer-implemented system of claim 11, further comprising means for grouping the word clusters that have been extracted from message stream into topics.

13. The computer-implemented system of claim 11, further comprising means for listing an identity of one or more message originators based on their influence on the messages being analyzed.

16. The computer-implemented system of claim 11, wherein the means for pruning the word clusters to reduce their size comprises a plurality of pruning levels.

14. The computer-implemented method of system 11, further comprising means for defining a communications channel based on a geographical location of one or more originators of messages.

15. The computer-implemented system of claim 14, further comprising means for displaying a map that is selectable for restricting messages based on a selected location from the map.

17. A computer program product comprising a tangible computer usable medium having a computer readable program code embodied therein, said tangible computer readable program code adapted to be executed to implement a method for summarizing a message stream, said method comprising:

defining a communications channel with one or more key words, wherein defining the communications channel comprises specifying one or more key words that are used to extract a message from the message stream, the message stream comprising at least two messages;

extracting one or more messages from the message stream based on the defined channel, wherein extracting one or more messages from the message stream based on the defined channel comprises filtering one or more messages from the message stream using the defined channel as a filter for selecting a message to be extracted for additional processing;

removing common words from the one or more extracted messages;

building a word order graph for the one or more extracted messages, the word order graph tracking sequencing of words found within each extracted message;

using an algorithm to find commonly occurring word clusters within each extracted message, wherein the algorithm reviews each extracted message for at least two-word clusters with a predetermined pair-frequency, the pair-frequency comprising a number of times that words appear together in an extracted message;

pruning the word clusters to reduce their size a total number of word clusters;

ranking one or more surviving clusters to determine an order of presentation;

arranging each word cluster into a natural order based on the word order graph; and

displaying the word clusters as a summary of the message stream.

18. The computer program product of claim 17, wherein the program code implementing the method further comprises:

grouping the word clusters that have been extracted from message stream into topics.

19. The computer program product of claim 17, wherein the program code implementing the method further comprises:

listing an identity of one or more message originators based on their influence on the messages being analyzed.

20. The computer program product of claim 17, wherein the program code implementing the method further comprises:

defining a communications channel based on a geographical location of one or more originators of messages.