Tehnologii Data Mining Utilizate In Domeniul Warehouse

Tehnologii data mining utilizate în domeniul warehouse

INTRODUCERE

Documentele, care sunt localizate în diferite locații pe diverse servere, pot fi regăsite cu ajutorul unui identificator numit URL. Hipertextul, inclusiv imagini etc. este afișat cu un ajutorul unui program de navigare în web numit browser, care descarcă paginile web de pe un server și le afișează pe un terminal „client” la utilizator.

WWW este numai unul din numeroasele servicii informatice disponibile în Internet. Alte servicii sunt de exemplu: afișarea de informații cu formă de text, imagini și sunete, e-mail, transferul de fișiere FTP, chat, aplicații video și video on demand, servicii telefonie și telefonie cu imagine prin Internet de tip VoIP, posturi de radio și televiziune prin Internet, e-commerce, răspândirea știrilor prin metode RSS, toate genurile de grafică și muzică, lucrul pe un calculator de la distanță prin Internet, distribuție de software ș.a.

Domeniile web, sunt colecții de host-uri(gazde). De exemplu, pentru host-ul ro.facebook.com, numele domeniului este facebook.com. Domeniile sunt arborescente: un domeniu poate fi subdomeniu al unui alt domeniu. Domeniile "rădăcină" se mai numesc și domenii de nivel superior (Top Level Domain, prescurtat TLD). Pe același exemplu, "com" este TLD-ul pentru host-ul ro.facebook.com.

Scopul studiului de caz, este să realizeze o predicție a claselor( Google PageRank) în care sunt împărțite domeniile web din topul preferințelor românilor, în vederea clasificării siteurilor care sunt indexate de către motorul de căutare Google.

Pentru efectuarea acestei clasificări, vom utiliza tehnologia data mining, mai exact tehnici de învățare supervizată, cum ar fi Clasificatorul Naïve Bayes, sau Mașini cu Suport Vectorial (SVM).

Lucrarea este structurată în 5 capitole principale, fiecare dintre acestea evidențiind tehnicile folosite în realizarea studiului de caz și legătura acestuia cu noile tendințe de pe piață.

În capitolul 1, sunt prezentate principalele tehnologii utilizate în domeniul analizei datelor, domeniul statistic și Business Intelligence, precum și de noile tendințe care își fac apariția pe piață. Dintre acestea, am amintit: Data Warehouse, Data Mining și noua tehnologie Big Data.

Capitolul 2 prezintă abordări și exemple existente în literatura de specialitate, cu privire la Web Mining și îmbunătățirea PageRank-ului unei pagini. Articolul prezentat în acest capitol poartă denumirea “Integrarea Algoritmilor Genetici si a Logicii Fuzzy in Optimizarea Structurii WEB” .

În capitolul 3 sunt prezentate principalele fundamente statistice și matematice, pe care se bazează studiul de caz. Printre acestea se numără Teoria Probabilităților, sau Teorema lui Bayes.

În capitolul 4 sunt prezentate principalele caracteristici ale învățării supervizate,precum și clasificatorii folosiți în realizarea studiului de caz: Clasificatorul Naïve Bayes și SVM.

În ultimul capitol, cel de-al 5-lea, este prezentată proiectarea și realizarea studiului de caz, precum și rezultatele obținute de pe urma acestuia. Rezultatele sunt interpretate pe baza output-urilor obținute în urma executării anumitor scripturi, în programul R.

I Descriere domeniu și concepte utilizate

I.1 Data Warehouse

Informațiile reprezintă un bun extrem de valoros pentru orice întreprindere, și din cauza aceasta, trebuie să fie depozitate în mod corespunzător și ușor accesibil, ori de cate ori acestea sunt necesare. Cu toate acestea, disponibilitatea prea mare de date, face ca extragerea celor mai importante informații sa devină dificilă, dacă nu imposibilă.

Depozitare de date(data warehousing) este un fenomen care a crescut datorită cantității imense de date electronice stocate în ultimii ani,dar și datorita necesitatii urgente de a utiliza aceste date, pentru a realiza obiective dincolo de prelucrarea tipică de zi cu zi.

Într-un scenariu tipic, o mare corporație are multe ramuri, iar managerii generali trebuie să cuantifice și să evalueze modul în care fiecare ramură contribuie la performanța afacerii la nivel mondial. Baza de date centrala,stocheaza informații detaliate cu privire la atribuțiile fiecărei ramuri. Pentru a satisface nevoile managerilor, pot fi realizate interogări personalizate pentru a prelua datele necesare. Pentru ca acest proces să funcționeze, administratorii bazei de date trebuie mai întâi să formuleze interogarea dorita (de obicei, o interogare SQL) după ce au studiat îndeaproape componența de bazei de date. Apoi interogarea este procesată. Aceasta poate dura câteva ore, din cauza cantității imensă de date, complexității de interogare, precum și efectelor concurente ale rulării unor interogari pe date din aceeasi baza de date. În cele din urmă, este generat un raport,iar acesta este livrat către manageri sub forma unei foi de calcul.

Un depozit de date(Data Warehouse) este o colecție de date orientată pe subiect, integrată,evolutivă în timp și ne-volatilă, care susține procesele de luare a deciziei [1].

Depozitele de date sunt orientate pe subiect, deoarece acestea sunt folosite pentru stocarea de date dintr-o anumita categorie.De exemplu, „vanzari”, „produse”, „clienti” , pot reprezenta un subiect al depozitului de date.

Un depozit de date, integrează date din surse multiple. De exemplu, sursa A și B pot avea diferite moduri de identificare a unui produs, insa într-un depozit de date, va exista doar un singur mod de identificare a acelui produs.

Din punct de vedere al evoluției in timp, un depozit de date păstrează toate datele istorice. De exemplu, se pot prelua date vechi de 3 luni, 6 luni, 12 luni, sau date chiar mai indepartate,dintr-un depozit de date. Acest lucru contrastează cu un sistem de tranzactii, unde de cele mai multe ori, sunt ținute doar cele mai recente date. De exemplu, un sistem de tranzacții poate deține cea mai recentă adresă unui client, în timp ce un depozit de date poate stoca toate adresele asociate cu un client.

Fundamental, datele nu sunt niciodată șterse din depozitele de date,iar actualizările sunt facute în mod normal atunci când baza de date este offline. Acest lucru înseamnă că depozitele de date pot fi, în esență, văzute ca baze de date read-only,de unde tragem concluzia de ne-volatilitate a acestora in timp.

Din punct de vedere arhitectural,un depozit de date este caracterizat de următoarele concepte [2]:

Separare: procesele analitice și procesele tranzactionale trebuie,pe cat de mult posibil,sa fie privite diferit;

Scalabilitate: caracteristicile Hardware si Software trebuie sa fie imbunatatite foarte rapid si usor,deoarece volumul de date care trebuie manipulat si procesat si cerintele utilizatorilor,cresc progresiv;

Extensibilitate: arhitectura trebuie să fie astfel realizata, incat sa gazduiasca noi aplicatii si tehnologii,fara ca intregul sistem sa fie reproiectat;

Securitate: monitorizarea accesului este un aspect esential de securitate,datorita datelor care sunt stocate in depozitul de date;

Administrare: managementul depozitului de date nu ar trebui sa fie dificil;

În figura următoare, este prezentată arhitectura unui depozit de date:

Source layer: un depozit de date folosește surse de date diferite. Aceste date sunt stocate inițial în baze de date relaționale, în aplicații corporate de bază(CRM,sisteme de feedback etc.), sau provin din sisteme informaționale din afara firmei(de exemplu: baze de date ale altor firme, care au nevoie de analiză pe acele date)

Data staging: data stocată in sursele enumerate mai sus trebuie să fie extrasă,curățată pentru a fi înlaturate inconsistențele și umplute golurile și integrată intr-o singură schemă,pentru a fuziona cu datele din alte surse. Tehnicile ETL (Extract Transform Load) se ocupă de fuzionarea datelor eterogene, de extragere, transformare, curățare, validare, filtrare și încărcare a acestora in depozitul de date. Din punct de vedere tehnologic, aceaastă fază se ocupă de probleme specifice sistemelor informatice distribuite,cum ar fi gestionarea inconsistentă a datelor,sau structuri incompatibile de date.

Data warehouse layer: informația este stocată într-un singur depozit logic,centralizat: Depozitul de Date. Depozitul de Date poate fi accesat direct,dar poate fi utilizat, de asemenea ca sursă pentru creare de Data Mart-uri,care replică parțial continutul Depozitului de Date. Data Mart-urile sunt create pentru anumite departamente, cu scopul dezvoltării de rapoarte. Depozitele de tip Meta Data rețin informații despre surse, proceduri de acces, utilizatori, schemele din Data Mart etc.

Analysis: în cadrul acestui strat, datele integrate sunt utilizate eficient, cu scopul dezvoltării de rapoarte, al analizei dinamice de date și al simulării diferitelor scenarii spre care pot să conveargă anumite situații sau proiecte. Tehnologic vorbind, ar trebui să conțină diferiți navigatori, optimizatori pentru interogări complexe și interfete cu utilizatorul.

I.2 Data Mining

Denumirea provine de la analogia cu activitatea minieră, deoarece aici sunt cercetate și analizate milioane de date pentru a extrage din ele informații și tipare noi, dincolo de scopurile pentru care acestea au fost colectate și memorate la origine.

Data mining are, ca și alte concepte folosite în informatică, mai multe definiții. În esență, acestea converg spre ideea formulată anterior: un proces de extragere de informații noi din colecțiile de date existente. Termenul de dată este utilizat cu semnificația de descriere a unui eveniment, produs în lumea reală și verificabil prin raportare la aceasta. Informația constituie descrierea unei categorii abstracte, ce acoperă mai multe evenimente sau exemple concrete.

Principiul de funcționare în data mining este următorul: se prelucrează date referitoare la perioade trecute, examinând o mulțime de situații care s-au produs și ale căror rezultate sau consecințe sunt cunoscute, pentru a evidenția caracteristicile acestora și a permite elaborarea unui tipar. Odată construit, modelul poate fi aplicat situațiilor noi, de același tip.

Informațiile obținute prin data mining sunt de natură predictivă sau descriptivă.

Un exemplu tipic de problemă predictivă este direcționarea acțiunilor de marketing. Datele rezultate din corespondența promoțională trecută se folosesc pentru a identifica destinatarii pentru care următoarea campanie promoțională poate aduce un maxim de efect.

