SA-A2-3

SCIS & ISIS 2008

Spam Filtering with Active Feature Identiﬁcation
Masayuki Okabe
Toyohashi University of Technology
Tenpaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

Seiji Yamada
National Institute of Infomatics
Chiyoda, Tokyo, Japanseiji@nii.ac.jp

Abstract—This paper proposes a spam ﬁltering method thatutilizes active learning and feature identiﬁcation. Identiﬁcation ofeffective features are very important procedure in spam ﬁltering
because spam mail includes so much meaningless words that areslightly different from each other. Those words bring down muchcalculation cost and performance reduction in ﬁltering process.
Thus identifying effective and ineffective features is promising
approach in spam ﬁltering. However traditional feature selection
methods calculate the score of features based on some amountof labeled training data. This assumption does not hold in thesituation of spam ﬁltering. Spam ﬁltering process starts withnon or few labeled data, and gradually increases labeled datausing user feedback. We propose a method to identify effective
features through this active learning process in spam ﬁltering
based on naive Bayes approach. Experimental results show that
our method outperforms traditional method with no feature
identiﬁcation.

I. I NTRODUCTION
There is a report that 96.5% of e-mails ﬂowing in theInternet are spams [1]. Spam ﬁltering is a disgusting task forthe most of users who use e-mail in daily life. They not only
annoys users but also make trafﬁc jams in the Internet. Mostof recent e-mail clients adopt spam ﬁltering function. However
it often fails to remove spams at it’s starting point. To ﬁlter
e-mails correctly, enough feedback have to be given from theclient’s user. In the early stage of the client’s usage, the user
have to notify mis-ﬁltered e-mails to the client every time new
e-mails arrives. Without enough training, we may miss e-mails
that have critical information for us.
The process of giving feedback to e-mail clients by labeling‘ham’ or ‘spam’ shown in Fig.1 is called active learning inthe ﬁled of machine learning [2]. This learning techniquetries to reduce the cost of data labeling, i.e. reducing thenumber of data to label by ﬁnding effective data to make ﬁlter.
This approach is to reduce the number of data that does notcontribute to make spam ﬁlters.
Several active learning techniques have been proposed so
far [3], [4], [5]. The most famous one is uncertainty sampling[6] that select a data for the candidate to label, which have themost uncertain value of a decision function. Decision function
is deﬁned by the ﬁltering method used in a spam ﬁlteringsystem, such as naive Bayes or support vector machines.
Uncertain sampling is a type of active learning technique thattries to reduce the version space. On the other hand, there is anactive learning technique that tries to reduce estimated errorthat is calculated by the distribution of estimated conditionalclass probability [7]. The results of the experiments in which== A-Z medications to choose from ==We give you FreeViagraPills (Free you 4-12 pills with any order)== ViagraPill ==== Cialix Pills ==== PenisGrowth Pack ==== SQMA ==== Phentrimine ==“spam !”== Levitr ==== Tramadol ==== FemaleViagra ==& 400 more meds to choose fromuser

Claim your Free 4-12 ViagraPills here with us

ham or spam?
Fig. 1.

Spam Filtering Processerror reduction approach is tested on naive Bayes show good
performance compared with uncertainty sampling.
The performance of ﬁltering is inﬂuenced by not only the
number of training data, but also the feature set used in
the ﬁltering process. There are several techniques to improve
the performance of ﬁltering. Feature selection is known to
be a good approach [8]. In classiﬁcation learning like ﬁltering, feature selection methods that uses class information
are promising. However a certain amount of labeled data isnecessary for those methods work effectively. This is a serious
problem when applying feature selection in the process ofactive learning. We propose a method to solve this problem.
Our method assumes the class of each unlabeled data using
conditional class probability estimated during active learning
process. This procedure can makes a pseudo set of labeled data
enough to calculate a feature’s score of importance. Once we
can get enough amount of (pseudo) labeled data, we haveanother problem that is how to select features to use formaking classiﬁers. We will propose a method to decide thenumber of necessary features by ﬁnding the point of the largest
gap between the sorted score list of features. These proposed
methods are used to identify a useful set of features to makegood classiﬁer.
In the following sections, we ﬁrst describe naive Bayesclassiﬁer and a sample error reduction approach of active
learning based on the classiﬁer in Section 2. Then we propose
a feature identiﬁcation method through the naive Bayes active
learning in Section 3. In Section 4, we show experimental
results in which our method and other two ones are comparedon the data set of TREC Spam Filtering track. We also discuss
about the results of some variational tests of our feature
identiﬁcation in Section 5. Finally we conclude in Section 6.

