Methods and apparatus for automatic classification of text messages into plural categories

• US 7,472,095 B2
• Filed: 12/16/2005
• Issued: 12/30/2008
• Est. Priority Date: 12/16/2005
• Status: Expired due to Fees

• Current Assignee: Piece Future Pte., Ltd.
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Huelsbergen, Lorenz, Qutub, S. Shehryar
• Primary Examiner(s): Hirl, Joseph P.
• Assistant Examiner(s): Kennedy, Adrian L
• Application Number:
  US11/305,300
• Publication Number:
  US 20070143236A1
• Time in Patent Office: 1,110 Days
• Field of Search: 706/20, 706/48, 706/18
• US Class Current: 706/20
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Systems and techniques for classification of incoming text messages into categories. An initial set of categories is created and populated with a set of initial messages in each category. Incoming messages are assigned to a category based on text analysis of the incoming message and analysis of dissimilarities and differences between the message and messages already in the category. A set of unclassified messages is also maintained for incoming messages that do not fit an established category. Periodically, unclassified messages are reassigned to one of the established categories or to new categories created based on analysis of the unclassified messages.

Claims

1. A processor based system for categorizing text messages into established categories populated with messages, comprising:

an incoming message categorization module for classifying incoming messages, the message categorization module being operative to examine elements of each incoming message to identify an appropriate category to which to assign the incoming message based on syntactic similarities and differences between the incoming message and messages already in the category, including messages that have previously been automatically assigned to the category by the incoming message categorization module;

the incoming message categorization module assigning the incoming message to an established category previously established by an initial category creation module if predetermined criteria for syntactic similarity between the incoming message and one of the established categories are met; and

the message categorization module assigning the incoming message to an overflow category if predetermined criteria are not met for syntactic similarity between the incoming message and one of the established categories.

2. The system of claim 1 further comprising:

a category creation module operative to create said established categories for assignment of messages, the category creation module being operative to perform syntactic analysis on an initial corpus of messages to create clusters of messages, each message in a cluster of messages assigned to a category being chosen so as to having similar syntactic characteristics to other messages in the category and different syntactic characteristics from messages in other categories, the category creation module creating the established categories populated with messages from the initial corpus and also creating the overflow category which is initially empty.

3. The system of claim 1 further comprising:

a recategorization module for periodically examining messages in the overflow category and using syntactic analysis to reassign messages in the overflow category to one of the established categories or to newly created categories.

4. The system of claim 1, wherein category creation is performed by assigning messages from the initial corpus to categories so as to create categories having a maximum achievable mutual syntactic distance.

5. The system of claim 4, wherein syntactic distance is evaluated by analyzing each message to identify tokens and calculating syntactic distance on the basis of frequency of tokens shared between messages.

6. The system of claim 5, wherein each token is a string of characters having a predetermined length.

7. The system of claim 6, wherein each token is a tri-gram.

8. The system of claim 5, wherein the category creation module is operative to label each category and wherein labeling of each category is performed by sequentially selecting and concatenating a predetermined number of tokens appearing in the category in descending order of priority, priority being assigned to tokens according to predetermined criteria, the criteria including frequency of occurrence.

9. The system of claim 1, wherein the incoming message categorization module is operative to categorize incoming messages by analyzing the incoming message to identify tokens appearing in the incoming message and calculating syntactic distance on the basis of tokens shared between the incoming message and messages in each of the categories.

10. A processor based system for categorizing text messages into established categories populated with messages, comprising:

an incoming message categorization module for classifying incoming messages, the message categorization module being operative to examine elements of each incoming message to identify an appropriate category to which to assign the incoming message based on syntactic similarities and differences between the incoming message and messages in the category;

the incoming message categorization module assigning the incoming message to an established category if predetermined criteria for syntactic similarity between the incoming message and one of the established categories are met;

the message categorization module assigning the incoming message to an overflow category if predetermined criteria are not met for syntactic similarity between the incoming message and one of the established categories; and

