# Distance Variance Score: An Efficient Feature Selection Method in Text Classification

Authors: Heyong Wang; Ming Hong
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With the rapid development of web applications such as social network, a large amount of electric text data is accumulated and available on the Internet, which causes increasing interests in text mining. Text classification is one of the most important subfields of text mining. In fact, text documents are often represented as a high-dimensional sparse document term matrix (DTM) before classification. Feature selection is essential and vital for text classification due to high dimensionality and sparsity of DTM. An efficient feature selection method is capable of both reducing dimensions of DTM and selecting discriminative features for text classification. Laplacian Score (LS) is one of the unsupervised feature selection methods and it has been successfully used in areas such as face recognition. However, LS is unable to select discriminative features for text classification and to effectively reduce the sparsity of DTM. To improve it, this paper proposes an unsupervised feature selection method named Distance Variance Score (DVS). DVS uses feature distance contribution (a ratio) to rank the importance of features for text documents so as to select discriminative features. Experimental results indicate that DVS is able to select discriminative features and reduce the sparsity of DTM. Thus, it is much more efficient than LS.


---

## Body

## 1. Introduction

Text classification is one of the important subfields of text mining, which recently gains increasing attention with the rapid development of web applications, such as social network. The problem of text classification can be described as follows. In practice,n text documents are often represented as a document term matrix DTM=[D1,D2,…,Dn]T (shown in (1)). Row vector Di=[fi1,fi2,…,fim](i=1,2,…,n) denotes the ith text document among the n text documents. Each feature fjj=1,2,…,m corresponds to a term in the n text documents and fij is term frequency of fj in Di. Consider a simple example of two short text documents. The first document is “You are beautiful!” and the second is “Good morning, you guys!”. DTM of two documents is shown in (2). D1=[1,1,0,0,0,1] and D11=f11=1 show that the first feature “are” exists once in the first text document (“You are beautiful!”). Moreover, Di is labeled with a class c in which Di should be. c is drawn from a predefined t-class label set C=c1,c2,…,ct. It is the major task of text classification to construct classification models using training text documents and then to predict a class label c (c∈C) for other text documents whose class labels are unknown.DTM of
n
Documents
(1)
f
1
f
2
⋯
f
m
D
1
f
11
f
12
⋯
f
1
m
D
2
f
21
f
22
⋯
f
2
m
⋮
⋮
⋮
⋯
⋮
D
n
f
n
1
f
n
2
⋯
f
n
mDTM of Two Documents
(2)
are
f
1
beautiful
f
2
good
f
3
guys
f
4
morning
f
5
you
f
6
D
1
1
1
0
0
0
1
D
2
0
0
1
1
1
1The most important characteristics of text data are its high dimensionality and sparsity [1]. A corpus of text documents often contains a large amount of words (high dimensionality) and a given text document may contain only a small number of words (sparsity). This idea is described in the aspect of DTM as follows. Consider DTM in (1), In most cases, m is very large, which makes DTM high-dimensional. For Di, a large number of fji=0 because Di only contains a small number of the total m terms. This makes DTM high-sparse. Due to the high dimensionality and sparsity of text data, it is essential to find an efficient feature selection method to reduce feature space. The reduction of feature space causes the loss of information for text classification. A feature selection method is efficient if it keeps classification accuracy of classifiers when feature space is reduced.Feature selection is one of the important tasks in text classification due to the high dimensionality of feature space and the existence of indiscriminative features [1]. Feature selection methods are able to reduce the high-dimensional indiscriminative feature space into low-dimensional discriminative feature subspace [2]. For example, in (2), feature “beautiful” and feature “morning” may be discriminative features and then a six-dimensional DTM can be reduced into a two-dimensional one. This paper focuses on filter feature selection and all the methods introduced in this paper are filter feature selection methods. Filter methods are chosen because they are more computationally efficient than wrapper methods [2]. A lot of feature selection methods have been proposed. Supervised feature selection methods include information gain (IG), mutual information, Gini index (GI), and expected cross-entropy. Unsupervised feature selection methods include document frequency (DF), variance score (VS) (or term variance), and LS.LS is an unsupervised feature selection method. It is the key assumption that data from the same class label are often close to each other and the importance of a feature is evaluated by its power of locality preserving ability [3]. More details of LS are covered in Section 2.2.3. LS has been successfully used in areas such as face recognition. LS has not been used in feature selection for text classification currently. We are interested in the efficiency of this proved-discriminative feature selection method in text classification. However, both experiments and analysis indicate that LS is inefficient for text classification due to the sparsity of DTM. LS is unable to keep accuracy of classifiers when feature space is reduced and is unable to efficiently reduce the sparsity of DTM. To improve LS, this paper proposes an unsupervised feature selection method DVS. DVS uses feature distance contribution (a ratio) to replace similarity measure used in original LS to rank feature importance so as to select discriminative features. DVS is efficient in selecting discriminative features from DTM because feature distance contribution pays much attention to nonzero values and is able to avoid negative effects caused by 0 values. DVS is also able to reduce the sparcity of DTM more efficiently than LS. More details of DVS are covered in Section 3.The rest of this paper is organized as follows. Section2 introduces current feature selection methods and gives details of LS. Section 3 formally introduces DVS and analyzes details of DVS. In Section 4, experiments are performed using two DTM from UCI repository to validate efficiency of DVS on DTM. More discussion between efficiency of DVS and LS in text classification are in Section 4.2.3. Finally, Section 5 gives the conclusion.


## 2. Related Work

This section discusses several supervised and unsupervised feature selection methods proposed in current studies.


### 2.1. Supervised Feature Selection Methods

ForDTM in (1), Pck denotes the prior probability that a text document Di belongs to class ck. Pfj denotes the prior probability that fij>0. Pck∣fj denotes the prior probability of ck such that Di belongs to ck and in Di, fij>0 (i=1,2,…,n; j=1,2,…,m).


#### 2.1.1. Information Gain (IG)

IG selects features according to amounts of information that a feature uses for classification [4–6]. IG of fj in text classification is given by the following formula: (3)IGfj=-∑k=1tPcklog⁡⁡Pck+Pfj·∑k=1tPck∣fjlog⁡⁡Pck∣fj+1-Pfj·∑k=1t1-Pck∣fjlog⁡⁡1-Pck∣fj.Some studies have applied IG to feature selection for text classification [7–9], including improvements of IG [10, 11].


#### 2.1.2. Mutual Information (MI)

MI [12, 13] observes interesting relationship between two variables. MI of fj in text classification is given by the following formula: (4)MIfj=∑k=1tPcklog⁡⁡Pfj∩ckPfj×Pck.MI has been used in feature selection for text classification in current studies [14, 15]. Improvements on MI are also covered in current studies [16, 17].


#### 2.1.3. Gini Index (GI)

GI is first introduced in CART (a typical decision tree algorithm) to evaluate impurity offj [6, 18]. GI of fj in text classification is given by the following formula: (5)GIfj=1-∑k=1tP2fj∣ck.GI has been used in feature selection for text classification [19]. Improvements of GI are also catch attentions of current studies [20].


#### 2.1.4. Expected Cross Entropy (ECE)

The same as IG and MI, ECE [21] is a measure from information theory. ECE of fj in text classification is given by the following formula:(6)ECEfj=Pfj∑k=1tPck∣fjlog⁡⁡Pck∣fjPfj.ECE is imposed to feature selection for text classification in some studies [22, 23], including improvements of ECE [24].


### 2.2. Unsupervised Feature Selection Methods

ForDTM in (1), f-j is the mean of fj and f-j=1/n∑ifij.


#### 2.2.1. Document Frequency (DF)

DF [7, 25] assumes that frequent terms are more informative than nonfrequent terms. DF is the total number of documents in which fj appears. DF is usually used as a criterion to evaluate efficiency of other feature selection methods. DF of fj is given by the following formula:(7)DFfj=nfij>0i=1,2,…,n;j=1,2,…,m.n(fij>0) denotes the total number of documents in which fj appears. A discriminative feature gets high DF. Improvements on DF have been proposed in some studies [26, 27].


#### 2.2.2. Variance Score (VS)

