Algoritmul de Categorisire al Site Urilor

Categorisire site-uri

CUPRINS

Capitolul I. Introducere

Algoritmul de categorisire site-uri este un altoritm de optimizare SEO. Motoarele de cautare folosesc în spate un algoritm care necesita un sistem hardware foarte complex și foarte mare, de dimensiunile unei cladiri, care consuma foarte multa energie electrica, depistand aceste probleme, de spatiu și de consum electric am încercat să gasesc o optimizare. Optimizarea propusă de mine este diminuarea ariei de cautare.

Optrimizarea consta în crearea unor baze de date uriase cu site-uri, în care fiecare site saă fie categorisit.Exemplu: https://www.uoradea.ro v-a fi cotegorisit în categoria „Educație”, iar daca voi cauta în motor de cautare folosind cuvântul „universitate” , motorul de cautare nu v-a fi nevoit să verifice tot continutul site-ului pentru a returna site-ul https://www.uoradea.ro deoarece cuvântul „universitate” se află în componența câmpului gramatical al categoriei „Educație”.

Algoritmul de categorisire nu are interfata pentru utilizatori deoarece nu este destinat utilizatorilor finali, pentru rulare se va folosi linia de comandă, este scris în Python 2.7 ,C# și SQL, va rula pe sitemele de operare Windows NT iar sistemele hardware compatibile vor fi x86 și amd64. Pentru scrierea codului am folosit urmatoarele editoare de text: Microsoft VisualStudio 2013 pemtru limbajele C# și Python, dbForge pentru SQL. Baza de date utilizată a fost MySQL pentru a memora pe suport fizic categoriile și campul lexical al fiecarei categorii.

Algoritmul de categorisire este compus din 3 mari module: primul modul este modulul de luare a paginii sursă a site-ului și curațarea lui de coduri html,php, și a altor limbaje de programare.Al doilea modul se referă la calcularea unuei ponderi a fiecarui cuvânt din textul curațat, în funcție de forma gramaticală daca este gazul. În ultimul modul se calculează categoria site-ului din care face parte folosind algoritmul NaiveBayes. Fiecare din aceste module vor fi detailate în aceast proiect.

Capitolul II . Tehnologii utilizate

II.1 Python

Python este un limbaj de programare dinamic multi-paradigmă, creat în 1989 de programatorul olandez Guido van Rossum. Python este un limbaj usor de folosit, nu necesita declararea de variabile, acestea fiind declarate la instantierea lor, se poate schimba tipul lor în orice moment vrea programatorul.Un dezavantaj este ca folosește un interpretor și nu un compilator in timp real, de aceea este mai lent decât multe limbaje, dar ca și un avantaj în utilizarea lui este ca are multe module gata create cum ar fi NumPy, ScyPy, NTLK .Python a ajuns la versiunea 3.4 care este mult mai rapida decât versiunea anterioara 2.7 dar se folosesc ambele deoarece forte multe librarii sunt scrise în Python 2.7. Python 2.7 va primii actualizari până în anuii 2015-2016, urmând să fie inlocuit complet cu Python 3.x.

Python are ca și compilator CPython care interpreteaza codul și il compileaza.In anul 2002 se lanseaza PyPy care este un compilator în timp real pentru Python, astfel Python ruleaza aproximativ cu aceasi viteza ca și alte limbaje precum C++,JAVA sau limbajede pe platforma .NET.

O altenativa a utilizarii PyPy este utilizarea unui traslator care să traducă din Python în C/C++. Un avantaj al acestei metode este timpul de programare și neinplicarea în tratarea eruarilor care vor fi tratate automat de catre translator.

Scrierea de programe în limbajul Python este foarte usor, având foarte puține cuvinte cheie, dar te obliga să fii ordonat în cod altfel apar eruari de scriere. Un exemplu al unei declaratii decizionale, „If” unde se vrea ca un anumit cod să se execute în interiorul unui If , astfel codul se va scrie cu un tab mai la dreapta.

Aceste limbaj face diferența dintre litere mari și litere mici, de aceea având doua variabile cu același nume dar o variabilă scrisă cu litere mari și alta cu litere mici, rezulta doua variabile distincte.

Corect:

if var == 200:

print "1 – Got a true expression value"

print var

Fig 1.1 cod Python corect

Gresit:

if var == 200:

print "1 – Got a true expression value"

print var

Fig 1.2 cod Python gresit

Atomi utilizate în Python:

Atomul „If” care în orice limbaj este o declarative decizionala, care executa codul doar daca expresia din condiție este adevarată, este folosit împreuna cu atomii else și elif care este o prescurtare a condiției else if.

if var == 200:

print "1 – Got a true expression value"

print var

Fig 1.3 cod Python

Atomul „for” este folosit pentru a parcurge o iterație, fiecare element al iterației va fi înregistrat într-o variabilă. Iar acea variabilă va fi utilizată în codul din dreapta for-ului.

for letter în 'Python': # First Example

print 'Current Letter :', letter

Fig 1.4 cod Python

