# A New Feature Selection Method for Text Classification Based on Independent Feature Space Search

Authors: Yong Liu; Shenggen Ju; Junfeng Wang; Chong Su
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Feature selection method is designed to select the representative feature subsets from the original feature set by different evaluation of feature relevance, which focuses on reducing the dimension of the features while maintaining the predictive accuracy of a classifier. In this study, we propose a feature selection method for text classification based on independent feature space search. Firstly, a relative document-term frequency difference (RDTFD) method is proposed to divide the features in all text documents into two independent feature sets according to the features’ ability to discriminate the positive and negative samples, which has two important functions: one is to improve the high class correlation of the features and reduce the correlation between the features and the other is to reduce the search range of feature space and maintain appropriate feature redundancy. Secondly, the feature search strategy is used to search the optimal feature subset in independent feature space, which can improve the performance of text classification. Finally, we evaluate several experiments conduced on six benchmark corpora, the experimental results show the RDTFD method based on independent feature space search is more robust than the other feature selection methods.


---

## Body

## 1. Introduction

In the task of text classification, how to remove the noise in a large number of text documents, such as the irrelevant and redundant features, is a challenging topic. Therefore, the dimension reduction methods have been proposed to solve this problem, including feature extraction and feature selection. Feature extraction methods extract features from the new and the low-dimensional feature space that is transformed from original feature space, such as principal component analysis (PCA) [1], Linear Discriminant Analysis (LDA) [2], and so on. Feature selection methods that select a small subset from the original feature set by the different evaluation on feature relevance, there are two main models that deal with feature selection, namely, wrapper models and filter models [3]. Wrapper models apply the specific classifier to evaluate and select features, which can generate different feature sets [4], although wrapper models can find a better and nonredundant feature set by the classifier with cross validation [5], and nevertheless, in the case of the high-dimensional space, the wrapper models will consume more feature search time than the filter models [6]. In contrast to wrapper models, filter models only rely on various evaluation algorithms rather than classifiers [7], and moreover, in many cases, filter models can be applied to scale large datasets because of its high-efficiency processing speed [8]. Within filter models, feature ranking methods attempt to rank features according to feature relevance based on different evaluation [7], many related methods have been widely used in feature selection for text classification [9, 10], which can be categorized into three groups: document frequency (DF), term frequency (TF), and document-term frequency (DTF), among which many theories have been proposed, such as Chi-square (CHI) [10], information gain (IG) [10], term frequency based on information gain (TFIG) [11], Gini index [12], improved Gini index (IMGI) [13], normal term frequency based Gini index (GININTF) [14], discriminative power measure (DPM) [15], odds ratio (OR) [16], t-test based feature selection (TTFS) [17], document frequency (DF) [10], term frequency-inverse document frequency (TFIDF) [18], and improved TFIDF (IMTFIDF) [19]. CHI, IG, GINI, IMGI, DF, DPM, and OR belong to DF, and TTFS and TFIG belong to TF, and moreover, TFIDF and IMTFIDF belong to DTF. Note that the feature/features is equivalent to the term/terms in this study, such as features number is equivalent to terms number.The motivation behind this work is the following. We know that the feature ranking methods are often used for feature selection, which assign the feature weightings that are often normalized in the range (0, 1) to each feature [20], then rank the feature weightings in descending order, and finally, select the top N features by the feature weightings. Although the feature weightings reflect the importance of the features in feature set, they cannot guarantee to construct a better feature set for classification, and the main reason is the higher correlation between the features, which leads to the redundancy of the features [21], therefore, the feature ranking methods are difficult to obtain much gain [22]. If a feature is highly correlated not only to the class but also to other features, it is redundant and should be removed [8], and therefore, Minimum Redundancy-Maximum Relevance (mRmR) was proposed to minimize the correlation between features and maximize the relevance of the features with class, and it has significantly improved classification performance on five gene expressions data sets [21]. However, some learning algorithms use the redundant but correlated features, which obtain the better performance on some datasets [4]. Overall, we known that the relationship between the features is extraordinarily complex. Hence, if we excessively seek features of the lower redundancy or better purity can lead to some good features to be abandoned, which can cause the negative effect on classification.To sum up, we know that a good feature set should contain two important characteristics, one is the high class correlation of the features and the lower correlation between the features, the other is the moderate redundancy of the features. Therefore, our research focuses on finding a feature selection method that can meet both characteristics simultaneously.In this paper, we propose a novel and effective idea of feature selection and use the diagrams to illustrate the difference between this method and the general feature selection method. Note that we call others the feature selection method as the general selection method, except the new feature selection method proposed in this paper.Figure1 shows the process diagram of the general feature selection methods, which consists of four steps: step ① shows all features are added to the original features set, step ② represents the calculating of all features weighting, step ③ represents that all features are ranked in descending order according to the weighting of the features, and step ④ represents that top N features are selected from the feature set.Figure 1
Process diagram of the general feature selection methods. Note that the green circle represents each feature in feature set.Figure2 shows the process diagram of the new feature selection method, namely, the RDTFD method, step ① represents all features are added to the original features set. Step ② consists of two substeps. The first substep represents that all features are divided into the positive or negative feature subsets according to the positive or negative values of the weighting, which could improve the high class relevance of the features and reduce the correlation between the features, this step corresponds to equation (8) in Section 3.1. The second substep is designed to reduce the search range of feature space and maintain appropriate feature redundancy, which corresponds to equation (9) in Section 3.1. Step ③ represents that all features of the positive feature subset are ranked in descending order by weighting, and all features of the negative feature subset are ranked in ascending order by weighting. Step ④ represents that the candidate feature subsets are selected from two independent feature subsets with some search strategies, as detailed in Section 3.2.Figure 2
Process diagram of the RDTFD method. Note that the green circle represents each features in features set, the orange circle represents each feature of the positive features, and the blue circle represents each feature of the negative features.Comparing with the general feature selection method, the RDTFD method has two major differences. Firstly, the RDTFD method divides the original feature set into two independent feature subsets, and however, the general selection method generates a feature set. Secondly, the RDTFD method selects feature subsets by some search strategies from two independent feature subsets, which are flexible and scalable, but the general selection method is only selects topN features from a feature set.In this paper, the application scenario of spam filtering is given to illustrate the advantages of the proposed feature selection method over the general feature selection method. As we known, the content-based filtering methods can be used to improve the accuracy of e-mail classification by machine learning, such as Naive Bayesian classifiers [23, 24], K-nearest neighbor [25], neural networks [26, 27], Support Vector Machines [28, 29], Boosting [30, 31], Three-way decisions [32, 33], and so on. The Naive Bayesian method is often used, because of its high efficiency and accuracy. Moreover, the support vector machine attempts to reduce the generalization error by using the constraints of the decision boundary and achieve the better performance [34].The remaining paper is divided into following main sections: In Section2, we review related work on feature selection methods. In Section 3, we proposed a relative document-term frequency difference (RDTFD) method and the particle swarm optimization (PSO) algorithm based on independent feature space search to achieve high performance for text classification. In Section 4, we describe the experimental results. In Section 5, we conclude our work with some possible extensions.


## 2. Related Work

### 2.1. Chi-Square (CHI)

The chi-square test is one of the most useful statistical methods, which not only provides the information with respect to the significance of any observed differences, but also provides the information of categories difference [35]. Compared to the t-test, the chi-square test does not assume the data to meet the normal distribution, and the null hypothesis of the independence will be rejected when there is a significant difference between observed frequency and expected frequency [36]. The feature measurement is defined to be(1)χ2ti=maxck∈s,hχ2ti,ck,χ2ti,ck=Naikdik−cikbik2aik+cikbik+dikaik+bikcik+dik,where N is the total number of documents in the corpus, aik is the number of documents in class ck that contains the feature ti, bik is the number of documents that contains the feature ti and does not belong to class ck, cik is the number of documents in class ck that does not contain the feature ti, and dik is the number of the documents that do not contain the feature ti and do not belong to class ck. When feature ti is independent of class ck, the chi-square will obtain 0 value. In addition, the chi-square value is normalized in the calculation process, which exaggerates the role of the low-frequency feature [10].


### 2.2. Information Gain (IG)

