//Spam Detector //SoloLearn Contest /*concepts applied Naive Bayes classification Bayes'' theorem: P(S|W)=(P(W|S)*P(S))/(P(W|S)*P(S)+P(W|H)*P(H)) Bag of words model Paul Graham's formula for combining individual probabilities Laplace smoothing *******************************************/ /*preprocessor directives*/ #include //used in input output stream #include //used to declare strings #include //used in count() function #include //used in log() function #include //used in string streams #include //used to declare vectors #include //used to declare map #include //for map iterator #include //for std::accumulate #include //for passing pairs to maps /********************************************/ using namespace std; /*global declarations*/ string *input = new string; //contains input from user string *spam=new string; //contains training set for spam emails string *ham= new string; //contains training set for non-spam emails string *grammar=new string; //contains common spelling mistakes vector arrinput; //holds each word from input variable vector arrspam; //holds each word from spam variable vector arrham; //holds each word from ham variable map combined; //has each word from input, and its spamliness. Takes no duplicates, since each word should be unique int spamcount; //number of words in spam training set int hamcount; //number of words in non-spam training set double spamicity; //the probability that the input email is spam /******************************************/ //functions----------------------------------------------------------- /*Breakdown function converts a string to a vector of words. It takes two arguments, extracts each word from str1, the first parameter, and appends it to vec, the second parameter*/ void breakdown(string &str1, vector & vec) { for (int i = 0; i < str1.size(); i++){ if ((int)(str1[i])>64&&(int)(str1[i])<91) str1[i]=tolower(str1[i]); //converts all uppercase letters to lowercase using their ASCII keys. Used in case insensitive string comparison } istringstream i(str1); while (i) { //extracts each word separated by spaces from string string x; i >> x; if ((x.back()=='.')||(x.back()=='!')||(x.back()=='?')||(x.back()==',')) //removes all periods, commas, exclamation and question marks from end of each word x.erase( x.end()-1 ); vec.push_back(x); //appends each word to vector } vec.pop_back(); //removes last element of vector, which is an empty string } /*******************************************/ //methods of spam detection //method #1, machine learning: /*compute function computes and returns the spamliness of each word in the email. It takes the word queried as an argument*/ double compute(string &str){ //we assume each word occurs at least once in spam and ham training set, to cater for words the program has never encountered. This is used to establish the corrected probability by laplace smoothing int frspam=count(arrspam.begin(), arrspam.end(), str)+1; //frequency of word in spam training set int frham=count(arrham.begin(), arrham.end(), str)+1; //frequency of word in ham training set double prspam=double(frspam)/double(spamcount); //probability that spam emails have the word, ie pr(W|S) double prham=double(frham)/double(hamcount); //probability that ham emails have the word,ie pr(W|H) double spamliness=prspam/(prspam+prham); //the spamliness of the word, ie pr(S|W). Check out the Wikipedia article "naive bayes spam filtering" for the formula double returned= log(1-spamliness) - log(spamliness); //values of pr(S|W) should be combined by multiplication. However, we add their logarithms instead, to avoid floating point underflow. Check out the Wikipedia article "naive bayes spam filtering" for the formula. return returned; } /************************************************/ /*loop() function iterates through ''arrinput'', computing each word''s corresponding spamliness, then adds each word along with its spamliness to the ''combined'' map. The map takes no duplicates*/ void loop(){ for (string i : arrinput) { //loops through vector combined.insert(make_pair(i , compute(i))); //writes each word and its spamliness returned by compute() in map } //free memory in heap no longer needed by emptying vectors arrspam.clear(); arrham.clear(); } /************************************************/ /*complete function finds the spamicity of the input email by adding natural logs of pr(S|W) in the map*/ void complete(){ double sum_p; //holds sum of 'combined' map's second element with each iteration through ''combined'' map::iterator it = combined.begin(); while(it != combined.end()){ //loops through the map with an iterator sum_p+=(it->second); //adds the second element to sum_p it++; } spamicity=1/(1+exp(sum_p)); //finds the spamicity of the input email using euler's number and the sum of natural logs. Check out the Wikipedia article "naive bayes spam filtering" for the formula. } /************************************************/ //method #2: identify terms requesting for personal information. Handled by spam training set in machine learning //method #3: looking up links /*findlink function looks up links in input email*/ void findlink(){ if (((*input).find("http://") != string::npos) || ((*input).find("https://") != string::npos) || ((*input).find("www.") != string::npos)) spamicity+=0.2; //if link exists, increment spamicity by 0.2 } /**********************************************/ //method #4, identifying strange characters /*findchar() function identifies all characters not in the latin alphabet or standard keyboard*/ void findchar(){ int num=0; for(char c : *input){ if (((int)c < 32) || ((int)c > 127)){ //find char with ascii code out of standard range num+=1; } } if (num>=3) spamicity+=0.1; //increase spamicity by 0.1 if 3 or more chars are found } /************************************************/ //method #5, check for common spelling mistakes //spellcheck function identifies words in input that exist in the string containing spelling errors void spellcheck(){ for (string i : arrinput) { //loop through input vector if ((*grammar).find(' '+i+' ') != string::npos) { //check if word exists in spelling mistakes. Note that we add spaces to the ends to look up the string as a word, but not part of a word. spamicity+=0.05; //increment spamicity by 0,05 break; //terminate loop } } } /*************************************************/ /*is_spam function prints true or false using the spamicity value*/ void is_spam(){ cout<<((spamicity>0.5)?"true":"false"); } /*************************************************/ /*init function initializes variables*/ void init(){ //takes input from user by reading from input stream till there's nothing left. Makes it possible to enter multiline input in the code playground's console. string tmp; while( cin >> tmp ) *input += ' '+tmp; //converts input to vector of words using breakdown() function breakdown(*input, arrinput); //the array below has inappropriate words in encrypted form. They exist in spam training set string str="abcdefghijklmnopqrstuvwxyz"; stringstream hide[15]; hide[0]< It has come to our attention that you may be entitled to an undisclosed amount of unclaimed funds. If so, these funds are currently reserved in your name and waiting or you to claim. Apply. Get back your lost cash. Unsubscribe Please enter your name at the unclaimed money search engine located at our site. Click Here Notification Date: 10/25/02 to 11/25/02 Unclaimed Funds Department Found Money.com We take your privacy very seriously and it is our policy never to send unwanted email messages. This message has been sent to you because you signed up with us. To unsubscribe click here or go to www.spam.com Terms and conditions apply. Subject: Win Big! How to win in the Foreign Yen market Date: Wed, 13 Nov 2002 18:53:41 PST From: maryalice nolan WOW! $10,000 INTO $25,000? Get Free Info on how a $10,000 investment could return $25,000 in less than 30 days. Learn about trading in The Forex currency markets. Get our reports, charts and strategies on the U.S. Dollar vs. The Euro see how $10,000. could leverage 1 million Euro! Cheap monthly fees Past performance not indicative of future results. Enter credit card and password information and start earning money. Unlimited cash. Apply now. http://www.wesellforyou.net/yen This email has been screened and filtered by our in house OPT-OUT system in compliance with state laws. If you wish to OPT-OUT from this mailing as well as the lists of thousands of other email providers please visit http://www.wesellforyou.net/yen/optout.html"; //converts string to vector of words breakdown(*spam, arrspam); //clears dynamic memory since it's no longer needed delete spam; //initialize ham training set with real non-spam emails *ham="From: nakagawa@yahoo.com To: scott@gmail.com Subject: Let's celebrate Hi Scott, Thanks for the e-mail. It is always nice to hear from people, especially from you, Scott. I have not got any reply, a positive or negative one, from Seibido yet. Let's wait and hope that it will make a BOOK. Have you finished your paperwork for Kaken and writing academic articles? If you have some free time in the near future, I want to meet you and explain to you our next project. Why not drink out in Hiroshima if we are accepted? We need to celebrate ourselves, don't we? Let's have a small end-of-the-year party! Sincerely, K. Nakagawa To: lauer@microsoft.com From: aisha@microsoft.com Dear Professor Lauer Having had some trouble calling you, I did drop in last Monday, but I have since seen Abdellah who told me he'd seen you and you don't go in on Monday's. How about you nominate a time for me to call you, or nominate a time for me to come and see you or, you can call me if it's easier because I am mostly here in my wee apartment. Please let me know. If you want to call the number is 21-5815. Otherwise, I'm happy to fit in with you. Kind regards, Aisha To: howard@yahoo.com From: reiko@yahoo.com Subject: How are you Hi Howard and Amy. It was great meeting you this week! You both are VERY NICE. The chocolate is in our refrigerator now. We look forward to eating it often throughout this fall! I hope things go well for you in the coming months, Amy and Howard! I'll keep in touch soon. Love, Reiko. From: judy@ovimail.com To: glen@ovimail.com Subject: Hello Hi! How's everything going? Things aren't going so well here. They just let me know that they are cutting all the full time foreign staff here, so I will need a job next year. I was wondering if you know anyone that's hiring. If you do, please let me know. Also I'm thinking of doing a presentation at Hirodai about how to database Hot Potatoes score results, and generally discuss cgi and html applications. Are you interested? I'm going to get in touch with Noda-san and see what I should do. I'm thinking late August, or early September. Keep cool! Judy From: george@mail.com To: lissa@mail.com Subject: Let's talk Hi Lissa, Thanks for note! I love the boundary waters--did we do it together in boy scouts? It's the only time I've been. My daughter Fay would love to canoe there--she's now a freshman at NAU in environmental science and goes backpacking whenever she can. She always thought she'd go to UA in Tucson which is like UW -Madison in Wisconsin, but it turned out that the better program in env. sci. was here and the music program she wanted. Have you thought about college options for George yet? I'm glad you enjoyed the TJ book. We took a family trip to Washington, D.C. this summer and saw the sights and had a family reunion t here too. Great fun. I'd love to see a photo of you all, and especially George! Got one online you can send me? Come visit us and see Grand Canyon etc. next summer, if you can! Love, George Subject: Sandra Jones from: me@x.com to: you@y.com Dear Mike, You may already have heard the news, but I wanted to take a moment to let you know that I am leaving my position here at ABC Company. I have enjoyed my tenure here, and I appreciate having had the opportunity to work with you. I have loved working on group projects with you and thoroughly enjoyed having lunch with you in the break room. Thank you for the support, guidance, and encouragement you have provided me during my time at ABC. I would appreciate any continued advice you could provide as I start the next phase of my career. Please keep in touch. I can be reached at my personal mail sandrajones@gmail2.com or via my cell phone - 555-121-2222. Thanks again for your friendship and support. Best regards, Sandra."; //converts string to vector of words breakdown(*ham, arrham); //clears dynamic memory since it's no longer needed delete ham; //initialize string containing common spelling mistakes *grammar=" accomodate accomodation acheive accross agressive agression apparantly appearence arguement assasination basicly begining beleive belive bizzare buisness calender carribean cemetary collegue comming commitee completly concious curiousity dedinately dilemna dissapear dissapoint ecstacy embarass enviroment existance farenheit familar finaly florescent foriegn forseeable fourty foward freind futher jist glamourous goverment gaurd hapenned harrass harrassment honourary humourous idiosyncracy immediatly incidently independant interupt irresistable knowlege liase liason lollypop manouver millenium millenia neandertal neccessary noticable occassion occured occuring occurance occurence pavillion persistant pharoah peice politican portugese posession prefered prefering propoganda publically realy recieve refered refering religous rember remeber resistence sence seperate seige succesful supercede suprise tatoo tendancy therefor threshhold tommorow tommorrow tounge truely unforseen unfortunatly untill wierd whereever wich "; //initialize word count for spam and ham training set. Note that an offset of 1 is added to the count since we assumed each word occurs at least once in each training set in the compute() function spamcount=arrspam.size()+1; hamcount=arrham.size()+1; } /************************************************/ /*driver code*/ int main() { init(); loop(); complete(); findlink(); findchar(); spellcheck(); is_spam(); return 0; } /************************************************/

spam detector||SoloLearn contest