VS [25] ranks features by calculating variance of each feature fj in DTM. VS is given by the following formula:(8)VSfj=Var⁡fj=1n∑i=1nfij-f-j2.A discriminative feature gets high VS. VS is a simple feature selection method used in feature selection for text mining [28].


#### 2.2.3. Laplacian Score (LS)

It is the key assumption of LS that data from the same class label are often close to each other and the importance of a feature is evaluated by its power of locality preserving ability and LS is described as follows [3]:(9)LSfj=∑pqfpj-fqj2SpqVar⁡fj.Spq evaluates the similarity between Dp and Dq. Dp and Dq are similar if Dp is among k nearest neighbors of Dq or Dq is among k nearest neighbors of Dp. Spq is given by the following formula:(10)Spq=e-Dp-Dq2/t,ifDpandDqare similar0,otherwise.t is a suitable constant. Spq is the p,q element of weighted matrix S which evaluates similarities of samples of D.Define vectorl=[1,1,…,1]T, then A=diag⁡(Sl). Var⁡(fj) in formula (4) is the weighted variance of fj. Var⁡(fj) is given by the following formula:(11)Var⁡fj=∑ifij-f-j2Aii.Aii is the (i,i) element of A. The weighted variance can be simply replaced by standard variance formulated as the following formula:(12)Var⁡fj=∑ifij-f-j2.For a discriminative feature,(fpj-fqj) is smaller whenever Spq is bigger and, on the other hand, Var⁡fj is bigger. Thus, LS of a discriminative feature tends to be small. (more details of LS are in [3]).LS is able to evaluate and rank importance of features and it has been used incurrent studies. He et al. [3] propose LS for feature selection and apply it and data variance (VS) to select features from CUM PIE face database for clustering. Experimental results show that LS performs better than data variance (VS) in several tests with different clusters (k=5,10,30,68). Hu and Man [29] impose LS to spare coding. They use it to evaluate the locality preserving ability of candidate atoms from data examples and select high ranked candidates. Experiments on UCI data demonstrate effectiveness, which also indicates efficiency of LS. Solorio-Fernández et al. [30] propose LS for supervised feature selection. It is imposed to rank features to reduce the search space. This method outperforms better than the other feature selection methods on UCI data sets. Good performance of this method also demonstrates robustness of LS in feature selection. Huang et al. [31] propose LS for face recognition. They impose LS to rank the regular and irregular features in order to achieve the best performances more quickly and it is demonstrated that it is better than other several methods. It is proved that it is capable of giving a better ranking of features in their experiments. Chunlu et al. [32] study classification of sMRI data in Alzheimer’s disease. LS is imposed to select more discriminative features by evaluating their locality preserving abilities. Experimental results prove robustness of LS in feature selection. Bo et al. [33] impose LS to gene feature selection and develop a new method called locality sensitive Laplacian Score (LSLS) by combining LS and locality sensitive discriminant analysis. Experimental results indicate that the method is effective and LS performs well.Current studies major in the ideas of improving LS. Liu et al. [34] propose an improved method called LSE (Laplacian Score combined with distance-based entropy measure) for unsupervised feature selection. LSE uses entropy measure to replace k-means clustering used in LS to solve the drawbacks of LS. Experimental results of 6 UCI data sets demonstrate that LSE performs better than LS. Padungweang et al. [35] also propose an efficient method based on the strong constraint on the global topology of the data space. Experimental results indicate that compared with conventional LS, this method has better performances. Zhu et al. [36] propose an improved LS method called IterativeLS. It tires improving LS by gradually improving the nearest neighbor graph by discarding the least relevant features at each iteration. Experimental results on both UCI data sets and face databases demonstrate that IterativeLS performs better than LS. Benabdeslem and Hindawi [37] address the problem of semisupervised feature selection for high-dimensional data and propose Constrained Laplacian Score (CLS) to improve LS. Experimental results on 5 UCI data sets demonstrate that CLS is better than LS in the problem of semisupervised feature selection. Moreover, Wang et al. [38] also propose a new method termed Label Reconstruction based Laplacian Score (LRLS) to improve LS for semisupervised feature selection. Experimental results on three UCI data sets indicate that LRLS is clearly better than LS in most occasions.It is shown that LS is efficient and widely used in feature selection of current studies. It is used as a benchmark technique in order to compare with a new technique in both unsupervised and supervised feature selections [35]. LS is successfully used in some areas such as sparse coding [29], face recognition [31], and gene feature selection [33]. This paper studies feature selection in text classification and argues that conventional LS is not appropriate for feature selection of DTM. This paper proposes an unsupervised method termed DVS to improve LS in feature selection of DTM. Section 3 introduces DVS and analyzes details of DVS.Current feature selection methods for text classification have been studied a lot and a lot of improvements have been proposed. LS is proved discriminative in the application of several areas. However, LS has not been used in feature selection for text classification currently. We are interested in performances of this proved-discriminative method in text classification. LS performs poorly in experiments. Through further analysis, we found that LS is not appropriate for text classification because LS is not able to select discriminative features from a usually sparseDTM. A new method called DVS is proposed to improve LS in text classification. DVS uses difference measure to replace similarity measure of original LS. More discussions of DVS and LS are covered in Section 4.2.3.


## 2.1. Supervised Feature Selection Methods

ForDTM in (1), Pck denotes the prior probability that a text document Di belongs to class ck. Pfj denotes the prior probability that fij>0. Pck∣fj denotes the prior probability of ck such that Di belongs to ck and in Di, fij>0 (i=1,2,…,n; j=1,2,…,m).


### 2.1.1. Information Gain (IG)

IG selects features according to amounts of information that a feature uses for classification [4–6]. IG of fj in text classification is given by the following formula: (3)IGfj=-∑k=1tPcklog⁡⁡Pck+Pfj·∑k=1tPck∣fjlog⁡⁡Pck∣fj+1-Pfj·∑k=1t1-Pck∣fjlog⁡⁡1-Pck∣fj.Some studies have applied IG to feature selection for text classification [7–9], including improvements of IG [10, 11].


### 2.1.2. Mutual Information (MI)

MI [12, 13] observes interesting relationship between two variables. MI of fj in text classification is given by the following formula: (4)MIfj=∑k=1tPcklog⁡⁡Pfj∩ckPfj×Pck.MI has been used in feature selection for text classification in current studies [14, 15]. Improvements on MI are also covered in current studies [16, 17].


### 2.1.3. Gini Index (GI)

GI is first introduced in CART (a typical decision tree algorithm) to evaluate impurity offj [6, 18]. GI of fj in text classification is given by the following formula: (5)GIfj=1-∑k=1tP2fj∣ck.GI has been used in feature selection for text classification [19]. Improvements of GI are also catch attentions of current studies [20].


### 2.1.4. Expected Cross Entropy (ECE)

The same as IG and MI, ECE [21] is a measure from information theory. ECE of fj in text classification is given by the following formula:(6)ECEfj=Pfj∑k=1tPck∣fjlog⁡⁡Pck∣fjPfj.ECE is imposed to feature selection for text classification in some studies [22, 23], including improvements of ECE [24].


## 2.1.1. Information Gain (IG)

IG selects features according to amounts of information that a feature uses for classification [4–6]. IG of fj in text classification is given by the following formula: (3)IGfj=-∑k=1tPcklog⁡⁡Pck+Pfj·∑k=1tPck∣fjlog⁡⁡Pck∣fj+1-Pfj·∑k=1t1-Pck∣fjlog⁡⁡1-Pck∣fj.Some studies have applied IG to feature selection for text classification [7–9], including improvements of IG [10, 11].


## 2.1.2. Mutual Information (MI)

MI [12, 13] observes interesting relationship between two variables. MI of fj in text classification is given by the following formula: (4)MIfj=∑k=1tPcklog⁡⁡Pfj∩ckPfj×Pck.MI has been used in feature selection for text classification in current studies [14, 15]. Improvements on MI are also covered in current studies [16, 17].


## 2.1.3. Gini Index (GI)

GI is first introduced in CART (a typical decision tree algorithm) to evaluate impurity offj [6, 18]. GI of fj in text classification is given by the following formula: (5)GIfj=1-∑k=1tP2fj∣ck.GI has been used in feature selection for text classification [19]. Improvements of GI are also catch attentions of current studies [20].


## 2.1.4. Expected Cross Entropy (ECE)

