KR20110057421A - Apparatus and method for classifying documents in a single class category - Google Patents

Abstract

The present invention relates to a document classification technique of a single class category, which performs indexing from a set of learning documents, selects important features, and incrementally selects association rule candidates in a depth-first search or a breadth-first search method based on the generated matrix. After generating and generating an association rule learning model from the generated association rule candidates, the document is classified using the generated association rule learning model. According to the present invention, the accuracy of document classification can be improved by applying the association rule search method to the document classification method and using the extracted association rule as a feature for document classification.

Description

Apparatus and method for classifying documents in a single class category {APPARATUS AND METHOD FOR CLASSIFICATING DOCUMENT OF SINGLE CALSS CATEGORY}

The present invention relates to a technique for performing document classification, and in particular, by using an association rule extracted by applying an association rule search method to a document classification method as a feature for document classification, A device and method for classifying documents in a suitable single class category.

The present invention is derived from a study conducted as part of the IT growth engine technology development project of the Ministry of Knowledge Economy [Task management number: 2008-S-020-02, title: WebQA technology development].

= <w1, w2,…, wm>로 표현되고 클래스 c_i에 속한다. 학습 문서 집합은 각각의 학습 문서마다 분류하고자 하는 범주에 대해 레 이블이 표기된 S = {(d₁,c₁), (d₂,c₂),…, (d_m,c_m)} 집합으로 표현된다. 문서 분류의 목적은 학습 문서 집합 S로부터 분류 규칙을 찾아내어, 분류를 위한 새 문서 집합이 입력되었을 때 정확도 높게 분류하는 것이다.In general, document classification is a limited set of document categories C = {c ₁ , c ₂ ,... , c _n } and a set of learning documents, the learning documents are represented by (d _i , c _i ) pairs. Document d _i is a vector of m attributes of vocabulary

= <w1, w2, ... , wm> and belongs to class c _i . The set of learning documents is labeled S = {(d ₁ , c ₁ ), (d ₂ , c ₂ ),... , (d _m , c _m )}. The purpose of document classification is to find classification rules from the learning document set S and classify them with high accuracy when a new document set for classification is entered.

As the document classification method, a naive base classifier, a support vector machine, a maximum entropy classifier (ME), and the like are widely used.

The naive base classifier is a probabilistic classification method based on Bayes' theorem and Naive Bayes independence assumption. Theorem of the base means that document d must be assigned to document category class c _i to achieve high classification accuracy. The naive base independence hypothesis allows us to quickly calculate the probability of P (W _j | c _i ) assuming that the probability between words is independent given the class category in which the document should be classified. The naive base classifier is less widely used than other classification methods, but it is widely used because of its simple implementation and fast learning speed.

The support vector machine is a classification method that uses statistical classification and regression analysis to increase the accuracy of document classification. The support vector machine finds and uses a hyper-margin hyperplane among a number of candidate planes that can classify document category classes, given a set of learning documents. In addition, ME classifiers and conditional random fields (CRF) classifiers are used.

Recently, associative rule mining or associative rule learning, a data mining technique that systematically and automatically finds statistical rules or patterns in large-scale stored data, is applied to document classification. Research is also in progress.

Association rule mining is the mining of sets of items that occur frequently, given the minimum amount of support and minimum confidence specified by the transaction database and the user. In general, a consumer who purchases bread and milk at a supermarket purchases butter, so it can be used as a method for mining consumer's {bread, milk}-> butter pattern from a large transaction database.

This association rule mining technique, when there are non-overlapping items, transaction T = (TID, X) has a TID identifier and an item set X.

A transactional database is a collection of transactions. An item set of k elements is represented by k-itemset. The support of item set X is the number of transactions including item set X in the transaction database, which is represented as support (X). It is expressed frequently that the support of the item set X is higher than the minimum support designated by the user. The confidence confidence that X will also occur when X occurs (X-> Y) is expressed as the conditional probability that a transaction with X will contain Y.

In addition to support and reliability, various association rule measurement methods, such as lift, conviction, and chi-square (χ2), have been proposed, and a method for automatically classifying multi-category documents by multiple association classification rules extracted using such association rule exploration techniques. We used associative rules to efficiently classify categories of documents with multiple category labels and multiple category labels.

