Data Mining. Procesul de Text Mining

Data mining

Date, de la inanitie la suprasaturatie

În ultimii ani asistăm la o crestere explozivă a capacitătii de a genera si colecta date. Progresele realizate în colectarea datelor, computerizarea majoritătii tranzactiilor de afaceri si guvernamentale produc o avalansa de informatii . Se discută din ce în ce mai mult despre oceanul de date, care în literatura de specialitate se numeste „ubiquitous“ . Acest termen nu are o traducere exactă si nici o semnificatie foarte precisă. El se referă la datele care urmăresc în mod aproape invizibil viata de zi cu zi a omului modern. Originile acestor date sunt diferite, iar existenta lor, aproape insesizabilă cu ochiul liber. Ele provin din cele mai diverse surse, de la dispozitivele cele mai simple, cum ar fi telefoanele digitale, automatele de eliberat numerar, si până la baze de date complexe, legate de evidenta populatiei, sănătate, circulatie etc.

Astfel, afirmatii ca “ Se consumă cantităti din ce în ce mai mari,dar se digeră din ce în ce mai greu cele ingerate“ au intrat de mult în folclorul informaticii economice. Se impune stabilirea unei clare distinctii între date si informatii, deoarece abundenta de date nu presupune si informatii pe masura.

Aparitia Internetului a dus la o crestere exponentială a informatiilor. Practic, este foarte greu de imaginat cantitatea de informatii vehiculată între cele 13.000.000 4 de calculatoare, câte se apreciază a cuprinde în acest moment Internetul. Tinind seama că numărul calculatoarelor legate în Internet se dublează în fiecare an, se poate estima usor uriasul volum de date care se ascunde în spatele lui.

Excavarea cunostintelor

Pentru luarea unor decizii, sint necesare cunostinte. Drept urmare, o atentie deosebita va trebui acordata extragerii cunostintelor din date.

Dacă datele sunt relativ putine, analiza se poate realiza simplu, manual, de către specialisti din diferite domenii sau statisticieni, adesea numiti „mineri“ sau „excavatori manuali de date“. Adevaratele probleme dint ridicate insa de “muntii de date”.

Pentru astfel de volume de mari dimensiuni continind date amorfe, sunt necesare instrumente speciale pentru extragerea cunostintelor. Este si motivul aparitiei unei noi discipline denumita Data Mining (DM), Knowledge Discovery (KD), Knowledge Discovery in Databases (KDD), Information Discovery (ID), sau Information Archeology (IA) etc., fiecare dintre denumiri avind propria justificare.Se impune precezarea că unii autori fac deosebire între unele dintre acestea, de exemplu între DM si KDD sau KD.

Data mining -scurt istoric

Inca de la inceputurile prelucrarii electronice a datelor, fundamentare automata a deciziilor a reprezentat o adevarata provocare pentru cercetarori, matematicieni sau apartinind altor ramuri corelate intr-o oarecare masura cu lumea in continua expansiune a calculatorului.Rezultatul imediat al cercetarilor sustinute a fost o noua paradigma: “machine learning”. Conform notiunii tocmai nascute, un calculator, “alimentat” cu un numar de observatii despre cazuri cunoscute si rezolvate ar putea dezvolta un set de reguli care sa fie universal valabile.Transpunerea in termeni umani s-ar putea regasi in cazul unui observator care incearca sa stabileasca setul de reguli al unui joc doar asistind la derularea acestuia in conformitate cu regulile specifice.Foarte probabil ca, dupa asistarea unui numar suficient de mare de partide, sa fie capabil stabili setul de reguli.Putin probabil insa, ca aceasta idee sa fi animat mintea lui Frank Rosenblatt, cind, la inceputul anilor 60 a dezvoltat faimosul perceptron, unul dintre precursorii retelelor neuronale moderne.Desi o realizare pentru acel moment, perceptronul se dovedeste limitat de tipurile de probleme carora le poate oferi solutii .In 1969, dupa ce Minsky si Papert realizeaza o retea neuronala cu o arhitectura mult mai complexa si sint stabilite cu certitudine limitarile perceptronului cercetarile in domeniu vor fi dedicate cu precadere unei noi abordari.

Aceasta presupune renuntarea la idee fundamentala a paradigmei anterioare.Nu se va mai pretinde calculatorului descoperirea unui set de regului pe baza unor exemple, ci se va considera ca aceste reguli, existente prin influenta lor in setul de exemple, “hranesc” calculatorul.Aceasta presupune codificarea manualului de regului si realizarea unor programe care sa il consulte intr-un mod inteligent. In acest sens, la inceputul anilor 70 se realizeaza citeva sisteme expert, al caror potential s-a dovedit ulterior mult peste nivelul asteptat de cercetatori.Interesul pentru astfel de produse se mentine si in anii 80, insa criticii devin tot mai sceptici referindu-se la capacitatea acestora de a-si atinge adevaratul potential.Neincrederile erau alimentate in parte de investitia masiva necesara realizarii si mentinerii unei baze de cunostinte, in parte de limitarile existente in realizarea de sisteme expert, care nu au fost nicicind dezvoltate pina la un nivel care sa le permita “emularea” unui expert uman.

In aceste conditii, la mijlocul anilor 80, momentul se dovedea propice unei revitalizari a domeniului, iar noua generatie de cercetatori realizeaza retele neuronale tot mai complexe, crescind corespunzator complexitatea problemelor pentru care se puteau oferi solutii.Apareau ca elemente de noutate retelele cu doua straturi de neuroni si algoritmul backpropagation, ca avantaje solide fata de perceptron.Raspindirea noilor arhitecturi este rapida, aplicatiile se regesesc in variate domenii, astfel ca in 1987 lumea este martora primei Conferinte de Retele Neuronale ce se desfasoara la San Diego, California. Concomitent multe dintre companii isi realizeaza structurarea datelor in baze de date de mari dimensiuni,creind astfel volume impresionante de date, o resursa fundamentala in realizarea prelucrarilor.

Consecinta imediata este aparitia, la sfirsitul anilor 80, a unei noi notiuni -“regasirea cunostintelor in baze de date”- al carei obiectiv era inlocuirea tuturor termenilor vechi ce denumeau tehnicile de determinare a similaritatilor dintre date sau a pattern-urilor.Cercetatorii din domeniile inteligentei artificiale si machine learning adoptă rapid noua paradigma si modifica procesul extregerii cunostintelor din baze de date in sensul plasarii in centrul intregului proces analiza si interpretarea rezultatelor obtinute.In acest context, “data mining” referea acea faza a procesului in care erau aplicati algoritmi specifici de regasire a cunostintelor. Aceasta interpretare a fost formalizata la prima Conferinta Internationala asupra KDD, gazduita de Montreal in 1995. Recent, ca urmare a interesului suscitat de notiune in tot mai multe domenii, noi utilizatori ai termenului, apartinind presei de cele mai multe ori, au largit sfera acesteia. Astfel, data minig desemneaza in noua acceptiune procesul de extregere a cunostintelor din baze de date in ansamblu.

Definire

Domeniul fiind in plin proces de conturare, numărul definitiilor este mare, fie ele simpliste si intuitive- „ extragerea informatiilor predictive ascunse din bazele mari de date“ , „torturarea datelor până când acestea se confesează“ – sau complexe si elaborate.

Se impune necesitatea unui cadru in care să pozitionam componentele in vederea unei mai bune intelegeri.In figura … sint redate componentele unui mediu orientat pe data mining si interactiunea dintre ele.

Utilizator

Baza de date Instrumente Instrumente de

data mining vizualizare

Fig1.1 Compomentele unui mediu orientat Data Mining

Urmatoarea definitie poate fi considerată suficient de cuprinzatoare pentru a fi acceptată:

“Data mining reprezintă procesul de extragere a informatiilor anterior necunoscute, valide si operationale din baze de date de mari dimensiuni in scopul utilizarii informatiilor astfel obtinute in fundamentarea deciziilor .”

Cuvintele evidentiate reprezinta esenta procesului de data mining si ajută la explicarea diferentelor fundamentale dintre acesta si metodele traditionale de analiza a datelor, cum ar fi cererile de regasire, realizarea rapoartelor, metodele din statistica sau OLAP.

Particularitatea esentiala a procesului de mining este data de obiectivul acestuia: descoperirea unor cunostinte fara formularea prealabila a unor ipoteze.

Informatiile descoperite trebuie sa fie necunoscute anterior.Desi aparent conditia pare satisfacuta, adevaratul sens se refera la posibilitatea existentei unor ipoteze anterioare referitoare la date. O astfel de situatie dispare din sfera mining-ului, incompatibil cu verificarea ipotezelor anterior formulate.

Intr-un proces de mining nu sint cautate informatii intuitive, ci poate tocmai acele cunostinte care contravin intuitiei.Potentialul cunostintelor achizitionate este cu atit mai mare cu cit ele sint mai departate de calea fireasca, asteptata, pe care intuitia o putea creiona usor.Se realizeaza astfel impingerea limitelor imaginatiei umane.

Informatiile obtinute trebuie sa fie valide . Acest element al definitiei realizeaza corelatia cu notiunea de “supraoptimism” in data mining:dupa o cautare asidua in colectii de date de mari dimensiuni, informatii de interes vor iesi la iveala mai devreme sau mai tirziu.In aceeasi masura, insa, se pot obtine informatii viciate, continind corelatii inselatoare, a caror utilizare poate induce grave prejudicii. Este si motivul pentru care merita subliniata importanta validarii datelor obtinute prin procesul de mining.

Ultimul atribut al informatiilor obtinute printr-un proces de mining este si cel mai important: vor trebui sa fie operationale.Satisfacerea acestei cerinte asigura “transpunerea” datelor in avantaje.In multe dintre cazuri, insa, obtinerea unor date ce pot fundamenta deciziile nu este deloc simpla.De exemplu, aplicarea unui proces de mining asupra unor colectii de date din trecut poate deduce existenta unor oportunitati pe care utilizatorul le-a sesizat la timpul potrivit, fructificindu-le corespunzator. Este un exemplu care ilustreza un rezultat neasteptat si inutil al procesului, si anume, redundanta.In aceeasi masura, exploatarea unei aparente oportunitati poate necesita utilizarea unor date dificil de achizitionat sau inaccesibile din ratiuni legale.

Succesul implementarii procesului de data mining depinde, in ultima instanta, de abilitatea utilizatorului de a utiliza cunostintele obtinute in fundamentarea deciziilor sale.

Managementul cunostintelor

Dezvoltarea rapida a noilor tenhologii si patrunderea lor in tot mai multe dintre sferele actititatii umane genereaza modificari in modul de generare si utilizare a informatiilor. Atributele esentiale ale informatiilor au capatat noi valente, fie ca este vorba de volumul informatiei, disponibilitatea sau importanta acesteia.” A naviga” printre aceste cunostinte, a desprinde un sens al lor a devenit deja o arta. O solutie pentru utilizarea eficienta a volumului mare de informatii eterogene cu care fiecare organizatie se confrunt isi propune sa ofere Managementul Cunostintelor,( KM) definit ca procesul de “capturare” a intregii experiente acumulate intr-o organizatie si directionarea acesteia catre punctele in care beneficiile aduse pot fi maxime.

Componentele KM

Bazele de cunostinte se refera la cunostintele asimilate de organizatie. Ele pot fi continute de documente, rapoarte de cercetare sause regsesc stocate in baze de date, datawarehouse-uri sau data mart-uri.

Distributia cunostintelor presupune cunoasterea deficientelor informationale ale unui anumit departament si realizeaza orientarea fluxurilor informationale catre aceste puncte.

Descoperirea cunostintelor realizeaza identificarea unor informatii necunoscute si care se pot dovedi folositoare in activitatea organizatiei.

Cunoscut Necunoscut Fig 1.2 Coe cercetare sause regsesc stocate in baze de date, datawarehouse-uri sau data mart-uri.

Distributia cunostintelor presupune cunoasterea deficientelor informationale ale unui anumit departament si realizeaza orientarea fluxurilor informationale catre aceste puncte.

Descoperirea cunostintelor realizeaza identificarea unor informatii necunoscute si care se pot dovedi folositoare in activitatea organizatiei.

Cunoscut Necunoscut Fig 1.2 Componetele KM

In contextul mai larg, al managementului cunostintelor, data mining se regaseste in cadrul ultimei componente , realizind descoperirea unor informatii noi.

Componentele data mining

In general, procesului de data mining sint supuse date structurate, adica date numerice organizate intr-o anumita structura, in baze de date, warehouse-uri sau data mart-uri. Una dintre directiile de evolutie a tehnologiei o reprezinta extinderea acesteia catre tipurile de date nestructurate. Astfel, text mining reprezinta o parte importanta a mining-ului aplicat datelor nestructurate, alaturi de mining aplicat imaginilor sau altor tipuri de date multimedia.

Pentru reprezentarea informatiilor sint utilizate o multitudine de formate diferite de formatul alfanumeric folosit pentru a stoca datele in baze de date. Documente, imagini, sunete, date spatiale si temporale sau texte reprezinta numai citeva exemple de date nestructurate. Un caz aparte il reprezinta documentele on line, continind date cu un inalt potential informational,al caror numar tinde sa devina tot mai mare. Printre ele se pot include e-mail-uri continind reactii ale cumparatorilor fata de un anumit produs sau serviciu, prezentari continind concluzii ale expertizelor, rapoarte tehnice ce descriu noi tehnologii,sau documente ce cuprind informatii despre piata si concurenta.

Corelatii intre DM si alte domenii ale informaticii

Data mining se utilizeaza intotdeauna in strinsa corelatie cu metodele clasice de analiza a datelor, inclusiv cele oferite de statistica. Astfel, data mining este adesea perceput ca una sau o imbinare a mai multora dintre urmatoarele modalitati clasice de regasire a informatiilor:

Metodele clasice de regasire a informatiilor sint redate in figura 1.3.

Interogari SQL orientate ale depozitelor de date de mari dimensiuni;

Interogari SQL orientate sles unor baze sau depozite de date distibuite;

Interogari SQL intr-un mediu ce permite procesare paralela;

Regsiri de date, cu ajutorul unor instrumente avansate precum agenii inteligeni;

Analize in sisteme de baze de date multidimensionale;

Analize in sisteme OLAP;

Vizualizri grafice avansate ale datelor;

Prelucrari statistice tradiionale ale datelor din cadrul bazelor sau depozitelor de date.

Interogari

Fig. 1.3. Analiza traditionala a datelor

Nici una dintre metodele prezentate nu reprezinta data mining, nefiind satisfacuta conditia esentiala: descoperirea unor informatii in lipsa unor ipoteze formulate anterior.

Data fiind natura exploratorie a procesului de data mining, o regula de aur ar putea fi formulata astfel: de fiecare data cind sint cunoscute forma si continutul probabil al informatiilor cautate este putin probabil sa se realizeze un proces de de data mining.

Data mining perminte obtinerea unor informatii la care nu pot conduce metodele clasice.Intrebarile ale caror raspunsuri sint oferite prin acest proces se deferentiaza net de intrebarile care orienteaza metodele traditionale, printr-un grad sporit de generalitate si un potential informational ridicat.

Conexiunea data mining –statistica

Dintre variatele metode clasice de analiza a datelor, modelele oferite de statistica sint cele mai apropiate de data mining. Intelegerea legaturii dintre cele doua domenii ar permite o mai buna delimitare a celui mai nou dintre ele. In acest sens se impune precizarea ca metode clasice apartinind statisticii au fost folosite pentru realizarea multora dintre analizele care acum se realizeaza prin data mining.Printre ele se regasesc construirea modelelor predictive sau descoperirea asocierilor in baze de date. Fiecarei componente de baza a tehnicilor de mining ii corespunde o metoda echivalenta din statistica si este foarte adevarat ca, daca nu toate, atunci o mare parte din prelucrarile realizate prin mining pot fi obtinute si prin metode pe care le regasim in statistica.Ceea ce atrage insa multi analisti catre domeniul nou format este relativa usurinta cu care pot fi descoperite noi informatii, spre deosebire de metodele statistice, care permit numai regasirea si verificarea unor template-uri.Accesibilitatea noului domeniu este evidentita in multe moduri.De exemplu, data mining este intotdeauna un proces in care nu se vor regasi ipoteze care sa fie verificate, in timp ce majoritatea metodelor statistice presupun elaborarea prealabila a unor ipoteze, statisticienii fiind nevoiti sa elaboreze ecuatiile care descriu ipotezele.Spre deosebire, intr-un proces de data mining aceste ecuatii sint elaborate automat.De exemplu, modelarea comportamentului consumatorului este realizata printr-un set de astfel de ecuatii.Datorita efortului necesar obtinerii solutiilor, multi statisticieni se limiteaza la folosirea unor tehnici avansate din domeniul statisticii, cum ar fi regresia neliniara.

