E-mail Spam Filtering

3Moving forward with these basic methods, I shall beimplementing a little more complex algorithms to detect spame-mails.filtering, I used the Bayes theorem. The Bayes theorem interms of spam and ham e-mails can be expressed as:Pr(𝑆 𝑊) Pr(𝑊 𝑆) Pr(𝑆) / Pr(𝑊 𝑠) Pr(𝑆) Pr(𝑊 𝐻) Pr(𝐻)III. IMPLEMENTATION OF THE PROJECTTHE project consists of 3 parts. They are: Data gathering and preprocessing Writing and implementing python programs to run thefour algorithms mentioned above. Evaluation and analysis of results.The first phase consisted of gathering possible spam e-mailcorpuses to work the algorithms on. While there were simpletext datasets of e-mails, I chose the UCI SpamBase due to thehigh volume of data that it provides. The SpamBase consists of4601 instances. Each instance has 57 attributes. Theseattributes are further divided into continuous and noncontinuous attributes. The main attributes are the 48continuous attributes that are the word frequencies of wordsfound in the instances. Other attributes are the total run length,longest run length etc. The general description of the dataset isas follows.Multivariate4601DatasetNumber ofcharacteristicsinstancesInteger, Real Number on MissingYesAssociatedtaskvalues?Table 1: Description of the Spam Base Dataset of UCIMachine LearningWhere Pr(S W) is the probability that a message is spamknowing the presence of a given word in it.Pr(W S) is the probability that a certain word appear in spammessagesPr(S) is the overall probability of a message being a spammessage.Pr(W H) is the probability that a certain word appears in hammessages.Pr(H) is the overall probability that a message is a hammessage[12].As described in the implementation section, we havecontinuous attributes of categorical data. For classifying datawith such attributes, I have used Gaussian Bayesian Filters. Itis assumed that the continuous values are distributed along theGaussian curve. The graph of a Gaussian is a symmetric bellshaped curve. To deal with such continuous attributes, let ussay, training data x, We first segment the data by class. Thenwe have to compute the mean and variance of each class.The mean is denoted by µ, standard deviation is denoted by σand the variance is denoted by σ2.In the following sections, I will describe all the methods thatI have used for classificationIV. NAÏVE BAYES ALGORITHMTHE Bayesian Classification model, proposed by ThomasBayes (1702 - 1761), is based on statistical andprobabilistic method of learning. It is a type of supervisedlearning algorithm. Supervised learning is defined as the taskof inferring a function from supervised training data[3]. Asupervised training algorithm analyzes the training data andcomes up with the classifier function and the regressionfunction. We are going to deal with classification here. Theinferred classification function performs the task of predictingthe correct output value for a given input value. The Bayesianclassifier assumes a probabilistic underlying model anddetermines probabilities of the outcomes. It can solvediagnostic as well as predictive problems. Naïve Bayes isbased on conditional probabilities. Conditional probability isthe probability of the occurrence of an event, given thatanother event has occurred.For implementing Bayesian Classification for e-mail spamFigure 2: Plot of different values of mean, standard deviation and varianceThe figure above, displays 4 Gaussian curves with means 0, 0,0 and -2 respectively. Their standard deviations and varianceare displayed in the figure.µ is defined as the central tendency for the probabilitydistribution. ‘σ2’ is a measure of how far the set of data pointsare spread out in the distribution. ‘σ’ is the square root of the‘σ2’ which describes how close the data points are to the mean.