At this time, FP-growth (Frequent pattern growth) was applied to the association rule mining algorithm as a method for classifying multi-class category documents, and the association rule was mined using the frequency pattern tree. Is stored as a prefix tree.

In the document classification method according to the related art operating as described above, there is no proposal for a method for classifying documents belonging to a single class category in addition to the method for classifying documents in a multi-class category.

As such, association rule mining can be applied to documents of a single class category as in the case of classifying documents of a multi-class category. However, two problems arise when applying association rule mining to a document classification simply. First, setting the minimum support too low creates a very large set of items. Second, if the minimum support is set too high, the frequency of occurrence is low, but there is a problem that the important item set is missing.

Accordingly, the present invention provides an apparatus and method for classifying a document of a single class category, which can perform accurate document classification by applying the association rule search method to the document classification method and using the extracted association rule as a feature for document classification. .

In addition, the present invention, by newly defining the class support (class support), class all confidence for the correlation evaluation of the association rules to generate a set of important and frequent items when learning association rules to improve document classification The present invention provides a single class category document classification apparatus and method for constructing a learning model for classifying documents and performing document classification using association rules when a new document for document classification is input.

According to an embodiment of the present invention, an apparatus for classifying a document of a single class category selects features from a set of learning documents, generates a matrix with the selected features, and based on this, the association rule candidates in a depth-first search or a breadth-first search method. And an association rule learner for generating an association rule learning model from the generated association rule candidates, and a document class category classifier for classifying documents for the input document set using the generated association rule learning model. do.

On the other hand, the association rule learning unit, the index and feature selection pre-processing unit for selecting the features by performing an index from the learning document set, the horizontal feature matrix with the selected features, and the horizontal feature matrix to the vertical feature matrix It characterized in that it comprises a data layout conversion unit for converting to.

The association rule learner may be configured to incrementally extract an item set having a length longer than the previous item set in a depth-first search or a breadth-first search method starting from one item set having one element.

The association rule learner may calculate class support, which is a probability of randomly extracting a specific set of items belonging to a document class, calculate a class total reliability that is the minimum reliability for the specific set of items in the document class, and calculate Confirming the minimum class support and the minimum class overall reliability in the class support and the class overall reliability, generating an item set in which the class support and the class overall reliability are higher than the minimum class support and the minimum class overall reliability, and generating the item set Repeatedly, when the item set is no longer generated, the final item set may be configured as the association rule learning model.

The document class category classifier generates a candidate item set including elements that are not duplicated from the generated matrix, and a preprocessor for indexing a class document set to select features to generate a matrix. Selecting a first item set having the largest number of undiscovered items in the set as an element, selecting a second item set having the longest length in the first item set, and then applying class support in the second item set. A document item set generation unit that selects a third item set having the highest value, and a class category classification unit that classifies the input document into a document class category having the highest probability of belonging to a document class with respect to the third item set; It is characterized by.

According to an embodiment of the present invention, a method of classifying a document of a single class category includes: selecting features by performing an index from a learning document set, generating a matrix using the selected features, and depth-first from the generated matrix. Incrementally generating association rule candidates in a search or breadth first search manner, generating an association rule learning model from the generated association rule candidates, and classifying documents using the generated association rule learning model Process.

The process of generating the matrix may include generating a horizontal feature matrix based on the selected features and converting the horizontal feature matrix into a vertical feature matrix.

The process of incrementally generating the association rule candidates may include incrementally extracting an item set having a length longer than the previous item set in a depth-first search or a breadth-first search method starting from one item set having one element. It features.

The generating of the association rule learning model may include a first process of calculating class support, which is a probability of randomly extracting a specific set of items belonging to a document class, and a minimum reliability of the specific set of items in the document class. A second process of calculating class overall reliability, a third process of checking minimum class support and minimum class overall reliability in the calculated class support and class overall reliability, and the class support and class overall reliability are the minimum class support and the minimum A fourth process of generating an item set having a higher reliability than a class overall reliability, and a process of configuring a final item set as the association rule learning model when the item set is no longer generated by repeating the first to fourth processes. It is characterized by including.