Atomul „while” execută un bloc de cod atât timp cât o condiție este adevarată

while (count < 9):

print 'The count is:', count

Fig 1.5 cod Python

Cuvintele cheie „try”, „except ” și „finally ” sunt folosite pentru a captura eruarile apărute în cod și pentru a trata aceste eruari.

try:

fh = open("testfile", "w")

fh.write("This is my test file for exception handling!!")

except IOError:

print "Error: can\'t find file or read data"

Fig 1.6 cod Python

Atomul def se referă la definirea unei funcții sau a unei metode.Acea funcție poate să returneze orice tip de date sau să returneze nimic, fără a specifica în prototipul funcției.

def printme( str ):

"This prints a passed string into this function"

print str

Fig 1.7 cod Python

Tipuri de date utilizare în Python:

Tlpul str este folosit pentru a memora siruri de caractere, respectiv pagina sursă a site-ului.

Exemplu : 'Wikipedia',

"Wikipedia",

"""Spanning
multiple
lines"""

Tipul list este o insiruire de date de același fel sau diferite, iar parcurgerea se face element cu element.

Exemplu: [4.0, 'string', True]

Tipul dict este o lista indexată dupa anumita cheie, dict este compus din cheie și valoare, iar pentru indexare se folosește o tabela de hashing.Acest tip este util pentru a găsi cel mai repede anumite elemete.

Exemplu: {'key1': 1.0, 3: False}

Tipurile int,float sunt folosit pentru a memora numere intregi respectiv numere reale.

Exemplu: 42, 123.25

In algoritmul de categorisire se folosesc toate cuvintele cheie prezentate și toate tipurile prezentate. Ca și compilator se folosește CPython, deoarece anumite module folosite nu sunt compatibile cu PyPy.Limbajul Python se folosește pentru găsi formele gramaticale cuvintelor din propozitii, gasirea formelor gramaticale se va explica în aceast proiect, și pentru a calcula categoria site-ului de care aparține.

II.2 C# și .NET

Limbajul C# este un limbaj modern, orientat pe obiecte, având o sintaxă asemănătoare cu cea din C/C++ și Java, care permite programatorilor să construiască rapid o varietate largă de aplicații pentru platforma Microsoft .Net, platformă care asigură instrumente și servicii pentru exploatarea sistemelor informațice și comunicațiilor.

Datorită designului elegant orientat pe obiecte, C# este o alegere bună pentru conceperea a variate componente – de la aplicații la nivel de sistem și până la realizarea aplicațiilor comerciale de nivel ridicat.

Unul dintre scopurile limbajului este acela de a simplifica programarea orientată pe componente. Prin componentă se înțelege un ansamblu de clase de obiecte care interacționează pentru a îndeplini anumite funcționalităti.

C# a fost proiectat în paralel cu platforma .NET realizată de către Microsoft și, de aceea, partajează cu aceasta un număr însemnat de caracteristici. De exemplu, oricât de surprinzător ar parea, toate tipurile de date (chiar și celelalte variabile cum ar fi int sau struct) au o clasă de bază comună, object. De aceea spunem despre această platformă că are un sistem unificat de tipuri.

Alte caracteristici, care aparțin în egală măsură limbajului și platformei sunt:

– utilizarea excepțiilor pentru semnalarea și tratarea erorilor,

– managementul automat al memoriei – memoria este alocată explicit de către programator, dar dealocată de sistem când acesta consideră că este cazul

– suportul pentru versiuni ale codului – codul se schimbă în timp ca urmare a cerințelor care se modifică permanent, și în .NET această problemă este tratată corespunzător.

C# este un limbaj simplu cu aproximativ 80 de cuvinte cheie, are 12 tipuri de date predefinite. Acesta permite programarea modulară, ștructurală și orientată pe obiecte și încoporeaza încapsularea, moștenirea și polimorfismul, acestea fiind principiile de bază ale C#-ului.

Sintaxă și principiile de programare rămând aproximativ aceleașî cu cele din C++, apar însă câteva tipuri de date noi.

O aplicație C# este formată din una sau mai multe clase, grupate în „spații de nume” numite namspaces. Un namespace poate conține mai multe clase, cu nume diferite, dar cu funcționalități diferite. Pot apărea clase cu același nume, condițiia fiind ca ele să nu fie definite în același namespace.

În cadrul unui spațiu de nume, poate fi definit un alt spațiu de nume, acesta fiind un spațiu de nume imbricat.

O clasă se identifică prin numele complet, adică numele propriu prefixat cu spațiul de nume unde este declarată, cele doua cuvinte fiind desparțite prin punct „.”. O clasă este formată din date și metode, sau funcții.

În cazul unei aplicații complexe, care trebuie partajată, C# ofera posibilitatea segmentării în mai multe fișiere numite „assemblies”. Într-un assembly se pot implementa spații de nume.

Este obligatoriu ca doar și numai o singură clasă să conțina un punct de intrare, adică metoda Main.

