An effective dimensionality reduction method for text classification based on TFP-tree

1 Introduction

Searching or extracting useful information from tremendous amount of data on the Web could boils down to analyzing and classifying features and texts, which are the backbones of increasingly Web application such as opinion mining [1], Web page classification [2, 3], filtering spam [4, 5] and so on. Text classification, as a very important part, has attracted many researchers’ attention. Conventional PU (Positive and Unlabeled) text classification, also known as semi-supervised classification, utilizes labeled and unlabeled data to build a classifier. It usually contains two-step. The first step is collecting reliable negative examples (also called RN) from unlabeled dataset (identified by U). The second step is training classifier using positive examples (identified by P), reliable negative examples and unlabeled examples. Some classification techniques are statistical-based such as Bayes classification (naïve Bayesian classifier and simple Bayes classifier) [6] and some classification techniques are geometrical-based such as SVM [7]. There are also some rule-based classification methods such as decision tree induction [8], IF-THEN rules for classification. However, the texts to be processed, more often than not, are represented as feature vectors, i.e. D = {x₁, x₂, …, x _m }. For example, the feature x₁ can be “classification”, and the feature x₂ can be “learning”. The parameter m denotes the total number of the features in a dataset instead of the total number of the features in a document. When a term x _i is not included in a document, its corresponding feature weight is zero, but it still takes up its own memory space. If so, the algorithms will process a lot of high-dimensional data, which probably leads to high computational cost. Some techniques have been developed to remove redundant or irrelevant features such as removing stop words. Removing stop words plays a role in dimensionality reduction in text classification. It is not sufficient to just applying stop words removing in the process of dimensionality reduction.

To solve this problem, this paper proposes a dimensionality reduction method for text classification based on a novel text frequent pattern generation technique called TFP-tree. Traditional frequent patterns are usually extracted from transaction or relational database and can be used to show the relations among all kinds of items. Frequent patterns can also be used in text classification. For examples, in the economic domain, the features occurring frequently can be “statistic”, “market”, “dollar”, “stock”, etc. In the sport area, the features occurring frequently can be “NBA”, “football”, “race”, “Kobe Bryant”, etc. Intuitively, the features in economic domain and the features in sport area are negative correlation. The typical features occurring in economic domain would probably not appear in sport area or the occurrence frequency would be low. The features in the same class should have some correlation in most cases. Due to the relation among the extracted features, the irrelevant or redundant features can be removed effectively according to their correlation shown in frequent patterns. Frequent itemset mining methods have been applied to many research areas. However, it is still a new attempt to apply them to text classification. Moreover, as we know, the extracted reliable negative examples play an important role in the performance of classifier. So, we also conduct frequent pattern mining on reliable negative examples from the perspective of dimensionality reduction and performance improvement. Motivated by this hypothesis, we extend the conventional two-step PU text classification method to three-step method. The first step, collecting reliable negative examples, remains unchanged. It is not the focus of this paper, so we will not explain this part in detail. You can find the details in our previous work [9–11]. In the second step, a new method for generating frequent patterns is put forward. Also, the benefits and experimental results of dimensionality reduction are illustrated in detail later. In the third step, the final classifier is obtained by iteratively training classifier using the text frequent patterns obtained from the second step. Since training data and testing data do not have the same data distribution, additional processing is needed. We conduct experiments on three datasets to verify the effectiveness and efficiency of our proposed method. The experimental results show that our proposed dimensionality reduction method for text classification outperforms traditional semi-supervised text classification methods both on precision and efficiency with the help of applying frequent patterns generated using TFP-tree.

The contributions of this paper are summarized as follows:

We propose a new concept called TFP-tree to deal with high dimensional data. It is used to generate positive frequent patterns and negative frequent patterns, which could be applied to conduct dimensionality reduction effectively.

The outline of this paper is organized as follows. We first review the related work in Section 2. Section 3 explains how to construct TFP-tree and how to generate frequent patterns. Section 4 illustrates the process of constructing the classifier. Several comprehensive experiments are performed to evaluate our proposed method in Section 5 in which experimental settings, performance metrics, and results are provided. Section 6 draws the conclusion.

2 Related work