The information gain can be used to measure capability of information acquisition for class prediction by the presence or absence of a term in a document. If most of the terms do not appear in most class, the information gain value will incline to the case of term absence. The information gain of the termti is defined as follows [10]:(2)IGti=−∑ck∈s,hpcklogpck+pti∑ck∈s,hpcktilogpckti+pti¯∑ck∈s,hpckti¯logpckti¯,where s denotes spam class, h denotes ham class, pck is the probability of the documents in ck, pti and pti¯ are the probability that a document contains or does not contain ti, and pckti and pckti¯ are the conditional probability that a document in ck contains and does not contain ti.


### 2.3. Term Frequency-Based Information Gain (TFIG)

TFIG is an information gain method based on the term frequency, which can measure the amount of information obtained for class prediction by knowing one appearance, multiple appearances, or absence of a term in a document. The TFIG can be defined as follows [11]:(3)TFIGti=−∑ck∈s,hpcklogpck+pti¯∑ck∈s,hpckti¯logpckti¯+pt1∑ck∈s,hpckt1logpckt1+c×pt2∑ck∈s,hpckt2logpckt2,where t1 denotes the one time appearance of the term t, t2 denotes the multiple appearances of the term t, and c is constant parameter c≥1.


### 2.4. Improved Gini Index (IMGI)

The Gini index is a measurement of the purity of the term, the greater purity, the better classification performance. Gini Index can be demonstrated as follows:(4)GINIti=ptis2×psti2+ptih2×phti2,where ptis is the probability that the term ti occurs in spam class, psti is the conditional probability that an e-mail belongs to spam class when ti occurs, ptih is the probability that the term ti occurs in ham class, phti is the conditional probability that an e-mail belongs to ham class when the term ti occurs.


### 2.5.T-Test-Based Feature Selection (TTFS)

The algorithm is based on theT-test, which can measure the different distributions of the terms in relevant class and corpus. T-test can be defined as follows:(5)TTFSti,ck=tfki¯−tfi¯mk×si,Si2=1N−K∑k=1k∑j∈cktfij−tfki¯2,mk=1Nk−1N,where ck denotes spam or ham class, Nk is the number of e-mails in ck, k is the number of categories, tfki¯ is the average term frequency of the term ti in ck, tfi¯ is the average term frequency of the term ti in all e-mails, N denotes the number of all e-mails, and si denotes standard deviation within a class. If there is threshold θ, when TTFSti,ck<θ, which shows that tfi¯ has the same or similar mean value in the whole e-mails, in this case, the term has less discrimination capability for class ck, otherwise, it shows that the term has more discrimination capability for class ck.


### 2.6. Improved Term Frequency-Inverse Document Frequency (IMTFIDF)

According to the TFIDF, the term with smaller frequency in e-mails is a good distinguishing capability, otherwise, the term has a poor distinguishing capability, and however, this theory cannot effectively reflect importance of all the terms in practice. The improved TFIDF (IMTFIDF) was proposed [19], which is defined as follows:(6)IMTFIDFti,dj,ck=tfij×logNKi,ifMiMi+Ki>70%,where N denotes the number of document frequency in all e-mails, ck denotes spam or ham class, Ki is the number of e-mails which contain term ti but do not belong to ck, Mi is the number of e-mails which contain term ti and belong to ck, and tfij is the term frequency of the term ti in e-mail dj of ck. If Mi/Mi+Ki is bigger than 70%, then the term ti can well represent the text features of this class of e-mail documents, and otherwise, the ti will be abandoned.


### 2.7. Normal Term Frequency-Based Gini Index (GININTF)

Considering some drawbacks of using document frequency, GININTF was proposed for feature selection by term frequency [14], which is defined as follows:(7)GININTFti=∑ck∈s,hAti,ckMck2Ati,ckAti,ck+Bti,ck2,where Ati,ck is the total normalized term frequency of the term ti of e-mails that belongs to class ck, Bti,ck is the total normalized term frequency of the term ti of e-mails that does not belong to class ck, and Mck is the total number of e-mails belongs to class ck.


## 2.1. Chi-Square (CHI)

The chi-square test is one of the most useful statistical methods, which not only provides the information with respect to the significance of any observed differences, but also provides the information of categories difference [35]. Compared to the t-test, the chi-square test does not assume the data to meet the normal distribution, and the null hypothesis of the independence will be rejected when there is a significant difference between observed frequency and expected frequency [36]. The feature measurement is defined to be(1)χ2ti=maxck∈s,hχ2ti,ck,χ2ti,ck=Naikdik−cikbik2aik+cikbik+dikaik+bikcik+dik,where N is the total number of documents in the corpus, aik is the number of documents in class ck that contains the feature ti, bik is the number of documents that contains the feature ti and does not belong to class ck, cik is the number of documents in class ck that does not contain the feature ti, and dik is the number of the documents that do not contain the feature ti and do not belong to class ck. When feature ti is independent of class ck, the chi-square will obtain 0 value. In addition, the chi-square value is normalized in the calculation process, which exaggerates the role of the low-frequency feature [10].


## 2.2. Information Gain (IG)

The information gain can be used to measure capability of information acquisition for class prediction by the presence or absence of a term in a document. If most of the terms do not appear in most class, the information gain value will incline to the case of term absence. The information gain of the termti is defined as follows [10]:(2)IGti=−∑ck∈s,hpcklogpck+pti∑ck∈s,hpcktilogpckti+pti¯∑ck∈s,hpckti¯logpckti¯,where s denotes spam class, h denotes ham class, pck is the probability of the documents in ck, pti and pti¯ are the probability that a document contains or does not contain ti, and pckti and pckti¯ are the conditional probability that a document in ck contains and does not contain ti.


## 2.3. Term Frequency-Based Information Gain (TFIG)

TFIG is an information gain method based on the term frequency, which can measure the amount of information obtained for class prediction by knowing one appearance, multiple appearances, or absence of a term in a document. The TFIG can be defined as follows [11]:(3)TFIGti=−∑ck∈s,hpcklogpck+pti¯∑ck∈s,hpckti¯logpckti¯+pt1∑ck∈s,hpckt1logpckt1+c×pt2∑ck∈s,hpckt2logpckt2,where t1 denotes the one time appearance of the term t, t2 denotes the multiple appearances of the term t, and c is constant parameter c≥1.


## 2.4. Improved Gini Index (IMGI)

The Gini index is a measurement of the purity of the term, the greater purity, the better classification performance. Gini Index can be demonstrated as follows:(4)GINIti=ptis2×psti2+ptih2×phti2,where ptis is the probability that the term ti occurs in spam class, psti is the conditional probability that an e-mail belongs to spam class when ti occurs, ptih is the probability that the term ti occurs in ham class, phti is the conditional probability that an e-mail belongs to ham class when the term ti occurs.


## 2.5.T-Test-Based Feature Selection (TTFS)

The algorithm is based on theT-test, which can measure the different distributions of the terms in relevant class and corpus. T-test can be defined as follows:(5)TTFSti,ck=tfki¯−tfi¯mk×si,Si2=1N−K∑k=1k∑j∈cktfij−tfki¯2,mk=1Nk−1N,where ck denotes spam or ham class, Nk is the number of e-mails in ck, k is the number of categories, tfki¯ is the average term frequency of the term ti in ck, tfi¯ is the average term frequency of the term ti in all e-mails, N denotes the number of all e-mails, and si denotes standard deviation within a class. If there is threshold θ, when TTFSti,ck<θ, which shows that tfi¯ has the same or similar mean value in the whole e-mails, in this case, the term has less discrimination capability for class ck, otherwise, it shows that the term has more discrimination capability for class ck.


## 2.6. Improved Term Frequency-Inverse Document Frequency (IMTFIDF)

According to the TFIDF, the term with smaller frequency in e-mails is a good distinguishing capability, otherwise, the term has a poor distinguishing capability, and however, this theory cannot effectively reflect importance of all the terms in practice. The improved TFIDF (IMTFIDF) was proposed [19], which is defined as follows:(6)IMTFIDFti,dj,ck=tfij×logNKi,ifMiMi+Ki>70%,where N denotes the number of document frequency in all e-mails, ck denotes spam or ham class, Ki is the number of e-mails which contain term ti but do not belong to ck, Mi is the number of e-mails which contain term ti and belong to ck, and tfij is the term frequency of the term ti in e-mail dj of ck. If Mi/Mi+Ki is bigger than 70%, then the term ti can well represent the text features of this class of e-mail documents, and otherwise, the ti will be abandoned.