C# a fost proiectat pe ideea ca sistemele moderne sunt construite din componente, furnizând suport direct pentru construcții de componente uzuale, permite extinderea componentelor în vederea reutilizării și a distribuirii. Nu mai folosește fișiere header și biblioteci speciale ca și C++.

Construcțiile noi din cadrul C# sunt delegați – echivalentul pointerilor la funcții și atribute custom, care permit notarea elementelor de cod cu informații aditionale

Păstrează facilitățiile din C++ precum: suprascrierea operatorilor, conversii utilizator și transmiterea prin referință.

Spre deosebire de majoritatea limbajelor de programare, C# nu are o biblioteca runtime proprie, ci folosește bibliotecile oferite de .NET Framework pentru abslout toate facilitățile necesare.

Algoritmul de clasificare folosește platforma .NET și limbajul C# pentru a extrage pagina sursă a site-ului și curațarea paginii de textul nedorit, se va explica mai în detailat în aceast proiect ce inseamna curațarea textului nedorit. Principalele librarii folosite din platforma .NET sunt „System.Net” pentru a comunica cu internetul și a lua pagina sursă a site-ului și „System.IO” care

convertește textul în tipul string de pe platform .NET.

II.3 SQL

SQL (Structured Query Language – Limbaj Structurat de Interogare) este un limbaj de programare specific pentru manipularea datelor în sistemele de manipulare a bazelor de date relaționale (RDBMS), iar la origine este un limbaj bazat pe algebra relațională.  A devenit un standard în domeniu fiind cel mai popular limbaj utilizat pentru creearea, modificarea, regăsirea și manipularea datelor de către sistemele de gestiune a bazelor de date relaționale.

Limbajul Sql este împartit în doua mari parți :

Data Definition Language (DDL)  sau un limbaj care manipulează structura de memorare a datelor, de exemplu baza da date, tabela, trigger, wiev.

Principalele comenzi din DDL sunt:

Create – comandă pentru a crea tabele, baze de date sau alte obiecte

CREATE TABLE nume_tabela

(coloana1 tip_data(dimensiune),

coloana2 tip_data(dimensiune),

coloana3 tip_data(dimensiune),

…

);

Alter – comandă pentru a modifica structura unei baze de date

ALTER TABLE tabel RENAME TO nume_nou_tabel;

Drop – comandă pentru a șterge un obiect din baza din baza de date

Drop Table table1;

Truncate – șterge toate liniile dintr-o tabela inclusiv spatiul alocat și neutilizat.

Truncate Table table1;

Data Manipulation Language (DML) este un limbaj care manipulează datele din baza de date.

Principalele comenzi DML sunt:

SELECT – comandă care se folosește pentru a extrage date din baza de date dupa anumite criterii daca este cazul , ordonate dupa un criteriu

INSERT – comandă pentru a insera date într-o tabela

UPDATE – comandă pemtru a modifica date deja existente în baza de date

DELETE – comandă pentru a șterge date din baza de date

CALL – comandă care executa un anumit subprogram creat în PL/SQL sau Java sau o procedura

Pentru a putea face legatura intre mai multe tabele se folosește Join care poate fi de mai multe feluri:

Inner Join – face legatura între elementele comune dintre cele doua tabele

Left Join – returnează toate elementele din tabela din partea stângă a join-ului și elemetele commune din tabela din partea dreaptă cu tabela din partea stângă a join-ului

Right Join – returnează toate elementele din tabela din partea dreapta a join-ului și elemetele commune din tabela din partea stângă cu tabela din partea dreaptă a join-ului

Outer Join – returnează toate elementele necomune dintre cele doua tabele

Exemplu de extragere a datelor dintre doua tabele, folosind join și comandă select și grupate dupa un anumit criteriu:

SELECT Book.title, Authors.name

FROM Book

INNER JOIN Authors

ON Book.author = Authors.id

GROUP BY Book.title;

Programul de clasificare folosește ca și baza de date MySql pentru ca are licenta gratisa, și este una dintre cele mai utilizate baze de date.

II.3.1 MySQL

Mysql este un system de gestiune a bazelor de date relationale(SGDB) , fiind una dintre cele mai utilizate SGDB. MySQL nu conține interfață grafică pentru administrarea sau gestionarea datelor din bazele de date. Utilizatorii pot folosi instrumente de linie de comandă, aplicații desktop sau aplicații web cu care se pot administra și crea baze de date MySQL.

Bazele de date MySQL, ca și alte tipuri de baze de date sunt compuse din tabele oarecum separate, acestea conțin diferite câmpuri de date corelate din punct de vedere logic. Bazele de date pot avea dimensiuni variate, de la câteva zeci de înregistrări și pot ajunge la ordinul de milioane de înregistrări.

Utilizatorii unei baze de date pot efectua mai multe operații asupra datelor:

Inserarea de date (insert)

Ștergerea de date (delete)

Modificarea datelor (update)

Citirea bazei de date (query) pentru a extrage anumite date

Bazele de date relaționale sunt de departe cel mai folosit tip de baze de date. Acestea au o bază teoretică solidă în algebra relațională.

II.4 NLTK

