Classification method and apparatus

• US 6,976,207 B1
• Filed: 04/27/2000
• Issued: 12/13/2005
• Est. Priority Date: 04/28/1999
• Status: Expired due to Term

• Current Assignee: Hyland Switzerland, Sarl
• Original Assignee: SER Solutions Incorporated (Atos SE)
• Inventors: Urbschat, Harry, Ruján, Pal
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Schlaifer, Jonathan D.
• Application Number:
  US09/561,196
• Time in Patent Office: 2,056 Days
• Field of Search: 715/500, 707/6, 707/5, 707/4, 707/3, 707/2, 707/1
• US Class Current: 715/234
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for building a classification model for classifying unclassified documents based on the classification of a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, and said method comprising the following steps: representing each of said plurality of documents by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space; representing the classification of said already classified documents into classes by separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class.

Claims

1. A method for building a classification model for classifying unclassified documents based on the classification of a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, and said method comprising the following steps:

processing said plurality of documents according to a plurality of classification schemes;

representing each of said plurality of documents in each of said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space;

representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.

3. The method of claim 1, wherein said step of separating said vector space further comprises:

creating a Voronoi-tessellation of said n-dimensional vector space.

5. The method of claim 1, wherein said finite set of symbols is one or more of the following:

the ASCII-set of characters,

a set of Chinese characters, and wherein a terms is one or more of the following;

a word formed by a sequence of one or more of said symbols,

a sequence of words respectively formed by a sequence of one or more of said symbols.

6. The method of claim 1, further comprising:

calculating a maximum margin surrounding said hyperplanes in said vector space such that said margin contains none of the vectors contained in the subspaces corresponding to said classification classes.

9. The method of claim 1, further comprising:

refining said classification model by a renewed calculation of said classification model by including further documents which have been classified as belonging to one of a said plurality of classes or by expanding said vector space by the incorporation of one or more additional dimensions corresponding to additional terms.

11. The method of claim 1, further comprising:

generating a plurality of sets of classification classes by generating a plurality of separations of said vector space into a corresponding set of subspaces such that each set of subspaces forms a classification model which corresponds to the classification of said documents.

12. The method of claim 1, wherein said classification model is used for indexing a database such that an index corresponds to a classification class or an intersection of classes in a plurality of classification schemes.

14. The method of claim 2, said method being applied for performing one of the following:

filtering the output of a computer system, in particular the output of a query on a database, a file directory system or an internet search engine, such that only the output elements which are in accordance with one or more selected classes form the filtered output;

automatically assigning or routing a document to a directory or a routing path, by assigning or routing said document to the directory or the routing path which corresponds to one of a plurality of classes used to classify directories or routing paths;

ordering documents according to their relevance by using said classification scheme for classifying documents into classes which correspond to the relevance of the documents being contained in a certain class;

analyzing, categorizing or archiving one or more unclassified documents, particularly a large set of unclassified documents such as the contents of a library, by classifying and/or ordering them according to said classification scheme;

checking the manually performed classification of one or more documents to identify inconsistencies or errors in said manual classification by comparing the result of an automatic classification according to one of the preceding claims with said manually performed classification.

2. A method for the classification of a document digitally represented in a computer into one of a plurality of classes in each of a plurality of predefined classification schemes, said document respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said method comprising the steps of:

representing said document by a vector of n dimensions, said n dimensions spanning up a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector;

classifying said document into one of said plurality of classes in each of said classification schemes by determining, for each of said classification schemes, into which of a plurality of subspaces said vector falls, said subspaces being formed by separating said vector space spanned up by said n-dimensional vector through one or more hyperplanes to define said subspaces such that each subspace corresponds to one of said plurality of classes for each of said classification schemes.

4. The method of claim 2, wherein said step of separating said vector space further comprises:

creating a Voronoi-tessellation of said n-dimensional vector space.

7. The method of claim 2 for automatically classifying an unknown document, said method comprising:

calculating the location of said vector in said subspaces by calculating the distance of said vector from said hyperplanes;

annotating a classification to said document or to its corresponding vector based on the result of said calculation.

8. The method of claim 2, further comprising:

calculating a confidence level for the classification of a document based on the distance between the vector representing said document and said hyperplanes and further based on the maximum margin surrounding said hyperplanes.

10. The method of claim 8, further comprising one or both of the following:

listing the automatically classified documents according to their confidence value;

refining the classification scheme by selecting the document with the lowest confidence level or the document whose confidence level is below a certain threshold for repeatedly calculating the classification scheme based on the correct classification of the selected document.

13. A method of selecting, filtering, or retrieving one or more documents from a set of documents, said method comprising:

classifying said set of documents according to claim 2; and

selecting, filtering or retrieving the documents which belong to a certain classification class or to certain classification classes.

