Self-organizing neural network for plain text categorization

• US 6,047,277 A
• Filed: 06/19/1997
• Issued: 04/04/2000
• Est. Priority Date: 06/19/1997
• Status: Expired due to Term

• Current Assignee: Ceridian Corporation
• Original Assignee: Ceridian Corporation
• Inventors: Parry, Michael H., Aspnes, Richard K.
• Primary Examiner(s): Stamber, Eric W.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/879,211
• Time in Patent Office: 1,020 Days
• Field of Search: 706/15, 706/16, 706/20, 706/25, 706/26, 706/27, 706/14, 704/6, 704/7, 704/9, 704/10
• US Class Current: 706/20
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

A method and system for natural language processing including using a trained neural network having a plurality of baseline nodes. A connection weight between any selected pair of baseline nodes is described by text strings within the selected pair of nodes. A plurality of text messages are received from a preselected source. For each received message, a non-baseline node associated with a selected one of the baseline nodes is created. A connection weight between any non-baseline node and the associated baseline node is described by the text string within the baseline node and the received text message.

Claims

1. A method for natural language processing comprising the steps of:

training a neural network comprising a plurality of baseline nodes, wherein a connection weight between any selected pair of baseline nodes is determined from text strings within the selected pair of nodes;

receiving a plurality of text messages from a preselected source;

for each received message, creating a non-baseline node associated with a selected one of the baseline nodes wherein a connection weight between any non-baseline node and the associated baseline node is determined from the text string within the baseline node and the received text message; and

identifying atypical received messages based upon the connection weight between any non-baseline node and the associated baseline node.

2. The method of claim 1 wherein the step of creating a non-baseline node further comprises:

applying each received text message to the neural network;

for each non-baseline node, calculating a distance from each baseline node in the neural network to determine the connection weights; and

based upon the calculating step, associating the non-baseline node with a baseline node having the greatest connection weight.

3. The method of claim 1 wherein the step of creating a non-baseline node further comprises:

applying each received text message to the neural network;

for each non-baseline node, calculating a distance from each baseline node and each prior non-baseline node in the neural network to determine the connection weights; and

based upon the calculating step, associating the non-baseline node directly with a baseline node having the greatest connection weight unless there exists a prior non-baseline node with greater connection weight than the greatest baseline node in which case the non-baseline node is indirectly associated with the baseline node associated with the prior non-baseline node having greatest connection weight.

4. The method of claim 3 wherein the step of calculating a distance from each baseline node and each prior non-baseline node uses a least common sub-sequence matching algorithm.

5. The method of claim 1 further comprising:

training the neural network using training data, wherein the training data comprises text messages from the preselected source.

6. The method of claim 1 further comprising the steps of preprocessing the received text messages to remove duplicates.

7. The method of claim 1 further comprising the steps of preprocessing the received text messages to break large massages into multiple paragraph-sized units.

8. The method of claim 1 further comprising the steps of preprocessing the received text messages to remove duplicate words, punctuation, and stop words.

9. The method of claim 1 further comprising the step of periodically combining the baseline and non-baseline nodes.

10. The method of claim 9 wherein the step of combining comprises:

encoding token sequences from a selected baseline node with token sequences from a selected non-baseline node in a graph;

randomly traversing the graph a plurality of times;

extracting a child token sequence for each random traversal;

comparing the extracted child token sequence with the selected token sequences; and

replacing the selected parent sequences with a best matching child token sequence in response to the comparing step.

11. The method of claim 1 further comprising analyzing atypical received text messages by determining cohesiveness of non-baseline nodes comprising the steps of:

identifying a cluster of non-baseline nodes comprising all non-baseline nodes associated with a selected baseline node;

calculating a distance between each non-baseline node in the identified cluster and each other non-baseline node in the identified cluster such that smaller calculated distances indicate cohesiveness.

12. A method for natural language processing comprising the steps of:

training a neural network comprising a plurality of baseline nodes, wherein a connection weight between any selected pair of baseline nodes is determined from text strings within the selected pair of nodes;

receiving a plurality of text messages from a preselected source;

for each received message, creating a non-baseline node associated with a selected one of the baseline nodes wherein a connection weight between any non-baseline node and the associated baseline node is determined from the text string within the baseline node and the received text message; and