The same as IG and MI, ECE [21] is a measure from information theory. ECE of fj in text classification is given by the following formula:(6)ECEfj=Pfj∑k=1tPck∣fjlog⁡⁡Pck∣fjPfj.ECE is imposed to feature selection for text classification in some studies [22, 23], including improvements of ECE [24].


## 2.2. Unsupervised Feature Selection Methods

ForDTM in (1), f-j is the mean of fj and f-j=1/n∑ifij.


### 2.2.1. Document Frequency (DF)

DF [7, 25] assumes that frequent terms are more informative than nonfrequent terms. DF is the total number of documents in which fj appears. DF is usually used as a criterion to evaluate efficiency of other feature selection methods. DF of fj is given by the following formula:(7)DFfj=nfij>0i=1,2,…,n;j=1,2,…,m.n(fij>0) denotes the total number of documents in which fj appears. A discriminative feature gets high DF. Improvements on DF have been proposed in some studies [26, 27].


### 2.2.2. Variance Score (VS)

VS [25] ranks features by calculating variance of each feature fj in DTM. VS is given by the following formula:(8)VSfj=Var⁡fj=1n∑i=1nfij-f-j2.A discriminative feature gets high VS. VS is a simple feature selection method used in feature selection for text mining [28].


### 2.2.3. Laplacian Score (LS)

It is the key assumption of LS that data from the same class label are often close to each other and the importance of a feature is evaluated by its power of locality preserving ability and LS is described as follows [3]:(9)LSfj=∑pqfpj-fqj2SpqVar⁡fj.Spq evaluates the similarity between Dp and Dq. Dp and Dq are similar if Dp is among k nearest neighbors of Dq or Dq is among k nearest neighbors of Dp. Spq is given by the following formula:(10)Spq=e-Dp-Dq2/t,ifDpandDqare similar0,otherwise.t is a suitable constant. Spq is the p,q element of weighted matrix S which evaluates similarities of samples of D.Define vectorl=[1,1,…,1]T, then A=diag⁡(Sl). Var⁡(fj) in formula (4) is the weighted variance of fj. Var⁡(fj) is given by the following formula:(11)Var⁡fj=∑ifij-f-j2Aii.Aii is the (i,i) element of A. The weighted variance can be simply replaced by standard variance formulated as the following formula:(12)Var⁡fj=∑ifij-f-j2.For a discriminative feature,(fpj-fqj) is smaller whenever Spq is bigger and, on the other hand, Var⁡fj is bigger. Thus, LS of a discriminative feature tends to be small. (more details of LS are in [3]).LS is able to evaluate and rank importance of features and it has been used incurrent studies. He et al. [3] propose LS for feature selection and apply it and data variance (VS) to select features from CUM PIE face database for clustering. Experimental results show that LS performs better than data variance (VS) in several tests with different clusters (k=5,10,30,68). Hu and Man [29] impose LS to spare coding. They use it to evaluate the locality preserving ability of candidate atoms from data examples and select high ranked candidates. Experiments on UCI data demonstrate effectiveness, which also indicates efficiency of LS. Solorio-Fernández et al. [30] propose LS for supervised feature selection. It is imposed to rank features to reduce the search space. This method outperforms better than the other feature selection methods on UCI data sets. Good performance of this method also demonstrates robustness of LS in feature selection. Huang et al. [31] propose LS for face recognition. They impose LS to rank the regular and irregular features in order to achieve the best performances more quickly and it is demonstrated that it is better than other several methods. It is proved that it is capable of giving a better ranking of features in their experiments. Chunlu et al. [32] study classification of sMRI data in Alzheimer’s disease. LS is imposed to select more discriminative features by evaluating their locality preserving abilities. Experimental results prove robustness of LS in feature selection. Bo et al. [33] impose LS to gene feature selection and develop a new method called locality sensitive Laplacian Score (LSLS) by combining LS and locality sensitive discriminant analysis. Experimental results indicate that the method is effective and LS performs well.Current studies major in the ideas of improving LS. Liu et al. [34] propose an improved method called LSE (Laplacian Score combined with distance-based entropy measure) for unsupervised feature selection. LSE uses entropy measure to replace k-means clustering used in LS to solve the drawbacks of LS. Experimental results of 6 UCI data sets demonstrate that LSE performs better than LS. Padungweang et al. [35] also propose an efficient method based on the strong constraint on the global topology of the data space. Experimental results indicate that compared with conventional LS, this method has better performances. Zhu et al. [36] propose an improved LS method called IterativeLS. It tires improving LS by gradually improving the nearest neighbor graph by discarding the least relevant features at each iteration. Experimental results on both UCI data sets and face databases demonstrate that IterativeLS performs better than LS. Benabdeslem and Hindawi [37] address the problem of semisupervised feature selection for high-dimensional data and propose Constrained Laplacian Score (CLS) to improve LS. Experimental results on 5 UCI data sets demonstrate that CLS is better than LS in the problem of semisupervised feature selection. Moreover, Wang et al. [38] also propose a new method termed Label Reconstruction based Laplacian Score (LRLS) to improve LS for semisupervised feature selection. Experimental results on three UCI data sets indicate that LRLS is clearly better than LS in most occasions.It is shown that LS is efficient and widely used in feature selection of current studies. It is used as a benchmark technique in order to compare with a new technique in both unsupervised and supervised feature selections [35]. LS is successfully used in some areas such as sparse coding [29], face recognition [31], and gene feature selection [33]. This paper studies feature selection in text classification and argues that conventional LS is not appropriate for feature selection of DTM. This paper proposes an unsupervised method termed DVS to improve LS in feature selection of DTM. Section 3 introduces DVS and analyzes details of DVS.Current feature selection methods for text classification have been studied a lot and a lot of improvements have been proposed. LS is proved discriminative in the application of several areas. However, LS has not been used in feature selection for text classification currently. We are interested in performances of this proved-discriminative method in text classification. LS performs poorly in experiments. Through further analysis, we found that LS is not appropriate for text classification because LS is not able to select discriminative features from a usually sparseDTM. A new method called DVS is proposed to improve LS in text classification. DVS uses difference measure to replace similarity measure of original LS. More discussions of DVS and LS are covered in Section 4.2.3.


## 2.2.1. Document Frequency (DF)

DF [7, 25] assumes that frequent terms are more informative than nonfrequent terms. DF is the total number of documents in which fj appears. DF is usually used as a criterion to evaluate efficiency of other feature selection methods. DF of fj is given by the following formula:(7)DFfj=nfij>0i=1,2,…,n;j=1,2,…,m.n(fij>0) denotes the total number of documents in which fj appears. A discriminative feature gets high DF. Improvements on DF have been proposed in some studies [26, 27].


## 2.2.2. Variance Score (VS)

VS [25] ranks features by calculating variance of each feature fj in DTM. VS is given by the following formula:(8)VSfj=Var⁡fj=1n∑i=1nfij-f-j2.A discriminative feature gets high VS. VS is a simple feature selection method used in feature selection for text mining [28].


## 2.2.3. Laplacian Score (LS)

