Analiza Prin Tehnici Data Mining a Rezultatelor la Bacalaureat
Analiza prin tehnici data mining a rezultatelor la Bacalaureat
CUPRINS
CAPITOLUL I – INTRODUCERE
CAPITOLUL II –INTRODUCERE ÎN DATA MINING
CAPITOLUL III- CLASIFICARE
CAPITOLUL IV – CLUSTERING ȘI ASOCIERI
CAPITOLUL V – DESCRIEREA ALGORITMILOR FOLOSIȚI ÎN BAZA DE DATE
CAPITOLUL VI – CONCLUZII
BIBLIOGRAFIE
CAPITOLUL II – INTRODUCERE ÎN DATA MINING
2.1 Scurtă istorie a data mining
În ultimii ani, ca urmare a disponibilității largi de informatie au apărut cantități mari de date și necesitatea iminentă pentru extrage din aceste date informații și cunoștințe utile. Informațiile și cunoștințele acumulate pot fi utilizate pentru aplicații care variază de la analize de piață, detectarea fraudelor, precum și păstrarea clienților, pentru controlul producției și explorare a știnței. Știința ce se ocupă cu extragerea cunoștințelor din date masive se numește data mining și poate fi considerată ca o prescurtare pentru „mineritul cunoștințelor din date” (knowledge mining from data).
Descoperirea de cunostințe din bazele de date (Knowledge Discovery in Databases – KDD) sau extragerea de date (Data Mining – DM) este reprezentat de modul de a înțelege, analiza și e de a utiliza o cantitate masivă de date disponibile. Knowledge Discovery in Databases a fost concepută în anul 1989, pentru a desemna o zonă de cercetare bazată pe metode de Data Mining, recunoașterea formelor, învățare automată și tehnici de baze de date în contextul bazelor de date de dimensiuni mari.În ziua de azi data mining reprezintă reprezentând un domeniu de vârf din domeniul bazelor de date, în plin avânt. Descoperirea de cunoștințe în bazele de date este considerat un proces însemnat de identificare a unor tipare de date valide, noi, potențial folositoare, care pot fi înțelese, așa cum este arătat de către Fayyad.
În opinia sa, există mai multe etape în procesul de descoperire de cunoștințe: selectarea, preprocesarea, transformarea, extragerea datelor, interpretarea sau evaluarea rezultatelor.
Data Mining poate fi definit în primă instanță ca fiind totalitatea proceselor de căutare și manipulare a datelor din bazele de date. Aceast proces de "minerit" în bazele de date are ca scop principal descoperirea unor corelații necunoscute sau puțin evidente între date. Piața de marketing din ziua de azi folosește din ce în ce mai mult rezultate obținute prin data mining
Un sistem de data mining este format din mai multe componente importante după cum urmează:
Baze de date, depozite de date sau de informații – este reprezentat de curățirea datelor (eliminarea zgomotului și corectarea inconsistențelor din date) și tehnicile de integrare (agregare) efectuate pe date.
Baze de date sau servere pentru depozitarea datelor – sunt responsabile pentru aducerea datelor relevante bazate pe cererea utilizatorului.
Cunoștințele de bază – pentru ghidarea căutării sau evaluarea pattern-urilor rezultate.
Motorul data mining – este important pentru sistemul de data mining și ar trebui să cuprindă module funcționale pentru sarcini cum ar fi, asocierile, clasificările, analiza clusterelor și analiza evoluției și derivării.
Module de evaluare a pattern-urilor – sunt folosite pentru a interacționa cu modulul de data mining pentru a realiza o căutare a pattern-urilor relevante.
Interfața grafică a utilizatorului – comunicarea între utilizator și sistemul de data mining pentru specificarea interogărilor de data mining și afișarea informațiilor obținute.
2.1.1 Preprocesarea datelor
Bazele de date din lumea reală sunt astăzi foarte sensibile la zgomot, la lipsuri și inconsistență a datelor. Pentru a putea obține rezultate folositoare din date se folosesc următoarele tehnici de preprocesare:
– Curățirea datelor – pentru eliminarea zgomotului și corectarea inconsistențelor din date;
– Agregarea datelor – contopirea datelor din surse multiple într-o formă corespunzătore mineritului. Combină datele din mai multe surse într-un depozit de date coerent: depozit de date sau cub de date;
– Selectarea datelor – pentru a selecta informațiile relevante pentru procesul curent de analiză cu scopul simplificării muncii în etapa propriu-zisă de extragere de cunoștințe;
– Transformarea datelor – pregătirea datelor pentru analiză printr-o reprezentare cât mai adecvată. Constă în operații cum ar fi normalizarea datelor. Normalizarea poate îmbunătăți acurateța și eficiența algoritmilor de data mining. Normalizarea datelor reprezintă scalarea tuturor datelor la un domeniu prestabilit;
– Reducerea datelor – poate reduce dimensiunea datelor prin agregare, eliminarea trăsăturilor caracteristice redundante sau gruparea trăsăturilor comune.
Aceste tehnici sunt aplicate apriori procesului de data mining și pot îmbunătăți calitatea procesului pentru găsirea șabloanelor și/sau reducerea timpului necesar pentru mineritul efectiv.
2.1.2 Curățirea datelor
Deobicei datele pentru procesul de data mining sunt preluate din diverse surse, acestea au deseori diverse structuri și valori eronate sau lipsă. Algoritmii de curățire a datelor încearcă să „umple” valorile lipsă, să netezească valorile considerate zgomot prin identificarea extremelor și să corecteze inconsistențele în date.
2.1.3. Valorile lipsă
Când se aduc toate datele în aceeași structură pot apărea valori lipsă în valorile corespunzătoare unui document. Pentru a umple valorile lipsă există câteva metode clasice:
– Ignorarea tuplelor – de obicei este făcută când clasa de etichete sau o mare parte din atributele tuplului lipsesc. Această metodă nu este eficientă mai ales în cazul în care tuplele conțin câteva atribute cu valori lipsă. Este în special slabă când procentajul valorilor lipsă per atribute variază considerabil;
– Umplerea valorilor lipsă manual – în general această cale este consumatoare de timp și nu este fezabilă la multe valori lipsă;
– Utilizarea unei constante globale pentru umplerea valorilor lipsă – înlocuiește toate atributele lipsă cu aceeași constantă. Această metodă este simplă dar nu este recomandată deoarece poate duce la valori eronate ale tuplului;
– Utilizarea unui atribut de mijloc pentru înlocuirea valorilor lipsă – de exemplu se umple cu media tuturor valorilor din câmpul respectiv. Utilizarea unui atribut de mijloc pentru toate eșantioanele aparținând aceleiași clase din care provine tuplul – Aceasta se aplică în cazul în care avem la dispoziție și un set mic de date preetichetate. Se vor înlocui valorile lipsă în setul de datete neetichetat cu media valorilor pe tuplul respectiv pentru toate documentele aparținând aceleiași clase din setul de date etichetat;
– Utilizarea valorii cele mai probabile pentru înlocuirea valorilor lipsă – determinarea prin regresie a valorilor, are ca rezultat componente bazate pe concluzii utilizând teoria Bayesiană sau bazat pe arbori de decizie.
Ultima metodă este cea mai des folosită pentru că utilizează datele prezente pentru a prezice valorile lipsă.
2.1.4. Zgomotul
Zgomotul este o eroare aleatoare sau variabilă în valorile măsurate. Acesta poate duce la erori în evaluarea pattern-urilor. Câteva tehnici de netezire a datelor sunt:
1. Filtrarea – reprezintă netezirea valorilor sortate prin consultarea vecinătății. Valorile sortate sunt distribuite într-un număr de „grupuri” sau bin (container). Deoarece metoda consultă valoarea vecinului, ea va face o netezire locală. Există mai multe metode de netezirea a datelor:
– Netezire prin filtru median – fiecare element din container este înlocuit cu media elementelor din acel grup.
– Netezirea prin margini – minimul și maximul sunt date de container și reprezintă granițele, fiecare element este înlocuit de valoarea graniței celei mai apropiate.
2. Clusterarea – extremitățile pot fi găsite prin grupare, unde valorile similare sunt organizate într-un grup sau „cluster”. Valorile care rămân afară după grupare sunt considerate zgomot și sunt eliminate.
3. Combinarea inspecției umane cu cea a calculatorului – aplicația este utilizată pentru identificarea pattern-urilor extreme care reflectă un conținut „surpriză” și respectă o etichetă cunoscută. Pattern-urile găsite pot fi bune sau pot fi „gunoi”. Omul poate sorta aceste pattern-uri pentru a identifica care dintre acestea reprezintă gunoi.
4. Revenirea la starea anterioară – datele pot fi netezite prin ajustarea datelor. Regresia liniară implică găsirea celei mai bune linii pentru a uni două variabile astfel încât variabilele cunoscute pot fi utilizate să predicționeze altele. Regresia multiplă liniară este o extensie a regresiei liniare unde mai mult de două variabile sunt implicate și datele sunt unite pe o suprafață multidimensională. Se utilizează regresia pentru a găsi ecuația matematică care ajută la netezirea datelor și elimină zgomotul.
2.1.5 Transformarea și integrarea datelor
Data mining oferă posibilitatea de integrare a datelor – concatenarea datelor din surse multiple de date. Aceste date trebuie transformate într-o formă convenabilă pentru căutare.
2.1.5.1 Integrarea datelor
Este inevitabil ca în etapa de analiză a datelor, să se apeleze și la integrarea datelor din surse multiple într-o sursă de date coerentă – aceasta reprezintă depozitarea datelor. Există un număr de probleme de luat în considerare pe durata integrării datelor:
Identificarea entităților – cum pot ști că customer_id dintr-o bază de date și cust_number din cealaltă fac referire la aceleași entități. Bazele de date și depozitele de date conțin de obicei metadate. Fiecare metadată poate fi folosită pentru a evita erori în schema de integrare.
Redundanța – un atribut poate fi redundant dacă el este „derivat” dintr-o altă tabelă. In consistența în atribute sau dimensiune pot de altfel cauza redundanță în setul de date. Redundanța poate fi eliminată prin analiza corelațiilor. Analiza măsoară cât de puternic un atribut implică pe celălalt, bazându-se pe datele disponibile. Corelația dintre atributele A și B poate fi măsurată prin:
rA,B=; (1.1)
unde n reprezintă numărul de tuple, sunt media valorilor A si B iar reprezintă deviația standard:
=iar , (1.2)
Dacă rezultatul relației (1.1) este mai mare decât zero atunci A și B sunt posibil corelate, în sensul că dacă valoarea lui A crește va crește și valoarea lui B. De aici, o valoare mare va indica că A sau B pot fi șterse deoarece sunt redundante. Dacă rezultatul este zero A și B sunt independente și nu există corelație între ele. Dacă valoarea rezultată este mai mică ca 0, atunci A și B au o corelație negativă (anticorelație) unde dacă valoarea unui atribut crește valoarea celuilalt atribut va descrește.
Detecția și rezoluția valorii datelor de conflict – valorile pot diferi din cauza scării de reprezentare sau codării. De exemplu înălțimea poate fi memorată în diferite unități de măsura. Prețul pentru diferite hoteluri poate implica nu doar diferențe de preț ci și diferențe de servicii. Integrarea cu grijă a datelor din surse multiple poate ajuta la reducerea și evitarea redundanțelor și inconsistențelor în setul de date rezultat și poate duce la o îmbunătățire a procesului de extragere de cunoștințe.
2.1.5.2 Transformarea datelor
Transformarea datelor constă în reprezentarea sau consolidarea datelor într-o formă convenabilă pentru mineritul datelor. Ea implică următoarele:
Netezirea – se folosește pentru eliminare zgomotului din date. Asemenea tehnici includ filtrare, clusterare și regresie; Agregarea – operații de sumarizare sau agregare sunt aplicate pe date. De exemplu vânzările zilnice pot fi agregate ca și calcule lunare sau anuale;
Generalizarea – unde primitivele de date de nivel jos sunt înlocuite cu primitive de nivel înalt. De exemplu atributul stradă poate fi generalizat cu oraș sau țară. La fel vârsta poate fi generalizată în tânăr, mediu și bătrân;
Normalizarea – se aplică o scalare într-un anumit domeniu pentru atribute. De exemplu – datele sunt scalate în intervalDe exemplu atributul stradă poate fi generalizat cu oraș sau țară. La fel vârsta poate fi generalizată în tânăr, mediu și bătrân;
Normalizarea – se aplică o scalare într-un anumit domeniu pentru atribute. De exemplu – datele sunt scalate în intervalul [-1.0, 1.0] sau în intervalul [0.0, 1.0].
Construirea atributelor (construirea articolelor) – unde noi atribute sunt create și adăugate în setul de atribute dat pentru procesul de mining. În continuare, nu voi detalia tehnicile de netezire, agregare și generalizare, ci mă voi axa pe normalizare pentru că a fost utilizată cu precădere în experimentele prezentate în această teză. Normalizarea – reprezintă scalarea unei valori a atributului într-un domeniu specificat și se realizează printr-o funcție matematică. Dintre metodele de normalizare mai des utilizate, se menționează următoarele: Normalizarea min-max: transformare liniară de la datele originale. Presupunem minA și maxA sunt valorile minime și maxime a atributului. Normalizarea valorii v a lui A în în noul domeniu [new_minA, new_maxA] se face după formula:
v’=(new_maxA-new_minA)+new_minA (2.3)
Normalizarea min-max păstrează relațiile dintre valorile datelor originale.
Normalizarea z-mediu – valoarea A este normalizată în baza unei medii și deviații
standard a lui A: v’=, unde v este valoarea lui A, v’ este valoarea calculată, este media iar este deviația standard. Metoda de normalizare se utilizează când minimul și maximul sunt necunoscute sau A iese din domeniul min-max.
Normalizarea prin scalare decimală – normalizare prin mutarea punctului decimal, punct care se mută ținând cont de valoarea maximă absolută a lui A: v’= , unde j este întreg dat de max (vț)<1.
Prin normalizare datele originale vor fi schimbate în totalitate, mai ales în ultimele două metode. Pentru a se normaliza în aceiași măsură noile date este necesar să se salveze parametrii de normalizare.
Construirea atributelor – noile atribute sunt construite și adăugate plecând de la atributele deja existente pentru a ajuta la o mai bună reprezentare a setului de date. De exemplu din atributele „lungime” și „lățime” s-ar putea construi atributul „arie”.
2.2 Text mining
Majoritatea bazelor de date din lumea reală sunt ăn format text și sunt formate din colecții mari de documente din diverse surse, precum articolele de știri, lucrări de cercetare, cărți, biblioteci digitale, mesaje e-mail, pagini web și fluxuri RSS etc. Aceste date nu au o structură complet determinată și sunt semistructurate. S-au dezvoltat tehnici de regăsire a informațiilor, precum tehnici de indexare a textului, ce s-au dezvoltat pentru a controla documentelor nestructurate.
În text mining există mai multe metode de abordare, ce se pot clasifica din diferite perspective, unele se bazează pe intrări din sistemul de text mining și unele se bazează pe sarcinile ce urmează să fie efectuate de sistemul de minerit. Abordările cel mai des folosite sunt în general cele pe bază de cuvinte cheie, atunci când ca și intrare există un set de cuvinte cheie sau termeni din documente. Un alt tip de abordare este aceea bazată pe etichetare, în situația în care datele de intrare sunt un set de etichete. O altă metodă de abordare este bazată pe extragerea de informații, ce are ca date de intrare informații semantice, precum evenimente, fapte sau alte entități descoperite prin mineritul de informații. O abordare simplă pe bază de cuvinte cheie poate descoperii doar relații la un nivel superficial, precum redescoperirea expresiilor simple (baze de date și sisteme) sau apariții împreună în pattern-uri cu semnificație mai puțin importantă (de exemplu, "brutar" și "pâine"), dare care nu ajută o înțelegere prea bună a textului. Abordarea ce se bazează pe etichetarea documentelor are la bază denumirea claselor, care se obține prin etichetare manuală (care este considerată costisitoare și este imposibilă pentru baze mari de date) sau de unii algoritmi de clasificare automată, dar aceștia pot prelucra un set relatic mic de clase și au nevoie de definirea etichetelor în prealabil. Ultima metodă de abordare este reprezentată de extragerea de informații este cea mai evoluată și poate ajuta la găsirea unor cunoștințe profunde, dar aceasta necesită o verificare semantică a textului prin înțelegerea limbajului natural folosind metode de lingvistică computațională și de învățare automată.
Cele trei metode de abordare prezentate mai sus, se pot rezolva prin metode diferite. Aceste metode de rezolvare se referă la clustering-ul documentelor, clasificarea, extragerea de informații și analiza asocierilor.
2.2.1. Analiza datelor text și regăsirea informației
Regăsirea informației (Information Retrieval – IR) reprezintă un domeniu ce s-a dezvoltat o dată cu sistemelor de baze de date. Față de un sistem de baze de date se folosește de interogări și procesare tranzacțiilor în date structurate, regăsirea informației se concentrează pe recunoașterea și organizarea informațiilor din documentele text. O problemă majoră pentu sistemele de regăsire a informației o constituie alegerea documentelor relevante pentru utilizatori. Datorită faptului că se utilizează diferite tipuri de date pentru sistemele de regăsire și sistemele de baze de date, problemele ce apar la aceste tipuri de sisteme sunt diferite. Cele mai mari probleme legate de regăsirea informației din documentele text sunt reprezentate de aproximarea căutării bazându-ne pe cuvinte cheie și pe noțiunea de relevanță.
2.2.1.1 Măsuri de bază pentru regăsirea informației
De exemplu putem presupune că un sistem de regăsire a informației a returnat un anumit număr de documente pe baze unei interogări, apare problema cum se poate aprecia dacă setul de informații returnat este sadisfăcător.
Pentru sistemele de regăsire a informației există două notații importante:
Fie {Relevant} mulțimea tutror documentelor relevante față de interogare și {Regăsit} mulțimea tutror documentelor găsite în urma interogării. Setul de documente care le include pe ambele și se notează cu {Relevant} {Regăsit}. Pentru aprecierea textului găsit există trei reguli:
– Precizie – este reprezentat de probabilitatea ca un document clasificat corect să fie util: precision= (2.4)
– Recall – este reprezentat de probabilitatea ca un document callutil să fie clasificat corect
recall = (2.5)
F-measure se definește ca fiind media armonică între Precizie și Recall
F-measure = (2.6)
Este bine de știut faptul că media armonică penalizează mai bine decât alte măsuri un sistem ce supralicitează o măsură în favoarea celeilalte.
2.2.2 Metode de regăsire a informației
Deobicei, metodele de regăsire se împart în două categorii:
Metode ce oferă o ierarhie de documente, acesta se bazează pe un scor obținut de fiecare document în funcție de cât de similar este față de interogarea formulată;
Metode care văd regăsirea de informație ca o problemă de selecțiea unor documente.
Se stabilesc de către interogare anumite limite epntru selectarea documentelor relevante, în metodele de selecție a documentelor: Modelul Boolean reprezintă o metodă tipică de regăsire a informației în care un document este reprezentat de un set de cuvinte și oferă utilizatorilor o expresie booleană de cuvinte cheie, precum “bed AND breakfest”, „coffee OR tea”, sau „browser web NOT Mozila Firefox”. Un sistem de regăsire a informației de genul acesta va efectua o interogare și va returna doar documentele ce justifică expresia booleană. În general, metoda de regăsire booleană funcționează bine doar în situațile în care utilizatorul cunoaște setule date din care vrea să selecteze informații și poate efectua o interogare booleană corectă.
Metodele care se ocupă de ierarhizarea documentelor, ordonează documentele în funcție de relevanța acestora în raport cu o interogare formulată. Pentru utilizatorii obișnuiți, aceste metode sunt mai adecvate decât metodele de selecție a documentelor. Majoritatea sistemelor moderne de regăsirea a informațiilor ca răspuns la interogarea pe cuvinte sau expresii cheie a unui utilizator, oferă o listă de documente ierarhizate. Această metodă are drept scop de a aproxima gradul de relevanță a unui document cu interogarea formulată, pe baza unui scor calculat cu ajutorul informațiilor, precum frecvența de cuvinte din document și cuvintele din întregul set. Este greu ca pentru un set de cuvinte cheie să se gasească o măsură precisă a gradului de relevanță.
Pentru prezentarea documentului cea mai utilizată metodă de abordare este utilizarea modelului spațiului vectorial (Vector Space Model-VSM). Ideea principlă a modelului Model Space Vector este următoarea: se reprezintă un document și o interpgare, ca vectori într-un spațiu n-dimensional ce corespunde tuturor cuvintelor cheie și se va folosi o măsură de similaritate specifică pentru a se calcula similaritatea dintre vectorul de interogare și vectorul documentului. Valorile similarității se pot utiliza și pentru ierarhizarea documentelor. Dacă se pleacă de la un set D de documente și t termeni, se poate modela fecare document ca fiind un vector v într-un spațiu n dimensional ortogonal Rn. Coordonata j a lui v este o frecvență de termeni care se poate și pondera, care măsoară importanța termenului j pentru documentul dat: de regulă este 0, în situația în care documentul nu conține termenul și diferit de 0 în rest. Acum se presupune că documentele similare se așteaptă să aibă o frecvență asemănătoare a termenilor, putem măsura similaritatea prin compararea frecvențelor cuvintelor de bază. Un bun exemplu ar fi folosirea formulei cosinusului dintre 2 vectori n-dimensionali:
sin(v1,v2) = (2.7)
unde v1*v2 sunt produsul scalar a 2 vectori și se calculează ca fiind , este modulul vectorului și se calculează ca fiind = . Se cunoște că sin(v1,v2)=1 reprezintă o similaritate maximă între cei doi vectori.
2.2.3 Asocierea între cuvinte cheie și clasificarea documentelor
Printr-o astfel de analiză se colectează seturi de cuvinte cheie sau termeni ce apar frecvent împreună și care stabilește relații de asociere sau de corespondență între ele. Prin metoda analizei asocierilor în baze de date text efectuează câteva operații de preprocesare a datelor, prin extragerea rădăcinii cuvintelor și prin eliminarea cuvintelor de „legătură” din text obținând astfel un set „redus”, apoi apelează algoritmi specifici mineritului pe bază de asocieri. Într-o bază de date ce cuprinde documente, fiecare document poate fi privit ca o tranzacție, în timp ce un set de cuvinte cheie din document poate fi considerat ca un set de elemente din acea tranzacție. Baza de date este în formatul:
{id_document, listă_cuvinte_cheie}
Mineritul asocierii înregistrărilor din bazele de date tranzacționale, reprezintă o problemă a mineritului asocierii cuvintelor cheie din documente, unde s-au dezvoltat mai multe metode. Prin procesul de minerit al asocierilor se poate ajuta la detectarea componentelor asocierii, adică termeni sau fraze dependente de domeniu sau asocierilor necombinate (curs valutar).”Mineritul asocierilor de termeni” este diferit de mineritul cuvintelor simple, și are două avantaje:
Se etichetează automat termenii și frazele, astfel se elimină necesitatea utilizatorului;
Se reduce semnificativ în timpul executării algoritmului de data mining numărul de rezultate fără sens.
2.2.4 Alte tehnici de indexare pentru regăsirea textului
Index invers și fișierele de semnături reprezintă alte tehnici de regăsire în data mining.
Un index invers este reprezentat de o structură de două tabele și anume document_table și term_table care sunt indexate cu tabele HASH sau cu ajutorul unui arbore B+ :
document_table – este reprezentat de un set de înregistrări, fiecare înregistrare conține două câmpuri și anume doc_id și posting_list, unde posting_list reprezintă o listă de termeni care apar în document, sortată în raport cu metrica utilizată;
term_table – este reprezentat de un set de termeni înregistrați, fiecare termen conținând: term_id și posting_list, unde posting_list specifică o listă de identificatori de documente în care apar termenii.
Fișierele de semnătură sunt reprezentate de fișierele ce memorează semnături ale înregistrărilor pentru fiecare document din baza de date. O semnătură are dimensiune fixă de b biți ce sunt reprezentași de termeni. La început fiecare bit al documentului de semnături este setat la 0. Dacă un termen reprezentat în semnătură apare în document atunci acel bit este trecut pe 1. Fiecare bit care este setat în S1 este setat și în S2, atunci o semnătură din S1 se potrivește cu altă semnătură din S2.
2.3 Utilizarea www ca sursă de data mining
WWW (World Wide Web) reprezintă totalitatea site-urilor, documentelor și informaților de tip hipertext.
Internet-ul este un domeniu mult prea vast pentru a se realiza un data warehouseing sau un data mining eficient. În momentul de față dimensiunea WEB-ului ajunge la mii de terabytes și se afla în plină ascensiune.
Datorită numărului foarte mare de site-uri se poate spune ca WEB-ul reprezintă cea mai bază de date care există și care depășeste prin complexitate orice bază de date de documente cu texte tradiționale, însă lipsește standardizarea. Fapt care a dus la apariția ideei de web semantic, de aceea se încearcă adăugarea uotuținor standarte la nivel de limbaj și structură a paginii. În momentul de față paginile web conțin stiluri și structuri diferite. Totuși deși internet-ul este ca o bibliotecă digitale imensă, majoritatea informațiilor nu sunt ordonate deoarece nu există indexare, fapt ce duce la o sarcină dificilă atunci când vine vorba și căutarea și regăsirea de informații.
Datorită faptului că internetul este într-o continuă creștere, informațile conținute sunt constant actualizate și se modifică zilnic, îl face să fie o sursă de informații foarte dinamică.
De asemenea internetul este deservit de o mare diversitate de utilizatori, care este intr-o continuă creștere: Utilizatorii au de regulă diferite cunoștințe, interese ți scopuri de utilizare diferite. Conform statisticilor pentru un utilizator sunt relevante doar o mică parte din informațile de pe web, aproape 99% din informațile obținute de un utilizator sunt neimportaum pot fi determinate porțiunile nte pentru el. Astfel apar întrebări de genul:
Cum pot fi determinate porțiunile din internet care sunt într-adevăr relevante ?
Cum putem găsi o pagină web de înaltă calitate cu un topic specific?
În internet există motoare de căutare ce se bazează pe indexi, acestea indexează pagini, construiesc și memorează indexi mari bazați pe cuvinte cheie, aceștia ajută la localizarea seturilor de pagini care conțin acele cuvinte cheie. Motoarele de căutare afișează în urma căutării numeroase pagini, datorită faptului că ficare topic conține numeroase documente. Problema polisemiei se justifică datorită faptului că multe documente care pot fi relevante în urma unei căutări, este posibil să nu conțină cuvinte cheie definite în căutare.
Data mining în domeniul internetului poate fi considerat ca fiind o mare provocare, doarece acesta presupune identificarea de structuri în internet, ordonarea conținutului, identificarea de regularități și conținuturi dinamice, pattern data mining de acces la internet. Când vine vorba de internet data mining se poate clasifica în trei categori:
Data mining conținutului web;
Data mining structurii web;
Data mining utilizării web.
2.3.1 Mineritul structurii paginilor web
În comparație cu un document normal, un site web poate conține pe lângă text imagini și o structură, acesta fiind motivul pentru care paginile we sunt considerate ca a fi date semistructurate. DOM (Document Object Model) este structura de bază a unei pagini web, acesta este independentă de platformă și limbaj, ceea ce permite script-urilor și programelor să acceseze și să actualizeze conținutul, stilul și structura documentului web.
Într-o pagină web structura Document Object Model este ca o structură arborescentă, în care fiecare etichetă HTML în site corespundeunui nod în arborele DOM. O pagină web poate fi marcată de etichete predefinite structural. Etichetele includ <p> paragraf, <table> tabel, <li> element de listă, <h1>…<h6> titlu-heading.
Pentru a facilita extragerea de informații poate fi folosită structura DOM, dar multe pagini nu respectă detaliile W3C referitor la structura HTML, datorită flexibilitășii de sintaxă HTML. Standartul HTML poate fi considerat cel mai „distructiv” standart utilizat în internet, deoarece permite amestecare „formei” și a „conținutului”, ceea ce face ca indexarea site-urilor web să fie greoaie. În momentul de față standartele XHTML1 și HTML5, au ca scop o separare clară a conținutului de forma de afișare, folosindu-se de CSS (Cascade Style Sheets) care utilizează stiluri declarate în antetele paginilor sau în fișiere separate. Pe langă acest lucru DOM a fost inițial introdus pentru afișarea documentului în utilitarul web și nu ca o descriere a structurii semantice a site-ului web.
2.3.2 Data mining-ul link-urilor pentru identificarea site-urilor web autoritare
Dacă un utilizator ar face o căutare pentru a obține pagini relative la un anumit subiect, precum „vremea intr-o anumită regiune”, site-urile autoritare sunt considerate site-urile relevante și de înaltă calitate din punct de vedere al cuvintelor cheie și subiectului folosit în căutare. Pe internet pe lângă site-uri există și hiperlink-uri care pointează de la un site la altul. Hiperlink-urile sunt formate din foarte multe notații umane latente, acestea pot ajuta la regăsirea automată a noțiunii de autoritate. În momentul în care un autor de site web creează un hiperlink către un alt site, acesta acordă un grad de încredere în site-ului către care a fost făcut link-ul. Link-urile distribuite pentru un site dat de la diferiți autori de site-uri poate arăta cît de important este acel site, astfel acest lucru conduce la descoperirea site-urilor web autorizate. Deci, (meta)informațiile web de legătură livrează informații importante legate de calitate, relevanță și structura conținutului web-ului astfel este o sursă bogată pentru data mining-ul internetului.
Site-urile web au în structura lor niște legături unice. Nu fiecare hiperlink poate fi considerat ca fiind o „avizare” pentru un site, unele link-uri au drept scop navigarea sau reclame. Dar totuși în situația ăn care majoritatea hiperlink-urilor către un anumit site sunt link-uri de „avizare”, opinia colectivă va domina. Din motive evidente de marketing un site autoritar nu va deține un link către rivalii din același domeniu, mai trebuie specificat și faptul că site-urile autoritare sunt foarte rar desciptive.
Proprietățile structurilor link-urilor conduce la apariția unei alte categorii importante a site-urilor web și anume hub. Hub-ul reprezintă un site sau un set de site-uri ce livrează seturi de link-uri autoritare. Unele pagini hub pot fi neimportante datorită faptului că există puține link-uri ce pointează către ele, totuși hub-urile livrează link-uri către site-uri autoritare, având un subiect comun. Astfel de site-uri pot fi seturi de link-uri recomandate pe site-uri personale, seturi de referințe ale unui curs sau pagini web comerciale. De regulă, un hub bun este un site cu link-uri către site-uri autoritare de calitate.
2.3.3 Data mining utilizării web
Data mining-ul utilizării web-ului, este la fel de importan precum data mining-ul conținutului și structurii de legături. Acesta prelucrează fișierele de log pentru descoperirea pattern-urilor de acces ale userilor la site-uri. Prin exploatarea și analizarea în înregistrările de web log ajută la identificarea clienților pentru comerțul electronic, mărirea calității și asigurarea serviciilor de informații pe web la userul final și îmbunătățitea performanței sistemelor de servere de pe internet.
De regulă în web log-ul înregistrat de serverele web, înregistrează fiecare logare pentru toate accesările la un site web. Web log-ul conține URL-ul, adresa IP de la care a fost făcută cererea inițială. Web log-urile livrează informații detaliate legate de dinamica internetului, fapt care este extrem de important în dezvoltarea data mining-ul pe web log-uri.
Pentru dezvoltarea data mining-ului pe web log-uri, se au în vedere următoarele:
Datele din web log-uri trebuie să fie valide si de încredere, pentru acest lucru datele din web log-uri trebuie să fie curățate, condensate și tranformate într-o ordine accesibilă pentru regăsirea și analiza informațiilor importante;
Având adresa IP, URL-urile disponibile, timpul și informațiile despre site-urile web se poate realiza o selecție multidimensională, de asemenea prin folosirea unei analize de tip OLAP (OnLine Analytical Processing – specifice masivelor de date) se pot determina N useri de top, numărul celor mai accesate site-uri și alte informații ce pot ajuta la descoperirea potențialilor clienți;
Mineritul poate fi făcut și pe înregistrările web log pentru găsirea pattern-urilor de asociere sau secvențiale
Informațiile extrase din web log-uri furnizează grupurile de useri ce accesează anumite grupuri de pagini, datele din web log-uri se pot integra cu conținutul web și structura de legături web cu ajutorul data mining-ului site-urilor, clasificarea informațiilor web și construcția pe mai multe nivele a informațiilor de bază.
2.3.4 Construirea informațiilor de bază pe mai multe niveluri web
În situația în care un site conține pe lângă text și metainformații despre site-ul respectiv, motiv pentru carre se urmărește structurarea informațiilor de bază pe mai multe niveluri pentru a se verifica cât de realiste și folositoare sunt. Cel mai mic nivel ar fi web-ul însuși, acesta poate fi despărțit în depozite, ne vom referi la acest nivel ca layer-0. Dar ar fi nerealist să se creeze depozite web ce conțin copii a fiecărui site web, deoarece ar fi un duplicat al world wide web.
Al doilea nivel se va numi layer-1 și este reprezentat de nivelul de descriere al site-ului, și conține informații ce descriu site-ul în sine, acesta va fi mai mic decât layer-0, dar suficient de vast pentru prezentarea informațiilor de bază pentru livrarea cuvintelor cheie de bază, căutarea multidimensională sau data minerit. Dacă ne bazăm pe multitudinea site-urilor, layer-1 se poate organiza în diferitate clase semistructurate precum organizații, documente etc.
Al treilea nivel layer-2, este reprezentat de nivelul de servicii WEB, și sunt defapt cataloage web construite deasupra nivelului și servicii de aplicație ce utilizează WSDL sau protocoale mai simple precum SOAP, acesta din urmă fiind un protocol ce ajută la schimbul de informație structurat între servicii de internte.
Prin folosirea ratingurilor site-urilor date de motoarele de căutare și algoritmi de clasificare a site-ului sau documentului se poat obține detalii de înaltă calitate și site-uri cu informații relevante de pe internet din construcția layer-0.
Se va facilita schimbul de informații folosind XML (eXtended Markup Language) schimbul și extragerea informațiilor principale pe internet și limbajele de descoperire a cunoștințelor, acestea pot fi create și implementate pentru astfel de scopuri. Astfel internetul semantic va avea ca bază această standardizare căreia i se vor adăuga diferite modele și limbaje de descriere a datelor cum ar fi RDF (Resource Description Framework). Resource Description Framework reprezintă un model standart pentru schimbul pe internet, acesta deține caracteristici ce ajută la fuzionarea informațiilor, indiferent dacă schemele care sunt baza acestor informații sunt diferite și ajută evoluția schemelor de-a lungul timpului fără a fi necesar ca toate datele consumatorilor să fie schimbate la un moment dat.
2.3.5 Clasificarea automată a documentelor web
În procesul de clasificare automată a unui document web se alocă o etichetă de clasă ce există într-un set pre-clasificat. Un bun exemplu poate fi setul DMOZ și documentele web ce sunt asociate unor categorii și poate fi folosit ca seturi de antrenament pentru a obține schema de clasificare. După obținerea schemei de clasificare aceasta poate fi aplicată documentelor web noi pentru a fi clasificate corespunzător. Un site web poate conține mai multe subiecte, publicitate și informații de navigare, analiza de conținut ce se bazează pe blocuri de pagină care joacă un rol important în datele de înaltă calitate din punct de vedere semantic în comparație cu topicul paginii. Este de preferat folosirea unor astfel de date semantice astfel se va obține o mai bună acuratețe decît clasificările simple ce au la bază cuvintele cheie. Cu toate astea link-urile din jurul unui document pot provoca zgomot fapt ce poate deteriora acuratețea.
În ultima perioadă activitățile de cercetare privind construcția și utilizarea internetului semantic, de aceea informația referitoare la insfrastructura internetului va fi structurată la un nivel superior web-ului, acesta bazându-se pe sensul conținutului site-urilor. Folosirea clasificări documentelor web prin we mining va ajuta extragerea automata a sensului semantic a paginilor web și la construirea ontologiilor pentru web-ul semantic. Construirea web-ului semantic va ajuta la clasificarea automată a datelor de pe internet.
2.4 Clustering vs. Clasificare
În ultima perioadă creșterea mare a internetului și creșterea utilizării internetului au creat o dependență puternică de informații și tehnologie. Domeniul ce ține de data mining a fost creat ca un mijloc ce extrage importante informații din baze de date pentru a gasi concepte sau modele ce nu sunt ușor de găsit.
Tehnicile de bază oferite de către învățarea automată pentru data mining prin mineritul informațiilor din datele brute conținute de către baze de date. Procesul de dat mining este format de regulă din următoarele etape:
Modificarea bazelor de date într-un format potrivit;
Curățarea bazelor de date;
Extragerea sau deducerea concluziilor referitoare la date.
Învățarea automată cuprinde două subdomenii principale:
Învățarea supervizată;
Învățarea nesupervizată.
Din primul subdomeniu și anume învățarea supervizată, face parte clasificarea datelor.
2.4.1 Învățare nesupervizată și supervizată
În cardul învățarii supervizate algoritmul primește atât datele vectorizate cât și etichetele ce reprezintă conceptul învățat. Învățarea supervizată are drept scop ca algoritmul să învețe conceptul, astfel ca în momentul în care este prezentat un exemplu nou , ce urmează a fi clasificat , algoritmul va trebui să prezică o etichetă specifică acestui caz. Acuratețea clasificării oferă măsura calității clasificării.
Ținându-se cont de această paradigmă, pe seturi relativ reduse de date apare o problemă și anume posibilitatea de „păcălire” prin memorarea tuturor etichetelor de către algoritm, în detrimentul învățării de către acesta a relațiilor generale predictive dintre valorile atributelor și etichete.
Pe un set de exemple test sunt de regulă evaluate rezultatele învățării, care este disjunct față de setul de exemple de antrenare. Se folosesc metode de clasificare variate, ele cuprinzând de la abordările tradiționale statisce, rețelele neunorale și până la algoritmi bazați pe nuclee precum SVM.
În cazul învățării nesuprvizate algortimul primește doar date neetichetate, astfel algoritmul are ca scop găsirea unei reprezentări adecvate distribuției datelor adică gruparea în clusteri relevanți.
S-a încercat combinarea celor două subdomenii (învățarea supervizată și învățarea nsupervizată), astfel a apărut învățarea semi-supervizată. De regulă, pentru acest tip de abordare învățarea nesupervizată se aplică inițial setuui de date necunoscut cu scopul de a se face unele presupuneri referitoare la distribuția datelor urmând ca prin abordarea supervizată să fie confirmată sau infirmată această ipoteză.
2.4.2 Definiții
Clustering-ul reprezintă procesul de gruparea de obiecte similare a unor obiecte fizice sau abstracte.
Un cluster reprezintă o colecție de obiecte ce sunt similare unu față de celălalt și sunt diferite față de obiectele ce nu fac parte din acel cluster.
Analiza clusterilor și clusteringul este văzută ca fiind o activitate foarte importată în aplicațiile ce ajută la recunoșterea de pattern-uri, cercatare de piață procesarea imaginilor. Pentru clasificarea documentelor web clusteringul este foarte important în vederea extragerii informațiilor importante. În data mining analiza clusterilor si clusteringul poate fi utilizată ca aplicație de sine stătătoare pentru analiza distribuirii datelor, astfel se pot observa diferite caracteristici ale fiecărui cluster. Analiza clusterilor se poate utiliza ca etapă de preprocesare în cadrul unor algoritmi de clasificare.
Clusteringul a devenit o parte foarte importantă pentru data mining datorită cantităților foarte mari de date acumulate în bazele de date, punându-se accent foarte mare pe clustering bazat pe distanță, astfel s-au dezvoltat algoritmii k-Means și k-Medoids.
Ulterior au apărut și altfel de abordări precum folosirea unor algoritmi pe bază de arbori de sufixe, pe ontologii și pe algoritmi bio-inspirați, astefel se explorează o inteligență de grup, care se aseamănă cu comportamentul furnicilor în căutarea hranei.
Clustering-ul conceptual reprezintă obiectele dintr-un grup ce vor forma o clasă doar în situația în care aceasta poate fi definită printr-un concept.Cluteringul convențional diferă față de această abordare. Clusteringul conceptual este format din două componente:
Descoperă clasele apropiate;
Creează descrieri pentru fiecare clasă ca și clasificare.
Clusteringul are ca idee principală, punctul de pornire pentru cele două abordări, este găsirea cluterilor cu similaritate intraclasă foarte mare și similaritate interclasă foarte mică.
2.4.3 Cerințe cheie pentru algoritmii de clustering
Scalarea algoritmilor: Majoritatea algoritmilor de clustering sunt folosiți pentru baze mici de date, dar bazele de date mari sunt formate din foarte multe obiecte iar utilizarea acestora ar duce la afișarea unor date neconcludente.
Posibilitatea de a se utiliza diferite tipuri de atribute: Majoritatea algoritmilor de clustering folosesc date numerice ca date de intrare. Este necesar ca în unele cazuri să se aplice algoritmi de clustering pe date binare, pe date ordinale sau pe o combinație dintre acestea.
Recunoașterea clusterilor de formă arbitrară: Majoritatea algoritmilor determină clusterii utilizând distanțe geometrice cum ar fi distanța euclidiană sau distanța Manhattan. Aceștia tind însă să găsească clusteri sferici cu dimensiune și densitate asemănătoare. În realitate, clusterii pot avea orice formă.
Stabilirea parametrilor de intrare bazată pe cunoașterea minimă a domeniului: Majoritatea algoritmilor de clustering în analiza clusterilor se bazează pe anumiți parametri precum numărul clusterilor de determinat. În funcție de parametrii de intrare stabiliți rezultatul clusteringului poate fi sensibil diferit. Parametrii de intrare, în special pentru bazele de date de dimensiuni mari, sunt dificil de determinat.
Abilitatea de a utiliza date care conțin zgomot: Majoritatea bazelor de date reale conțin date incomplete, necunoscute sau outlineri (informații ce sunt complet diferite în comparație cu marea majoritate a datelor). Algoritmii pot fi sensibili la astfel de date și astfel calitatea clusteringului devine slabă.
Insensibilitate la ordinea de prelucrare a datelor: Algoritmii de clustering pot produce rezultate diferite la schimbarea ordinii prelucrării datelor de intrare .Dezvoltarea unor algoritmi care nu sunt sensibili la ordinea datelor de intrare este importantă.
Dimensiunea mare: Bazele de date pot fi formate dintr-o mulțime de atribute și de dimensiuni. În cazul datelor cu două sau trei dimensiuni majoritatea algoritmilor de clustering reușesc să producă bune rezultate. Un cluster poate fi evaluat de către ochiul uman cu până la trei dimensiuni.
Clustering care ține cont de anumite constrângeri: În situația în care ar trebui identificate zone urbane, atunci anumite granițe naturale precum râurile, șosele importante sunt constrângeri semnificative pentru unele aplicații și de care algoritmii de clustering trebuie să țină cont.
Interpretabilitate și utilitate: Userii vor să obțină rezultate ale clusteringului care să fie utile, interpretabile și inteligibile.
2.5 Metrici de similaritate a documentelor text
2.5.1 Structurarea datelor utilizate în clustering
2.5.1.1 Matricea de date
Matricea de date reprezintă, de exemplu în clustering, n obiecte ce au fiecare m atribute, astfel se creează o matrice de n x m atribute
(2.11)
2.5.1.2 Matricea de disimilaritate
Matricea de disimilaritate este o matrice pătratică n x n ce va conține disimilaritățile pentru toate perechile supuse clusteringului.
d(i,j)=d(j,i) și d(i,i)=0 astfel se va obține matricea de disimilaritate:
(2.12)
unde d(i,j) reprezintă disimilaritatea măsurată dintre două obiecte.
Astfel se grupează obiectele în funcție de disimilaritatea dintre ele sau în funcție de similaritatea dintre ele.
2.5.2 Distanțe uzuale
Pentru calculul disimilarității dintre obiecte este necesar să se calculeze distanța pentru fiecare obiecte. Aceasta se definește în Rn astfel:
Fie mulțimea X . fiind distanță pe X, o funcție d:X × X R, cu proprietățile:
1. x,yX d(x,y)0 și d(x,y)=0 x=y;
2. x,yX d(x,y) = d(y,x);
3. x,y,zX d(x,z)d(x,y) + d(y,z) (regula triunghiului). Unde X se numește spațiu metric
Distanța euclidiană: reprezintă două puncte din spațiul n, ce au valori între intervalul [0 , ), aceasta se calculează cu formula:
dE (xi, xj) = (2.13)
Distanța Manhattan: se deosebește de distanța euclidiană prin faptul că ea se măsoră ca și cum drumul se parcurge pe axe perpendiculare, și are valorile între [0 , ).
dM2 (xi,xj)= (2.14)
Distanța Minkowski:reprezintă o generalizare a distanței Manhattan și a distanței euclidiene. Dacă p se obtine distanța Cebîșev, și are valorile în intervalul [0 , )
dMi (xi,xj)= , p1 (2.15)
Distanța cosinus: reprezintă o măsură de similaritate ce calculează unghiul dintre doi vectori din spațiul n, aceasta are valori cuprinse între [0,1].
Dcos= (2.16)
:
(2.17)
Distanța Canberra se modifică pentru vectori care conțin mai multe valori 0, precum în cazul vectorilor de reprezentare a documentelor, acesta întoarce valori în intervalul [0, ∞).
Distanța Bray-Curtis:
(2.18)
Distanța Bray-Curtis se aseamănă cu distanța Canberra iar toate coordonate sunt pozitive, acesta are valori în intervalul [0,1].
2.5.4 Variabile utilizate în clustering/clasificare
2.5.4.1 Variabile scalate într-un anumit interval
În urma operației de normalizare se pot obține variabilele scalate într-un anumit interval. Acestea vor fi folosite pentru descrierea măsurilor distanțelor.
2.5.4.2 Variabile standardizat
O metodă de standardizare a valorilor este convertirea valorilor originale la valori fără unitate de măsură. Pentru o variabilă x în care n are valori xnse procedează astefel:
Se calculează abaterea mediu absolută
Se presupune ca este abaterea mediu absolută, aceasta se definește ca fiind media aritmetică simplă sau ponderată a abaterilor absolute ale valorilor variabilei, aceasta se caracterizează cu media sau mediana.
În situația în care se calculează și analizează față de medie, abaterea valorilor individuale atunci abaterea medie absolută fiind pentru variabila x :
(2.19)
Xi- valoarea variabilei
(2.20)
Coeficientul acesteia, fiind în intervalul [0,1]
Dacă o variabilă are valorile {1,2,3,4,5,10,0}
,
iar abaterile medii sunt:
Tabel 2.1 Calculul abaterilor medii
Calcularea scorului standardacesta este reprezentat de către valoarea standardizată a variabilei.
Scorul se calculează după formula:
(2.21)
Pentru variabila x valorile standardizate devin:
Pentru aplicațile de clustering sau clasificare se utilizează stabdardizarea datelor, în special cînd se face compararea rezultatelor unor algoritmi diferiți ce au ieșiri în domenii diferite.
2.5.4.3 Variabile dihotomice
Variabila dihotomică are două stări, 0 sau 1, zero reprezintă o valoare inexistentă, iar 1 o valoare existentă. Totuși în situația în care aceste variabile vor fi folosite ca și variabilele scalate într-un interval dat s-ar ajunge la interpretări eronate.
2.5.4.3.1 Matricea de disimilaritate pentru variabile binare
Dacă presupunem că toate variabilele au aceiași pondere, se poate construi un tabel de contingență de 2×2 (tabel 2.3), a reprezintă numărul de vriabile ce au valoarea 1 în i sau j, b reprezintă numărul de variabile care sunt 1 pentru i sau 0 pentru j, c reprezintă numărul de variabile care sunt 0 pentru i si 1 pentru j și d reprezintă care este numărul de variabile cu valoarea 0 pentru i și j.
Numărul total de variabile se calculează: p = a+b+c+d
Dacă ambele stări au aceiași pondere o variabilă este simetrică și nu este important care din ele este 0 si care este 1. În situația în care variabilele simetrice se bazează pe calcul disimilarității se numește disimilaritatea invariată.
Folosinduse coeficientul dat de formula de mai jos se va calcula disimilaritatea:
(2.22)
Fie următoarele 3 documente:
d1: Peștele este în tigaia mea.
d2: Tigaia mea este roșie.
d3: Mark este student.
Se calculează disimilaritatea dintre d1 și d2 ;
(2.23)
(2.24)
Se observă din (2.23) și (2.24) că d1 și d2 au valoarea de disimilaritate mică.
Observație : Dacă coeficientul de disimilaritate ajuge la valoarea 1 obiectele nu sunt similare iar în momentul în care valoarea este 0 atunci sunt computațional identice.
În situația în care codarea ieșirilor are importanță diferită pentru ieșiri, se poate spune că o variabilă binară este asimetrică. Similaritatea a două ieșiri codate cu 1 ajunge să fie mai importantă decât similaritatea a două ieșiri codate cu 0.
Similaritatea de acest gen se poate numi similaritate noninvariabilă, și cel mai important coeficient pentru acest gen de similaritate este corficientul Jaccard, acesta determinându-se după formula:
d(i,j) = (2.23).
Capitolul III – Clasificarea în data mining
3 Algoritmi de clasificare. Paradigma actuală
3.1 Noțiuni generale
Prin clasificarea datelor se întelege procesul prin care unui tuplu i se însușesc una sau mai multe etichete dintr-o mulțime de etichete. Clasificarea datelor se face în două etape. Prima etapă este reprezentată prin construcția unui clasificator ce va distribui un set predefinit de concepte sau date, acesta poartă denumirea de etapa de învățare sau etapa de antrenare, și prin care se aplică un algoritm de clasificare care construiește clasificatorul învățând pe baza unor seturi de antrenament și etichetele asociate claselor acestora. Se presupune că reprezentăm un tuplu X printr-un vector de atribute n-dimensional X = (x1,x2,…,xn) și este reprezentat de măsurătorile făcute în cadrul tuplului pentru n atribute A1, A2,….An . Se consideră că acestei clase aparține fircare tuplu și la rândul ei are o etichetă de clasă, aceasta nefiind ordonată și deține o valoare discretă. Când vine vorba de clasificare , tuplurile se definesc ca fiind exemple, instanțe sau obiecte. În cadrul învățării supervizate, se etichetează fiecăre tuplu în etapa de învățare
Așadar, prin prima etapă a procesului de clasificare se poate înțelege că învățarea unei funcții de mapare y=f(x)ce poate prezice eticheta y a unei clase pentru un tuplu X. Maparea se reprezintă cu regulile de clasificare, arbori de decizie și formule matematice.
Următorea etapă a procesului de clasificare se face prin folosirea modelului construit în prima etapă, în clasificarea unui set de test. Pentru măsurarea eficienței clasificatorului se va face o aproximare a acurateței de clasificare. Dacă măsura acurateței de clasificare care este la baza setului de antrenament, valorile ce se vor obține vor fi acceptabile, astfel va apărea efectul de supraînvățare, prin care algoritmul învață anomaliile din setul de antrenament ce nu se pot aplica în general. Motiv pentru care se construiește set de test ce constă din tupluri și clasele asociate acestora, clase diferite de cele prezentate în setul de antrenament. Acuratețea clasificatorului se calculează ca procentaj al numărului de tupluri corect clasificate de clasificator.
3.2 Algoritmi stohastici
Cel mai important clasificatpr stohastic este clasificatorul bayesian. Acesta ajută la predicția cu o anumită probabilitate apartanența la o anumită clasă. Baza clasificarii bayesiană este teorema lui Bayes. Prin comparația algoritmilor de clasificare s-a identificat clasificatorul bayesian sub numele de clasificator bayesian naiv, acesta având în practicp performanțe foarte bune în situațile în care este folosit la bazele mari de date, iar acolo unde există multe documente , acestea sunt reprezentate prin atribute.
În cazul clasificatorului bayesian simplu atributele pentru o clasa dată sunt indenpende unele de altele, acest lucru poartă denumirea de independență condițională de clasă.
3.2.1 Clasificarea bayesiană
Dacă Y este o variabilă pentru o clasă, iar aceasta poate lua valorile {y1,y2,…ym}.
Dacă X este o instanță a unui vector cu n atribute <x1,x2,…,xn> și xk o valoare posibilă pentru X și xijo valoare posibilă a lui xi. Pentru a se face clasificarea Bayes se calculează probabilitățile P( Y=yi | X=xk ) pentru I =, de aici resultă că trebuie să calculăm toate probabilitățile pentru fiecare categorie, pentru fiecare instanță posibilă din spațiul de instanțe- lucru ce este greu de calculat pentru o bază de date.
Astfel, se va calcula pentru fiecare xi probabilitatea, pentru a se determina categoria lui xk :
(3.1)
Se poate determina probabilitatea P(X=xk) pentru că mulțimea categoriilor este completă și disjunctă, astfel avem relația de echilibru :
(3.2)
Deci,
(3.3)
Se poate aproxima ușor probabilitatea P(Y=yi), dacă ni exemple din D se găsesc în yi
P(Y=yi) = , iar D este mulțimea documentelor din setul de antrenament.
Se estimează probabilitatea P(X=xk | Y=yi). Fapt pentru care se va presupune că atributele unei instanțe sunt independente, în acest caz :
(3.4)
Se va calcula P(Xi | Y) pentru toate perechile posibile
Dacă toate Xi și Y sunt binare, atunci se vor calcula 2n valori:
față de 2n valori, dacă nu am presupune independența atributelor.
Dacă setul de date D este format din nkexemple din categoria n din aceste nk
exemple au a j-a valoare pentru atributul Xi pe xij caz în care se va estima :
(3.5)
O astfel de estimare însă poate genera erori la baze de date foarte mici, fiindcă un atribut rar într-un set de antrenament face ca Xi să fie fals în setul de antrenament :
.
În situația în care Xi =true într-un exemplu test, atunci și
Prin utilizarea uniformizării Laplace, se va evita acest lucru, aceasta ășeacî de la ideea că fiecare atribut are p probilitate p care este evidențiată într-un exemplu virtual de dimensiune m.
În acest caz,
(3.6)
unde p este o constantă
În cazul clasificării de tip text, se generează cu ajutorul clasificatorului Bayes pentru un document dintr-o anumită categorie ci, folosind o colecție de cuvinte, dintr-un vocabular V = {w1,w2, …wm}, probabilitatea P(wj| ci). Prin folosirea normalizării Laplace, se va imagina o distribuție uniformă a tuturor cuvintelor, acest lucru se va scrie astfel:
3.2.2 Antrenarea clasificatorului Bayes
Calculul probabilității ca un document Y să fie aparținator clase Xi
(3.7)
P(yi |Xi) este probabilitatea condițională ca yj să apară într-un document al clasei Xi, se presupune că P(yi |Xi) este măsura contribuției lui yj , în stabilitatea faptului că Xi este clasa corectă.
P(Xi) este probabilitatea apariției unui document în clasa Xi.
(y1,y2,…yj) sunt termeni din documentul Y, acesta fiind o submulțime a lui v utilizat în clasificare, n fiind numărul de termeni.
Clasificarea documentelor text, are ca scop de a găsi cea mai bună clasă pentru acel document. Clasificarea Naive Bayes, cea mai bună clasă este stabilită prin metoda maximului aposteriori MAP și se va nota cu Cmap:
(3.8)
S-a folosit pentru P, pentru că nu se cunosc valorile parametrilor P(Xi) și P( yj | Xi) dar aceștia se pot estima pe baza setului de antrenament.
Dacă V este vocabularul de cuvinte al documentelor conținute în D și pentru Xi V, Di un subset de cuvinte de documente din D din Xi :
(3.9)
Yi este concatenarea tuturor documentelor din Di și ni este numărul aprițiilor pentru toate cuvintele din Yi. Fiecare cuvânt yj V, iar nij numărul apariților cuvântului vj în Yi, aceasta se va scrie:
(3.10)
Numărul total de atribute n=1309, numărul de documente din setul de antrenare D=4702, numărul de clase m=16, numărul de documente ce există în fiecare clasă D1…D16.
Se ia din setul de date de antrenament clasa C18 (Xi =C18) ce conține 328 documente. Se folosește un algoritm ce utilizează uniformizarea Laplace și probabilitatea clasei C18, și se calculează cu formula:
(3.11)
Se calculează probabilitățile pentru cele 1309 atribute în raport cu fiecare clasă în parte.
Se calculează probabilitatea condițională ca un stribut să fie într-o anumită clasă:
(3.12)
3.2.3 Testarea clasificatorului Bayes
Se presupune că D1 este un document test ce conține nD1 termeni. În acest caz, unui document ce trebuie clasificat, i se vor extrage atributele din tabelul de mai sus probabilitățile condiționale.
În, se calculează probabilități, unele sunt foarte mici de aceea prin înmulțire se ajunge la floating point underflow. Pentru a se evita acest lucru, vom folosi proprietatea algoritmului prin care
log (xy) = log x + log y
Funcția logaritmică este monotonă, logaritmarea ecuației nu va modifica rezultatul clasei alese:
(3.13)
Parametrul condițional log reprezintă o pondere prin care se vede cât de bun este un indicator yj pentru Xi. Frecvența relativă a clasei c este indicată de ponderea log . Prin suma lor se poate dovedi că un document aparține acestei clase. Relația 5.13 alege cea mai semnificativă clasă. De accea se va obține pentru fiecare clasă o valoare, apoi se va alege clasa cu valoarea cea ai mare, aceasta fiind clasa cu valoarea cea mai apropiată de 0. Un exemplu ar putea fi un fișier test, pentru care se vor obține următoarele valori pentru fiecare clasă în parte:
3.2.4 Rezultate obținute cu clasificatorului Bayes
Cu ajutorul clasificatorului naiv Bayes au fost testate pe un sistem AMD X2 Turion 1,7GHz, 3GB RAM. S-a folosit metoda n-Fold Crossvalidation, pentru validarea datelor de test. S-a ales n=10 , motiv pentru care setul de date s-a împărțit în 10 submulțimi disjuncte, din care 9 submulțimi au fost folosite pentru antrenament, și o submulțime pentru testare/evaluare. Operația s-a executat de 10 ori, până în momentul în care toate submulțimile au fost folosite măcar o singură dată în testarea clasificării. Iar pentru a vizualiza acuratețea învățării , s-au ales procente diferite pentru datele de intrate, acestea fiind folosite pentru antrenarea clasificatorului după cum urmează: 0%, 1%, 5%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90%, și 100%. În figura de mai jos sunt prezentate rezultatele obținute.
Figura 3.1 Curba de învățare a clasificatorului Bayes și acurateșea clasificării
Astfel în graficul de mai sus, pe axa x, au fost reprezentate documentele folosite succesiv pentru antrenare. Valorile prezentate sunt în concordanță cu procentele: 0%, 1%, 5%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90% și 100%. Iar pe axa y a fost reprezentată acuratețea la antrenare și testare.
Pentru acest test s-a folosit setul de testare T1 și setul de antrenament A1, acestea urmând a fi împărțite în date de testare și antrenare prin metoda n-Fold Crossvalidation. Acest clasificator a fost folosit în clasificarea documentelor din setul de testare T2, astfel s-a testat dacă se pot clasifica corect documentele ce nu au fost clasificate corect de către clasificatorii tip SVM (Suport Vector Machine).
S-a utilizat pentru testare setul de date T2 ce conține doar 136 documente, iar pentru antrenare setul de date A1. Clasificatorul Bayes împarte documentele din T2 în 10 subseturi. În general rezultatele clasificării sunt mai bune spre deosebire de rezultatele obținute cu SVM, cel din urmă obținând un maxim de 18% în timp ce clsificatorul Bayes a obținut un maxim de 33,56%. În figura de mai jos au fost reprezentate rezultatele de clasificare din cele zece situații ca medie. Acest clasificator a fost testat pentru a se verifica daca rezultatele afișate pentru seturile de date A1 și T1 respectiv A2 și T2, urmînd a fi incluse într-un metaclasificator . În urma analizei datelor, acest clasificator obține rezultate mai bune în comparație cu clasificatorul SVM pentru setul de date T2.
Cercetările din mai multe domenii au proiectat rețele neunorale artificiale, astfel s-au rezolvat probleme legate de recunoșterea pattern-urilor, predicție, optimizare, control etc. Acestea pot fi aplicate în domenii ce nu sunt suficient de flexibile în utilizarea altor metode. Astfel, folosirea unei rețele neunorale artificială reprezintă o alternativă viabilă.
În evoluția sa, creierul uman a obținut trăsături ce nu se regăsesc în modelul von Neumann, sau apar într-o cantitate foarte mică.
Figura 3.2 Folosirea Clasificatorului Byes pentru clasificarea unor documente ce nu au fost clasificate corect de către clasificatorul SVM
Trăsăturile dobîndite de către creierul uman precum :
Paralelism masiv
Reprezentare și procesare distribuită
Abilități de învățare
Abilități de generalizare
Adaptabilitate
Procesarea informației pe bază de context
Toleranță la erori
Consum reudc de energie
Omul este dominat net de către calculatoarele numerice, în domeniul prelucrărilor numerice.
Cu toate acestea, omul poate rezolva fără un efort prea mare probleme complexe de percepție și recunoaștere a formelor cu o viteza mult superioară celor mai bune computere.
RNA (Rețelele Neunorale Artificiale) reprezintă sisteme de calcul cu paralelism mare formate dintr-un număr imens de elemente de procesare simple, astia avînd denumirea de neuroni. Neuronii țin cont de anumite principii de organizare în creierul uman.
3.3.1 Neuronului artificial
Acesta are la bază modelul lui McCulloch și Pitts acesta fiind generalizat în mai multe feluri. În figura următoare este prezentată cea mai cunoscută variantă.
Figura 3.3 Neuronul artificial – model
Neuronul artificial prezentat mai sus calculează suma ponderată a n semnale de intrare, la aceasta se mai adaugă o valoare denumită prag, aceteia i se aplică o funcție de activare astefel se generează la ieșire valori cuprinse în (0,1].
(3.14)
unde xi este semnalul de intrare i, iar wi sinapsa integrată intrării, este valoarea de prag (offset) aceasta transpunând iețirea S a neuronului. Lui S i se aplică funcția de activare f, ce are rolul de a normaliza ieșirea neuronului în domeniul necesar.
Funcțile de activare cel mai des întâlnite în figura 3.4 sunt:
funcția de activare treaptă, step (x)=
funcția de activare semn, sign (x) =
funcția de activare sigmoidală, sigmoid (x) =
funcția de activare gaussiană, Gauss (x) =
Figura 3.4 Funcțile de activare cel mai des întâlnite
Modelul neunoral prezentat mai sus, are funcția de actovare în treaptă. Dar cel mai cunoscut model neunoral este cel cu funcția de activare sigmoidală care este strict monoton crescătoare, mărginită și derivabilă:
(3.15)
unde α reprezintă un facor de scală ce are valori strict pozitive. Pentru α ce tinde spre infinit funcția sigmoidă ajunge funcția treaptă.
3.3.3 Învățarea rețelelor neuronale
O caracteristică importantă a inteligenței este reprezentată de capacitatea de învățare.Este dificil în a găsi o definiție a învățării, dar se poate spune că în RNA, învățarea se definește în modificarea rețelei pentru a se adapta la nevoile de rezolvare a unei probleme.De obicei se schimbă coeficienții de conectivitate sinaptică, uneori se modifică configurația rețelei și numărul de unități.
RNA are ca principal avantaj în comparație cu sistemele expert clasice, faptul că are loc o învățare prin exemple, în detrimentul folosirii unui set de reguli date de zătre user.
Sunt două categorii de învățare ținând cont de organizarea datelor de intrare:
învățarea nesupervizată, prin aceasta rețelei îi sunt prezentate doar datele de intrare, în acest caz rețeaua nu cunoaște informațiile legate de prezența sau valoarea erorii. În această situație rețeaua evoluează liber, iar la sfârșit se va constata rezultatul învățarii.
învățarea supervizată, în cadrul acesteia mulțimea de exemple de antrenament se organizează sub formă de intrări și ieșiri, apoi se specifică pentru fiecare pas, valoarea ce trebuie să o aibă ieșirea corectă, în cele din urmă rețeaua va genera datele de intrare. Pentru ca rețeaua să producă ieșiri cât mai realiste, se modifică ponderile.
Reinforcement learning reprezintă o variantă a învățării supervizate, aceasta furnizează rețelei o singură informație legată de prezența erorii dar nu și a valorii ei.
Rețelele își modifică ponderile în funcție de regulile de învățare, acestea depind de modul în care este construită rețeaua și de datele de intrare. Plecând de la aceast lucru se pot distinge patru tipuri cunoscute de reguli de învățare:
învățare prin corecția erorii;
regula lui Boltzmann;
regula lui Hebb;
învățarea competitivă.
5.3.4 Reguli de învățare prin corecție a erorii (“error-correction rules”)
În cadrul învățării supervizate, rețeaua deține ieșirea necesară pentru fiecare vector de intrare., iar ieșirea rețelei, de regulă nu este egală cu valoarea dorită. Semnalul de eroare este folosit de către părincipiul corecției erorii, scopul acestuia este minimizarea erorii.
Modificarea unui coeficient sinaptic w se face prin relația:
(3.16)
unde E reprezintă eroarea globală iar η reprezintă viteza de învățare.
Relația de mai sus stă la baza învățării în rețelele feed-forward multistrat
Prin utilizarea pantei gradientului se va căuta în spațiul ipotezelor de posibili vectori, pentru a se găsi ponderile ce aproximează cel mai bine exemplele de antrenament, aceasta este o regulă ce livrează bazele algoritmului Backpropagation, acesta fiind folosit pentru rețelele cu mai multe unități interconectate.
Panta gardienului are drept scop determinarea vectorului pondere ce minimizează eroarea plecând de la un vector pondere unițial arbitrar. Vectorul pondere este schimbat la fiecare pas, în direcția în care produce o pantă descendentă de-a lungul erorii. Procesul se continuă până în momentul în care se atinge eroarea minimă globală.
Relația lui Rosenblatt de minimizare a erorii, varianta simplificată:
(3.17)
în care w și x sunt vectorul ponderilor și vectorul de intrare, d este ieșirea dorită și y ieșirea reală.
În rețeaua Adaline are ca regulă de învățare regula Widrow-Hoff are ca bază minimizarea erorii.
(3.18)
unde wij reprezintă ponderea legăturii ieșirii cu intrarea j, iar x vectorul de intrare, T vectorul necer la ieșire și y vectorul ieșirii. O particularitate a regulii gradientului :
(3.19)
3.3.4.1 Perceptronul
Perceptorul este cea mai simplă rețea neunorală, acesta prezentată în figura de mai jos
Figura 3.5 Calculul ieșirii perceptorului
unde:
Într-un hiperplan în spațiul n, perceptorul este văzut ca fiind reprezentarea unei suprafețe de decizie. Relația hiperplanului este :
În acest fel perceptorul se poate folosi ca fiind un clasificator binar sau predicator, în care taken=1 / not taken = -1.
Principala problemă este cum se poate crea o regulă de învățare pentru percepton simplu. Considerăm pentru fiecare exemplu o regulă de învățare supervizată dD trebuie cunoscută ieșirea td.
ieșire reală
(.20)
Pentru formula E() suprafața sunt întotdeauna un paraboloid cu un singur minim global. Gradientul E() este reprezentat prin relația :
(3.21)
unde reprezintă vectorii unitate ortogonali în spațiul n. Regula de învățare prin care se produce cea mai rapidă micșorare a lui E:
echivalent cu :
În cele din urmă, relația regulei de învățare supervizată este:
(3.24)
Relația de mai sus poartă denumirea de gradient descendent sau regula delta. Algoritmul regulei delta este descris mai jos:
Un mod de a implementa semnalizarea erorii cu acest gradient se folosește relația:
(3.23)
Regula de semnalizare a erorii pentru gradientul descendent:
Însă folosirea regulii standard a gradientului descendent necesită foarte mult timp deoarece multiplele exemple se însumează, dar se folosesc în general cu o rată de învățare per exemplu mai mare în comparație cu rata de învățare per exemplu de la regula cu gradientul incremental descendent.
Se consideră ca ieșire a perceptorului O() = sgn() în schimbul O() = (), acesta poartă denumirea de regula de antrenare a perceptorului:
(3.24)
În situația în care exemplu de antrenament este corect clasificat, (t-o=0), ponderea rămâne aceiași.
3.3.5 Regula de învățare Boltzmann
Mașinile Bolzmann sunt defapt rețele simetrice (wij = wji), ce sunt formate din unități binare. Subsetul de intrare și ieșire, reprezintă acea parte a neuronilor ce sunt vizibili aceștia interacționând cu mediul, restul neuronilor fiind neuroni ascunși. Probabilitatea ca starea unei iețiri să fie 1 sau 0 este:
(3.25)
X reprezintă stările celorlalte unități, wijcoeficienți sinaptici valori de prag
După regula de învățare Boltzmann, poderile coeficienților sinaptici se modifică
(3.26)
unde η reprezintă rata de învățare
Prin regula de învățare Boltzmann se reduce eroarea, eroarea nu poate fi măsurată direct, ci ca fiind o corelație între ieșiri.
3.3.6 Regula de învățare Hebb
Aceasta este cea mai veche regulă de învățare și matematic se descrie astfel:
(3.27)
unde xi și yireprezintă avtivitățile neuronilor i,j, aceștia fiind conectați prin sinapsa wij iar η este rata de învățare
Regula de învățare a lui Hebb are avantajul faptul că învățarea se face local și depinde doar de neuronii alăturați modificarea ponderii unei sinapse, acest lucru ajută la implementarea în circuitele VLCI, sub formă analogică și digitală.
3.3.7 Regula de învățare competitivă
Această regulă de învățare are la bază “winner takes all”, astfel la un moment dat se va activa o singură unitate, comparativ cu regula de învățare Hebb unde se pot active mai multe unități simultan.
Regula prin care se modifică ponderile sinaptice:
(3.28)
3.3.8 Algoritmul de învățare Backpropagation
Acest algoritm în comparație cu celelalte algoritmuri, învață ponderile pe mai multe nivele pentru o rețea. Pentru minimizarea erorii dintre valoarea ieșirii și valoarea țintă se folosește panta gradientului.
Principala problemă pentru regula de învățare Backpropagation este căutarea spațiului ipotezelor, definit de valorile ponderilor pentru toți neuronii din rețea.
Mai jos este prezentat algoritmul cu activare sinusoidală, acesta se aplică rețelelor feed-forward cu două nivele de unități.
Backpropagation (exemple_antrenamen, η, nin, nout, nhidden)
Exemplele din antrenament formează o pereche de forma (), fiind valorile vectorilor de intrare iar valorile țintă ale vectorului de ieșire, η este rata de învățare ce are valorea între (0,1], nin este reprezentat de numărul de neuroni de pe stratul de intrare, nout numărul de neuroni de pe stratul de ieșire, nhidden reprezintă numărul de neuroni de pe stratul ascuns. Cu xij se notează intrarea de la unitatea i la unitatea j, iar ponderea de la unitatea i la unitatea j se notează cu vij
Se construiește o rețea cu nin intrări, nhidden unități ascunse și nout unități de ieșire
Se accesează toate ponderile din rețea cu valori aleatoare mici, precum;
Pentru fiecare (), din exemple_antrenament se execută:
Se implementează rețelei apoi se calculează ieșirea y ținând cont de fiecare neuron din rețea
Ținând cont de fiecare neuron de ieșire din rețea se calculează după formula (5.32)
Ținând cont de fiecare neuron din stratul ascuns se va calcula eroarea după formula (5.33)
Se calculează pentru nivelele anterioare din propagarea backward a erorii.
Se actualizează ponderile rețelei cu ajutorul formulei .
Algoritmul de mai sus este descris pentru o rețea feed-forward, acesta conține două straturi de unități. Fiecare unitate este conectată cu restul unităților din straturile precedente. Unitățile reportatoare sunt considerate ca fiind unitățile de intrare, acestea prezintă la ieșire valoarea pe care a primit-o la intrare.
3.5 Algoritmi bazați pe nuclee. Support Vector Machine (SVM)
Clasificarea VSM se bazează pe teoria învățării statice, fiind folosită cu succes în optimizarea mulțimilor de date de dimensiuni mari, chiar daca referirea se face la numărul de articole de clasificat sau la numărul de caracteristici prin care se prezintă.
Algoritmi SVM ai rolul de a găsi un hyperplan, acesta ar urma să separe datele de intrare în două clase, mai pe scurt algoritmul constă în determinarea parametrilor ecuației generale a planului. În general algoritmul funcționează doar pentru două clase, dar se poate adapta pentru mai multe clase. Se urmărește găsirea unei linii care să separe punctele aflate în clasa pozitivă de punctele din clasa negativă, așa cum a fost reprezentat în figura de mai jos.
Figura 3.8 – Hiperplanul optim pentru separare
După reprezentarea figurii 5.8, se consideră că datele sunt clasificate în două clase, astefel se presupune că cele două clase se vor numi clasa punct și clasa pătrat. Însă deși pare a fi o problemă simplă, trebuie precizat că se va ține cont că o linie optimă de clasificare trebuie să clasifice corect toate datele ce sunt generate cu aceiași distribuție. Sunt o multitudine de hiperplane ce întrunesc condițile de clasificare corectă, dar rolul algoritmului este acela de a alege hiperplanul cel mai apropiat de task-ul cerut. Funcția cu ajutorul căreia se face separarea:
(3.47)
Funcția de mai sus se numește funcție de decizie, în care w este vectorul pondere ortogonal pe hiperplan, marginea hiperplanului este reprezentată de scalarul b, x reprezintă eșantionul curent, (x) fiind funcția ce trece pe x.
Dacă x,y Rn cu x = (x1,x2,….xn) și y = (y1,y2,….yn), astfel se poate zice că valoarea ce măsoară suprafața determinată de cei 2 vectori este produsul scalar al vectorilor, aceasta se notează cu <x,y> cu următoarea formulă de calcul:
(3.48)
Astfel se poate spune că x este ortogonal pe y, în situația în care produsul lor scalar este 0, acest lucru se poate scrie:
<x,y>=0 (3.49)
În situția în care e are lungimea 1, <w , (x)> = lungimea proiecției pe x și pe direcția lui w. De regulă, w va fi scalat prin astfel se va obține un vector de lungime unitară. este normal lui w, deci =<w,w> se mai poate numi si normă euclidiană.
Hiperplanul pentru separare se bazează pe două trăsături fundamentale:
Trăsătura ce precizează existența unui hiperplan optim pentru separare a datelor, acesta fiind hiperplanul cu cea mai mare valoare a lui b;
Trăsătura ce precizează că puterea de separare a hiperplanului scade în momentul creșterii marginii.
Soluția următoarei ecuații determină hiperplanul optim:
(3.50)
Pentru datele separabile în spațiul vectorial de intrare, hiperplanul este calculat direct prin datele empirice. Iar pentru datele care nu sunt separabile, hiperplanul este calculat intr-un spațiu de dimensiune mai mare, Acesta este exprimat matematic pentru a se obține un hiperplan optim prin folosirea unei probleme de optimizare astfel:
(3.51)
Având restricția yi(<w,xi>+b)1 pentru i=1,…,m, unde τ este funcția obiectiv, restricția mai este numită inegalitatea de constrângeri.
Se poate observa că datorită restricției se face clasificarea corectă. Deci f(xi), +1 pentru yi egal cu +1 și -1 pentru yi = -1. În situația în care =1, atunci o parte in restricție este egală cu distanța de la xi la hiperplan, pentru a se transforma această distanță, de regulă se împarte yi(<w, xi >+b) prin . Marginea totală va fi maximizată , pentru i=1,…,m cu w de lungime minimă.
Este dificil de rezolvat problema de optimizaare, deoarce sunt costuri ridicate pentru calcul, astfel pentru rezolvarea ei există posibilitatea de a se folosi problema duală, aceasta oferind aceiași soluție conform relaților matematice. Astfel se va implementa Langrangian-ul și multiplicatorii Lagrange:
(3.52)
Se poate observa că restricțile sunt implementate în al doilea termen al Lagrangian-ului, fără a mai fi necesar să fie explicate. În situația în care restricția este coruptă, yi(<w, xi >+b)-1> 0). În cazul în care L descrește w și b se vor modifica, iar yi(<w, xi >+b)-1 nu trebuie să devină un număr arbitrar negativ foarte mare, astefel modificările suferite de către w și b se vor face astfel încât să sadisfacă restricțile.
Se poate înțelege că pentru toate restricțile ce nu se potrivesc cu egalitatea αi=0 acesta maximizândul pe L. Următoarea condiție pentru optimizarea lui Karush-Kuhn-Tucker (KKT) spune că se vor anula derivatele L, în raport cu variabilele primare, astfel:
(3.53)
de aici rezultă că:
(5.54)
Support Vectors adică pattern-urile α diferite de 0, împreună cu condițiile KKT:
(3.55)
Totuși exemplele e antrenament sunt irelevante, deoarece se pot elimina restricțile yi(<wxb >+b)-1, astfel acestea vor lipsi din formula finală. Datorită lor putem vedea că hiperplanul este complet defini de cele mai apropiate pattern-uri, de accea soluția nu ar trebui să depindă de restul exemplelor.
Dacă se înlocuiește formula 5.54 în Lagrangian vor fi eliminate variabilele w și b, astfel va apărea problema de optimizare duală, ce rezolvă în practică:
(3.56)
(3.57)
(3.58)
folosind condițiile KKT se poate calcula variabila primară b.
În general pentru rezolvarea problemei duale de multe ori se activează un singur subset de restricții. De exemplu, în momentul în care se bagă o bilă într-o cutie, acesta se va rotogoli într-unul din colțuri, astfel restricțile pereților neatinși de bilă devin irelevante fapt ce duce la eliminarea acestor pereți.
Practic vorbind hiperplanul de separare poate fi scos din discuție dacă clasele sunt suprapuse.
Prin folosirea variabilelor discrete, restricțile vor fi restricțile yi(<w,xb >+b)-1- ζ pentru i=1,…,m. Hiperplanul optim folosit este reprezentat de controlul capacității de clasificare și suma variabilelor discrete Σi ζi, se poate spune că în a doua parte se livrează o limită superioară a numărului de erori de antrenament, aceasta având numele de clasificare cu margine soft, în acest caz relația devine:
(3.59)
C>0, folosind aceleași restricții calculânduse maximizarea marginii și minimizarea erorii de antrenare. Prin rescrierea cu termeni de multiplicator Lagrange apare următoarea restricție:
(3.60)
Dacă sunt generate costuri mari prin găsirea unui hiperplan optim, se va încerca ideea SVM prin maparea datelor de intrare într-un alt spațiu de dimensiuni mari folosind funcția ɸ, apoi se va încerca găsirea unui hiperplan optim ce generează costuri mici în spațiul cel nou. Acest lucru va duce la crearea unei granițe de decizie neliniare în spațiul datelor de intrare. Datorită faptului că traferul datelor într-un spațiu mai mare generează calcule mai mari si mai dificile, se va folosi trucul nucleu. Acesta prin calcularea produsului scalar a 2 vectori x și x’, trucul nucleu substituie cu un nucleu produsul scalar, apoi se va calcula în spațiul cel nou.
Matematic trucul nucleu va fi reprezentat :
(3.61)
(3.62)
Principalul avantaj pe care îl are acest algoritm este faptul că nu este necesar transferul datelor într-un spațiu nou, deci nu sunt necesare calcule greoaie, pe lângă acesta rezultă o dimensiune mică a setului de date de antrenament. Un alt avantaj este acela că oricât de mare ar fi dimensiunea datelor de intrare nu crește timpul de calcul, dare acest fapt nu este valabil și în cazul rețelelor neunorale.
De asemenea algoritmul de mai sus se bazează pe ideea că datele de intrare sunt în doar două clase. Acesta fiind un algoritm de clasificare binară, etichetele luând doare două valori. Totuși în practică sunt necesare mai mult de două clase la o problemă de clasificare. Folosind clasificarea binară se pot folosi anumite metode pentru preluarea mai multor clase: clasificarea unul versus altul, se aleg elementele ce aparțin unei clase astfel se vor diferenția de restul elementelor. Aici se va calcula un hiperplan optim pentru fiecare clasă . La ieșirea algoritmului se va folosi valoarea maximă a hiperplanurilor de separare:
(3.63)
Metoda acesta are o complexitate liniară, și pentru n clase se vor calcula n hiperplane.
O altă metodă folosită este clasificarea perechilor ,aceasta este formată din perechi ce conțin două clase, urmând a se calcula câte un hiperplan de separare pentru fiecare.
De exemplu, dacă sunt M clase se va calcula hiperplane, complexitatea acestei metode fiind polinomială. Avantajul acestei metode fiind faptul că hiperplanul optim este de dimensiuni mici.
Clasificatori hibrizi. Metaclasificatori
Clasificarea hibridă are la baza alegerea clasificatorului corect. O problemă importantă în cazul acestora apare în momentul în care sunt utilizați mai mulți clasificatori, și este greu a se ști dacă clasificatorul ales este necesar, însă acesta problemă se poate rezolva ușor prin folosirea ansamblurilor de clasificatori. Ideea de bază fiind a învăța un metaclasificator să afișeze gradul de corectitudine pentru fiecare clasificator de bază.
În funcție de încrederea acordată unui clasificator se va face selectarea pentru a se eticheta o instanță, încrederea este acordată datorită clasificărilor corecte pentru instanțele de genul respectiv.
Fiecărui clasificator i se cere să implementeze o clasă la instanța curentă , urmând ca metaclasificatorul să decidă cea mai de încredere clasificare. Prin folosirea mai multor clasificatoare se crește acuratețea de clasificare. Un al avantaj al metaclasificării fiind posibilitatea de a exploata paralelismele funcționale.
Se poate abuza de diversitatea clasificatorilor folosiți pentru a se reduce eroarea de varianță nefiind necesară mărirea erorii de prag. În unele cazuri metaclasificatorul va reduce eroarea de prag în situația clasificatorilor cu margini largi. Folosirea temaclasificatorilor este facilă în mai multe domenii precum: clasificarea textului, bioinformatică, finanțe, medicină, geografie, industrie etc.
Ținând cont de utilitatea clasificatorilor hibrizi, se pot distinge câțiva factori ce fac diferența dintre tipurile de ansambluri:
Clasificatorii ce interacționează în cadrul clasificatorilor hibrizi, ținând cont de acest lucru clasificatorii se împart în:
Metaclasificatori secvențiali;
Metaclasificatori concurenți.
Folosirea strategiei de combinare a clasificatorilor, acesta este implementată de un algoritm inductiv. Un mod simplu de a combina clasificatorii este acela prin care se determină o ieșire pe baza ieșirilor din clasificatorii individuali.
Crearea unui ansamblu de clasificatori prin generarea diversității, așadar clasificatorii vor lucra eficient numai dacă există o anumită diversitate. Acest lucru se poate obține prin diferite forme de prezentare a datelor de intrare.
CAPITOLUL IV – Clustering și Asocieri
A. Clustering
4 Algoritmi de clustering. Paradigma actuală
Există o serie de algoritmi importanți folosiți pentru clustering. Aceștia vor fi prezentati în continuare.
4.1 Taxonomie
Prin diverse strategii se pot aranja datele în diferite grupuri. Tehnicile de clustering pot fi împărțite în două mari categorii:
tehnici de clustering ce se bazează pe partiționarea datelor;
tehnici de clustering ce se bazează pe metode ierarhice.
De asemenea, pe lângă cele două categorii de mai sus, algoritmii de clustering se mai pot împărții astfel:
algoritmi bazați pe densitate;
algoritmi bazați pe rețele;
algoritmi bazați pe modele.
Figura 3.1 Taxogomia algoritmilor de clustering
Se presupun n obiecte, acestea trebuiesc grupate în k grupe, folosind o metodă de partiționare, astfel se formează k partiții din n obiecte, de unde fiecare partiție care de mai numește și cluster, kn. Formarea clusterilor ține cont de o funcție numită funcție de disimilaritate, de aici rezultă că obiectele din clusteri diferiți sunt disimilare, iar obiectele dintr-un cluster sunt similare. Este necesar ca gruparea să îndeplinească două condiții:
Un cluster trebuie să fie compus din cel puțin un obiect;
Fiecare obiect trebuie să fie în componența unui singur cluster.
În aceste metode se folosește următoarea idee de bază: prima dată se dau un număr de k ce va reprezenta numărul de clusteri ce se doresc, urmând a se aplica o metodă de partiționare ce va grupa un număr de k clusteri.
Prin folosirea acestei metode, mai folosim și tehnica de relocare iterativă, ce are ca scop îmbunătățirea partiționării, folosind mutarea obiectelor dintr-un grup în altul. Rezultatul la care trebuie să se ajungă în urma mutării este acela ca clusterii formați să aibă în componență obiecte asemănătoare.
Există trei tipuri de algoritmi ce sunt folosiți pentru partiționare:
Algoritmi de tip k-means – aceștia au pentru fiecare cluster valoarea medie a obiectelor;
Algoritmi de tip k-Medoids – aceștia au pentru fiecare cluster reprezentat de obiectul ce se află cel mai aproape de centrul de greutate al clusterului;
Algoritmi de tip probalistic – acestea pleacă de la ideea că datele sunt formate dintr-o amestecătură de populații ale căror distribuții și probabilități este necesar să fie determinate.
Algoritmii prezentați mai sus se utilizează pentru baze de date mici și mijocii, formând clusteri sferici.
4.1.1. Algoritmul de tip k-Means
Algoritmul k-Means este cel mai cunoscut și folosit algoritm pentru știință și industrie. În acest algoritm se reprezintă k clusteri Cj iar valoarea lor (mean) este cjce se calculează ca centrul de greutate al obiectelor din Cj. Valoarea lui k se stabilește la începutul algoritmului. Pentru evaloarea clusteringului se folosește eroarea medie pătratică reprezentată matematic astfel:
Se implementează la întâmplare k centre în spațiul n- dimensional;
Se calculează distanța până la centroizi pentru fiecare obiect, documentul curent va fi introdus în clusterul corespunzător centroidului față de acesta obtinându-se distanța minimă. Când vine vorba despre distanță există mai multe metode, în funcție de acestea se partilarizează algoritmul utilizat. Foarte des se utilizează: distanța euclidiană, distanța Manhattan sau distanța Minkovski.
După implementarea tuturor obiectelor în clusteri, se calculeazp din nou poziția centroizilor k acestia fiind centrul de greutate al eșantioanelor folosit pentru fiecare cluster;
Procesul de recalculare se repete până în momentul în care poziția lui k nu se mai modifică semnificativ;
Obiectele corespunzătoare centroizilor formează obiectele celor k clusteri construiți.
Sunt metode în care se aleg la întâmplare k obiecte din N disponibile în baza de date, aici N>>k.
Pseudocodul algoritmului este reprezentat mai jos:
Intrări:
x = {xi,…,xn} obiectele de clusterizat
k – numărul clusterilor de obținut
Ieșiri:
C = {ci,…,ck} centroizi clusterilor
m: x C apartanența la cluster
Algoritmul k-Means
Inițializează C (aleator)
for each xj X
m (xj) = ar min distanta (xj, cn)
end
while m se modifică
for each i {1,k}
recalculează ci ca centroid {c|m(x) = i}
end
for each x
m (xj) = ar min distanta (xj, cn)
end
end
return C
În următoarele figuri sunt reprezentați pașii algoritmului k-Means, a fost folosit un set de 50 puncte implementate la întâmplare folosind o distribuție gaussiană. Astfel s-a folosit pentru calcularea distanței in Figura 3.3 – distanța Euclidiană, în Figura 3.4 – distanța Manhattan iar în Figura 3.5 – distanța Minkovski.
Figura 4.2 Distanța euclidiană
Figura 4.3 Distanța Manhattan
Figura 4.4 Distanța Minkovski
Acest algoritm este scalabil și foarte folositor, pentru că complexitatea computațională este O (nkt), aici n reprezintă numărul total de obiecte , k fiind numărul clusterilor și t numprul iterațiilor. Algoritmul folosește centrul de greutate al centroidului, dar acesta se poate implementa doar bazelor de date numerice.
Dezavantajele algoritmului k-means:
Rezultatele depind de alegerea inițială a numărului de clusteri;
În unele cazuri optimul global este diferit de optimul local;
Este ușor de aflat valoarea optimă a lui k;
Algoritmul prezintă sensibilitate la zgomot;
Algoritmul acceptă doar valori numerice;
Fără să conțină ceva clusterii rezultați pot fi dezechilibrați.
4.1.2 Algoritmul de tip k-Medoids
Este o variantă adaptată a algoritmului k-Means, se va alege un element important, sau medoid, pentru fiecare cluster la fiecare iterație. Metoda de calcul a metodoidului se bazează pe găsirea unui element i din cluster ce face un cost mai mic:
(4.1)
Unde Ck este clusterul ce îl conține pe i, și d(i,j) reprezintă distanța de la obiectul i la obiectul j.
Se pot deosebi două avantaje prin folosirea obiectelor existente ca centru de cluster. Primul avantaj este acela că un medoid poate descrie intr-un mod util clusterul. Al doilea avantaj se referă la faptul că nu este necesar calculul repetat al distanțelor la fiecare iterație, pentru că după calcul se salvează într-o matrice de distanțe.
Algoritmul k-Medoids are următorii pași:
Se aleg k obiecte aleatoriu să fie medoidoizii inițiali ai clusterilor
Se atribuie fiecărui obiect clusterului asociat metodoidului cel mai apropiat și se calculează costul 3.2.
Se recalculează în ce poziție se află metodoizii k.
Apoi se vor repeta 2,3 până când medoizii nu se vor mai modifica sau costul rămâne constant.
K-Modoids este folositor în bazele de date mici, aproximativ 100 documente, la utilizarea pe seturi mari de date apare un cost computațional mare, iar procesul de clatering devine lent. Pentru folosirea algoritmului Partitioning Around Medoids (PAM) la seturi de date mari Kaufman și Rousseew s-a format algoritmul Clustering Large Applications (CLARA), acesta se bazează pe folosirea algoritmului PAM pe un set de date dat. Dacă acesta este ales întâmplător și va reprezenta corect setul de date.
Algoritmul CLARA poate fi scris sub formă de pseudocod astfel :
unde,
M fiind setul de medoizi, d(Oi, Oj) este distanța dintre Oi și Oj și ret (M, Oi) înapoiază un metoid din M ce este cel mai apropiat de Oi.
Este necesară folosirea algoritmului Clustering Large Applications based upon RANdomized Search (CLARANS), pentru scalabilitatea și calitatea algoritmului CLARA. Algoritmul CLARANS se găsesc k medoizi și este văzută ca și căutarea într-un graf. În graf este reprezentat un mod de k obiecte { O1,…, Ok } ceea ce arată că O1,…, Ok sunt aleși. Dacă seturile a două noduri diferă cel puțin cu un singur obiect, atunci cele două noduri sunt vecine. Se poate constata că fiecare nod din graf are k(n-k) vecini. O formație de k metodoizi reprezintă un nod, acesta corepunde unui posibil rezultat al clusteringului.
Algoritmul CLARANS folosește un mod de căutare euristică pe baza unei selecții aleatorii. Acesta pleacă de la un nod aleatoriu în graf și folosește unul dintre vecinii săi aleși la întâmplare, iar dacă costul rezultat este mai mic în comparație cu cel al nodului curent, algoritmul se repornește de la acest nod, continuând selectarea vecinilor. În cazul în care costul rezultat este mai mare algoritmul va examina în continuare nodurile vecine, până în momentul în care este găsit un nod vecin mai bun sau se atinge numărul prestabilit de vecini. Nodul ales este numit minim local. Pentru a se alege o soluție bună, algoritmul repetă căutarea plecând de la un nod diferit pentru un număr predeterminat.
Dacă numim maxneighbor numărul maxim de vecini și numlocal numărul de minimele locale obținute, vom reprezenta algortmul CLARANS astfel:
Este recomandat ca numLocal să fie pornit cu 2 iar parametrul maxNeighbor cu valoarea:
În comparație cu algoritmul CLARA, CLARANS sustrage un eșantion cu un grad random mai mare. Prin procesul de clustering se caută într-un graf iar fiecare nod constituie o eventuală soluție.
4.2.1 Metode ierarhice
Se pot distinge două tipuri de abordări pentru metodele ierarhice:
Abordările aglomerative, acestea folosesc abordarea „bottom-up”, pentru fiecare obiect este asignat la început un cluster, urmănd ca pe baza unor măsuri de similaritate să se unească clusterii până în momentul în care sunt uniți într-unul singur, sau până se ajunge la condiția de oprire dată, astfel se va crea o structură ierarhică
Abordări divizive, acestea folosesc abordarea „top-down”, se consideră că la început toate obiectele se află într-un singur cluster, ulterior clusteri vor fi divizași în clusteri mai mici prin iterații succesive, până în momnetul în care obiectele devin clusteri sau se ajunge la condiția de oprire.
În clusteringul ierarhic există o mare problemă și anume faptul că procesul de divizare sau unire este ireversibil, totuși acest tip de algoritmi au și un avataj major și anume numărul redus de calcule, deoarece numai este necesar calculul diverselor combinații.
Metodele de partiționare și cele ierarhice sunt combinate de algoritmii Balanced Iterative Reducing and Clustering (BIRCH) și Clustering Using Representatives (CURE).
4.2.2 Algoritmi aglomerativi ierarhici (HAC)
Acest algoritm, fiecare obiect are rolul de a forma un cluster, apoi câte 2 clusteri ce sunt uniți prin similaritatea lor. Algoritmul este repetat până toți clusterii sunt uniți într-unul singur. Disimilaritatea este reprezentată de distanța dintre doi clusteri. Acesta se exprima pe baza distanței euclidiene sau pe baza cosinusului unghiului între cei doi vectori ce formează clusterii.
4.2.2.1 Disimilaritatea dintre doi clusteri în algoritmi ierarhici aglomerativi
Se pot remarca mai multe tipuri de algoritmi, ținând cont de metoda de calcul a disimilarității:
Single link – între doi clusteri disimilaritatea este dată de către disimilaritatea celor mai apropiate obiecte dintre cei doi clusteri, dacă există doi clusteri A și B cu obiectul a A și obiectul b B apare relația matematică:
(4.2)
Complete link – între doi clusteri disimilaritatea este dată de către disimilaritatea a celor mai dismilare obiecte dintre cei doi vectori. Dacă există doi clusteri A și B cu obiectul a A și obiectul b B apare relația matematică:
(4.3)
Average link- – între doi clusteri disimilaritatea este dată de către media disimilarității obiectelor calculată între cei doi clusteri. Acest lucru fiind reprezentat matematic astefel:
(4.4)
Centroid link – -între doi clusteri disimilaritatea se calculează ca fiind disimilaritatea dintre centroizii clusterilor. Acest lucru fiind reprezentat matematic astefel:
(4.5)
Metoda lui Ward – aceasta folosește distanța dintre doi clusteri, astfel valoarea creșterii sumei pătratelor distanțelor când se unesc cei doi clusteri. În formula de mai jos este repezentată creșterea sumei pătratelor distanțelor (A,B):
(4.6)
unde mj reprezintă centroidul clusterului j iar nj numărul punctelor din j.
(A,B) = 0 , datorită faptului că fiecare cluster este format dintr-un singur obiect. Astfel prin unirea clusterilor (A,B) crește și prin folosirea ecuației 3.8 se încearcă minimizarea valorii. În cadrul metodei Ward dacă există două perechi de clusteri cu centrele la distanțe identice se vor uni clusterii mai mici.
Metoda SAHN- calculul unei distanțe dA(B,C) a unui cluster notat cu A și nk punctele față de un alt cluster notat cu (B,C), se calculează astfel:
(4.7)
Iar α,β,γ sunt coeficienți și sunt reprezentați în următorul tabel:
Tabel 3.1 – Reprezentarea coeficienților formulei generalizate
Pentru a se calcula costul unirii clusterilor se poate folosi metoda Ward. Astfel se va micșora k până (A,B) ajunge la o valoare mare a costului. Se consideră că în urma unirii se va pierde multă diferență specifică fapt ce ar duce la oprirea algoritmului la doi clusteri obținuți înainte de a crește costul.
4.2.3 Algoritmul BIRCH
Balanced Iterative Reducing and Clustering este un algoritm hibrid, acesta lucrează cu baze mari de date și folosește o structură ce se salvează în memoria principală.
Structura lui BIRCH are două concepte:
Clustering Feature;
CF-Tree.
Clustering Feature (CF) – este defapt un triplet ce înmagazinează informația unui subcluster de puncte. Se dau N puncte într-un spațiu n- dimensional , {Xi} este un subluster CF fiind reprezentat ca:
(4.8)
Clustering Feature Tree – reprezintă un arbore de tip B+. Acesta este format din frunze, acestea conțin mai multe intrări ele reprezentând un cluster, clusterele pot constitui subclustere ale intrărilor și noduri ce sunt reprezentate din clustere formate din clusteri din nodurile copil. Datele se implementează în arbore dinamic ținând cont de doi parametri: pragul T și factorul de ramificare B pentru dimensiunea unei intrări.
Pentru a se adăuga date în arbore se foloște nodul frunză, în cel mai apropiat cluster pentru acel element respectând pargul T. Dacă se depăsește T , se construiește un arbore nou urmînd a se introduce un nou punct. Se vor actualiza nodurile arborelui de la frunze până la rădăcină.
Ținând cont de faptul că arborele salvează direct în memorie, este posibil ca T să nu aibă suficientă memorie, iar prin mărirea lui T se va micșora arborele.
BIRCH lucrează în două etape:
Construcția arborelui CF, ce este defapt o compresie a datelor fără a le modifica structura;
Se aplică un algoritm ierarhic la nodurile frunză.
Figura 4.6 – CF Tree
Acest algoritm este scalabil, și afișează rezultate bune în cazul clusterilor sferici, iar în cazul formelor arbitrare acesta obține rezultate slabe.
4.2.4 Algoritmul CURE
În general algoritmii obțin rezultate bune doar în cazul clusterilor sferici sau asemănători dar sunt sensibili la zgomot. Clustering Using Representatives folosește clustering ierarhic și partițional în acest fel clusteri sferici ne mai fiind favorizați.
Acest algoritm utilizează un număr fix de puncte reprezentative pentru un cluster.
4.2.5 Algoritmi divizivi
Acest algoritm pleacă un cluster construit din toate obiectele, apoi folosind o metodă de divizare ce este aplicată recursiv se ajunge la clusteri construiți dintr-un singur obiect.
În prima etapă a unei metode aglomerative, se consideră că toate unirile posibile se va ajunge la un număr de combinații iar pentru utilizarea metodei ierarhice, avem 2n-1-1 șanse de a împărți datele ăn două grupuri. Numărul acesta fiind mult mai mare comparativ cu cel din metoda aglomerativă.
Algoritmul are la bază același principiu precum algoritmul AGglomerative NESting , numai că pleacă de la un cluster format din toate obiectele, și separă clusterul în doi subclusteri, acest proces se repetă până în momentul în care obiectele ajung să fie într-un singur cluster, sau până se va ajunge la condiția de oprire.
43
ș
a
Regula extrasă nu trebuie să fie restricționată de numărul de obiecte cumpărate în acel moment, înainte sau după. Există însă și posibilitatea de a specifica anumite constrângeri pe reguli (de exemplu doar reguli care invoca anumite obiecte, cum ar fi: bere). Tiparele secvențiale maximale găsite trebuie să fie susținute de mai mult decât un procentaj specificat de clienți. Fiecare regulă are două măsuri suportul și confidența. Pornind de la aceste formulări inițiale, se definesc conceptele de bază utilizate.
a) Frecvența unui articolset este numărul total de tranzacții care conține acel articolset.
b) Suportul (preponderența) unei reguli X ⇒ Y este procentul de tranzacții din baza de date care conține X ∪ Y. Pentru calculare suportului folosim formula:
S(X ⇒ Y) = P(X ∪ Y) (4.9.)
Sau
Suportul = (4.10.)
Interpretare: Regula de asociere este validă în s% din totalul tranzacțiilor.
c) Confidența (încrederea în regulă) ( α ) unei reguli de asociere X ⇒ Y este raportul dintre numărul de tranzacții care conțin X ∪ Y și numărul de tranzacții care conțin X.
α (X ⇒ Y) = P(Y/X) = P (X ∪ Y) / P(X) (4.11.)
sau
Condidența = (4.12.)
Interpretare: Dacă X și Y sunt în același coș (sunt cumpărate de aceeași persoană), atunci Z este de asemenea în coș în α % din cazuri.
d) Scopul unei reguli de asociere este de a identifica toate regulile X ⇒ Y cu un suport minim și o confidență minimă. Aceste valori sunt date ca și intrări ale problemei, fiind stabilite de utilizatori sau de specialiști în domeniu.
4.3.1 Algoritmi pentru descoperirea regulilor de asociere
Descoperirea regulilor de asociere are ca scop descoperirea unui set de atribute comune care aparțin unui număr mare de obiecte dintr-o bază de date în general. Pentru descoperirea asocierilor, se presupune că există un set de tranzacții, fiecare tranzacție fiind o listă de articole (listă de cărți, listă de alimente). Un utilizator ar putea fi interesat de găsirea tuturor asocierilor care au s% suport (preponderență) cu α % confidență (încredere), așadar:
trebuie găsite toate asocierile care satisfac constrângerile utilizatorului;
asocierile trebui găsite eficient dintr-o bază de date de dimensiuni mari.
O dată cu progresul în tehnologia codurilor de bare, firmele de comercializare a produselor au acumulat și stocat cantități imense de date despre produse, despre vânzări referite ca și date despre coșul de cumpărături (basket data). În cazul acestor tipuri de date, o înregistrare (articol, item) constă în mod tipic dintr-un identificator de tranzacție, data tranzacției și produsele cumpărate la acea tranzacție.
Firmele de succes privesc aceste baze de date ca și părți esențiale ale infrastructurii de marketing. Ele sunt interesate în introducerea unor procese de marketing conduse de informații, coordonate prin folosirea tehnologiilor de baze de date care să permită agenților de marketing să dezvolte și să implementeze programe și strategii de marketing adaptate diverselor categorii de clienți. Primele abordări ale problemei le-a făcut Agrawal care a propus algoritmul AIS în anul 1993 . În anul 1994, tot el a propus algoritmul APRIORI. În anul 1995, apare algoritmul SETM propus de Houtsma și Swami. Însă algoritmul APRIORI a avut cel mai mare impact, rămânând și la ora actuală tehnica majoră utilizată de producătorii comerciali pentru a detecta seturile frecvente de item-uri.
Găsirea acestor tipuri de reguli sunt folosite adesea atât în analizarea coșului de cumpărături, cât și pentru design-ul de cataloage, pentru așezarea mărfurilor în rafturi, pentru categorisirea clienților pe baza tiparelor de cumpărături pe care aceștia le fac, etc.
De obicei, așa cum am mai arătat, bazele de date implicate în astfel de aplicații sunt de dimensiuni foarte mari. Din acest motiv, este foarte importantă utilizarea unor algoritmi cât mai rapizi pentru aceste aplicații.
Descoperirea regulilor frecvente de asociere dintr-o bază de date de dimensiuni mari este o problemă complexă deoarece spațiul de căutare crește exponențial cu numărul de atribute din baza de date și cu obiectele bazei de date. Cele mai recente abordări sunt de natură iterativă necesitând scanări multiple ale bazei de date, ceea ce este foarte costisitor.
4.3.2. Algoritmul APRIORI
Algoritmul APRIORI este cel mai cunoscut algoritm pentru descoperirea regulilor de asociere și este folosit în cele mai multe produse comerciale. El a fost propus pentru a extrage articolset-uri frecvente folosind generarea candidaților. Algoritmul folosește proprietatea itemset-urilor frecvente:
Orice subset al unui articolset frecvent trebuie să fie la rândul său frecvent.
Algoritmul pornește de la presupunerea că un articolset este format din două câmpuri: unul care păstrează numărul de tranzacții suportate de articolset-ul respectiv (un contor) și altul un set de articole.
În prima parte a algoritmului, se numără, pentru fiecare articol i ∈ L în câte tranzacții apare i. Dacă rezultatul depășește suportul minim smin atunci acel articol devine 1-articolset (1 – itemset) frecvent (set de articole frecvente de lungime 1). Orice pas ulterior, de exemplu pasul k, constă mai departe din două faze.
Figura 4.7 – Algoritmul APRIORI
În prima fază, articolset-urile frecvente găsite la pasul (k -1) sunt folosite pentru generarea articolset-urilor candidat Ck, folosind funcția AprioriGen, descrisă în figura 3.32. În faza a doua se scanează baza de date D și se calculează, pentru fiecare tranzacție t, care dintre candidați se găsesc în t. Dacă un candidat se găsește în t, contorul său este mărit cu 1. Pentru un calcul rapid, se determină într-un mod eficient candidații din Ck care sunt conținuți într-o anumită tranzacție t cu ajutorul funcției.
4.3.2.1. Funcția AprioriGen
Funcția AprioriGen constă la rândul ei din două faze. Ea primește ca și argument Lk-1, setul tuturor (k-1) articolset-uri frecvente și întoarce un superset al setului tuturor k- articolset-urilor frecvente.
În prima fază, numită faza reuniune, se reunește Lk-1 cu el însuși. Se presupune că articolele unui articolset sunt sortate în ordine lexicografică. Această primă fază generează mai multe articolset-uri decât este necesar. În faza a două se șterg toate itemset-urile c ∈ Ck a căror oricare (k-1) subset nu se regăsește în Lk-1.
Figura 4.8 – Funcția AprioriGen
Avantaje și dezavantaje ale algoritmului APRIORI:
a) Avantaje:
– utilizează proprietățile articolset-urilor frecvente;
– poate fi ușor paraleliza;
– este ușor de implementat.
b) Dezavantaje:
– presupune că baza de date tranzacțională este încărcată în memorie;
– necesită mai mult de m scanări ale bazei de date.
4.3.3. Algoritmul SAMPLING (de eșantionare)
Pentru a facilita reducerea numărării articolset-urilor din bazele de date de dimensiuni mari se folosește de obicei eșantionarea bazei de date. Algoritmul SAMPLING original reduce numărul de parcurgeri ale bazei de date la una în cazul cel mai favorabil și la două în cazul cel mai nefavorabil Eșantionul din baza de date este ales astfel încât să poată fi încărcat în memorie. După aceasta, orice algoritm, cum ar fi Apriori, poate fi utilizat la găsirea seturilor frecvente din eșantion. Acestea sunt văzute ca și seturi de articole potențial frecvente (potentially large – PL) și sunt utilizate ca și seturi candidat care sunt numărate folosind întreaga bază de date. În plus, seturile candidat sunt determinate prin aplicarea unei funcții de graniță negativă (negative border function – BD-) asupra setului de articole frecvente din eșantion. Setul total de candidați C este calculat cu relația următoare: C = BD- (PL) ∪ PL. Funcția de graniță negativă este o generalizare a algoritmului Apriori-Gen. Această funcție este definită ca un set minimal de seturi de articole care nu sunt în PL, dar ale căror subset-uri sunt toate în PL.
Pentru a ilustra această idee folosim următorul exemplu: Presupunem că setul de articole este {A, B, C, D}. Setul de articole frecvente găsit în eșantionul din baza de date este PL = {A, C, D, CD}. La primul pas scanăm întreaga bază de date, apoi generăm seturile de candidați după cum urmează:
C = BD- (PL) ∪ PL = { B, AC, AD}∪ {A, C, D, CD}.
Avantaje și dezavantaje ale algoritmului SAMPLING:
a) Avantaje :
– reduce numărul de scanări ale bazei de date la una în cel mai bun caz și la două în cel mai rău caz;
– măsoară mai bine.
b) Dezavantaje :
– la a doua trecere există un număr mai mare de potențiali candidați.
4.3.4. Algoritmul PARTITIONING ( de partiționare)
Diferite abordări ale generării articolset-urilor frecvente a fost propuse pe baza partiționării seturilor de tranzacții. Algoritmul PARTITIONING abordează problema generării seturilor de articole frecvente bazându-se pe o partiționare a setului de tranzacții din baza de date. Astfel, baza de date D este divizată în p partiții: D1, D2, …, Dp. Partiționarea poate îmbunătăți performanța găsirii seturilor de articole frecvente prin câteva metode:
Prin luarea în considerare a proprietății unui articolset frecvent, știm că un articolset frecvent trebuie să fie frecvent în cel puțin una din partiții. Această idee poate ajuta ca algoritmul proiectat să fie mai eficient decât cei bazați pe căutarea în întreaga bază de date;
Algoritmul de partiționare poate fi adaptat mai bine la limitările memoriei principale. Fiecare partiție poate fi creată astfel ca ea să se încarce în memorie. În plus, se presupune că numărul de articolset-uri pe partiție să fie mai mic decât cele din întreaga bază de date;
Prin utilizarea partiționării pot fi ușor creați algoritmi paraleli și/sau distribuiți, iar fiecare partiție poate fi gestionată pe o mașină separată;
Generarea incrementală a regulilor de asociere poate fi ușor făcută prin tratarea stării curente a bazei de date ca și o partiție și tratând noua stare a bazei de date ca a doua partiție;
Algoritmul PARTITIONING reduce numărul de scanări a bazei de date la două și împarte baza de date în partiții astfel ca fiecare partiție să poată fi încărcată în memorie.
La scanarea bazei de date, algoritmul aduce acea partiție a bazei de date în memoria principală și numără numai articolele din acea partiție.
La prima scanare a bazei de date, algoritmul găsește toate articolele frecvente din fiecare partiție. Cu toate că, orice algoritm ar putea fi utilizat în acest scop, propunerea originală presupune că se adoptă o abordare pe nivele, asemănătoare algoritmului APRIORI. Aici Li reprezintă articolset-urile frecvente din partiția Di.
Pe parcursul celei de-a doua scanări, numai acele articolset-uri care sunt frecvente în cel puțin una din partiții sunt folosite ca și candidate și sunt numărate pentru a determina dacă ele sunt frecvente în întreaga bază de date.
Avantaje și dezavantaje ale algoritmului PARTITIONING
a) Avantaje:
– se adaptează memoriei principale disponibile;
– poate fi ușor paralelizat;
– numărul maxim de scanări a bazei de date este 2.
b) Dezavantaje:
– poate avea o mulțime de candidați pe parcursul celei de-a doua scanări.
CAPITOLUL V – Algoritmii folosiți pentru prelucrarea bazei de date
Pentru partea aplicativă am ales folosirea bazei de date de la Bacalaureat din anul 2006, pentru municipiul București acesta urmând să fie supusă unor tehnici de data mining precum clasificare, clustering și asociere.
Programul de data mining ales este TANAGRA, acesta fiind un produs software de data mining folosit în scopuri academice și de cercetare . Aceasta propune mai multe metode de data mining din analiza exploratorie a datelor , învățarea statistice , masina de învățare și o zonă de baze de date .
5.1 Obținerea bazei de date
5.2 Algoritmii folosiți pentru prelucrarea bazei de date
Pentru prelucrarea bazei de date s-au folosit o serie de algoritmi pentru clasificare, clustering și asociere după cum urmează:
Algoritmul k-means – este un algoritmul pentru clustering și este cel mai cunoscut și folosit algoritm pentru știință și industrie. În acest algoritm se reprezintă k clusteri Cj iar valoarea lor (mean) este cjce se calculează ca centrul de greutate al obiectelor din Cj. Valoarea lui k se stabilește la începutul algoritmului.
Au fost alese ca date de intrare disciplina opțională 1, disciplina opțională 2 și media finală de la matematică și un număr de trei clusteri astefel au fost obținute următoarele rezultate
5.2 Implementarea algoritmilor de data mining în baza de date
CAPITOLUL VI – Concluzii
Mi-am ales acesta lucrare deoarece mi-am propus să prezint un domeniu relativ nou, Data Mining reprezentând un domeniu forte larg în găsirea cunoștințelor noi din bazele de date.
Datorită faptului că bazele de date sunt din ce în ce mai mari, s-a ajuns la necesitatea de a se extrage diverse informații din acestea, informații ce nu se pot obține orin folosirea programelor clasice. Motiv pentru care utilizarea Data Mining este folositoare pentru extragerea diverselor statistici sau previziuni în foarte multe domenii precum învățământ, tehnologie, medicină etc.
KDD adică Knowledge Discovery in Databases reprezintă un proces important pentru extragerea informaților implicite și care sunt potențial folositoare.
Ce reprezintă defapt data mining? Un proces folosit pentru a prelucra un volum mare de date și a le converti în cunoștințe folositoare. Procesul de data mining face referire la metodele de selectare a unor relații necunoscute înaintea folosirii lui și având drept scop onținerea unui rezultat căutat / folositor de către utilizator.
Procesul de data mining are câteva nivele, nivele încep cu baza de date și se termină cu dobândirea informației căutate. Informația / rezultatele căutate sunt rezultatul proceselor de : selectare, preprocesare, transformare, data mining urmând ca rezultatul să fie evaluat și interpretat.
Se poate spune că data mining se trage din trei domenii ale învățării / cercetării și anume statistica , învățarea mașinilor și inteligența artificială. Statistica poate fi considerată baza metodelor de data mining deoarece majoritatea domenilor din statistică precum analiza regresiei, distribuții standard sau analiza grupului sunt folosite în metodele de data mining.
În ziua de azi există mai multe metode de data mining, acestea au fost prezentate în capitolul III și IV al lucrării. Alegerea unei metode care este potrivită unei anumite aplicații se face ținând cont de materia primă pe care o avem adică baza de date dar și de situație și obiectivele acesteia.
Regulile de asociere sunt folosite foarte des cu succes în analiza vânzărilor dar și în serviciile de marketing pentru a se determina interesele comune ale clienților. În afaceri data mining este utilizat de către analiști pentru a construi modele de risc privind dezvoltarea strategiilor de investiții. În domeniul financiar multe companii au folosit cu succes metode de data mining pentru analizarea conturilor clienților și pentru identificarea serviciilor financiare pe care aceștia le-ar putea solicita.
Data mining fiind un domeniu oarecum nou, iar metodele vechi de folosire a bazelor de date precum regresie sau clostering au fost înlocuite de către metode noi și mai performante precum arborele de decizie.
Însă algoritmi și arborele de decizie, ce sunt creați pot crea un rezultat complex, dar acesta poate fi prezentat într-un mod mai ușor de înteles. În data mining arborii de decizie sunt niște modele importante. Arborii de decizie pot fi utilizați pentru clasificare astfel se furnizează informații în diverse domenii precum store locațion, știință, target marketing etc.
Se poate spune, în concluzie că data miningul prin folosirea algoritmilor de clasificare, clustering sau asociere este și rămâne un domeniu de cercetare ce creează un mare interes pentru cercetătorii de azi, acest lucrur fiind datorat faptului că informația devine din ce în ce mai mare iar stocarea electronică a acesteia nu mai este o problemă, iar necesitatea de informație pentru suportul decizional de bună calitate crește, astfel că cercetările în data mining pot duce la îmbunătățirea semnificativă a explorării bazelor de date.
BIBLIOGRAFIE
Agrawal R. and Srikant R., „Fast Algorithms for Mining Association Rules”, Proc. of 20th International Conference on VLDB, 1994
Fayyad U.M., Piatetski-Shapiro G., Smyth P. and Uthurusamy R., “Advances in Knowledge Discovery and Data Mining”, AAAI/MIT Press, 1996
Agrawal R., Imielinski T. And Swami A.N., „Mining association rules between sets of items in large databases”, Proceeding of ACM International Conference on Management of Data, 1993
Dunham M.H., “Data Mining Introductory and Advanced Topics”, Prentice Hall, Pearson Education Inc. Upper Saddle River, New Jersey, 2003
Houtsma M. and Swami A., “Set-oriented mining for association rules in relational databases”, Proceedings of IEEE International Conference on Data Engineering, 1995
Savasere A., Omiencinski E., and Navathe S., “An Efficient Algorithm for Mining Association Rules in Large Databases”, Proceedings of the 21st International Conference on Very Large Databases, Zurich, Switzerland, September 1995
Agrawal, R.; Imielinski, T.; Swami, A., Database mining: a performance perspective in Knowledge and Data Engineering, IEEE Transactions Volume: 5 Issue:6, 1993
Abraham, A., Ramos, V., Web Usage Mining Using Artificial Ant Colony Clustering and Genetic Programming. Proc. of the Congress on Evolutionary Computation (CEC 2003), Canberra, pp. 1384-1391, IEEE Press. 2003
Crețulescu, R., Morariu, D, Vințan, L, Coman, I. – An Adaptive Metaclassifier for Text document, 16th International Conference on Information Systems Analysis, pp. 372-377, ISBN-13: 978-1-934272-86-2(Collection), ISBN-13: 9781-934272-88-6(Volume II) ,Florida, USA, 2010 indexată (ISI) Thomson Reuters
Hsu, C., Chang C., Lin, C., A Practical Guide to Support Vector Classification, Department of Computer Science and Information Engineering National Taiwan University, 2003)
Hotho, A., Staab, S. Stumme,G., Ontologies Improve Text Document Clustering, IEEE International Conference on, p. 541, Third IEEE International Conference on Data Mining (ICDM'03), 2003
Ilango M.,R., Mohan, V., A Survey of Grid Based Clustering Algorithms, International Journal of Engineering Science and Technology, Vol. 2(8), 2010
Manning, C., Raghavan, P., Schütze, H. Introduction to Information Retrieval, Cambridge University Press, ISBN 978-0-521-86571, 2008
Vințan N. L., Arhitecturi de procesoare cu paralelism la nivelul instructiunilor, Editura Academiei Române, București, ISBN 973-27-0734-8, 200
Zhao, Y. Karypis, G., Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, Vol. 55. No. 3, 2004
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
Metrics for Evaluating clustering algorithms http://www.scribd.com/Clustering/d/28924807
BIBLIOGRAFIE
Agrawal R. and Srikant R., „Fast Algorithms for Mining Association Rules”, Proc. of 20th International Conference on VLDB, 1994
Fayyad U.M., Piatetski-Shapiro G., Smyth P. and Uthurusamy R., “Advances in Knowledge Discovery and Data Mining”, AAAI/MIT Press, 1996
Agrawal R., Imielinski T. And Swami A.N., „Mining association rules between sets of items in large databases”, Proceeding of ACM International Conference on Management of Data, 1993
Dunham M.H., “Data Mining Introductory and Advanced Topics”, Prentice Hall, Pearson Education Inc. Upper Saddle River, New Jersey, 2003
Houtsma M. and Swami A., “Set-oriented mining for association rules in relational databases”, Proceedings of IEEE International Conference on Data Engineering, 1995
Savasere A., Omiencinski E., and Navathe S., “An Efficient Algorithm for Mining Association Rules in Large Databases”, Proceedings of the 21st International Conference on Very Large Databases, Zurich, Switzerland, September 1995
Agrawal, R.; Imielinski, T.; Swami, A., Database mining: a performance perspective in Knowledge and Data Engineering, IEEE Transactions Volume: 5 Issue:6, 1993
Abraham, A., Ramos, V., Web Usage Mining Using Artificial Ant Colony Clustering and Genetic Programming. Proc. of the Congress on Evolutionary Computation (CEC 2003), Canberra, pp. 1384-1391, IEEE Press. 2003
Crețulescu, R., Morariu, D, Vințan, L, Coman, I. – An Adaptive Metaclassifier for Text document, 16th International Conference on Information Systems Analysis, pp. 372-377, ISBN-13: 978-1-934272-86-2(Collection), ISBN-13: 9781-934272-88-6(Volume II) ,Florida, USA, 2010 indexată (ISI) Thomson Reuters
Hsu, C., Chang C., Lin, C., A Practical Guide to Support Vector Classification, Department of Computer Science and Information Engineering National Taiwan University, 2003)
Hotho, A., Staab, S. Stumme,G., Ontologies Improve Text Document Clustering, IEEE International Conference on, p. 541, Third IEEE International Conference on Data Mining (ICDM'03), 2003
Ilango M.,R., Mohan, V., A Survey of Grid Based Clustering Algorithms, International Journal of Engineering Science and Technology, Vol. 2(8), 2010
Manning, C., Raghavan, P., Schütze, H. Introduction to Information Retrieval, Cambridge University Press, ISBN 978-0-521-86571, 2008
Vințan N. L., Arhitecturi de procesoare cu paralelism la nivelul instructiunilor, Editura Academiei Române, București, ISBN 973-27-0734-8, 200
Zhao, Y. Karypis, G., Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, Vol. 55. No. 3, 2004
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
Metrics for Evaluating clustering algorithms http://www.scribd.com/Clustering/d/28924807
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Analiza Prin Tehnici Data Mining a Rezultatelor la Bacalaureat (ID: 136067)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.