## 2.7. Normal Term Frequency-Based Gini Index (GININTF)

Considering some drawbacks of using document frequency, GININTF was proposed for feature selection by term frequency [14], which is defined as follows:(7)GININTFti=∑ck∈s,hAti,ckMck2Ati,ckAti,ck+Bti,ck2,where Ati,ck is the total normalized term frequency of the term ti of e-mails that belongs to class ck, Bti,ck is the total normalized term frequency of the term ti of e-mails that does not belong to class ck, and Mck is the total number of e-mails belongs to class ck.


## 3. Feature Selection Method Based on Independent Feature Space Search

### 3.1. Relative Document-Terms Frequency Difference (RDTFD)

In order to describe the RDTFD method clearly, we list the definition of the concept related to the frequency in Table1, including document frequency, term frequency, average term frequency, and term frequency distribution.Table 1
Definition related to frequency terms.
KeywordDefinitionDocument frequencyThe number of documents that contains the term in the datasetTerm frequencyThe number of the term in all documents of the datasetAverage term frequencyThe average number of the term in all documents of the datasetTerm frequency distributionThe number of the term in each document of the datasetTable2 shows the number of documents and the total number of terms in ham and spam datasets, it is worth noting that Dataset1 and Dataset2 including spam and ham datasets, respectively. Table 3 shows some samples and the corresponding document frequency, term frequency, average term frequency, and term frequency distribution in ham and spam datasets, respectively.Table 2
Datasets examples of spam and ham.
DatasetsSpamHamDocument numberTotal terms numberDocument numberTotal terms numberDataset 1510005500Dataset 2105000102000Table 3
Document frequency and terms frequency of term examples in dataset 1 and dataset 2.
DatasetsTermDocument frequencyTerm frequencyAverage term frequencyTerm frequency distributionSpamHamSpamHamSpamHamSpamHamDataset 1Investment535310.61,1,1,1,10,1,1,0,1Linguistic55105212,2,2,2,21,1,1,1,1Marketing551010222,2,2,2,22,3,2,1,2Dataset 2Debian10102020222,2,2,2,2,2,2,2,2,22,2,2,2,2,2,2,2,2,2Mailings1012010212,2,2,2,2,2,2,2,2,210,0,0,0,0,0,0,0,0,0Workshop10102020222,2,2,2,2,2,2,2,2,21,3,1,2,3,1,3,2,1,3As shown in Table3, when DF methods (CHI, IG, and IMGI) are applied, the term “mailings” can obtain the highest value of DF methods, which shows that “mailings” has a discriminative capability compared with others terms. Moreover, the document frequency of “mailings” in spam class is higher than that in ham class, which means that an e-mail document tends to spam class if it contains “mailings.” Further, although “marketing” and “linguistic” have the same document frequency,however, “marketing” has a higher average frequency in ham class, which means that it is more likely to appear in ham class than in spam class.Since “debian” and “workshop” have the same document frequency in spam and ham class, if DF methods such as IG is used, “debian” and “workshop” will be abandoned. In addition, according to TFFS method GININTF, “debian” and “workshop” will get the same GININTF value, which shows that “debian” and “workshop” cannot be identified as spam or ham class. However, the term frequency distribution of “workshop” is more variable in ham class than in spam class, and therefore, an e-mail document containing “workshop” will tend to spam class by using TTFS method, although TTFS method is interpretable and easy to implement. Nevertheless, the method is based ont-test, namely, the prior distribution of the data must conform to normal distribution, this assumption is not consistent with distribution of the real data [37], and hence, it cannot obtain the better performance for feature selection.In this section, we propose a relative document-terms frequency difference (RDTFD) method, and it considers not only the document frequency and term frequency, but also the number of documents and the total number of terms, which can construct a better model to measure the ability to identify spam or ham class for each term and it can be demonstrated as follows:(8)RTDFD=logdfti∈hamlogDNH×logtfti∈hamlogTNH−logdfti∈spamlogDNS×logtfti∈spamlogTNS,(9)if MAXdfti∈hamdfti∈ham+dfti∈spam,dfti∈spamdfti∈ham+dfti∈spam>0.7,where dfti∈ham denotes the document frequency of term ti in ham documents, dfti∈spam denotes the document frequency of term ti in spam documents, tfti∈ham denotes the term frequency of term ti in ham documents, tfti∈spam denotes that term frequency of term ti in spam documents, DNH is the number of ham documents, DNS is the number of spam documents, TNH is the total number of terms in ham documents, and TNS is the total number of terms in spam documents.Equation (8) is intended to address the content mentioned in the first substep of step 2 in Figure 2, which shows that when document and term frequency of term ti in spam class are very close to ham class, RDTFD value is approximately equals to zero, which means that term ti has a poor discrimination capability in spam or ham class. Therefore, the bigger positive RDTFD weighting represents a document that containing the term ti tends to ham class and the smaller negative RDTFD weighting represents a document that containing the term ti tends to spam class, which can construct two independent term subsets, namely, the terms of the positive weighting will be put into the subset of ham class and the terms of the negative weighting will be put into to the subset of spam class. For instance, in Table 2, since term “debian” has same document frequency, term frequency and distribution of term frequency, it has no discriminating capability in spam or ham class according to the typical DF and TF methods. However, the total terms number of documents contain “debian” in spam class more than in ham class, we know log10/log10×log20/log2000−log10/log10×log20/log5000>0, by which, a document contains “debian” will tend to ham class.Since the distribution of each term in the text is very complicated and cannot be accurately measured by a constant formula, we can delineate a general scope for the distribution of these terms, as long as the terms in this scope are better for text classification. Furthermore, to limit the search range of features can not only reduce the time cost of feature search, but also maintain appropriate feature redundancy. Thus, we propose equation (9) that makes the term ti be selected as the candidate term belonging ham or spam class; otherwise, the term ti will be abandoned, which is similar to that mentioned in [19]. In the experiment of this paper, when this equation (9) is satisfied, the text classification performance would be better.


### 3.2. Feature Search Strategy

From the step 4 in Figure2, we know that the candidate feature subsets are selected from two independent term spaces by some search strategies. Compared with other optimization algorithms, the parameter setting of particle swarm optimization (PSO) algorithm is convenient and the population is rich. In addition, the convergence speed of PSO algorithm is fast and it is suitable to search the high-dimensional feature spaces. Therefore, in this study, we apply the PSO algorithm as the search strategy for the feature selection method.The PSO was proposed by Kennedy and Eberhart in 1995, the original inspiration was from the behavior of birds flocking and fish schooling [38]. In our experiment, the PSO algorithm that can search the optimal term set by multi-iteration and is given as follows [39]:(10)vidt+1=w×vidt+c1×r1×pidt−xidt+c2×r2×pgdt−xidt,xidt+1=xidt+vidt,d=1,2,…,D.Figure3 shows the process of feature search strategy implementation, the dotted line rectangle can be viewed as a feature selection window, the red part is from S1 to Sn, which shows that the negative term weighting of spam is sorted in the ascending order, and the green part is from H1 to Hn, which shows that the positive term weighting of ham is sorted in the descending order. In addition, the movement of the feature selection window is controlled by two parameters, the first parameter is the width of the feature selection window that determines the number of terms for classification, the second parameter is the ratio of spam terms number to the terms number, which is in the interval (0,1) and generated by the PSO algorithm, note that the terms number includes the spam terms number and the ham terms number. In Figure 3, R1⟶Rm represents each ratio, and m denotes the particle number. The feature selection window will move back and forth between ham and spam term set by the ratio value, which can generate m candidate term subsets, and they can be fed to a specific classifier such as NB or SVM to select the optimal term set with the highest F1 values. For instance, when the width of feature selection window is set to 10, namely, N=10, it denotes 10 terms will be selected between spam and ham term subsets for spam filtering, and moreover, the ratio is set to 0.7, which denotes feature selection window will select 7 terms in terms of spam and 3 terms in terms of ham. In extreme cases, the ratio approaches to 0 or 1, which means that all terms of ham or spam will be selected as a candidate term subset, respectively. Therefore, the term search space is 2×10=20, namely, O2N.Figure 3
A feature selection window can select the optimal term subset by adjusting the ratio of spam terms number to terms number. Terms number includes terms number of spam and ham.Suppose there areN terms in term set, exhaustive search space is O2N, and greedy search sequential search space is ON2 [12], which are impractical unless N is a smaller value, it is unpractical and unnecessary for the RDTFD method to search all possible candidate terms from ham and spam term set. Moreover, because Chi-square and Information gain methods can reach the peaked value in 2000 terms [10], we set maximum number of candidate terms to n=2000 in this experiment, and in general, n is the term number of term subset and far less than N.We can view each feature in the feature space as each particle in the search space of PSO. In equation (10), D denotes dimensions of term space. vidt denotes the speed of particle i on the dth dimension at the iteration t, which represents the ratio of spam terms number to the terms number. pidt denotes the best position of individual particle i comparing with its current best fitness at iteration t. pgdt denotes the globally best position of all particles comparing with its current globally best fitness at iteration t. xidt denotes the position of particle i on the dth dimension at the iteration t. xidt+1 denotes the new position of particle i on the dth dimension at the iteration t+1. W denotes inertia weighting which controls the velocity in the previous iteration on the current velocity, W is nonnegative value which can adjust the scope of space search, and we initialize Wmin=0 and Wmax=1, c1 and c2 are acceleration constants initialized to 2, which can adjust maximum step size, r1 and r2 are random numbers, in the interval (0,1), which can be used to increase the randomness. Moreover, the maximum and minimum vidt of particle are Vmax=0.01 and Vmin=0.001, respectively. The maximum and minimum xidt of particle are Xmax=0.999 and Xmin=0.001, respectively. The maximum iteration is set to Nt=30, for each iteration t, W is given as follows:(11)wt+1=wmax−wmax−wmintNt.