The classifying the document may include generating a matrix by selecting indexes and qualities from the classified document set, generating a candidate item set including elements that are not overlapped with the generated matrix, and generating the candidate item. Selecting a first item set having the largest number of undiscovered items in the set as an element, selecting a second item set having the longest length in the first item set, and selecting the second item set And selecting a third item set having the highest class support in the class, and classifying the input document into a document class category having the highest probability of belonging to a document class. It is done.

According to the document classification apparatus and method of a single class category according to the embodiment of the present invention as described above has one or more of the following effects.

According to the apparatus and method for classifying a document of a single class category according to an embodiment of the present invention, an accuracy of document classification may be improved by using an association rule exploration method when classifying a document belonging to a single class category as a feature for classifying a document.

In addition, associative rule data constructed using class support and class-wide confidence can be used as an important feature for classification other than the word of words or stemming results used in existing document classification methods. It takes much less time than the conventional support vector machine, so it can be used efficiently for large data classification.

Advantages and features of the present invention and methods for achieving them will be apparent with reference to the embodiments described below in detail with the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but can be implemented in various different forms, and only the embodiments make the disclosure of the present invention complete, and the general knowledge in the art to which the present invention belongs. It is provided to fully inform the person having the scope of the invention, which is defined only by the scope of the claims. Like reference numerals refer to like elements throughout.

In describing the embodiments of the present invention, if it is determined that a detailed description of a known function or configuration may unnecessarily obscure the gist of the present invention, the detailed description thereof will be omitted. In addition, terms to be described below are terms defined in consideration of functions in the embodiments of the present invention, which may vary according to intentions or customs of users and operators. Therefore, the definition should be based on the contents throughout this specification.

Combinations of each block of the accompanying block diagram and each step of the flowchart may be performed by computer program instructions. These computer program instructions may be mounted on a processor of a general purpose computer, special purpose computer, or other programmable data processing equipment such that instructions executed through the processor of the computer or other programmable data processing equipment may not be included in each block or flowchart of the block diagram. It will create means for performing the functions described in each step. These computer program instructions may be stored in a computer usable or computer readable memory that can be directed to a computer or other programmable data processing equipment to implement functionality in a particular manner, and thus the computer usable or computer readable memory. It is also possible for the instructions stored in to produce an article of manufacture containing instruction means for performing the functions described in each block or flow chart step of the block diagram. Computer program instructions may also be mounted on a computer or other programmable data processing equipment, such that a series of operating steps may be performed on the computer or other programmable data processing equipment to create a computer-implemented process to create a computer or other programmable data. Instructions that perform processing equipment may also provide steps for performing the functions described in each block of the block diagram and in each step of the flowchart.

In addition, each block or step may represent a portion of a module, segment or code that includes one or more executable instructions for executing a specified logical function (s). It should also be noted that in some alternative embodiments, the functions noted in the blocks or steps may occur out of order. For example, the two blocks or steps shown in succession may in fact be executed substantially concurrently or the blocks or steps may sometimes be performed in the reverse order, depending on the functionality involved.

In an embodiment of the present invention, a learning model for document classification is constructed by newly defining class support and class-wide reliability for evaluating correlation of association rules to generate a set of important and frequent items when learning association rules. When a new document for document classification is entered, document classification using association rules is performed.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram illustrating the structure of a single category document classification apparatus through association rule learning according to an embodiment of the present invention.

Referring to FIG. 1, the apparatus for classifying a single category document may include an association rule learner 100 performing a preprocessing procedure for generating an association rule learn model, and an association rule learning model generated through the association rule learner 100. A document class category classifying unit 150 for classifying a new document using 130). Here, the association rule learner 100 may include a term index and feature selection preprocessor 102, a data layout converter 106, a candidate k-item set generator 110, and a high frequency / critical k-item set. The document class category classifier 150 includes a term index and feature selection preprocessor 152, a document item set generation unit 154, a class category classifier 156, and the like. .