Text classification and frequent patterns generation both have a long history. Text classification aims to automatically collect, organize and obtain the information which users are interested in. Researchers put forward a lot of methods to improve the accuracy and efficiency [12, 13]. However, most of automatic text classification techniques need to handle the high-dimensional data such as SVM, which is quite effective but takes up a lot of time and space.

So far, many researchers have delved into PU text classification and proposed a number of approaches. Support Vector Machines is a very famous text classification technique proposed by Cortes and Vapnik [7]. Since then, there are many other improvements and applications showing up. It is a two-step classification method which can be used in PU text mining. The first step is collecting reliable negative examples (also called RN) from unlabeled dataset (identified by U). Feature selection and feature reduction are major problems of this step. They have been widely studied in PU text mining. Wang et al. [14] put forward a feature selection method which made a lot of innovation ideas in the field of feature reduction. The core feature set improves the classification effect a lot. Saidani and Rassoul [15] proposed a weighted genetic algorithms which optimized the feature selection process for sentiment analysis. They combined a supervised weighting method and stochastic search methods to generate feature subset, which can extracts and selects more efficient features. Jiang and Wang [16] introduced a clustering feature selection method which selected final feature subset based on the separabilities of features. The second step is constructing the classifier using positive examples and reliable negative examples collected by the first step. In the second step, Baccianella et al. [17] put forward a new feature selection method using micro-documents which broke down each training document of length k into k training micro-documents. It makes the features more sensitive to term frequency. Bayes theorem, as another method for classification is based on statistics [6]. It combined posterior probability and class-conditional independence to predict the class label of a document. Pan et al. [18] utilized transfer learning for text classification to tackle the challenge of different data distribution. It aims to deal with the situation that source domain and target domain are related but different in accordance with original features. Tang and Liu [19] proposed a novel feature selection method for high dimensional data which used social context to social data during selecting features. The effectiveness of linked data is shown in their work. However, there are lots of noisy and incomplete data in the whole Web environment. How to get rid of it to improve the effectiveness and efficiency of feature selection is still a challenging problem.

Frequent patterns play an important role in mining the relationship among massive amount of data. Most of frequent pattern mining algorithms use support-confidence framework. The first algorithm for mining frequent patterns was the Apriori algorithm presented by Agrawal and Srikant [20]. There are also a lot of variations of Apriori. They need to generate a huge amount of candidates, which takes a lot of time and space. Another approach, called FP-growth (Frequent Pattern growth), presented by Han et al. could mine frequent patterns without generating the candidates [21]. Cheng et al. [22, 23] applied discriminative frequent patterns in classification. It uses the feature selection to remove the features which are included in the discriminative and redundant frequent patterns. Also, many algorithms have been proposed to deal with the PU classification task which makes use of mining frequent patterns or association rules. The CBA (Classification Based on Associations) [24], CMAR (Classification based on Multiple Association Rules) [25], and CPAR (Classification based on Predictive Association Rules) [26] are three of them and also our baseline algorithms. CBA iteratively constructs the classifier using the generated association rules. Those rules make up a decision list which is similar to the decision tree. It utilizes the generated rules to classify the testing tuples, which seems to be better than C4.5. CMAR constructs the FP-tree only through scanning the database just twice. CPAR generates far fewer association rules than CMAR and CBA. However, it outperforms CMAR and CBA on accuracy and efficiency with large amount of training set. Our proposed CTFP is different from the three methods above. The strategies for mining the frequent pattern and constructing the classifier are both different. As CBA, CMAR, and CPAR use frequent patterns to generate association rules and are rule-based method for classification, we choose these three methods and two clustering-based classification methods as our baseline algorithms.

3 Generating frequent patterns using TFP-tree

Text classification is the process of assigning predefined category labels to new documents on the basis of the classifier learnt from training examples. Each document can be in multiple, exactly one, or no category at all. By using machine learning technique, the objective is to learn classifier from examples that do the category assignments automatically. Most text classification tasks can be formulated in a way to use binary classifiers. And, multiclassification can also be regarded as a variant of the binary classification. That is, for a task with n classifications, there will be n binary classifiers. Consider an L (L > 2) categories classification task, the method called the one-versus-all works uses L classifiers. When training the ith classifier, ith category document examples are treated as positive examples, and the documents of all the rest of classes can be treated as the negative examples. When classifying a document, the class label choice depends on the largest value yielded by classifier.