identifying atypical received text messages by calculating a distance between each non-baseline node and its associated baseline node such that greater calculated distances indicate atypical data.

13. The method of claim 12 further comprising a step of notifying a user to review the text messages associated with atypical non-baseline nodes in response to the step of identifying atypical nodes.

14. A method for natural language processing comprising the steps of:

training a neural network comprising a plurality of baseline nodes, wherein a connection weight between any selected pair of baseline nodes is determined from text strings within the selected pair of nodes;

receiving a plurality of text messages from a preselected source;

for each received message, creating a non-baseline node associated with a selected one of the baseline nodes wherein a connection weight between any non-baseline node and the associated baseline node is determined from the text string within the baseline node and the received text message; and

analyzing atypical received text messages by determining a magnitude of a frequency of associations of non-baseline nodes with a selected baseline node.

15. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for natural language processing, the computer program product comprising;

computer readable program code devices configured to cause a computer to effect a trained neural network comprising a plurality of baseline nodes, wherein each baseline node has a weight that is represented by a text string within the node;

computer readable program code devices configured to cause a computer to effect receiving a plurality of text messages from a preselected source;

computer readable program code devices configured to cause a computer to effect for each received message, creating a non-baseline node having a weight that is represented by the received text message;

computer readable program code devices configured to cause a computer to effect associating each non-baseline node with a selected one of the baseline nodes; and

computer readable program code devices configured to cause a computer to effect identifying atypical received text based upon a difference between the non-baseline node associated with the received message and the baseline node to which the non-baseline node is associated.

16. The computer program product of claim 15 wherein the computer readable program code devices configured to cause a computer to effect associating each non-baseline node with a selected one of the baseline nodes further comprises:

computer readable program code devices configured to cause a computer to effect applying each received text message to the neural network;

computer readable program code devices configured to cause a computer to effect for each non-baseline node, calculating a distance from each baseline node and each prior non-baseline node in the neural network to determine a connection weight, wherein the program code for calculating a distance uses a least common sub-sequence matching algorithm; and

computer readable program code devices responsive to the calculating step configured to cause a computer to effect associating the non-baseline node directly with a baseline node having the greatest connection weight unless there exists a prior non-baseline node with greater connection weight than the greatest baseline node in which case the non-baseline node is indirectly associated with the baseline node associated with the prior non-baseline node having greatest connection weight.

17. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for natural language processing, the computer program product comprising;

computer readable program code devices configured to cause a computer to effect a trained neural network comprising a plurality of baseline nodes, wherein each baseline node has a weight that is represented by a text string within the node;

computer readable program code devices configured to cause a computer to effect receiving a plurality of text messages from a preselected source;

computer readable program code devices configured to cause a computer to effect for each received message, creating a non-baseline node having a weight that is represented by the received text message;

computer readable program code devices configured to cause a computer to effect associating each non-baseline node with a selected one of the baseline nodes;

computer readable program code devices configured to cause a computer to effect a self-organizing neural network architecture comprising a one-dimensional circular array of baseline nodes;

computer readable program code devices configured to cause a computer to effect randomizing the weight within each of the baseline nodes;

computer readable program code devices configured to cause a computer to effect receiving a baseline text messages from the preselected source;

computer readable program code devices configured to cause a computer to effect associating the received baseline text message with a closest one of the randomized baseline nodes wherein closeness is measured by a longest common sub-sequence algorithm;

computer readable program code devices configured to cause a computer to effect combining the received baseline text message with the associated baseline node using a genetic algorithm; and

computer readable program code devices configured to cause a computer to effect iteratively executing the program code effecting the receiving, the associating, and the combining until the neural network achieves a desired state of training.

18. The computer program product of claim 17 wherein the computer readable program code devices configured to cause a computer to effect least common sub-sequence matching algorithm further comprises computer readable program code devices configured to cause a computer to effect the equation:

##EQU3## wherein len(s1) is the length of the text within the baseline node, len(s2) is the length of the baseline text, and len(LCS) is the length of the longest common sequence between s1 and s2.

19. A system for processing information to identify atypical information content of received digitized text information with respect to prior digitized text information, the system comprising:

a digital computer;

communication means for electronically collecting text information into the computer, the text organized in messages;

software operable in the computer for representing the prior digitized text information in a neural network array, the array comprising a plurality of baseline nodes wherein each baseline node occupies a unique location in a text hyperspace and each baseline node has a weight represented by text tokens within the baseline node wherein the text tokens are determined from the prior digitized text;