15. An apparatus for classifying a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said apparatus comprising:

means for processing said plurality of documents according to a plurality of classification schemes;

means for representing each of said plurality of documents in each said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space; and

means for representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.

16. An apparatus for classifying a document digitally represented in a computer into one of a plurality of classes in each of a plurality of predefined classification schemes, said document respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said method classifying said document as belonging to one of a plurality of classes, said apparatus comprising:

means for representing said document by a vector of n dimensions, said n dimensions spanning up a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector; and

means for classifying said document into one of said plurality of classes in each of said classification schemes by, for each of said classification schemes, determining into which of a plurality of subspaces said vector falls, said subspaces being formed by separating said vector space spanned up by said n-dimensional vector through one or more hyperplanes to define said subspaces such that each subspace corresponds to one of said plurality of classes defined by a corresponding one of said plurality of classification schemes.

17. A software tool embodied on a computer-readable medium for building a classification model for classifying unclassified documents based on the classification of a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, and said software tool comprising the following:

computer program code for processing said plurality of documents according to a plurality of classification schemes;

computer program code for representing each of said plurality of documents in each of said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space;

computer program code for representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.

18. A software tool embodied on a computer-readable medium for the classification of a document digitally represented in a computer into one of a plurality of classes in each of a plurality of classification schemes, said document respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said method classifying said document as belonging to one of a plurality of classes, and said software tool comprising the following:

computer program code for representing said document by a vector of n dimensions, said n dimensions spanning up a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector;

computer program code for classifying said document into one of said plurality of classes in each of said classification schemes by determining into which of a plurality of subspaces said vector falls for each of said classification schemes, said subspaces being formed by separating said vector space spanned up by said n-dimensional vector through one or more hyperplanes to define said subspaces such that each subspace corresponds to one of said plurality of classes.

19. A computer readable medium having embodied thereon computer program code, said computer program code comprising:

a computer program code portion for processing a plurality of documents according to a plurality of classification schemes;

a computer program code portion for representing each of said plurality of documents in each said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space;

a computer program code portion for representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.

20. A computer readable medium having embodied thereon computer program code, said computer program code comprising:

a computer program code portion for representing a document by a vector of n dimensions, said n dimensions spanning up a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector;

a computer program code portion for classifying said document into one of said plurality of classes in each of a plurality of predefined classification schemes by determining into which of a plurality of subspaces said vector falls for each of said classification schemes, said subspaces being formed in each of said classification schemes by separating said vector space spanned up by said n-dimensional vector through one or more hyperplanes to define said subspaces such that each subspace corresponds to one of said plurality of classes in each of said classification schemes.

21. A computer-readable medium comprising computer program code for building a classification model for classifying unclassified documents based on the classification of a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said computer program code comprising:

a computer program code portion for processing said plurality of documents according to a plurality of classification schemes;

a computer program code portion for representing each of said plurality of documents in each said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space; and

a computer program code portion for representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.

22. A computer-readable medium comprising computer program code for the classification of a document digitally represented in a computer into one of a plurality of classes in each of a predefined plurality of classification schemes, said document respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, said method classifying said document as belonging to one of a plurality of classes, said computer program code comprising:

a computer program code portion for representing said document by a vector of n dimensions, said n dimensions spanning up a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector; and

a computer program code portion for classifying said document into, for each of said classification schemes, one of said plurality of classes in a respective one of said classification schemes by determining into which of a plurality of subspaces said vector falls, said subspaces being formed by separating said vector space spanned up by said n-dimensional vector through one or more hyperplanes to define said subspaces such that each subspace corresponds to one of said plurality of classes for each of said classification schemes.

23. A data structure being stored on a computer-readable medium, said data structure representing a classification model for classifying unclassified documents based on the classification of a plurality of documents which respectively have been classified as belonging to one of a plurality of classes, said documents being digitally represented in a computer, said documents respectively comprising a plurality of terms which respectively comprise one or more symbols of a finite set of symbols, wherein said classification model is generated by the steps of:

processing said plurality of documents according to each of a plurality of classification schemes;

representing each of said plurality of documents in each of said classification schemes by a vector of n dimensions, said n dimensions forming a vector space, whereas the value of each dimension of said vector corresponds to the frequency of occurrence of a certain term in the document corresponding to said vector, so that said n dimensions span up a vector space; and

representing the classification of said already classified documents into a plurality of classes corresponding to respective ones of said plurality of classification schemes by, for each of said classification schemes, separating said vector space into a plurality of subspaces by one or more hyperplanes, such that each subspace comprises one or more documents as represented by their corresponding vectors in said vector space, so that said each subspace corresponds to a class defined by a corresponding one of said plurality of classification schemes.