As described in Section 1, the whole procedure contains three steps: (1) extracting reliable negative documents, (2) generating text frequent patterns, and (3) constructing text classifier. In the first step, we choose 1-DNFC [11], which uses a threshold lambda to make up a defect of traditional 1-DNF and corrects a bug of 1-DNFII, to identify the reliable negative documents. Suppose the training data D = [ d 1 , d 2 , … d n ] T = [ x 1 T , x 2 T , … x m T ] ∈ R n × m , where n is the number of the documents in the data set and m is the dimensionality in the whole data collection. In 1-DNFC algorithm, the input data would be positive documents P and unlabeled documents U, which feature set is assumed to be x₁, x₂, ..., x _m , and x _i is a word feature that occurs in P ∪ U. A feature is defined as a positive feature when it occurs in the positive set P more frequently than in the unlabeled set U and absolute frequency of the feature in P should reach a specific threshold. The algorithm of 1-DNFC is described as follows. freq (x _i , P) is the number of documents where feature x _i appears in P.

Generating frequent patterns is one of the most important steps in our proposed method. The basic idea is to extract the representative features according to the importance of the features appearing in both positive and negative document sets, so the data dimensionality can be reduced to save the computational cost. FP-growth approach [27], as we know, has already been used for mining frequent itemset in order to avoid generating a costly candidate sets, especially mining the transaction database. However, applying FP-growth into text classification is a relatively novel research method. An obvious difference between transaction and a huge number of texts is that the item in one transaction only occurs once but the words in one document may occur several times. In this paper, we do not focus on FP-growth. Instead, some additional procedures are added into original FP-growth approach. We split all documents, denoted as D, into several paragraphs PGs(D), which include the same number of documents. That is, each dataset yields a series of paragraphs including several documents in order to avoid the situation that too many branches in a tree. In that situation, it is difficult to generate useful frequent patterns. The number of document, also called paragraph length (denoted by parameter n), will be discussed in detail in the following section. We will explain it later.

Let’s look at a motivating example to illustrate how to use the TFP-growth to conduct text mining and classification. Assume that d ={ x₁, x₂, …, x _m  } be a set of words representing the document d. What’s more, given a document d _i  = {(x_i1 : w_i1) , (x_i2 : w_i2) , …, (x _im  : w _im )} , w _im is used to represent the occurrence times of word x _im that shows up in document d _j . Suppose there are five documents containing in a paragraph PG₁ as shown in the first column in Table 1. Each document is scanned to calculate the occurrence times of each word as shown in the third column. Then we begin constructing the TFP-tree as follows. After creating the root node “null” of the tree, the documents are scanned the first time in the order that shows in Table 1. In the table of Fig. 1, the words are listed in the order of descending occurrence frequency just as processed in TFP-tree (Word_ID). The first document of Table 1 is “{x₁ : 2, x₃ : 3, x₄ : 1}”. The first branch of the tree is constructed with three nodes x₁, x₃ and x₄ in the order that shows in Fig. 1. The following steps are different from those in constructing original FP-tree. Scan the set of paragraphs a second time. There is only one document that covers x₁, x₃ and x₄. So, we mark <x₁ : 2> , < x₃ : 3 >, and <x₄ : 1> in each node of the branch instead of <x₁ : 1> , < x₃ : 1 > and <x₄ : 1>. Next, scan the second paragraph {x₁ : 1, x₂ : 2, x₃ : 1}. It contains x₁, x₃ and x₂ in the order of Word_ID, which results in a branch where x₂ is linked to x₃. Then the value of node x₁ becomes 3 (2 + 1 =3). With this method, the TFP-tree is built after scanning all the documents shown in Table 1. By now, all the leaf nodes are marked with a number which is called support. Notice that the support count of x₃ is 3, which is the occurrence number that x₃ shows in d₁ instead of just incrementing the support count by 1. In addition, < x₁, x₃>also appear in d₂ and d₄, and the occurrence numbers are 1 and 2, respectively. So, the node x₃ is marked with six (3 + 1 +2 = 6) in the end. In this way, we get the TFP-tree as shown in Fig. 1 as follows. The way of generating the frequent patterns from TFP-tree are as same as the method of generating frequent patterns from original FP-tree, which is not detailed in this paper. According to the TFP-tree above, for item x₅, we could obtain the generated frequent patterns: {x₁, x₅ : 2}.