software operable in the computer for representing each received message as a non-baseline node having a position in the text hyperspace;

software operable in the computer for directly or indirectly associating each non-baseline node with one baseline node; and

software operable in the computer for evaluating relative positions of the non-baseline nodes in the text hyperspace to identify atypical received messages.

20. The system of claim 19 wherein the software operable in the computer for evaluating relative positions calculates a metric score based upon content of the baseline nodes and the non-baseline nodes.

21. A system for processing information to identify atypical information content of received digitized text information with respect to prior digitized text information, the system comprising:

a digital computer;

communication means for electronically collecting text information into the computer, the text organized in messages;

software operable in the computer for representing the prior digitized text information in a neural network array, the array comprising a plurality of baseline nodes wherein each baseline node occupies a unique location in a text hyperspace and each baseline node has a weight represented by text tokens within the baseline node;

software operable in the computer for representing each received message as a non-baseline node having a position in the text hyperspace;

software operable in the computer for directly or indirectly associating each non-baseline node with one baseline node; and

software operable in the computer for evaluating relative positions of the non-baseline nodes in the text hyperspace to identify atypical received messages, wherein the software operable in the computer for evaluating relative positions calculates a metric score using the equation;

##EQU4## wherein len(s1) is the length of text within the baseline node, len(s2) is the length of text within the non-baseline node, and len(LCS) is the length of the longest common sequence between s1 and s2.

22. A system for processing information to identify atypical information content of received digitized text information with respect to prior digitized text information, the system comprising:

a digital computer;

communication means for electronically collecting text information into the computer, the text organized in messages;

software operable in the computer for representing the prior digitized text information in a neural network array, the array comprising a plurality of baseline nodes wherein each baseline node occupies a unique location in a text hyperspace and each baseline node has a weight represented by text tokens within the baseline node, wherein the software operable in the computer for representing the prior digitized text information in a neural network array further comprises software operable to implement a text domain one dimensional neural network array and the software operable for associating each non-baseline node with one baseline node operates to directly associate each non-baseline node with one of the baseline nodes;

software operable in the computer for representing each received message as a non-baseline node having a position in the text hyperspace;

software operable in the computer for directly or indirectly associating each non-baseline node with one baseline node; and

software operable in the computer for evaluating relative positions of the non-baseline nodes in the text hyperspace to identify atypical received messages.

23. A system for processing information to identify atypical information content of received digitized text information with respect to prior digitized text information, the system comprising:

a digital computer;

communication means for electronically collecting text information into the computer, the text organized in messages;

software operable in the computer for representing the prior digitized text information in a neural network array, the array comprising a plurality of baseline nodes wherein each baseline node occupies a unique location in a text hyperspace and each baseline node has a weight represented by text tokens within the baseline node, wherein the software operable in the computer for representing the prior digitized text information in a neural network array further comprises software operable to implement a text domain extensible minimum-spanning-tree (MST) neural network array and the software operable for associating each non-baseline node with one baseline node is operable to associate each non-baseline node with a baseline node or non-baseline node having the smallest relative position;

software operable in the computer for representing each received message as a non-baseline node having a position in the text hyperspace;

software operable in the computer for directly or indirectly associating each non-baseline node with one baseline node; and

software operable in the computer for evaluating relative positions of the non-baseline nodes in the text hyperspace to identify atypical received messages.

24. A system for processing information to identify atypical information content of received digitized text information with respect to prior digitized text information, the system comprising:

a digital computer;

communication means for electronically collecting text information into the computer, the text organized in messages;

software operable in the computer for representing the prior digitized text information in a neural network array, the array comprising a plurality of baseline nodes wherein each baseline node occupies a unique location in a text hyperspace and each baseline node has a weight represented by text tokens within the baseline node;

software operable in the computer for representing each received message as a non-baseline node having a position in the text hyperspace;

software operable in the computer for directly or indirectly associating each non-baseline node with one baseline node;

software operable in the computer for evaluating relative positions of the non-baseline nodes in the text hyperspace to identify atypical received messages; and

software operable in the computer for combining the contents of a non-baseline node with the contents of a selected baseline node in order to train the neural network.

25. The system of claim 24 wherein the software operable for combining comprises a genetic algorithm.