Aplicarea Algoritmilor DE Machine Learning ÎN Securitatea Informației Pentru Detectarea Email Urilor DE Tip Spam

UNIVERSITATEA DIN ORADEA

FACULTATEA DE INGINERIE ELECTRICĂ ȘI

TEHNOLOGIA INFORMAȚIEI

PROGRAMUL DE STUDIU : SECURITATEA SISTEMELOR DE CALCUL

FORMA DE ÎNVĂȚĂMÂNT: ZI

Disertație

COORDONATOR ȘTIINȚIFIC

Conf. univ. dr. ing. Mirela PATER

ABSOLVENT

Tontea (Ivancsuk) Andrei

ORADEA

2014

UNIVERSITATEA DIN ORADEA

FACULTATEA DE INGINERIE ELECTRICĂ ȘI

TEHNOLOGIA INFORMAȚIEI

PROGRAMUL DE STUDIU : SECURITATEA SISTEMELOR DE CALCUL

FORMA DE ÎNVĂȚĂMÂNT: ZI

APLICAREA ALGORITMILOR DE MACHINE LEARNING ÎN SECURITATEA INFORMAȚIEI PENTRU DETECTAREA

EMAIL-URILOR DE TIP SPAM

OORDONATOR ȘTIINȚIFIC

Conf. univ. dr. ing. Mirela PATER

ABSOLVENT

Tontea (Ivancsuk) Andrei

ORADEA

2014

DECLARAȚIE DE AUTENTICITATE A

LUCRĂRII DE FINALIZARE A STUDIILOR

Titlul lucrării: APLICAREA ALGORITMILOR DE MACHINE LEARNING ÎN SECURITATEA INFORMAȚIEI PENTRU DETECTAREA EMAIL-URILOR DE TIP SPAM

Autorul lucrării: Tontea (Ivancsuk) Andrei

Lucrarea de finalizare a studiilor este elaborată în vederea susținerii examenului de finalizare a studiilor organizat de către FACULTATEA DE INGINERIE ELECTRICĂ ȘI TEHNOLOGIA INFORMAȚIEI din cadrul UNIVERSITĂȚII DIN ORADEA, sesiunea IULIE a anului universitar 2014

Prin prezenta, subsemnatul (nume, prenume, CNP) Tontea (Ivancsuk) Andrei

CNP: [anonimizat]

declar pe proprie răspundere că această lucrare a fost scrisă de către mine, fără nici un ajutor neautorizat și că nici o parte a lucrării nu conține aplicații sau studii de caz publicate de alți autori.

Declar, de asemenea, că în lucrare nu există idei, tabele, grafice, hărți sau alte surse folosite fără respectarea legii române și a convențiilor internaționale privind drepturile de autor.

Oradea,

Data 27.06.2014 Semnătura

Cuprins

Capitolul I – Introducere

1.1 Mesajele spam

Spamming (sau spam) este procesul de expediere a mesajelor electronice nesolicitate, de cele mai multe ori cu caracter comercial, de publicitate pentru produse și servicii dubioase, practicată în industria e-marketingului și de proprietarii de situri pornografice. Spam-ul se distinge prin caracterul agresiv, repetat și prin privarea de dreptul la opțiune. [20]

Spamming-ul este o metodă foarte ieftină de a face reclamă pentru ceva în Internet; succesul campaniei este de obicei proporțional cu numărul de destinatari; de aceea mesajul respectiv este transmis la mii, chiar milioane de adrese simultan.

Termenul Spam a apărut mai întâi pe grupurile de discuții USENET, cu referire la EMP (Excessive Multi Posting) și ECP (Excessive Cross Posting). Astăzi este folosit și pentru a descrie UBE (Unsolicited Bulk E-mail) și UCE (Unsolicited Commercial E-mail).

Denumirea de Spam este derivată dintr-o schiță umoristică a grupului britanic Monty Python, în care într-o cafenea, orice de pe meniu includea SPAM, un fel de parizer din carne de porc. În timp ce un client întreabă pe ospătar dacă are ceva care să nu conțină SPAM, acesta înșiră din nou meniul plin de SPAM. La final, un cor de vikingi se alătură cântând "SPAM, SPAM, minunatul SPAM, gloriosul SPAM", acoperind toată conversația. [20]

1.2 Inteligența artificială

Inteligența artificială este un termen tehnic provenit din limba engleză: Artificial Intelligence, prescurtat AI, care desemnează un domeniu de cercetare în cadrul informaticii.

Definiția cea mai acceptată a inteligenței artificiale a fost dată de John McCarthy în 1955: “o mașină care se comportă într-un mod care ar putea fi considerat inteligent, dacă ar fi vorba de un om”. O trăsătură des întâlnită a inteligenței artificiale este că sistemul respectiv este capabil să învețe, cu sau chiar fără ajutoare externe, cu scopul de a se îmbunătăți permanent.[3]

O altă definiție ar fi: Studiul principiilor, modelelor si metodelor de realizare a sistemelor inteligente artificiale prin intermediul sistemelor de calcul, in sensul reproducerii comportamentului inteligent al sistemelor inteligente naturale. [4]

Inteligența artificială se poate descrie, ca fiind capabilitatea mașinilor sau programelor să mimeze procesele de gândire umane, cum ar fi cugetarea sau învățarea . Mai mult, obiectul Inteligența artificială se poate defini ca fiind  studiul de a face calculatoarele să realizeze lucruri pentru care omul are nevoie de inteligență pentru a le realiza. Această definiție extinsă nu doar include prima definiție, dar acoperă și tehnologiile pe care le utilizează calculatoarele pentru a dobândi sarcini inteligente, chiar dacă acestea nu simulează în mod necesar procesele de gândire umane. O trăsătură des întâlnită a Inteligenței artificiale este că sistemul respectiv este capabil să învețe, cu scopul de a se îmbunătăți permanent și fără ajutoare externe. [5]

1.3 Machine Learning

Ca subdomeniu al inteligenței artificiale, Machine Learning se ocupă cu dezvoltarea de algoritmi și tehnici care le permit calculatoarelor să învețe. Machine learning se suprapune cu tematica statisticii, deoarece ambele se ocupă cu analiza datelor, dar, spre deosebire de statistică, machine learning are ca domeniu de interes complexitatea algoritmică a implementărilor computaționale. Unele sisteme de învățare încearcă se elimine necesitatea intuiției umane în analiza datelor, în timp ce altele adoptă tehnica de colaborare dintre om și mașină. Intuiția umană nu poate fi eliminată în totalitate, întrucât cel care a proiectat sistemul trebuie să specifice modul de reprezentare a datelor și mecanismele ce vor fi utilizate în scopul descoperirii caracteristicilor datelor.

Tehnicile de machine learning sunt organizate astfel: 

–          învățare prin abducție

–          învățare prin inducție

–          învățare transductivă

–          învățare cu întărire.  [1]

1.3.1 Aplicabilități  

 De exemplu, un sistem Machine Learning ar putea fi dezvoltat cu privire la mesajele de e-mail pentru a învăța să distingă între mesajele spam sau non-spam. După ce a ”învătat” să facă distinctia între e-mail-uri, sistemul poate fi apoi folosit pentru a clasifica mesajele e-mail în mesaje de tip spam și în non-spam. Această clasificare ajuă ulterior utilizatorul căsuței de e-mail sa ordoneze e-mail-urile în dosare.

Machine Learning reprezintă studiul algoritmilor care se îmbunătățesc pe baza experienței. Experiența este asociată cu însumarea cunoștințelor dobândite prin intermediul diverselor resurse. Datorită faptului că majoritatea cunoștințelor se află stocate sub forma datelor sau sub formă textuală, pentru ca acestea să poată fi descoperite și utlizate sunt necesare metode de explorare a datelor și a textului, respective text mining și data mining.

Data mining-ul a apărut ca o continuare a metodelor tradiționale de analiză a depozitelor de date (pe volume mari). Datorită costurilor de implementare ridicate a apărut necesitatea identificării unor soluții de extragere a esențialului dintr-un volum foarte mare de date, la costuri mult mai reduse, soluții cunoscute astăzi sub denumirea de data mining. Odată cu expansiunea Intemet-ului și a informației de tip text în format electronic, a apărut necesitatea extragerii automate de cunoștințe și din text, și astfel data mining-ul a cunoscut o nouă specializare: text mining-ul. Spre deosebire de data mining, text mining-ul presupune un software care se adresează publicului larg consumator de servicii în rețea, motivele pentru aceasta fiind universalitatea cererii de achiziționare de informație în timp real și costurile mici (prețul conexiunii) de achiziționare a informației, comparativ cu data mining-ul. Text mining-ul are drept obiectiv principal extragerea automată de cunoștințe, ce trebuie să îndeplinească la rândul lor cerințele de: noutate, validitate, operaționalitate. Text mining este foarte relevant astăzi în special datorită afluxului mare de cunoștințe existente în documentele de tip text, din cadrul sau din afara unei organizații. în organizațiile care se bazează pe informațiile textuale, lucrul cu un amont mare de text devine foarte dificil. întreaga colecție de text este prea mare pentru a putea fi citită și analizată ușor. Mai mult de atât, se modifică in mod constant și necesită revizuire și analiză pentru a fi actualizată. Text mining-ul are în vedere aceste probleme, oferind diverse instrumente pentru a analiza și a învăța din cadrul acestor informații dinamice.