OPEN IN VIEWER

Fig.1

A TFP-tree covering the words showing up in paragraph PG₁ (documents d₁ to d₅).

In this section, we will focus on how to construct the classifier using the generated frequent patterns. Moreover, we define an IU (Intersection-Union) framework to deal with the situation where the inconsistence of data distribution exists.

Before constructing TFP-tree, document pre-processing and feature extracting are needed. After mining frequent patterns from TFP-tree, text classification is transformed to deal with a small number of low-dimensional data instead of handling a lot of high dimensional data. In the training set, there are a small proportion of positive documents (denoted by P) and a large proportion of unlabeled documents (denoted by U). The frequent patterns generated from the positive document set are called positive frequent patterns (denoted by PFP). Similarly, the frequent patterns generated from the reliable negative documents are called negative frequent patterns (denoted by NFP). It is easy to understand that the frequent patterns in positive examples may be the representative words in the documents we are interested in. Similarly, the words in the negative frequent patterns are probably not included in that kind of documents. So, in the documents of the training data set, we remove all the features which do not occur in the frequent pattern set. The features showing up in the frequent pattern set are regarded as “useful” features in the process of classification and vice versa. However, we do not simply remove the features showing up in the frequent pattern set. As we know, frequent patterns contain k-itemset, where k could be one, two, three and more. It is easy to know that almost every 1-itemset belongs to frequent pattern set. Any feature, that satisfies the min_sup requirement, would be added to 1-itemset. Once it is added to frequent pattern set, it would be removed from the training set. Using 1-itemset to represent the specific-topic document is meaningless. Therefore, we do not treat 1-itemset as the frequent pattern. The positive documents, which get rid of the features not occurring in PFP and NFP, are marked by DP. Also, the negative documents, which get rid of the features not occurring in NFP and PFP, are marked by DN. DP, DN and unlabeled documents make up the whole training set.

The whole dataset contains the training dataset and test dataset. After conducting dimensionality reduction in training dataset, most irrelevant and redundant features have been removed from the training dataset, which results in the inconsistence between training data and test data. Different from the previous methods for constructing SVM classifier, the training data and the test data have the same data distribution in traditional SVM classifier. It means that the dimensionality of the training data and the test data is the same. Then, how to make the dimensionality of each document remain the same after removing those redundant features. We give a simple example to illustrate it. Traditional support vector and the maximum margin like Fig. 2 are used to show how to obtain the maximum margin. However, they are used to show how to reach the consistency of data distribution. In Fig. 2, the nodes like “⚫” represent the features of positive document examples. And the nodes like “◍” indicate the features of negative document examples. All the nodes are the features of the documents after removing the redundant and irrelevant ones. For example, suppose the original feature set includes x₁, x₂, x₃, x₄, x₅ and x₆. After conducting dimensionality reduction, node A is denoted as {x₁ : w₁, x₂ : w₂, x₃ : w₃, x₄ : w₄} (w _i  ≠ 0, i = 1, 2, 3, 4) and node B is denoted as {x₁ : w₁, x₂ : w₂, x₃ : w₃, x₅ : w₅} (w _i  ≠ 0, i = 1, 2, 3, 5). All the features, say, x₁, x₂, x₃, x₄ and x₅, belong to the frequent pattern set.

OPEN IN VIEWER

Fig.2

Support vectors and the maximum margin.