NLTK este o platforma de librării și programe folosite în inteligență artificială, fiind scris în Python.

Programul de categporisire folosește din aceasta platforma urmatoarele module: NLTK Grammar pentru a gasii parțile gramaticale dintr-o propozitie, și NLTK Tokenizer care împarte un text în atomi de cuvinte .

II.4.1 NLTK Tokenizer

NLTK Tokenizer este o funcție care împarte un text în propozitii și construieste un model matematic pentru a identifica parțile gramaticale a propozițiilor folosind abrevierile cuvintelor, cuvintele de inceput a propozitiilor.Aceasta funcție are la baza un algoritm de inteligență artificială și anume un algoritm nesupravegheat .

Exemplu de utilizare a NLTK Tokenizer:

>>> from nltk.tokenize import TreebankWordTokenizer

>>> s = "Exemplu de impartire sub forma de tokens."

>>> TreebankWordTokenizer().tokenize(s)

['Exemplu', ’de’, 'impartire', 'sub', 'forma', 'de','tokens', '.']

Un algoritm nesupravegheat reprezintă un algoritm care încearca să gasească un model matematic folosind date de intrare corecte. Datele de intrare trebuiesc să fie de o acuratețe mare pentru a evita eruarile sau să se diminueze situațiile de fals pozitiv, adica aparține modelului matematic dar la o analiza mai atentă nu face parte din model. Algoritmul nesupravegheat este inrudit cu algoritmul de estimare a densitatii din statistica.

Algoritmul nesupravegheat are la baza o retea neuronala care este antrenata de catre datele introduse la început.

Exemplu de algoritm nesupravegheat:

Pentru început se primesc datele de intrare și se calculează o distanta Euclidiana intre doua date de intrare

Fig Fig 4.1 Exemplu clasificare

In pasul urmator urmator incep să se formeze grupuri de date în jurul fiecarei date esalon aleasă în pasul precedent.

Fig 4.2 Exemplu clasificare

In ultima parte parte se definesc grupele finale de date in jurul datelor esalon, chiar daca anumite date nu mai apar în grupele finale modelul final este correct doearece acele date sunt date neglijabile.

II.4.2 NLTK Grammar

NLTK Grammar este un algoritm de identificare a parților gramaticale dintr-o propoziție și creeaza arborele sintactic al propoziției. În arborele sintactic al propozitiei fiecare cuvânt reprezintă o frunză din arbore iar nodul este partea gramaticală. Fiecare parte gramaticală este prescurtata intr-un anumit mod,prescuratrile vin din limba engleza :

Tabel 4.1

. Construirea arborelui sintactic folosește regulile de gramataci în care am producții și simboluri.Simbolurile sunt definite în tabelul anterior (Tabel 4.2.1), iar ca simbol de start se alege simbolul “S” sau rădăcina , iar ca și producții avem predefinite în funcția de creere a arborelui cateva producții, sau se pot scrie de utilizatori.

Exemplu de producție predefinită:

“<S> -> <NP> <VP>” care reprezintă faptul ca din rădăcina putem avea substantiv propriu și verb.

Productia este compusă din doua parti: partea dreaptă și partea stângă despartite prin simbolul “->”. În partea stângă a producției se află numele structurii gramaticale pe care o poate avea în propoziție o anumită structura de text. Partea dreaptă de text reprezintă parțile gramaticale din care partea stânga poate fi alcatuită.

Algoritmul de creere a arborelui grammatical are urmatoarele proceduri:

Se setează simbolul de start al arborelui. Se selectează o producție care are partea stângă a producției formată din mai mult de un cuvânt și se înlocuieste cu un subarbore la care sa identificat fiecare cuvânt ce parte gramaticală are. Aceasta operațiune se repeată atâta timp cât toate cuvintele din text sunt folosite.

Etapele algoritmului în mod ilustrat:

Fig 4.4 Exemplu rulare algoritm de detectare a gramaticii

Fig 4.5 Exemplu rulare algoritm de detectare a gramaticii

Fig 4.6 Exemplu rulare algoritm de detectare a gramaticii

Exemplu de folosire a NLTK Grammar utilizand Python :

Fig 4.7 cod Python

Iar arborele de gramatica este:

Fig 4.8 Arbore de gramatica

II4.2 NaiveBayes

Naive Bayes este un algoritm de clasificare probabilistica. Este construit pornind de la datele de antrenare pentru a estima probabilitatea fiecarei clase, fiind date valorile caracteristicilor documentului pentru o noua instanta. Teorema lui Bayes este folosita pentru a estima aceste probabilitați. Lucreaza bine chiar și atunci cand nu este indeplinita condiția de independenta a caracteristicilor presupusă de Naive Bayes. Se bazeaza pe simplificarea supozițiilor (independenta conditionala a cuvintelor).

II4.2.1 NaiveBayes Teorie

Fie Y o variabilă pentru o categorie care este formată din multimea {y1, y2, …, ym}.

Fie X o instanță a unui vector cu n atribute <X1, X2, …, Xn> și xk o valoare posibilă