1.3.2 Elemente ce trebuie avute în vedere la selectarea unei soluții text mining

Datorită evoluției accelerate în domeniul text-miningului, utilizatorii trebuie să se ghideze după următoarele reguli când doresc să selecteze una dintre metodele de text mining.Să nu solicite categorizarea manuală, tagging-ul sau construirea unor tezaure.Text mining-ul transmite identificarea automată și indexarea conceptelor din cadrul textelor, prezintă o imagine la nivel înalt a scopului întregului text, cu abilitatea de a "fora" pentru obținerea detaliilor relevante. Tehnicile de text-mining permit utilizatorilor să facă noi asocieri și relații, ducând la noi căi pentru inovare și explorare.

Aplicațiile de text mining se pot clasifica în aplicații online și aplicatii offline. În prezent, cele mai cunoscute aplicații de text mining sunt:

a) Aplicații online pentru:

– căutarea inteligentă pe Internet, care presupune analiza de conținut (cu ajutorul tehnicilor de text mining documentele regăsite de un motor de căutare sunt filtrate, fiind păstrate doar rezultatele cu sensul cautat), dezvoltarea unui profil al utilizatorului (documentele sunt aduse automat fără o solicitare expresă din partea utilizatorului, plecând de la un profil al preferințelor conform cărora programul caută independent documente relevante).

– regăsirea știrilor interesante: selectarea de știri de pe Usenet este o provocare care apare în viața de zi cu zi a multor utilizatori de Internet.

– regăsirea de răspunsuri la întrebări: există întrebări frecvente la care altcineva poate răspunde sau a răspuns deja. Acestea se numesc frequently asked questions și se găsesc împreună cu răspunsurile lor în baze de date.

– filtrarea poștei: partiționarea mulțimii scrisorilor electronice în grade de prioritate în funcție de reacțiile anterioare ale utilizatorului și emiterea de recomandări de ștergere a unor mesaje pasibile de a fi comerciale sau neinteresante.

b) Aplicatii offline pentru:

– clasificarea documentelor preluate de pe Internet.

– rezumarea documentelor (obținând astfel documente condensate și rezumate, abstracturi ale lucrărilor depozitate)

– concatenarea documentelor (de exemplu crearea de relatări ale unor stiri pe baza informațiilor preluate din mai multe surse)

Aplicațiile menționate nu respectă întru totul obiectivul de extragere a cunoștințelor, aceste sisteme realizând cel mult extragere de informații. Extragerea cunoștințelor reclamă mai mult de la metodele de text mining și anume înțelegerea, măcar aproximativă, a documentelor și crearea unui sistem de generare într-o forma inteligibilă de cunoștințe noi. [1]

Capitolul II

Algoritmi Machine Learning

Cei mai importanți algoritmi/tehnici utilizate pentru implementarea diferitelor soluții pentru sistemele de Machine Learning sunt:

Arborii decizionali

k-NN(k-Nearest Neighbor)

Naïve-Bayes

rețelele neuronale

SVM(SUPPORT VECTOR MACHINE)

2.1 Tehnica Bayes

(În limba engleza, denumirea tehnicii este însotita de adjectivul “naiv”: Naïve-Bayes)

Metoda de clasificare bayesiană se bazează pe calcularea probabilităților ca o anumită instanță să aparțină claselor problemei. Într-o rețea bayesiană, se evita calcularea întregii distribuții comune de probabilitate după regula de înmulțire a probabilităților presupunând că un nod depinde doar de părinții săi din graf. În metoda naivă, presupunerea simplificatoare este și mai puternică, considerând că toate atributele sunt independente dată fiind clasa. Acest fapt nu este neapărat adevărat, de cele mai multe ori, dimpotrivă, condiția de independență poate să nu fie satisfăcută. Cu toate acestea, s-a constatat că deseori metoda are rezultate foarte bune. [6]

Bayes este o tehnica de clasificare cu potential atât predictiv, cât si descriptiv. Ea permite analiza relatiei dintre fiecare variabila independenta si variabila dependenta, prin calcularea unei probabilitati conditionate pentru fiecare din aceste relatii. Când o noua instanta se doreste a fi clasifica-ta, predictia se realizeaza prin combinarea efectelor variabilelor independente asupra variabilei dependente

Limitele tehnicii – Pentru instanțele care aparțin setului de date utilizat la calculul probabilităților apriori și al celor condiționale, “predicția” atributului-obiectiv este 100% corectă. Însă pentru instanțe din afara setului de date de instruire, eficiența algoritmului este puternic afectată de prezența unor probabilități condiționate egale sau foarte aproape de zero.

O altă limită a algoritmului provine din asumția ca între atributele independente din setul de date există (teoretic) o independență statistică. Aceasta asumpție stă și la originea adjectivului “naiv” din denumirea algoritmului, având în vedere ca independența statistică de regulă nu se verifică și în practică. Algoritmul este limitat din punct de vedere al inputului la date booleene sau categorice. Dincolo de efortul de preprocesare necesar pentru transformarea datelor cu caracter continuu în intervale valorice, așa cum s-a mai menționat, operațiunea este de multe ori dependentă de experiența și chiar intuiția analistului, factori subiectivi care vor marca rezultatele explorarii.

Avantajele tehnicii – Ținând seama de faptul că pentru calculul probabilităților nu este nevoie decât de o singura parcurgere a setului de date, algoritmul prezintă avantajul important

al unei viteze mari de construire a modelului de clasificare. Ca avantaj semnificativ, algoritmul prezintă capacitatea de a realiza predicții din informații parțiale. În ciuda sensibilității la caracteristici slab reprezentate în setul de date, pentru realizarea unei predicții algoritmul nu are obligatoriu nevoie de toate atributele independente, astfel încât cele identificate de analist a fi irelevante pot fi ușor eliminate din algoritm. De fapt, chiar dacă nu s-ar cunoaște nimic despre atributele independente, analistul tot ar putea face o predictie (fara pretenția de a fi foarte acurata) numai pe baza probabilităților apriori.

Modelul obtinut prin aplicarea algoritmului are si un conținut descriptiv, care poate fi util analistului. Probabilitățile condiționate aferente fiecărui atribut independent pot fi utilizate în a descrie legatura dintre acestea și atributul-obiectiv. [2], [6]

Dintre avantajele metodei de clasificare bayesiene trebuie să menționăm calculele simple și robustețea la zgomot și atribute irelevante. De aceea, este foarte potrivită pentru mulțimi de antrenare de dimensiuni medii sau mari (de exemplu pentru clasificarea documentelor text, detecția spam-ului, diagnoză etc.). Chiar dacă se bazează pe independența atributelor dată fiind clasa, metoda funcționează de multe ori bine chiar și atunci când presupunerea este infirmată în realitate. [6]

2.2 ALGORITMUL k-NN (prescurtare a k-Nearest Neighbor)

k-NN este cea mai simplă metodă de clasificare bazată pe instanțe. Algoritmul presupune că toate exemplele sunt plasate într-un spațiu n-dimensional. Fiecare instanță de test este clasificată în funcție de cele mai apropiate k exemple din memorie, fără a încerca să se determine funcția de distribuție pe baza căreia instanțele sunt plasate în spațiul n-dimensional. [7]

Pentru a găsi și extrage din memorie aceste exemple, estenevoie de o metodă de a compara cât de similare sunt două  instanțe. În cazul în care se lucrează cu valori reale, se pot aplica metrici de genul distanței Euclidiene, distanței normate sau funcției cosinus între instanțe. Pentru situațiile în care valorile sunt discrete, se calculează numărul caracteristicilor distincte între cele două instanțe.

În continuare vom detaila doar ultima variantă, cazul valorilor reale fiind similar, unica diferență fiind modul de calcul al similarității dintre două instanțe.

După definirea unei metrici pentru determinarea similarității dintre două instanțe, următorul pas este să se calculeze distanța dintre exemplul de test și toate exemplele de învățare aflate în memorie. În ultimul pas se determină pentru fiecare instanță de test care sunt cele maiapropiate k instanțe din setul din memorie și pe baza acestor instanțe similare se decide care este cea mai probabilă clasificare a acesteia. Acest lucru se realizează  prin votarea între cele mai similare k instanțe. Din modul de calcul al clasificării instanțelor de test se observă faptul că algoritmul k-NN utilizează o aproximare diferită pentru fiecare instanță de test în parte. Acest lucru oferă un mare avantaj în cazul în care funcția de distribuție este foarte complexă, dar poate fi descrisă printr-o colecție de aproximări locale mai puțin complicate. [7]