### 3.3. Correlation Algorithm

Algorithms1 and 2 outline how the RDTFD method obtains the optimal term set by using PSO algorithm.Algorithm 1: RDTFD method (terms grouping and ranking, and to call PSO algorithm).
Input: the e-mail datasetOutput:Gs, Gt and GrStep 1: parameters initialization(1.1)
setGs=null//initialize variable Gs to preserve the optimal F1 value(1.2)
setGt=null//initialize variable Gt to preserve the optimal terms(1.3)
setGr=null//initialize variable Gr to preserve the optimal ratio(1.4)
setN=1000//initialize maximal candidate number of terms for feature selectionStep 2: generating training term set(2.1)
Calculate term weighting of all terms according to equations (8) and (9)//since the log function is used in both the numerator and denominator of equation (8), when the parameter values of the log function is 0 or 1, the value of the numerator divided by the denominator will be set to the constant 0(2.2)
The terms of positive weighting are put intoFh(2.3)
The terms of negative weighting are put intoFs(2.4)
Ranking all the terms ofFh by the weighting in descending order, ranking all the terms of Fs by the weighting in ascending orderStep 3: seeking the optimal candidate term subset by using PSO algorithm(3.1)
TransmittingFh, Fs, and N into PSO algorithm(3.2)
Run PSO algorithm (Algorithm2)(3.3)
Return the optimalF1 value and put into Gs(3.4)
Return the optimal term subset and put intoGt(3.5)
Return the optimal ratio and put intoGrAlgorithm 2: PSO (to search the optimal term set).
Input:Fh and Fs denote term set of ham and spam, respectively. N denotes the number of candidate terms.Output:Gs,Gt,GrStep 1: parameters initialization(1.1)
setNp=30//initialize the number of particles(1.2)
setNt=30//initialize the number of iteration times(1.3)
fori=1 to Np(1.4)
setxi1=randomxmin,xmax//initialize the position of each particle(1.5)
setvi1=randomvmin,vmax//initialize the velocity of each particle(1.6)
endfor(1.7)
Setr=vi1//r is the ratios of spam terms number to the terms numberStep 2: main procedure(2.1)
sett=1//initialize iterations(2.2)
whilet≤Ntdo(2.3)
fori=1 to Np(2.4)
setr=vit//update the ratios at t iterations(2.5)
j=0//initialize the terms number for training(2.6)
setFa=NULL//initialize terms Fa(2.7)
whilej<N(2.8)
j=j+200;(2.9)
Ns=r×j//terms number of spam(2.10)
Nh=j−Ns//terms number of ham(2.11)
fork=0 to Nh−1(2.12)
putFhk into Fa(2.13)
endfor(2.14)
fork=0 to Ns−1(2.15)
putFsk into Fa(2.16)
endfor(2.17)
endwhile(2.18)
F=EVALFa//calculate the local F1 value according to equation (12)(2.19)
endfor(2.20)
ifF>Gsthen(2.21)
Gs=F//update Gs by the maximal F1 value(2.22)
Gt=Fa//update Gr by Fa in terms of the maximal F1 value(2.23)
Gr=r//update Gt by using r according to the maximal F1 value(2.24)
remove the particle of the lowestF1 value from particle swarm(2.25)
setxit=randomxmin,xmax(2.26)
setvit=randomvmin,vmax(2.27)
construct new particle and insert into the particle swarm(2.28)
fori=1 to Np(2.29)
calculatexit+1//update position of particle according to equation (11)(2.30)
calculatevit+1//update velocity of particle according to equation (11)(2.31)
endfor(2.32)
t=t+1//update iterations(2.33)
endwhile(2.34)
returnGs,Gt,GrNote that theF1 value in step 3.3 of Algorithm 1 represents the mean value of F1 measure, which is defined as follows:(12)F1=2×r×pr+p.In equation (12), r=nss/nss+nsh, p=nss/nss+nhs, nss represents the number of spams that are correctly identified as spams, nsh represents the number of spams that are identified as hams, nhs represents the number of hams that are identified as spams.In the step 2.18 of Algorithm2, we apply evaluation function on each iteration to obtain the optimal candidate term set, which is defined as follows:(13)F=EVALFt.In equation (13), Ft denotes the candidate term subset, note that the candidate term subsets range from 200 terms to n terms with intervals of 200 terms, and n denotes the number of terms for text classification. The function EVALFt evaluates the performance on NB or SVM classifier with 10-fold cross validation, which can obtain the mean value of F1 measure.In order to improve the search efficiency of particles and obtain optimal term set, we consider to select the particle of minimumF1 value and remove it at each iteration and further to construct a new mutation particle into particle swarm for new iteration.


## 3.1. Relative Document-Terms Frequency Difference (RDTFD)