It is the key assumption of LS that data from the same class label are often close to each other and the importance of a feature is evaluated by its power of locality preserving ability and LS is described as follows [3]:(9)LSfj=∑pqfpj-fqj2SpqVar⁡fj.Spq evaluates the similarity between Dp and Dq. Dp and Dq are similar if Dp is among k nearest neighbors of Dq or Dq is among k nearest neighbors of Dp. Spq is given by the following formula:(10)Spq=e-Dp-Dq2/t,ifDpandDqare similar0,otherwise.t is a suitable constant. Spq is the p,q element of weighted matrix S which evaluates similarities of samples of D.Define vectorl=[1,1,…,1]T, then A=diag⁡(Sl). Var⁡(fj) in formula (4) is the weighted variance of fj. Var⁡(fj) is given by the following formula:(11)Var⁡fj=∑ifij-f-j2Aii.Aii is the (i,i) element of A. The weighted variance can be simply replaced by standard variance formulated as the following formula:(12)Var⁡fj=∑ifij-f-j2.For a discriminative feature,(fpj-fqj) is smaller whenever Spq is bigger and, on the other hand, Var⁡fj is bigger. Thus, LS of a discriminative feature tends to be small. (more details of LS are in [3]).LS is able to evaluate and rank importance of features and it has been used incurrent studies. He et al. [3] propose LS for feature selection and apply it and data variance (VS) to select features from CUM PIE face database for clustering. Experimental results show that LS performs better than data variance (VS) in several tests with different clusters (k=5,10,30,68). Hu and Man [29] impose LS to spare coding. They use it to evaluate the locality preserving ability of candidate atoms from data examples and select high ranked candidates. Experiments on UCI data demonstrate effectiveness, which also indicates efficiency of LS. Solorio-Fernández et al. [30] propose LS for supervised feature selection. It is imposed to rank features to reduce the search space. This method outperforms better than the other feature selection methods on UCI data sets. Good performance of this method also demonstrates robustness of LS in feature selection. Huang et al. [31] propose LS for face recognition. They impose LS to rank the regular and irregular features in order to achieve the best performances more quickly and it is demonstrated that it is better than other several methods. It is proved that it is capable of giving a better ranking of features in their experiments. Chunlu et al. [32] study classification of sMRI data in Alzheimer’s disease. LS is imposed to select more discriminative features by evaluating their locality preserving abilities. Experimental results prove robustness of LS in feature selection. Bo et al. [33] impose LS to gene feature selection and develop a new method called locality sensitive Laplacian Score (LSLS) by combining LS and locality sensitive discriminant analysis. Experimental results indicate that the method is effective and LS performs well.Current studies major in the ideas of improving LS. Liu et al. [34] propose an improved method called LSE (Laplacian Score combined with distance-based entropy measure) for unsupervised feature selection. LSE uses entropy measure to replace k-means clustering used in LS to solve the drawbacks of LS. Experimental results of 6 UCI data sets demonstrate that LSE performs better than LS. Padungweang et al. [35] also propose an efficient method based on the strong constraint on the global topology of the data space. Experimental results indicate that compared with conventional LS, this method has better performances. Zhu et al. [36] propose an improved LS method called IterativeLS. It tires improving LS by gradually improving the nearest neighbor graph by discarding the least relevant features at each iteration. Experimental results on both UCI data sets and face databases demonstrate that IterativeLS performs better than LS. Benabdeslem and Hindawi [37] address the problem of semisupervised feature selection for high-dimensional data and propose Constrained Laplacian Score (CLS) to improve LS. Experimental results on 5 UCI data sets demonstrate that CLS is better than LS in the problem of semisupervised feature selection. Moreover, Wang et al. [38] also propose a new method termed Label Reconstruction based Laplacian Score (LRLS) to improve LS for semisupervised feature selection. Experimental results on three UCI data sets indicate that LRLS is clearly better than LS in most occasions.It is shown that LS is efficient and widely used in feature selection of current studies. It is used as a benchmark technique in order to compare with a new technique in both unsupervised and supervised feature selections [35]. LS is successfully used in some areas such as sparse coding [29], face recognition [31], and gene feature selection [33]. This paper studies feature selection in text classification and argues that conventional LS is not appropriate for feature selection of DTM. This paper proposes an unsupervised method termed DVS to improve LS in feature selection of DTM. Section 3 introduces DVS and analyzes details of DVS.Current feature selection methods for text classification have been studied a lot and a lot of improvements have been proposed. LS is proved discriminative in the application of several areas. However, LS has not been used in feature selection for text classification currently. We are interested in performances of this proved-discriminative method in text classification. LS performs poorly in experiments. Through further analysis, we found that LS is not appropriate for text classification because LS is not able to select discriminative features from a usually sparseDTM. A new method called DVS is proposed to improve LS in text classification. DVS uses difference measure to replace similarity measure of original LS. More discussions of DVS and LS are covered in Section 4.2.3.


## 3. Distance Variance Score (DVS)

### 3.1. Feature Distance Contributions (DC)

It is the difference between DVS and LS that DVS takes difference measures among text documents inDTM instead of similarity measures. Let DCfj denote feature distance contributions of fj. DCfj shows how much fj contributes to differences among text documents in DTM so as to evaluate importance of fj for text classification. DCfj is given by the following formula:(13)DCfj=∑pqdist⁡fpj,fqjdist⁡Dp,Dq.dist
⁡
(
) is a distance measure. dist⁡(Dp,Dq) evaluates the difference between Dp and Dq and dist⁡(fpj,fqj) evaluates the difference between fpj and fqj. DCfr is a ratio to show the importance of dist⁡(fpj,fqj) for dist⁡(Dp,Dq). dist⁡(fpj,fqj) gives little information to understand how much it contributes to dist⁡(Dp,Dq). However, if dist⁡(Dp,Dq) is taken into account, it is easy to understand how much dist⁡(fpj,fqj) contributes to dist⁡(Dp,Dq). City block distance is introduced to implement dist⁡() because it is a well-know and computationally easy-calculated distance measure [6]. dist⁡Dp,Dq=∑kfpk-fqk and dist⁡fpj,fqj=fpj-fqj.Consider theDTM in (16):(14)dist⁡D1,D2=∑k=19f1k-f2k=20,dist⁡f13,f23=f13-f23=8,dist⁡D3,D4=∑k=19f3k-f4k=10,dist⁡f33,f34=f33-f43=5.Obviously,dist⁡f13,f23>dist⁡f33,f43 but it is hard to understand whether dist⁡f13,f23 contributes more to dist⁡D1,D2 than dist⁡f33,f43 contributes to dist⁡D3,D4. However, if dist⁡D1,D2 and dist⁡D3,D4 are taken into account,(15)DCf31=dist⁡f13,f23dist⁡D1,D2=40%,DCf32=dist⁡f33,f43dist⁡D3,D4=50%.It is clear thatdist⁡f13,f23 contributes 40% to dist⁡D1,D2 and dist⁡f33,f43 contributes 50% to dist⁡D3,D4, which indicates that dist⁡f33,f43 is more important for dist⁡D3,D4 than dist⁡f13,f23 is for dist⁡D1,D2.DC
f
j is efficient to evaluates importance of a given feature fj for text documents.A
D
T
M
(16)
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
D
1
0
0
0
1
0
0
0
5
9
D
2
0
0
8
3
0
0
0
6
0
D
3
4
0
5
0
0
0
0
0
0
D
4
0
0
0
1
0
0
0
0
0
D
5
0
1
0
0
1
2
1
0
0


### 3.2. Algorithm of DVS

LetDTM=[D1,D2,…,Dn] denote a document term matrix of n text documents and Di=[fi1,fi2,…,fim](i=1,2,…,n) denote the ith text document of D. Let fj(j=1,2,…,m) denote the rth term of D and fij denote the ith term frequency of fj. Let DVS(fj) denote DVS of fj. DVS(fj) is formulated as:(17)DVSfj=Var⁡fj×DCfj=∑ifij-f-j2∑pqfpj-fqj∑kfpk-fqk.f
-
j is the mean of fj. DVS is constructed by two parts: standard variance Var(fj) (shown in formula (8)) and feature distance contributions DC(fj). Var(fj) shows global structure of a given feature and DC(fj) shows local structure of a given feature. The key idea of DVS in choosing discriminative features is that a feature fj is discriminative if it contains much information (Var(fj) is large) and it contributes much to differences among documents (DCfj is large). DVS is able to show differences among documents so as to classify text documents from different classes. Spq and Dp-Dq2 in original LS (shown in Formula (6)) are replaced by DC(fj) to evaluate differences instead of similarities. More details of DC(fj) are in Section 3.1. For a discriminative feature fj, if DCfj and Var(fj) are large, DVSfj is large, too.Algorithm of feature selection using DVS is shown in Algorithm1.  DVSfj of each fj is calculated using DVS() and all the DVSfj are sorted in decreasing order using FSDVS() in Algorithm 1.  FSDVS() also creates a matrix dmat such that dmatp,q=dist⁡(Dp,Dq). dmat is used to store city block distances among documents to avoid recalculating each dist⁡(Dp,Dq) in procedure DVS() so as to improve efficiency of the algorithm. The N features whose DVS are bigger are chosen for text classification. N is determined manually.Algorithm 1:Algorithm of feature selection using DVS.
Procedure  FSDVS(DTM,N)
begin
let  mapf denotes the map storing fj and DVS(fj) and mapf=null
#dmat is the matrix to store value of city block distance among documents and
#dmat[p,q]=dist(Dp,Dq)
#whenp=q, dmat[p,q]=0
for each p in Id  do
for each q in Id  do
dmat[p,q]=dist⁡(Dp,Dq);
end
end
#calculateDVS(fj) for each fj
for  j in DTM  do
mapf.key=fj;
mapf[fj]=DVS(fj,dmat);
end
#sortmapf in decreasing order according to value
mapf=sort(mapf);
#select and return the firstN features
return  mapf[1:N];
end
Procedure  DVS(fj,dmat)
#dmat is the matrix to store value of city block distance among documents and
#dmat[p,q]=distDp,Dq
#whenp=q, dmatp,q=0
begin
let  Var(fj) denotes the standard variance of fj
let  DC(fj) denotes feature distance contributions of fj
let  Id denotes the index vector of samples in D and Id=[1,2,…,n]
#calculateDC(fj).  See Section 3.1
for each p in Id  do
for each q in Id and p≠q  do
#calculate city block distance betweenDp and Dq. See Section 3.1
distx=dmat[p,q];
#calculate city block distance betweenfpj and fqj. See Section 3.1
distf=dist(fpj,fqj);
DC(fj) += distf/distx;
end
end
return  var(fj)∗DC(fj);
end