Dezavantajele tehnicii . Timpul de calcul este direct proporțional cu numarul de instanțe din setul de date. Din acest motiv, pentru seturi mari de date se impune ca în etapa de preprocesare, din setul inițial de date sa se selecteze un subset de instanțe cu dimensiuni rezonabi-le. Algoritmul lucrează eficient în probleme de clasificare atunci când toate clasele aferente atributului-obiectiv au o reprezentare egală ca pondere în setul de date, fapt care face necesară “îmbogațirea” setului de date original. Algoritmul pe care se bazează tehnica k-NN permite doar realizarea unei estimări a valorii atributului-obiectiv, fară a produce informații suplimentare despre instanța supusa analizei, despre structura setului de date ori despre categoriile de clasificare a atributului-obiectiv.

De cele mai multe ori este dificil de stabilit ce tip de funcție estimează cel mai bine distanța dintre două instanțe. Deși din punct de vedere matematic tehnica permite calculul distanțelor și pentru atribute categorice si booleene, în astfel de cazuri metrica devine puternic influențată de transformarile aplicate de analist setului de date în preprocesare. De aceea,

k-NN este de preferat a fi utilizata mai mult în situațiile în care pentru toate atribute-le instanțelor se poate aplica aceeasi functie de distanta.

Avantajele tehnicii-. Tehnica permite clasificarea în multiple clase si modelarea relatiilor neliniare dintre date (în probleme de predictie).Pentru tehnicile care necesita o etapa de învatare a carei output îl constituie un model predictiv, exista riscul ca acest model sa devina desuet în timp, iar predictiile realizate în baza lui sa piarda din reprezentativitate. În cazul k-NN, modelul îl constituie chiar setul de date, care se presupune ca odata supus analizei, este deja în forma sa cea mai recenta. Chiar daca de multe ori pot aparea dificultati în stabilirea unei metrici eficiente, algoritmul este unul dintre putinele care accepta ca input date de natura diferita (continua, categorica, booleana etc) [2]

2.3 Retele neuronale

Tehnica are la baza doua concepte apartinând domeniului inteligentei artificiale:

Neuronul artificial – reprezinta unitatea de baza pentru prelucrarea informatiei în cadrul calculului neuronal. Prin analogie cu neuronul biologic, el a fost definit ca o unitate ce proceseaza inputuri informaționale si generează outputuri.

Reteaua neuronala artificiala – reprezinta un ansamblu de neuroni artificiali, legati prin conexiuni. Rețelele neuronale sunt sisteme dinamice, al caror comportament poate fi caracterizat prin urmarirea stărilor la momente diferite de timp. Starea unei retele la un moment dat este definita de ansamblul nivelurilor de activare a neuronilor si de intensitatile conexiunilor dintre neuroni. În plus fata de acești parametri ajustabili, o retea este definită si de următorii parametri ficși: configurația conexiunilor și tipul functiilor de activare.

Dezavantajele tehnicii – Retelele neuronale nu opereaza decât direct asupra variabilelor numerice. Drept urmare, orice variabila non-numerica din setul de date care se doreste analizat va trebui convertita în variabila numerica înainte de utilizarea sa în instruirea retelei. În cazul problemelor complexe, utilizatorul este pus în situația de a rezolva un compromis, între a creste numarul de neuroni ascunsi, ceea ce poate conduce la o instruire foarte lenta și a accepta o topologie mai simpla, asociata unei solutii mai putin precise. Pentru seturi de date cu numar mare de atribute, folosirea retelelor neuronale devine nefezabila.

Determinarea numarului de neuroni ascunși, pentru probleme complexe de clasificare, nu se poate face decât experimental, ceea ce pe de o parte crește substantial timpul alocat cautării modelului optim de clasificare, iar pe de alta parte lasa calitatea rezultatelor analizei să depinda de nivelul de experientă al utilizatorului. Absența componentei descriptive într-un model generat de o rețea neuronală face ca evolutia modelului în etapa de instruire sa fie lipsita de transparența pentru utilizator. Datorita acestei caracteristici, tehnica este deseori comparata cu o “cutie neagra”.Unul dintre cele mai mari neajunsuri al rețelelor neuronale este timpul îndelungat necesar pentru o buna instruire, fapt corelat cu necesitatea existentei unui numar relativ mare de instante în setul de instruire.

Avantajele tehnicii – Reteaua odata instruită poate realiza predicții rapide pentru instante noi. Aceasta caracteristica face ca rețelele neuronale sa fie utilizate cu succes în probleme care necesita raspuns în timp real. Rrețelele neuronale reprezintă o metodă foarte eficienta de modelare a unor relatii neliniare. Aplicațiile în care a fost implementate rețelele neuronale au demonstrat aplicabilitatea acestei tehnici în domenii dificil de modelat, precum

vederea, electronica sau recunoastere vocala.

Spre deosebire de celelalte tehnici, retelele neuronale nu restrictioneaza output-ul la un singur atribut. Folosind o arhitectura de retea potrivita se pot obtine predictii simultane pentru mai multe variabile, ceea ce poate însemna o eficientizare semnificativa a proceselor de explorare a datelor. [2]

2.4 Arbori decizionali

Arborele decizional este o tehnică de explorare a datelor cu potențial atât predictiv, cât si descriptiv. Denumirea sa provine de la aceea ca rezultatul se prezintă utilizatorului sub forma unui graf de tip arbore. Output-ul major al unui model bazat pe arbori decizionali este arborele în sine. Procesul de instruire care creeaza arborele este numit inductie. Inducția presupune, ca si în cazul rețelelor neuronale, parcurgerea de câteva ori a setului de date de instruire, cu deosebirea că în cazul arborilor, timpul de instruire si implicit numarul de baleieri ale setului de date este mult mai mic decât la rețelele neuronale. Mai precis, numarul de parcurgeri ale setului de instruire este egal cu numarul de niveluri în arbore.

Limitele tehnicii – Majoritatea algoritmilor nu folosesc întregul set de date indicat de utilizator pentru inducție. Pentru acesti algoritmi, construirea arborelui presupune transferul instantelor din setul de date de instruire în memoria RAM. Dimensiunea limitată a memoriei face ca programul sa transfere în RAM numai un subset de date, selectat aleator. În consecință, gradul de reprezentativitate al modelului construit este determinat de capacitatea aplicație de a selecta un subset reprezentativ pentru întreg setul de inductie.

O critică adusa frecvent arborilor decizionali este aceea ca algoritmii de inducție nu iau în considerare la momentul splitarii efectul pe care respectiva separare o are asupra viitoarelor splitari. În plus, toate separarile se fac secvential, ceea ce determina dependenta fiecarei splitari de cele precedente.

Avantajele tehnicii – Majoritatea algoritmilor care construiesc arbori decizionali pot fi aplicați fară restricții legate de tipul datelor. Deși variabila dependentă trebuie sa fie de natura

numerica (în cazul problemelor de regresie) sau categorică (în cazul problemelor de clasificare), pentru majoritatea algoritmilor, variabilele independente pot lua valori în orice domeniu.

Tehnica se caracterizează prin capacitate de prelucrare a unor seturi de date cu număr mare de atribute. Exista situatii în care o instanta poate fi descrisa printr-un număr relativ mare de atribute, de ordinul sutelor sau chiar miilor. În astfel de situatii, explorarea prin tehnica arborilor decizionali reprezintă singura alternativă, cei mai multi algoritmi fiind capabili să trateze seturi de date cu peste 1000 de coloane.

Algoritmii de construire a arborilor decizionali necesită un numar redus de parcurgeri

setului de date utilizat în inductie. Consecința directă a acestei caracteristici funcționale este rapiditatea procesului de inducție și aplicarea eficientă asupra seturilor mari de date. Forma outputului permite nu numai realizarea de previziuni și clasificări, ci și descrierea relațiilor existente între variabilele independente si variabila dependenta. În plus, forma grafica a outputului faciliteaza analiza relațiilor. Exista aplicatii care permit reprezentarea arborelui sub forma unui set de reguli care, pentru arbori de dimensiuni mari, este mai usor de înteles.[2]

Tabelul 2.1- Analiza comparativa a celor patru tehnici descrise mai sus [2]

2.5 SVM(SUPPORT VECTOR MACHINE)

Support Vector Machine (SVM) este o tehnică de clasificare bazată pe teoria învățării statistice care a fost aplicată cu mult succes în multe probleme neliniare de clasificare și pentru mulțimi foarte mari de date.

Idea algoritmului SVM este de a găsi un hiperplan care împarte optim setul de date de