Figure 2 shows an example of support vectors and maximum margin. Only the support vector that has the same dimensionality could be used to support vector machine. How could node A and node B be shown in the same hyperplane when the dimensionalities are the different? In this paper, we create a new dictionary and obtain the union of each feature of the frequent patterns to get the same data distribution. If there are only two documents, say, A and B, in the training set, then the dictionary would be x₁, x₂, x₃, x₄, x₅. The feature x₆, which is regarded as an irrelevant feature, is removed from the feature set. The dimensionalities of node A and node B are both five with the corresponding term weighting values. The feature representation of node A would be {x₁ : w₁, x₂ : w₂, x₃ : w₃, x₄ : w₄, x₅ : 0} and the feature representation of node B would be {x₁ : w₁, x₂ : w₂, x₃ : w₃, x₄ : 0, x₅ : w₅}. As we can see, a lot of redundant and irrelevant features have been removed while creating the frequent patterns. However, there exists missing redundant and irrelevant features which would results in the mismatch with the data distribution of test data. Each document in the test data still has the original data dimensionality which is higher than that of the new generated documents after removing the redundant features. To get the final category of the under-classified documents, we plug DP and DN into SVM to find the maximum margin hyperplane. SVM has been applied to text classification over the past decades and achieved good performance.

Then, how to deal with this kind of inconsistence between the new training data and the test data? Here, we propose an IU (Intersection-Union) framework to solve this problem. Note that we have already built a dictionary which contains all the features of the frequent patterns no matter positive ones or negative ones when we construct the classifier. It can be easily to get intersection between the features in the dictionary and the features in the test documents. Suppose dictionary vector Dic → contains 10 features as shown in Equation 1 as follows. In Equation 2, Test _ D → is the vector of a test document and the w _i denotes the frequency of word x _i . Dic → = { x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 , x 9 , x 10 }(1) Test _ D → = { x 1 : w 1 , x 2 : w 2 , x 3 : w 3 , x 5 : w 5 , x 7 : w 7 , x 9 : w 9 , x 11 : w 11 , x 17 : w 17 }(2)

In order to extract the relevant and useful information, in the intersection part, we just intersect the vector Dic → with the vector Test _ D → according to the vector component x _i . Then we get a new vector which could be relatively low-dimensional as shown in Equation 3.

New _ D → = Dic → ( x ) ∩ Test _ D → ( x ) = { x 1 : w 1 , x 2 : w 2 , x 3 : w 3 , x 5 : w 5 , x 7 : w 7 , x 9 : w 9 }(3)

Until then, a certain amount of redundant features have been removed. It is also needed to get the union between the obtained features and the original features in the dictionary. In the union part, to reach the consistence of the data distribution between the test data and the training data, the union of New _ D → and D ı c → is created to restore the missing features, which is described in Equation 4. The implementation of how to use TFP-tree to conduct text classification is detailed in Algorithm 2.

Final _ D → = New _ D → ( x ) ∪ Dic → ( x ) = { x 1 : w 1 , x 2 : w 2 , x 3 : w 3 , x 4 : w 4 , x 5 : w 5 , x 6 : w 6 , x 7 : w 7 , x 8 : w 8 , x 9 : w 9 , x 10 : w 10 } = { x 1 : w 1 , x 2 : w 2 , x 3 : w 3 , x 4 : 0 , x 5 : w 5 , x 6 : 0 , x 7 : w 7 , x 8 : 0 , x 9 : w 9 , x 10 : 0 }(4)

DP, DN and Dic are used as input. We first expand each document to make them have the same dimensionality. For each document in the test data, we extract the common feature with the dictionary and reserve the corresponding weight. Then, the missing features are restored. DPL and DPN are applied to construct the classifier. Finally, the test data can be labeled as the corresponding category. Also, the dimensionality inconsistence between the training data and test data can be solved.

We have presented a novel method for text classification based on frequent patterns generated from TFP-tree. This method utilizes a TFP-tree to capture frequent patterns from datasets. After constructing TFP-tree, text classification could be transformed to deal with a relatively low-dimensional data instead of high-dimensional data. There are a lot of researches on text classification and how to generate and make use of frequent patterns. However, combining frequent patterns from positive documents set and negative documents set, and applying them into the area of Web mining are a relatively new attempt. The experimental results suggest that our proposed method is able to mining and classifying data effectively and efficiently from the datasets which has a small positive training data. Besides, it shows that our proposed method outperforms the previous state-of-the-art methods on accuracy, time complexity and space complexity.