Cercetari recente in machine learning au permis dezvoltarea unor algoritmi dedicati regasirii informatiei in volume mari de date, iar extinderea aplicarii acestor algoritmi dincolo de granitele laboratoarelor a oferit atractivitate comerciala data mining-ului.

In sfirsit, tipul datelor care pot fi supuse prelucrarii prin mining reprezinta o alta componenta a atractivitatii acestuia. In timp ce majoritatea metodelor din statistica utilizeaza date de intrare numerice in scopul realizarii unei analize laborioase a distributiei , algoritmii de mining pot prelucra un set mult mai larg de tipuri de date, realizind o analiza sumara asupra distributiei acestora sau chiar lipsind o astfel de analiza.

In concluzie, ascendentul data mining-ului asupra statisticii nu este determinat de un singur factor.In multe medii orientate pe un astfel de proces, statistica pastreaza inca un rol bine definit. Desi elementele evidentiate pledeaza in favoarea data mining-ului mai degraba decit pentru modelele statisticii, o strategie optimala presupune imbinarea celor doua tehnici complementare.

Elemente comune data mining –statistica

Data mining se dovedeste a fi ultima dintr-un lung sir de tehnici ce permit rezolvarea unor probleme concrete utilizind analiza datelor. Mijloacele specifice pe care le pune la dispozitia utilizatorilor determina o crestere a vitezei procesului de elaborare a deciziilor si o fundamentare temeinica a acestora. Ca toate tehnologiile conduse prin date, data mining prezinta o sensibilitate critica fata de acuratetea datelor supuse prelucrarii.Acestea vor trebui sa nu contina erori sa sa fie permanent supuse unou procese de verificare a validitatii si integritatii.De aici si importanta cruciala a interpretarii corespunzatoare a rezultatelor: la limita, vor trebui recunoscute si eventualele erori care denatureaza fenomenele.

Legatura data mining -data warehouse

Data warehouse

Elementul fundamental in definirea unui warehouse este dat de diferenta dintre datele operationale si cele strategice. Datele operationale asigura buna functionare a unei organizatii( agent economic,organizatie politica sau de alta natura) in timp ce datele strategice fundamenteaza deciziile luate pentru conducerea acesteia. Datele operationale mentin organizatia in viata in timp ce datele strategice o conduc. Un depozit de date este destinat stocarii informatiilor strategice, si este de dorit sa fie singura sursa care ofera date pentru fundamentarea deciziilor de conducere ale organizatiei. Unicitatea sursei reprezinta o prima diferentiere fata de datele operationale, stocate intr-o multitudine de modalitati si colectii.

Un datawarehouse reprezinta o colectie de date dedicate unui anume subiect,integrate, constante in timp si persistente”.

Datele sint dedicate unui anume subiect:intr-un warehouse datele sint definite si organizate corespunzator activitatii organizatiei respective. Se vor evidentia datele referitoare la clienti, produse, rapoarte si analize. Aceasta orientare a datelor dupa tipul de activitate este determinata de modelarea lor.

Integrate: datele continute intr-un warehouse trebuie sa fie valide atit la nivelul organizatiei, cit si la nivelul surselor de date operationale si al celor externe.

Variabilitate in timp: toate datele continute intr-un warehouse sint stocate la valoarea avuta in momentul inregistrarii. Este realizata astfel o evidenta cronologica a datelor care permite realizarea unor analize care sa determine tendintele manifestate in timp. Pe baza lor se pot realiza extrapolari obtinindu-se informatii despre momentul actual. Totodata aceasta modalitate de stocare reprezinta o alta diferentiere fata de datele operationale, de obicei suprascrise cind valorile actuale nu mai prezinta interes.

Presintente:odata stocate intr-un warehouse, datele nu vor mai fi modificate. Se pot realiza astfel rapoarte bine fundamentate si analize comparate.

Data mart

Realizarea unui depozit de date se dovedeste o activitate nu tocmai simpla, mai ales daca scopul acestuia este de a oferi informatii intregii organizatii. Este si motivul pentru care multe dintre acestea s-au orientat catre data mart-uri: o colectie mai restrinsa de date referitoare la un domeniu mai restrins, cu un grad mai mare de specializare, mai accesibila si de dimensiuni mai mici decit un datawarehouse. Pentru organizatiile care deja au implementat un depozit de date, un data mart poate fi destinat numai unui anumit departament .

Data warehousing, desi un domeniu strict delimitat teoretic si practic, de afla cu siguranta in strinsa corelatia cu data mining. Prezentarea principiilor fundamentale ale datawarehous-ului permite evidentierea asemanarilor si deosebirilor dintre cele doua domenii. Se impune insa precizarea ca un depozit de date( datawarehouse) nu reprezinta o componenta esentiala pentru derularea procesului de mining. In ciuda interesului sporit manifestat de catre utilizatorii data mining-ului fata de aceasta forma de organizare a datelor, multe prelucrarii se realizeaza asupra unor date provenind din cele mai variate surse.

De la datawarehouse la data mining

Tranzitia se dovedeste a fi una naturala, deoarece organizatiile care au realizat investitiile necesare implementarii unui depozit de date constientizeaza valoarea strategica a informatiilor si sint dispuse sa accepte fara rezerve conceptele data mining-ului.

Multe dintre operatiile de structurare, validare si stocare a datelor au fost deja efectuate, astfel ca data mining apare ca o posibilitate de amortizare a investitiei efectuate pentru realizarea depozitului de date.

De la data mining la datawarehouse

Succesul unui proiect orientat pe data mining va demonstra valoarea strategica a seturilor de date si validitatea solutiilor oferite de metodele orientate pe date.

Un depozit de date va reprezenta o excelenta modalitate de a integra solutiile unui proces de mining in structura informationala a organizatiei

Data mining OLAP, DSS

DM si KDD sunt foarte legate de o serie de domenii noi ale informaticii.Cele mai apropiate domenii de DM si KDD sunt OLAP (On Line Analitic Processing) si DSS (Decision Support Systems).

OLAP este un mod de utilizare a depozitelor de date, utilizare care presupune pe de o parte un acces în timp real (OLTP – On Line Transactional Processing), iar pe de altă parte, o analiză multidimensională (vectorială) a bazelor de date mari. DSS este un ansamblu format din baze si depozite de date, precum si alte ansambluri de informatii utile, împreună cu produse soft adecvate întocmirii rapoartelor, analizei datelor, precum si implementării unor algoritmi de optimizare în vederea sprijinirii actului decizional al oamenilor de afaceri. Aceste două domenii fiind foarte apropiate de DM, determină o serie de furnizori de OLAP sau DSS să sustină că livrează DM.Dând o interpretare slabă notiunii de Data Mining, vânzătorii OLAP pot spune că se ocupă de DM.Una dintre liniile de demarcare clară dintre cele două domenii este gradul de automatizare. A doua este gradul de utilizare a mijloacelor statistice de determinare a ceea ce este interesant si a ceea ce este irele vant. Acestea sunt clar în favoarea DSS. OLAP si DSS utilizează mai putini algoritmi si depind de cererile si ipotezele livrate de utilizator. În ceea ce priveste răspunsurile, diferenta dintre OLAP si DSS, pe de o parte, si DM si KDD, pe de altă par te, se poate asemăna cu cea dintre răspunsurile date de o bază de date si una de cunostinte.

Există si diferente, dintre care cea mai importantă este modul de rationare. Astfel, rationarea în sistemele OLAP si DSS este deductivă, în timp ce în DM si KDD este inductivă.

Pe de altă parte, trebuie subliniat că diferentele dintre DM, OLAP si DSS au tendinta să dispară,algoritmii si facilitătile DM incepind să fie incluse în produsele DSS si OLAP

Scurta trecere in revista a corelatiilor dintre DM si alte domenii ale informaticii demonstreaza ca data mining este intr-o mult mai mare masura rezultatul unei evolutii decit al unei revolutii.

Domenii de aplicabilitate a tehnologiei data mining

Tehnologia data mining isi gaseste aplicabilitate in special in domeniile care dispun de un volum considerabil de date. Astfel, se contureaza la principale directii de aplicabilitate a noii tehnilogii

Mediul inteligent al afacerilor

Termenul de mediu inteligent al afacerilor se refera la totalitatea proceselor, tehnicilor si instrumentelor care permit asistarea elaborarii deciziilor facind apel la tehnologia informatiei. Data mining se dovedeste a fi o componenta importanta a acestui mediu.

Creste potentialul informational al datelor

Decizii

Prezentari

Data mining

Explorari ale datelor

Data warehouse / data mart

Surse de date

Fig . 1.4 Data mining si mediul inteligent de afaceri

Sursele de date pot fi :fisiere, documente stocate pe diverse suporturi, baze de date.

Explorarile datelor cuprind: on line analitycal processing , MDA.

Prezentarile datelor se pot realiza utilizind metode de vizualizare.

Diferitele nivele ale piramidei sint destinete unor clase diferite dfe utilizatori.

Astfel ,primele doua nivele vor fi subordonate administratorului bazei de date;

Urmatoarele doua nivele sint destinate analistului de date.

Analistul de sistem este va stabili tehnicile de vizualizare a cunostintelor obtinute in timp ce utilizarea scestora in fundmentarea deciziilor ii revine utilizatorului final.

O ierarhizare a acestor elemente in functie de potentialul lor de a sta la baza deciziilor tactice si strategice este redata in figura 1.4.

In general, acest potential creste de la baza piramidei catre virful acesteia. O decizie bazata pe datele nivelelor inferioare, unde de obicei sint milioane de inregistrari, poate afecta numai o singura tranzactie . O decizie avind la baza prelucrari ale datelor de pe nivelele superioare se poate referi la initiative ale unui intreg compartiment, ale intregii organizatii sau pot fundamenta politicile de reorientare ale acesteia. De asemenea, diferitelor nivele ale piramidei li se asociaza diferite tipuri de utilizatori.Administratorul bazei de date manipuleaza datele nivelelor “Surse de date” si “Depozite de date”, in timp ce analistii opereaza cu datele nivelelor superioare ale piramidei.

De remarcat ca figura ilustreaza dependentele logice dintre tehnoligiile respective, si nu pe cele fizice. De exemplu, un proces de date mining se poate baza pe datawarehouse, iar tehnicile de vizualizare pot fi si utilizate in afara unui astfel de proces.

Realizarea studiilor de piata

Analiza grupurilor tinta

gestionarea relatiilor cu clientii;

analiza cosului zilnic

segmentari ale pietei;

Managementul riscului

realizarea previziunilor

realizarea estimarilor;

anticiparea comportamentului consumatorilor;

controlul calitatii;

Managementul fraudelor

detectarea fraudelor