antrenament. Hiperplanul optim se poate distinge prin marginea de separare maximă dintre toate punctele de antrenare și hiperplan. Pentru o problemă într-un spațiu bidimensional algoritmul caută după o dreapă care separă „cel mai bine” punctele din clasa pozitivă de punctele din clasa negativă . Hiperplanul este caracterizat printr-o funcție de decizie de forma:

f(x) = sgn(<w,x> + b)

unde: – w este vectorul pondere, perpendicular pe hiperplan, “b” este un scalar care reprezintă

marginea hiperplanului, “x” este eșantionul curent testat și <*,*> reprezintă produsul scalar.

Sgn este funcția semn care întoarce 1 dacă valoarea obținută este mai mare sau egală cu 0 și -1 altfel. Dacă w este de lungime 1, atunci <w,x> este de lungimea lui x de-a lungul direcției lui w . În general w va fi scalat prin ||w||. În partea de antrenare algoritmul trebuie să găsească

vectorul normal “w” care conduce la cea mai mare margine “b” a hiperplanului. [8]

Modalitatea de lucru al acestui model este sintetizata in figura 1.Asa cum se poate deduce vectorii suport sunt cele 5 puncte vizibile pe linia delimitatoare față de marginea de clasificare.

Figura 1. Detalierea modelului SVM int-un spatiu bidimensiona [23]

Capitolul III

Aplicații ale Machine Learning pentru detectarea email-urilor de tip spam -SpamAssassin

SpamAssassin este o aplicatie care filtreaza mesajele si care incearca să identifice mesajele de tip spam folosind diferite tehnici printre care: analiza textului, filtrare Bayesiană, blocarea DNS-ului si folosirea unei baza de date open source SpamAssassin. SpamAssassin detecteaza automat mesajele de tip spam inainte ca acestea sa ajunga in casuta de email. La activarea contului de gazduire SpamAssassin este dezactivat, insa activarea acestui serviciu se poate face foarte ușor ca în imaginea de mai jos:

Fig 3.1 Activarea SpamAssassin

Doar simpla activare a SpamAssassin poate fi de ajuns pentru a filtra mesajele de tip spam, nefiind nevoie de alte configurari suplimentare, dar exista si optiunea de a configura SpamAssassin mai in detaliu, insa aceste optiuni sunt pentru a adauga adrese de email sau liste cu adrese de email in blacklist, pentru a fi marcate intotdeuna ca spam, sau in whitelist, pentru ca mesajele primite de la aceste adrese sa nu fie marcate niciodata ca spam. [16] , [17]

Fig 3.1

Capitolul IV

Tehnologiile utilizate si mediul de dezvoltare a aplicației

4.1 PyCharm- Generalități

Dinpunctul meu de vedere descrierea completa a acestuia se afla chiar pe propria pagina si anume:

„The intelligent Python IDE with unique code assistance and analysis, for productive Python development on all levels.”[9]

PyCharm este un mediu de dezvoltare integrat (IDE) utilizat pentru a scrie cod în Python. Acesta oferă analiză de cod, debugger grafic, teste unit integrate, integrare VCS / DVCS și suporta dezvoltare web cu Django. PyCharm este dezvoltat de compania ceha JetBrains . [10]

Poate fi utilizat pe urmatoarele sisteme de operare: Windows, Mac OS X și Linux. PyCharm a fost lansat sub o licență dubla, una proprie – brevetata sub numele de „Professional Edition” ( advanced tool for professional Python and Web development)

și, de asemenea una free, sub licența Apache- PyCharm Community Edition (for pure Python coding and learning), care este mai puțin extensibila.

Caracteristici :

– Code editor – PyCharm, ca orice alt mediu de dezvoltare integrat, suportă syntax highlighting (caracteristica prin care textul este colorat diferit, în funcție de tipul termenilor) si code completion pe baza IntelliSense. Code completion se refera la autocompletare textului înainte ca programatorul să termine de completat textul, iar syntax highlighting la caracteristica prin care textul este colorat diferit, în funcție de tipul termenilor.De asemenea suportă adăugarea de marcaje pentru o navigare mai rapidă, include un clipboard și un tasklist.

– O caracteristică foarte importantă este compilarea în fundal. Pe măsură ce codul este scris, PyCharm îl compilează, pentru a furniza un feedback despre sintaxă și erorile de compilare (marcate cu o linie ondulată roșie; avertizăriile sunt subliniate cu o line verde).Compilarea în fundal nu generează cod executabil și are nevoie de un compilator diferit decât cea utilizată la generarea codului executabil.

– Debugger – PyCharm include un debugger (sau un depanator) ce lucrează atât cu cod nativ cât și cu cod administrat. De asemenea, permite stabilirea de breakpoints (ce permit oprirea temporară a execuției la o anumită poziție) și watches (ce monitorizează valoarea unei variabile pe măsură ce execuția progresează). Breakpoints pot fi condiționate, în sensul că sunt declanșate doar dacă este întâlnită condiția. Există de asemenea opțiunile stepped over (pentru a rula linie cu linie codul sursă), step into și step over. Dacă mouse-ul se află deasupra unei variabile în timpul depanării, apare valoarea curentă a variabilei într-un tooltip, unde aceată valoare poate fi modificată, dacă se dorește acest lucru.
– Refactorizare: inclusiv redenumirea varioabillelor, metode de extragere, introduce variabile, introduce constante și altele.

– Instrumente de dezvoltare web Django si multe altele.

Am ales PyCharm in mod special, pentr ca este free, dar are in spate o comunitate suficient de mare, este dedicat Python si ca atare acopera destul de multe din cerintele majoritatii dezvoltatorilor.
Prima ar fi autocompletarea. Din punctul meu de vedere nu e importantă doar pentru că scrii mai puțin cod, ci pentru că dezvăluie funcții din module pe care nu le cunoști și te scutește de ore de căutat în documentație.

Un alt aspect important este suportul pentru proiect: multe din IDE-uri nu te lasă să testezi o funcție fără să creezi un proiect, ceea ce este ridicol pentru python. Exista posibilitatea sa navigezi ușor cu o hartă a claselor, fără să mut fiecare clasă în fișierul ei.

Deloc lipsit de importanță, consumul de resurse ar trebui luat în calcul. Dacă îți trebuie ultima generație de masina doar pentru un IDE, cred că majoritatea preferă să muncească ceva mai mult cu un text-editor decăt să plătească.

Figura. 4.1 Interfata IDE-ului PyCharm

4.2 Limbajul Python -generalități

Python este un limbaj de programare dinamic multi-paradigmă, creat în 1989 de programatorul olandez Guido van Rossum.

Python este un limbaj de programare foarte popular azi, oferind posibilitatea programarii structurale dar și orientate pe obiecte și incluzând și elemente din paradigma funcțională. Este un limbaj de scripting, ceea ce înseamnă ca este interpretat și nu compilat, economisind mult timp în procesul de dezvoltare și depanare. [11]

Implementarea de baza CPython este software liber și este administrată de fundația Python Software Foundation. Implementarea principală a Python, CPython (scrisă în C) a fost concepută pentru a fi portabilă: funcționează pe Linux, Unix, Windows, Mac X. Pe platformele mobile actuale există implementări pentru iOS, iar Android oferă SL4A, o platformă pentru limbaje de scripting cu suport și pentru Python, folosită de engine-uri precum QPython. Programele pot fi executate, de asemenea, și pe mașina virtuală Java prin folosirea compilatorului Jython, care le transformă în bytecode Java și permite și folosirea de clase Java în cadrul acestora. Similar, există IronPython pentru .NET. [11]

Python este un limbaj multifuncțional folosit de exemplu de către companii ca Google sau Yahoo! pentru programarea aplicațiilor web, însă există și o serie de aplicații științifice sau de divertisment programate parțial sau în întregime în Python.

Python pune accentul pe curățenia și simplitatea codului, iar sintaxa sa le permite dezvoltatorilor să exprime unele idei programatice într-o manieră mai clară și mai concisă decât în alte limbaje de programare ca C. Sistemul de tipizare este dinamic iar administrarea memoriei decurge automat prin intermediul unui serviciu „gunoier” (garbage collector). Alt avantaj al limbajului este existența unei ample biblioteci standard de metode.[12]

4.2.1 Particularități de sintaxă

Indentarea

Indentarea în Python este mai mult decât parte a stilului de programare, este chiar parte din sintaxă

O linie nouă termină o declarație, pentru a continua o declarație pe mai multe linii, se foloseste caracterul “\”.

Un bloc de cod are toate liniile indentate cu același număr de spații (nu există begin și end sau {}). Instrucțiunile dintr-un bloc de cod vor fi grupate unele sub altele, pe același nivel de indentare.

Definițiile neindentate într-un program Python vor fi de obicei variabile globale, definiții de clase, proceduri, funcții sau părți ale main-ului.