Specifically, as a preprocessing step for generating the association rule learning model, the term index and feature selection preprocessor 102 in the association rule learning unit 100 first receives the training document set 120. Here, the learning document set 120 is a document to be used for machine learning, and this document is composed of words or phrases as in a general sentence or e-mail, and is a word as a basic feature.

The term index and feature selection preprocessor 102 extracts a term vector in the form of a bag of words by indexing each learning document from the input learning document set 120. In this case, since the extracted term vectors are represented by a large sparse matrix, feature selection is performed to remove non-essential terms.

The term index and feature selection preprocessor 102 receives the learning document set 120 and outputs a term-document matrix of m × n, that is, a horizontal feature matrix 104, and each document d _i is a vector. It is composed.

In the document vector of Equation 1, w _ij represents a weight with respect to the j th term of the document d _i .

The output horizontal feature matrix 104 is generated as a result of the preprocessing of the term index and feature selection preprocessor 102, where m non-overlapping terms are columns of the matrix and n documents are lines of m × n term-documents. It is a matrix. That is, it consists of terms included in the document.

The data layout converter 106 inversely reconstructs rows and columns of the m × n term-document matrix that is the horizontal feature matrix 104 to generate the vertical feature matrix 108.

The candidate k-item set generating unit 110 receives the vertical feature matrix 108 and uses the class support and the class all confidence to search for a width first from the set of one item. Generate a set of k items that are important and frequent with breadth-first search or depth-first search.

In document classification, transaction database D in association rule exploration can be viewed as a document collection, with each transaction T mapped to a document instance. In order to use the association rule learning method as a feature selection method for document classification, each set of items must have a statistical weight for each document class c _i . To this end, embodiments of the present invention use class support.

The class support of the item set X is a ratio of a transaction in which the item set X is included in the class category c _i in the entire transaction D, and can be expressed by Equation 2 below.

In addition, the class support is a probability of randomly extracting an item set X belonging to the document class c _i , and the sum of all class support of the item set X is equal to the class support of the item set X in the entire transaction D.

Class all confidence of item set X is the minimum confidence in document class c _i . That is, all association rules generated from item set X have a value equal to or greater than the class-wide confidence.

In Equation 3, the denominator is the maximum number of transactions having the item set X as the power set in the entire transaction D. The maximum number of item sets X occurs when item set X consists of one element. Therefore, we do not calculate the class-wide confidence for all the elements in the set of itemsets X, but only for the set of items X.

The high-frequency / important k-item set extractor 112 recursively applies the minimum depth of class support and the minimum class by applying a depth-first search method to the input data composed of the vertical feature matrix 108 from one item set composed of one element. Extract item sets with values greater than the overall confidence. Each item set also has a transaction identifier and class frequency, which are information needed to calculate class support for each document class c _i .

The high frequency / critical k-item set extracting unit 112 obtains the intersection of the transaction identifiers for all two item candidate sets having two elements from the one item set having one element, and calculates the number of elements included in the intersection. Set to the class frequency. After obtaining class support and class-wide confidence for all document classes c _i , two-item candidates with values greater than minimum class support and minimum class overall confidence are extracted.

After all two item candidate sets have been extracted, the above process is repeated recursively to extract a three item set having three elements. This process is repeated until no more item sets are generated, and finally, the output item set is output to the association rule learning model 130, and the output association rule learning model 130 is the item set having class support. It consists of F

Meanwhile, the document class category classifying unit 150 uses the extracted association rule learning model 130 as the document class c _i having the highest probability that the document belongs when the newly classified classification document set 140 is input. Categorize the document.

In more detail, the term index and feature selection preprocessor 152 performs the same function as the term index and feature selection preprocessor 102 of the association rule learner 100. Print a vertical feature matrix from the required document.

을 생성한다. 멱집합 L을 점증적으로 구성하기 위한 조건은 아래 <수학식 4>와 같다. C는 이미 발견된 아이템 집합을 나타내며, X의 부분집합이다.The document item set generation unit 154 receives a vertical feature matrix extracted from a document requiring classification, where a new document has X = {l ₁ , l ₂ ,... , l _n }. Power set consisting of non-overlapping elements from set X for classification