In order to describe the RDTFD method clearly, we list the definition of the concept related to the frequency in Table1, including document frequency, term frequency, average term frequency, and term frequency distribution.Table 1
Definition related to frequency terms.
KeywordDefinitionDocument frequencyThe number of documents that contains the term in the datasetTerm frequencyThe number of the term in all documents of the datasetAverage term frequencyThe average number of the term in all documents of the datasetTerm frequency distributionThe number of the term in each document of the datasetTable2 shows the number of documents and the total number of terms in ham and spam datasets, it is worth noting that Dataset1 and Dataset2 including spam and ham datasets, respectively. Table 3 shows some samples and the corresponding document frequency, term frequency, average term frequency, and term frequency distribution in ham and spam datasets, respectively.Table 2
Datasets examples of spam and ham.
DatasetsSpamHamDocument numberTotal terms numberDocument numberTotal terms numberDataset 1510005500Dataset 2105000102000Table 3
Document frequency and terms frequency of term examples in dataset 1 and dataset 2.
DatasetsTermDocument frequencyTerm frequencyAverage term frequencyTerm frequency distributionSpamHamSpamHamSpamHamSpamHamDataset 1Investment535310.61,1,1,1,10,1,1,0,1Linguistic55105212,2,2,2,21,1,1,1,1Marketing551010222,2,2,2,22,3,2,1,2Dataset 2Debian10102020222,2,2,2,2,2,2,2,2,22,2,2,2,2,2,2,2,2,2Mailings1012010212,2,2,2,2,2,2,2,2,210,0,0,0,0,0,0,0,0,0Workshop10102020222,2,2,2,2,2,2,2,2,21,3,1,2,3,1,3,2,1,3As shown in Table3, when DF methods (CHI, IG, and IMGI) are applied, the term “mailings” can obtain the highest value of DF methods, which shows that “mailings” has a discriminative capability compared with others terms. Moreover, the document frequency of “mailings” in spam class is higher than that in ham class, which means that an e-mail document tends to spam class if it contains “mailings.” Further, although “marketing” and “linguistic” have the same document frequency,however, “marketing” has a higher average frequency in ham class, which means that it is more likely to appear in ham class than in spam class.Since “debian” and “workshop” have the same document frequency in spam and ham class, if DF methods such as IG is used, “debian” and “workshop” will be abandoned. In addition, according to TFFS method GININTF, “debian” and “workshop” will get the same GININTF value, which shows that “debian” and “workshop” cannot be identified as spam or ham class. However, the term frequency distribution of “workshop” is more variable in ham class than in spam class, and therefore, an e-mail document containing “workshop” will tend to spam class by using TTFS method, although TTFS method is interpretable and easy to implement. Nevertheless, the method is based ont-test, namely, the prior distribution of the data must conform to normal distribution, this assumption is not consistent with distribution of the real data [37], and hence, it cannot obtain the better performance for feature selection.In this section, we propose a relative document-terms frequency difference (RDTFD) method, and it considers not only the document frequency and term frequency, but also the number of documents and the total number of terms, which can construct a better model to measure the ability to identify spam or ham class for each term and it can be demonstrated as follows:(8)RTDFD=logdfti∈hamlogDNH×logtfti∈hamlogTNH−logdfti∈spamlogDNS×logtfti∈spamlogTNS,(9)if MAXdfti∈hamdfti∈ham+dfti∈spam,dfti∈spamdfti∈ham+dfti∈spam>0.7,where dfti∈ham denotes the document frequency of term ti in ham documents, dfti∈spam denotes the document frequency of term ti in spam documents, tfti∈ham denotes the term frequency of term ti in ham documents, tfti∈spam denotes that term frequency of term ti in spam documents, DNH is the number of ham documents, DNS is the number of spam documents, TNH is the total number of terms in ham documents, and TNS is the total number of terms in spam documents.Equation (8) is intended to address the content mentioned in the first substep of step 2 in Figure 2, which shows that when document and term frequency of term ti in spam class are very close to ham class, RDTFD value is approximately equals to zero, which means that term ti has a poor discrimination capability in spam or ham class. Therefore, the bigger positive RDTFD weighting represents a document that containing the term ti tends to ham class and the smaller negative RDTFD weighting represents a document that containing the term ti tends to spam class, which can construct two independent term subsets, namely, the terms of the positive weighting will be put into the subset of ham class and the terms of the negative weighting will be put into to the subset of spam class. For instance, in Table 2, since term “debian” has same document frequency, term frequency and distribution of term frequency, it has no discriminating capability in spam or ham class according to the typical DF and TF methods. However, the total terms number of documents contain “debian” in spam class more than in ham class, we know log10/log10×log20/log2000−log10/log10×log20/log5000>0, by which, a document contains “debian” will tend to ham class.Since the distribution of each term in the text is very complicated and cannot be accurately measured by a constant formula, we can delineate a general scope for the distribution of these terms, as long as the terms in this scope are better for text classification. Furthermore, to limit the search range of features can not only reduce the time cost of feature search, but also maintain appropriate feature redundancy. Thus, we propose equation (9) that makes the term ti be selected as the candidate term belonging ham or spam class; otherwise, the term ti will be abandoned, which is similar to that mentioned in [19]. In the experiment of this paper, when this equation (9) is satisfied, the text classification performance would be better.


## 3.2. Feature Search Strategy

From the step 4 in Figure2, we know that the candidate feature subsets are selected from two independent term spaces by some search strategies. Compared with other optimization algorithms, the parameter setting of particle swarm optimization (PSO) algorithm is convenient and the population is rich. In addition, the convergence speed of PSO algorithm is fast and it is suitable to search the high-dimensional feature spaces. Therefore, in this study, we apply the PSO algorithm as the search strategy for the feature selection method.The PSO was proposed by Kennedy and Eberhart in 1995, the original inspiration was from the behavior of birds flocking and fish schooling [38]. In our experiment, the PSO algorithm that can search the optimal term set by multi-iteration and is given as follows [39]:(10)vidt+1=w×vidt+c1×r1×pidt−xidt+c2×r2×pgdt−xidt,xidt+1=xidt+vidt,d=1,2,…,D.Figure3 shows the process of feature search strategy implementation, the dotted line rectangle can be viewed as a feature selection window, the red part is from S1 to Sn, which shows that the negative term weighting of spam is sorted in the ascending order, and the green part is from H1 to Hn, which shows that the positive term weighting of ham is sorted in the descending order. In addition, the movement of the feature selection window is controlled by two parameters, the first parameter is the width of the feature selection window that determines the number of terms for classification, the second parameter is the ratio of spam terms number to the terms number, which is in the interval (0,1) and generated by the PSO algorithm, note that the terms number includes the spam terms number and the ham terms number. In Figure 3, R1⟶Rm represents each ratio, and m denotes the particle number. The feature selection window will move back and forth between ham and spam term set by the ratio value, which can generate m candidate term subsets, and they can be fed to a specific classifier such as NB or SVM to select the optimal term set with the highest F1 values. For instance, when the width of feature selection window is set to 10, namely, N=10, it denotes 10 terms will be selected between spam and ham term subsets for spam filtering, and moreover, the ratio is set to 0.7, which denotes feature selection window will select 7 terms in terms of spam and 3 terms in terms of ham. In extreme cases, the ratio approaches to 0 or 1, which means that all terms of ham or spam will be selected as a candidate term subset, respectively. Therefore, the term search space is 2×10=20, namely, O2N.Figure 3
A feature selection window can select the optimal term subset by adjusting the ratio of spam terms number to terms number. Terms number includes terms number of spam and ham.Suppose there areN terms in term set, exhaustive search space is O2N, and greedy search sequential search space is ON2 [12], which are impractical unless N is a smaller value, it is unpractical and unnecessary for the RDTFD method to search all possible candidate terms from ham and spam term set. Moreover, because Chi-square and Information gain methods can reach the peaked value in 2000 terms [10], we set maximum number of candidate terms to n=2000 in this experiment, and in general, n is the term number of term subset and far less than N.We can view each feature in the feature space as each particle in the search space of PSO. In equation (10), D denotes dimensions of term space. vidt denotes the speed of particle i on the dth dimension at the iteration t, which represents the ratio of spam terms number to the terms number. pidt denotes the best position of individual particle i comparing with its current best fitness at iteration t. pgdt denotes the globally best position of all particles comparing with its current globally best fitness at iteration t. xidt denotes the position of particle i on the dth dimension at the iteration t. xidt+1 denotes the new position of particle i on the dth dimension at the iteration t+1. W denotes inertia weighting which controls the velocity in the previous iteration on the current velocity, W is nonnegative value which can adjust the scope of space search, and we initialize Wmin=0 and Wmax=1, c1 and c2 are acceleration constants initialized to 2, which can adjust maximum step size, r1 and r2 are random numbers, in the interval (0,1), which can be used to increase the randomness. Moreover, the maximum and minimum vidt of particle are Vmax=0.01 and Vmin=0.001, respectively. The maximum and minimum xidt of particle are Xmax=0.999 and Xmin=0.001, respectively. The maximum iteration is set to Nt=30, for each iteration t, W is given as follows:(11)wt+1=wmax−wmax−wmintNt.


## 3.3. Correlation Algorithm