## 3.1. Feature Distance Contributions (DC)

It is the difference between DVS and LS that DVS takes difference measures among text documents inDTM instead of similarity measures. Let DCfj denote feature distance contributions of fj. DCfj shows how much fj contributes to differences among text documents in DTM so as to evaluate importance of fj for text classification. DCfj is given by the following formula:(13)DCfj=∑pqdist⁡fpj,fqjdist⁡Dp,Dq.dist
⁡
(
) is a distance measure. dist⁡(Dp,Dq) evaluates the difference between Dp and Dq and dist⁡(fpj,fqj) evaluates the difference between fpj and fqj. DCfr is a ratio to show the importance of dist⁡(fpj,fqj) for dist⁡(Dp,Dq). dist⁡(fpj,fqj) gives little information to understand how much it contributes to dist⁡(Dp,Dq). However, if dist⁡(Dp,Dq) is taken into account, it is easy to understand how much dist⁡(fpj,fqj) contributes to dist⁡(Dp,Dq). City block distance is introduced to implement dist⁡() because it is a well-know and computationally easy-calculated distance measure [6]. dist⁡Dp,Dq=∑kfpk-fqk and dist⁡fpj,fqj=fpj-fqj.Consider theDTM in (16):(14)dist⁡D1,D2=∑k=19f1k-f2k=20,dist⁡f13,f23=f13-f23=8,dist⁡D3,D4=∑k=19f3k-f4k=10,dist⁡f33,f34=f33-f43=5.Obviously,dist⁡f13,f23>dist⁡f33,f43 but it is hard to understand whether dist⁡f13,f23 contributes more to dist⁡D1,D2 than dist⁡f33,f43 contributes to dist⁡D3,D4. However, if dist⁡D1,D2 and dist⁡D3,D4 are taken into account,(15)DCf31=dist⁡f13,f23dist⁡D1,D2=40%,DCf32=dist⁡f33,f43dist⁡D3,D4=50%.It is clear thatdist⁡f13,f23 contributes 40% to dist⁡D1,D2 and dist⁡f33,f43 contributes 50% to dist⁡D3,D4, which indicates that dist⁡f33,f43 is more important for dist⁡D3,D4 than dist⁡f13,f23 is for dist⁡D1,D2.DC
f
j is efficient to evaluates importance of a given feature fj for text documents.A
D
T
M
(16)
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
D
1
0
0
0
1
0
0
0
5
9
D
2
0
0
8
3
0
0
0
6
0
D
3
4
0
5
0
0
0
0
0
0
D
4
0
0
0
1
0
0
0
0
0
D
5
0
1
0
0
1
2
1
0
0


## 3.2. Algorithm of DVS

LetDTM=[D1,D2,…,Dn] denote a document term matrix of n text documents and Di=[fi1,fi2,…,fim](i=1,2,…,n) denote the ith text document of D. Let fj(j=1,2,…,m) denote the rth term of D and fij denote the ith term frequency of fj. Let DVS(fj) denote DVS of fj. DVS(fj) is formulated as:(17)DVSfj=Var⁡fj×DCfj=∑ifij-f-j2∑pqfpj-fqj∑kfpk-fqk.f
-
j is the mean of fj. DVS is constructed by two parts: standard variance Var(fj) (shown in formula (8)) and feature distance contributions DC(fj). Var(fj) shows global structure of a given feature and DC(fj) shows local structure of a given feature. The key idea of DVS in choosing discriminative features is that a feature fj is discriminative if it contains much information (Var(fj) is large) and it contributes much to differences among documents (DCfj is large). DVS is able to show differences among documents so as to classify text documents from different classes. Spq and Dp-Dq2 in original LS (shown in Formula (6)) are replaced by DC(fj) to evaluate differences instead of similarities. More details of DC(fj) are in Section 3.1. For a discriminative feature fj, if DCfj and Var(fj) are large, DVSfj is large, too.Algorithm of feature selection using DVS is shown in Algorithm1.  DVSfj of each fj is calculated using DVS() and all the DVSfj are sorted in decreasing order using FSDVS() in Algorithm 1.  FSDVS() also creates a matrix dmat such that dmatp,q=dist⁡(Dp,Dq). dmat is used to store city block distances among documents to avoid recalculating each dist⁡(Dp,Dq) in procedure DVS() so as to improve efficiency of the algorithm. The N features whose DVS are bigger are chosen for text classification. N is determined manually.Algorithm 1:Algorithm of feature selection using DVS.
Procedure  FSDVS(DTM,N)
begin
let  mapf denotes the map storing fj and DVS(fj) and mapf=null
#dmat is the matrix to store value of city block distance among documents and
#dmat[p,q]=dist(Dp,Dq)
#whenp=q, dmat[p,q]=0
for each p in Id  do
for each q in Id  do
dmat[p,q]=dist⁡(Dp,Dq);
end
end
#calculateDVS(fj) for each fj
for  j in DTM  do
mapf.key=fj;
mapf[fj]=DVS(fj,dmat);
end
#sortmapf in decreasing order according to value
mapf=sort(mapf);
#select and return the firstN features
return  mapf[1:N];
end
Procedure  DVS(fj,dmat)
#dmat is the matrix to store value of city block distance among documents and
#dmat[p,q]=distDp,Dq
#whenp=q, dmatp,q=0
begin
let  Var(fj) denotes the standard variance of fj
let  DC(fj) denotes feature distance contributions of fj
let  Id denotes the index vector of samples in D and Id=[1,2,…,n]
#calculateDC(fj).  See Section 3.1
for each p in Id  do
for each q in Id and p≠q  do
#calculate city block distance betweenDp and Dq. See Section 3.1
distx=dmat[p,q];
#calculate city block distance betweenfpj and fqj. See Section 3.1
distf=dist(fpj,fqj);
DC(fj) += distf/distx;
end
end
return  var(fj)∗DC(fj);
end


## 4. Experiments

### 4.1. Data

DBWorld e-mails data set is taken from UCI ML repository and contains 64 e-mails of two classes manually collected from DBWorld mailing list. This data set is represented asDTM. Each attribute corresponds to a term in documents. This data set is donated on the 6th of November, 2011, and it is for classification task. Stop Words have been removed in the preprocessing task. The donator has used it to train different classification algorithms.CNAE data set is also taken form UCI ML repository. It contains 1080 documents of free text business descriptions of Brazilian companies categorized into a subset of 9 categories. Each document of this data set is represented as a term vector. CNAE data set is then transformed into aDTM for experiments. The donator donated this data set on the 3rd of October, 2012.Details about the two data sets are shown in Table1.Table 1
Details of the two UCI data sets.
Data set
DBWorld data set
CNAE data set
Number of documents
64
1080
Number of terms
3721
856
Data preprocessing task
Stop word removal
—
Associated tasks
Classification
Classification
Date donated
2011-11-06
2012-08-03
Number of web hits
13438
17858


### 4.2. Discriminative Features Experiments