După instrucțiuni nu este obligatoriu să puneți simbolul ';' precum în alte limbaje de programare, indentarea corespunzatoare fiind suficientă.

Este foarte important sa nu uitați simbolul ':' care precede o indentare.

4.2.2 Tipuri de date și variabile

Python oferă tipuri de date numerice, booleene, șiruri (string, liste etc), dicționare, fișiere, clase, instanțe și excepții.

Din punct de vedere al tipării Python folosește tipuri pentru obiecte, însă la definirea variabilelor nu trebuie precizat tipul acestora. Constrângerile de tip sunt verificate la execuție (late binding), astfel încât pot apărea erori si excepții generate de folosirea unui tip necorespunzător în atribuiri și excepții.

Python asociază numele unei variabile cu un obiect, care poate fi număr, șir de caractere sau ceva mai complex. Când este folosită o variabilă, tipul acesteia este tipul obiectului cu care este asociată. Este greșită folosirea intr-o expresie a unei variabile care nu a fost asociată cu un obiect.

Alocarea și dealocarea de memorie se face automat de către Python, existând un mecanism de garbage collection.[11]

4.2.3 Main-ul

Construcția main este opțională în scripturile Python, și rolul său este similar funcțiilor main din alte limbaje (C, Java etc).

Codul conținut într-un script Python este executat și fără prezența acestui mecanism, însa dezavantajul nefolosirii lui este că atunci când se include fișierul cu import se va executa și codul din el.[13]

4.2.4 Biblioteci și Extindere

Includerea tuturor acestor structuri, precum și a funcțiilor ce permit manipularea și prelucrarea lor, precum și multe alte biblioteci de funcții sunt prezente datorită conceptului “Batteries Included”, ce poate fi explicat prin faptul că Guido van Rossum și comunitatea ce s-a format în jurul limbajului cred că un limbaj de programare nu prezintă utilitate practică dacă nu are un set de biblioteci importante pentru majoritatea dezvoltatorilor.

Din acest motiv Python include bibioteci pentru lucrul cu fișiere, arhive, fișiere XML și un set de biblioteci pentru lucrul cu rețeaua și principalele protocoale de comunicare pe internet (HTTP, Telnet, FTP). Un număr mare de platforme Web sunt construite cu Python. Abilitățile limbajului ca limbaj pentru programarea CGI sunt în afara oricăror dubii. De exemplu YouTube, unul din site-urile cu cea mai amplă cantitate de trafic din lume, este construit pe baza limbajului Python.

Totuși, Python permite extinderea funcționalității prin pachete adiționale programate de terți care sunt axate pe o anumită funcționalitate. De exemplu, pachetul wxPython conține metodele și structurile necesare creării unei interfețe grafice.[12]

4.3 Expresii regulate – RegexBuddy

Expresiile regulate (sau regex) sunt un șir de caractere șablon care descriu mulțimea cuvintelor posibile care pot fi formate cu acele caractere, respectând anumite reguli. Aceste expresii regulate folosesc paranteze (rotunde, pătrate, acolade) prin care formează regulile de formare a cuvintelor. Utilitatea cea mai frecventă a unei expresii regulate constă în a recunoaște dacă un șir conține sau nu sub-șiruri care pot fi formate prin expresia regulată respectivă.

Cu ajutorul expresiilor regulate se pot găsi sau înlocui anumite părți dintr-un text. Sunt o metodă obisnuită de a verifica de exemplu validitatea adreselor de e-mail, domenii de internet, coduri poștale și altele. Un e-mail valid trebuie să se muleze pe un model prestabilit. De asemenea cu ajutorul expresiilor regulate putem să analizăm fișiere mari de text în căutarea informațiilor dorite.

Utilitarul pe care îl propun si pe care l-am utilizat si eu în construirea expresiilor regulate este RegexBuddy de la firma “Just Great Software “. Este o unealta ușor de utilizat si intuitivă in construirea regex-urilor și are un preț acceptabil.

RegexBuddy este poate cel mai puternic si bogat utilitar in caracteristici program pentru manipulari de expresii regulate și are posibilitatea de a exporta expresia in cele mai populare limbaje de programare.

Utilizarea programului de asistenta in construirea expresiilor regulate, RegexBuddy, ofera o modalitate comoda de scriere a codului, permitand inlocuirea mai multor linii cu o simpla functie, dar cere insa putin exercitiu si atentie.Nu exista un tipar unic pentru o restrictionare. Decizia pentru o expresie sau alta trebuie facuta cantarind intre exact si practic, pentru ca utilizarea acestora poate avea efecte in performanta programului. Din acest motiv as dori sa subliniez accentuat faptul că calitatea datelor colectate de către aplicatia propusă depinde intr-o mare măsură de abilitatea operatorului de a construi expresii regulate.

În cele ce urmează voi detalia câteva reguli esențiale in scrierea expresiilor regulate și voi prezenta mai multe caractere speciale specifice utilitarului RegexBuddy si rolul lor in expresiile regulate.

Astfel:

^   – indica inceputul liniei

$   – indica sfarsitul liniei

.   – (punct) orice caracter

[]   – un caracter dintre cele din paranezele patrate

[^]   – orice caracter, in afara celor din paranezele patrate

\   – scoate din contextul formari expresiei caracterul care urmeaza

+   – caracterul sau expresia anterioară acestui semn se poate repeta odata si de cate ori e posibil (de la 1 la infinit)

*   – caracterul sau expresia anterioră acestui semn se poate repeta de cate ori e posibil sau niciodată (de la 0 la infinit)

?   – caracterul (expresia) anterior acestui semn se poate repeta ce mult odata

(|)   – lista de optiuni SAU

{m, n}   – repetarea expresiei de la "m" la "n" ori

[a-z] – marchează toate caracterele cuprinse intre a-z

[1-9] – marchează cifrele de la 1 la 9

\w – este echivalent cu [A-Za-z0-9_]

\d – este prescurtarea pentru [0-9] cifrele zecimale

\s – [\n\r\t\f] specifică spatiile albe

\W – [^A-Za-z0-9_] – tot ce nu este word caracter

\D – [^0-9] tot ce nu este cifră zecimală

\S – [^\n\r\t\f] tot cu nu este spațiu alb.

CAPITOLUL V

Detalii privind implementarea filtrelor pentru detectarea email-urilor de tip spam

5.1 Generalități

Asa cum am mai relatat anterior lucrarea de fata isi propune sa prezinte algoritmii cei mai utilizati in machine learning si sa implementeze in python un filtru pentru detectarea emailurilor de tip spam.

In acest sens pentru a exemplifica cat mai pe inteles voi reveni pe scurt la explicatiile algoritmului Naive Bayes, care-l voi aplica in cele ce urmeaza.

5.2 Pași pentru realizarea clasificatorilor de texte

In vederea determinarii claselor de care apartin un text ce apartine unui email trebuie parcurse cateva etape.

Aceste etape sunt:

– Preprocesarea datelor

– Construirea, antrenarea si testarea modelului (modelelor)

– Aplicarea modelului pe date noi .

Figura 5.1 – Etapele procesului de machine learning [15]

Preprocesarea datelor presupune citirea datelor bute, cură area lor și prelucrarea lor în

vederea optimizării procesului de machine learning.

Datele brute pot con ine valori lipsă, date introduse greșit, date expirate, date duplicat,

valori aberante sau pot fi afectate de zgomot. În acest sens se impune o primă

preprocesare a datelor brute, prin estimarea valorilor lipsă, prin eliminarea datelor duplicat

sau expirate, prin eliminarea sau corectarea datelor introduse greșit, prin utilizarea unor

parametri statistici toleran i la valori extreme prin utilizarea de filtre hard și soft pentru

reducerea zgomotului, etc. În urma prelucrării datelor brute se ob in date cură ate.

Datele curățate trebuie preprocesate în continuare, în vederea optimizării procesului de

data mining. Câteva tehnici care pot fi utilizate în acest scop sunt prezentate în continuare:

• Agregarea – combinarea mai multor atribute existente într-un singur atribut, cu

scopul reducerii volumului de date și al ob inerii de date mai stabile (exemplu:

agregarea satelor în comuna de care apar in, a orașelor în jude ul de care apar in, a

vânzărilor săptămânale în vânzările lunare, etc.)

• Eșantionarea – se alege un eșantion reprezentativ pentru întreaga mul ime de date.

O problemă importantă este alegerea optimă a volumului eșantionului astfel încât să

nu se piardă date dar să nici nu fie mai multe decât este necesar.

• Reducerea dimensionalită ii – se știe că atunci când dimensiunea (numărul

atributelor) crește va crește în mod implicit și împrăștierea datelor, ceea ce duce la

scăderea vitezei de lucru. Acest fenomen este denumit în data mining ca și blestemul

dimensionalită ii (curse of dimensionality). Antidotul este reducerea dimensionalită ii