4Then, the probability distribution of some value given aclass,, can be computed by pluggingis very high. I am going to demonstrate this by implementing iton the 4091 instances that I have in the dataset.into theequation for a Normal distribution parameterized byand[12]. That is,Since we have to work with the same dataset as a test set and atraining set, I first divide my dataset into train and test sets. Mytrain/test ratio is 0.67.I find the probabilities of the test set based on the training set.This gives me all the predictions for the testing data. Now thatI have the predicted classification of an instance as spam orham, and I also have their original classification, I can checkhow accurate my classification is. To calculate the accuracy, Icheck if the result of prediction is the same as the originaldataset. If the values match, the classification is correct. Icalculated the accuracy rate by dividing this by the totalnumber of test data sets.The results of my accuracies are as follows:Time taken to run the algorithm on the SpamBase is “1.8seconds”Figure 3: Plot depicting 5 nearest neighbors of xThe above figure depicts the general idea of the k NearestNeighbors algorithms. There are two classes, blue and black.We have a data point x that needs to be classified. Consideringthat the value of k is taken as 5, we first find the distance of xfrom all of the given points. All the distances are then sorted inascending order and the first 5 distances are considered. Weare thus considering the 5 points that are nearest to point x. Wethen check the maximum frequency of points within theneighborhood of x. As we can see, there are 3 black points and2 blue points. So the maximum frequency is 3 and it belongs toblack. X is therefore classified as a black point.The observed accuracy rate is 82.62%.V. K- NEAREST NEIGHBORSTHE k Nearest Neighbors algorithm, also known as kNN, isa non-parametric method used for pattern classification. Itis an instance-based learning algorithm. The function issimply approximated locally. All computation is deferred untilclassification. The neighbors for the data points are taken as aset of objects whose values are known. This is basically thetraining phase of the algorithm. In the classification phase ofthe algorithm, for each point in the testing set, we consider kneighbors where k is predefined by the programmer. We thenfind the most frequent class values in the training set. We canfind the neighbors using many methods such as linear search,space partitioning, locality sensitive hashing etc[7].To implement the kNN algorithm, my program divides theSpamBase into a testing dataset and a training dataset. There isno preprocessing on the training dataset. We directly calculatethe k nearest neighbors for each data point in the testingdataset. Then among these k values, I calculate whether the email is mostly classified as ham or spam. If majority of the kneighbors are classified as spam, the data point or the instanceis classified as spam. Otherwise it is classified as ham. Thenwe move on to calculate the accuracy by checking the value ofthe ham/spam to the original class value.Dependency of the value of k on the accuracy of thealgorithmFor implementing the algorithm, I have used the Euclideandistance between the attributes of the instances. The squaredEuclidean distance between the point p (p1, p2, ., pn) andthe point q (q1, q2, ., qn) is the sum of the squares of thedifferences between the components: Dist2(p,q) Σi (pi – qi)2.The Euclidean distance is then the square root ofDist2(p,q)[10].While Euclidean distance is a good measure for finding all theneighbors of a given instance, it has a major drawback that itcannot work for very large data sets as the computational timeFIGURE 4: PLOT SHOWING THE ACCURACY OF KNN FORDIFFERENT VALUES OF K

5During implementation, I used 5 values of k to see how theaccuracy differed on changing the values. The 5 values of kare {1,3,4,5,9,13,23}. The accuracies of the values % }two classes seems to be the best positioning of the decisionboundary.Based on the observations above, I infer that the value of kdoes change the accuracy of the algorithm to an extent.However, the change in accuracy also depends on the datasetdistribution. If the dataset is evenly distributed or if it is denseor sparse, can change the effect of k on the efficiency of thealgorithm.Dependency of the value of k on the time taken for thealgorithm to classify dataConsider the figure above, the line H1 is a bad choice for adecision boundary because it does not separate the blackpoints and the white points into two different classes.Therefore, H1 is eliminated as an option. Now consider theline H2. H2 is a valid decision boundary, but not a good one.The reason being, the marginThe value of k is directly proportional to the time taken by thealgorithm. On running the algorithm with the same values of k,i.e. {1,3,4,5,9,13,23} the execution times, in terms of secondswere observed to 3,321.07}As we can see, the time taken continually increases with thevalue of k. This can be linked to the fact that it takes more timeto find more nearest neighbors.VI. SUPPORT VECTOR MACHINESSMachines, also called as SVM aresupervised learning models that analyze data and recognizepatterns. If we have a set of training data points, eachmarked with a class value such as [0,1] , [1,-1] ,[TRUE,FALSE] , on being fed with new data points, a supportvector machine can categorize them into one of the twoclasses. Therefore, a support vector machine is a nonprobabilistic binary linear classifier. How a support vectormachine works is, it produces a hyper plane on a highdimensional space or a set of hyper planes on an infinitedimension space. Classification of data points is done aroundthese hyper planes. For two classes with linearly separabledata, there may be many such separators that can separate thetwo classes of data. Intuitively, it seems like a decisionboundary that is drawn in the middle of the void between theWhile some learning methods such as the perceptron algorithmfind just any linear separator, others, like Naive Bayes, searchfor the best linear separator according to some criterion. TheSVM defines the criterion to be looking for a decision surfacethat is maximally far away from data points in either of the twolinearly separable classes. The margin is this distance which isthe distance between the nearest point to either of the classesand the hyper plane that linearly separates them. This methodof construction necessarily means that the decision function foran SVM is fully specified by a (usually small) subset of thedata which defines the position of the separator[14]. Thepoints, that lie on the hyper plane are called as support vectors.Other data points play no part in determining the decisionsurface that is chosen[6].UPPORT VectorMargin maximization in support vector machinesThe figure given below explains and depicts the term supportvectors and margin.