#### 4.2.1. Experiments of DVS

DVS is calculated using formula (17).DVS
f
j are calculated using DVS() in Algorithm 1   and all the DVSfj are sorted in decreasing order using FSDVS() in Algorithm 1.   For both data sets, the N features of total features are selected by LS and DVS from feature spaces to compare performances of LS and DVS. It shows performances of LS and DVS as N rapidly decreases, choosing N = 2721, 1721, 721, 521, 321, 121, and 21 for DBWorld data set and, moreover, choosing N = 656, 456, 256, 156, and 56 for CNAE data set. DF can be used as a criterion to evaluate performance of a feature selection method for text mining. DF is also applied to experiments to select features from the two data sets to evaluate performance of DVS.In order to compare efficiency of LS and DVS for feature selection, features selected by LS and DVS are tested by classifiers. The commonly used classifiers for text classification include Naïve Bayes [39, 40], k-nearest neighbor [40, 41], neural network [42, 43], support vector machine (SVM, [40]), and decision tree (DT, [40, 43]). This paper chooses DT(C5.0) and SVM to test features selected by LS and DVS because DT has been used either as main classification tool or as baseline classifier and SVM offers two advantages for text classification, according to Fabrizio’s paper [43].Both data sets are separated into training sets and testing sets. A training set is 70% of the whole data set. DT(C5.0) and SVM classifiers are constructed to test the firstN features selected by LS and DVS. Meanwhile, DT(C5.0) and SVM classifiers constructed by total features are used as baselines to compare efficiency of LS and DVS for feature selection.For eachN, 20 DT(C5.0) and 20 SVM classifiers are constructed using randomly separated training sets. “Two-tailed paired t test” is used to test whether feature selection using LS and DVS will affect accuracy of classification. If significances (Sig.’s) are lower than 0.05, then means of the baseline and means of classifiers using LS or DVS are considered not the same (to reject the null hypothesis); that is, LS or DVS will affect accuracy of classification negatively or positively. If Sig.’s are greater than 0.05, then mean of the pairs is considered the same (not to reject the null hypothesis); that is, LS or DVS has no effects on accuracy of classification.


#### 4.2.2. Experimental Results

Figure1 shows average accuracies of each N of both DT(C5.0) and SVM classifiers of the two data sets. Obviously, DVS outperforms LS and accuracy of classifiers using feature selected by DVS keeps in a high level as N reduces from 2721 to 21 and from 656 to 56. Features selected by DVS are more effective than those selected by LS. At a very small subfeature space, classifiers using LS gets low accuracies. High accuracies can be achieved by using features selected by DVS. Figure 1 also shows that DVS performs as well as DF. Furthermore, Table 2 shows average accuracies (mean) and standard deviations (std) of testing sets of classifiers and results of two-tailed paired t test. For DBWorld data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. On the contrary, in Table 2(a), all the significances of the two classifiers using DVS are much higher than 0.05, showing that DVS significantly gets the same good classification accuracies as baseline. For CNAE data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. Classifiers using LS gets a very low accuracies when N = 156 or 56. Table 2(b) shows that DT(C5.0) using DVS significantly gets the same good accuracies as baseline. However, in Table 2(b), SVM using DVS does not significantly gets the same accuracies as baseline still keeps relatively high accuracies. Figure 1 shows low accuracies of classifier using features selected by LS. Feature selected by LS have negative effects on text classification, especially when N is very small. Figure 1 shows high accuracies of classifiers using features selected by DVS. Feature selected by DVS have positive effects on text classification. Figure 1 also shows that DVS performs better in DT(C5.0) than in SVM.Table 2
Accuracy of classifiers (unit for mean and std: %).
(a)
DBWorld data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
3721
91.30± 7.54
—
85.73± 6.73
—
91.30± 7.54
—
85.73± 6.73
—
2721
82.64± 8.17
.004
84.14± 7.06
.505
89.50± 6.59
.736
85.22± 6.10
.807
1721
70.27± 8.22
.000
80.73± 6.68
.023
89.61± 5.57
.779
87.02± 8.92
.291
721
58.53± 10.52
.000
63.97± 11.09
.000
91.74± 6.07
.433
84.15± 8.67
.129
521
56.49± 6.94
.000
62.66± 9.16
.000
89.07± 7.08
.185
85.10± 7.57
.584
321
53.58± 10.79
.000
57.75± 8.83
.000
92.16± 4.58
.454
83.55± 7.19
.192
121
52.44± 10.34
.000
51.92± 10.91
.000
92.74± 6.61
.179
90.56± 6.16
.098
21
58.03± 6.73
.000
57.38± 9.53
.000
88.26± 7.68
.332
91.40± 6.41
.722
(b)
CNAE data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
856
87.59± 2.25
—
92.93± 1.58
—
87.59± 2.25
—
92.93± 1.58
—
656
86.67± 2.21
.910
82.19± 4.52
.000
87.64± 1.77
.924
83.41± 2.02
.000
456
86.87± 2.62
.394
84.42± 2.26
.000
88.25± 1.86
.338
85.18± 2.73
.000
256
73.11± 2.77
.000
66.53± 2.09
.000
87.93± 2.31
.700
84.53± 2.12
.000
156
17.60± 1.48
.000
15.08± 2.48
.000
86.54± 2.46
.146
82.77± 2.33
.000
56
8.86± 0.930
.000
5.33± 0.95
.000
81.99± 1.90
.000
77.47± 2.33
.000Figure 1
Accuracy of classifiers of two UCI data set.
(a)
DBWorld data set
(b)
CNAE data setExperimental results in this paper show that DVS is much better than LS in feature selection of text classification, especially asN is reduced to a small number. Features selected by DVS have positive effects on text classification and features selected by LS make negative effects. DVS is able to overcomes negative effects caused by sparsity of DTM.


#### 4.2.3. More Discussion about DVS and LS

As mentioned above, it is the key assumption of LS that documents with the same class are close. LS of a discriminative feature should be smaller. Consider formula (10) introduced in Section 2. LS uses Spq to measure similarity between Dp and Dq and (fpj-fqj)2 to measure similarity between fpj and fqj. For a discriminative feature, (fpj-fqj)2Spq tends to small, which indicates that each feature selected by LS contains many 0 values. Thus, LS is easily affected by 0 values in DTM and the sub-DTMs constructed by features selected by LS are also sparse. As N reduces, the sub-DTMs contain less and less information, resulting in pool performances of classifiers in text classification. On the contrary, the key idea of DVS is that text documents with different classes are not close. DVS tries to discover differences instead of similarities among documents and DCfj are used to evaluate how much a feature contributes to differences among text documents. DCfj pays much attention to nonzero value and is able to avoid negative effects caused by 0 values. Thus, DVS is capable of reducing the sparsity of DTM and select discriminative features capable of discovering differences among text documents. By discovering differences among text documents, DVS is much more efficient than LS. The sparsity of sub-DTMs of LS and DVS is shown in Table 3. Table 3 shows that as N reduces, the sparsity of sub-DTMs constructed by features selected by DVS also reduce but the sparsity of sub-DTMs constructed by features selected by LS still keep a high level.Table 3
The sparsity of sub-DTMs constructed by features selected by LS and DVS (unit: %).
DBWorld data set
CNAE data set
N
DVS
LS
N
DVS
LS
3721
95.01
856
99.20
2721
93.76
97.28
656
99.00
99.01
1721
91.04
98.00
456
98.60
98.81
721
83.16
98.10
256
97.73
98.68
521
79.47
98.03
156
96.60
99.78
321
73.01
98.40
56
92.80
99.90
121
61.23
98.44
21
49.70
98.44


## 4.1. Data

DBWorld e-mails data set is taken from UCI ML repository and contains 64 e-mails of two classes manually collected from DBWorld mailing list. This data set is represented asDTM. Each attribute corresponds to a term in documents. This data set is donated on the 6th of November, 2011, and it is for classification task. Stop Words have been removed in the preprocessing task. The donator has used it to train different classification algorithms.CNAE data set is also taken form UCI ML repository. It contains 1080 documents of free text business descriptions of Brazilian companies categorized into a subset of 9 categories. Each document of this data set is represented as a term vector. CNAE data set is then transformed into aDTM for experiments. The donator donated this data set on the 3rd of October, 2012.Details about the two data sets are shown in Table1.Table 1
Details of the two UCI data sets.
Data set
DBWorld data set
CNAE data set
Number of documents
64
1080
Number of terms
3721
856
Data preprocessing task
Stop word removal
—
Associated tasks
Classification
Classification
Date donated
2011-11-06
2012-08-03
Number of web hits
13438
17858