prin tehnici ca: analiza factorială și analiza componentelor principale.

• Selectarea de submul imi de caracteristici – pentru eliminarea caracteristicilor

redundante sau nerelevante

• Crearea de caracteristici – crearea de noi atribute care pot capta mai bine

informațiile din date decât cele originale

• Discretizarea și binarizarea – trecerea de la date continue la date discrete (de exemplu trecerea de la numere reale la numere întregi)

• Transformarea atributelor – transformarea unor atribute vechi în atribute noi

În mod op ional, datele cură ate sau preprocesate pot fi supuse unei etape de analiza

statistică a valorilor fiecărui atribut. Această analiză statistică poate extrage din date

informa ii utile, privind distribu ia valorilor fiecărui atribut și ajută la în elegerea datelor.

Construirea modelului și testarea lui. De regulă, în studiile de data mining se

construiesc mai multe modele și se alege cel mai performant dintre ele. O situa ie rară, în care

nu se justifică construirea mai multor modele, este aceea în care primul model construit este

cel mai bun cu putin ă (de exemplu am construit un model clasificator care are o acurate e a

predic iei de 100 %). De obicei însă, este necesară construirea mai multor modele cu diferi i

algoritmi, compararea performan elor ob inute de toate modelele și alegerea celui mai bun

model. Dacă toate modelele pe care încercăm să le construim au performan e nesatisfăcătoare,

este necesară revenirea în etapa de preprocesare, prelucrarea datelor fie prin discretizare, fie

prin alte tehnici precum selectarea și crearea de caracteristici și reconstruirea modelelor, poate

că în urma unor prelucrări a datelor de intrare vor ob ine performan e mai bune. Construirea

oricărui model se face învă ând din datele disponibile. Pentru a învă a din date se pot utiliza

diverse tehnici (clasificare, regresie, grupare sau reguli de asociere) și diverși algoritmi în

funcție de tehnica aleasă. De exemplu pentru clasificare se pot folosi algoritmii Naive Bayes,

C4.5, Suport Vector Machines, pentru regresie se pot folosi algoritmi de regresie liniara,

regresie liniara multipla, regresie logistica, pentru grupare se pot folosi algoritmii K-Means,

EM, FarthestFirst, pentru a descoperi reguli de asociere algoritmul Apriori, FPGrowth etc. Un

model poate fi testat pe datele de antrenare, sau întregul set de date se împarte în date de

antrenare și date de test (în acest caz va fi testat pe date noi și trebuie ales procentul de

instan e folosit la antrenare), etc. În func ie de algoritmul folosit pentru construirea modelului

trebuie configura i parametrii specifici de intrare și trebuie aleși parametrii de ieșire.

Dacă cel pu in unul din modele construite ob ine rezultate satisfăcătoare, atunci

modelul poate fi aplicat pe date noi.[15]

In cazul nostru clasele sunt:

email de tip SPAM – sau pe scurt spam

emai de tip NON-SPAM – sau pe scurt de tip „ham”

5.3 Aplicarea etapelor in creerea modelului nostru pentru clasificarea email-urilor

5.3.1 Colectarea si preprocesarea datelor

5.3.1.1 Colectarea sau achizitia emailurilor

Pentru colectarea datelor am creat un crawler in PHP, care a adunat datele din mai multe conturi personale de email (majoritatea de la yahoo) si le-a pus intr-o baza de date mysql. In acest sens am utilizat expresii regulate si Xpath-uri pentru a extrage informatiile necesare din pagina.

Codul PHP aferent crawlerului il voi prezenta in randurile urmatoare:

<?php

require_once '../core/mink.phar';

require_once '../core/helper.php';

require_once '../core/MySqlClass.php';

use \Behat\Mink\Driver\Goutte\Client as GoutteClient, Behat\Mink\Driver\GoutteDriver, Behat\Mink\Session;

$connectionInfo = array ( 'host' => '127.0.0.1', 'user' => 'root', 'pass' => 'ela', 'db' => 'emails' );

$m = new MySqlcon ( $connectionInfo );

$session = new Session ( new \Behat\Mink\Driver\Selenium2Driver ( 'phantomjs', array () ) ); $session->start ();

$session2 = new Session ( new \Behat\Mink\Driver\Selenium2Driver ( 'phantomjs', array () ) ); $session2->start ();

/*$client = new GoutteClient ();$driver = new GoutteDriver ( $client );$session = new \Behat\Mink\Session ( $driver );

$session->start ();setHeaders($session);*/

$session->visit ( 'https://login.yahoo.com/config/mail?&.src=ym&.intl=ro');

$mainPage = $session->getPage ();

//print_r($mainPage->getContent());die;

$mainPage->find( 'xpath', '//div[@id="inputs"]/input[@id="username"]' )->setValue('andreitontea89');

$mainPage->find( 'xpath', '//div[@id="inputs"]/input[@id="passwd"]' )->setValue('parola');

$mainPage->find( 'xpath', '//div[@id="submit"]/button[@type="submit"]' )->click();

sleep(2);

$mainPage = $session->getPage ();

//print_r($mainPage->getContent());die;

if($continueLink = $mainPage->find( 'xpath', '//div[@class="rs-return"]/a[@class="rs-continue"]' )){

$session->visit ($continueLink->getAttribute('href'));

$mainPage = $session->getPage ();

//print_r($mainPage->getContent());die;

}else{die('error at ContinueLink');}

$emails = $mainPage->findAll ( 'xpath', '//div[contains(@class,"list-view-item-container ")]//div[@class="subj"]' );

//print_r($emails[3]->getText());die;

//print_r(count($emails));die;

$ln = count ( $emails);//echo $ln;die;

foreach ($emails as $email) {

$email->click();

sleep(3);

$Page = $session2->getPage ();

print_r($Page->getContent());die;

$firma = array();

if($title = $mainPage->find ( 'xpath', '//div[@aria-label="Message header"]/h3/span[@class="thread-subject"]' )){

$firma['title'] = $title->getText();

}

if($from_email = $mainPage->find ( 'xpath', '//span[@class="from lozengfy"]' )){

$firma['from_email'] = $from_email->getAttribute('data-address');

}

print_r($firma);//die;

if($backLink = $mainPage->find( 'xpath', '//a[@class="btn x-gap btn-inbox"]' )){

$backLink->click();

sleep(1);

$mainPage = $session->getPage ();

//print_r($mainPage->getContent());die;

$emails = $mainPage->findAll ( 'xpath', '//div[contains(@class,"list-view-item-container ")]//div[@class="subj"]/span[contains(@class,"subject")]' );

}else{die(' error la BACK LINK!! ');}

}

Din aceasta tabela apoi datele au fost incarcate in liste locale in cod python:

train_spam_messagesMysql, test_spam_messagesMysql=FromMysql.TakeFromDB()

cu ajutorul functiei python TakeFromDB din clasa mysqlProcessing:

class mysqlProcessing(object):

def TakeFromDB(self):

db = mysql.connector.connect(host="localhost", # your host, usually localhost

user="root", # your username

passwd="passw", # your password

db="email") # name of the data

cursor = db.cursor()

script= """SELECT content FROM email.spam_emails_distinct; """

train_spam_messages=[]

try:

cursor.execute(script)

all_spam_messages =cursor.fetchall()

train_spam_messages =all_spam_messages[:400]

test_spam_messages =all_spam_messages[401:]

except Exception as e:

s = str(e)+' '+str(sys.exc_traceback.tb_lineno)

print s

return

cursor.close()

db.close

return (train_spam_messages, test_spam_messages)

Dar datorita faptului ca am constatat lipsa setului de emailuri de tip ham am completat atat setul de antrenare cat si cel de testare cu date din cursul de MachineLearning de Andrew Ng [22], astfel:

train_ham_messages = get_msgdir('/home/dana/Documents/DataEmails/nonspam-train')

test_ham_messages = get_msgdir('/home/dana/Documents/DataEmails/nonspam-test').

Acest pas a fost realizat cu functiile get_msgdir si get_msg :

def get_msgdir(path):

try:

filelist = os.listdir(path)

filelist = filter(lambda x: x != 'cmds', filelist)

all_msgs =[get_msg(os.path.join(path, f)) for f in filelist]

return all_msgs

except Exception as e:

s = str(e)+' '+str(sys.exc_traceback.tb_lineno)

print s

def get_msg(path):

try:

with open(path, 'rU') as con:

msg = con.readlines()

msg = msg[0: ]

return ''.join(msg)

except Exception as e:

s = str(e)+' '+str(sys.exc_traceback.tb_lineno)

print s

5.3.1.2 Preprocesarea textelor care compun corpul email-urilor

Au fost mai intai eliminate duplicatele, apoi textele email-urilor au suferit mai multe transformari, prin aplicarea urmatoarelor tehnici.