6To find an optimal hyper plane, the main objective of thealgorithm is to maximize the margin. The margin is thedistance between points belonging to either of the classes withthe hyper plane. By support vectors, we mean the vectors thatdefine the hyper plane. To maximize the margin, the followingsteps are followed.The thing about SVM is that if there is linear separability, thenthe value of global minimum is a unique value.However, it might be very difficult, in some cases to come upwith data points that are purely linearly separable. So weintroduce the concept of slack variables. Slack variables maybe defines as the variables that may break the rule of linearseparability, but they will be penalized.As we can see, we have to maximize the value highlighted inthe red box. Here b is the bias. The dot product of the marginwith the vector x is -1 for the support vectors marked with thecolor green. The same value is 1 for the support vectorsmarked with red color. This gives rise to two classes that areClass 1 and Class 2. Class 1 are all the red points and theirproperty is that the value of the dot product of the two vectorsw and x with an added bias is greater than or equal to 1. On theother hand, we have the dot product of the width vector withthe vector x added with the biases, if the value is less than -1,the data point belongs to Class 2.As seen above, we introduce the slack variables denoted by ϛ.So now the value of the equations mentioned above changesby the effect of the slack variables.We can define width as unit width multiplied by the distancei.e (x2-x1). This is further described in the next figureWe define the width in terms of the unit vector w and use theequations for the support vector to derive that the width can bewritten as 2/ w .This would be the same as minimizing the inverse. That is.The above descriptions have been about hyper planes that arelinear. There may, however be cases such that a non linearhyper plane may be more efficient in separating data pointsthan a linear hyper plane. The SVM handles these situationwith a trick known as the ‘kernel trick’[7]. The kernel trickmay be defined as the use of a function that maps data into adifferent space where the hyper plane cannot separate the data.This function is called as the kernel function. The kernel tricktherefore is using the kernel function to transform the data intoa higher dimensional space so as to separate them with a hyperplane of a higher dimension. So the data is mapped into a newspace and the dot product is then performed in the new space.