pentru X și xki o valoare posibilă pentru xk. Pentru clasificarea de tip Bayes calculăm

probabilitățile P ( Y = yi | X = xi ) pentru i care ia volori între 1 și m , ceea ce reprezintă calcularea tuturor posibilitaților pentru o categorie pentru fiecare instanta posibila din spatial de instante.

Formula de calculare a probabilitaților:

Deoarece categoriile sunt complementare și disjuncte iar probabilitatea poate fi usor determinata rezulta urmatoarea formula :

De unde se duduce formula finala :

Probabilitatea P ( X = xk | Y= yi ) trebuie estimată (deoarece există 2n posibile instanțe pentru a calcula probabilitatea). De aceea, dacă presupunem că atributele unei instanțe sunt independente una fața de alta , rezulta urmatoarea formula:

Din formula se deduca ca va trebui să calculăm fiecare posibilitate pereche "valoare atribut" -"categorie" , iar daca Y și Xi sunt binare se presupune ca atributele sunt idependente de unde rezulta ca va trebui să se calculeze doar 2n valori fata de 2n. .

Daca avem un set de date de intrare A care contine nk exemple din categoria yk și nijk , din exemplele nk rezulta ca au a j-a valoare pentru atributul Xi pe xij, de unde se duduce formula :

Aplicand aceasta formulă pe un set de date restrâns vor aparea eruari deoarece va face ca Xi să fie fals în setul de antrenament P ( Xi = true | Y = yk) =0 unde yk poate să aiba orice valoare.

Pentru a evita aceste situții se folosește uniformizarea Laplace care presupune ca fiecare atribut are probabilitatea p într-un exemplu virtual de dimensiune m, și rezulta formula :

Iar p este o constantă, care poate să aiba de exemplu valoarea p=0,5

II4.2.1 NaiveBayes exemplu de clasificare:

Se presupune ca avem anumite date de intrare iar reprezentarea lor grafică într-un plan este urmatoarea :

Bulinele cu roșu reprezintă un anumit tip de date iar cele reprezentate cu verde alt tip de date.Pe baza datelor existente trebuie să clasificam noi date. Deoarece exista mai multe date reprezentate cu verde fata de cele reprezentate cu roșu , este normal să presupunem ca un nou exemplu, care nu a fost inca observat, are mai multe șanse să fie verde decât roșu . Aceasta este probabilitatea “prior”. Probabilitatile prior se bazeaza pe experiența anterioara.

Se calculează care este probabilitatea ca o data noua să fie roșu sau verde cu urmatoarea formula: numar de cazuri existente impartit la numarul total de cazuri, astfel să presupune ca probabilitatea pentru verde este de 130 (cazuri existente) împartit la 200 cazuri în total iar pentru roșu vom avea 70 împartir la 200, acesata fiind probabilitatea “prior”.

In acest moment se introduce o noua data care va trebui să fie clasificata, iar procedura de clasificare este urmatoarea:

In imagine avem bulina nouă care se presupune a fi o data nouă

Pentru a gasi ce culoare are punctul alb se traseaza un cerc imaginar și se numara punctele verzi și punctele rosii din acel cerc. Probabilitatea ca punctual alb să aparțina unei grupe este numarul total de buluine din cercul imaginar împartit la numarul total de cazuri pentru aceea categorie, de unde rezultă că probabilitatea pentru punctual alb ca să fie în categoria roșu este de 3/70 iar pentru verde probabilitatea este de 1/130, acesata fiind probabilitatea “verosimila”.

In final se va calcula probailitatea reala ca puncrul alb să fie verde sau roșu prin aplicarea urmatoarei formule: probabilitatea “prior” înmultita cu probabilitatea “verosimila” și se alege cea mai mare probabilitate.Aceasta probabilitate se numește probabilitatea “posterioara”.

Probabilitatea posterioara pentru cazul verde este de 13/20*1/130=1/200 =0.005

Probabilitatea posterioara pentru cazul roșu este de 70/200*3/70=3/200=0.015

Rezultatul final va fi că bulina alba este de culoare roșu pentru că probabilitatea posterioara pentru cazul roșu este mai mare decât probabilitatea posterioara a cazului verde.

Capitolul III Algotirmul de categorisire

Algoritmul de categorisire este împărțit în trei mari module. Primul modul ia pagina sursă a site-ului și o curața de limbaje de programare, ramânând doar informațiile utile. Al doilea modul gasește forma gramaticală a cuvintelor din propoziție și calculează o pondere de relevanța a acelui cuvânt în gasirea categoriei din care face parte site-ul. Al trelea modul folosește un algoritm de clasificare pentru a gasi categoria site-ului.

III.1 Obținerea paginii surse și pregătirea acesteia.

Pagina sursă a site-urilor este o pagină unde se gasește codul sursă a site-ului. Pagina sursă contine limbaje de programare, ex: HTML,CSS,JavaScript, care nu se văd în browser și informații pe care le vede utilizatorul. Pentru algoritmul de categorisire se utilizează doar informațiile vizibile cum ar fi titlul paginii, meniul paginii, descrieri, comenatrii daca este cazul.