Algorithms1 and 2 outline how the RDTFD method obtains the optimal term set by using PSO algorithm.Algorithm 1: RDTFD method (terms grouping and ranking, and to call PSO algorithm).
Input: the e-mail datasetOutput:Gs, Gt and GrStep 1: parameters initialization(1.1)
setGs=null//initialize variable Gs to preserve the optimal F1 value(1.2)
setGt=null//initialize variable Gt to preserve the optimal terms(1.3)
setGr=null//initialize variable Gr to preserve the optimal ratio(1.4)
setN=1000//initialize maximal candidate number of terms for feature selectionStep 2: generating training term set(2.1)
Calculate term weighting of all terms according to equations (8) and (9)//since the log function is used in both the numerator and denominator of equation (8), when the parameter values of the log function is 0 or 1, the value of the numerator divided by the denominator will be set to the constant 0(2.2)
The terms of positive weighting are put intoFh(2.3)
The terms of negative weighting are put intoFs(2.4)
Ranking all the terms ofFh by the weighting in descending order, ranking all the terms of Fs by the weighting in ascending orderStep 3: seeking the optimal candidate term subset by using PSO algorithm(3.1)
TransmittingFh, Fs, and N into PSO algorithm(3.2)
Run PSO algorithm (Algorithm2)(3.3)
Return the optimalF1 value and put into Gs(3.4)
Return the optimal term subset and put intoGt(3.5)
Return the optimal ratio and put intoGrAlgorithm 2: PSO (to search the optimal term set).
Input:Fh and Fs denote term set of ham and spam, respectively. N denotes the number of candidate terms.Output:Gs,Gt,GrStep 1: parameters initialization(1.1)
setNp=30//initialize the number of particles(1.2)
setNt=30//initialize the number of iteration times(1.3)
fori=1 to Np(1.4)
setxi1=randomxmin,xmax//initialize the position of each particle(1.5)
setvi1=randomvmin,vmax//initialize the velocity of each particle(1.6)
endfor(1.7)
Setr=vi1//r is the ratios of spam terms number to the terms numberStep 2: main procedure(2.1)
sett=1//initialize iterations(2.2)
whilet≤Ntdo(2.3)
fori=1 to Np(2.4)
setr=vit//update the ratios at t iterations(2.5)
j=0//initialize the terms number for training(2.6)
setFa=NULL//initialize terms Fa(2.7)
whilej<N(2.8)
j=j+200;(2.9)
Ns=r×j//terms number of spam(2.10)
Nh=j−Ns//terms number of ham(2.11)
fork=0 to Nh−1(2.12)
putFhk into Fa(2.13)
endfor(2.14)
fork=0 to Ns−1(2.15)
putFsk into Fa(2.16)
endfor(2.17)
endwhile(2.18)
F=EVALFa//calculate the local F1 value according to equation (12)(2.19)
endfor(2.20)
ifF>Gsthen(2.21)
Gs=F//update Gs by the maximal F1 value(2.22)
Gt=Fa//update Gr by Fa in terms of the maximal F1 value(2.23)
Gr=r//update Gt by using r according to the maximal F1 value(2.24)
remove the particle of the lowestF1 value from particle swarm(2.25)
setxit=randomxmin,xmax(2.26)
setvit=randomvmin,vmax(2.27)
construct new particle and insert into the particle swarm(2.28)
fori=1 to Np(2.29)
calculatexit+1//update position of particle according to equation (11)(2.30)
calculatevit+1//update velocity of particle according to equation (11)(2.31)
endfor(2.32)
t=t+1//update iterations(2.33)
endwhile(2.34)
returnGs,Gt,GrNote that theF1 value in step 3.3 of Algorithm 1 represents the mean value of F1 measure, which is defined as follows:(12)F1=2×r×pr+p.In equation (12), r=nss/nss+nsh, p=nss/nss+nhs, nss represents the number of spams that are correctly identified as spams, nsh represents the number of spams that are identified as hams, nhs represents the number of hams that are identified as spams.In the step 2.18 of Algorithm2, we apply evaluation function on each iteration to obtain the optimal candidate term set, which is defined as follows:(13)F=EVALFt.In equation (13), Ft denotes the candidate term subset, note that the candidate term subsets range from 200 terms to n terms with intervals of 200 terms, and n denotes the number of terms for text classification. The function EVALFt evaluates the performance on NB or SVM classifier with 10-fold cross validation, which can obtain the mean value of F1 measure.In order to improve the search efficiency of particles and obtain optimal term set, we consider to select the particle of minimumF1 value and remove it at each iteration and further to construct a new mutation particle into particle swarm for new iteration.


## 4. Experimental and Results

### 4.1. Experimental Environment Configuration

In this experiment, we use Intel(TM)-i5 Processor with a CPU clock rate of 3.2GHZ and 8 GB main memory. The feature selection methods run on the platform of windows7 Ultimate and python3.5.


### 4.2. Algorithms Selection for the Experiment

For the convenience of description, the RDTFD method and PSO algorithm based on independent feature space search are called RDTFD. In order to evaluate the performance of RDTFD, we selected six feature selection methods, including CHI, IG, TFIG, TTFS, IMTFIDF, and GININTF.


### 4.3. Datasets

In this experiment, we chose six spam datasets from a wide variety of applications, such as PU123A [40], CSDMC2010 (CS), and Enron-spam3 (ES) [41], which are shown in Table 4.Table 4
Mail datasets consist of PU1, PU2, PU3, PUA, CS, and ES.
DatasetsHamSpamPU1610480PU2570140PU323101820PUA570570CS29491378ES40121500


### 4.4. Stopwords

The stopwords are usually removed to improve performance for classification in spam filtering, however, we do not apply it in our experiment in the light of two main reasons. Firstly, since stopwords are language-specific and domain-specific, removing these words can lead to the negative result [42]. Secondly, in order to protect the privacy personal e-mails, PU1, PU2, PU3, and PUA are encrypted with a set of digits, and therefore, it is impossible to identify which of the encrypted contents are belong to stopwords. Moreover, CS, and ES datasets consist of many nonnumerical characters, therefore, in order to unify the experimental standards, we do not simply remove the terms from these datasets.


### 4.5. Classifiers and Evaluation Measure

Because this paper focuses on feature selection algorithm, rather than discussing the advantages and disadvantages of classifiers, we apply the common classifiers to meet the requirement of this paper, namely, the NB [43] and SVM [44] are used to evaluate the performance of feature selection methods, respectively. Because multinomial NB is the better model in NB classifier, which can achieve the highest classification performance on multiple datasets [45], it will be used as a classifier in this experiment. In addition, because the popular sequential minimal optimization (SMO) classifier is the linear support vector machine, which can handle very large training set and has a higher performance in sparse datasets [46], we utilize it as another classifier in this experiment. Finally, the experiment was conducted on six corpus by utilizing tenfold cross validation [47], by which we apply F1 measure to evaluate classification performance on each dataset.


### 4.6. Performance Comparison of Different Feature Selection Methods

Figure4 shows the performance of seven feature selection methods on PU1, PU2, PU3, PUA, CS, and ES by using F1 measure when NB and SVM are used, respectively. Further, we design Tables 5 and 6 to show the relation about the feature selection methods, terms number (column terms), and classifiers on six datasets, respectively.Figure 4
F1 values on six spam datasets.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 5
Performance of feature selection methods in NB classifier.
DatasetsMethodTerms numberHighestF1MethodTerms numberLowestF1MethodLowest terms numberHighestF1PU1RDTFD6000.971GININTF2000.865RDTFD2000.960PU2RDTFD10000.939IMTFIDF2000.706RDTFD2000.904PU3RDTFD/IMTFIDF10000.967GININTF2000.788RDTFD2000.953PUARDTFD10000.973GININTF2000.875RDTFD2000.954CSRDTFD10000.954IMTFIDF2000.713TFIG2000.906ESRDTFD10000.967IMTFIDF2000.754CHI2000.938Table 6
Performance of feature selection method in SVM classifier.
DatasetsMethodTerms numberHighestF1MethodTerms numberLowestF1MethodLowest terms numberHighestF1PU1RDTFD10000.977TTFS2000.925RDTFD2000.966PU2RDTFD4000.938IMTFIDF2000.792RDTFD2000.913PU3RDTFD/IMTFID10000.970TTFS2000.943IMTFIDF2000.955PUARDTFD10000.979GININTF2000.915RDTFD2000.963CSRDTFD8000.983IMTFIDF2000.926TFIG2000.951ESRDTFD10000.971IMTFIDF2000.890TFIG2000.947Tables5 and 6 include four column parts: the first column part is Datasets, which represents each dataset for experiment, the second column part is Method/Terms Number/Highest F1, which means the highest F1 value based on N terms and the feature selection methods, the third column part is Method/Terms Number/Lowest F1, which denotes the lowest F1 value based on N terms and the feature selection methods, and the fourth column is Method/Lowest terms Number/Highest F1, which represents the highest F1 value based on the lowest N terms and the feature selection methods. Note that terms range from 200 to 1000 with intervals of 200 terms. In Tables 5 and 6, we know that RDTFD method outperforms the other methods in text classification. Moreover, since F1 value of SVM based on SMO almost completely surpasses NB on seven datasets, the SVM is more suitable than NB in text classification.


