Text categorization toolkit

A module information extraction system capable of extracting information from natural language documents. The system includes a plurality of interchangeable modules including a data preparation module for preparing a first set of raw data having class labels to be tested, the data preparation module being selected from a first type of the interchangeable modules. The system further includes a feature extraction module for extracting features from the raw data received from the data preparation module and storing the features in a vector format, the feature extraction module being selected from a second type of the interchangeable modules. A core classification module is also provided for applying a learning algorithm to the stored vector format and producing therefrom a resulting classifier, the core classification module being selected from a third type of the interchangeable modules. A testing module compares the resulting classifier to a set of preassigned classes, where the testing module is selected from a fourth type of the interchangeable modules, where the testing module tests a second set of raw data having class labels received by the data preparation module to determine the degree to which the class labels of the second set of raw data approximately corresponds to the resulting classifier.

BACKGROUND OF THE INVENTION
 1. Field of the Invention
 The present invention generally relates to computer text classification
 and, more particularly, to a framework which provides an environment where
 testing several options can be done in an efficient and structured manner.
 2. Background Description
 Businesses and institutions generate many documents in the course of their
 commerce and activities. These are typically written for exchange between
 persons without any plan for machine storage and retrieval. The documents,
 for purposes of differentiation, are described as "natural language"
 documents as distinguished from documents or files written for machine
 storage and retrieval.
 Natural language documents have for some time been archived on various
 media, originally as images and more recently as converted data. More
 specifically, documents available only in hard copy form are scanned and
 the scanned images processed by optical character recognition software to
 generate machine language files. The generated machine language files can
 then be compactly stored on magnetic or optical media. Documents
 originally generated by a computer, such as with word processor, spread
 sheet or database software, can of course be stored directly to magnetic
 or optical media. In the latter case, the formatting information is part
 of the data stored, whereas in the case of scanned documents, such
 information is typically lost.
 There is a significant advantage from a storage and archival stand point to
 storing natural language documents in this way, but there remains a
 problem of retrieving information from the stored documents. In the past,
 this has been accomplished by separately preparing an index to access the
 documents. Of course, the effectiveness of this technique depends largely
 on the design of the index. A number of full text search software products
 have been developed which will respond to structured queries to search a
 document database. These, however, are effective only for relatively small
 databases and are often application dependent; that is, capable of
 searching only those databases created by specific software applications.
 The natural language documents of a business or institution represents a
 substantial resource for that business or institution. However, that
 resource is only a valuable as the ability to access the information it
 contains. Considerable effort is now being made to develop software for
 the extraction of information from natural language documents. Such
 software is generally in the field of knowledge based or expert systems
 and uses such techniques as parsing and classifying. The general
 applications, in addition to information extraction, include
 classification and categorization of natural language documents and
 automated electronic data transmission processing and routing, including
 E-mail and facsimile.
 SUMMARY OF THE INVENTION
 It is therefore an object of the present invention to provide an
 environment where testing out several options can be done in an efficient
 and structured manner.
 The present invention describes a method and apparatus for computer text
 classification and, more particularly, to a framework which provides an
 environment where testing several options can be done in an efficient and
 structured manner.
 The process of the present invention includes mainly:
 1. Feature definition: Typically this involves breaking the text up into
 tokens. Tokens can then be reduced to their stems or combined to
 multi-word terms.
 2. Feature count: Typically this involves counting the frequencies of
 tokens in the input texts. Tokens can be counted by their absolute
 frequency, and several relative frequencies (relativized to the document
 length, the most frequent token, square root, etc.).
 3. Feature selection: This step includes weighting features (e.g.,
 depending on the part of the input text they occur in: title vs. body),
 filtering features depending on how distinctive they are for texts of a
 certain class (filtering can be done by stop word list, based on in-class
 vs. out-class frequency etc.).
 The present invention provides tools for all these tasks.
 The apparatus of the present invention includes inputting raw annotated
 input data document collection means which collects raw data from an
 application. The raw data is submitted to a data preparation module, where
 the data is prepared for testing and training. The data preparation module
 splits the data randomly according to a user specification and submits a
 portion of the prepared data to a test data collection module and a
 portion of the data to a training data document collection module. The
 test data document collection module submits the data to be tested to a
 testing module, while the training data module submits data for training
 to a feature extraction module. The feature extraction module is divided
 into a feature definition module and a feature selection module, each
 having their own configuration files. The feature definition module,
 breaks the text up into tokens, which can then be reduced to their stems
 or combined to multi-word terms. The feature selection module weights the
 features. The feature selection module may also filter features depending
 on how distinctive they are for texts of a certain class.
 The extracted data is then submitted to a feature vector module where the
 extracted data is provided in a vector format, such as a feature count
 table. This data may then be submitted back to the feature extraction
 module, where it may then be submitted to a reduced feature vector module.
 The reduced feature vector module provides the data in a simpler vector
 format that uses less disk space and is easier to process at a later time.
 The vector data is then submitted to a machine learning module where an
 algorithm is applied to the data. At this stage, the present invention
 stores the various data in a directory tree module, which may store the
 data in various formats. The testing module then tests the data and
 provides a precision, recall, accuracy or other statistic analysis of the
 tested data, as described in detail below. The test module may be provided
 in a report format.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION
 Text classification typically involves three major tasks including data
 preparation, training and testing. Data preparation involves obtaining a
 corpus of pre-classified data and training involves training a classifier
 on a corpus of pre-classified data. Testing includes testing the
 classifier with some subset of the pre-classified data set aside for this
 purpose.
 The process of generating training vectors of the present invention can be
 divided into three steps:
 1. Feature definition: Typically this involves breaking the text up into
 tokens. Tokens can then be reduced to their stems or combined to
 multi-word terms.
 2. Feature count: Typically this involves counting the frequencies of
 tokens in the input texts. Tokens can be counted by their absolute
 frequency, and several relative frequencies (relativized to the document
 length, the most frequent token, square root, etc.).
 3. Feature selection: This step includes weighting features (e.g.,
 depending on the part of the input text they occur in: title vs. body),
 filtering features depending on how distinctive they are for texts of a
 certain class (filtering can be done by stop word list, based on in-class
 vs. out-class frequency etc.).
 The present invention provides tools for all these tasks. The approach used
 here is to allow for flexibility and uniformity by using ASCII
 configuration files that are shared in all three steps involved. The
 programs used in the three steps also use the same plug-in DLLs for
 processing (e.g., the rule application DLL) or are at least compiled using
 the same C++ classes or other languages.
 Referring now to the drawings, and more particularly to FIG. 1, there is
 shown a block diagram of the general layout of the present invention. More
 specifically, the present invention includes raw annotated input data
 document collection means 10 which collects raw data from an application
 and submits the raw data to a data preparation module 12. The raw data is
 then prepared and split into two components. One component prepared for
 testing and training while the other component is submitted directly to a
 testing module 30 in order to determine whether the labels associated with
 the prepared data of the other component falls into any class, as
 described below.
 In other words, the data preparation module 12 submits the prepared data to
 the test data collection module 16 and the training data document
 collection module 14. The test data document collection module 16 submits
 the data to be tested to the testing module 30, while the training data
 module 14 submits data for training to the feature extraction module 18.
 The feature extraction module 18 is divided into a feature definition
 module 18a and a feature selection module 18b, each having their own
 configuration files, 18c, 18d, respectively. The feature definition module
 18a, in embodiments, breaks the text up into tokens, which can then be
 reduced to their stems or combined to multi-word terms. The feature
 selection module 18b weights the features (e.g., depending on the part of
 the input text they occur in: title vs. body). In further embodiments, the
 feature selection module 18b filters features depending on how distinctive
 they are for texts of a certain class.
 The extracted data from the feature definition module 18a is submitted to
 the feature vector module 20 where the extracted data is provided in a
 vector format, such as a feature count table. This data may then be
 submitted back to the feature extraction module 18, where the feature
 selection module 18b further reduces and/or alters the data and places it
 into a reduced feature count table in the reduced feature vector module
 22. The reduced feature vector module 22 provides the data in a simpler
 vector format that uses less disk space and is easier to process at a
 later time. The vector data is then submitted to a machine learning module
 24 where an algorithm is applied to the data.
 At this stage, the present invention stores the various data in a decision
 tree form, rule form or a vector form in module 28, which may store the
 data in various formats such as a directory tree, vectors, etc. The
 testing module 30 then tests the data and provides, in embodiments, a
 precision, recall, accuracy or other statistic analysis of the tested
 data, as described in detail below. The testing module 30 submits the test
 data to a test report module 32, where a report on the test data is
 provided.
 The modules of the present invention are interchangeable with modules that
 perform the same function, but in a different manner. For example, the
 machine learning module may be either a rule based engine, a vector based
 engine and a multiplicative update based algorithm engine
 In the practice of the invention, and more specifically (with reference to
 FIG. 1), since the task of training for text categorization has several
 stages, the present invention saves the output of each stage for later
 use. If different settings have to be tested for parts of the process,
 only the steps affected by the new settings have to be redone. This is
 important as text categorization often involves huge amounts of data, and
 the user does not want, for example, to re-parse 5 MB of text, just to
 "quickly" try out an option in the last step of training.
 The toolkit of the present invention stores the various options in a
 directory tree in the decision tree module 28 of FIG. 1. That way, the
 various runs with different settings can be structured more easily.
 Typically, this step corresponds to a directory level in the tree below
 the input data.
 The following sections describe the tools and procedures used in the three
 main classification tasks of the present invention, and further refer to
 FIG. 1.
 Training
 The training task follows the three steps described above, i.e., feature
 definition, feature count and feature selection. Usually, training data is
 delivered as one or more (text) files, where each file may contain any
 number of documents, which are annotated with class information and
 possibly a document identifier.
 Starting from this, the following steps are performed:
 Filtering out unwanted categories.
 Splitting the data into training and test data.
 Acquiring information about the data set.
 Feature definition and counting program.
 Feature selection program.
 The feature definition performs a process which extracts the text to be
 used for training from an SGML file or other file (can be text from
 different tags, e.g., TEXT and HEADER). It thereafter extracts the class
 label(s) and tokenizes the texts. In embodiments, the feature definition
 also performs stemming, abbreviation expansion, names or term extraction
 etc., thereby defining the features to be used. The process then computes
 the feature counts in various ways, such as computing the class and
 overall counts for the features.
 Thereafter, an output is obtained in a feature count table with one column
 for each defined feature (features occurring in different sections of the
 input are counted separately) and one line for each input document. The
 feature count table is processed in either the complete feature vector
 module 20 or the reduced feature module 22. Also provided are one line for
 each defined class and one overall summary line. Each cell in this table
 contains several different counts for the feature (absolute count plus
 several relative counts). This representation (as described with reference
 to FIG. 2) is designed to be as information rich as possible so that
 various training runs using different counting, weighting or filtering
 strategies do not have to revisit the input text.
 The feature selection module 18b performs a process which selects which
 type of word count (absolute, binary or a relative count) to use. After
 this selection three steps of computation are executed:
 1. Filtering features, for example, using a stop word list or filtering on
 word frequencies (absolute/relative, threshold/in-class out-class).
 2. Weighting features, for example, by the section of the input text they
 occurred in (e.g., Body vs. Header).
 3. Merging features, for example, merging all features from different
 sections of the input text into one feature (as an intermediate output,
 this results in a feature value table). Usually this has to be done one
 time for each class one wants to train on. Finally, the feature value
 table is written to disk. The format of the output can be adapted for
 different machine learning programs.
 The output of the merging feature function is a table with vectors suitable
 as input for the chosen machine learning program as referred to in FIG. 1
 as the provided in the reduced feature vector module 22.
 Testing
 Testing uses the fraction of the input text set aside in the training step.
 The test program takes a file in the SGML tagged format as input and
 consults the configuration file (the same used during training). The
 testing program also does the same feature definition steps (using the
 same plug-in DLLs) and uses the same counts, filters, weights and merging
 as defined in the configuration file 18d. The resulting feature table for
 the document is then processed using the classifier learned in the
 learning step. The result is a (possibly empty) set of proposed classes
 for the document, which is then compared with the class(es) annotated for
 the document in the SGML file.
 Detailed statistics of precision and recall (overall, per class, etc.) may
 be written to disk.
 Application
 To apply the training results to a new document, the same configuration
 file as performed in the training and testing modules of FIG. 1 is
 consulted. The application applies the rules (or vectors) generated in the
 training step to the new document and prints the categories predicted by
 the rules (vectors) to the screen. That is, the testing module 30 compares
 class labels assigned by the classifier (i.e., of the prepared dat
 preassigned class labels of the testing data from the module 16.
 By way of example, the application step typically is integrated into an
 application (e.g. a mail routing/answering application like Lotus Notes).
 In order to accomplish this, a DLL/shared library based classification API
 is provided. The text from these applications does not have to be in an
 SGML format, such that an application using any classification API can
 feed the text directly to the classification engine. The application
 program feeding the classification API has to, in embodiments, flag
 sections of the input text consistent with the tags used in training. The
 actual classification application is using the same source code that is
 used in the test program.
 Directory Hierarchy
 In preferred embodiments, the data used and produced by the toolkit of the
 present invention is organized in a specific directory hierarchy as
 provided in the decision tree module 28 of FIG. 1. To organize the data in
 this manner serves a two-fold purpose, namely, (i) allowing the toolkit to
 make assumptions about input data which is essential to keep the number of
 switches down to a manageable level and (ii) by imposing a certain
 organization on all users, it also helps the user to find data that was
 produced by another user. For example purposes only, the directory of the
 present invention may include, but is not limited to:
 1. The toolkit root directory: This directory may contain the major data
 directories as sub-directories. It also may contain a directory to store
 files common to all data sets (such as a stop-word list, e.g.) and a
 default data directory that contains default initialization files. This
 directory may also contain the programs that make up the toolkit as a
 whole. The root directory can also be set with an environment variable.
 2. The data directories: The data directories, in preferred embodiments,
 contain the training and testing data. Other files in this directory may
 also be relevant to the data set as a whole, e.g., a list of all
 categories to be trained on, if not all categories are considered. As
 subdirectories, the data directories contain feature definition
 directories. If, for example, the data are processed with a number of
 different tokenizers, or with and without name and term extraction, then
 different subdirectories for these different feature definition steps may
 be created. This is useful if only one feature definition strategy is ever
 used, or a particular one is used most of the time. The data directories
 may be organized hierarchically.
 3. Feature definition directories: Before a feature definition run, this
 directory contains only one file, an initialization file for the toolkit
 feature definition engine. During a run, a feature count table for the
 training data is created. Subdirectories may be created for each distinct
 feature selection strategy.
 4. Feature selection directories: Each feature selection directory contains
 an initialization file. After a run, it may also contain a word count
 file, i.e., a feature count table restricted to the features defined for
 this run. The subdirectories depend on the classification engines chosen
 for training. If text output was specified, then there is a directory, for
 example, text_output. For the classifiers, there may be other specific
 directories.
 5. Classifier directories: The classifier directories are typically empty
 of data, but also may contain data in certain circumstances. If binary
 files are not used, but classifier specific training files are used, then
 these files are in the classifier directory. As with all classifiers, the
 present invention supports some parameters to be set for training,
 subdirectories for individual training runs will be created.
 6. Parameter directories: These directories contain the results of
 training. That is, the rule file generated either directly, or as a
 translation from a decision tree. It may also contain the report file
 generated by the testing module 30 and submitted to the test report module
 32. Furthermore, it may contain some temporary files created by the ML
 algorithm. They may be useful for debugging purposes.
 The Training and Testing Script
 This section describes the top-level script that may be used to drive
 preparation, training and testing in a uniform and easy manner. A detailed
 description of the individual tools and how to run them outside the
 toolkit framework is not essential to the understanding of the present
 invention. However, in embodiments, all the tools display usage
 information when called without arguments.
 Switches to Control Directory Names
 To work with the toolkit script, the directories containing the data and
 initialization files should preferably be organized in the manner
 described above. This enables the script to organize the produced data in
 a perspicuous manner. The user receives a warning if directories are
 missing, and the present invention may create the missing directories.
 The script may perform minimal checks on the parameters to the directory
 switches. Those strings may contain alpha-numeric characters, dashes (-)
 and underscores (_).
 Environment Variables
 To work properly, the present invention relies on several environment
 variables. Some are only used internally, but the following may be set by
 the user, for example:
 TOOLKITBASEDIR: This optional variable can hold the (constant) base
 directory where all Toolkit files are located.
 TOOLKITOS: You need to tell the toolkit which operating system it is
 running under.
 TMP or TEMP: This variable tells the script where to generate temporary
 files in the training phase.
 Feature Definition
 Before the toolkit actually runs the feature definition program of the
 feature definition module 18a, it will check that all required files and
 directories are present. In setup mode, the present invention may also
 copy missing .ini files from default locations. If an .ini file already
 exists, the user can decide if (s)he wants to keep it or not. Setup will
 not actually run feature definition, so the use may have the opportunity
 to edit the default .ini file.
 The output of feature definition is a feature count table file, the input
 to feature selection. The file will be written to specified directories.
 Training
 In training mode, a machine learning (ML) algorithm is applied to the data
 files produced in the feature selection module 18b. Training is usually
 performed on the binary files. These binary files first need to be
 translated to a file format that the ML algorithm understands. To increase
 speeds in a network, these temporary training files are generated locally
 on the machine where training takes place. Thus, only the small binary
 files need to be transmitted over the network. Under Aix, the present
 invention checks for a TMP or TEMP variable set by the user. If such a
 variable is not set, then the user needs to specify a temp directory on
 the command line with the -tempdir parameter.
 Data Access Rules
 The following data access rules apply during training. For example, assume
 that the user is working on class "X". The script first looks if there is
 a binary directory, and if so, it generates data in a temporary directory,
 immediately deleting the data after training. This practice not only saves
 space, it is also faster when training on a machine other than the one
 that contains the data. In that case, the huge vector files need not be
 moved over the network, only the comparatively small binary ones.
 If there is no binary directory, the script looks in the classifier
 directory for the files X.par (the parameter file) and X.slq (the data
 file). If these do not exist, execution is halted.
 Input Document Collection (SGML) Format
 In preferred embodiments, the toolkit tools uses an SGML inspired text file
 format for storing and annotating the input files; however, other files
 are equally contemplated for use with the present invention. It is SGML
 based in so far as it used SGML like tags (e.g. &lt;TAGNAME&gt; text &lt;/TAGNAME&gt;)
 to mark units of the text. In embodiments, it is not full SGML since a
 definition file is not required or used.
 A toolkit input file may contain more than one document and all toolkit
 tools may work on more than one of those input files. This makes it easy
 to specify the document collection one wants to train/test on.
 For training and testing, there must be, in preferred embodiments, a tag
 with the pre-assigned categories from which the training algorithm should
 learn the categorization. The default name for that tag is preferably
 &lt;