III.1.1 Obtinerea paginii sursă a site-ului

Pagina sursă se obtine folosind un script scris în C#. Scriptul are ca și parametru de intrare url-ul site-ului dorit să se categoriseze.Acest script utilizeaza librariile „System.Net” și „System.IO” de pe platforma .NET. Libraria System.Net face request la servărul web și împreuna cu libraria System.IO care citeste pagina sursă din memoria RAM a calculatorului și o pune într-o variabilă de tip string. La crearea cererii catre servărul web se pot obține diferite eruari de cerere către servar, iar în acest caz se incepe trateare lor.

Tratarea eruarilor de tip 3xx presupune ca url-ul la care se face cerere nu mai este valabil și ma atentionează ca sa modificat și imi spune noul url. În cazul acestor eruari voi face o noua cerere la servar-ul web folosind noul url, la care m-a redirectat.

Tratarea eruarilor de tip 4xx presupune ca url-ul este greșit sau nu există raspuns pentru acel url deaorece functioneaza fără „www” în url sau are la sfârsit caracterul ’/’. Daca url-ul are prefixul „www” se va încerca din nou să se obțina pagina sursă dar de data aceasta url-ul va fi fără „www”. Daca din nou obținem eruarea 4xx de va pune la sfarsitul url-ului caracterul ‚/’, url-ul având „www” în componența sa, și se va incerca din nou. Daca din nou se obtțne eruare de tipul 4xx atunci se va incerca url-ul cu ‚/’ la sfârsit dar fără „www” în componența sa. Daca din nou se obtine eruare de tip 4xx atunci inseamna ca site-ul nu funcționeaza.

Tratarea eruarilor de tip 5xx. Aceste eruari sunt eruari de servar iar singura metoda de a rezolva aceste eruari este de a încerca să se ia pagina sursă a site-ului in alt moment de timp.

Tratarea eruarilor de tip 1xx. Aceste eruari indica un raspuns provizoriu al servarului și în acest caz putem ignora aceste eruari.

Daca avem un raspuns de tip 2xx în HttpStatusCode, atunci progamul va trece la curațarea paginilor sursă de coduri de programare.

III.2 Curățarea paginii sursa

Curățarea paginii sursă se realizeaza în mai mulți pasi și presupune parcurgerea paginii de fiecare data caracter cu caracter.

III.2.1 Curățarea de cod Javascript

Primul pas este curățarea de coduri JavaScript . Pentru a șterge codul javascript se identifica etichelete „<script>” și „</script>” se se șterge tot textul dintre aceste etichete.

Exemplu de cod JavaScript care va fi sters :

<script>

(function($, d) {

$('#one').liteAccordion({

onTriggerSlide : function() {

this.find('figcaption').fadeOut();

},

onSlideAnimComplete : function() {

this.find('figcaption').fadeIn();

},

autoPlay : true,

pauseOnHover : true,

theme : 'stitch',

rounded : true,

enumerateSlides : true

}).find('figcaption:first').show();

$('#two').liteAccordion();

})(jQuery, document);

</script>

III.2.2 Curățarea de cod CSS

Curățarea paginii de cod CSS este asemanatoare curățării de cod JavaScript. Se folosește același algoritm dar etichetele identificate sunt : „<style>” și „</style>”.

Exemplu de cod CSS care va fi sters :

<style>

/* css */

strong + p { margin-top: 0 }

dt { font-weight: bold }

dd { margin: 0 }

figure { display: block; width: 100%; height: 100%; margin: 0 }

figcaption { padding: 10px 15px; position: absolute; bottom: 20px; right: 30px; z-index: 3; background: black; background: rgba(0,0,0,0.7); color: white;

-webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px }