### 4.7. The Distribution of Particles in Different Term Spaces

In this experiment, the PSO algorithm is used to find the optimal term set for spam filtering by searching the best particle that represents the ratio of spam terms number to terms number. Tables7 and 8 include three column parts. The first column part has Datasets, which represents each dataset for experiment. The second column part has Terms Number/Highest F1/Ratio, which means the ratio of spam terms number to the terms number when the RDTFD method obtains the highest F1 values. The third column part has Terms Number/Lowest F1/Ratio, which means the ratio of spam terms number to the terms number when the RDTFD method obtains the lowest F1 values.Table 7
The distribution of particles corresponding to the ratio in different terms number by using NB classifier.
DatasetsTerms numberHighestF1RatioTerms numberLowestF1RatioPU16000.9710.2162000.9600.236PU210000.9390.3762000.9070.447PU310000.9670.4722000.9530.504PUA10000.9730.6332000.9540.624CS10000.9540.7802000.9030.728ES10000.9670.9522000.8970.985Table 8
The distribution of particles corresponding to the ratio in different terms number by using SVM classifier.
DatasetsTerms numberHighestF1RatioTerms numberLowestF1RatioPU110000.9770.4542000.9670.432PU24000.9380.4252000.9130.439PU310000.9700.5952000.9530.615PUA10000.9800.5322000.9630.415CS8000.9830.5652000.9470.248ES10000.9710.7242000.9390.377


### 4.8. Analysis of Time Complexity

Compared with the general feature selection, although the RDTFD method takes much less time than some methods based on exhaustive search and greedy search, it is still more time consuming than the methods based on feature weighting ranking.As mentioned Section3.2, the feature selection window will select n terms in 2×n terms as terms for spam filtering. Therefore, in this experiment, we select term subsets range from 200 to n terms with the step of 200 terms between 2×200 and 2×n terms, which finally generate Ft=n/200 candidate term sets. Moreover, the particle number and iteration times in PSO algorithm (Algorithm 2) will affect the running time of RDTFD method, for instance, the iteration times will decrease as the terms number decreases, and thus, we can consider adjusting these parameters. In addition, for a unifying experiment standard, the particle number and iteration times are set to 30, which means the 30×30×Ft candidate term subsets will be generated. For instance, when the term subsets range from 200 to 1000 terms with the step of 200 terms, we will select Ft=1000/200=5 candidate term subsets between 2×200 and 2×1000 terms, and thus, altogether 30×30×5=4500 candidate term subsets are generated and the size of each candidate subsets will increase as the terms number increases.Consequently, the running time of RDTFD method is affected by the number of the selected terms on the specific samples. Table9 shows that the running time of RDTFD method will increase linearly with the increase of the samples and the number of the selected terms when particle number and iteration times are constant.Table 9
Running time of the RDTFD method on specific samples and terms number in NB and SVM.
DatasetsSamplesTerms numberTerms number20040060080010002004006008001000Running time of NB (sec)Running time of SVM (sec)PU11090128230324416506127223318409499PU27108614720626431988156216275333PU34130464843127016452005441805116415081844PUA1140130235333428519135235334425520CS4327486904133017202109479852121916151959ES551260311321673218426725711051156920862575


### 4.9. Statistical Analysis

When the two sets of paired data approximately obey the normal distribution, the pairedt-test can be used. Otherwise, we can use Wilcoxon signed ranks test (Wilcoxon, 1945) to replace the paired t-test. Moreover, Wilcoxon signed ranks test method not only considers the positive and the negative differences, but also ranks the differences in performances of two classifiers for each dataset, and thus, it is more sensible than the t-test [48]. In this experiment, NB and SVM classifiers are applied to evaluate the performance of RDTFD method on six datasets, such as PU1, PU2, PU3, PUA, CS, and ES, and Wilcoxon signed ranks test is applied on the paired F1 values by the RDTFD method and the other six feature selection methods, such as CHI, IG, TFIG, TTFS, IMTFIDF, and GININTF. In addition, the terms range from 200 to 2000 with the step of 200. Table 10 shows the p values when the significance level is at 5%, we apply IBM SPSS Statistics 23 software to observe the data, and experimental result shows that the performance of RDTFD method is obviously better than other feature selection methods in 66 cases p<0.05, but in 6 cases p>0.05, the RDTFD method has no significant difference than the other methods. Therefore, the RDTFD method based on independent feature space search is more robust than the other feature selection methods in spam filtering.Table 10
Two-tailed Wilcoxon signed ranks test results by using NB and SVM.
MethodNBSVMPU1PU2PU3PUACSESPU1PU2PU3PUACSESCHI0.0050.0050.0050.0050.0050.5080.0050.0050.0170.0050.0170.028IG0.0050.0050.0050.0050.0050.1850.0050.0050.0110.0050.0120.027TFIG0.0850.0050.0050.0050.0070.0050.0050.0050.0110.0050.0080.074TTFS0.0050.0050.0050.0050.1130.0050.0050.0050.0050.0050.0050.005IMTFIDF0.4120.0050.0120.0050.0070.0050.0050.0110.0230.0210.0050.005GININTF0.0050.0050.0050.0050.0050.0050.0050.0050.0050.0050.0120.005


## 4.1. Experimental Environment Configuration

In this experiment, we use Intel(TM)-i5 Processor with a CPU clock rate of 3.2GHZ and 8 GB main memory. The feature selection methods run on the platform of windows7 Ultimate and python3.5.


## 4.2. Algorithms Selection for the Experiment

For the convenience of description, the RDTFD method and PSO algorithm based on independent feature space search are called RDTFD. In order to evaluate the performance of RDTFD, we selected six feature selection methods, including CHI, IG, TFIG, TTFS, IMTFIDF, and GININTF.


## 4.3. Datasets

In this experiment, we chose six spam datasets from a wide variety of applications, such as PU123A [40], CSDMC2010 (CS), and Enron-spam3 (ES) [41], which are shown in Table 4.Table 4
Mail datasets consist of PU1, PU2, PU3, PUA, CS, and ES.
DatasetsHamSpamPU1610480PU2570140PU323101820PUA570570CS29491378ES40121500


## 4.4. Stopwords

The stopwords are usually removed to improve performance for classification in spam filtering, however, we do not apply it in our experiment in the light of two main reasons. Firstly, since stopwords are language-specific and domain-specific, removing these words can lead to the negative result [42]. Secondly, in order to protect the privacy personal e-mails, PU1, PU2, PU3, and PUA are encrypted with a set of digits, and therefore, it is impossible to identify which of the encrypted contents are belong to stopwords. Moreover, CS, and ES datasets consist of many nonnumerical characters, therefore, in order to unify the experimental standards, we do not simply remove the terms from these datasets.


## 4.5. Classifiers and Evaluation Measure

Because this paper focuses on feature selection algorithm, rather than discussing the advantages and disadvantages of classifiers, we apply the common classifiers to meet the requirement of this paper, namely, the NB [43] and SVM [44] are used to evaluate the performance of feature selection methods, respectively. Because multinomial NB is the better model in NB classifier, which can achieve the highest classification performance on multiple datasets [45], it will be used as a classifier in this experiment. In addition, because the popular sequential minimal optimization (SMO) classifier is the linear support vector machine, which can handle very large training set and has a higher performance in sparse datasets [46], we utilize it as another classifier in this experiment. Finally, the experiment was conducted on six corpus by utilizing tenfold cross validation [47], by which we apply F1 measure to evaluate classification performance on each dataset.


## 4.6. Performance Comparison of Different Feature Selection Methods