## 4.2. Discriminative Features Experiments

### 4.2.1. Experiments of DVS

DVS is calculated using formula (17).DVS
f
j are calculated using DVS() in Algorithm 1   and all the DVSfj are sorted in decreasing order using FSDVS() in Algorithm 1.   For both data sets, the N features of total features are selected by LS and DVS from feature spaces to compare performances of LS and DVS. It shows performances of LS and DVS as N rapidly decreases, choosing N = 2721, 1721, 721, 521, 321, 121, and 21 for DBWorld data set and, moreover, choosing N = 656, 456, 256, 156, and 56 for CNAE data set. DF can be used as a criterion to evaluate performance of a feature selection method for text mining. DF is also applied to experiments to select features from the two data sets to evaluate performance of DVS.In order to compare efficiency of LS and DVS for feature selection, features selected by LS and DVS are tested by classifiers. The commonly used classifiers for text classification include Naïve Bayes [39, 40], k-nearest neighbor [40, 41], neural network [42, 43], support vector machine (SVM, [40]), and decision tree (DT, [40, 43]). This paper chooses DT(C5.0) and SVM to test features selected by LS and DVS because DT has been used either as main classification tool or as baseline classifier and SVM offers two advantages for text classification, according to Fabrizio’s paper [43].Both data sets are separated into training sets and testing sets. A training set is 70% of the whole data set. DT(C5.0) and SVM classifiers are constructed to test the firstN features selected by LS and DVS. Meanwhile, DT(C5.0) and SVM classifiers constructed by total features are used as baselines to compare efficiency of LS and DVS for feature selection.For eachN, 20 DT(C5.0) and 20 SVM classifiers are constructed using randomly separated training sets. “Two-tailed paired t test” is used to test whether feature selection using LS and DVS will affect accuracy of classification. If significances (Sig.’s) are lower than 0.05, then means of the baseline and means of classifiers using LS or DVS are considered not the same (to reject the null hypothesis); that is, LS or DVS will affect accuracy of classification negatively or positively. If Sig.’s are greater than 0.05, then mean of the pairs is considered the same (not to reject the null hypothesis); that is, LS or DVS has no effects on accuracy of classification.


### 4.2.2. Experimental Results

Figure1 shows average accuracies of each N of both DT(C5.0) and SVM classifiers of the two data sets. Obviously, DVS outperforms LS and accuracy of classifiers using feature selected by DVS keeps in a high level as N reduces from 2721 to 21 and from 656 to 56. Features selected by DVS are more effective than those selected by LS. At a very small subfeature space, classifiers using LS gets low accuracies. High accuracies can be achieved by using features selected by DVS. Figure 1 also shows that DVS performs as well as DF. Furthermore, Table 2 shows average accuracies (mean) and standard deviations (std) of testing sets of classifiers and results of two-tailed paired t test. For DBWorld data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. On the contrary, in Table 2(a), all the significances of the two classifiers using DVS are much higher than 0.05, showing that DVS significantly gets the same good classification accuracies as baseline. For CNAE data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. Classifiers using LS gets a very low accuracies when N = 156 or 56. Table 2(b) shows that DT(C5.0) using DVS significantly gets the same good accuracies as baseline. However, in Table 2(b), SVM using DVS does not significantly gets the same accuracies as baseline still keeps relatively high accuracies. Figure 1 shows low accuracies of classifier using features selected by LS. Feature selected by LS have negative effects on text classification, especially when N is very small. Figure 1 shows high accuracies of classifiers using features selected by DVS. Feature selected by DVS have positive effects on text classification. Figure 1 also shows that DVS performs better in DT(C5.0) than in SVM.Table 2
Accuracy of classifiers (unit for mean and std: %).
(a)
DBWorld data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
3721
91.30± 7.54
—
85.73± 6.73
—
91.30± 7.54
—
85.73± 6.73
—
2721
82.64± 8.17
.004
84.14± 7.06
.505
89.50± 6.59
.736
85.22± 6.10
.807
1721
70.27± 8.22
.000
80.73± 6.68
.023
89.61± 5.57
.779
87.02± 8.92
.291
721
58.53± 10.52
.000
63.97± 11.09
.000
91.74± 6.07
.433
84.15± 8.67
.129
521
56.49± 6.94
.000
62.66± 9.16
.000
89.07± 7.08
.185
85.10± 7.57
.584
321
53.58± 10.79
.000
57.75± 8.83
.000
92.16± 4.58
.454
83.55± 7.19
.192
121
52.44± 10.34
.000
51.92± 10.91
.000
92.74± 6.61
.179
90.56± 6.16
.098
21
58.03± 6.73
.000
57.38± 9.53
.000
88.26± 7.68
.332
91.40± 6.41
.722
(b)
CNAE data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
856
87.59± 2.25
—
92.93± 1.58
—
87.59± 2.25
—
92.93± 1.58
—
656
86.67± 2.21
.910
82.19± 4.52
.000
87.64± 1.77
.924
83.41± 2.02
.000
456
86.87± 2.62
.394
84.42± 2.26
.000
88.25± 1.86
.338
85.18± 2.73
.000
256
73.11± 2.77
.000
66.53± 2.09
.000
87.93± 2.31
.700
84.53± 2.12
.000
156
17.60± 1.48
.000
15.08± 2.48
.000
86.54± 2.46
.146
82.77± 2.33
.000
56
8.86± 0.930
.000
5.33± 0.95
.000
81.99± 1.90
.000
77.47± 2.33
.000Figure 1
Accuracy of classifiers of two UCI data set.
(a)
DBWorld data set
(b)
CNAE data setExperimental results in this paper show that DVS is much better than LS in feature selection of text classification, especially asN is reduced to a small number. Features selected by DVS have positive effects on text classification and features selected by LS make negative effects. DVS is able to overcomes negative effects caused by sparsity of DTM.


### 4.2.3. More Discussion about DVS and LS

As mentioned above, it is the key assumption of LS that documents with the same class are close. LS of a discriminative feature should be smaller. Consider formula (10) introduced in Section 2. LS uses Spq to measure similarity between Dp and Dq and (fpj-fqj)2 to measure similarity between fpj and fqj. For a discriminative feature, (fpj-fqj)2Spq tends to small, which indicates that each feature selected by LS contains many 0 values. Thus, LS is easily affected by 0 values in DTM and the sub-DTMs constructed by features selected by LS are also sparse. As N reduces, the sub-DTMs contain less and less information, resulting in pool performances of classifiers in text classification. On the contrary, the key idea of DVS is that text documents with different classes are not close. DVS tries to discover differences instead of similarities among documents and DCfj are used to evaluate how much a feature contributes to differences among text documents. DCfj pays much attention to nonzero value and is able to avoid negative effects caused by 0 values. Thus, DVS is capable of reducing the sparsity of DTM and select discriminative features capable of discovering differences among text documents. By discovering differences among text documents, DVS is much more efficient than LS. The sparsity of sub-DTMs of LS and DVS is shown in Table 3. Table 3 shows that as N reduces, the sparsity of sub-DTMs constructed by features selected by DVS also reduce but the sparsity of sub-DTMs constructed by features selected by LS still keep a high level.Table 3
The sparsity of sub-DTMs constructed by features selected by LS and DVS (unit: %).
DBWorld data set
CNAE data set
N
DVS
LS
N
DVS
LS
3721
95.01
856
99.20
2721
93.76
97.28
656
99.00
99.01
1721
91.04
98.00
456
98.60
98.81
721
83.16
98.10
256
97.73
98.68
521
79.47
98.03
156
96.60
99.78
321
73.01
98.40
56
92.80
99.90
121
61.23
98.44
21
49.70
98.44


## 4.2.1. Experiments of DVS