(1) tokenizarea – ajuta la identificarea cuvintelor si expresilor prin separarea acestora prin intermediul unor delimitatori precum spatiul sau alte semne de punctuatie precum „!”, „?”, 959f59j „.” etc.

(2) eliminarea cuvintelor irelevante – proces in care cuvintele irelevante(stopwords) sunt eliminate din text pentru a nu participa la etapa de indexare. Cateva exemple de astfel de cuvinte pentru limba romana ar fi „cum”, „despre”, asadar”.

(3) stemming – in aceasta faza cuvintele sunt inlocuite cu radacinile acestora, cuvantul obtinut prin eliminarea sufixelor si prefixelor.

(1) In prima faza textul email este divizat in cuvinte prin utilizarea anumitor delimitatori. In urma procesului de tokenizare documentul este reprezentat de un set de termeni, termeni care sunt mai mult sau mai putin importanti. Unii dintre delimitatorii utilizati sunt „?”, „.”, „,”, „<”, etc. Acest lucru il realizeaza urmatoarea functie, utilizand wordpunct_tokenize din libraria NLTK dupa ce in prealabil sa mai fac unele procesari cu ajutorul expresiilor regulate :

def get_msg_words(msg,strip_html, stopwords=[]):

msg=str(msg)

msg_words=[]

try:

# Strip out weird '3D' artefacts.

msg = re.sub('3D', '', msg)

# Strip out html tags and attributes and html character codes,

# like &nbsp; and &lt;.

if strip_html:

msg = re.sub('<(.|\n)*?>', ' ', msg)

msg = re.sub('&\w+;', ' ', msg)

msg = re.sub('_+', '_', msg)

# Note, remove '=' symbols before tokenizing, since these are

# sometimes occur within words to indicate, e.g., line-wrapping.

msg_words = set(wordpunct_tokenize(msg.replace('=\n', '').lower()))

# Get rid of stopwords

msg_words = msg_words.difference(stopwords)

# Get rid of punctuation tokens, numbers, and single letters.

msg_words = [w for w in msg_words if re.search('[a-zA-Z]', w) and len(w) > 1]

except Exception as e:

s = str(e)+' '+str(sys.exc_traceback.tb_lineno)

print s

return msg_words

(2) In aceasta etapa de preprocesare cuvintele considerate irelevante, care nu contin nici o informatie despre continutul documentului, spre exemplu „and”, „what”, „to”, sunt cuvinte care, desi apar frecvent, nu ne prezinta nici o informatie. Aplicatia de fata utilizează lista de stopwords oferita de NLTK:

„ from nltk.corpus import stopwords”

lista, care a fost imbunatatita ulterior cu inca cateva stopwords.

Pentru a fi disponibila si local a fost necesar mai intai downloadarea si instalarea ei prin :

import nltk

nltk.download()

asa cum poate fi vazut si in imaginea de mai jos:

Figura 5.2 NLTK download

5.3.2 Construirea, antrenarea si testarea modelului

In aceasta etapa fiecare document este reprezentat de un set de termeni, carora li se asociaza o pondere(weight), in functie de gradul de discriminare pe care il are acel cuvant. Astfel dupa etapa de preprocesare se construieste vocabularul de termeni ai colectiei de documente reprezentand corpul emailurilor, care contine toti termenii cheie din toate documentele care urmeaza a fi grupate.

Am optat pentru 40 cei mai relevanti termeni, care pot fi urmariti in lista de mai jos, impreuna cu ponderile asociate fiecarei clase:

Most Informative Features:

department = True ham : spam = 56.7 : 1.0

click = True spam : ham = 56.6 : 1.0

reference = True ham : spam = 55.2 : 1.0

analysis = True ham : spam = 53.7 : 1.0

submit = True ham : spam = 48.4 : 1.0

title = True ham : spam = 46.8 : 1.0

field = True ham : spam = 45.3 : 1.0

state = True ham : spam = 43.8 : 1.0

details = True spam : ham = 43.5 : 1.0

fax = True ham : spam = 42.6 : 1.0

auto = True spam : ham = 41.7 : 1.0

aspect = True ham : spam = 41.5 : 1.0

institute = True ham : spam = 40.0 : 1.0

call = True ham : spam = 39.0 : 1.0

consider = True ham : spam = 36.2 : 1.0

making = True spam : ham = 35.3 : 1.0

serif = True spam : ham = 34.7 : 1.0

sent = True spam : ham = 34.7 : 1.0

germany = True ham : spam = 34.7 : 1.0

area = True ham : spam = 33.1 : 1.0

acquisition = True ham : spam = 32.4 : 1.0

tr = True spam : ham = 31.8 : 1.0

process = True ham : spam = 31.8 : 1.0

result = True ham : spam = 31.6 : 1.0

web = True ham : spam = 29.9 : 1.0

whether = True ham : spam = 29.3 : 1.0

recent = True ham : spam = 28.6 : 1.0

study = True ham : spam = 27.9 : 1.0

major = True ham : spam = 27.0 : 1.0

due = True ham : spam = 27.0 : 1.0

rather = True ham : spam = 27.0 : 1.0

require = True ham : spam = 26.3 : 1.0

material = True ham : spam = 26.3 : 1.0

color = True spam : ham = 26.1 : 1.0

present = True ham : spam = 25.9 : 1.0

project = True ham : spam = 25.5 : 1.0

appear = True ham : spam = 25.5 : 1.0

lead = True ham : spam = 24.0 : 1.0

question = True ham : spam = 23.5 : 1.0

interest = True ham : spam = 23.4 : 1.0

Aceastea au fost realizati cu ajutorul functiilor:

def features_from_messages(messages, label, feature_extractor, sw, strip_html):

features_labels = []

for msg in messages:

features = feature_extractor(msg, sw, strip_html)

features_labels.append((features, label))

return features_labels

Fiind un algoritm supervizat a fost necesar creerea unui dictionar de intrari care sa marcheze fiecare termen carei clase apartine:

def word_indicator(msg, sw, strip_html):

features = defaultdict(list)

msg_words = get_msg_words(msg,strip_html, sw)

for w in msg_words:

features[w] = True

return features

Antrenarea si evaluarea clasificatorului Naive Bayes se face in urmatoarele linii de cod:

strip_html=False

check_classifier(word_indicator,sw, strip_html,train_spam_messages,test_spam_messages,train_ham_messages,test_ham_messages)

#without the HTML tags and information

strip_html = True

check_classifier(word_indicator, sw, strip_html,train_spam_messages,test_spam_messages,train_ham_messages,test_ham_messages)

iar codul asociat functiei este:

def check_classifier(feature_extractor,sw, strip_html, train_spam_messages,test_spam_messages,train_ham_messages,test_ham_messages):

# Make training and testing sets of (features, label) data

try:

train_spam = features_from_messages(train_spam_messages, 'spam', feature_extractor, sw, strip_html)

train_ham = features_from_messages(train_ham_messages, 'ham', feature_extractor, sw, strip_html)

train_set = train_spam + train_ham

test_spam = features_from_messages(test_spam_messages, 'spam', feature_extractor, sw, strip_html)

test_ham = features_from_messages(test_ham_messages, 'ham',feature_extractor, sw, strip_html)

# Train the classifier on the training set

classifier = NaiveBayesClassifier.train(train_set)

# How accurate is the classifier on the test sets?

print ('Test Spam accuracy: {0:.2f}%'

.format(100 * nltk.classify.accuracy(classifier, test_spam)))

print ('Test Ham accuracy: {0:.2f}%'

.format(100 * nltk.classify.accuracy(classifier, test_ham)))

# Show the top 40 informative features

print classifier.show_most_informative_features(40)

except Exception as e:

s = str(e)+' '+str(sys.exc_traceback.tb_lineno)

print s

Acuratetea modelului implementat cu algoritmul Naive Bayes este data de indicatorii:

Test Spam accuracy: 99.23%

Test Ham accuracy: 96.92%

Spam precision: 0.96992481203

Spam recall: 0.992307692308

Spam F-measure: 0.980988593156

Ham precision: 0.992125984252

Ham recall: 0.969230769231

Ham F-measure: 0.980544747082

Pe acelasi principiu am construit un model bazat pe clasificatorul SVM ( Support Vector Machines):

classifierSVM = SklearnClassifier(LinearSVC())

classifierSVM.train(train_set)

# How accurate is the classifier on the test sets?

print ('Test Spam accuracy with SVM: {0:.2f}%'

.format(100 * nltk.classify.accuracy(classifierSVM, test_spam)))

print ('Test Ham accuracy with SVM: {0:.2f}%'

.format(100 * nltk.classify.accuracy(classifierSVM, test_ham)))

print ('Verificarea clasificatorului SVM:')

referenceSetsSVM=defaultdict(set)

testSetsSVM=defaultdict(set)

for i, (feature,label) in enumerate(test_features):