Figure4 shows the performance of seven feature selection methods on PU1, PU2, PU3, PUA, CS, and ES by using F1 measure when NB and SVM are used, respectively. Further, we design Tables 5 and 6 to show the relation about the feature selection methods, terms number (column terms), and classifiers on six datasets, respectively.Figure 4
F1 values on six spam datasets.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 5
Performance of feature selection methods in NB classifier.
DatasetsMethodTerms numberHighestF1MethodTerms numberLowestF1MethodLowest terms numberHighestF1PU1RDTFD6000.971GININTF2000.865RDTFD2000.960PU2RDTFD10000.939IMTFIDF2000.706RDTFD2000.904PU3RDTFD/IMTFIDF10000.967GININTF2000.788RDTFD2000.953PUARDTFD10000.973GININTF2000.875RDTFD2000.954CSRDTFD10000.954IMTFIDF2000.713TFIG2000.906ESRDTFD10000.967IMTFIDF2000.754CHI2000.938Table 6
Performance of feature selection method in SVM classifier.
DatasetsMethodTerms numberHighestF1MethodTerms numberLowestF1MethodLowest terms numberHighestF1PU1RDTFD10000.977TTFS2000.925RDTFD2000.966PU2RDTFD4000.938IMTFIDF2000.792RDTFD2000.913PU3RDTFD/IMTFID10000.970TTFS2000.943IMTFIDF2000.955PUARDTFD10000.979GININTF2000.915RDTFD2000.963CSRDTFD8000.983IMTFIDF2000.926TFIG2000.951ESRDTFD10000.971IMTFIDF2000.890TFIG2000.947Tables5 and 6 include four column parts: the first column part is Datasets, which represents each dataset for experiment, the second column part is Method/Terms Number/Highest F1, which means the highest F1 value based on N terms and the feature selection methods, the third column part is Method/Terms Number/Lowest F1, which denotes the lowest F1 value based on N terms and the feature selection methods, and the fourth column is Method/Lowest terms Number/Highest F1, which represents the highest F1 value based on the lowest N terms and the feature selection methods. Note that terms range from 200 to 1000 with intervals of 200 terms. In Tables 5 and 6, we know that RDTFD method outperforms the other methods in text classification. Moreover, since F1 value of SVM based on SMO almost completely surpasses NB on seven datasets, the SVM is more suitable than NB in text classification.


## 4.7. The Distribution of Particles in Different Term Spaces

In this experiment, the PSO algorithm is used to find the optimal term set for spam filtering by searching the best particle that represents the ratio of spam terms number to terms number. Tables7 and 8 include three column parts. The first column part has Datasets, which represents each dataset for experiment. The second column part has Terms Number/Highest F1/Ratio, which means the ratio of spam terms number to the terms number when the RDTFD method obtains the highest F1 values. The third column part has Terms Number/Lowest F1/Ratio, which means the ratio of spam terms number to the terms number when the RDTFD method obtains the lowest F1 values.Table 7
The distribution of particles corresponding to the ratio in different terms number by using NB classifier.
DatasetsTerms numberHighestF1RatioTerms numberLowestF1RatioPU16000.9710.2162000.9600.236PU210000.9390.3762000.9070.447PU310000.9670.4722000.9530.504PUA10000.9730.6332000.9540.624CS10000.9540.7802000.9030.728ES10000.9670.9522000.8970.985Table 8
The distribution of particles corresponding to the ratio in different terms number by using SVM classifier.
DatasetsTerms numberHighestF1RatioTerms numberLowestF1RatioPU110000.9770.4542000.9670.432PU24000.9380.4252000.9130.439PU310000.9700.5952000.9530.615PUA10000.9800.5322000.9630.415CS8000.9830.5652000.9470.248ES10000.9710.7242000.9390.377


## 4.8. Analysis of Time Complexity

Compared with the general feature selection, although the RDTFD method takes much less time than some methods based on exhaustive search and greedy search, it is still more time consuming than the methods based on feature weighting ranking.As mentioned Section3.2, the feature selection window will select n terms in 2×n terms as terms for spam filtering. Therefore, in this experiment, we select term subsets range from 200 to n terms with the step of 200 terms between 2×200 and 2×n terms, which finally generate Ft=n/200 candidate term sets. Moreover, the particle number and iteration times in PSO algorithm (Algorithm 2) will affect the running time of RDTFD method, for instance, the iteration times will decrease as the terms number decreases, and thus, we can consider adjusting these parameters. In addition, for a unifying experiment standard, the particle number and iteration times are set to 30, which means the 30×30×Ft candidate term subsets will be generated. For instance, when the term subsets range from 200 to 1000 terms with the step of 200 terms, we will select Ft=1000/200=5 candidate term subsets between 2×200 and 2×1000 terms, and thus, altogether 30×30×5=4500 candidate term subsets are generated and the size of each candidate subsets will increase as the terms number increases.Consequently, the running time of RDTFD method is affected by the number of the selected terms on the specific samples. Table9 shows that the running time of RDTFD method will increase linearly with the increase of the samples and the number of the selected terms when particle number and iteration times are constant.Table 9
Running time of the RDTFD method on specific samples and terms number in NB and SVM.
DatasetsSamplesTerms numberTerms number20040060080010002004006008001000Running time of NB (sec)Running time of SVM (sec)PU11090128230324416506127223318409499PU27108614720626431988156216275333PU34130464843127016452005441805116415081844PUA1140130235333428519135235334425520CS4327486904133017202109479852121916151959ES551260311321673218426725711051156920862575


## 4.9. Statistical Analysis

When the two sets of paired data approximately obey the normal distribution, the pairedt-test can be used. Otherwise, we can use Wilcoxon signed ranks test (Wilcoxon, 1945) to replace the paired t-test. Moreover, Wilcoxon signed ranks test method not only considers the positive and the negative differences, but also ranks the differences in performances of two classifiers for each dataset, and thus, it is more sensible than the t-test [48]. In this experiment, NB and SVM classifiers are applied to evaluate the performance of RDTFD method on six datasets, such as PU1, PU2, PU3, PUA, CS, and ES, and Wilcoxon signed ranks test is applied on the paired F1 values by the RDTFD method and the other six feature selection methods, such as CHI, IG, TFIG, TTFS, IMTFIDF, and GININTF. In addition, the terms range from 200 to 2000 with the step of 200. Table 10 shows the p values when the significance level is at 5%, we apply IBM SPSS Statistics 23 software to observe the data, and experimental result shows that the performance of RDTFD method is obviously better than other feature selection methods in 66 cases p<0.05, but in 6 cases p>0.05, the RDTFD method has no significant difference than the other methods. Therefore, the RDTFD method based on independent feature space search is more robust than the other feature selection methods in spam filtering.Table 10
Two-tailed Wilcoxon signed ranks test results by using NB and SVM.
MethodNBSVMPU1PU2PU3PUACSESPU1PU2PU3PUACSESCHI0.0050.0050.0050.0050.0050.5080.0050.0050.0170.0050.0170.028IG0.0050.0050.0050.0050.0050.1850.0050.0050.0110.0050.0120.027TFIG0.0850.0050.0050.0050.0070.0050.0050.0050.0110.0050.0080.074TTFS0.0050.0050.0050.0050.1130.0050.0050.0050.0050.0050.0050.005IMTFIDF0.4120.0050.0120.0050.0070.0050.0050.0110.0230.0210.0050.005GININTF0.0050.0050.0050.0050.0050.0050.0050.0050.0050.0050.0120.005


## 5. Conclusions and Future Work

In this paper, we propose a new feature selection method based on independent feature space search for text classification, which can be divided into two steps. Firstly, a relative document-term frequency difference (RDTFD) method is used to divide the features of text into two independent features subsets according to the ability to discriminate the ham and spam samples, which can improve the high correlation of feature class and reduce the correlation between features.  Furthermore, the RDTFD method also reduces the search range of feature space and maintains appropriate feature redundancy. Secondly, the feature search strategy based on particle swarm optimization algorithm (PSO) is used to find the optimal feature space, which can improve the performance of text classification. Finally, we apply NB and SVM to evaluate RDTFD model method by using theF1 measure on six spam datasets such as PU123A, CS, and ES, respectively. Experiment result shows that, in most cases, the RDTFD method based on independent feature space search outperforms the others general feature selection methods.In future work, we will try to use other feature search strategies to improve RDTFD method. In addition, we are expanding this study to improve the running speed of RDTFD, especially the parallel operation of large-scale PSO on terms of the high-dimensional feature space.



---

*Source: 6076272-2020-05-12.xml*