. The condition for incrementally constructing the set L is as shown in Equation 4 below. C represents the set of items already found and is a subset of X.

Given document class c _i , found item set C, and candidate item set L, an item set L 'with the largest number of undiscovered items is selected, and the longest length in item set L' is selected. The item set L "having the highest class support is selected from the item set L".

The class category classification unit 230 classifies the input document into a document class category having the highest probability of belonging to the document class c _i .

2 is a flowchart illustrating an operation procedure of a single category document classification apparatus through association rule learning according to an embodiment of the present invention.

Referring to FIG. 2, in step 200, the term index and feature selection preprocessor 102 in the association rule learner 100 performs feature selection by indexing the learning documents of the input learning document set 120 and then horizontally. The term vector is extracted as the product feature matrix 104. The layout of the horizontal feature matrix 104 is converted into the vertical feature matrix 108 through the data layout converter 106.

In step 202, the candidate k-item set generator 110 receives the vertical feature matrix 108 and uses the class support and the class-wide confidence, which is important as a breadth-first search or a depth-first search from a single set of items. Create a frequent set of k items.

In addition, the high frequency / critical k-item set extractor 160 generates an item set in which the class support and class overall reliability calculated in step 204 are higher than the minimum class support and the minimum class overall reliability, and repeats these steps, step 206. In FIG. 3, the finally generated item set is configured as the association rule learning model 130.

Accordingly, the term index and feature selection preprocessor 152 in the document class category classification unit 150 generates a matrix by selecting indexes and features for the classified document set input in step 208, and generates a document item set generation unit in step 210. In operation 154, a set of non-overlapping elements is generated from the generated matrix, and the set is incrementally configured to selectively extract an item set having a length longer than that of the previous item set.

Afterwards, the class category classification unit 156 classifies the input document into a document class category having the highest probability of belonging to the document class based on the item set extracted in step 212.

3A to 3B are diagrams illustrating a class support and class overall reliability calculation method according to an embodiment of the present invention.

Referring to FIG. 3A, ten transactions T1 to T10 having five items, such as A, B, C, D, and E, show an example of a document set belonging to two classes C1 and C2.

That is, it can be seen that transactions T1 to T5 have C1 class, T6 to T10 as C2 class, T1 has A, B items as C1 class, and T2 has A, B, C items as C1 class.

Referring to FIG. 3B, class support and class total support are calculated and output for each class C1 and C2 in all item sets that may be configured as five items, such as A, B, C, D, and E. FIG.

4 is a diagram illustrating an association rule extraction method for a learning document set according to an embodiment of the present invention.

Referring to FIG. 4, after converting the horizontal feature matrix 400 to the vertical feature matrix 402, all two item sets that can be configured for one item set are generated to generate each class support and class overall reliability. 404 and then generate 406 two item sets ab, bc, be, ce that satisfy the minimum class support and the minimum class overall reliability. Then recursively generate three sets of items bce.

5 is a diagram illustrating a document classification method according to an embodiment of the present invention.

Referring to FIG. 5, an example of classifying a class category to which a document belongs is configured by constructing a set L from an index feature {a, b, c} extracted from a test document X requiring classification.

As described above, the apparatus and method for classifying a document of a single class category according to an embodiment of the present invention newly defines a class support and a class-wide reliability for evaluating the correlation of the association rule, thereby making it important and frequent when learning the association rule. By creating a high item set, we build a learning model for document classification, and perform document classification using association rules when a new document for document classification is entered.

While the present invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiments, but is capable of various modifications within the scope of the invention. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be defined not only by the scope of the following claims, but also by those equivalent to the scope of the claims.

1 is a block diagram showing the structure of a single category document classification apparatus through association rule learning according to an embodiment of the present invention;

2 is a flowchart illustrating an operation procedure of a single category document classification device through association rule learning according to an embodiment of the present invention;

3A to 3B are diagrams illustrating a class support and class overall reliability calculation method according to an embodiment of the present invention;

4 is a diagram illustrating an association rule extraction method for a learning document set according to an embodiment of the present invention;