referenceSetsSVM[label].add(i )

predictedSVM=classifierSVM.classify(feature)

testSetsSVM[predictedSVM].add(i)

print 'train on %d instances, test on %d instances' % (len(train_set ), len(test_features))

print 'Spam precision:', nltk.metrics.precision(referenceSetsSVM['spam'], testSetsSVM['spam'])

print 'Spam recall:', nltk.metrics.recall(referenceSetsSVM['spam'], testSetsSVM['spam'])

print 'Spam F-measure:', nltk.metrics.f_measure(referenceSetsSVM['spam'], testSetsSVM['spam'])

print 'Ham precision:', nltk.metrics.precision(referenceSetsSVM['ham'], testSetsSVM['ham'])

print 'Ham recall:', nltk.metrics.recall(referenceSetsSVM['ham'], testSetsSVM['ham'])

print 'Ham F-measure:', nltk.metrics.f_measure(referenceSetsSVM['ham'], testSetsSVM['ham'])

Rezultatele rularii codului de mai sus sunt concretizate in indicatorii urmatori, care se refera la acuratetea modelului, specificitatea si sensitivitatea modelului atat in detectarea emailurilor de tip spam cat si de tip ham:

Test Spam accuracy with SVM: 100.00%

Test Ham accuracy with SVM: 99.23%

Verificarea clasificatorului SVM:

Test on 960 instances

Spam precision: 0.992366412214

Spam recall: 1.0

Spam F-measure: 0.996168582375

Ham precision: 1.0

Ham recall: 0.992307692308

Ham F-measure: 0.996138996139

Din compararea rezultatelor celor doua modele reiese faptul ca clasificatorul SVM are o acuratate si precizie mai mare, chiar de 100% in cazul email-urilor de tip ham. Dar aici e posibil totusi sa existe o marja de eroare, pe care n-am reusit sa o identific inca cu exactitate.

5.3.3 Aplicarea modelului pe date noi

In aceasta etapa se va aplica modelul pe date noi, se va analiza acuratetea modelului pe aceste date si se va decide pentru fiecare caz in parte daca va intra sau nu in setul de antrenare sau nu.

Rularea modelului pe alte date decat cele din setul de antrenare a efectuat-o pe setul de date crawlate din conturile personale de email (in special yahoo) din folderul spam. Se poate observa mai jos ca acuratetea modelului se pastreaza aproximativ la aceeasi parametrii, inregistrandu-se indicatori chiar mai buni in ceea ce priveste sensitivitatea (recall) si precizia:

Test Spam accuracy with test mysql set: 99.23%

Verificarea clasificatorului Naive Bayes pe setul de date Mysql

train on 700 instances, test on 260 instances

Spam precision pe setul de date Mysql: 1.0

Spam recall pe setul de date Mysql: 0.992307692308

Spam F-measure pe setul de date Mysql: 0.996138996139

5.4 Vizualizarea datelor

Se va face cu ajutorul librariei matplotlib.

Figura 5.3 Exemplu de vizualizare a modelului[21]

5.5 Instalarea pachetelor necesare

Pentru a putea importa si accesa fara erori clasele specifice clasificatorului Naive Bayes:

from pandas import *

import numpy as np

import re

import nltk

from nltk import NaiveBayesClassifier

import nltk.classify

from nltk.tokenize import wordpunct_tokenize

from nltk.corpus import stopwords

from collections import defaultdict

am utilizat pachetul miniconda (http://conda.pydata.org/miniconda.html), care contine: un manager de pachete de la conda si Python. Am utilizat versiunea pentru python 2.7.

Odata ce miniconda a fost instalat, utilitarul ofera posibilitatea de a instala prin conda command orice alt pachet sau creea medii de dezvoltare specifice acestuia. De exemplu: $conda install numpy

$ conda create -n py3k anaconda python=3

conda create -n myenv python [18]

Concluzii

O data cu dezvoltarea soluțiilor IT și extinderea retelelor de internet s-a trecut de la poșta/comunicarea clasica(pe hârtie) la poșta electronica/ comunicarea in format digital în aproape toate domeniile, iar cum de fiecare dată când se realizează un lucru bun există și indivizi care vor să profite în interes personal în detrimentul altora, nici domeniul poștei electronice/ email nu a rămas neatins de cei care au căutat breșe pentru a utiliza poșta electronică în alte scopuri decât cel care a fost creat.

Mesajele spam aduc mereu un disconfort utilizatorului care își găsește mereu căsuța poștală electronică plină cu mesaje nedorite, iar pe lăngă ”nevinovatele” mesajele spam publicitare sunt foarte multe periculoase/dăunătoare (mai ales pentru utilizatorii neexperimentați/neatenți), cu ajutorul lor se pot receptiona virusi, viermi, cai troieni, etc., dar si periculoasele atacuri phishing care pot aduce mari prejudicii materiale.

Pe de altă parte mesajele electronice nesolicitate primite de o companie pot reprezenta conform unor statistici chiar peste 60 % din totalul e-mail-urilor. De aceea, spamul costă spațiu de stocare pe servere e-mail, trafic intern suplimentar pentru livrarea lor către angajați(mai ales daca sunt in cadrul companiei si alias-uri), precum și timpul de lucru al destinatarilor. În medie, fiecare utilizator poate pierde chiar și 50 de minute pe zi pentru a verifica, sorta și șterge mesajele nesolicitate. Astfel, pierderile provocate de spam la nivel mondial se estimează conform statisticilor la 81,2 miliarde de dolari anual. În România, unde există peste 13 milioane de utilizatori Internet, pagubele provocate de spam se cifrează la circa 270 milioane de dolari pe an, conform unor date furnizate de către Ministerul Comunicațiilor și Tehnologiilor Informaționale.

Având în vedere cele enumerate mai sus rămâne in sarcina dezvoltatorilor de soluții software găsirea unei soluții optime pentru a filtra/bloca spam-urile. Pe lângă întocmirea de liste cu adresele de unde vin spam-uri, blocarea adreselor IP, crearea de baze de date în care să fie stocate mesaje de tip spam pentru a putea compara eventuale noi mesaje de tip spam pentru a fi blocate, o soluție ar putea fi implementată pe baza unui sistem Machine Learning care să ”învețe”, să clasifice/diferențieze mesajele de tip spam versus non-spam pe baza informațiilor din ierarhia de foldere a utilizatorilor fără a mai fi nevoie de o bază de date de antrenament care să conțină deja mesaje de tip spam

Bibliografie

[1] – http://www.asociatia-profesorilor.ro/tehnici-de-explorare-a-textului-in-cadrul-sistemelor- de-invatare.html

[2] – http://www.revistaie.ase.ro/content/27/militaru.pdf

[3] – http://ro.wikipedia.org/wiki/Inteligen%C8%9B%C4%83_artificial%C4%83

[4] – http://software.ucv.ro/~cbadica/ai/cap1.pdf

[5] –   IOA N DZIȚAC – Inteligența artificială – Editura Universității ”Aurel Vlaicu”, Arad, 2008

[6] – Florin Leon – Inteligenta artificiala: rationament probabilistic, tehnici de clasificare, Tehnopress, Iasi, 2012

[7] http://www.academia.edu/4424156/O_imbunatatire_a_performantelor_algoritmului_KNN _in_sistemele_de_recomandare_pe_web

[8] -Ionel Daniel MORARIU – Contribuții la extragerea automată de cunoștințe din masive de date, Teză de doctorat, 2007

[9] – http://www.jetbrains.com/pycharm/

[10] – http://en.wikipedia.org/wiki/PyCharm

[11] – http://cs.curs.pub.ro/wiki/asc/asc:lab1:index

[12] – http://ro.wikipedia.org/wiki/Python

[13] – Guido van Rossum, Fred L. Drake, Jr., editor –

Tutorial Python -Versiune 2.2

[14] – http://users.utcluj.ro/~nedevski/PR/labs/prs_lab_08r.pdf

[15] – Raul ROBU- Contribu ii la îmbunătă irea tehnologiei

de clasificare a datelor

[16] – http://en.wikipedia.org/wiki/SpamAssassin

[17] – http://spamassassin.apache.org

[18] – http://conda.pydata.org/miniconda.html

[19] – http://sebastianraschka.com/Articles/2014_install_python_sci_pkgs.html

[20] – http://ro.wikipedia.org/wiki/Spam

[21]- http://www.sersc.org/journals/IJHIT/vol6_no1_2013/5.pdf

[22]-http://openclassroom.stanford.edu/MainFolder/DocumentPage.php?course=MachineLearning&doc=exercises/ex6/ex6.html

[23] – http://nlp.stanford.edu/IR-book/html/htmledition/support-vector-machines-the-linearly-separable-case-1.html

Anexa nr.1

(Sursa: http://www.spamcop.net/spamgraph.shtml?spamyear)