1218

II. S PAM F ILTERING WITH NAIVE BAYES C LASSIFIER
A. Naive Bayes Classiﬁer
Naive Bayes is a basic classiﬁcation technique that is simple
and easy to implement but shows relatively good performance[9]. Although there are other classiﬁers that show better performance such as Support Vector Machines, many spam ﬁlter
implementation is based on naive Bayes approach because of
its simplicity.
The classiﬁer calculates the probability for each mail tobelong to ‘ham’ or ‘spam’ based on the Bayes theorem.
Suppose we want to classify e-mails X into a class in C.
Here X = (x1 , x2 , . . . , xi ) and C = ‘ham′ , ‘spam′ .
The conditional probability P (C|X) that a data belongs to(X|C)
in which Bayesa class is written by P (C|X) = P (C)PP (X)theorem is applied.
Naive Bayes classiﬁer adopts a generative model that assumes data X are produced by the selection of a class c ∈ C
and x ∈ X given c. Moreover, it assumes the independenceof features of a data x. According to the generative approach,the conditional probability P (cj |xi , θ) that a data xi belongs
to a class cj is written as follows.
i
P (cj |θ)Πnk=1
P (wi,k |cj , θ)P (cj |xi , θ) = ∑|C|ni
j=1 P (cj |θ)Πk=1 P (wi,k |cj , θ)

Algorithm 1 Procedure for active learning on naive Bayes
1: P : a pool of unlabeled data.
2: E(xi , c) : expected loss when adding a data (xi , c)
3: E(xi ) : total expected loss when adding a data xi
4: for i = 1 to |P | do
5:
E(xi ) = 0
6:
for c ∈ ‘ham′ , ‘spam′ do
7:
E(xi ,c) = 0
8:
for k = 1 to |P | do9:next if i == k
10:E(x, c)+ = −P̂ ∗ (c|x) log P̂ ∗ (c|x)
11:
end for12:
E(xi )+ = P̂ (c|xi ) ∗ E(xi , c)
13:
end for
14: end for
15: return argmax E(xi )approach estimates the expected error E using a loss function
L that calculates between true distribution of the class probability conditioned on x P (C|X) and estimated one using aloss function.

(1)

∫
E=

Here wi,k is the kth word that appears in xi , θ = (θc , θw|c )is a set parameters that includes the class prior and theprobability of generating word w class c. Using maximum aposteriori estimation, each parameter is calculated as follows.
∑|X|
1 + i=1 δ(xi , cj )θ̂cj =(2)|C| + |X|∑|X|
1 + i=1 N (wk , xi )δ(xi , cj )(3)θ̂wk |cj =∑|V | ∑|X|
|V | + k=1 i=1 N (wk , xi )δ(xi , cj )where V is all kinds of words that are used to estimate parameters. N (wk , xi ) is word frequency of a word wk appears
in xi . δ(xi , cj ) is a function that returns 1 if the class of xi
equals to cj and 0 otherwise.
The above estimation includes smoothing parameters thatremoves zero counts when there is no training data. This
simple smoothing method is called the Laplace smoothing.
B. Naive Bayes with Active Learning
Until now, we have explained classiﬁcation technique withan assumption that we have enough training data (i.e. enoughmails categorized either ‘ham’ or ‘spam’). However suchassumption is unrealistic. When we start to use a mail client,
there is no labeled mails. We notify spams to the client one
by one as described in the introduction of this paper.
This process is called active learning where the objective isto reduce the cost of labeling procedure by selecting a data thatis expected to improve the classiﬁcation performance most.
Among several techniques of active learning as described in
the section of introduction, we adopt a sampling techniqueof error reduction approach proposed by Roy[Roy01]. This

L(P (c|x), P̂ (c|x))P (x)(4)

x

As a loss function, we use the log loss function describe
below.
L=∑−P (c|x) log P̂ (c|x)

(5)

c∈C