.accordion.stitch .slide div { background: #333 }

.social-buttons { width: 100%; text-align: center; margin-top: 30px }

.social-buttons ul { display: inline-block; margin: 0 }

.social-buttons li { float: left; list-style-type: none }

</style>

III.2.3 Curățarea finala

In această fază avem codul sursă curățat de cod JavaScript și cod CSS. Urmează curățarea paginii sursă de cod HTML care este asemanatoare curațarilor anterioare, dar de data aceasta se șterge tot ce este între caracterele „<” și „>”.Prin aplicarea acestui algoritm se sterg toate etichetele de cod HTML precum: „</div>”, „ </body>”, „ </p>”>”, „ <body>”, „ <div >” ,

„ <table>”, „ <tr >”, „ <td>”, „ <p >”, „ <href >”, „ <a >”, „ <h1 >”, „ <h2>”, „ <h3 >”,

„ <h4 >”. Algoritmul de curățare va șterge și comentariile lasate în cod, identificate prin etichetele: „<!–”, eticheta de început și eticheta de final „–>” și va identifica etichetele de linie noua, „\r\n”, „\n” și le va înlocui cu un spatiu pentru a micșora lungimea textului rezultat în urma curățarii.

Exemplu de cod din pagina sursă înainte de curățare :

Exemplu de pagina curățata înainte de a înlocui etichetele de linie noua:

Exemplu de cod dupa aplicarea de înlocuire cu spațiu a etichetelor de linie noua :

DESPRE NOI Facultăți Conducerea UO Managementul Calității Informații publice Structuri interne EDUCAȚIE Admitere Studii doctorat Învățământ la Distanță Departament DPPPD Educație Continuă

III.2.4 Tratarea caracterelor special(diacritice)

Tratarea caracterelor speciale presupune înlocuirea lor folosind caractere din alfabetul englez sau să aibe codul ascii a caracterului cuprins între 65 și 90 pentru caractere mari și 97 și 122 pentru caractere mici. Aceasta transformare se va realiza deoarece categorisirea se va face în cod Python care folosește ca și metode de memorare a caracterelor Unicode și de cele mai multe ori transformarea caracterelor speciala în Unicode returneaza eruari sau alte valori fata de valoarea inițiala.

Exemplu de eruare pentru în transformare de text Unicode:

>>> u = unichr(40960) + u'abcd' + unichr(1972)

>>> u.encode('utf-8')

'\xea\x80\x80abcd\xde\xb4'

>>> u.encode('ascii')

Traceback (most recent call last):

File "<stdin>", line 1, în ?

UnicodeEncodeError: 'ascii' codec can't encode character '\ua000' în position 0: ordinal not în range(128)

Pentru a evita aceste eruari se va inlocui caracterele speciale cu caracterele aferente, cum este ilustrat în urmatorul tabel:

Pentru realizarea acestei normalizari se va folosi o metoda scrisă în C# care va utiliza expresii regulate sau regex pentru a identifica diacriticile și le va înlocui cu caracterul aferent lui.

III.3 Algoritmul de categorisire, partea de categorisire

În momentul în care exista un text curațat și normalizat de va apela un script scris în Python care va împarții textul pe atomi de cuvinte, va identifica forma gramaticală și va categoriza site-ul în funcție de atomii de cuvinte și forma lor gramaticală. Scriptul are ca și parametrii de intrare textul curațat.

In primă fază se normalizeaza din nou texul, transformând tot textul în text format doar din caractere mici, semnele de punctuatie raman pentru ca nu influențeaza categorizarea.

III.3.1 Aplicarea funcțiilor NTLK.Tokenizer și NLTK.Grammar

Funcția de tokenizare este o funcție care împarte textul în atomi de cuvinte folosind algoritmi descrisi în capitolul II.4.1 NLTK Tokenizer.

Pentru a gasii parțile gramaticale se folosește NTLK.Grammar. Modul de functionare al algoritmului este descries în capitolul anterior II.4.2 NLTK Grammar.

Aplicand cei doi algoritmi vom avea fiecare cuvânt și ce parte gramaticală reprezinta acesta. Pentru a putea categorisi site-ul vom avea nevoie de a introduce ponderi de relevanta a cuvantului. Aceasta pondere depinde forma gramaticală, de exemplu un verb nu poate să aiba o pondere foarte mare în determinarea categoriei, el chiar putand fi ignorant. Cele mai importante parți gramaticale care pot determina categoria sunt substantivele și adjectivele. Pondrea pentru o parte gramaticală este dinamica depinzând de numatul de cuvinte din propoziție, dar per total, ponderile adunate din propoziție trebuie să dea 100%. Astfel ponderea este pe propozitie și nu pe text.

Pentru ca verbele se pot neglija atunci acestea vor avea o pondere de 0% .La fel se poate proceda și cu pronumele.

Exemplu de gasire a parților gramaticale și calcularea ponderilor de relevanța:

Se presupune ca avem în text urmatoarea propoziție:

“Eu dau licenta”.

Se analizeaza ce forme gramaticale au cuvintele din propoziție:

Tabel 3.1

Iar propozitia va fi sub urmatoarea forma

Pronume verb substantiv.

Pentru ca verbele și pronumele pot fi neglijate, vom avea urmatoare tabela de pondere:

Tabel 3.2

Suma ponderilor din cuvânt este 100% deci este corect raportul de importanta

III.3.2 Aplicarea algoritmului de categorisire NaiveBayes

Functionalitatea acestui algoritm este descrisă în capitolul II4.2 NaiveBayes.Datele de intrare sunt luate din baza de date unde sunt create categorii pe baza anumitor cuvinte. Acele cuvinte dau o anumită relevanța pentru o categorie în funcție de partea gramaticală pe care o poate avea. De exemplu pentru o categorie un cuvant care este substantiv poate să fie neglijabil, dar daca apare ca și adjectiv să dea categoria, adică are o pondere foarte mare.

Sistemul de categorizare are la baza cateva categorii mari sau categorii principale care pot fii extinse daca este cazul și fiecare categorie mare sau principală este împartita în alte categorii mai mici sau categorii secundare. Exemplu de categorii principale: Informativa general, Educație, Economice, Politice etc. iar categorii secundare care derivă din categoria principala Educație ar fi urmatoarele subcategorii: Universitare, Post Universitare, etc.

Pe baza datelor de antrenament a algoritmului NaiveBayes și împreuna cu celelealte cuvinte din site se va identifica subcategoria și categoria principala.

Continuam cu exemplu prezentat în gasirea formelor gramaticale și gasirea ponderilor.Sa presupunem ca baza de date avem cuvântul licenta care apare la forma gramaticală subiect ca aparține categoriei Educatie dacă are pondere de 100%. Daca se folosește algoritmul NaiveBayes de categorizare se va identifica faptul ca textul “Eu dau licenta” poate să se refere la categoria Universitate.

III3.3 Structura bazei de date

Baza de date folosită este de tipul bazelor de date relationare, iar distribuția folosită este MySql.

Baza de date are o tabela cu toate categoriile principale, o alta tabela cu toate categoriile secundare legate printr-o legatură de tip Foreignt Key cu tabelă cu categoriile principale. Amandoua tabelele se leaga cu alte doua tabele, tabela de forme gramaticale și tabela de cuvinte prin o a treia tabela unde este setat ponderea pentru care un cuvânt aparține unei grupe în funcție de forma gramaticală. În imaginea urmatoare este diagrama bazei de date :

Fig 3.3 Diagrama baza de date

Capitolul IV Concluzii

In această lucrare am prezenatat o metodă de clasificare a site-urilor pe baza tesxtului din site. S-a folosit diverse librarii precum NLTK, NaiveBayse în Python iar în C# Regex și motodele de extragere a paginii sursă din site-uri.

In prima parte a proiectului s-au prezentat tehnologiile utilizate, partea teoretica și exemple daca era cazul și ce module din aceste tehnlogii s-au folosit.

S-au tratat diferite eruari care apar, de exemplu la comunicarea cu servarul de host al site-ului, sau se incearca să se anticipeze anumite eruari și să se evite apariția lor, modificarea diacriticelor cu caractere din alfabetul englez. S-au aplicat metodele necesare pentru a identifica categoria și se afiseaza în linia de comandă categoria și subcategoria site-ului. Metodele aplicate au fost normalizarea și curațare de text, imparțire în atomi de text și identificarea parților gramaticale, și algoritmul de clasificare a site-ului.

Aceasta metodă de clasificare se bazează mult pe datele de intrare care trebuiesc să fie cat mai corecte și cat mai multe, iar din aceste motiv este mai mult teoretic pentru ca apar multe cazuri de fals pozitiv, adica categoria rezultata este greșita. Procentajul de acuratete este de 60% în conditiile actuale dar pe parcurs cand se îmbunatațeste baza de date cu categorii, subcategorii și cuvinte care definesc categoriile acest procentaj va creste.

Bibliografie

http://www.ling.helsinki.fi/kit/2008s/clt231/nltk-0.9.5/doc/en/ch07.html

http://www.dotnetperls.com/remove-html-tags

http://ro.wikipedia.org/wiki/Optimizare_pentru_motoare_de_căutare

http://en.wikipedia.org/wiki/Python_(programming_language)

http://en.wikipedia.org/wiki/CPython

http://msdn.microsoft.com/en-us/library/system.net.httpwebrequest.aspx

http://www.tutorialspoint.com/python/python_exceptions.htm

http://www.tutorialspoint.com/python/python_functions.htm

http://ro.wikipedia.org/wiki/SQL

http://en.wikipedia.org/wiki/Unsupervised_learning

http://www.nltk.org/api/nltk.tokenize.html

http://humansensing.cs.cmu.edu/projects/reke.html

http://www.nltk.org/api/nltk.html#module-nltk.grammar

Eyheramendy, S., Lewis, D. and Madigan, D. On the naive bayes model for text

categorization. In: Proceedings Artificial Intelligence & Statistics 2003.

Duda, R and Hart, P., Pattern Classification and Scene Analysis. Wiley, New

York. 1973

Bibliografie

http://www.ling.helsinki.fi/kit/2008s/clt231/nltk-0.9.5/doc/en/ch07.html

http://www.dotnetperls.com/remove-html-tags

http://ro.wikipedia.org/wiki/Optimizare_pentru_motoare_de_căutare

http://en.wikipedia.org/wiki/Python_(programming_language)

http://en.wikipedia.org/wiki/CPython

http://msdn.microsoft.com/en-us/library/system.net.httpwebrequest.aspx

http://www.tutorialspoint.com/python/python_exceptions.htm

http://www.tutorialspoint.com/python/python_functions.htm

http://ro.wikipedia.org/wiki/SQL

http://en.wikipedia.org/wiki/Unsupervised_learning

http://www.nltk.org/api/nltk.tokenize.html

http://humansensing.cs.cmu.edu/projects/reke.html

http://www.nltk.org/api/nltk.html#module-nltk.grammar

Eyheramendy, S., Lewis, D. and Madigan, D. On the naive bayes model for text

categorization. In: Proceedings Artificial Intelligence & Statistics 2003.

Duda, R and Hart, P., Pattern Classification and Scene Analysis. Wiley, New

York. 1973