7The following table depicts the difference between theexecution time of SVC and NuSVC with the Spam Basedataset.Execution time for SVC15.467435214.984507217.3467981Execution time for NuSVC12.123678111.235609311.2546890Therefore on an average, the function svm.NuSVC() seems tobe 20% faster than svm.SVC().This figure defines how the data points are mapped in a newspace and how they can be linearly separated in the new space.To implement support vector machines on my dataset, I usetwo sets of my Spam Base. They’re the training set and thetesting set. The training set consists of all 57 columns of thedataset including the class column. The testing set includes allthe columns except the class. I am using the inbuilt Pythonfunctions for SVM that is the SVC function and the NuSVCfunction. These are used by importing the SKLEARN packagein Python.I store the results in two class files. I am also storing theprobabilities in a file. The results look as follows.The first column shows the probability of the data point beinga ham message and the second column gives a probability ofthe dataset being a spam message. The result, that is actuallystored in the result.txt file, but is being here for representationpurposes, considers the maximum of the two probabilities andassigns ham or spam class to the data point at hand. The result‘1.0’ indicates a spam message and ‘0.0’ indicates a spammessage.I have observed a running time of 12-15 seconds on runningthis algorithm on my datasets.I have tested two versions of the algoritms by using twodifferent functions, namely svm.SVC() and svm.NuSVC().The are basically the same performance with different functionparameters. The range of SVC is between 0 and infinity whilethe range of NuSVC is always between [0,1]. I observed thatthe function NuSVC works faster than the function SVC.VII. CONCLUSIONWE have seen the running times and accuracy rates of allthe three algorithms. I am tabulating all of the results sothat I can present the conclusion to this project.Algorithm/ApproachNaïve Bayes (Firstimplementation)Naïve Bayes(Secondimplementation)K Nearest Neighbors(k 1)K Nearest Neighbors(k 3)K Nearest Neighbors(k 4)K Nearest Neighbors(k 5)K Nearest Neighbors(k 9)K Nearest Neighbors(k 13)K Nearest Neighbors(k 23)SVM (FirstImplementation usingsvm.SVC())SVM (secondimplementation usingsvm.SVC())SVM(Firstimplementation usingsvm.NuSVC())SVM(Secondimplementation usingsvm.NuSVC())Accuracy Rate82.62%Execution Time1.8 seconds84.58%1.4 6%11.2356093The best results would be the algorithm where the accuracy aswell as the execution time are optimized. As we can see above,the Naïve Bayes algorithm gives the least execution time. Italso surpasses the other two algorithms in terms of theaccuracy. Support Vector machines also have high accuraciesand low run times. The K Nearest Neighbors algorithm gives

8the worst performance in terms of both the accuracy and therun time. The run time of KNN is approximately 255 timesthat of Naïve Bayes and 197 times that of Support VectorMachines. Therefore,Naïve Bayes classifier is the best algorithm among NaïveBayes, SVM and K Nearest Neighbors for classifying emails as spam while taking into consideration, theiraccuracies and execution times.While there is a stark difference in the performance of thethree algorithms, these could vary with different data sets. Theratio of ham/spam messages, the number of data points in thetraining set and the number of data points in the testing set canhave an effect on the performance of the 0][11][12][13][14]Vangelis Metsis, Spam Filtering with Naive Bayes -- Which NaiveBayes?, Vangelis Metsis Telecommunications (2006)Freund, Y.: Boosting a weak learning algorithm by majority.Information and Computation 121(2), 256–285 (1995) .Bartlett, P.L., Traskin, M., AdaBoost is consistent. Journal of MachineLearning Research 8, 2347–2368 (2007)Drucker, H., Wu, D., Vapnik, V.N, Support Vector Machines for SpamCategorization. IEEE Transactions on Neural Networks 10(5), 1048–1054 (September 1999)Hinneburg, C.C.A.A., Keim, D.A.: What is the nearest neighbor in highdimensional spaces? In: Proc. of the International Conference onDatabase Theory (ICDT), pp. 506–515. Morgan Kaufmann, Cairo,Egypt (September 2000)Bickel, P.J., Ritov, Y., Zakai, A., Some theory for generalized boostingalgorithms. Journal of Machine Learning Research 7, 705–732 (2006)Ratsch, G., Onoda, T., M uller, K.R.: Soft margins for AdaBoost.Machine Learning 42(3), 287–320 (2001)Ting Fan Wu, Chih-Jen Lin, Ruby C. Weng, Probability estimates ofmulticlass classification by pairwise coupling, Journal of MachineLearning research 5, 975-1005 (2004)La Bouli, Yu Shiven, Lu Qin , An improved k Nearest Neighborsalgorithm for text Categorization (2002)Manning C. D. and Schutze H., 1999. Foundations of StatisticalNatural Language Processing [M]. Cambridge: MIT .paulgraham.com/spam.htmlwww.nlp.stanford.edu

Abstract—E-mail spam filtering is a very widely discussed and studied topic in the field of pattern classification. E-mails can be filtered as spam or non-spam based on many features such as the frequency or occurrence of a few words in the e-mail, the length of the e-mail or the domain from which it is being sent. Based on