Since true distribution is unknown, we replace P (c|x) toP̂ (c|x). As a result, an expected loss when adding a data is
calculated by the following formula.
E=

1 ∑∑−P̂ ∗ (c|x) log P̂ ∗ (c|x)
|P |

(6)

x∈P c∈C

where P̂ ∗ (c|x) is conditional class probability when adding adata (x, c) that is a data selected by each active learning process. Algorithm 1 shows precise algorithm of active learning.
This algorithm repeats to consider each unlabeled data in thepool as a feedback candidate. For each data, it considers eachpossible label c for x, and add each pair (x, c) to training data
set to make temporary new training data by which a temporal
new classiﬁer is created. By using this temporal classiﬁer,
resulting expected loss are estimated. Each estimated losses
E(xi , c) are aggregated by multiplying its present conditionalclass probability P (c|xi ).
Because the true distribution is unknown, the value isactually calculated by using estimated distribution for true one.
According to this replacement, loss function actually calculates
the sharpness of class distribution, large difference is more
preferable.

1219

score of IG

III. F EATURE I DENTIFICATION THROUGH ACTIVE
L EARNING

the largest gap point

A. Feature selection by Information Gain
Feature selection is a technique of improving classiﬁcation performance by removing unnecessary features. Although
there are several measures to select effective features in textclassiﬁcation, we use information gain that is one of mosteffective technique. Information gain (IG) is calculated by thefollowing formula.
IG(w)

= −

∑

features to use

rank of feature

P (c) log P (c)c∈C+P (w)∑(7)
Fig. 2.

Illustration of the largest gap point

P (c|w) log P (c|w)

c∈C+P (w̄)∑P (c|w̄) log P (c|w̄)c∈C

Where P (c) is the probability that data with class c isselected among all training data, P (c|w) is the probability
that data with class c is selected among all data in which aword w appears, and P (c|w̄) is the probability that data withclass c is selected among all data in which a word w does notappear.
When using IG in active learning, there are mainly two
problems. The ﬁrst one is the lack of training data. Since there
are few training data in the early stage of active learning, theconﬁdence of the value of IG is low. The second is how todecide the number of features to use. Although this problem
is not limited to the case of active learning, it is more serious
because the conﬁdence of IG is low. We explain the solutionof these problems.
B. Identiﬁcation of a feature set though active learning process
We summarize again each problem when applying feature
selection in active learning and show the solution for eachproblem.
The ﬁrst problem is how to prepare enough labeled data.
The normal feature selection technique needs some amountof labeled training data. However there are small number oflabeled data in the early stage of active learning. We propose
a solution for the problem by assuming the class of unlabeleddata that have some certain conﬁdence of their class labels.
we assume the class label of unlabeled data by the probability
P (c|x) with large difference between two classes, i.e. ‘ham’and ‘spam’ class. Moreover even if there are enough unlabeleddata with high probability of conditional class conﬁdence, it
is difﬁcult to discriminate the important features if the numberof data in each class are biased to one class. According to theabove consideration, we adopt two threshold to prepare thesource data for selecting important features to classify.
1) Tconf : threshold for the conditional probability of classconﬁdence of each unlabeled data.
2) Tbal : threshold for the balance of the number of training
data in classes.

Both thresholds are lower limits that must be satisﬁed. Tconf
controls the number of source data for feature selection. Tbal
is a parameter to prevent from making an unbalanced source
data set where data with only one class occupies the set. Thisis the solution for the ﬁrst problem.
The second problem is how to deﬁne the number of usefulfeatures. According to the scoring function (IG), we candiscriminate the usefulness of each feature. However we also
have to decide the number of feature to use in classiﬁcation.
To solve this problem, we propose to deﬁne the number offeatures by ﬁnding the largest gap point. Gap points can befound by ﬁrstly sorting the score of IG(w)s, and secondly
check the difference of the score between rank k and rank
k + 1. If the largest gap point is K, we select features until
Kth feature in the sorted list of IG as shown in Fig.4. Since
the probabilities used in IG are calculated based on the numberof data in which each word appears, a group of words tend tohave the same value like shown as horizontal lines in Fig.4.
Thus this procedure selects such groups of words by ﬁnding
the largest gap.
Algorithm 2 summarizes the procedure of active learning
accompanied with feature identiﬁcation.