a recategorization module for periodically examining messages in the overflow category and using syntactic analysis to reassign messages in the overflow category to one of the established categories or to newly created categories, wherein the recategorization module is operative to perform recategorization when the number of messages in the overflow category is greater than the average number of messages in the established categories.

11. A processor based method of message categorization for categorizing messages into established categories populated with messages, the method comprising the steps of:

receiving incoming messages;

examining elements of each incoming message to identify an appropriate category to which to assign the incoming message based on syntactic similarities and differences between the incoming message and messages already in the category, including messages that have previously been automatically assigned to the category by an incoming message categorization module;

assigning the incoming message to an established category previously established by an initial category creation module if predetermined criteria for syntactic similarity between the incoming message and one of the established categories are met; and

assigning the incoming messages to an overflow category if predetermined criteria are not met for syntactic similarity between the incoming message and one of the established categories.

12. The method of claim 11 further comprising:

analyzing an initial corpus of messages to create an initial set of categories for assignment of messages, analyzing the initial corpus of messages comprising analyzing syntactic characteristics of messages to create clusters of messages based on similarities of syntactic characteristics of messages in the same cluster and differences of syntactic characteristics between messages in different clusters, and assigning messages from the clusters to create categories to the established categories populated with messages, creation of the initial set of categories further comprising creation of an initially empty overflow category.

13. The method of claim 11 further comprising:

periodically examining messages in the overflow category and using syntactic analysis to reassign messages in the overflow category to one of the established categories or to newly created categories.

14. The method of claim 11, wherein the categories are created such that the categories have the maximum achievable mutual syntactic distance based on syntactic characteristics of messages assigned to each category.

15. The method of claim 14, wherein evaluating syntactic distance between messages includes analyzing each message to identify tokens in each message, assigning a token signature to each message and comparing token signatures of messages.

16. The method of claim 15, wherein the step of creating initial categories is followed by a step of labeling each category and wherein labeling of each category is performed by sequentially selecting concatenating a predetermined number of tokens appearing in the category in descending order of priority, priority being assigned to tokens according to predetermined criteria, the criteria including frequency of occurrence.

17. The method of claim 11, wherein the step of categorizing incoming messages comprises analyzing each incoming message to identify tokens appearing in the incoming message and calculating syntactic distance on the basis of tokens shared between the incoming message and messages in each of the categories.

18. The method of claim 17, wherein the step of calculating syntactic similarities and differences comprises computing probability values for inclusion of the message in each category.

19. A message control and routing center for receiving and routing text messages, comprising:

an interface for receiving and routing text messages

a processor for analyzing and categorizing text messages and directing routing of text messages according to their categories; and

a computer readable storage medium storing instructions directing operation of the processor in categorizing the text messages, the instructions comprising;

a category creation module operative to automatically create a set of initial categories for assignment of messages, the category creation module being operative to perform syntactic analysis on an initial corpus of messages to create clusters of messages, each message in a cluster of messages assigned to a category by the category creation module and being chosen so as to having similar syntactic characteristics to other messages in the category and different syntactic characteristics from messages in other categories, the category creation module being operative to create a plurality of established categories populated with messages from the initial corpus and an initially empty overflow category;

an incoming message categorization module for classifying incoming messages, the message categorization module being operative to examine elements of each incoming message to identify an appropriate category to which to assign the incoming message based on syntactic similarities and differences between the incoming message and messages in the category and to assign the incoming message to an established category if predetermined criteria for syntactic similarity between the incoming message and one of the established categories is met, the message categorization module being operative to assign the incoming message to the overflow category if predetermined criteria are not met for syntactic similarity between the incoming message and one of the established categories; and

a recategorization module for periodically examining messages in the overflow category and using syntactic analysis to reassign messages in the overflow category to one of the established categories or to newly created categories.

20. The system of claim 19, wherein category creation is performed by assigning messages from the initial corpus to categories so as to create categories having a maximum achievable mutual syntactic distance.