Ciclul de utilizare a Data Mining

Potențialul oferit de tehnicile de data mining trebuie încorporat în procesele comerciale curente ale organizațiilor pentru a deveni realmente utile. Căutarea de informații nu este un scop în sine; ea devine utilă doar în măsura în care se transpune în acțiune.

Declanșarea unei acțiuni bazată pe tehnici de explorare a datelor se face ca urmare a observării sau constatării unei necesități sau oportunități comerciale. Observarea reducerii numărului de clienți, scăderea vânzărilor la anumite produse, lansarea unui nou produs sau serviciu, sunt exemple de situații de acest gen. O firmă poate alege să reacționeze sau nu la asemenea situații și, în caz afirmativ, poate alege diferite moduri de a o face. Tehnicile de tip data mining constituie unul dintre acestea. Totuși, este de notat faptul că fiecare dintre ele este potrivită doar unui anumit tip de probleme sau de situații și că, în majoritatea cazurilor, aplicarea lor combinată poate produce rezultatele cele mai bune. Alegerea tehnicii sau tehnicilor folosite trebuie să ia în seamă și compatibilitatea dintre cerințele legate de date, ale tehnicii sau tehnicile alese și cele care se pot folosi în cazul real.

Pasul următor constă în explorarea propriu-zisă a datelor. La rândul său, acesta este departe de a fi simplu sau liniar. Multe dintre aceste tehnici solicită, înainte de a putea fi utilizate, un proces de învățare; datele, fiind eterogene, impun o etapă de pregătire prealabilă; rezultatele sunt rareori aplicabile în forma în care sunt obținute, cerând un efort suplimentar de interpretare și adaptare, la care să participe și decidentul, cu cunoștințele și experința sa în afaceri. Spre exemplu, aplicarea unui algoritm de grupare poate evidenția existența a 20 de clustere diferite; dintre acestea, doar unul se poate dovedi util dar relevanța lor nu poate fi apreciată decât de specialistul sau specialiștii din firmă.

Informațiile obținute anterior au valoarea acțiunilor întreprinse pe baza lor. Tehnicile de data mining permit obținerea de cunoștințe mai bogate privitoare la mediul în care există și funcționează întreprinderea. Acestea trebuie însă transformate în acțiune iar efectul acestora măsurat.

Toate aceste conturează ideea unui ciclu în utilizarea data mining [3], în cursul căruia se parcurg patru etape:

identificarea oportunității comerciale și a datelor pe care se poate baza studiul

extragerea de informații din depozitele de date existente, folosind tehnici potrivite de data mining

adoptarea de decizii și efectuarea de acțiuni pe baza informațiilor rezultate

măsurarea rezultatelor certe pentru a identifica și alte modalități de exploatare a datelor disponibile

Verificarea ipotezelor si căutarea cunoștințelor

Aplicarea tehnicilor de data mining poate fi făcută din perspectiva unui demers ascendent sau descendent.

În abordarea descendentă, efortul este orientat spre confirmarea sau infirmarea unor idei (ipoteze) formulate în prealabil prin alte mijloace. Un demers asemănător se aplică în statistică și în analiza datelor, dar folosind alte tehnici și metode.

Abordarea ascendentă are o cu totul altă finalitate; ea urmărește extragerea de cunoștințe sau informații noi din datele disponibile. Căutarea poate fi dirijată sau nedirijată .

Căutarea dirijată ia în considerare un atribut sau un câmp, ale cărui valori încearcă să le explice prin celelalte câmpuri. Este cea mai folosită în practică.

Căutarea nedirijată are ca scop identificarea relațiilor sau structurilor existente în ansamblul datelor examinate, fără a acorda prioritate unui câmp sau altul. Deși mai spectaculoasă, în practică se recurge mult mai puțin la ea decât la căutarea dirijată.

Tehnici si acțiuni

Ceea ce se exploatează prin data mining [9] sunt colecțiile de date de care dispune o organizație, colecții care au fost însă constituite pentru alte scopuri; în cazurile cele mai frecvente, este vorba de datele privitoare la tranzacțiile derulate într-o anumită perioadă de timp: comenzi, livrări, plăți, încasări etc. La acestea se adaugă, deseori, date provenite din alte surse, cum ar fi, spre exemplu, statistici oficiale privitoare la evoluția economiei în ansamblu, date privitoare la concurență, diverse măsuri legislative sau normative etc. Aceasta explică utilizarea frecventă a calificativului de informații ascunse: volumul mare sau foarte mare și faptul că structura și conținutul lor sunt edificate în perspectiva altor finalități, fac foarte dificilă sau imposibilă detectarea corelațiilor sau raporturilor de ansamblu pe care le încorporează în mod intrinsec.

Rezultatele sunt cu atât mai sigure și relevante, cu cât se bazează pe un volum mai mare de date, din motive lesne de înțeles: o tendință relevată de un număr foarte mare de cazuri practice este mult mai pertinentă decât cea dedusă din doar câteva situații.

Data mining nu este un panaceu universal, capabil să rezolve orice problemă de gestiune. În fapt, aportul său se rezumă la un număr limitat de acțiuni: clasificarea, estimarea, predicția, gruparea, analiza grupărilor, dar care, folosite în mod adecvat, se pot dovedi extrem de utile pentru numeroase probleme și situații din domeniul decizional.

Clasificarea urmărește să plaseze obiectele prelucrate într-un grup limitat de clase predefinite. Spre exemplu, o cerere de credit va fi încadrată, prin clasificare, în una dintre următoarele categorii de risc: scăzut, mediu, ridicat. Obiectele clasificate sunt reprezentate, în general, sub formă de înregistrări, compuse din atribute sau câmpuri. Dintre tehnicile de data mining, cele mai adecvate clasificării sunt arborii de decizie și raționamentul bazat pe cazuri.

Estimarea urmărește să atribuie o valoare unei variabile, pe baza celorlalte date de intrare. Prin intermediul său se poate aprecia, de exemplu, numărul de copii sau venitul total al unei familii. Rezultatele obținute prin estimare sunt valori continue. Rețelele neuronale sunt printre cele mai bune tehnici de data mining pentru acest gen de prelucrări.

Predicția urmărește să claseze înregistrările tratate în funcție de un comportament sau o valoare estimată viitoare. În acest scop, se recurge la o colecție de exemple, bazate pe date din trecut, în care valorile variabilei de previzionat sunt deja cunoscute. Cu ajutorul acestora se construiește un model care să explice comportamentul observat. Aplicând acest model asupra înregistrărilor de prelucrat, se obține o predicție a comportamentului sau valorilor acestora în viitor. Cu condiția folosirii unui set adecvat de exemple trecute, toate tehnicile de clasificare sau estimare pot fi folosite și pentru predicții.

Gruparea urmărește să determine care sunt obiectele care apar cel mai frecvent împreună. Exemplul tipic pentru acest gen de acțiune este determinarea mărfurilor care se cumpără uzual împreună, de unde și denumirea de “analiză a coșului gospodinei”.

Analiza grupurilor urmărește să dividă o populație eterogenă în grupuri mai omogene, numite “cluster”. Spre deosebire de celelalte tipuri de acțiuni asemănătoare, aici nu există un set predeterminat de clase ca în cazul clasificării și nici exemple trecute. Segmentarea se face în exclusivitate pe baza similitudinilor sesizate între obiecte.

I.3 Big Data

Date Big presupune, de obicei, seturi de date cu dimensiuni care depășesc capacitatea instrumentelor software utilizate în mod obișnuit pentru a extrage, gestiona și prelucra datele, într-un timp tolerabil.

Termenul se referă adesea, pur și simplu, la utilizarea analizei predictive („Predictive Analytics”) sau a altor metode avansate pentru extragerea valorii din date, și rareori la o dimensiune specifică a setului de date.

Definiția dată pentru conceptul Big Data, de către Viktor Mayer-Schönberger și Kenneth Cukier [4] este următoarea: „Datele păstrate și prelucrate în cantități imense, datorită unor medii de stocare mai ieftine, unor metode de procesare mai rapide și unor algoritmi mai performanți”.

Seturile de date cresc în dimensiune, deoarece acestea sunt adunate de numeroase dispozitive, cum ar fi : telefoane mobile, camere video, frecvențe radio (RFID), microfoane, rețele și senzori wireless. Capacitatea tehnologică de stocare la nivel mondial, per capita, s-a dublat la aproximativ 40 de luni, din 1980 pâna în prezent. Începând cu anul 2012, au fost creați, în fiecare zi, aproximativ 2,5 exabytes (~2,5 miliarde gigabytes) de date. Provocarea pentru marile întreprinderi este de a determina cine să conducă inițiativele Big Data, de care depinde întreaga companie.