Algorithm 2 Procedure for active learning with feature identiﬁcation
1: V : vocabulary set
2: wi : ith word in V
3: Conduct algorithm1
4: Calculate conditional probability P (c|x) for each x
5: Select x that has the probability more than Tconf
6: Make a pseudo training data set Dpse that consist of true
training data and data selected above procedure.
7: for i = 1 to |V | do
8:
calculate IG(wi ) using Dpse
9: end for
10: Sort V in descending order
11: Find the largest gap point and create new vocabulary set
V∗
12: return V ∗1220

(b) 501-1000
1

0.8

0.8

0.6

0.6

Accuracy

Accuracy(a) 1-500
10.4

FT_SELALL
UNCERT

0.2

0.4

FT_SELALL
UNCERT

0.2

0

0
0

10

20

30
40
50
60
70
Number of labeled data

80

90

100

0

10

20

1

0.8

0.8

0.6

0.6

0.4

FT_SELALL
UNCERT

0.2

80

90

100

90

100

(d) 1501-2000

1

Accuracy

Accuracy(c) 1001-1500

30
40
50
60
70
Number of labeled data

0.4

FT_SELALL
UNCERT

0.2

0

0
0

10

20

30
40
50
60
70
Number of labeled data

80

90

100

Fig. 3.

0

10

20

30
40
50
60
70
Number of labeled data

80

Results of experiments

IV. E XPERIMENTS
This section shows the experiments of spam ﬁltering to compare our proposed method with two others. In the experiments,
we used an e-mail collection that is used in the TREC Spam
Filtering Track [10]. This data set contains about 90,000 emails that are sorted by date. Since this data is too large
to simulate active learning, we select 4 data sets. They arelabeled (a) 1-500, (b) 501-100, (c) 1001-1500, (d) 1501-2000,
respectively. Each data set consists of 500 data in which ﬁrst
100 data are used for the pool of unlabeled training, the rest
400 are used for test. The process of active learning starts fromno labeled training data, and then add labeled data one by one
until total 100 data are added. E-mails are preprocessed byremoving only symbols. Each data are represented as a bag ofwords.
We compared our method with other two ones.

The ﬁrst one is naive Bayes based active learning with sample
error reduction approach that is the basis of our proposed
method. Our method merge feature selection procedure to thismethod. This base method uses all features. The second one
is also naive Bayes based active learning with uncertainty
sampling. This technique selects a data that is the most difﬁcult
to classify, namely the difference between class probability.
Fig.3 shows the results on 4 data sets. On all data sets,
our method shows better or comparative performance to othertwo methods. We summarize the characteristics of each result
below.

1) FT SEL : This is our proposed method. Parameters
Tconf and Tbal are set to 0.9 and 0.1, respectively.
2) ALL : naive Bayes based active learning with sample
error reduction
3) UNCERT : naive Bayes based active learning withuncertainty sampling

1221

Data 1-500: FT SEL and ALL are comparative during theearly stage (until about 40 data are added). In the following stage, FT SEL mostly outperforms ALL. UNCERTshows bad performance in this data set.
• Data 501-1000: UNCERT slightly outperforms FT SEL
until about 20 data are added. However from the point,
FT SEL gets better, and UNCERT decreasing to the same
performance of ALL.
• Data 1001-1500: In this data set, FT SEL and ALL show
almost the same performance. UNCERT shows worse
performance than other two methods. Its performance•

(b) 501-1000
1

0.8

0.8

0.6

0.6

Accuracy

Accuracy(a) 1-500
1

0.4

1st
2nd
3rd
4th

0.2

0
0

10

20

30
40
50
60
70
Number of labeled data

80

0.4

1st
2nd
3rd
4th

0.2

0
90

100

0

10

20

1

0.8

0.8

0.6

0.6

0.4

1st
2nd
3rd
4th

0.2

0
0

10

20

30
40
50
60
70
Number of labeled data

90

100

80

90

100

0.4

1st
2nd
3rd
4th

0.2

0
90

Fig. 4.

•80(d) 1501-2000

1

Accuracy

Accuracy(c) 1001-1500

30
40
50
60
70
Number of labeled data

100

0

10

20