DVS is calculated using formula (17).DVS
f
j are calculated using DVS() in Algorithm 1   and all the DVSfj are sorted in decreasing order using FSDVS() in Algorithm 1.   For both data sets, the N features of total features are selected by LS and DVS from feature spaces to compare performances of LS and DVS. It shows performances of LS and DVS as N rapidly decreases, choosing N = 2721, 1721, 721, 521, 321, 121, and 21 for DBWorld data set and, moreover, choosing N = 656, 456, 256, 156, and 56 for CNAE data set. DF can be used as a criterion to evaluate performance of a feature selection method for text mining. DF is also applied to experiments to select features from the two data sets to evaluate performance of DVS.In order to compare efficiency of LS and DVS for feature selection, features selected by LS and DVS are tested by classifiers. The commonly used classifiers for text classification include Naïve Bayes [39, 40], k-nearest neighbor [40, 41], neural network [42, 43], support vector machine (SVM, [40]), and decision tree (DT, [40, 43]). This paper chooses DT(C5.0) and SVM to test features selected by LS and DVS because DT has been used either as main classification tool or as baseline classifier and SVM offers two advantages for text classification, according to Fabrizio’s paper [43].Both data sets are separated into training sets and testing sets. A training set is 70% of the whole data set. DT(C5.0) and SVM classifiers are constructed to test the firstN features selected by LS and DVS. Meanwhile, DT(C5.0) and SVM classifiers constructed by total features are used as baselines to compare efficiency of LS and DVS for feature selection.For eachN, 20 DT(C5.0) and 20 SVM classifiers are constructed using randomly separated training sets. “Two-tailed paired t test” is used to test whether feature selection using LS and DVS will affect accuracy of classification. If significances (Sig.’s) are lower than 0.05, then means of the baseline and means of classifiers using LS or DVS are considered not the same (to reject the null hypothesis); that is, LS or DVS will affect accuracy of classification negatively or positively. If Sig.’s are greater than 0.05, then mean of the pairs is considered the same (not to reject the null hypothesis); that is, LS or DVS has no effects on accuracy of classification.


## 4.2.2. Experimental Results

Figure1 shows average accuracies of each N of both DT(C5.0) and SVM classifiers of the two data sets. Obviously, DVS outperforms LS and accuracy of classifiers using feature selected by DVS keeps in a high level as N reduces from 2721 to 21 and from 656 to 56. Features selected by DVS are more effective than those selected by LS. At a very small subfeature space, classifiers using LS gets low accuracies. High accuracies can be achieved by using features selected by DVS. Figure 1 also shows that DVS performs as well as DF. Furthermore, Table 2 shows average accuracies (mean) and standard deviations (std) of testing sets of classifiers and results of two-tailed paired t test. For DBWorld data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. On the contrary, in Table 2(a), all the significances of the two classifiers using DVS are much higher than 0.05, showing that DVS significantly gets the same good classification accuracies as baseline. For CNAE data set, most of the significances (Sig.’s) of DT(C5.0) or SVM using LS in Table 2(a) are much lower than 0.05, which means accuracies of classifier using features selected by LS are significantly different form baseline. Classifiers using LS gets a very low accuracies when N = 156 or 56. Table 2(b) shows that DT(C5.0) using DVS significantly gets the same good accuracies as baseline. However, in Table 2(b), SVM using DVS does not significantly gets the same accuracies as baseline still keeps relatively high accuracies. Figure 1 shows low accuracies of classifier using features selected by LS. Feature selected by LS have negative effects on text classification, especially when N is very small. Figure 1 shows high accuracies of classifiers using features selected by DVS. Feature selected by DVS have positive effects on text classification. Figure 1 also shows that DVS performs better in DT(C5.0) than in SVM.Table 2
Accuracy of classifiers (unit for mean and std: %).
(a)
DBWorld data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
3721
91.30± 7.54
—
85.73± 6.73
—
91.30± 7.54
—
85.73± 6.73
—
2721
82.64± 8.17
.004
84.14± 7.06
.505
89.50± 6.59
.736
85.22± 6.10
.807
1721
70.27± 8.22
.000
80.73± 6.68
.023
89.61± 5.57
.779
87.02± 8.92
.291
721
58.53± 10.52
.000
63.97± 11.09
.000
91.74± 6.07
.433
84.15± 8.67
.129
521
56.49± 6.94
.000
62.66± 9.16
.000
89.07± 7.08
.185
85.10± 7.57
.584
321
53.58± 10.79
.000
57.75± 8.83
.000
92.16± 4.58
.454
83.55± 7.19
.192
121
52.44± 10.34
.000
51.92± 10.91
.000
92.74± 6.61
.179
90.56± 6.16
.098
21
58.03± 6.73
.000
57.38± 9.53
.000
88.26± 7.68
.332
91.40± 6.41
.722
(b)
CNAE data set
LS
DVS
N
DT(C5.0)
SVM
DT(C5.0)
SVM
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
Mean± std
Sig.
856
87.59± 2.25
—
92.93± 1.58
—
87.59± 2.25
—
92.93± 1.58
—
656
86.67± 2.21
.910
82.19± 4.52
.000
87.64± 1.77
.924
83.41± 2.02
.000
456
86.87± 2.62
.394
84.42± 2.26
.000
88.25± 1.86
.338
85.18± 2.73
.000
256
73.11± 2.77
.000
66.53± 2.09
.000
87.93± 2.31
.700
84.53± 2.12
.000
156
17.60± 1.48
.000
15.08± 2.48
.000
86.54± 2.46
.146
82.77± 2.33
.000
56
8.86± 0.930
.000
5.33± 0.95
.000
81.99± 1.90
.000
77.47± 2.33
.000Figure 1
Accuracy of classifiers of two UCI data set.
(a)
DBWorld data set
(b)
CNAE data setExperimental results in this paper show that DVS is much better than LS in feature selection of text classification, especially asN is reduced to a small number. Features selected by DVS have positive effects on text classification and features selected by LS make negative effects. DVS is able to overcomes negative effects caused by sparsity of DTM.


## 4.2.3. More Discussion about DVS and LS

As mentioned above, it is the key assumption of LS that documents with the same class are close. LS of a discriminative feature should be smaller. Consider formula (10) introduced in Section 2. LS uses Spq to measure similarity between Dp and Dq and (fpj-fqj)2 to measure similarity between fpj and fqj. For a discriminative feature, (fpj-fqj)2Spq tends to small, which indicates that each feature selected by LS contains many 0 values. Thus, LS is easily affected by 0 values in DTM and the sub-DTMs constructed by features selected by LS are also sparse. As N reduces, the sub-DTMs contain less and less information, resulting in pool performances of classifiers in text classification. On the contrary, the key idea of DVS is that text documents with different classes are not close. DVS tries to discover differences instead of similarities among documents and DCfj are used to evaluate how much a feature contributes to differences among text documents. DCfj pays much attention to nonzero value and is able to avoid negative effects caused by 0 values. Thus, DVS is capable of reducing the sparsity of DTM and select discriminative features capable of discovering differences among text documents. By discovering differences among text documents, DVS is much more efficient than LS. The sparsity of sub-DTMs of LS and DVS is shown in Table 3. Table 3 shows that as N reduces, the sparsity of sub-DTMs constructed by features selected by DVS also reduce but the sparsity of sub-DTMs constructed by features selected by LS still keep a high level.Table 3
The sparsity of sub-DTMs constructed by features selected by LS and DVS (unit: %).
DBWorld data set
CNAE data set
N
DVS
LS
N
DVS
LS
3721
95.01
856
99.20
2721
93.76
97.28
656
99.00
99.01
1721
91.04
98.00
456
98.60
98.81
721
83.16
98.10
256
97.73
98.68
521
79.47
98.03
156
96.60
99.78
321
73.01
98.40
56
92.80
99.90
121
61.23
98.44
21
49.70
98.44


## 5. Conclusion

This paper proposes an unsupervised feature selection method DVS for text classification. DVS aims to improve LS in feature selection of text classification. DVS uses feature distance distributions to discover importance of a feature for text classification and overcomes affects caused by the sparsity of DTM. DVS efficiently reduces the sparsity of DTM and features selected by DVS have positive effects on text classification. Experimental results on UCI DBWorld e-mails data set indicates that DVS performs much better than LS in feature selection of text classification.



---

*Source: 695720-2015-05-11.xml*