Document categorisation system

• US 7,971,150 B2
• Filed: 09/25/2001
• Issued: 06/28/2011
• Est. Priority Date: 09/25/2000
• Status: Active Grant

• Current Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Original Assignee: Telstra New Wave Pty Limited
• Inventors: Kowalczyk, Adam, Raskutti, Bhavani
• Primary Examiner(s): Bashore; William L
• Assistant Examiner(s): Zahr; Ashraf
• Application Number:
  US10/514,470
• Publication Number:
  US 20060089924A1
• Time in Patent Office: 3,563 Days
• Field of Search: 707/1, 707/7, 707736-740, 715/764
• US Class Current: 715/764
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

A document categorization system, including a clusterer for generating clusters of related electronic documents based on features extracted from the documents, and a filter module for generating a filter on the basis of the clusters to categorize further documents received by the system. The system may include an editor for manually browsing and modifying the clusters. The categorization of the documents is based on n-grams, which are used to determine significant features of the documents. The system includes a trend analyzer for determining trends of changing document categories over time, and for identifying novel clusters. The system may be implemented as a plug-in module for a spreadsheet application for permitting one-off or ongoing analysis of text entries in a worksheet.

Claims

1. A data categorization computer system comprising:

data processing logic having;

a clusterer module configured to apply unsupervised learning to first items of electronic data stored on a computer-readable storage medium to generate a set of clusters of related ones of said first items of electronic data based on features extracted from said first items of electronic data, said features including at least one of n-grams, words and phrases, and the clusters representing respective item categories;

an interactive cluster editor configured to display the set of clusters to a user and to modify the set of clusters based on input from the user to provide a set of training clusters;

a filter module configured to use the set of training clusters as training data for supervised learning to generate categorization data representing models that distinguish respective ones of said clusters from the other clusters;

a classifier configured to use the categorization data to categorize second items of electronic data stored on the computer-readable storage medium into the training clusters; and

a trend analyzer for determining trends of item categories over time.

2. The system of claim 1, wherein the interactive cluster editor includes user interface components to create one or more clusters, delete one or more clusters, and to move one or more of said items or one or more of said clusters to another cluster.

3. The system of claim 1, wherein the system is configured to select groups of items of electronic data received over respective time periods, each selected group being provided to the clusterer module and the filter module to generate respective categorization data, the trend analyzer being adapted to compare the categorization data generated by the clusterer module with the categorization data generated by the filter module to determine changes in received items of electronic data over time.

4. The system of claim 1, wherein the clusterer module and filter module are components of a spreadsheet application.

5. The system of claim 1, wherein said clusterer module is configured to extract features from the first items of electronic data, select features from the extracted features based on discriminating abilities of the extracted features, and to generate said clusters of said first related items of electronic data based on the selected features.

6. The system of claim 1, further including a cluster describer module configured to automatically generate text describing each cluster, and wherein the interactive cluster editor is configured to modify the text describing the clusters based on input from the user.

7. The system as claimed in claim 1, wherein said features include n-grams.

8. The system as claimed in claim 1, wherein said features include n-grams, words and phrases.

9. The system of claim 1, wherein at least some of the items of electronic data are electronic documents.

10. A data categorization process executed by a computer system, the process including:

using the computer system to apply unsupervised learning to first items of electronic data stored on a computer-readable storage medium to generate a set of clusters of related ones of said first items of electronic data based on features extracted from said first items of electronic data, said features including at least one of n-grams, words and phrases, and the clusters representing respective item categories;

displaying the set of clusters to a user;

receiving cluster modification data from the user;

modifying the set of clusters on the basis of the cluster modification data to provide a set of training clusters;

using the training clusters as training data for applying supervised learning to generate categorization data representing models that distinguish respective ones of said training clusters form the other training clusters;

using the categorization data to categorize second items of electronic data into the training clusters; and

determining one or more trends of respective item categories over time.

11. The process of claim 10, wherein said modifying includes one or more of:

creating one or more clusters, deleting one or more clusters, moving one or more of said items to another cluster, and moving one or more of clusters to another cluster.

12. The process of claim 10, wherein the extraction of features includes:

determining features of said first items of electronic data;

determining discriminating abilities of said features; and

selecting ones of said features based on said discriminating abilities, wherein the clusters are generated based on the selected features.

13. The process of claim 12, wherein a discriminating ability of each feature is determined by comparing similarities generated for groupings of said first items of electronic data with and without the feature.

14. The process of claim 10, including:

selecting one or more of said clusters if the number of items in each of said one or more clusters exceeds a threshold value; and

generating descriptive labels for the selected one or more clusters.

15. The process of claim 14, wherein the descriptive labels include at least one of phrases and sentences.

16. The process of claim 10, wherein at least some of said items of electronic data are electronic documents.

17. The process of claim 10, wherein at least some of said items of electronic data are entries in at least one worksheet of a spreadsheet document.

18. The process of claim 17, wherein each of said entries includes text data to be used for categorizing the entries, and structured data.

19. The process of claim 17, including generating at least one category descriptor for each entry.

20. The process of claim 17, including generating a formatted version of data of an entry to indicate a category of said entry.

21. The process of claim 17, including generating category identifiers for said entries.

22. The process of claim 17, including generating category columns of said at least one worksheet for identifying respective categories of said entries.

23. The process of claim 17, including generating one or more scores for respective categories of an entry.

24. The process of claim 23, including generating an error for an entry if any one of said one or more scores is inconsistent with a respective category.

25. The process of claim 23, wherein a score for an entry indicates that the entry belongs to a corresponding category if said score exceeds a predetermined value.

26. The process of claim 25, wherein the value of said predetermined value is zero.

27. The process of claim 25, wherein scores exceeding said predetermined value are formatted differently than scores less than said value.

28. The process of claim 23, including generating a probability that said entry belongs to a corresponding category on the basis of said score.

29. The process of claim 10, including generating a cluster identifier for identifying at least one of said clusters;

and a cluster size value for identifying the size of said cluster.

30. The process of claim 10, clusters are generated on the basis of features extracted from items of electronic training data, and the process includes testing said categorization data by categorizing the electronic training data.

31. The process of claim 10, wherein the features include n-grams.

32. The process of claim 10, wherein the features include n-grams, words and phrases.

33. A computer component for use with a spreadsheet application, the component being configured to execute the steps of claim 10.

34. A data categorisation system having components configured to execute the steps of claim 10.

35. A computer readable storage medium having stored thereon program instructions for executing the steps of claim 10.

36. A data categorization system embodied on a computer-readable storage medium for use with first items of electronic data and second items of electronic data, the data categorization system including:

a clusterer configured to apply unsupervised learning to the first items of electronic data to generate clusters of the first items of electronic data based on features extracted from the first items of electronic data, said features including at least one of n-grams, words and phrases;

a cluster editor having user interface components for displaying the clusters of the first items of electronic data to a user of the system and for receiving cluster modification data from the user;

the clusterer being configured to create or delete one or more clusters of the first items of electronic data and to move one or more of the first items of electronic data or one or more of said clusters to another cluster on the basis of the cluster modification data to form one or more modified clusters;

a filter module configured to use the modified clusters as training data for supervised learning to generate classification data;

a classifier for using the classification data to classify the second items of electronic data into the modified clusters; and

a trend analyzer for determining trends of item classifications over time.

37. The system of claim 36 wherein the filter module is additionally configured to use the clusters of the first items of electronic data as training data for supervised learning to generate the classification data.