30
40
50
60
70
Number of labeled data

80

Results of various gap selections

gets better around 50 data are added.
Data 1501-2000: Three methods reach the best performance until less than 10 data are added in this data set.
However only FT SEL keeps the best performance until
around 70 data are added.
V. D ISCUSSION

Our method ﬁxes the threshold to the largest gap point forfeature selection. This strategy seems to be an adhoc heuristic.
Thus we check the adhocness of the strategy by changing
the threshold to select features. We test the 2nd, 3rd and 4thlargest gap points in our method. Fig.4 shows the results. On
every data set, the largest gap point mostly performs the best.
In data set (a), feature sets without the largest gap selection
show almost the same performance. This results indicatesthat our feature selection procedure could remove unnecessary
features. It is interesting that the result of the 3rd largest gap
is comparable with the largest one in a data set (b). Since thefeature set by 2nd largest selection shows worse performance,
there are very important features between 2nd and 3rd largest
gap points. In data set (c), the performance of feature sets
without by the largest gap is terribly worse than the largest
one. Feature selection may not be necessary in this data set.

Finally the feature set by the 3rd largest gap shows worse
performance than other ones. It is interesting that the feature
set by the 4th largest gap outperforms others. Larger featuresets may work well in the stage i which there are a lot of datawith true label. According to these results, feature selection
by the largest gap works relatively well.
VI. C ONCLUSIONSIn this paper we propose a feature identiﬁcation approachwith active learning. Our approach iteratively apply information gain based feature selection method through the processof active learning. Since our task is focused on spam ﬁltering,
we use naive Bayes as basic classiﬁer in our approach.
Data selection is conducted by the sample error reduction
approach that estimates the errors of unlabeled training databy temporally updated conditional class probabilities. Then
we pointed out the problem when applying the information
gain based feature selection method through active learning
process. For the ﬁrst problem that the lack of labeled training
data, our solution is to attach pseudo labels estimated by the
temporal conditional class probabilities. The solution for thesecond problem of how to deﬁne the number of features touse is to set a threshold by ﬁnding the largest gap among1222

information gain scores. Experimental results shows that our
proposed method shows good performance compared with anapproach without feature selection and a approach based on
uncertainty sampling. According to additional experiments,
feature selection by the largest gap point work relatively works
well irrespectively to data sets.
R EFERENCES[1] Sophos’s report: http://www.sophos.com/pressofﬁce/news/articles/2008/07/
dirtydozjul08.html, 2008.
[2] D. Sculley, Online Active Learning Methods for Fast Label-Efﬁcient
Spam Filtering, In Fourth Conference on Email and Anti-Spam, 2007.
[3] S. Tong, D. Koller, Support vector machine active learning with applications to text classiﬁcation. In Proceedings of the Seventeenth International
Conference on Machine Learning , 2001.
[4] M. Lindenbaum, S. Markovitch, D. Rusakov, Selective sampling fornearest neighbor classiﬁers, In Proceedings of the Sixteenth National
Conference on Artiﬁcial Intelligence, pp.366-371, 1999.
[5] A. McCallum, K. Nigam, Employing EM and pool-based active learning
for text classiﬁcation, In Proceegings of the Fifteenth International
Conference on Machine Learning, pp. 359-367, 1998.
[6] D. Lewis, W. Gale, A sequential algorithm for training text classiﬁers,
In Proceedings of the International ACM-SIGIR Conference on Researchand Development in Information Retrieval, pp. 3-12, 1994.
[7] N. Roy and A. McCallum, Toward Optimal Active Learning throughSampling Estimation of Error Reduction, In Proceedings of the EighteenthInternational Conference on Machine Learning, pp.441-448, 2001.
[8] Y. Yang and J. O. Pederson, Feature selection in statistical learning of text
categorization, In Proceedings of the Fourteenth International Conference
on Machine Learning, pp.412-420, 1997.
[9] A. McCallum, K. Nigam, A comparisonof event models for naive Bayes
text classiﬁcation, In Proceedings of AAAI-98 Workshop on Learning for
Text Categorization, 1998.
[10] G. Cormack and T. Lynam, TREC 2005 Spam Track Overview, In
Proceedings of the Fourteenth Text Retrieval Conference, 2005.

1223