Big Data a devenit o problemă în afaceri, sau cel puțin o problemă pe care oamenii de afaceri incep să o conștientizeze. Presa începe să aloce din ce în ce mai mult spațiu acestui subiect. Pornind cu Wall Street Journal "Companiile sunt inundate cu date" (“Companies are being inundated with data") la Financial Times "Din ce în ce în afaceri sunt aplicate analize din mass-media, cum ar fi Facebook și Twitter" ("Increasingly businesses are applying analytics to social media such as Facebook and Twitter"), Forbes "Big Data a ajuns la Seton Health Care Family" ("Big Data has arrived at Seton Health Care Family"). De ce atâtea articole pe aceasta temă? Deoarece Big Data are potențialul de a afecta profund modul in care facem afaceri și chiar modul de a trăi [5].

Big Data are 4 caracteristici principale [5]:

Prima caracteristică este volumul.

Experții prezic că volumul de date din lume, va crește la 25 de Zettabytes în 2020. Același fenomen afectează fiecare companie – datele sunt în creștere la aceeași rată exponențială. Dar nu este numai volumul de date care este în creștere, numărul de surse de date este de asemenea în creștere.

A doua caracteristică este viteza.

Datele se creează la viteze din ce în ce mai mari. Companiile își mută aplicațiile de la aplicații de tip "batch" la aplicații în timp real. Și cerințele de afaceri au crescut la fel – de la răspunsuri săptămâna viitoare sau măine la un răspuns într-un minut sau la secundă. Și lumea este, de asemenea, din ce în ce mai instrumentată și interconectată. Volumul de date de streaming de pe aceste instrumente este exponențial mai mare decât a fost chiar cu 2 ani în urmă.

A treia caracteristică este varietatea datelor.

Varietatea datelor prezintă o provocare la fel de dificilă. Creșterea surselor de date a alimentat și creșterea tipurilor de date. De fapt, 80% din datele generate în lume sunt date nestructurate. Cu toate acestea, metodele tradiționale de analiză se aplică numai la informații structurate.

A patra caracteristică este veridicitatea datelor.

Cum se poate acționa pe baza acestor informații, dacă nu sunt de încredere? Stabilirea încrederii în datele pe care le folosește orice companie reprezintă o provocare uriașă odată cu creșterea surselor și tipurilor de date.

Un alt motiv pentru care Big Data este un subiect fierbinte astăzi este noua tehnologie care permite unei organizații să beneficieze de resursele interne de date. Ceea ce este nou, este tehnologia pentru a procesa și analiza aceste date la volumul și viteza dorită. Scopul tehnologiei Big Data este să analizeze toate datele disponibile, eficient din punct de vedere costuri. Orice date, așa cum sunt. Se pot analiza date structurate, video, audio, date spațiale sau orice tip de date.

Datele pot veni de la sistemele tradiționale – sisteme de facturare, sisteme ERP, sisteme CRM. De asemenea, vin de la mașini – de la etichetele RFID, senzori, comutatoare de rețea. Și datele vin de la oameni – site-ul web, social media, etc. Acest lucru face foarte dificilă analiza datelor sociale – extragerea ideilor de conținut în mare parte sub formă de text într-un timp foarte scurt.

II Trecere în revistă a literaturii de specialitate

II.1 Integrarea Algoritmilor Genetici si a Logicii Fuzzy in Optimizarea Structurii WEB

Ușurinta utilizării reprezintă una dintre cheile succesului unui site. Dacă structura legăturilor nu este bine organizată, pentru site-urile care au mai multe pagini legate intre ele,pe plan intern, poate fi dificil pentru un utilizator sa găsească informațiile de care are nevoie. Pe măsură ce complexitatea structurii legăturilor (link-urilor) crește, optimizarea acesteia devine foarte importantă pentru ca utilizatorii să poată naviga pe site cu ușurință.

Motoarele de căutare, cum ar fi Google, folosesc tehnologia Web mining pentru a extrage informații semnificative de pe Web. Pe lângă multe alte tehnologii Web mining, cercetarea realizată de către Jeffrey, J., Karski, P., Lohrmann, B., Kianmehr, K., și Alhajj, R. [6] se bazează pe tehnicile Web log mining și Web structure mining pentru a obține o perspectivă despre cum structura internă a unui site poate fi îmbunătățită.

În cadrul studiului realizat în publicația de mai sus, a fost folosit algoritmul WPS(weighted page rank) pentru a analiza structura legăturilor unui website. Algoritmul WPR ia în considerare faptul că gradul(page rank) unei pagini populare ar trebui să fie mai mare decât al unei pagini nepopulare. Mai mult de atât, prin intermediul algoritmului Web log mining, s-a demonstrat cum se pot obține date despre istoricul de navigare al utilizatorilor unui anumit site. În final, pe baza rezultatelor, proprietarii site-urilor au urmat să primească recomandări despre cum să îmbunătățească structura site-ului.

Înainte de a se putea face recomandări cu privire la structura site-ului, au fost descoperite două probleme principale:

Să se descopere care pagini erau importante potrivit structurii site-ului

Să se descopere care pagini erau importante pentru utilizatorii site-ului, bazat pe informațiile obținute în urma aplicării tehnicii Web log mining.

După ce aceste două probleme se vor rezolva, se poate trece la clasificarea paginilor Web. Metoda de clasificare folosită, se rezumă în felul următor: se presupune că vi este numărul de vizitatori ai unei pagini i , iar ti este timpul total petrecut de către toți vizitatorii acestei pagini, atunci indicatorul log rank value di este definit astfel: di = 0.4vi + 0.6ti . di reprezintă importanța unei pagini web, raportată la alte pagini web. Valoarea numerică di este calculată pentru fiecare pagină web în parte și este prezentată proprietarului paginii, pentru a găsi ceea ce este problematic în structura site-ului.

Un exemplu de date folosite în acest studiu este reprezentat în tabelul urmator:

Valoarea di nu a fost considerată foarte semnificativă, deoarece un utilizator final nu își poate da seama care este diferența dintre -455 și 1508. De aceea, în publicația [6], di este privit ca factorul de restructurare, folosindu-se logica fuzzy, pentru ca proprietarul site-ului să înțeleagă mai bine valoarea lui di , prezentată în termeni fuzzy.

Logica fuzzy oferă un grad de apartenență unei probleme, și prin urmare, descrie mai adecvat raționamentul unei probleme, decât o face o valoare numerică. Cu toate acestea, o valoare fuzzy poate fi lipsită de sens fără o funcție de apartenență bine-definită. Genetic Algorithms(Algoritmi Genetici) este un proces folosit pentru a optimiza funcțiile de apartenență.

Va fi aplicată tehnica algoritmilor genetici logicii fuzzy, pentru o mai bună reprezentare a factorului de restructurare. Folosind funcții de apartenență optimizate, se obține factorul de restructurare fuzzyficat, reprezentat în tabelul de mai jos.

Gradul de apartenență variază cu valori între 0 și 1, un factor de restructurare mare poate indica faptul că acea pagină va fi restructurată. Este mai dificil de precizat dacă după restructurare, o pagină va fi mai ușor sau mai greu de găsit.

In tabelul de mai sus, termenul “harder to reach” inseamna ca nu este neaparat necesar sa existe un link la pagina respectiva din pagina principala a site-ului, sau ca aceasta pagina nu tebuie sa fie adaugata intr-o locatie unde joaca un rol de legatura catre alte pagini, permitandu-le utilizatorilor doar sa treaca prin aceasta pagina pentru a ajunge pe alte pagini.

Solutia propusa este implementarea unei aplicatii pe baza algoritmilor genetici, pentru doua intrari(inputs) si in singur system fuzzy de iesire(output).

Soluția propusă

Pentru a aplica logica fuzzy lui di , trebuie sa determinam functiile de apartenenta pentru doua variabile de intrare: index (pi ) (WPR index) si index( li ) (Log rank index) si pentru variabila de iesire: factorul de restructurare. Astfel:

Functia de apartenenta pentru valoarea WPR : µ(x) ;

Functia de apartenenta pentru valoarea Log rank : µ(y) ;

Factorul de restructurare(di ) este definit astfel: di = index( li ) – index (pi ) ;

Valoarea lui di poate fi atat negativa cat si pozitiva, de aceea, se calculeaza valoarea absoluta a sa, notate rfi . Un rfi mai mare indica faptul ca este de preferat ca pagina sa fie restructurata, utilizand, de preferat, urmatoarele metode:

Stergerea lagaturilor catre acea pagina, in special de pe pagini cu un coeficient(page rank) mare;

Crearea de legaturi catre acea pagina, de pe pagini cu un coeficient(page rank) mic

Definirea valorilor de intrare și de ieșire

Fiecare functie de apartenenta pentru intrari si iesiri, poate avea orice numar de apartenente (memberships). Insa, pe masura ce numarul de apartenente creste, performanta algoritmului genetic scade, deoarece va creste numarul bazelor. Au fost definite astfel, patru apartenente(memberships), numite: low, medium left, medium right, high, atat pentru cele doua functii de intrare: µ(x) si µ(y), cat si pentru functia de iesire µ(z).

In figura de mai jos, se pot observa functiile de apartenenta initiale, ne-optimizate:

Setul de antrenare

Pentru experimentare, s-a folosit un site Web de dimensiune medie(~631 de pagini),care furnizeaza informatii despre dispositive HiFi.

Solutia optima pentru functiile de apartenenta, devine mai buna pe masura ce numarul de date din setul de antrenare, creste. Urmatoarele 5 inregistrari, reprezinta setul de antrenare care a fost folosit in experiment.

Input1 : xi = {11,132,182,369,476}

Input2 : yi = {11,56,375,7,2003}

Output : zi = {0,76,193,362,1527}i = 1,2,3,4,5

Codificare (encoding)

Cromozomul este reprezentarea functiilor de apartenenta de intrare si iesire si consista in numere naturale (uint). Fiecare functie de apartenenta are nevoie de 5 puncte, pentru a fi reprezentata; un punct pentru centrul apartenentei(membership) de tip medium si 4 puncte pentru 4 baze. Prin urmare, in total, este nevoie de 15 numere naturale (uint) pentru a forma un cromozom.Punctele fiecarui cromozom sunt generate in asa fel incat µ(x), µ(y), sau µ(z) sa nu contina valoarea 0, pentru niciun parametru de intrare x, y, sau z. Aceasta este o cerinta necesara a cromozomului.

Populația

Este necesar sa se aleaga dimensiunea populatiei (numarul de cromozomi) pentru o generare. Cresterea numarului de cromozomi duce la cresterea timpului de rulare al algoritmului. In acelasi timp, un numar scazut de cromozomi duce la scaderea acuratetii solutiei, din cauza variatiei reduse a cromozomilor.

In cadrul acestui experiment s-a folosit un numar de 10 cromozomi, in tabelul urmator fiind un exemplu de cromozom, cu informatii despre functiile de apartenenta.

Calcularea erorilor (Error score calculation)

Eroarea pentru fiecare cromozom poate fi calculata folosind urmatoarea formula:

, i = cromozomul i , n = numarul total de inregistrari(pagini)

Cromozomul cu cea mai mica eroare, devine cel mai optim cromozom.

Selectarea părinților (Parent selection)

Metoda folosita in experiment pentru selectarea parintilor, a fost Sorted Roulette: sorteaza populatia dupa fitness si apoi selecteaza pentru reproducere, cu o inclinare catre partea superioara a listei.

Este posibil ca o alta metoda( Fitness Roulette, Fitness Generation, Sorted Generation, Elitist Random Search ), sa aiba rezultate mai bune in optimizarea datelor de iesire.

Incrucișare (Crossover)

Incrucisarea este un schimb de informatii de la doi parinti. Rata de incrucisare poate avea valori in intervalul [0,1].

Dupa ce doi parinti (cromozomi) sunt selectati, programul decide aleator daca are loc o incrucisare. Atunci cand are loc incrucisarea, o pozitie aleatoare (pos1) este aleasa si fiecare unitate a pozitiei este schimbata intre cei doi parinti. Copiii rezultati sunt verificati daca indeplinesc proprietatile unui cromozom, mentionate mai sus. Daca o pozitie (posi) din componenta unui cromozom, nu indeplineste acele proprietati, pe acea pozitie este generat un nou numar natural (uint).

Cromozomul cu cea mai mica eroare este stocat si devine cel mai bun cromozom atunci cand programul se termina.

Funcții optime fuzzy de apartenență

Daca cel mai bun cromozom al celei mai bune generatii indeplineste cerintele de a fi cromozom, acesta devine solutie optima si functie optima fuzzy de apartenenta. Insa, daca nu indeplineste caracteristicile unui cromozom, cromozomul cu valoarea erorii imediat urmatoare devine cel mai bun cromozom, si asa mai departe pana este gasit un cromozom care sa indeplineasca proprietatile. In cazul in care niciun cromozom din cea mai buna generatie nu indeplinesc caracteristicile, aplicatia se termina fara sa returneze vreun rezultat.

Calcularea erorii relative (Calculating Error Ratio)

Valoarea totala posibila a erorilor(TPE) este calculata dupa urmatoarea formula:

, i = cromozomul i , n = numarul total de inregistrari(pagini)

Folosind formula de calculare a erorii unui cromozom, din sectiunea Error score calculation , eroarea totala(TE) poate fi calculata. Eroarea relativa este calculata folosind urmatoarea formula:

Prin experimentare se poate ajunge la o solutie mai buna(un cromozom cu o eroare mai mica), alegand o dimensiune diferita a populatiei, o alta metoda de selectie a parintilor, o alta rata de incrusicare, sau de mutatie.

Reguli generale

Dupa ce este identificat un cromozom optim, poate fi determinata regula fuzzy pentru fiecare inregistrare(pagina). Pentru un numar de n pagini , vom avea n reguli, dupa cum este expus in tabelul de mai jos. Pentru a determina regulile generale fuzzy, este nevoie sa se calculeze un indice al intensitatii( strength score ), pentru fiecare pagina in parte, folosind urmatoarea formula:

, n = numarul total de inregistrari(pagini)

Se poate defini un numar maxim de 4 reguli generale fuzzy(low, medium left, medium right, high), deoarece sistemul fuzzy are 4 apartenente: low, medium left, medium right si high. Urmatoarele reguli, determină normele generale fuzzy, dintre n reguli:

Regula #1: Daca apartenenta output-ului regulii fuzzy nu se potriveste cu apartenenta unui output al unei reguli generale fuzzy existente, atunci regula devine regula generala fuzzy;

Regula #2: Daca apartenenta output-ului regulii fuzzy se potriveste cu apartenenta unui output al unei reguli generale fuzzy existente, atunci regula cu indicele intensitatii( strength score ) mai mare, devine regula generala fuzzy;

Presupunand ca se aplica regulile de mai sus, paginilor din Fig. 5 , se vor obtine urmatoarele rezultate: prima pagina este regula generala fuzzy deoarece nu mai este nicio alta regula generala fuzzy definita. A doua pagina este de asemenea regula generala, potrivit regulii #1. Pentru cea de-a treia pagina, regula #2 este aplicata , deoarece factorul de restructurare z, are de asemenea valoarea high , la fel ca a doua pagina. Indicele intensitatii(strength score) celei de-a doua pagini este mai mare, deci aceasta ramane regula generala. Paginile 4 si 5 devin reguli generale conform regulii #1. Cea de-a sasea pagina are indicele intensitatii mai mare decat cel al primei pagini.Prin urmare, cea de-a sasea pagina o inlocuieste pe prima si devine regula generala.

Evaluare

631 de pagini WEB, impreuna cu WPR index si log rank index au reprezentat datele de intrare pentru aplicatie, care a folosit o dimensiune a populatiei de 10, 15 generari maxime, o rata a incrucisarii de 85, o rata a mutatiei de 0.09 si metoda Sorted Roulette pentru selectarea parintilor.

Figura de mai jos a fost obtinuta prin aplicarea algoritmilor amintiti anterior, pe datele de mai sus. Cel mai bun cromozom a avut o eroare relativa de 2.73% . Regulile generale fuzzy pentru acest rezultat, au fost urmatoarele:

Daca x este LOW si y este LOW, atunci factorul de restructurare z, este LOW.

Daca x este LOW si y este MEDIUM LEFT, atunci factorul de restructurare z, este HIGH.

Daca x este MEDIUM LEFT si y este LOW, atunci factorul de restructurare z, este MEDIUM LEFT.

Daca x este HIGH si y este LOW, atunci factorul de restructurare z, este MEDIUM RIGHT.

Eficienta incorporarii fuzzificarii in acest proces, arata cum informatiile obtinute in timpul analizei structurii legaturilor dintr-un site, pot fi sumarizate sub forma unor reguli simple de tipul daca-atunci (if-then) . Se poate observa ca regulile if-then de mai sus pot fi intelese de un utilizator oarecare, fara cunostinte tehnice, deoarece acestea sunt simple conjunctii ale celor doua valori de intrare (WPR index si log rank index) , exprimate in termeni fuzzy in functie de valorile lor, iar consecintele sunt reprezentate de factorii de restructurare z.

In Fig. 7 este aratata reprezentarea fuzzy a 4 pagini diferite, extrase din cele 631. Putem observa cum, pentru pagina /images/index.html factorul de restructurare are valoarea HIGH , cu un grad de apartenenta de 0.95. Aceste valori semnifica faptul ca pagina respectiva este problematica din punct de vedere al structurii link-urilor si i se poate sugera proprietarului site-ului sa revizuiasca structura link-urilor catre aceasta pagina, in cadrul site-ului.

Concluziile experimentului

Prin intermediul acestui experiment s-a demonstrat faptul că logica fuzzy poate fi aplicată valorii abaterii, folosind algoritmii genetici. În primul rând, s-a convertit valoarea abaterii într-un factor de restructurare. În al doilea rând, s-a definit apartenența fuzzy inițială, folosing WPR index, log rank index și factorul de restructurare. În al treilea rând, funcțiile de apartenență au fost optimizate folosind tehnicile algoritmilor genetici. Inultimul rând, folosind cel mai bun cromozom( funcții fuzzy optime de apartenență), s-au derivat reguli fuzzy pentru fiecare pagină WEB în parte și s-au selectat reguli generate dintre aceste. Ca rezultat, s-a putut atribui un factor de restructurare fuzzificat, fiecărei pagini. Reprezentarea fuzzy a fiecărei pagini îl poate ajuta pe proprietarul site-ului WEB să înțeleagă cât de mult trebuie să fie restructrat site-ul.

III Fundamente statistico-matematice

III.1 Probabilități condiționate

Fie (X, Ω, p) un câmp de probabilitate, B ⊂ Ω, p(B)> 0.
Definim pB : Ω R (sau p(∙ | B)) prin:

P(A|B) = pB(A) = , numită probabilitatea lui A, condiționată de B.

În condițiile definiției de mai sus p(A∩B) = p(B) ∙ pB(A).

Demonstrație:

Deoarece ᶲ ⊂ A ∩ B ⊂ B, atunci 0 ≤ pB(A) ≤ 1. De asemenea pB(ᶲ) = 0¸ și pB(X) = 1 sunt evidente. Daca A1 ∩ A2 = ᶲ, atunci și (A1 ∩ B) ∩ (A2 ∩ B) = ᶲ, deci

pB(A1 ∪ A2) =

Două evenimente A și B sunt independente dacă p(A ∩ B) = p(A) ∙ p(B), altfel spus dacă p(A) = pB(A).

A1, A2, …An sunt independente, dacă pentru orice k ≤ n ¸și orice evenimente Ai1, Ai2, … , Aik dintre cele A1, A2, … An date, avem

p(Ai1 ∩ Ai2 ∩…∩ Aik ) = p(Ai1)p(Ai2)…p(Aik) .

Fie (X, Ω, p) un câmp de probabilitate și partiția A1, …, An . Atunci pentru orice B ∈ Ω, avem:

P(B) =

Formula de mai sus se numește formula probabilității totale.

III.2 Teorema lui Bayes

Teorema lui Bayes este una dintre teoremele fundamentale ale teoriei probabilitățiilor, care determină probabilitatea apartenenței evenimentelor și a obiectelor la o anumită grupă. Probabilitatea bayesiană este numele dat mai multor interpretări ale noțiunii de probabilitate, care au în comun ideea de probabilitate ca credință parțială, în loc de cea de frecvență de apariție a unui eveniment. Aceasta permite aplicarea probabilității mai multor propoziții și nu doar cele care au o clasă de referință. Termenul de „bayesian” [7] a început să fie folosit în acest sens cam din 1950. Nu se știe dacă Bayes însuși a îmbrățișat larga interpretare denumită astăzi bayesiană. Este dificil să se evalueze ideile filosofice ale lui Bayes despre probabilitate, deoarece eseul său nu intră în chestiuni de interpretare. Acolo, Bayes definește probabilitatea ca și: “Probabilitatea oricărui eveniment este raportul între valoarea la care ar trebui calculată o așteptare în funcție de întâmplarea unui eveniment, și valoarea lucrului așteptat după ce s-a întâmplat”.

În teoria modernă a utilității, utilitatea așteptată poate fi considerată a fi probabilitatea unui eveniment înmulțită cu răsplata primită în cazul lui. Rearanjarea acestei formule pentru a permite calculul probabilității dă definiția lui Bayes. Așa cum arată Stigler, această definiție este subiectivă și nu necesită evenimente repetate; ea, însă, necesită ca evenimentul în chestiune să fie observabil, fiindcă altfel nu se poate spune deloc că „s-a întâmplat”. Stigler argumentează că Bayes intenționa să obțină rezultate într-o manieră mai limitată decât studiile moderne; dată fiind definiția probabilității după Bayes, rezultatul său privind parametrul unei distribuții binomiale are sens doar în măsura în care se poate paria pe consecințele sale observabile.

În cazul mașinilor de învățare sunetm interesați de determinarea celei mai bune ipoteze pentru un spațiu H, având în vedere datele de antrenare D. În acest context, atunci când vorbim despre cea mai bună ipoteză ne referim la cea mai probabilă ipoteză având datele D și alte cunoștiințe inițiale despre probabilitățiile diverselor ipoteze din H. Teorema lui Bayes conferă o metodă directă de a calcula aceste probabilități. Mai precis, ea furnizează o manieră de a calcula probabilitatea unei ipoteze bazată pe probabilitatea anterioară a acesteia, denotată din diverse date observate având în vedere ipotezele .

Pentru a putea exprima în termeni matematici teorema lui Bayes, avem nevoie de anumite notații. Vom considera o ipoteză h din spațiul ipotezelor H. Prin P(h) vom nota probabilitatea inițială a ipotezei h. La probabilitatea anterioară observării datelor de antrenare D ne vom referi prin P(D), iar la probabilitatea de a observa datele D în raport cu ipoteza h, prin P(D|h). Deși trebuie să avem în vedere toate acestea, în lumea mașinilor de învățare suntem interesați de o altă probabilitate notată prin P(h|D). Aceasta este probabilitatea ulterioară a lui h, aceea ca ipoteza h să se petreacă având în vedere datele de antrenare D. Aceasta reflectă influența datelor de antrenare asupra decizilor care pot fi luate, în contrast cu P(h), probabilitate independent de D.

Teorema lui Bayes este piatra de temelie a învățarii bayesiene deoarece ea furnizează metoda de a calcula probabilitatea ulterioară, P(h|D), din P(h), P(D) și P(D|h), astfel:

Din această ecuație, care concentrează raționamentul bayesian, se poate observa faptul că P(h|D) crește deodată cu P(h) și P(D|h), și descrește atunci când P(D) crește.

În numeroase discuții despre teorema lui Bayes este posibil să existe susținători ai psihologiei cognitive care să afirme faptul că oamenii nu iau suficient de mult în considerare frecvențele anterioare. Acest lucru înseamnă că atunci când oamenii abordează o problemă pentru care există o oarecare indicație către evaluarea ca și adevărată a unei condiții, ei tind să judece probabilitatea acelei condiții numai după cât de bine se potrivește indicația cu ea, fără a lua în considerare frecvența anterioară a condiției.

În multe scenari de învățare, se consider câteva seturi de ipoteze candidat H și interesul se axează asupra găsirii celei mai probabile ipoteze h din H, având în vedere datele de antrenare D. Fiecare dintre aceste ipoteze de probabilitate maximă este numită “ipoteză maximă posterioară” (maximum a posteriori hypothesis-MAP). Pentru determinarea MAP se folosește teorema lui

Bayes pentru a calcula probabilitatea ulterioară a fiecărei ipoteză candidat. Mai precis se poate spune ca o ipoteza hMAP este ipoteză maximă posterioară dacă:

hMAP  arg max (arg max )

hH

=arg max

hH

=arg max

hH

După cum se poate observa în cea din urmă formă a ecuației care exprimă hMAP lipsește termenul P(D). Acest fapt este deoarece P(D) este o constantă independentă de valoarea pe care o ia h.

Există în practică și cazuri în care toate ipotezele dintr-un spațiu al problemei H au aceeași probabilitate: P(hi)=P(hj), pentru oricare ar fi hi, hj din H. În aceste situații ecuația anterioară poate fi simplificată sub forma:

hMAP  arg max

hH

Această ipoteză se mai numește și ipoteza de probabilitate maximă, P(D|h) fiind numită probabilitatea maximă.

Deoarece teorema lui Bayes este mult mai generală, ea poate fi la fel de bine aplicată pe orice set H de propuneri ce se exclude reciproc și a căror sumă de probabilitate este 1. Datorită faptului că această teoremă furnizează principala manieră de a calcula probabilitatea ulterioară a fiecărei ipoteze luând în calcul datele de antrenare, poate fi folosită ca și bază pentru un algoritm simplu care calculează probabilitatea pentru fiecare ipoteză și o afișează pe cea mai probabilă. Pe baza unui studiu realizat s-a observat că în anumite condiții, mai mulți algoritmi returnează aceeași ipoteză ca și această forță brută Bayesiană, în ciuda faptului că acestea nu manipulează în mod direct probabilități și sunt considerabil mai eficiente.

Să presupunem câteva spații finite de ipoteze H, definite peste spațiul instanță X, în care sarcina este de a învăța unele concepe țintă: c : X  [0,1]. La fel ca oricărui elev dispus să învețe, și la aces elev virtual trebuie să îi fie furnizate cateva secvențe de exemple, date de antrenare. Considerăm aceste date sub forme de grupuri de genul: (x1,d1), (x2,d2), …, (xm,dm), unde xi este o instanță din X, di o valoare țintă pentru xi și di=c(xi). Cu presupunerea simplă care nu restrânge generalitatea, și anume că setul de instanțe deținut (x1, x2, …, xm) este fix astfel încât setul de date de antrenament D poate fi scris ca și o secvență de valori țintă (d1, d2,…, dm).

Proiectarea unui algoritm simplu, bazat pe conceptul de învățare și pe teorema lui Bayes, care să returneze o ipoteză posterioară maximă, poate fi facut astfel:

Pentru oricare h ∈ H, calculează:

Returnează ipoteza hMAP cu cea mai mare probabilitate posterioară:

hMAP  arg max

hH

IV Descrierea metodelor și tehnicilor utilizate

IV.1 Invățarea supervizată

Învățarea supervizată este una dintre categoriile principale de probleme de învățare, iar obiectivul ei este acela de a modela o funcție din datele de antrenament pe care le primește [8]. Datele de antrenament sunt o mulțime de perechi, fiecare pereche fiind compusă dintr-un obiect de intrare (de obicei un vector) și valoarea de ieșire dorită. Cazul optim al rezolvării unei probleme de acest tip va permite algoritmului creat pe baza setului de date de antrenament, să generalizeze de la aceste date până la situații cu care nu s-a mai confruntat, cu rezultate mulțumitoare.

IV.1.1 Pașii rezolvării unei probleme de învățare supervizată

Pentru a rezolva o problemă de învățare supervizată, trebuie efectuați următorii pași [8]:

Determinarea tipului datelor din setul de antrenament. Utilizatorul trebuie să decidă ce tip de date îi este necesar pentru a fi folosit ca set de antrenament.

Colectarea datelor pentru setul de antrenament. Setul de date de antrenament trebuie să fie relevant în aflarea modelului pentru aplicarea acestuia în lumea reală.

Determinarea reprezentării atributelor obiectului de intrare. De cele mai multe ori intrarea este transformată într-un vector de caracteristici, care conține atribute ce descriu obiectul. Numărul de însușiri nu trebuie să fie foarte mare, dar trebuie să fie suficient pentru a putea prezice rezultatul cu exactitate mare.

Determinarea structurii funcției de învățare și alegerea algoritmului corespunzător de învățare (exemple de algoritmi de învățare: Naive Bayes, SVM, Rețele Neuronale etc.).

Aplicarea algoritmului de învățare pe setul de antrenament.

Evaluarea acurateței funcției rezultate pentru un set de testare, diferit de setul de antrenare.

IV.1.2 Învățarea prin clasificare

Învățarea prin clasificare [10] este un tip de problemă de învățare supervizată sau semi-supervizată, al cărei obiectiv este de a crea automat un model din setul de date de antrenament. Datele pentru antrenarea modelului constă într-o listă de obiecte cu o anumită ordine între ele, ordine care este de obicei indusă prin introducerea unei valori numerice sau ordinale, sau a uneia binare (de exemplu „fals” sau „adevărat”) pentru fiecare înregistrare. Clasificarea modelului produce o permutare a elementelor listei într-o nouă listă, ceea ce într-o anumită măsură este similar procesului de ierarhizare a datelor setului de antrenament.

Acestă extindere a învățării supervizate este o cercetare aproximativ tânără, care a apărut și a crescut în ultimul deceniu. Domeniile în care această tehnică a fost aplicată sunt: regăsirea informației, traducerile automate, clasificarea documentelor, clasificarea paginilor web în funcție de conținut etc..

IV.2 Clasificatorul Naive Bayes

Una dintre cele mai vechi metode de clasificare este dată de Clasificatorul Naive Bayes(CNB). Deși simplu în structură și bazat pe presupuneri nerealiste, CNB a surclasat, deseori, tehnici mult mai sofisticate. De fapt, datorită structuri sale extrem de simple, CNB este o alegere foarte atractivă atunci când vine vorba despre un set de variabile independente mare. În ciuda simplicității sale, CNB este rareori folosit în practică, cele mai populare pachete software statistice neavând un modul de CNB. Motivele pentru acestea ar fi pe de o parte faptul căci clasele de probabilitate părtinitoare ar putea fi o problemă reală pentru aplicațiile de modelare în care accentul nu cade neaparat pe clasificare. Un alt motiv este acela că CNB estimează sub presupunearea că predicțiile sunt independent condiționate, având în vedere valorile țintă. Ca și un rezultat, relațiile dintre variabilele dependente și predicții sunt estimate în mod izolat, fără a lua în calcul covarianța dintre predicții. Prin urmare, CNB nu este capabil să aproximeze funcții de regresie multivariate și ca un instrument de explorare a datelor nu se adaugă mai multe informații decât o analiză univariată. În anumite domenii performanțele CNB au fost comparabile cu cele ale rețelelor neuronale sau ale învățarii în arbori de decizie. Succesul CNB, în prezența carcteristicilor de dependență, poate fi explicată astfel: optimalitatea în termeni de pierdere zero-unu(eroarea de clasificare) nu este neaparat legată de calitatea de a potrivi o distribuție de probabilitate. Mai degrabă, o clasificare optimă se obține atâta timp cât ambele distribuții efective estimate sunt de accord cu privire la clasa cea mai probabilă.

Această metodă extrem de practică a învățarii Bayesiene se aplică pentru sarcinile de învățare în cazurile în care fiecare instanță x este descrisă printr-o conjuncție de valori și fiecare funcție țintă f (x) poate lua orice valoare dintr-un anumit set finit de valori, V. Se pornește de la un set de date de antrenare pentru funcția țintă și o nouă instanță descrisă printr-un n-uplu de valori atribut (a1,a2,…, an). Sistemul este solicitat să facă o predicție cu privire la valoarea țintă sau la clasa din care face parte noua instanță. Abordarea Bayesiană pentru clasificarea noii instanțe constă în a îi atribui cea mai probabilă valoare țintă având date valorile atributelor care descriu noua instanță. Să notăm cea mai probabilă valoare țintă cu vMAP și valorile atributelor cu (a1 , a2 ,…, an ) . În acest caz avem relația:

vMAP  arg max P(v j | a1 , a2 ,…, an ) .

v j V

Putem folosi teorema lui Bayes pentru a rescrie relația, și vom obține:

arg max P(a1 , a2 ,…, an | v j ) * P(v j )

j V

Acum se pune problema de a estima cele două probabilități care apar în relația de mai sus pe baza datelor de antrenare. Este relativ simplu de estimat probabilitatea P(v j ) , aceasta făcându-se prin simpla numărare a frecvenței cu care apare fiecare valoare țintă v j în datele de antrenare. Cu toate astea, estimarea diferiților termeni P(a1, a2 ,…, an | v j ) în această manieră nu este posibilă dacă setul de antrenare nu este extrem de mare. Problema este că numărul termenilor de acest fel este egal cu numărul instanțelor înmulțit cu numărul posibilelor valori țintă. De aceea trebuie să vedem fiecare instanță în spațiul instanțelor de mai multe ori pentru a obține estimări de date fiabile.

CNB se bazează pe simpla presupunere că valorile atributelor sunt independent condiționate de valorile țintă. Altfel spus, presupunerea este că având valorile țintă ale instanțelor, probabilitatea de a observa îmbinarea a1,a2,…,an este egală cu produsul probabilitățiilor pentru atributele individuale[1]: P(a1 , a2 ,…,a n | v j ) = .

În aceste condiții, formula pentru determinarea valorii țintă de probabilitate maximă este: vNB = arg max P(v j ) * , unde prin vNB ne referim la valoarea țintă de ieșire pentru CNB.

Este observabil faptul că în cazul CNB numărul termenilor P(ai | v j ) distincți care trebuiesc estimați din datele de antrenare este același cu numărul de atribute cu valori distincte înmulțit cu numărul de valori țintă distincte. Acest număr este considerabil mai mic decăt numărul de termeni P(a1, a2 ,…,an | v j ) pe care i-am fi estimat inițial.

Învățarea CNB implică un pas de învățare în care diferiți termeni P(v j ) și P(ai | v j ) sunt estimați, bazându-ne pe frecvența lor peste datele de antrenare. Setul acestor estimări corespunde ipotezelor care au fost învățate în partea de antrenare. Aceste ipoteze sunt apoi folosite pentru a clasifica fiecare nouă instanță prin aplicarea ecuației CNB. Oricând este îndeplinită ipoteza de clasificare naivă Bayes cu privire la independența condițională, vNB este identic cu clasificarea data de ipoteza maximă corespunzătoare(MAP).

Dacă se vorbește despre problemele de clasificare binară, în care funcția țintă este 0 sau 1, sunt cunoscute câteva limitări a CNB. El poate învăța doar funcții liniare ale discriminantului și de aceea este totdeauna suboptimal pentru concepe non-liniar separabile. În cazul în care funcția țintă poate avea mai mult de două valori posibile, CNB este capabil să învețe și funcții polinomiale. Acesta este motivul pentru care este necesară separabilitatea polinomială, dar nu este condiție suficientă pentru optimalitatea CNB pentru concept cu un domeniu de caracteristici finit.

În ciuda limitărilor sale, CNB s-a dovedit a fi optim pentru unele clase de concepte care au un grad ridicat de dependențe facilitate, cum ar fi concepte disjunctive și conjunctive. Tocmai de aceea se poate spune că CNB este optimal pentru orice două clase de concepte cu caracteristici nominale care atribuie clasei 0 exact un exemplu, și clasei 1 un alt exemplu, cu probabilitatea 1[11]. O observație aproape evidentă este aceea că performanța CNB scade odată cu creșterea numărului de clase.

Surprinzător, precizia CNB nu este direct corelată cu gradul de dependențe facilitate,

masurată ca informarea reciprocă între clasele condiționate de caracteristici. În schimb, un predictor de precizie mai bună este pierderea de informații care conțin caracteristici despre clase, atunci când se presupune un model naiv Bayes. Cu toate acestea, în continuare studiul empiric și teoretic este necesar pentru a înțelege mai bine relația dintre aceste metrici de informații teoretice și comportamentul Bayes naiv. Direcțiile suplimentare includ, deasemenea, analiza naivă Bayes cu privire la aplicabilitatea practică, care are dependențe aproape deterministe, caracterizând alte regiuni ale optimalității naiv Bayes și studiul efectului diferiților parametri de date cu privire la eroarea naiv Bayes. În cele din urmă, o mai bună înțelegere a impactului ipotezei de independență asupra clasificări poate fi utilizată pentru a elabora tehnici de aproximare pentru o mai bună învățare a clasificatorilor Bayesieni, și pentru deducția probabilistică, spre exemplu, pentru găsirea probabilității maxime.

O diferență interesantă între metoda de învățare naivă Bayes și alte metode este aceea că în acest caz nu există o căutare explicită în spațiul posibilelor ipoteze. În schimb, ipoteza este formată fără căutare, prin simpla numărare a frecvențelor diferitelor date combinate cu datele de antrenare.

IV.3 Support Vector Machines (Mașini cu suport vectorial)

Mașinile cu suport vectorial reprezintă o metodă de clasificare introdusă în anul 1992 de către Boser, Guyon și Vapnik [12]. Clasificatorul care foloseste această tehnică este folosit în mai multe discipline, datorită acurateței ridicate și a faptului că se descurcă bine atunci când întâlnește date cu multe dimensiuni, dar și pentru flexibilitatea în modelarea diferitelor surse de date. Mașinile cu suport vectorial aparțin unei categorii de „metode cu nucleu”. O astfel de metodă este un algoritm care depinde de date doar prin produse scalare. Atunci când este necesar, produsul scalar poate fi înlocuit cu o funcție nucleu, care calculează acest produs scalar într-un posibil spațiu de caracteristici multidimensional. Această abordare are două avantaje. Primul dintre ele este capacitatea de a genera decizii neliniare asupra limitelor, folosind metode construite pentru clasificatorii liniari. Al doilea avantaj îl constituie faptul că folosirea funcșiilor nucleu permit utilizatorului să aplice un clasificator datelor care nu au o reprezentare a spațiului vectorial de dimensiune fixă. Printre primele exemple de astfel de date în bioinformatică se numără ADN-ul și structura proteinelor.

Mașinile cu suport vectorial construiesc un hiperplan sau o mulțime de hiperplane într-un spațiu cu mai multe dimensiuni sau cu un număr infinit de dimensiuni, care pot fi utilizate pentru clasificare, regresie sau alte sarcini. Intuitiv, o bună separare este obținută de hiperplanul care are cea mai mare distanță până la cea mai apropiată dată de antrenament reprezentată indiferent de clasa din care aceasta face parte (numită si marjă 2 functională), având în vedere că în general cu cât este mai mare marja, cu atât este mai redusă eroarea de generalizare a clasificatorului. Chiar dacă problema inițială este specificată într-un spatiu finit dimensional, se întâmplă de multe ori ca mulțimile care trebuie distinse să nu fie separabile liniar în acel spatiu. Din acest motiv a fost propus ca spațiul finit original să fie potrivit într-unul mai mare ca dimensiune, separarea fiind probabil mai usor de făcut în acest nou spațiu. Pentru a păstra un efort computațional rezonabil, potrivirile folosite de schemele mașinilor cu suport vectorial sunt construite în așa fel încât să poată asigura că produsele scalare vor putea fi calculate cu usurință în ceea ce priveste variabilele din spatiul original, prin definirea unei funcții nucleu selectate să satisfacă cerințele problemei [13]. Hiperplanele din spațiul cu mai multe dimensiuni sunt definite prin multimi de puncte al căror produs scalar cu un vector din acel spațiu este constant. Vectorii care definesc hiperplanurile pot fi aleți ca fiind combinații liniare cu parametrii αi ai imaginilor vectorilor de caracteristici care există în baza de date. Folosind această alegere a hiperplanului, punctele din spațiul caracteristicilor care sunt potrivite în hiperplan sunt definite prin relația . În cazul în care devine mai mic pe măsură ce creste si mai mult fată de , fiecare element din sumă măsoară gradul de apropiere al punctului de test fată de punctul corespunzător din baza de date . În aceste condiții, suma nucleelor poate fi utilizată în vederea măsurării apropierii relative a fiecărui punct de test în comparație cu punctul original aparținând uneia dintre mulțimile ce trebuie distinse.

Mașinile cu suport vectorial sunt modele de învățare supervizată cu algoritmi de invățare asociați care analizează date și recunosc tipare.

Modelarea matematică a SVM

Considerăm o populație ale cărei obiecte sunt studiate din punctul de vedere a n caracteristici. Un obiect este reprezentat de un punct (x1,…,xn) Rn,
x1,…,xn fiind valorile celor n caracteristici pentru obiectul studiat.

Definirea problemei:

Se fac r măsurători asupra unui eșantion din populație. Dupa cum s-a văzut, observațiile sunt reprezentate de puncte din Rn .

Datele de intrare obținute (date de antrenare) se împart în două clase D1 ⊆ E1, D2 ⊆ E2 . (D= D1 ∪ D2 = datele de intrare).

Se pune problema clasificării unor date noi: pornind de la datele de antrenare, să se spună dacă o observație nouă este în E1 sau în E2. D=spațiul intrărilor.
Spațiul intrărilor este linear separabil dacă există un hiperplan H al lui Rn ce separă D1 și D2 .

Dificultăți în rezolvarea problemelor de clasificare:

Pentru clasificare se pot utiliza mai mulți separatori ai claselor.

Spațiul intrărilor nu este liniar separabil.

V Studiu de caz

V.1 Descrierea problemei

PageRank este un instrument de analiză a legăturilor(link-uri), care atribuie o valoare numerică fiecărei pagini web, cu scopul clasificării siteurilor care sunt indexate de către motorul de căutare Google. Algoritmul poate fi aplicat oricărei colecții de entități din cadrul unei citări sau referiri reciproce. Valoarea numerică atribuită unui element S se mai numește și PageRank-ul lui S și este notat PR(S).

Acest indicator ia valori în intervalul 0-10, pentru fiecare pagină de pe Internet. În graficul de mai jos, se pot observa doar valori între 0 și 7, deoarece 8, 9 și 10 sunt cel mai greu de obținut, iar uneori, aproape imposibil.

Valorile luate de Google PageRank sunt urmatoarele:

0 – pagina respective nu este listată pe Google, sau a fost ștearsă;

1 – calificativ foarte scăzut;

2 – calificativ scăzut, singurul avantaj este că există șanse de îmbunătățire;

3 – calificativ mediu, obținut de majoritatea site-urilor;

4 – calificativ peste medie;

5 – calificativ bun, cu ajutorul căruia site-ul respectiv poate ajunge pe prima pagină a motorului de căutare Google, în funcție de termenii introduși ;

6 – calificativ mai mult decât bun;

7 – calificativ foarte bun, obținut de site-uri de top;

8 – obținut de site-uri precum ESPN.com, sau imdb.com;

9 – obținut de site-uri precum facebook.com, youtube.com, sau google.com;

10 – obținut de un număr foarte mic de site-uri, 9 la număr până în momentul actual. Acestea sunt: twitter.com, usa.gov, get.adobe.com/reader, hhs.gov, addthis.com/bookmark, europeana.eu/portal, eua.be și un.org/en .

PageRank-ul unei pagini se bazează pe numărul de link-uri de la site-uri externe, precum și pe PageRank-ul paginilor care furnizează acele link-uri. Numărul de factori care influențează PageRank-ul este de aproximativ 250. Printre aceștia se numără: vechimea domeniului web, numărul de domenii externe care au link-uri catre pagina respectivă, numărul de domenii educaționale și guvernamentale care au link-uri catre pagina respectivă, numărul de utilizatori unici/zi, timpul mediu petrecut de fiecare utilizator/zi, timpul de încărcare al paginii, cuvintele care apar în titlul site-ului etc.

În lucrarea de față sunt considerate primele 80 de domenii web,cu PageRank mai mare sau egal decât 3, în topul preferințelor utilizatorilor din România, conform site-ului alexa.com. Cele 80 de domenii sunt caracterizate de următoarele 8 atribute cantitative: numărul de link-uri de la pagini externe, numărul de domenii externe care au link-uri catre domeniul respectiv, numărul de pagini educaționale care au link-uri către domeniul analizat, numărul de pagini guvernamentale care au link-uri către domeniul analizat, vechimea domeniului web, numărul de vizualizări/vizitator, timpul mediu petrecut de fiecare utilizator/zi și durata de încărcare a paginii, precum și de variabila calitativă Google PageRank.

Înregistrările din setul de date analizat, sunt ilustrate in imaginea de mai jos:

Setul de date utilizat, a fost alcătuit cu ajutorul site-urilor: www.alexa.com/topsites/countries/RO și checkpagerank.net.

Valorile atributelor diferă, în funcție de caracteristicile acestora. Astfel, primele 4 atribute: External Backlinks, Referring Domains, EDU Backlinks și GOV Backlinks, pot atinge valori inclusiv de ordinul miliardelor. Variabila Domain Age, conține valori reprezentate în ani, reprezentând vechimea domeniului analizat. Daily Pageviews/Visitor este o valoare de ordinul unităților, sau al zecilor, calculată ca raport între numărul total de vizionări al paginii respective și numărul zilnic de utilizatori. Daily time on site/Visitor, reprezintă timpul mediu petrecut de un utilizator pe site, acesta fiind calculat ca raport între timpul total petrecut de toți utilizatorii dintr-o zi, pe site și numărul de utilizatori. Unitatea de măsură pentru acest atribut, este minutul. Variabila Loading time, cuantifică durata în care se încarcă pagina respective, în secunde. În ultimul rând, variabila calitativă Google PageRank, despre care am discutat mai sus, reprezintă indicatorul folosit în clasificarea siteurilor care sunt indexate de către motorul de căutare Google. Aceasta conține valori între 3 și 10 inclusiv.

V.2 Reprezentarea și analiza statistică a datelor

Pentru o mai înțelegere mai exactă a valorilor atributelor incluse în analiză, vom folosi o scală ordinală pentru reprezentarea acestora, conform tabelelor de mai jos:

Noul set de date va avea următoarea reprezentare:

Analiza statistică a variabilelor incluse în cercetare, este reprezentată în tabelul de mai jos:

Observăm cum, în cazul variabilei external_backlinks, mediana este egală cu 3, ceea ce înseamnă că 50% dintre valori sunt mai mici decât 10,000,000.

În cazul variabilei referring_domains, se observă cum 50% dintre valori sunt mai mici decât 10,000. În același timp, 25% dintre valori sunt mai mari decât 1,000,000 , acestea caracterizând domenii perecum facebook.com, youtube.com, twitter.com sau wikipedia.org .

În cazul variabilei edu_backlinks, la fel ca și în cazul variabilei referring_domains, observăm cum 25% dintre valori sunt mai mari decât pragul 4, adică 10,000,000.

Valorile variabilei gov_backlinks au o medie de 1.875,adică între 10,000 și 100,000, ceea ce înseamnă că valorile scăzute predomină. Acest aspect se poate observa și datorită medianei, care ne spune că 50% dintre valori sunt mai mici decât 1 (< 10,000) , iar 75% dintre valori sunt mai mici decât 3(<500,000).

Analizând variabila domain_age, observăm cum, doar 25% dintre domenii au o vechime mai mare de 19 ani. Printre acestea se numără yahoo.com, amazon.com, sau microsoft.com

Variabila daily_pgv ne arată cum aproximativ 25% dintre domenii, au un număr foarte mare de vizualizări zilnice/vizitator, de peste 11.

La fel ca și în cazul variabilei daily_pgv, variabila daily_time ne arată cum timpul mediu de activitate/vizitator/zi, pentru aproximativ 25% dintre domenii, este foarte mare, de peste 9 minute.

Variabila loading_time ne arată cum, doar 25% dintre domenii au un timp de încărcare sub timpul mediu (< 1.1).

Înregistrările au următoarea distribuție între clase:

V.3 Determinarea seturilor de antrenare și testare

Domeniile web alese, vor fi clasificate în funcție de Google PageRank, folosind unul dintre clasificatorii: Naïve Bayes, sau Support Vector Machines(SVM). Pachetul software și limbajul de programare ales pentru realizarea clasificării și a previzionărilor este R.

R, împreuna cu librăriile sale, implementează o mare varietate de tehnici statistice și grafice, incluzând modelare liniară și non-liniară, teste statistice, analiza seriilor de timp, clasificare, clusterizare etc.

Setul de date se împarte în 3 subseturi, astfel: set de antrenare a modelului, care va conține 50% dintre înregistrări, set de alegerea a algoritmului utilizat pentru clasificare, care va conține 25% dintre înregisrări și un set de testare a algoritmului, care va conține restul de 25% dintre înregistrări.

Setul de antrenare:

> records <- 1:nrow(web)

> records

> trainrecords <- sample(records, trunc(length(records)*(50/100)))

> trainrecords

[1] 43 45 15 11 62 56 50 55 38 52 29 78 8 64 30 65 40 7 77 12 25 79 48 44 41 10 60 9 71 3 14 42 34 32 2 54 68 51 74 28

Numerele de mai sus au fost alese aleator, din totalul celor 80 de înregistrări. Aceste numere reprezintă numerele de ordine ale înregistrărilor din setul de antrenare.

Setul de antrenare are următoarea formă:

Setul de alegere a algoritmului:

> algrec <- setdiff(records, trainrecords)

> algrec

> algtestrec <- sample(algrec, trunc(length(algrec)*(50/100)))

> algtestrec

[1] 18 73 46 63 22 23 59 66 31 75 49 67 17 4 80 47 70 58 53 5

Dintre înregistrările rămase după alegerea setului de antrenare, alegem aleator 50% pentru construirea unui set de alegere a clasificatorului.

> algtestSet <- web[algtestrec,]

> algtestSet

Setul de alegere a algoritmului are următoarea reprezentare:

Setul de testare:

> setrec <- setdiff(algrec, algtestrec)

> setrec

[1] 1 6 13 16 19 20 21 24 26 27 33 35 36 37 39 57 61 69 72 76

Cele 25% dintre înregistrări, rămase, vor fi utilizate pentru testarea clasificatorului folosit la previzionarea rank-ului domeniilor.

> testSet <- web[setrec,]

> testSet

Setul de testare are următoarea reprezentare:

V.4 Antrenarea clasificatorilor

Clasificatorul Naive Bayes:

> classifier <- naiveBayes(trainSet[,2:9], factor(trainSet[,10]))

> classifier

Construim modelul de clasificare pe baza setului de antrenare, utilizând ca variabilă factor, variabila google_page_rank.

Probabilitățile a-priori calculate de clasificator, ne arată faptul că un nou obiect, are o probabilitate(0.5) mai mare să fie clasificat în clasa ‘mediu’, decât în celelalte 2 clase. Probabilitățile ca un nou obiect să fie clasificat într-una din celelalte 2 clase sunt: 0.375 pentru clasa ‘mare’ și 0.125 pentru clasa ’mic’.

Clasificăm obiectele din subsetul algtestSet într-una din cele 3 clase, pe baza modelului creat anterior cu ajutorul setului de antrenare.

> predicted <- predict(classifier, algtestSet[,2:9])

> predicted

> df <- data.frame(algtestSet$url, algtestSet$google_page_rank, predicted)

> df

Adăugăm clasele previzionate într-un data frame, alături de numele domeniului pentru care a fost previzionată si de clasa reală.

Observăm cum, majoritatea domeniilor cu un PageRank ‘mediu’ au fost incluse în clasa previzionată ‘mic’.De exemplu, ’mobile.de’, care face parte din clasa reală ‘mediu’, a fost previzionat în clasa ‘mic’. Confuziile apar deoarece atributele luate în calcul în construirea modelului reprezintă doar o parte din atributele folosite de Google în calcularea PageRank.

Construim o matrice de confuzie pentru a vedea care clase au fost previzionate corect și care clase au fost previzionate eronat, și în ce clase au fost previzionate acestea.

> matrice <- table(predict(classifier, algtestSet[,2:9]), algtestSet[,10])

> matrice

Instanțele clasei ‘mare’ au fost toate previzionate corect, în clasa ‘mare’. Observăm că instanțele clasei ‘mediu’, din 14, doar 2 au fost previzionate corect în clasa ‘mediu’, restul de 12 au fost previzionate eronat, în clasa ‘mic’. Instanțele din clasa ‘mic’ au fost ambele previzionate corect, în clasa ‘mic’.

Support Vector Machines(SVM)

Funcție cu nucleu radial

> classifierrad <- svm(formula = google_page_rank~., data = trainSet, kernel="radial")

> classifierrad

Observăm că au fost obtinuti 34 de vectori suport, împărțiți între cele 3 clase, după cum se poate vedea în outputul din R, de mai sus.

Funcția nucleu implicită este de tip radial, cu parametrii impliciți: cost C=1 și un parametru gamma de care depinde funcția nucleu radială. Functia nucleu radial este de forma:

Clasificăm obiectele din subsetul algtestSet într-una din cele 3 clase, pe baza modelului creat anterior cu ajutorul setului de antrenare.

> predictrad <- predict(classifierrad, algtestSet[,-10])

> predictrad

> df <- data.frame(algtestSet$url, algtestSet$google_page_rank, predictrad)

> df

Vom obține un data frame cu 3 coloane: numele domeniului, clasa reală căreia îi aparține și clasa previzionată cu ajutorul clasificatorului SVM, cu funcție nucleu radială:

Observăm că ambele domenii aparținând clasei reale ‚mic’, au fost previzionate în clasa ‚mediu’. Cele două domenii sunt: ‘adcash.com’ și ‘flashscore.ro’.

Construim o matrice de confuzie pentru a vedea care clase au fost previzionate corect și care clase au fost previzionate eronat, și în ce clase au fost previzionate acestea.

> matricerad <- table(pred=predictrad, true=algtestSet[,10])

> matricerad

Observațiile din clasa reală ‘mare’, au fost toate 4 previzionate corect.

Toate cele 14 observații aparținând clasei reale ‘mediu’, au fost, de asemenea, previzionate corect.

Ambele observații din clasa reală ‘mic’ au fost previzionate eronat, în clasa ‘mediu’.

Funcție cu nucleu liniar

> classifierlin <- svm(formula = google_page_rank~., data = trainSet, kernel="linear")

> classifierlin

> summary(classifierlin)

Observăm că au fost obținuți 24 de vectori suport, împărțiți între cele 3 clase, după cum se poate vedea în outputul din R, de mai sus.

Funcția nucleu este de tip liniar, cu parametrii impliciți: cost C=1 și un parametru gamma de care depinde funcția nucleu liniară.

Clasificăm obiectele din subsetul algtestSet într-una din cele 3 clase, pe baza modelului creat anterior cu ajutorul setului de antrenare.

> predictlin <- predict(classifierlin, algtestSet[,-10])

> predictlin

> df <- data.frame(algtestSet$url, algtestSet$google_page_rank, predictlin)

> df

Vom obține un data frame cu 3 coloane: numele domeniului, clasa reală căreia îi aparține și clasa previzionată cu ajutorul clasificatorului SVM, cu funcție nucleu liniară:

Observăm că un singur domeniu a fost clasificat eronat, din clasa reală ‘mic’ în clasa previzionată ‘mediu’. Acest domeniu este ‘adcash.com’.

Construim o matrice de confuzie pentru a vedea ce clase au fost previzionate corect și ce clase au fost previzionate eronat, și în care clase au fost previzionate acestea.

> matricelin <- table(pred=predictlin, true=algtestSet[,10])

> matricelin

Observăm că singura eroare de clasificare este reprezentată de previzionarea unui obiect din clasa reală ‘mic’ în clasa ‘mediu’. În rest, toate celelalte obiecte au fost previzionate corect.

Comparăm cei doi clasificatori, pentru a-l alege pe cel cu acuratețea mai mare, în vederea efectuării unei predicții a claselor, pe setul de testare.

Vom utiliza următoarele comenzi în R:

#determinarea ratei de exactitate a modelului bazat pe clasificatorul Naïve Bayes:

> classAgreement(matrice)

> class <- classAgreement(matrice)$diag

> class

[1] 0.4 rata de exactitate a modelului

#determinarea ratei de exactitate a modelului bazat pe clasificatorul SVM cu nucleu radial:

> classAgreement(matricerad)

> classsvm <- classAgreement(matricerad)$diag

> classsvm

[1] 0.9 rata de exactitate a modelului

#determinarea ratei de exactitate a modelului bazat pe clasificatorul SVM cu nucleu liniar:

> classAgreement(matricelin)

> class <- classAgreement(matricelin)$diag

> class

[1] 0.95 rata de exactitate a modelului

Din output-urile de mai sus observăm că rata de exactitate a modelului bazat pe clasificatorul SVM cu nucleu liniar este mai mare decât rata de exactitate a modelului bazat pe clasificatorul Naïve Bayes și a modelului bazat pe clasificatorul SVM cu nucleu radial:

0.95 > 0.9 > 0.4

V.5 Predicția claselor pe setul de testare

Datorită acestui rezultat, în continuare, vom utiliza clasificatorul SVM cu nucleu liniar, pentru efectuarea unei predicții a claselor, pe setul de testare.

>predictionsvm <- predict(classifierlin, testSet[,-10])

>predictionsvm

>df <- data.frame(testSet$url, testSet$google_page_rank, predictionsvm)

>df

Vom obține un data frame cu 3 coloane: numele domeniului, clasa reală căreia îi aparține și clasa previzionată cu ajutorul clasificatorului SVM, cu funcție nucleu liniar:

Obținem matricea de confuzie care afisează valorile reale și valorile previzionate, astfel:

> matricesvm <- table(pred=predictionsvm, true=testSet[,10])

> matricesvm

Observațiile din clasa reală ‘mare’, au fost toate 5 previzionate corect.

Cele 13 observații aparținând clasei reale ‘mediu’, au fost previzionate astfel: 11 corect, în clasa ‘mediu’ și 2 eronat, în clasa ‘mic’.

Observațiile din clasa reală ‘mic’ au fost previzionate astfel: 1 corect, în clasa ‘mic’ și 1 eronat, în clasa ‘mediu’.

Obținem rata de exactitate a modelului, folosind functia classAgreement() , astfel:

>classAgreement(matricesvm)

>classvm <- classAgreement(matricesvm)$diag

>classvm

[1] 0.85

Rata de exactitate a modelului este de 85%, procent justificat prin prisma faptului că în cadrul analizei de mai sus, au fost incluși doar 8 din cei peste 200 de factori luați în considerare de Google, la calcularea PageRank.

CONCLUZII

Caracteristica principală a tehnologiei data mining este reprezentată de aplicarea unor metode si algoritmi cu scopul identificării și extragerii unor modele din datele stocate in volume din ce în ce mai mari. Un rol important in acest proces îl prezintă pasul de extragere/transformare/încărcare (ETL – Extract Transform Load) a datelor – datele sunt selectate din diferite baze de date, sau extrase din fisierele HTML ale paginilor web (în cazul Web Mining), folosind instrumente software de tipul Web Crawlers.

Domeniul web mining a cunoscut o evoluție în ultima vreme datorită acurateții aplicatiilor de clasificare și a progresului științific, dar și a faptului că rețeaua web este într-o continuă expansiune.

Studiul de caz realizat în această lucrare este întocmai o problemă de clasificare, aplicată primelor 80 de domenii web în preferințele utilizatorilor din România, conform site-ului alexa.com. Clasele utilizate în analiză au fost reprezentate de coeficientul Google PageRank(un număr de la 3 la 10), în vederea clasificării siteurilor care sunt indexate de către motorul de căutare Google.

Agoritmii de clasificare folosiți în analiză au fost Naïve Bayes și SVM cu nucleu radial și nucleu liniar. În urma rulării unui set de scripturi în R, am ajuns la concluzia că cea mai mare rată de exactitate o are modelul previzionat cu ajutorul clasificatorului SVM cu nucleu liniar, procentul fiind de 95%.

Metodele de clasificare din cadrul Web Mining îl pot ajuta pe proprietarul site-ului web să înțeleagă cat de mult trebuie să fie restructrat site-ul, pentru a obține un PageRank mai mare și pentru a urca în ierarhia de indexare a motorului de căutare Google.

O posibilitate de dezvoltare a acestui studiu o constituie construirea unui set de date care să conțină frecvența anumitor cuvinte de pe anumite pagini ale unor site-uri web, în vederea clasificării acestor pagini în funcție de aria din care fac parte. Acest tip de cercetare face parte din categoria Web Content Mining( clasificarea paginilor în funcție de conținut).

BIBLIOGRAFIE

[1] Bill Inmon – “Building the Data Warehouse. 1st Edition”, Editura “Wiley and Sons”, 1992

[2] Matteo Golfarelli, Stefano Rizzi – “Data Warehouse Design: Modern Principles and Methodologies”, Editura “The McGraw Hill Companies”, New York, 2009

[3] M.J.A. Berry, C. Linoff – “Data Mining -Techniques appliquée au marketing, à la vente et aux services clients”, Editura “InterEditions”, 1997

[4] Viktor Mayer-Schonberger, Kenneth Cukier – „Big Data: A revolution that will transform how we live, work and think”, Editura „Eamon Dolan”, 2014

[5] Preluat de pe https://ro.wikipedia.org/wiki/Big_data

[6] Nasrullah Memon, Jennifer Jie Xu, David L. Hicks, Hsinchun Chen – „Data Mining for Social Network Data”, Editura „Springer”, New York, 2010

[7] Preluat de pe http://www.cursuricibernetica.info/anul-3/inteligenta-computationala/rationamentul-bayesian/

[8] Preluat de pe http://www.cursuricibernetica.info/anul-3/inteligenta-computationala/invatarea-supervizata/

[9] Meta S. Brown – „Data Mining for dummies”, Editura „John Wiley and Sons”, New Jersey, 2014

[10] Tye-Yan LIU – „Learning to Rank for Information Retrieval, Vol. 3”, Editura „Springer”, 2009

[11] Gareth M. James – „Variance and Bias for General Loss Functions”, Machine Learning 51, 115-135, 2003

[12] B.E. Boser, I.M. Guyon, V.N. Vapnik – „A training algorithm for optimal margin classifiers”, Editura “ACM Press”, 1992

[13] H. William, A. Saul, J.P. Vert – “ Support Vector Machines. Numerical Recipes: The Art of Scientific Computing (3rd ed.)”, Editura “Cambridge University Press”, 2007