5 is a diagram illustrating a document classification scheme according to an embodiment of the present invention.

<Description of Signs of Major Parts of Drawings>

100: association rule learning unit 102: term index and feature selection preprocessor

104: horizontal feature matrix 106: data layout converter

108: vertical feature matrix 110: candidate k-item set generator

112: high frequency / important k-item set extractor

130: Association rule learning model

150: document class category classifier 152: term index and feature selection preprocessor

154: document item set generation unit 156: class category classification unit

Claims (10)

Select features from a set of training documents, generate a matrix with the selected features, generate association rule candidates based on the depth-first search or breadth-first search, and generate an association rule learning model from the generated association rule candidates. Association rule learning department to say, A document class category classifier for classifying documents for an input document set using the generated association rule learning model. Document classification device of a single class category comprising a. The method of claim 1, The association rule learning unit, An index and feature selection preprocessing unit configured to select features by indexing the set of learning documents, and generate a horizontal feature matrix using the selected features; A data layout converter for converting the horizontal feature matrix into a vertical feature matrix Document classification apparatus of a single class category comprising a. The method of claim 1, The association rule learning unit, A document classifier of a single class category, characterized by incrementally extracting an item set having a length longer than the previous item set in a depth-first search or a breadth-first search method starting from one item set having one element. The method of claim 1, The association rule learning unit, Calculate class support, which is the probability that a particular set of items in a document class will be randomly extracted, Calculate a class overall reliability which is the minimum reliability for the specific set of items in the document class, Confirm the minimum class support and the minimum class overall reliability from the calculated class support and the class overall reliability, Generate an item set in which the class support and the class overall confidence are higher than the minimum class support and the minimum class overall confidence, When the item set is no longer generated by repeating the generation of the item set, document classification apparatus of a single class category, characterized in that the final item set to configure the association rule learning model. The method of claim 1, The document class category classification unit, A pre-processing unit for generating a matrix by selecting features by indexing the set of classification documents; Generate a candidate item set consisting of non-overlapping elements from the generated matrix, select a first item set having the largest number of undiscovered items as elements in the candidate item set, and in the first item set A document item set generation unit for selecting a second item set having the longest length and then selecting a third item set having the highest class support value from the second item set; A class category classification unit classifying the input document into a document class category having the highest probability of belonging to a document class based on the third item set Document classification apparatus of a single class category comprising a. Selecting features by indexing from a set of learning documents, Generating a matrix with the selected qualities; Incrementally generating association rule candidates from the generated matrix in a depth-first or breadth-first search manner; Generating an association rule learning model from the association rule candidates generated; Classifying documents using the generated association rule learning model Document classification method of a single class category, including. The method of claim 6, The process of generating the matrix, Generating a horizontal feature matrix based on the selected features; Converting the horizontal feature matrix into a vertical feature matrix Document classification method of a single class category comprising a. The method of claim 6, Incrementally generating the association rule candidates, A method of classifying a document of a single class category, comprising extracting an item set having a length longer than the previous item set by using a depth-first search or a breadth-first search method starting from one item set having one element. The method of claim 6, The process of generating the association rule learning model, A first step of calculating class support, which is a probability of randomly extracting a specific set of items belonging to a document class; Calculating a class total reliability, which is a minimum reliability for the specific item set, in the document class; A third process of confirming minimum class support and minimum class overall reliability in the calculated class support and class overall reliability; A fourth process of generating an item set in which the class support and the class overall reliability are higher than the minimum class support and the minimum class overall reliability; When the item set is no longer generated by repeating the first to fourth processes, a process of configuring a final item set as the association rule learning model Document classification method of a single class category comprising a. The method of claim 9, The process of classifying the document, Generating a matrix by selecting features and indexing from a set of classified documents; Generating a candidate item set composed of non-overlapping elements from the generated matrix; Selecting a first item set having the largest number of undiscovered items as elements in the candidate item set; Selecting a second item set having the longest length from the first item set, Selecting a third item set having the highest class support in the second item set; Classifying the input document into a document class category having a highest probability of belonging to a document class based on the third item set; Document classification method of a single class category comprising a.

Images