` Stadiul actual al DM

Majoritatea autorilor sunt de părere că stadiul actual al DM este cel de „artă“.

Aceasta situatie a DM si KDD se datorează si faptului că, spre deosebire de alte dezvoltări ale informaticii, cum au fost Internetul, programarea orientata obiect, retelele neuronale, algoritmii genetici, etc., care au pornit de la lumea academică, fiind ulterior preluată de cea a afacerilor, în cazul DM s-a întâmplat invers, a pornit de la firmele puternice, cum sunt IBM, Microsoft, GTE, etc., lumea academică sesizând ulterior problema.

Tendinte de evolutie

Data fiind noutatea domeniului, orice incercare de a creiona evolutia ar putea fi hazardata, insa anumite tendinte devin tot mai clare . Un numar tot mai mare de realizatori de produse soft tind sa sa implementeze in acestea paradigmele data minig. Consecinta directa va fi o impulsionare puternica a tehnologiei . Se vor dezvolta noi algoritmi de mining, dar in timp tehnologia va fi asimilata de contexte mai largi, cum ar fi analiza datelor si tehnologia bazelor de date. Deja se realizeaza extinderea facilitatilor OLAP si MDA catre implementarea functiilor de mining direct din bazele de date relationale. Noile extensii ale SQL urmaresc acelasi scop.

Cazuri concrete de succese repurtate utilizind noua tehnologie vor consolida credibilitatea procesului de data mining. Astfel de cazuri si-au facut deja paritia. In timp, tehnoligia data mining se va translata in domeniul public, similar tehnologiei datawarehouse.

Faza finala a evolutiei va fi reprezentata de integrarea noii tehnologii in cadrul cuprinzator al mediului inteligent de afaceri, in timp ce procesul de data mining va putea fi tot mai dificil identificat ca o entitate distincta. La capatul unei lungi evolutii, ca orice tehnologie avansata, data mining va sfirsi prin a deveni transparenta!

Text mining

Analiza textelor in limbaj natural- Scurt istoric

Inca din anii 50, s-a realizat un lung sir de incercari ale cercetatorilor din domeniul Inteligentei Artificiale sau al Retelelor Neuronale Artificiale de a intelege si modela capacitatea umana de procesare a informatiilor. Drept urmare, au fost obtinute citeva solutii partial de succes in procesarea textelor exprimate in limbaj natural.

Sistemele astfel dezvoltate realizau analize ale textului la nivel de propozitie, in scopul obtinerii unei reprezentari semantice a propozitiei sub forma unei relatii intre cele mai importante cuvinte continute de propozitie. Propozitia era analizata in corelatie cu anumite sabloane lingvistice predefinite . In cazul unei compatibilitati ridicate intre sablon si propozitie, acesteia i se asociaza o anumita constructie semantica. Se realiza astfel o prima modalitate de a distinge semantica unui anumit text. Principalul inconvenient al metodei il reprezenta numarul mare de sabloane necesare a fi predefinite pentru a analiza diferite tipuri de propozitii. Constructiile exceptionale, mai rar intilnite , sporeau numarul sabloanelor , a caror lista devenea extrem de mare, diminuind eficacitatea metodei. In concluzie, metoda oferea solutii acceptabile numai pentru o categorie restrinsa de texte, in care se regaseau un numar redus de sabloane. O alta limitare era data de numarul de limbaje in care era redactat textul,pentru limbaje diferite fiind necesare sabloane diferite .

Ramura inteligentei artificiale cunoscuta drept prelucrarea limbajului natural are ca obiectiv major al activitatii procesarea textelor exprimate in limbaj natural. Se urmareste regasirea informatiei utilizind criterii semantice, realizarea de sisteme expert. Pentru analiza semantica a textului sint utilizate metode pur lingvistice. Rezultatele analizei sint reprezentate sub forma unei retele semantice, continind cei mai importanti termeni ai textului si relatiile dintre acestia.

O retea semantica este o forma conventionala de reprezentare a textului, utilizata intens in stiintele cognitive.

Se impune precizarea ca aaseturile de reguli sint orientate pe un anumit subiect. Este motivul pentru care un set de reguli va genera rezultate corespunzatoare numai pentru acele documente care abordeaza un subiect pentru care a fost elaborat un set de reguli. Ij acest fel, analiza textului dovedeste o puternica dependenta fata de domeniul abordat in textele procesate. De asemenea, in faza de dezvoltare a regulilor lingvistice este esentiala participarea unui expert uman. Astfel de aplicatii isi dovedesc utilitatea in realizarea de sisteme expert destinate unui anumit domeniu. Totusi, in cazul analizei unor colectii eterogene, continind texte din mai multe domenii, raminea inca necesitatea dezvoltarii unor algoritmi capabili sa realizeze analize mai generale.

Un alt domeniu ale carui aplicatii s-au regasit in analiza textelor exprimate in limbaj natural este reprezentat de retelele neuronale(NN).. In acest caz, principiul de baza era ca, o procesare omogena realizata cu ajutorul unor elemente interconectate asemanator neuronilor va decurge de maniera realizarii acestui proces de catre creierul uman. Si in acest caz au fost obtinute rezultate partial satisfacatoare, cum ar fi realizarea unor analize simpliste, insa in general, procesarea omogena a datelor structurate conform regulilor lingvistice s-a dovedit ineficienta.

In concluzie, IA si NN au adus contributii in evolutia metidelor de analiza a textelor exprimate in limbaj natural, insa aplicarea in practica a solutiilor indicate de aceste doua domeniii a dovedit un succes limitat. O solutie imbunatatita in acest sens ar putea fi obtinuta utilizind o combinare a metodelor celor doua domenii. O astfel de solutie presupunea realizarea unor analize ale textelor cu ajutorul unor elemente de procesare (unitati de procesare) intre care sa existe interconectari conforme modelelor cognitive.

Se obtinea astfel o structura mai complexa, capabila sa realizeze un set mai amplu de analize asupra textelor. Informatia era procesata automat in utinatile de prelucrare, ca in cazul solutiei oferite de NN, construindu-se in acelasi timp structurile semantice specifice solutiei AI.

Analiza unui text se realiza astfel in mai multe subtaskuri, interconectate prin fluxuri de informatii.

Noi orientari in analiza textelor exprimate in limbaj natural

Data fiind eficienta scazuta dovedita de metodele anterioare, noi metode hibrid au fost dezvoltate.

O prima solutie de acest fel considera textul ca o succesiune de simboluri , organizate in cuvinte si propozitii. Textul astfel reprezentat este analizat cu ajutorul unui cadru de lungime variind intre 2 si 20 de simboluri, in care simbolurile sint introduse unul cite unul. Continutul cadrului la un anumit moment dat este retinut in neuroni alocati in mod dinamic. Reteaua neuronala astfel construita contine mai multe nivele. Fragmente de text care se regasesc de mai multe ori in cuprinsul acestuia vor fi stocate de neuronii de pe nivelele mai inalte ale retelei.

In ansamblu, reteaua se constituie intr-un dictionar multinivel continind diferite tipuri de elemente ele textului: litere, silabe, cuvinte, propozitii. La realizarea analizei, elementele de baza vor fi cuvintele, in timp ce celelalte elemente vor reprezenta surse auxiliare de informatii.

Text mining

Definire

Text mining reprezinta un ansamblu de metode avind drept scop regasirea informatiilor in datele de tip text exprimat in limbaj natural.

Nu pot fi incluse in sfera noii tehnologii prelucrarile efectuate asupra datelor de tip sir de caractere care se pot regasi cu usurinta stocate in bazele sau depozitele de date. Insasi definitia notiunii conduce insa si la prima limitare a acesteia.

Text mining este restrictionat in primul rind de incapacitatea tehnologiei actuale de a prelucra limbajul natural. Dintre multiplele informatii continute de un text exprimat in limbaj natural, asupra caruia nu au fost aplicate restrictiile unei forme de structurare, numai o mica parte vor putea fi regasite. Informatiile regasite cu usurinta pot fi autorul, data si titlul unui anumit document, insa analizarea acestuia in afara oricarui context nu poate oferi informatii despre continutul sau semantic. Procesul de text mining se dovedeste de multe ori iterativ si reclama obtinerea unor rezultate care sa poate fi exprimate cantitativ si sa permita comparatii intre diferitele metode de regasire a informatiilor utilizate.

Data fiind forma de stocare a informatiilor, si anume textul, aplicarea analizei numerice se dovedeste necorespunzatoare. Regasirea are la baza o analiza lexicografica, urmata de determinarea anumitor indicatori statistici, cum ar fi frecventa de aparitie in document a structurilor lexicale, aceste putind fi cuvinte sau grupuri de cuvinte. Pe baza similaritatii dintre date se pot determina clusterizari ale setului de documente. Rezultatele obtinute pot fi vizualizate evidentiind relatiile descoperite intre sursele de date.

Regasirea clasica a informatiilor in date de tip text

Metodele clasice de regaisire a informatiilor in text, implementate cu precadere in instrumentele de regasire a informatiilor in internet, au ca element central o cerere formulata de utilizator. Cererea trebuie sa cuprinda cuvintele cheie ale domeniului din care se vor regasi informatiile. Anumiti algoritmi stabilesc similaritatea dintre documente si cererea formulata de utilizator. Un numar mai mare de astfel de elemente pot asigura rezolvarea cererii intr-un mod satisfacator. In mod normal, unul sau mai multe documente care contin termenii din cerere vor fi indicate drept corespunzatoare. Astfel de sisteme de regasire, orientate pe cereri specifice dovedesc performante reduse in regasirea eficienta a informatiei, indicind ca relevante documente care nu au tangenta cu subiectul solocitat si nerecunoscind documente cu care acesta este corelat. Cauza principala a unui astfel de comportament o reprezinta subtilitatile semantice, in virtutea carora o idee poate fi exprimata in mai multe moduri, generindu-se astfel constructii lexicale echivalente semantic, sau, reciproc, un cuvint poate avea mai multe sensuri, constructii identice lexical avind semantica diferita.

O alta limitare a acestor sisteme deriva din subordonarea lor fata de utilizator.Intregul proces de regasire este subordonat acestuia, care cunoaste elementele cheie ale informatiilor si este in masura sa formuleze o cerere specifica. Ce se intimpla insa cind utilizatorul nu este in masura sa formuleze o astfel de cerere, ci poate adresa numai intrebari formulate generic? Text mining este tehnologia care-si propune sa ofere solutii unor cerere abstracte de forma “ce s-a mai intimplat?”, “ce este nou?”, “care domenii dovedesc cea mai tumultoasa evolutie?”.

Existenta unor instrumente noi, capabile sa prelucreze documente exprimate in limbaj natural este imperioasa, data fiind tendinta acestor tipuri de date de a deveni forma predominanta de stocare a informatiilor. Consecinta directa a utilizarii unui astfel de instrument este cresterea eficacitatii utilizarii depozitelor de date nestructurate, folosind analize relizate automat. Principalul impediment este ca textele exprimate in limbaj natural nu sint destinate prelucrarii cu ajutorul calculatorului, pretindu-se intr-o mica masura unor astfel de analize. Spre deosebire de datele structurate, pastrate in bazele de date, documentele in limbaj natural dovedesc, in cel mai bun caz, un grad redus de structurate. Mai mult decit atit, informatia pe care o contin nu este explicita, ci implicita, ingropata in text. De aici si metafora termenului “mining” -explorare, forare: calculatorul trebuie sa descopere informatiile ascunse in text de autorul acestuia. Realizarea analizelor asupra documentelor exprimate in limbaj natural conduce la imbogatirea acestora cu informatii despre continutul lor, metadatele astfel obtinute putind fi apoi stocate in baze de date.

La baza domeniului numit text mining se afla presupunerea ca modul de asociere a termenilor cu obiectele se face conform unui anumit model, care devine insa transparent datorita modalitatilor multiple de alegere a cuvintelor. Descoperirea acestei structuri latente se realizeaza folosind metode statistice, pe baza carora se poate stabili ulterior gradul de similaritate intre documente.

Obiectivele text mining

Stabilirea subiectului abordat de un text exprimat in limbaj natural

Clasificarea documentelor dupa un anumit subiect;

Identificarea prinicipalelor subiecte abordate in colectii mari de documente;

Determinarea celor mai relevante documente, utilizind cereri de regasire performate si flexibile;

Navigarea in colectii mari de texte

Componente text mining

Desi tehnologia text mining cuprinde un amsamblu complex de elemente, acestea pot fi grupate in doua componente functionale principale:

Regasirea informatiilor

Clasificarea informatiilor

Regasirea informatiilor

Regasirea informatiilor presupune identificarea si apoi extragerea acestora. Primul pas in identificarea informatiior il reprezinta determinarea gruparilor semantice, de cele mai multe ori elementul semantic fiind cuvintul, insa nu este exclusa realizarea unor analize asupra unor nuclee semantice continind mai multe cuvinte. Acest pas este urmat de clasificarea documentelor in functie de elementele semantice identificate, dupa o anumita schema si indexarea acestora, in scopul unei regasiri mai bune.

Analiza lexicografica aplicata textelor poate avea ca rezultate urmatoarele module functionale:

Identificarea limbajului in care este redactat textul

Presupune determinarea numarului de limbaje in care a fost redactat textul si raportul dintre partile apartinind diferitelor limbaje. Determinarea se realizeaza utilizind elemente specifice identificate in text si un set de antrenare continind documente redactate in mai multe limbaje.

Printre aplicatiile acestui modul functional se pot enumera: automatizarea procesului de indexare a colectiilor de date dupa limbaj; restrictionarea rezultatelor cererilor de regasire in functie de limbaj; directionarea documentelor catre translatoarele automate.

Identificarea elementelor semantice specifice

Termenii identificati se refera la denumiri de persoane, locuri sau organizatii, abrevieri, identificatori formati din mai multe cuvinte, numerale, date scrise in formate specifice sau simboluri monetare.

Prelucrarea unui document in scopul identificarii nucleelor semantice se poate realiza in doua moduri:

1. Se analizeaza documentul in afara oricarui context, identificindu-se termenii specifici pe care ii contine;

2. In documentul analizat se urmareste localizarea unor termeni continuti intr-un dictionar construit anterior pe baza precedentelor documente analizate. Utilizarea unui set de documente permite crearea automata a acestui dictionar cuprinzind termenii cei mai reprezentativi pe care ii contin. Pentru fiecare termen se determina prin metode statistice un anumit grad al semnificatiei acestuia. Un numar atasat fiecarui termen din setul de date, numit “coeficient al informatiei” stabileste aceasta masura a semnificatiei. Determinarea acestui coeficient presupune utilizarea mai multor metode statistice, care conduc la stabilirea gradului de semnificatie al unui cuvint sau grup de cuvinte apartinind setului de documente. Elementele lexicale avind un coeficient al informatiei ridicat indica cel mai adesea denumiri sau identificatori formati din mai multe cuvinte, dat fiind ca acestea au un continut semantic sporit.

Identificarea denumirilor . Forme canonice

Denumirile pot constitui o adevarata cheie in stabilirea subiectului abordat de un text. Utilizarea unor algoritmi euristici rapizi si robusti poate conduce la determinarea pozititei denumirilor in text si stabilirea tipului de entitate pe care acestea o refera: persoane, locuri, organizatii sau alte tipuri, cum ar fi publicatii sau conflicte. Procesul poate fi aplicat unui singur document, caz in care determina denumirile si aparitiile lor in text, sau unei colectii de texte, obtinindu-se un dictionar al denumirilor continute in colectie. Folosirea ulterioara a acestui dictionar se dovedeste folositoare, insa nu strict necesara. Regasirea denumirilor se datoreaza intr-o mare masura algoritmilor euristici care exploateaza repetitiile sau alte regularitati detectate in text. Dificultatea o reprezinta ambiguitatile inerente unui text expprimat in limbaj natural. De exemplu, o conjunctie poate uni doua cuvinte, sau poate face parte, impreuna cu acestea dintr-o denumire sau proprietatea mai multor constructii de a defini o aceeasi entitate. Pentru elminarea dificultatilor induse de aceste din urma caz se foloseste forma canonica. Forma canonica asociata unui grup de structuri lexicale ce definesc aceeasi entitate este data de structura cea mai putin ambigua dintre toate variantele identificate in text. Prin asocierea unei variante cu forma canonica corespunzatoare, ambiguitatea variantei se va reduce.

Extragerea termenilor specifici unui anumit domeniu

Termenii specifici unui domeniu reprezinta o alta categorie lexicala capabila sa furnizeze informatii despre subiectul documentului analizat. Determinarea lor se face utilizind algoritmi euristici care utilizeaza dictionare continind termeni specifici anumitor domenii. Algoritmii regasesc in textul analizat forme pentru care verifica in ce masura se potrivesc exemplelor din dictionar. Obtinerea unor rezultate valide reclama repetarea termenilor specifici in text. Repetarea unui termen intr-un singur document conduce la concluzia ca documentul este corelat cu conceptul ilustrat de termen. Utilizarea dictionarului de termeni stabileste daca termenul apartine unui domeniu specific. Dictionarul de date se dezvolta progresiv, pe masura ce noi colectii de date sint supuse analizei fiind adaugati termeni apartinind tot mai multor domenii .

Abrevierile

O importanta sursa de forma variabile ale aceleiasi entitati o reprezinta abrevierile si prescurtarile. Utilizind un dictionar de termeni, abrevierile vor putea fi corelate cu formele canonice corespunzatoare. Aplicind aceeasi metoda, de corelare cu forma canonica, se identifica si alte elemente , cum ar fi :

Numere exprimate in diverse formate

Diferite formate de date

Exprimari ale unor sume valorice fofosond simboluri monetare

Uitlizarea unor formule stricte de limbaj( titluri, formulte de politete)

Clasificarea informatiilor

Determinarea similaritatii dintre documente pe baza asemanarii lexicale

Notinuea de similaritate intre documente sau clase de documente este esentiala. O masura simplista a similaritatii ar putea fi data de frecventa de aparitie a cuvintelor in documente. Totusi, datorita proprietatior semantice ale cuvintelor, aceasta metoda se dovedeste imprecisa, clusterele generate nefiind, de cele mai multe ori, reprezentative. O alternativa la folosirea cuvintelor ar fi realizarea unei analize semantice a documentelor, in scopul descoperirii conceptelor utilizate si clasificarii documentelor in functie de aceste concepte. Acest tip de analiza se dovedeste insa costisitor si dificil de realizat, reclaminind prezenta unor elemente continind cunostinte din anumite domenii. Printre astfel de elemente se pot afla dictionare de termeni specifici si de multe ori sint realizate manual, cu un efort considerabil, sau se preiau din surse suplimentare. Date fiind neajunsurile metodelor anterior prezentate, in analiza sint utilizate tot mai mult nuclelele lexicale in locul cuvintelor.

Un nucleu lexical reprezinta un grup de cuvinte care apar frecvent impreuna. Astfel de exemple pot fi “online library” sau “computer hardware”, ca si alte grupuri de cuvinte intilnite mai rar. Aceste nuclee sint identificate si stocate dinamic, fiind astfel specifice unei anumite colectii de documente. Se obtine astfel o colectie de termeni semnificativi semantic fara utilizarea unui element auxiliar –dictionar, lexicon- realizat manual. Nucleele lexicale identificate in fiecare document vor sta la baza algoritmilor de clusterizare. O clasa de documente poate fi fi identificata prin nuclelele lexicale cele mai frecvent intilnite in documentele pe care le contine. In acest mod conceptele continute sint rapid identificate.

Cautarea multipla

Paradigmele cautarii multiple clasice

Procesul clasic de cautare a informatiilor are la baza notiunea de cerere de regasire.

Aceasta reprezinta specificatiile utilizatorului care doreste sa regaseasca o anumita informartie. In functie de modul de precizare a specificatiilor, se pot identifica mai multe tipuri de cereri.

Cererile booleene permit utilizarea conjunctiilor , disjunctiilor intre termeni sau negarea unora dintre acestia. Termenii regasiti pot fi cuvinte sau grupuri de cuvinte. Cererile booleene permit utilzarea wild-card-urilor, la inceputul, in interiorul unui termen sau la sfirsitul acestuia. Se pot folosi conditii de proximitate, care reclama prezenta termenilor in acelasi paragraf. Cererile de regasire booleene permit regasirea informatiei necesitind insa specificatii destul de precis formulate din partea utilizatorului. Este si motivul pentru care nu se numara printre elementele de regasire specifice text-mining-ului, ci numai printre cele auxiliare.

Cererile exprimate in limbaj natural

Se bazeaza pe modelele probabilistice de regasire, care se aplica unui numar mare de aplicatii din domeniul regasirii informatiei si dovedesc performante ridicate .

Ideea de baza a acestor cereri este stabilirea probabilitatii conditionate p(Q|D) care exprima in ce masura documentul D este reprezentativ pentru cererea Q. Estimarea probabilitatii se face tinind cont de frecventa de aparitie a termenilor din cerere in documentul analizat si, eventual, de alte informatii desprinse din colectia de documente. Rezultatul unei cereri exprimate in limbaj natural este reprezentat de o secventa de documente ordonate descrescator in functie de valoarea probabilitatii estimate. Avantajul unor astfel de cereri il constituie usurinta in utilizare, motiv pentru care multe din motoarele de cautare le implementeaza.

Cererile hibrid( mixte)

Reprezinta combinarea intr-un mod unic a acelor doua tipuri –booleene si exprimate in limbaj natural, in scopul imbunatatirii performantelor celor din urma.

In principiu, o cerere mixta reprezinta o cerere exprimata in limbaj natural ale carei rezultate sint restrictionate astfel incit sa satisfaca si conditiile cererii booleene incorporate. In acest fel este posibila exprimarea specificatiilor negative, care nu sint suportate de cererile in limbaj natural. Cererile mixte sint utilizate pentru procese de regasire avansata, performantele regasirii fiind net superioare tipurilor de cereri anterioare.

Procesul de regasire poate fi imbunatatit prin utilizarea unor elemente auxiliare, cum sint dictionarele de sinonime, tezaurele sau prin eliminarea cuvintelor cu valoare semantica redusa.

Un tezaur reprezinta o resursa specifica unui anumit domeniu, continind termeni intre care exista anumite relatii semantice. Relatiile pot fi ierarhice, asociative sau, la limita, se poate defini o relatie intre cuvintele sinonime. Expandarea unui anumit termen al unei cereri intr-un tezaur se realizeaza de-a lungul unei anumite relatii.

Sinonimele reprezinta cuvinte avind acelasi continut semantic. Identificarea lor intr-un anumit document se realizeaza utilizind un dictionar de sinonime. Acesta este construit anterior si este independent de domeniu.

Cuvintele cu valoare semantica redusa sint reprezentate de prepozitii, conjunctii sau pronume, forme care apar cu frecventa mare in textele exprimate in limbaj natural, dar care nu fac referire la subiectul abordat de un anume document. Aceste forme lexicale vor fi eliminate in procesul de analiza lexicografica. De asemenea, vor fi excluse si din cererile care le contin. In acest sens vor fi definite colectii de astfel de termeni nesemnificativi semantic, care sa permita identificarea lor in vederea eliminarii.

Acest mod de ralizare a procesului, condus de utilizator, se dovedeste eficient in cazul cind se cunosc suficiente informatii despre informatia cautata iar utilizatorul este in masura sa precizeze suficient de exact coordonatele informatiei cautate.

In cazul regsirii unor informatii generale sau despre care se cunosc prea putine amanunte pentru a se formula o cerere suficient de precisa, mecanismul se dovedeste ineficient.

Este si motivul pentru care in domeniul cautarii informatiilor, a fost adoptata si se impune tot mai mult o noua notiune:scenariul.

Reprezinta o noua paradigma a regasirii informatiei, si presupune o utlizarea unui ansamblu de elemente in scopul regasirii informatiei. La baza unui astfel de proces se va afla un anumit numar de cereri, generate in mod automat de componente specializate capabile sa proceseze informatii cu un redus cintinut semantic ale utilizatorului.

Tipuri de scenarii

“Show me more like this”

Cunoscut si drept cerere prin exemple, este o tehnica eficienta pentru regasirea informatiilor cind se cunoaste un exemplu concret.

Exemplul este specificat de utilizator si poate avea un continut semantic ridicat , sau, dimpotriva, vag. Mecanismul presupune analizarea exemplului prezentat in scopul identificarii elementelor semantice principale, care sint apoi utilizate pentru a genera un ansamblu de cereri de regasire . Realizarea unui astfel de proces reclama existenta unor componente specializate, capabile sa realizeze analize ale exemplelor, sa identifice semnificatia acestora si sa genereze cereri de regasire pe baza informatiilor identificate. Elementul central al regasirii il constituie analizarea exemplului oferit de utilizator.

“Cauta numai”

“Cautarea utilizind categorii” este utilizat in scopul asigurarii unei regasiri eficiente a informatiilor. Utilizatorul specifica un anumit element de cautare, care poate fi o cerere sau un exemplu, si, anumite categorii de documente care corespund criteriilor sale.

Procesul de regasire este in acest caz mai complex, si presupune intr-o prima faza prelucrari asupra setului de documente care vor fi clusterizate in conformitate cu criteriile specificate de utilizator. Cererile de regasie, specificate de utilizator, sau, dupa caz, generate utilizind un exemplu al acestuia, vor fi adresate numai documentelor incluse in clase ce corespund specificatiilor utilizatorului..

In acest tip de scenariu, elementul central al regasirii il constutuie prelucrarea prealabila a colectiei de dcumente.

Social learning

Reprezinta, alaturi de scenarii, o noua orientare in regasirea eficienta a informatiilor si are la baza notiunea de sociabilitete a unui anumit document. Pentru fiecare document al colectiei se creeaza si mentine in cursul unei sesiuni de regasire o structura continind informatii despre numarul de cereri cu care documentul respectiv s-a dovedit compatibil. In cazul unei noi cereri, un document va fi indicat drept corespunzator si in functie de aceste informatii de “sociabilitate”. Elementul de noutate adus de aceasta noua orientare il reprezinta tratarea cererii de regasire in contextul mai larg al unei sesiuni de regasire, si nu ca o entitate izolata.

Clasificare prin clusterizare

Clusterizarea non-ierarhica

Clusterizarea este un proces automatizat care imparte o colectie de documente in mai multe clase, denumite clustere Documentele continute intr-o clasa prezinta o oarecare asemanare. Daca la baza procesului de clasificare se afla continutul documentelor, diferitele clase generate vor corespunde diferitelor teme majore dezbatute in colectia de date. Astfel, clasificarea se dovedeste o metoda utila de stabili continutul colectiilor de date. Pentru a identifica tema abordata de documentele unei anumite clase, sint selectati si evidentiati o serie de termeni comuni acestora.

Clasificarea se poate realiza insa si in functie de o combinatie de proprietati ale documentelor : dimensiunea lor, data eleborarii si, evident, continutul semantic al acestora. Cu cit complexitatea criteriului de clasificare este mai ridicata, cu atit numarul de clase generate va fi mai mare.

Ca o prima alicare a clasificarii se poate mentiona o forma a studiilor de piata care presupune analiza e-mail-urilor continind opinii ale consumatorilor, in scopul determinarii temelor majore abordate. Termenii identificati se pot referi, deopotriva, la punctele forte sau slabe ale organizatiei.

In sens general, clasificarea non-ierarhica este folosita pentru :

A stabili un sumar al subiectelor dezbatute in colectii mari de documente;

Determinarea similaritatilor mai putin evidente;

Prefectionarea procesului de cautare a unor informatii similare sau corelate.

Procesul de clasificare se poate realiza iterativ, sau recursiv, caz in care procesul este aplicat documentelor continute intr-o clasa rezultata, la rindul ei, in urma unui astfel de proces.

Identificarea clusterelor se realizeaza stabilind subseturi de documente intre care exista similaritati mai mari decit similaritatea lor cu elementele din afara subsetului. Scopul oricarui algoritm de clusterizare este minimizarea similaritatii intre clasele generate si maximizarea similaritatii interne.

Clusterizarea ierarhica

Algoritmii de clusterizare ierarhica se dovedesc deosebit de eficienti in cazul textelor exprimate in limbaj natural. Datele de intrare pentru un astfel de algoritm sint reprezentate de o multime de clustere formate dintr-un singur document, denumite si clustere singleton. Cele mai similare doua clustere vor fi apoi incluse intr-un cluster aflat pe un nivel superior. Aceste proces se repeta pina la obtinerea unui singur cluster, radacina, sau pina la atingerea unui nivel minim de similaritate. Depasirea acestui pragar conduce la realizarea unor clustere nevalide.

Arborele binar generat prin acest proces, numit si dendograma, contine in nodurile sale informatii complete referitoare la clusterizare, cum ar fi similaritatea intra si inter–cluster. Utilizind aceaste informatie, noi clustere sint formate prin fuzionarea unor clustere anterioare.

Vizualizarea si interpretarea informatiilor utilizind dendogramele se dovedesc a fi dificile, putin intuitive. In acest sens sint utilizati anumiti algoritmi care identifica, pe baza informatiilor referitoare la similaritate, clusterele .

“Decuparea” clusterelor din dendograma se realizeaza in functie de caracteristicile problemei de rezolvat. In general se defineste un nivel minim al similaritatii intra-cluster si un numar maxim de iteratii in care sa poata fi atinsa aceasta valoare prag.

O modalitate eficienta de a obtine in acelasi timp o viziune de ansamblu, dar si informatii detaliate despre structura de clustere este aplicarea procesului de identificare a acestora utilizind diferite valori prag ale similaritatii intra-cluster. Rezultatele obtinute reflecta cele mai importante decizii ale algoritmilor de clasificare, decizii luate la un anumit moment de timp si aplicate unui anumit nivel ierarhic al dendogramei.

Categorizarea

Presupune asignarea documentelor prelucrate unor categorii preexistente, denumite teme sau evenimente. Categoriile sint stabilite in conformitate cu scopul folosirii colectiei de documente. Atasarea documentelor unor categorii faciliteaza organizarea lor.

Documentele pot fi asociate uneia sau mai multor clase/categorii. Pe de alta parte, daca subiectul abordat de un document nu corespunde nici uneia dintre categoriile predefinite se impune crearea unei noi categorii. In acest sens este necesara colectarea unui set de exemple pentru noua categorie. Instrumentele matematice necesare realizarii unei astfel de operatii dint oferite de analiza discriminanta.

Categorizarea informatiilor utilizind reguli de productie

Clasificarea/ categorizarea documentelor utilizind reguli de productie presupune utilizarea unui set de documente pe baza carora se deduc intr-o prima faza regulile. Aceste sint folosite ulterior pentru clasificarea documentelor. Un avantaj al metodei este ca regulile obtinute pot fi modificate de utilizator, in scopul imbunatatirii performantelor procesului de clasificare. Un dezavantaj al acesteia il reprezinta imposibilitatea generarii unor reguli cu grad inalt de generalitate si, in acelasi timp, sificient de specializate pentru se dovedi eficienta aplicarea lor in colectii eterogene de documente. Pentru astfel de cazuri se impune realizarea mai multor seturi de reguli, corespunzator numarului de domenii abordate in colectie, ceea ce de cele mai multe ori reclama un efort considerabil.

Clasificarea informatiilor utilizind metode celei mai apropiate vecinatati

Reprezinta o solutia alternmativa analizei discriminate. Metoda se aplica atunci cind pentru un anumit cluster / clasa nu se poate stabili un “document mediu”, adica un centroid.

Presupune compararea noului document cu documente care au fost deja clasificate. Documentul va fi asimilat de clasa documentelor care ii sint similare in cea mai mare masura

Metodele reprezentate reprezinta numai setul de baza utilizat in scopul realizarii obiectivelor TM. In functie de context, acestora li se pot asocia:

Tehnici pentru identificarea corelatiilor;

Utilizarea arborilor de decizie;

Clasificari fuzzy;

Analiza discriminanta.

Instrumente TM

Datorita potentialului ridicat de regasire a informatiilor dovedit de noua orientare, citeva solutii soft au fost realizate .

Acestea implementeaza o varietate de metode de identificare a continutului semantic al unui text. Complexitatea fiecaruia dintre ele este diferita, in continuare fiind prezentate citeva dintre solutii, in ordinea crescatoare a complexitatii functionalitatii lor.

Ca elemente de implementare, majoritatea produselor utilizeaza retele neuronale ca metoda de baza in identificarea formelor lexicale.

Sint utilizate elemente de teoria probabilitatilor, analize statistice, liste de cuvinte cheie si reguli gramaticale.

SemioMap , Semio Ccorporation

A fost realizat utilizind tehnologia SEMIOLEXTM , elaborata de Claude Vogel.

Implementeaza paradigmele calculului semiotic, calculului formal al simbolurilor si elemente de calcul neuronal.

SemioMap permite extragerea frazelor relevante din colectii de date. In acest scop este construita o retea neuronala de co-aparitie, care grupeaza frazele intre care exista corelatii, si evidentiaza elementele principale ale grupurilor astfel realizate.

Structurile astfel construite releva pivotii semantici ai intregii colectii de texte.

Un pivot semantic reprezinta un concept cheie, care permite realizarea unor grupari semnificative, devenind astfel elementul central al unei grupari de texte.

Existenta pivotilor semanitci spliteaza reteaua semiotica in “cuiburi” de cunostinte.

Ca tehnici auxiliare sint utilizate procesarea lexicala, clusterizarea si vizualizari ale rezultatelor.

Determinarea proximitatii dintre frazele analizate se realizeaza tinid cont de contextul in care acestea se regasesc.

TextAnalyst , Megaputer Corporation

TextAnalyst realizeaza trei procese principale:

Textul este introdus intr-un cadru de lungime variabila, un simbol la un anumit moment de timp. Simbolurile pot fi litere, semne de punctuatie sau spatii. Dimesniunea cadrului poate fi modificata, limitele fiind de 2 sau 20 de caractere.

La trecerea textului prin acest cadru, cu ajutorul cadrelor instantanee obtinute pot fi identificate cuvintele, cuvintele derivate si gruparile de cuvinte ce apar in text.

Elementele identificate sint retinute de o retea neuronala construita in timpul translatarii textului prin cadru.

Conexiunile dintre termeni sint determinate de frecventa aparitiei impreuna a acestora.

Urmatorul pas presupune stabilirea frecventei cu care aceste elemente se regasesc impreuna in anumite constructii semantice , cum ar fi propozitiile. In acest fel sint identificate relatiile de baza intre concepte.

Ca elemente predefinite, sistemul utilizeaza o retea neuronala Hopfield, in care fiecare cuvint are asociat a anumita pondere. Datele continute in reteaua initiala devin intrari pentru reteaua construita. Drept rezultat, se obtine o retea semantica rafinata, care, prin normalizare conduce reteaua semantica rezultat.

Elementul principal al analizei este construirea retelei semantice.

Printre functionalitatile produsului se regasesc:

Construirea bazelor de cunostinte;

Analizarea continutului unor texte arbitrare;

Clasificarea textelor conform anumitor subiecte;

Regasirea semantica a informatiilor;

Agentware,, Autonomy Corporation

Arhitectura Agentware permite imbinarea algortimilor performanti de regasire a formelor cu realizarea unor analize complexe de analiza a contextului si identificare a conceptelor. Scopul acestor tehnici este automatizarea proceselor de clasificare, categorizare, imbunatarirea performantelor procesului de regasire a informatiilor si realizarea unor personalizari automate in cadrul colectiilor de date de mari dimensiuni.

Principiile de baza ale implementarii sint date de teoria Bayesiana a probabilitatilor si elementele de calcul neuronal. Elementul de baza in realizarea analizelor il reprezinta agentii inteligenti.

Aceste elemente permit produsului identificarea formelor intr-un anumit text si regasirea rapida si eficienta a acestor forme in colectii de texte. Pot fi identificate conceptele de baza dintr-un anumit text, pe baza unei analize a frecventelor termenilor continuti de acesta. Odata identificata “semnatura semantica “ a unui anumit text, este creat un Concept Agent, capabil sa regaseasca idei similare in site-uri, colectii de mail-uri sau alte tipuri de documente.

Elementul constitutiv esential al produsului il reprezinta Dynamic Reasoning Engine , carea realizeaza :

Identificarea conceptelor;

Crearea Concept Agentilor;

Antrenarea Concept Agentilor;

Regasirea informatiilor utilizind Concept Agentii;

Intelligent Miner for Tex, IBM

Reprezinta cel mai performant instrument al momentului pentru Text Mining, avind incluse functionalitati avansate in scopul,:

Realizarii unuor analize complexe asupra colectiilor eterogene de texte;

Colectiile eterogene reprezinta volume continind text in diferite limbaje si apartinind unui numar mare de domenii.

Realizarea unor analixe complexe asupra unui anumit text , cum ar fi:

Regasirea substantivelor proprii;

Regasirea conceptelor de baza, pe baza carora se stabileste continutul semantic al textului;

Corelarea abrevierilor cu forma normala;

Identificarea diferitelor formate de exprimare a timpului;

Identificarea utilizarii unor constructii specifice de limbaj, cum ar fi formulele de politete;

Identificarea formelor de reprezentare a valorilor monetare;

Elementul constructiv principal utilizat in regasirea informatiilor este reprezentat de o structura de index, capabila sa suporte multiple tipuri de cereri: booleene, cererei exprimate in limbaj natural sau cereri hibrid. Structura este modificata in timp real, prin integrarea termenilor identificati, dupa o prealabila analiza morfologica.

Pentru regasiri avansate sint utilizate tehnici fuzzy. O extensie a structurii de index permite regasirea informatiilor exprimate in dialecte asiatice: japonez, chinez.

Domenii de aplicabilitate a TM

Realizarea prelucrarilor asupra unor texte exprimate in limbaj natural ofera tehnologiei TM un potential urias de aplicabilitate in variate domenii, dat fiind si puternicul avint al unor domenii cum ar fi e-bussines sau e-commerce. Nu este de neglijat nici “avalansa” de potentiale surse de prelucrare creata de continua extindere a Internetului. In aceste conditii, pentru fiecare dintre functionalitatile TM se delimiteaza domenii de aplicabilitate. Acestea acopera un spectru extins, putind fi domenii conexe , cum este cazul tehnologiilor web, sau domeni indepartate informaticii, cum este cazul sociologiei.

Navigarea prin colectii mari de date isi gaseste o prima aplicabilitate in regasirea informatiilor pe web. Motoarele de cautare care implementeaza falcilitati Text Mining pot creste eficienta procesului de regasire intr-un mediu aflat in continua expansiune.

Organizarea documentelor conform unor categorii predefinite permite o mai buna organizare a documentelor unei organizatii in intranet.

Fluidizarea fluxurilor de realizare a tranzactiilor on-line in cazul activitatilor tip

e-commerce, e-bussines prin posilbilitatea asignarii automate a mesajelor primite unei anumite categorii : relatii cu furnizorii, relatii cu clientii, etc..

Analiza superioara a rezultatelor studiilor de piata moderne, efectuate utilizind instrumente web;

Realizarea unor analize economice , sociale si politice ale unei anumite zone sau perioade de timp;

administrare mai fluenta a colectiilor de date ale unei organizatii, prin automatizarea procesului de personalizare a informatiilor;

Procesul de text mining

Etapele procesului de text mining

Deoarece notiunea de proces de text mining nu este strict definita, etapele descrise in continuare se refera la cazul cel mai general al unui astfel de proces. Ele nu sint corelate cu nici un instrument specific de text mining si nu sint specifice unui anumit tip de aplicatie din acest domeniu. De asemenea, unele dintre detalii au fost omise, in scopul realizarii unei relatari cit mai clare. Procesul astfel prezentat nu este o garantie a succesului : stricta urmare a pasilor indicati nu va conduce neaparat la obtinerea unor rezultate. Expunerea evidentiaza in principal numai mecanismele procesului, factorii care influenteaza obtinerea unui succes fiind numai amintiti.

Procesul de text mining

Date Date Date Cunostine Cunostinte

Surse de date selectate preprocesate transformate Cunostinte asimilate

Selectare Preprocesare Transformare Mining Asimilare

Fig 3.1 Procesul de text mining

Obiectivele proiectului ce urmeaza sa fie realizat conduc intreg procesul de text mining.

Ele determina initierea noului proiect si tot ele stabilesc masura in care acesta este sau nu un succes. De asemenea, in activitatile fiecarei etape sint realizate in conformitate cu aceste obiective. Desi in general etapele sint realizate in ordinea ce va fi prezentata, activitatea efectiva necesita de multe ori reveniri asupra uneia sau mai multora dintre etapele prezentate, procesul dovedindu-se iterativ si nefiind departe de a fi unul autonom. In pofida recentelor cuceriri in domeniu,text mining ramine tributar experientei capatate in practica.

Din punct de vedere al resurselor solicitate pebtru realizarea lor, nu toate etapele procesului se dovedesc echivalente. In figura ___ este redata repartitia resurselor alocate unui proiect pe fiecare etapa a acestuia.

Stabilirea Procesarea Mining Asimilare

obiectivelor datelor cunostinte

Fig 3.2 Repartitia resurselor

Dupa cum se observa cu usurinta, cea mai mare parte a resurselor este destinata regatirii datelor ce vor fi supuse prelucrarii, ceea ce evidentiaza stricta dependenta a calitatii rezultatelor obtinute de calitatea datelor de intrare. Etapa efectiva de mining necesita numai un procent redus din resursele consumate in proiect.

Etapele procesului de data mining

Etapa 1: Definirea obiectivelor proiectului

Presupune stabilirea clara a problemei propuse spre rezolvare. Este o conditie esentiala a fiecarui proiect bazat pe data mining. Realizarea ei doar pe baza intuitiei, fara o fundamentare riguroasa poate conduce catre un insucces.

Etapa 2: Prelucrarea datelor

Cuprinde mai multe faze:

selectarea datelor

Se vor identifica sursele interne sau externe de date si se vor selecta subseturile de date care vor fi supuse procesului de mining;

preprocesarea datelor

Se determina calitatea datelor de intrare, stabilindu-se totodata tipul de operatii specifice data mining-ului care se pot implenenta si pot conduce la rezultate.

transformarea datelor

Datele vor fi transformate in conformitate cu cerintele unui anumit model analitic de structurare. Aceasta modelare urmareste obtinerea datelor intr-un format specific anumitor algoritmi din minig si reprezinta o conditie esentiala a incheierii cu succes a procesului.

Etapa 3: Text mining

Datele obtinute in etapa anterioara vor fi supuse unor prelucrari specifice. Reprezinta etapa esentiala a intregului proces, realizeaza implementarea diferitilor algoritmi, este de obicei cea mai rapida si se realizeaza automat.

Etapa 4: Analiza rezultatelor

Rezultatele obtinute in etapa antarioara sint interpretate si evaluate. Analiza se realizeaza in mai multe moduri, corespunzator tipurilor de prelucrari realizate, insa de cele mai multe ori sint implicate tehnici de vizualizare. Evaluarea se face in conformitate cu obiectivele proiectului.

Etapa 5 :Asimilarea cunostintelor.

Presupune integrarea cunostintelor obtinute in etapa anterioara in sintemul informational al organizatiei si valorificarea potentialului informational al acestora.

Coordonarea procesului de text mining

In realizarea procesului de text mining sint implicati mai multi participanti, indeplind diferite roluri in diferitele etape ale acestuia.

Analistul de sistem : dovedeste o intelegere profunda a domeniului studiat si stabileste obiectivele proiectului realizind un model analitic pe baza caruia vor fi stabiliti algoritmii ce se vor folosi.

Analistul de date : poseda cunostinte solide de statistica, si este un bun cunoscator al tehnicilor de analiza a datelor. Stabileste pentru fiecare operatie a modelului elaborat de analistul de sistem cel mai potrivit instrument text mining.

Specialistul in managementul datelor: este specializat in tehnici de manipulare a datelor si se ocupa cu colectarea acestora din surse operationale, baze de date externe sau depozite de date.

Etapa 1: Stabilirea obiectivelor proiectului.

Singura restrictie care poate afecta aceasta etapa este existenta unei probleme sau a unei oportunitati. Daca problema de rezolvat sau oportunitatea ce va trebui fructificata sint identificate, poate aparea o restrictie suplimentara generata de interesul manifestat in gasirea unei solutii. Tratarea superficiala a acestei etape poate genera mari dificultati in desfasurarea procesului,proiectele rau definite neavind sanse de a obtine rezultate de succes.

Elaborarea unor definitii clare si cuprinzatoare ale obiectivelor se dovedeste de cele mai multe ori dificila. Este necesara in acest sens o strinsa colaborare intre analistul de sistem,care cunoaste in profunzime domeniul, si analistul de date care poate transpune obiectivele intr-o aplicatie text mining.

Tot in aceasta etapa vor fi stabilite rezultatele ce se doresc a fi obtinute,o supraestimare a acestora determinind catalogarea proiectului drept un insucces. Precizarea rezultatelor ce se vor obtine va elimina neintelegerile ce se pot ivi pe parcursul procesului.

O alta activitata importanta a acestei etape este analiza costuri/beneficii. Rezultatele ce vor fi obtinute trebuie sa fie pe masura efortului depus pentru realizarea proiectului. De asemenea, echipele de analisti de sistem si analisti de date pot realiza identificari preliminare ale bazelor de date ce prezinta relevanta pentru proiect si ale algoritmilor ce vor fi implementati .

Etapa 2: Prelucrarea datelor

Este etapa care necesita cel mai mare volum de resurse, fiind utilizate mai mult de jumatate din resursele alocate intregului proces. Activitatile etapei sint structurate in trei faze.

Selectarea datelor –identificarea suselor si extragerea datelor

Preprocesarea datelor -testarea calitatii acestora

Transformarea datelor – prelucrarea acestora in conformitate cu cerintele unui anumit model de structurare;

Selectarea datelor

Scopul acestei faze este identificarea surselor de date, extragerea datelor necesare si supunerea lor unor prelucrari preliminare in vederea declansarii procesului de mining.

Dat fiind specificul procesului de text mining, numarul surselor potentiale este extrem de mare . In functie de formatul in care textele exprimate in limbaj natural se regasesc stocate, se pot evidentia doua categorii principale de tipuri de surse : surse care permit extragerea metadatelor; si surse care nu prezinta elemente auxiliare care sa poata fi valorificate sub forma de metadate

Printre sursele de date se regasesc:

Rapoarte de cercetare stocate in format electronic.

Informatii textuale obtinute ca urmare a realizarii studiilor de piata.

Texte in limbaj natural incluse in fisiere avind un anumit format, cum este cazul majoritatii informatiilor disponibile pe web.

Mesaje e-mail continind reactii ale clientilor sau alte informatii de piata.

Colectii de documente ale agentiilor de presa.

Output-uri ale instrumentelor de recunoastere automata a limbajului natural.

Variabilele selectate pentru text mining se numesc variabile active deoarece sint efectiv supuse prelucrarilor utilizind algoritmi de mining. Majoritatea acestor algoritmi,utlizeaza insa, cind este posibil, seturi de variabile auxiliare, care nu sint implicate direct in procesul de analiza dar faciliteaza vizualizarea si mai buna explicare a rezultatelor.

In aceasta faza, analistul de date poate indica deja metodele de mining corespunzatoare, fiind selectati algoritmii ce corespund cel mai bine aplicatiei respective. Este o faza importanta pentru intregul proces de mining, avind o mare influenta asupra desfasurarii celorlalte etape. Pe baza specificatiilor elaborate acum se va stabili modelul analitic al aplicatiei. Un rol important revine in acest moment specialistului in managementul datelor, responsabil cu colectarea datelor si integrarea lor in circuitul informational.

Preprocesarea datelor

Scopul acestei faze este de a sigura calitatea datelor selectate. Ca si in cazul oricarei analize cantitative, existenta unor date neafectate de erori este o conditie esentiala pentru obtinerea unor rezultate .

Preprocesarea datelor reprezinta cea mai delicata operatie in procesul de prelucrare a datelor, in principal datorita faptului sursele cuprind texte exprimate in limbaj natural, dovedind un grad redus de structurare. In aceasta etapa se vor realiza eventuale conversii de cod, in scopul unei prime omogenizari a colectiilor de date supuse prelucrarii. In anumite conditii se pot dovedi necesare conversii case.

Transformarea datelor

In timpul acestei etape, datele preprocesate sint transformate in vederea realizarii unui model analitic de structurare. Forma acestui model este specifica tipului de problema ce urmeaza a fi rezolvata.

Principalele atribute ale textelor exprimate in limbaj natural indica si tipul operatiilor la care va fi supus acesta in cadrul acestei etape. Textelor, care reprezinta date nenumerice si nestructurate, li se vor asocia anumite structuri de reprezentare si valori numerice. Cea mai intuitiva forma de reprezentare o reprezinta vectorul de cuvinte, adesea intilnit sub denumirea “Bag of words”, si reprezentat schematic in fig. 3.3

Fig 3.3Rreprezentarea sub forma vectorului de frecvente

Structura este generata cu ajutorul analizei lexicale efectuate asupra textului, si permite determinarea unor indicatori la nivel de cuvint. Pot fi determinati, pe baza ei, cu usurinta :

Numarul de cuvinte din text;

Frecventa de aparitie a unui cuvint in text;

Ponderea unui anumit cuvint in text;

Realizarea unor operatii simple, cum ar fi normarea vectorului si ordonarea lui in functie de frecventele cuvintelor pot da indicii preliminare despre continutul semantic al textului. Utilizarea unor elemente auxiliare in analiza, cum ar fi dictionare ale particulelor morfologice, permit, pe baza acestei structuri, identificarea cuvintelor de baza, aprofundind astfel continutul semantic al textului.

Vector de structuri de tipul : Cuvint; pozitia cuvintului in text

Permite determinarea numarului total de cuvinte, a frecventei absolute si relative a unui cuvint. Datorita informatiei suplimentare retinute – pozitit cuvintului in text- poate fi utilizata in corelatie cu reguli lingvistice.

Vector de structuri de tipul: Cuvint ; Cuvint predecesor; Cuvint succesor;

Informatia retinuta fiind mai complexa, se pot realiza analize la nivel de cuvint sau grup de cuvinte. Se poate astfel determina frecventa de aparitie a unui grup de cuvinte .

Vector de nuclee lexicale

Nucleele lexicale reprezinta grupuri formate dintr-un numar de n cuvinte, numite si

n-grame. O astfel de reprezentare realizeaza o extindere a modelelor precedente.

Reprezentarea bool-eana a textului

Presupune structurarea acestuia sub forma unui vector continind numai doua valori, de cele mai multe ori 0 si 1, indicind prezenta / absenta unui cuvint. Utlizarea acestei metode presupune existenta unui dictionar, lexicon continind cuvintele a caror prezenta/absenta va fi indicata in vector.

Avantajul metodei este dat de unificarea continutului textelor colectiei, dezavantajul fiind tocmai lexiconul, care poate atinge dimensiuni considerabile.

Asocierea de valori numerice textelor structurate reprezinta o alta transformare absolut necesara. Modalitatile de asociere difera in functie de tipul analizei realizate.

Pentru analizele efectuate asupra unui singur document valoarea textul poate fi reprezentat prin valori numerice reprezentind:

Frecventa absoluta a cuvintelor;

Frecventa relativa a cuvintelor;

Valori ale frecventei obtinute in urma normalizarii;

Analizele efectuate pe colectii de documente vor asocia valori numerice elementelor utilizate –cuvint sau n-grame- tinind cont de ansamblul intregii colectii. In general aceste valori se determina pe baza unui produs de forma :

TF(d,w)=tf(d,w)*IDF, unde

TF(d,w) : valoarea corectata a frecventei asociate elementului w in documentul d;

tf(d,w) : valoarea intrinseca a frecventei elementului w in documentul d;

IDF: coeficient de corectie, numit si frecventa inversa a documentelor;

Coeficientul de corectie prezinta diferite expresii analitice, in functie de tipul colectiilor pentru care se determina, insa de cele mai multe ori se regaseste sub una din formele:

IDF=log[D/D(w)] (1)

IDF(t,p)=log[D(t)/D(t,p)] (2)

Forma (1) este utilizata in cazul colectiilor statice, al caror continut este constant in timp. D reprezinta numerul de documente din colectie iar D(w) numarul de documente continind termenul w.

Pentru colectiile al caror continut este actualizat dinamic este utilizata pentru stabilirea frecventei inverse a documentelor forma (2) . IDF(t,p) reprezinta valoarea coeficientului la momentul de timp t, D(t) numarul total de documente din colectie la acelasi moment de timp, iar D(t,p) numarul de documente care la momentul t contin termenul p.

O forma alternativa de corectare a frecvntei interne poate fi date de expresia:

TF(w)=(1+ log(w))*(log( D/D9w))/ ||d|;

notatiile avind aceeasi semnificatie, iar ||d|| reprezentind norma vectorului d;

Etapa 3 : data mining

Datele prelucrate in etape anterioara vor fi supuse algoritmilor selectati.

In scopul unei mai bune intelegeri, aceasta etapa este prezentata independent. In practica insa, se dovedeste aproape imposibil de separat de etapa urmatoara – analiza datelor. De multe ori aceasta etapa determina reveniri in etapa de prelucrare a datelor.

Durata acestei etape si consumul de resurse implicate variaza mult in functie de tipul de problema. Astfel, in cazul segmentarii unei baze de date, citeva iteratii ale algoritmului se pot dovedi sufieciente si, dupa realizarea lor, se poate trece la etapa urmatoare. Modelele predictive implica un proces repetitiv in care modelul este aplicat datelor de test inainte de a fi implmentat pe datele reale. De obicei, in procesul de data mining sint implicati mai multi algoritmi. De exemplu, o baza de date poate fi mai intii segmentata, si apoi fiecare segment rezultat prelucrat cu ajutorul unor modele predictive. Alegerea acestor algoritmi este facuta de analistul de date pe baza unui set de factori, printre care :tipul obiectivelor, capacitatea de a prelucra anumite tipuri de date, scalablilitatea sau masura in care rezultatele obtinute pot fi explicate.

Principalele tehnici auxiliare implicate in text mining sint:

Vizualizarea

Clasificarea

Modele predictive

Segmentarea

Determinarea asocierilor

Recunoasterea formelor

Instrumentele de mining implementeaza toate aceste tehnici, ele putind fi folosite in rezolvarea diferitelor tipuri de probleme. Imbunatatirea performantelor algoritmilor se poate realiza prin utilizarea unor elemente auxiliare, cum ar fi : liste de morfoelemente – permint identificarea cuvintelor derivate; dictionare de sinonime – permit stabilirea mai precisa a continutului semantic al textului analizat;liste de stop- contin elemente lexicale cu continut semantic redus, cum ar fi : conjunctii, prepozitii, adverbe, prenume personale. Utilizarea listelor de stop permite identificrea rapida a unor astfel de elemente, in scopul eliminarii lor. Un ultim element auxiliar folosit il reprezinta metadatele, atunci cind sursele de date permit extragerea lor.

Analiza rezultatelor

Este cea mai importanta etapa a intregului proces. De altfel, in pofida existentei tehnicilor de vizualizare tot mai peformante, activitatea nu poate fi realizata corespunzator decit printr-o colaborare intre analistul de sistem si a analistul de date. Analiza rezultatelor obtinute se realizeaza in strinsa corelatie cu obiectivele stabilite pentru proiect.

Ca etapa, analiza rezultatelor se afla intr-o strinsa corelatie cu etapa de text mining, in practica una dintre etape determinind adesea reiterari ale celeilalte.

Specificul aplicatiei dezvoltate stabileste tipul activitatilor ce vor fi realizate in aceasta etapa. Conditia care guverneaza intregul proces de analiza este :”descoperirea unor informatii noi, valide si operationale”. In caz negativ va fi reiterata etapa de text mining. Se observa o diferenta fundamentala fata de metodele de analiza apartinind statisticii, care conduc intotdeauna la un raspuns categoric de forma :“da, ipoteza este corecta” sau “ nu, ipoteza nu este verificata”. Tehnologia text mining poate avea ca rezultat fie o ipoteza fie o noua directie de explorare. De exemplul, in segmentarea bazelor de date echipele de analisti incearca sa asocieze o interpretare fiecaruia dintre segmentele obtinute. Pentru a fi posibil acest lucru fiecare segment trebuie sa prezinte un grad mare de omogenitate. Daca insa se obtin numai citeva segmente avind un numar mare de inregistrari, nu se pot realiza diferentieri semnificative intre ele. Intr-o astfel de situatie utilizarea elementelor auxiliare se poate dovedi hotaritoare.

Reguli de productie

Utilizarea regulilor de productie in aceasta etapa a procesului de mining trebuie sa tina cont de problemele specifice ce se pot ivi. Astfel, stabilirea unui nivel de incredere prea scazut va permite algoritmilor identificarea unui numar mare de reguli. In acest caz, multe dintre reguli se dovedesc inaplicabile, afectind numai un numar redus de date. Reciproc, stabilirea unui nivel de incredere prea ridicat va detremina identificarea unui numar mic de reguli, de obicei regulile cele mai importante, deja cunoscute, si, in consecinta, inoperabile la rindul lor.

Obtinerea unor rezultate operationale utilizind regulile de productie este consecinta unui sir de iteratii care sa permita variatii ale nivelului de incredere.

Asimilarea cunostintelor

Reprezinta etapa care incheie procesul de text mining si are drept scop realizarea obiectivelor stabilite in prima etapa, prin utilizarea informatiilor noi, valide si operationale identificate in timpul procesului.

Doua sint obiectivele principale ale acestei etape:

sa demonstreze ca informatiile identificate sint noi, valide si operationale;

sa indice modalitati de utilizare ale informatiilor identificate;

Aceste obiective vor fi indeplinite de analistul de sistem a carui experienta ii va permite sa coreleze informatiile descoperite cu obiectivele care au declansat procesul de mining. Asimilarea cunostintelor este semnificativ dependenta de tipul si domeniul aplicatiei ce va fi fundamentata utilizind noile cunostinte. De asemenea, ca urmare a procesului de text mining se pot impune modificari ale sistemului informational sau operational al organizatiei. Integrarea cunostintelor poate presupune utilizarea unor noi modele predictive, sau a unor noi reguli de productie. Se pot dovedi necesare modificari ale structurilor bazelor de date sau utilizarea altor forme de structurare a datelor.

Un ultim avantaj al realizarii unui proiect utilizind text mining ar putea fi demonstrarea importantei datelor si eficientei solutiilor “data-driven”. In acest mod pot fi fundamentate noi initiative orientate pe date ale organizatiilor, cum ar fi datawarehousing sau data marting.

Factorii care influenteaza succesul unui proces de text mining

Etapele prezentate anterior reprezinta numai succesiunea logica a activitatilor unui proces de text mining, nefiind o garantie a atingerii obiectivelor acestuia.

Succesul deplin al unui astfel de proces este influentat de anumiti factori, care, intr-o abordare generala, se pot structura pe trei categorii.

Factorii determinati de cadrul organizatoric

existenta unui grup tinta caruia sa i se adreseze aplicatia realizata.

Existenta unui coordonator al activitatii intregului proces;

Existenta unor specialisti in analiza datelor si analiza de sistem;

Existenta bazei materiale necesare dezvoltarii procesului;

Factori determinati de oportunitatea aplicatiei

Definirea clara a obiectivelor aplicatiei;

Realizarea unei analize detaliate costuri / beneficii;

Capacitatea acesteia de a genera solutii cara sa aiba un impact deosebit in mediul pentru care a fost dezvoltata;

Obtinerea aplicatiei in timp real;

Factori determinati de calitatea surselor de date utilizate

Dupa cum se observa, in lista factorilor care influentezza succesul aplicatie, tehnologia text mining nu se regaseste. Principalul motiv este ca, procesul de text mining, in ansamblu, este intr-o mai mare masura supus experientei oamenilor implicati , obiectivelor sale si datelor pe care le prelucreaza decit tehnologiei text mining in sine.

Detectarea si regasirea evenimentelor in articole de presa

Societatea contemporana ofera spectacolul unei evolutii tumultuoase in fiecare dintre multiplele planuri ale complexului sau edificiu. Mecanismul mass media este cel care ofera instantanee fidele ale unei realitati in continua schimbare. Stocarea electronica a acestor adevarate radiografii ale momentului devine astfel un amanunt deloc neglijabil, constituindu-se intr-o adevarata provocare in domeniul regasirii informatiei. Date fiind caracteristicile surselor astfel obtinute –colectii de mari dimensiuni, un grad sporit de neomogenitate, textele fiind exprimate in limbaj natural- text mining se dovedeste a fi instrumentul cel mai potrivit .

Detectarea si regasirea evenimentelor in articole de presa se cristalizeaza astfel atit ca un cimp fertil de aplicabilitate a tehnologiei text mining, cit si ca o directie de cercetare de sine statatoare.

Printre obicetivele noului domeniu se regasesc :

Identificarea evenimentelor semnificative din colectii de articole de mari dimensiuni;

Prezentarea continutului acestor colectii sub forma unor sumare cu diferite grade de abstractizare;

Posibilitatea identificarii automate a unui nou eveniment atunci cind apare;

Regasirea unor articole reprezentative in raport cu anumite exemple indicate de utilizator;

In scopul eliminarii ambiguitatilor de limbaj se impune definirea clara a doua notiuni fundamentale, respectiv eveniment si instanta a evenimentului.

Evenimentul reprezinta o notiune abstracta ce descrie un anumit fenomen. Referirea fiind una abstracta, nu vor exista elemente care sa conduca la particularizarea fenomenului. De exemplu, un eveniment poate fi o criza politica, in general.

Instanta evenimentului reprezinta o notiune concreta, ce descrie un anumit fenomen precizind si elemente pentru individualizarea acestuia. Criza politica din Balcani va reprezenta o instanta a unui eveniment. Un eveniment pentru care sint precizate coordonate locale sau temporale devine o instanta a unui eveniment.

In conformitate cu aceste precizari, prima observatie care se desprinde este ca in articolele de presa nu se regasesc evenimente, ci instante ale acestora. Distributia acestor instante se realizeaza conform anumitor reguli, ce se dovedesc utile in orientarea procesului de mining.

Articolele care abordeaza acelasi eveniment prezinta similaritati lexicale. Articolele referitoare la aceeasi instanta a unui eveniment, pe linga similaritatea lexicala sint, de obicei, apropiate in timp. Exceptie fac instantele ce efect intirziat, cind ecourile se pot regasi dupa o perioada considerabila de timp. Tinind seama de aceste caracteristici, o prima metoda de identificare a evenimentelor in articole de presa ar putea fi clusterizarea colectiei de articole dupa un criteriu complex, care sa includa similaritatea lexbcala si proximitatea temporala.

Existenta unui decalaj temporal considerabil intre articole similare lexical indica existenta unui eveniment care prezinta instante multiple. Pentru identificarea unei anumite instante se impune utilizarea unei ferestre temporale care reduce procesul de cautare la un interval limitat de timp.

Modificari ale vocabularului folosit si o brusca schimbare in distributia frecventelor termenilor indica un nou eveniment. Este si motivul pentru carea actualizarea dinamica a setului de cuvinte regasite intr-o anumita colectie si a frecventelor asociate acestora se dovedesc extrem de importante. Identificarea substantivelor proprii se dovedeste utila in particularizarea anumitor instante.

anumita instanta este abordata intr-un interval de timp limitat, cuprins de obicei intre una si patru saptamini. Se dovedesc astfel necesare metode de regasire a informatiei care sa necesite un numar redus de exemple de antrenare pentru a atinge o anumita performanta in procesul de regasire, fructificind astfel decalajul temporal dintre anumite instante.

Aplicatia realizata are drept scop studierea comportamentului algoritmilor implementati pe texte in limba romana, in vederea stabilirii parametrilor optimi care conduc la obtinerea unor rezultate.

Au fost implementati algoritmi pentru identificarea evenimentelor din colectii mari de articole, identificarea unui eveniment nou si asignarea automata a unor etichete pentru articole noi, pe baza unui set redus de exemple si contraexemple de antrenare.

Algoritmii au fost integrati in cadrul mai larg al procesului de text mining, sistemul permitind selectarea datelor, prelucraea acestora, aplicarea algoritmilor de mining si vizualizarea rezultatelor obtinute.

Selectarea datelor

Permite selectarea unei anumite baze de date autilizatorului. Nu este necesara o anumita atructura, sistemul fiind capabil sa identifice structura acesteia, numarul de tabele si structura fiecareia dintre ele.

Fig . 4.1. Selectarea datelor

Selectarea unui anumit atribut este realizata utlizind cereri de regasire parametrizate, pe baza carora este creata o tabela temporal numita t ,avind structura Cod, Articol;

pTab->Create("t");

pTab->CreateField("Articol",dbMemo,1000);

pTab->CreateField("Cod",dbInteger,2);

Cererea de regasire permite selectarea a trei cimpuri: cheia primara a tabelei, cimpul care va fi supus prelucrarilor si un cimp de ordonarea cel mai adesea acesta fiind data.

Atributele selectate ,exceptind cimpul de ordonare sint pastrate in tabela t. in vederea prelucrarilor ulterioare.

Fig 4.2 Creare cerere parametrizata

In implementare a fost folosita baza de date Articole. mdb, si tabela Articole avind structura :

Cod articol; Titlu; Autor; Data; Articol;

Articoleloe selectate apartin mai multor agentii de presa si acopera perioada octombrie 1998? 2000, distributia acestora in timp nefiind uniforma. Au fost utilizate atructuri de date sfecifice tehnologiei Dao, respectiv CDaoDatabase, CDaoTableDef, CDaoRecordset, CDaoQueryDef.

Prelucrarea datelor are drept scop eliminarea inconvenientelor majore ale textelor exprimate in limbaj natural: inexistenta unei structuri si lipsa valorilor numerice. Se stabileste in aceasta etapa modul de asociere a unor valori numerice si structurarea acestor valori conform unui anumit model . Principalele operatii efectuate sint analiza lexicala, transformarea, si sortarea .

Fig. 4.3 Prelucrarea datelor

Analiza lexicala permite identificarea cuvintelor unui anumit text si stabilirea frecventelor absolute ale acestora. Pentru un cuvint se retin doua tipuri de informatii: informatiile locale, decsriu cuvintul in contextul local, al unui anumit articol si sint modelate prin clasa :

class InfLocal

{

public:

InfLocal();

CString Cuvint;

double Frecventa;

};

si informatiile globale, care caracterizeaza cuvintul in contextul intregii colectii supuse analizei. Acest tip de informatii sint modelate de clasa:

class InfGlobal

{

public:

InfGlobal();

CString Cuvint;

int NrArticole;

};

Pentru realizarea analizei lexicale au fost utilizate elemente auxiliare , modelate sub forma unor structuri LIFO, si implementate prin clasele:

class stiva

{

public:

InfLocal vector[1000];

int NrElemente;

int Inca();

stiva();

void Init()

{NrElemente=0;};

int Exista(CString);

void NewFrecveta(int i);

int Vida();

void In(CString);

void Out(InfLocal *c);

int GetDim();

};

Clasa permite identificarea cuvintelor distincte dintr-un text , stabilirea numarului acestora si frecventelor absolute asociate.

class StivaG

{

privat:

InfGlobal vector[30000];

int TotalCuvinte;

public:

void Init();

int Inca();

int Exista(CString);

int Vida();

void In(CString);

void Out(InfGlobal &c);

int GetTotalCuvinte();

void NewFrecventa(int);

int GetNrArticole(int);

};

Structura modelata permite determinarea numarului total de articole din colectie, determinarea numarului total de cuvinte dintincte si stabilirea numarului de articole in care se regaseste un anumit cuvint.

Modelul de structurare pentru un anumit articol este redat de clasa Articol:

class Articol

{

private:

int NrCuvinte;

int CodArticol;

public:

int Rang[1000];

InfLocal vector[1000];

Articol();

void Init();

void Sortare();

int GetNrCuvinte();

int GetCodArticol() ;

int Exista(CString);

double GetFrecventa(int);

void SetCodArticol(int );

void AddCuvint(InfLocal);

void AddCuvint(InfLocal, int);

void Transformare();

void Normare();

};

Clasa retine informatii de identificare a unui articol, prin codul acestuia, cuvintele continute si frecventele asociate, numarul de cuvinte distincte si permite realizarea unor operatii asupra valorilor frecventelor.

Sistemul creeaza automat o structura de tip stiva continind elemente lexicale cu continut semantic redus. Acestea sint reprezentate de conjunctii, prepozitii, adverbe, pronume personale. Structura, denumita StivaStop permite eliminarea elementrlor pe care le contine din textele supuse analizei. Utilizarea acesteia este facultativa, putind fi inhibata sau activata.

Analiza lexicala opereaza asupra unui element CString, si presupune cautarea repetata a delimitatorilor definiti prin:

Delimitator=" ,.'?!:;+=<>\"()}{][+*|";

while(!sArticol.IsEmpty())

{

buffer.Cuvint.Empty();

int l=sArticol.FindOneOf(Delimitator);

if(l)

for(int i=0;i<l;i++)

buffer.Cuvint+=sArticol[i];

if(!VbEliminare)

{

int Poz;

Poz=StivaTmp.Exista(buffer.Cuvint);

if(Poz) StivaTmp.NewFrecveta(Poz);

else if(StivaTmp.Inca())

StivaTmp.In(buffer.Cuvint);else

AfxMessageBox("Depasire stiva");

}

else

{

int Pozs;

Pozs=StivaStop.Exista(buffer.Cuvint);

if(!Pozs)

{

int Poz;

Poz=StivaTmp.Exista(buffer.Cuvint);

if(Poz) StivaTmp.NewFrecveta(Poz);

else if(StivaTmp.Inca())

StivaTmp.In(buffer.Cuvint);else

AfxMessageBox("Depasire stiva");

}; };

buffer.Cuvint.Empty();

sArticol.Delete(0,l+1);};

Pentru descrierea intregii colectii este utilizata clasa :

class SetArticole

{

private:

int NrArticole;

Articol vector[1500];

public:

void Init();

int GetNrArticole();

void IncNrArticole();

void Add(int,InfLocal);

void SetCod(int,int);

void Transformare();

void Sortare();

void GetSimilaritate(int,int,int, double *);

void GetSimilaritate(Articol *, int, double *);

void Normare();

void GetCod(int, int *);};

Structura contine informatii cantitative, specificind numarul total de articole identificate in intreaga colectie. Au fost implementate operatii la nivelul intregii colectii, cum este adaugarea unui articol, sau la nivel de articol: transformare, sortare, normalizare. De asemenea, structura permite obtinerea unor informatii de identificare a articolelor continute.

Rezultatele obtinute in urma prelucrarilor sint stocate in structurile globale :

SetArticole Colectie; StivaG InfG;

Transformarea datelor

Presupune aplicarea unor transformari asupra valorilor primare reprezentate de frecventele absolute. Transformariloe pot fi simple normari, pentru incadrarea valorilor frecventelor in intervalul (0, 1] sau pot fi mai complexe, avind drept scop corelarea informatiilor globale si locale pentru un anumit cuvint.

Sortarea ordoneaza descrescator in functie de frecventa cuvintele dintr-un articol.

Aplicatia realizeaza o transformare de tipul:

TF(w)=(1+ log(w))*(log( D/D(w))/ ||d|;

Unde TF(w) reprezinta valoarea modificata a frecventei;

w reprezinta valoarea initiala a frecventei;

D este numarul total de articole den colectie;

D(w) este numarul de articole care contin cuvintul pentru care se recalculeaza valoarea frecventei, iar

||d|| este norma vectorului prin care este reprezentat articolul.

Transformarea este implementata utilizind doua metode ale clasei Articol, respectiv Transformare si Normare.

void Articol::Transformare()

{ int N=Colectie.GetNrArticole();

double s=0;

for(int i=1;i<=NrCuvinte;i++)

{ int poz=InfG.Exista(vector[i].Cuvint);

int n=InfG.GetNrArticole(poz);

double f=vector[i].Frecventa;

vector[i].Frecventa=(1+log(f)/log(2))*log((float)N/(float)n)/log(2);} }

void Articol::Normare()

{

double s=0;

for(int i=1;i<=NrCuvinte;i++)

{ double f=vector[i].Frecventa;

s+=(f*f);};

for(int j=1;j<=NrCuvinte;j++)

{ double m;

m=vector[j].Frecventa;

m/=sqrt(s);

vector[j].Frecventa=m;

};}

La nivelul colectiei de articole, transformarile se realizeaza prin metodele similare ale clasei SetArticole.

Rezultatele partiale ale etapei de prelucrare a datelor pot fi vizualizate intr-o structura ce prezinta sursa de provenienta a datelor, intervalul de timp acoperit de articolele din colectie, numarul total de articole si numarul total de cuvinte distincte identificate in acestea.

Fig 4.4 Rezultate partiale

Algoritimi utilizati

Au fost utilizati algoritimi de clasificare, specifici pentru fiecare din operatiile implementate .

Identificarea evenimentelor in articole de presa

Are drept scop descoperirea evenimentelor necunoscute anterior in colectii de articole neomogene si de mari dimensiuni. Activitatea poate fi asociata unui proces de invatare nesupervizata, neexistind seturi de antrenare, exemple specificate de utilizator sau ,metadate .

Metode specifice

Deoarece fiecarui eveniment i se asociaza un numar de articole continid instante ale acestuia, clusterizarea se dovedeste o metoda corespunzatoare . In acest sens sint utilizate doua metode de clusterizare .

Group Average Clustering-GAC o varianta a algoritmilor de clusterizare implementind strategia divede et impera;

Single pass incremental clustering- INCR, un algoritm de clustarizare incrementala, avind pasul 1.

Cele doua metode implementeaza strategii diferite de analiza a colectiei de articole.

GAC este un algoitm de clasificare ierarhica, generind iererhii ale documentelor analizate. Datele de intrare sint reprezentate de intreaga colectie, din care se “decupeaza “ la fiecarea iteratie clustere pe baza similaritatii dintre articole.

INCR prodece partitionari nonierarhice ale colectiei initiale. Maniera de analizare a colectiei este total opusa, articolele fiind procesate iterativ, la fiecare iteratie fiind supus analizei un nou articol, care va fi absorbit de un cluster deja existent sau va deveni primul element al unui nou cluster.

Forme de reprezentare

Reprezentarea textului este realizata sub forma “bag of words” ,fiecare articol avind asociat un vector de frecvente modificate in faza de prelucrare a datelor. Pentru reprezentarea clusterelor se utilizeaza un vector prototip, denumit si centriod al clusterului, ale carui valori se obtin pe baza valorilor frecventelor vectorilor care il compun.

Similaritate

Pentru a stabili similaritatea dintre doua articole se poate utilizat una din metodele :

sim=1-d; unde d reprezinta distanta euclidiana dintre vectorii asociati;

sim= F1(i)*F2(i); unde F1(i),F2(i) reprezinta valorile frecventelor de pe pozitia “i” in cei doi vectori de frecvente.

Aplicatia realizata implementeaza a doua metoda de determinare a simlaritatii dintre articole.

Group Average Clustering

Algoritmul maximizeaza similaritatea medie dintre doua articole, generind o ierarhie de clustere incepind de la baza acesteia, forma cea mai generala putind fi descrisa astfel:

Pasul 1:

se determina similaritatile dintre toate elementele colectiei;

cele mai apropiate doua elemente formeaza un cluster;

Pasul 2:

se elimina din colectie elementele care au format la pasul precedent un cluster;

se adauga in colectie centroidul clusterului format;

Pasul 3:

se reiau pasii precedenti pina la obtinerea unui singur cluster;

Deoarece complexitatea unui astfel de algoritm depinde de numarul documentelor de intrare la puterea a patra, aplicarea algoritmului in aceasta forma se dovedeste costisitoare pentru aplicatiile care presupun prelucrarea unui volum considerabil de date.

In scopul eliminarii consumului considerabil de resurse, a fost dezvoltata fractionarea, bazata la rindul ei tot pe strategia divide et impera, si care realizeaza un compromis intre calitatea clusterelor generate si counsumul de resurse. Fractionarea presupune divizarea prealabila a colectiei initiale. Generarea clusterelor esre realizata iterativ, fiecare iteratie fiind insa precedata de de impartirea colectiei in subcolectii de o anumita dimensiune. Fiecareia dintre subcolectii I se aplica algoritmul de clusterizare. Clusterele astfel obtinute, prin analiza subcolectiilor, sint apoi integrate pe nivelul imediat superior. Complexitatea algoritmului astfel modificat depinde de produsul m*n, unde n reprezinta numarul de elemente ale colectiei initiale, iar n reprezinta dimensiunea subcolectiilor fractionate.

In aplicatia realizata a fost implementata urmatoarea varianta a algoritmului:

Pasul 1:

fiecare element al colectiei devine un cluster singleton;

partitia initiala este compusa din aceste clustere singleton;

Pasul 2:

colectia curenta este fractionata in subcolectii consecutive si disjuncte de dimensiune m;

Pasul 3:

fiecarei partitii i se aplica algoritmul GAC, care presupune gruparea celor mai apropiate doua elemente intr-un cluster aflat pe un nivel ierarhic superior;

se repeta gruparea pina cind numarul de elemente din subcolectie s-a diminuat cu un factor r, sau pina cind similaritatea dintre oricarea doua elemente este inferioara unui prag prestabilit.

Pasul 4:

se elimina limitele subcolectiilor,

clusterele rezultate sint integrate in colectia modificata care va fi analizata in continuare;

Pasul 5:

se repeta pasii de la 1 la 4, pina cind partitia modificata contine cel mult m elemente, sau cind similaritatea intre orocare doua elemente ale acesteia este inferioara unui prag prestabilit.

Implementare

Aplicatia realizata permite utilizatorului specificarea unui set de parametri , in functie de care se analizeaza si performantele algoritmilor implementati.

Deoarece in implemetare au fost utilizate doua metode de identificare a evenimentelor in colectii de articole, in vederea compararii rezultatelor generate de cele doua metode a fost realizata o interfata comuna pentru acestea.

Se poate compara comportamentul algoritmilor in cazul aceluiasi prag de similaritate.

De asemenea, devin posibile comparatii intre senzitivitatile celor doi algoritmi fata de setul de parametrii stabiliti de utilizator.

Fig 4.4 Stabilirea parametrilor

Utilizatorul poate specifica numarul de articole continute de sobcolectiile generate – dimensiunea acestora-, nivelul mininm al similaritatii – pragul de similaritate-, factorul de reductie a numarului de articole dintr-o subcolectie si numarul de cuvinte dintr-un text utilitate pentru determinarea similaritatii. Valorile specificate de utilizator pot fi stricte, cum este cazul pragului de similaritate, sau orientative , cum este valoarea care indica numarul de cuvinte utilizate in analiza. In acest din urma caz, daca un articol contine un numar de cuvinte mai mic decit valoarea specificata de utilizator, determinarea similaritatii sale cu alte articole se va realiza utilizind in analiza, pentru ambele articole, numarul de cuvinte cel mai mic.

Clase modelate

Pentru implementarea algoritmului au fost modelate clasele cluster si partitie.

class Cluster

{ int CodCluster;

int Stare;

int NrArticole;

int CodArticole[100];

Articol Centroid;

public:

Cluster();

void Init();

void AddArticol(int);

void SetCod(int);

int GetCod();

void SetInactiv();

void SetActiv();

int GetStare();

int GetNrArticole();

int GetCodArticol(int);

virtual ~Cluster();

};

Clasa contine informatii de identificare a articolelor continute de cluster, informati retinute in vectorul de coduri al acestora. Sint posibile operatii de actualizare , respectiv adaugarea unuia sau mai multora articole in cluster. Un element important il reprezinta atributul “stare”, care indica existenta unui cluster activat sau dezactivat. Structura contine si informatii cantitative, prin artibutul NrArticole, care specifica numarul de articole asimilate de cluster.

Pentru utilizarea intregii multimi de clustere generate este utilizata clasa Partitie.

class Partitie

{

int NrClustere;

Cluster vector[300];

int Cursor;

public:

Partitie();

void Init();

void AddCluster(int);

void SetActiv(int);

void SetInactiv(int);

void AddArticol(int,int);

void Update(int,int);

int GetRang(int);

int GetNrCluster();

int GetFirst();

int GetNext();

int GetPrev();

int GetLast();

virtual ~Partitie();

};

Permite stocarea informatiilor despre clusterele generate, retind numarul acestora. Sint retinute informatii de identificare a acesstora, prin intermediul vectorului de coduri.

Operatiile se pot realiza la nivel de partitie –adaugarea unui nou cluster- sau la nivel de cluster, fiind posibil:

adaugarea unui articol intr-un cluster;

activarea/dezactivarea unui cluster;

modificarea unui cluster;

Au fost implementate si facilitati pentru parcurgerea iererhiei de clustere generate.

Clasele auxiliare utilizate in implementarea algoritmului sint:

class Punct

{

public:

int Linie;

int Coloana;

Punct();

virtual ~Punct();

};

Clasa permite determinarea coordonatelor elementelor intre care similaritatea este maxima si care vor fi agregate intr-un cluster.

class MatSimilaritate

{

privat:

double Similar[500][500];

int NrElemente;

byte Stare[500];

int NrActive;

public:

MatSimilaritate();

void GetSimGlobal(double *);

void GetSimInterval(Punct *,int,int);

void GetSim(int, int, double *);

void SetCluster(int);

void SetInactiv(int);

void SetActiv(int);

int GetNrElemente();

void GetSimilarPast(int *,int, double *);

void SetNrElemente(int);

void SetSimilar(double,int,int);

void GetCadru(int,int, int *);

void GetReductie(int,int,int, double *);

void Update(int,int);

void UpdateMin(int,int);

void UpdateMax(int,int);

void GetActive(int *);

int GetStare(int);

void GetSimVector(int,int, double *);

void GetSimilar(int, double *);

void Init();

void GetMinSim(double *);

double GetSPunct(int,int);

virtual ~MatSimilaritate();};

Clasa este utilizata pentru a determina similaritatea maxima :

la nivelul intregii colectii;

pentru un anumit interval;

dintre un anumit element si celelalte elemente ale colectiei;

Numarul de elemente al matricei de similaritate este stabilit prin metoda SetNrElemente.

Liniile matricei de similaritate au valori asociate, avind semnificatiile :

0: este o linie inactiva, care a referit un element absorbit de un cluster de pe un nivel ierrhic superior;

1: linia se refera la un articol;

2 : linia se refera la un cluster;

Operatiile implementate se refera la determinarea similaritatii, modificarea starilor anumitor linii, sau modificarea similaritatii in cazul generarii unor clustere.

Implementarea algoritmului GAC, utilizind structurile prezentate, se realizeaza astfel:

while(((*SimG)>SimMin)&&((*Active)>DimC))

{

while(((*SimL)>SimMin)&&((*RedL)>Red))

{

Punct *p;

p=new Punct;

mat.GetSimInterval(p,Prim,(*Ultim));

int sLinie,sColoana;

sLinie=mat.GetStare(p->Linie);

sColoana=mat.GetStare(p->Coloana);

// daca sint doua articole

if((sLinie==1)&&(sColoana==1))

{

mat.SetCluster(p->Linie);

mat.SetInactiv(p->Coloana);

mat.Update(p->Linie,p->Coloana);

partitie.AddCluster(p->Linie);

int rang=partitie.GetRang(p->Linie);

partitie.AddArticol(rang,p->Linie);

partitie.AddArticol(rang,p->Coloana);

}

// primul este articol, al 2 lea cluster

if((sLinie==1)&&(sColoana==2))

{ mat.SetInactiv(p->Linie);

mat.Update(p->Coloana,p->Linie);

int rang=partitie.GetRang(p->Coloana);

partitie.AddArticol(rang,p->Linie); }

// primul este cluster, al 2 lea articol

if((sLinie==2)&&(sColoana==1))

{ mat.SetInactiv(p->Coloana);

mat.Update(p->Linie,p->Coloana);

int rang=partitie.GetRang(p->Linie);

partitie.AddArticol(rang,p->Coloana);

}

// ambele sint clustere

if((sLinie==2)&&(sColoana==2))

{

mat.SetInactiv(p->Coloana);

mat.Update(p->Linie,p->Coloana);

int rang=partitie.GetRang(p->Coloana);

partitie.SetInactiv(rang);

partitie.Update(p->Linie,p->Coloana);

}

mat.GetSim(Prim,(*Ultim),SimL);

mat.GetReductie(Prim,(*Ultim),DimC,RedL);

}

// se determina un nou interval

if((*Ultim)==NrElem)

Prim=1;else Prim=(*Ultim);

mat.GetCadru(Prim,DimC,Ultim);

mat.GetSimGlobal(SimG);

mat.GetActive(Active);

mat.GetSim(Prim,(*Ultim),SimL);

mat.GetReductie(Prim,(*Ultim),DimC,RedL);

}

Metoda GetCadru a clasei MatSimilaritate realizeaza fractionarea colectiei de articole in subcolectii avind dimensiunea specificata de utilizator.

Incremental single pass clustering

Este un algoritm de clusterizare nonierarhica, si utilizeaza o strategie opusa algoritumului precedent, care analiza intr-o anumita iteratie intreaga colectie. In cazul acestui algoritm, intr-o anumita iteratie este analizat un singur element al colectiei, denumit element activ sau element curent.Acesta poate fi absorbit de unul dintre clusterele precedente, daca se dovedeste similar centroidului acestuia, sau poate deveni primul element al unui nou cluster. Algoritmul poate fi descris prin forma generala:

Pasul :

primul element al colectie devine cluster;

centroidul primului cluster este elementul 1;

elementul doi devine element curent;

Pasul 2:

se determina similaritatea maxima dintre elementul curent si clusterele precedente;

daca valoarea similaritatii este superioara unui prag, elementul curent este absorbit de clusterul fata de care este cel mai apropiat; in caz contrar, elementul curent devine primul obiect al unui nou cluster;

Pasul 3:

se determina un nou element curent;

Pasul 4:

se reiau pasii doi si trei pina la parcurgerea intregii colectii;

Sint generate, astfel, in mod aglomerativ, clustere intre care nu exista relatii ierarhice, un cluster nefiind niciodata analizat in vederea agregarii pe un nivel superior. Elementul supus analizei este intotdeauna un articol al colectiei.

Modificarea pragului de similaritate permite obtinerea unor partitii cu grade diferite de granularitate.

Implementare

Aplicatia permite utilizatorului stabilirea anumitor parametri, cum ar fi pragul de similaritate si numarul de cuvinte dintr-un articol introduse in analiza.

Clase modelate

In vederea implementarii algoritmului au fost modelate aceleasi clase ca si pentru algoritmul GAC, respectiv Cluster, Partitie, MatSimilaritate.In cazul clasei MatSimilaritate,vor fi utilizate metode specifice.

Implementatea algoritmului se realizeaza prin secventa :

mat.SetCluster(1);

partitie.AddCluster(1);

for(int t=2;t<=NrElem;t++)

{

double *sim=new double;

mat.GetSimilarPast(p,t,sim);

if((*sim)>SimMin)

{ int stare=mat.GetStare((*p));

if(stare==1)

{

mat.SetInactiv(t);

mat.SetCluster((*p));

partitie.AddCluster((*p));

int r=partitie.GetRang((*p));

partitie.AddArticol(r,t);

mat.Update((*p),t);

};

if(stare==2)

{ mat.SetInactiv(t);

int r=partitie.GetRang((*p));

partitie.AddArticol(r,(*p));

mat.Update((*p),t);

}

}

else mat.SetActiv(t);

Identificarea evenimentelor noi

Are drept scop identificarea automata a evenimentelor noi abordate in articole de presa receptionate in flux continuu. Procesul poate fi asociat unuia de instruire supervizata, deoarece presupune utlizarea unei colectii preexistente de articole. atributul de “ nou” asociat evenimentului este exprimat tocmai prin raportare la aceasta colectie. Rezultatele procesului nu sint influentate de numarul de articole pe care aceasta le contine, ci de gradul de omogenitate pe care il prezinta.

Un grad mare de neomogenitate a colectiei folosite in analiza reduce sansele articolului de a fi etichetat drept “nou”.

Metode specifice

Algoritmul utilizat reprezinta o forma utilizata a algoritmului INCR. Modalitatile

nu se refera la strategia de analiza, ci la modificarea semnificatiei anumitor parametri. Astfel, deoarece articolul supus analizei nu a fost prelucrat in contextul mai larg al intregii colectii, nu mai este posibila specificarea unui prag de similaritate, ci a unuia de noutate. In informatiile globale ale colectiei nu se regasesc referiri la noul articol, care, de exemplu, poate contine cuvinte noi, care nu sint continute in dictionarul acesteia, generat dinamic pe baza articolelor componente. De asemenea, asupra articolului nu se realizeaza transformari care sa necesite corelarea informatiilor intrinseci- in general frecventa absoluta a cuvintelor- cu informatii globale, cum ar fi numarul de articole din colectie in care se regaseste un anumit cuvint. Toate aceste constituie motive pentru valoare prag indicata nu reprezinta un prag de similaritate, ci unul de noutate.

Implementare

Aplicatia utilizeaza o colectie de articole implicita, continuta in tabela Articole a bazei de date Articole.mdb. si permite utilizatorului stabilirea parametrilor a

algoritmului si selectarea articolului supus analizei, dupa cum se vede in fig 4.5

Fig 4.5 Identificarea articolelor noi

Numarul de parametri specificati de utilizator este mai redus, acesta neavind posibilitatea de a stabili numarul de cuvinte introduse in analiza. justificarea este aceea ca, fiind analizat un singur articol, continutul semantic al fiecarui element lexical capata o importanta sporita. In scopul cresterii ponderii elementelor lexicale semnificative sint eliminate din articolul analizat prepozitiile, conjunctiile si adverbele.

Surse de date utilizate

Aplicatia permite doua modalitati de selectare a articolului supus analizei.Acesta poate fi preluat dintr-o sursa externa si integrat in sistem utiliziind un cimp de editare sau poate fi preluat dintr-o baza de date. In ultimul caz este asigurata independenta aplicatiei fata de structura bazei de date a utilizatorului si numarul sau structura tabelelor continute de aceasta. Tabela selectata poate fi rasfoita, iar atributul introdus in analiza este selectat utilizind cereri de regasire parametrizate.

In vederea determinarii noutatii sale, articolul este supus analizei lexicale, normalizarii si sortarii.

Noutatea unui articol raportata la o colectie este determinata de valoarea maxima a noutatii acestuia fata de fiecare dintre elementele colsctiei. O valoare a noutatii superioara valorii prag va determina etichetarea articolului ca nou. In caz contrar acesta va fi indicat drept vechi. Modificarea pragului de noutate determina modificarea senzitivitatii colectiei fata de noutate. Aceasta poate fi astfel instruita in vederea sporirii “exigentei” sau :indulgentei” fata de noutate.

Utilizatorul are posibilitatea de a activa aplicarea unei penalitati temporale. Cea mai simpla modalitate de implementare presupune utilizarea unei ferestre temporale . Deoarece articolele continute in colectia etalon sint ordonate in functie de data, fereastra temporala poate fi exprimata sub forma numarului de articole pe care le contine, si nu printr-o anumita data care sa limiteze procesul de cautare.

Utilizatorul poate specifica astfel dimensiunes acesteia, indicind numarul “m” al celor mai recente articole pe care aceasta le poate contine. Se impune precizarea ca utilizarea ferestrei temporale poate afecta procesul de analiza a articolului, in sensul ca se va tinde de la stabilirea nuotatii unui eveniment catre stabilirea noutatii unei instante. Utilizind fereastra temporala, valorile noutatii unui articol fata de clusterele colectiei se modifica, putind avea una dintre expresiile:

Sim(x,c)=sim(x,c), daca cel putin un articol din c se regaseste in fereastra temporala;

Sim(x,c)= 0 daca nici un articol din c nu se regaseste in fereastra temporala;

unde c reprezinta orice cluster din colectie, iar x reprezinta articolul de analizat

sau

Sim(x,c)=(1-i/m)*Sim(x,c), dacain fereastra temporala se gesesc articole din c;

Sim(x,c)=0, daca in fereastra temporala nu se regasesc articole din c;

Notatiile au semnificatia: x articolul supus analizei;

c reprezinta orice cluster din colectie;

m este dimensiunea colectiei;

i indica numarul de articole din clusterul c continute de fereastra temporala ;

Clase modelate

Pentru implementarea algoritmului au fost utilizata clase MatSimilaritate, apelindu-se la metode specifice ale acesteia.

Utilizarea acestora in implementarea algoritmului este redata in secventa :

if(vb)

{ CString s;

m_Fereastra.GetWindowText(s);

int f=(int)(atof(s));

mat.GetSimVector(1,f,noutate);

}

else

mat.GetSimilar(1,noutate);

Rezultatele generate sint sub forma unor valori binare, respevtiv articolul este indicat drept nou sau vechi. Ca varianta alternativa, in cazul cind nu este specificat un prag de noutate care sa reprezinte baza de comparatie, se poate indica o masura a noutatii articolului exprimata sub forma :

Score(x)=1-argmax(sim(x,c));

unde x reprezinta articolul analizat, iar argmax(sim(x,c)) este valoarea maxima a noutatii acestuia in raport cu fiecare dintre clusterele c ale colectiei;

Regasirea evenimentelor in articole de presa

Are drept scop asignarea automata de etichete articolelor noi, folosind in acest sens un set de instruire de dimensiuni reduse. In termeni specifici, procesul presupune asignarea etichetei unui eveniment oricarei noi instante a acestuia.

Pentru un anumit eveniment, setul de instruire contine un numar de exemple pozitive, reprezentate de instante ale evenimentului, si exemple negative de instruire, sau contraexemple, care reprezinta instante ale altor evenimente.

Procesul de asignare a etichetelor poate fi asimilat unuia de instruire supervizata, avind ca principala caracteristica utilizarea unui numar redus de instante de instruire.

Metode specifice

Particularitatile procesului indica drept corespunzatoare doua metode :

Algoritmul de clasificare K nearest neighbor KNN

Inductia bazata pe arbori de decizie;

Algoritmul KNN a fost intens utilizat in domenii ca recunoasterea formelor sau machine learning. In regasirea evenimetelor in articole de presa este utilizat datorita proprietatii sale de a genera rezultate satisfacatoare utilizind un numar redus de instante de instruire si datorita numarului mic de restrictii pe care le impune datelor prelucrate, respectiv exprimarea acestora sub forma numerica. In acest sens , articolele au fost reprezentate sub forma unor vectori de frecvente, valorile asociate reprezentind frecventele absolute normalizate.

Algoritmul presupune existenta unor “evenimente eticheta”, pentru care exista seturi de instruire continind exemple pozitive ci contraexemple. Numarul acestora este redus, de obicei avind valorile 2, 4, 6, 8 sau, in cazuri exceptionale 16.

Analiza unui articol este realizata in doua etape, la doua nivele diferite.

Pasul 1:Articolul este analizat la nivelul setului de antrenare specific unui eveniment

Se determina similaritatea dintre articol si fiecare instanta de instruire a setului ;

Se determina gradul de corespondenta dintre articol si evenimentul respectiv;

Pasul 2: Analizarea articolului la nivelul colectiei de seturi de antrenare

Se determina valoarea maxima a corespondentei dintre articol si evenimente;

Se asigneaza eticheta unui anumit eveniment sau una implicita;

Determinarea gradului de corespondenta dintre un articol si un eveniment redat prin setul propriu de instruire este descrisa de relatia:

S(YES)=d(p,x)- d(n,x)

Unde d(p,x) reprezinta suma similaritatilor dintre articol si instantele pozitive de instruire, iar

d(n,x) reprezinta suma similaritatilor dintre articol si instantele negative de instruire.

O astfel de determinare se dovedeste eficienta cind instantele pozitive de antrenare si cele negative se gasesc intr-un numar apropiat. In realitate insa, instantele negative sint mult mai numeroase, numarul lor este mai mare decit numarul instantelor pozitive, astfel incit diferentele intre cele doua valori d(p,x), respectiv d(n,x) se datoreaza numarului diferit de exemple continute. In astfel de cazuri se impune determinarea gradului de corespondenta utilizind expresia:

S(YES)=d(p,x)/k1- d(n,x)/k2,

Unde k1 indica numarul de instante pozitive iar k2 numarul de instante negative.

Inductia bazata pe arbori de decizie

Are la baza o strategia bazata pe determinarea optimului local –greedy- si notiunea de entropie a sistemului, care descrie gradul de “dezordine”, de neomogenitate existent in sistem la un anumit moment de timp. Fiecare iteratie a algoritmului realizeaza o restructurare a colectiei de articole astfel incit sa se obtina o reductie maxima a entropiei. Optimul local se refera la determninarea reductiei maxime a entropiei. Principalele dificultati in aplicarea acestei metode sint date de definirea entropiei si forma de reprezentare a textului .

O masura a entropiei ar putea fi data de disilimaritatea maxima asociata unui forme de structurare a colectiei.

Textele supuse analizei trebuiesc reprezentate sub forma binara, ca vectori de 0 si 1 , indicind absenta/prezenta unui anumit cuvint. Aceasta reprezentare necesita existenta unei componente, numita dictionar, care sa contina un numar mare de cuvinte a caror prezenta/ absenta sa fie indicata pentru fiecare articol. Generarea dictionarului si analiza dificila aplicata fiecarui articol determina dificultati in aplicarea acestei metode.

Implementare

Aplicatia implementeaza numai prima dintre metodele prezentate.

Selectarea datelor

Seturile de instruire se regasesc in baza de date Samples.mdb, avins o structura specifica, in sensul ca numele fiecarei tabele reprezint etichete ce va fi asignata. De asemenea , structura tabelei este simpla, continind numai un atribut cheie si un cimp text continind exemplul de instruire. Delimitarea intre instantele pozitive si cele negative este realizata de o inregistrare avind valoarea “end” pentru atributul de tip text.

Aplicatia permite asignarea etichetelor in colectii de mari dimensiuni, respectiv baze de date ale utilizatorului. Selectarea atributului ce va fi analizat se facs utilizind cereri de interogare. Tabela al carui cimp a fost selectat va suferi modificari de structura, prin adaugarea unui nou cimp, numit “Label”.

Clase modelate

Implementarea algoritmului KNN a impus modelarea unei clase specifice.

class TrainingSet

{privat:

int P[10];

int N[10];

int NrPozitiv;

int NrNegativ;

public:

CString eticheta;

int GetNegativ();

int GetPozitiv();

int GetCodP(int);

int GetCodN(int);

void SetP(int);

void SetN(int);

void SetEticheta(CString);

TrainingSet();

virtual ~TrainingSet();};

Aceasta incapsuleaza atributele unui anumit set de instruire.

Prin utilizarea acestei clase , algoritmul KNN este redat de secventa urmatoare :

for(int col=1;col<=n;col++)

{ double *sim=new double;

Colectie.GetSimilaritate(pArticol,col,sim);

mat.SetSimilar((*sim),1,col);

};

double *Yes;

Yes=new double[DimSet];

for(int c=1;c<=DimSet;c++)

{ int Np=Set[c].GetPozitiv();

int Nn=Set[c].GetNegativ();

double Sp=0;

for(int ip=1;ip<=Np;ip++)

{

double var;

int poz=Set[c].GetCodP(ip);

var=mat.GetSPunct(1,poz);

Sp+=var;

};

double Sn=0;

for(int in=1;in<=Nn;in++)

{double var;

int poz=Set[c].GetCodN(in);

var=mat.GetSPunct(1,poz);

Sn+=var;

};

double yes=(Sp/Np)+(Sn/Nn);

Yes[c]=yes};

int vPoz=1;

double max=Yes[1];

for(int m=2;m<=DimSet;m++)

if(Yes[m]>max)

{ vPoz=m;

max=Yes[m];

};

Rezultatele se regasesc in tabele utilizator, de unde pot fi ulterior vizualizate.

Vizualizarea rezultatelor

Se realizeaza ditferit, pentru fiecare din cele trei activitati principale realizate .

In cazul metodelor care genereaza partitii ale colectiei, este posibila analiza partitiei generate. Se realizeaza traversari ale clusterelor generate,ca si parcurgerea intregii partitii. Pentru un cluster este specificat identificatorul sau, cetroidul si sint regasite articolele continute.

Fig 4.6 Vizualizare partitie

In cazul identificarii evenimentelor noi, rezultatul este vizualizat direct.

Pentru regasirea evenimentelor in articole de presa vizualizarea permite parcurgerea tabelei utilizator, evidentiind modificarea structurala si etichetele atasate.

Fig 4.7 Vizualizare etichete

Concluzii

Aplicatia realizata a avut drept scop studierea unor algoritmi destinati detectarii se regasirii evenimentelor in articole de presa, utilizind texte exprimate in limba romana. Integrarea algoritmilor a fost realizata in cadrul unui proces de text mining. Datele de intrare au fost reprezentate de o colectie de articole, preluate din surse diferite pentru asigurarea neomogenitatii, abordind in principal 6 evenimente principale: Alegeri electorale, Vizita Suveranului Pontif in Ramania, Seisme, Crah financiar,Poluarea mediului inconjurator. Evenimentele au fost selectate astfel incit sa apartina unor domenii cit mai variate. Colectia contine, de asemenea, si articole care nu contin instante ale evenimentelor mentionate.

Din studierea algoritmilor s-a dedus in primul rind o dependenta senzitiva a acestora fata de anumiti parametri. Contrar asteptarilor, cea mai semnificativa influenta asupra performantelor acestora a fost determinata de numarul de cuvinte dintr-un text introdus in analiza. Astfel valori de 25-30 de cuvinte conduc la generarea unei matrice de similaritate avind valori cuprinse intre 0.002-0.007 in timp ce utilizarea a 100 de cuvinte in analiza genereaza valori ale similaritatilor in intervalul 0.1-1.

Utilizarea listei de cuvinte cu continut semantic redus a adus imbunatatiri minore ale rezultatelor.

Pentru identificarea articolelor in colectii de date, algoritmul GAC dovedeste performante superioare algoritmului INCR.

Detectarea evenimentelor noi si regasirea evenimentelor s-au dovedit mai dificile, cel putin prin prisma metodelor implementate.

Parametrii care sa permita un comportament corespunzator al algoritmilor s-ar putea dovedi specifici unui anumit set de articole prelucrat. Odata stabiliti, insa ar putea conduce la concretizari ale potentialului urias al acestora, obtinundu-se astfel un instrument extrem de util in realizarea analizelor sociale.

Bibliografie :

Fionn Murtagh , Andre Heck , Multivariate data analysis , Dr Reidel Publishing Company,Amsterdam 1997

http://www.semio.com/

http://www.software.ibm.com/

http://www.sciam.com/
http://www.infoworld.com/

http://www.megaputer.com/

http://www.datajunction.com/

http://www.autonomy.com/

http://ds-dataset.com

http://www.infonautics.com

http://www.db2mag.com