Data minig

Data minig

-referat-

"In ultimii zece ani asistam la o crestere exploziva a capacitatii noastre de a genera si colecta date. Progresele realizate in colectarea datelor, raspandirea utilizarii codurilor bara pentru majoritatea produselor comerciale si computerizarea majorit atii tranzactiilor de afaceri si guvernamentale ne-au inundat cu informatii" 3. Se discuta din ce in ce mai mult despre oceanul de date, care in literatura de specialitate se numeste "ubiquitous". Acest termen nu are o traducere exacta si nici o semnificatie foarte precisa. El se refera la datele care urmaresc in mod aproape invizibil viata de zi cu zi a omului modern. Originile acestor date sunt diferite, iar existenta lor, aproape insesizab ila cu ochiul liber. Ele provin din cele mai diverse surse, de la dispozitivele cele mai simple, cum ar fi, masinile de spalat cu program, cuptoarele cu microunde, telefoanele digitale, automatele de eliberat numerar, si pana la baze de date complexe, le gate de evidenta populatiei, sanatate, circulatie etc.

Aceste cantitati mari de date se memoreaza in depozite sau antrepozite de date, numite si data warehouse, utilizand tehnici speciale, denumite OLTP, OLAP etc.

In ultimul timp, aparitia Internetului a dus la o crestere exponentiala a informatiilor. Practic, este foarte greu de imaginat cantitatea de informatii vehiculata intre cele 13.000.000 de calculatoare, cate se apreciaza a cuprinde in acest moment Internetul. Se apreciaza ca in 1995, in Internet erau peste 2.000.000 de servere situate in peste 1500 de noduri. Daca tinem seama ca numarul calculatoarelor legate in Internet se dubleaza in fiecare an, ne putem da seama usor de uriasul volum de date care se ascunde in spatele lui.

Excavarea cunostintelor

". informatiile numerice se capteaza simplu si practic se memoreaza ieftin. Dar ce poate face lumea cu atat de multe date?".

Pentru luarea unor decizii, asa dupa cum s-a vazut mai sus, omul are nevoie de cunostinte. Se pune deci problema cum se pot analiza datele si cum se pot extrage cunostintele necesare din ele?

Daca datele sunt relativ putine, analiza se poate realiza simplu, manual, de catre specialisti din diferite domenii sau statisticieni. Pe acestia, unii autori ii numesc "mineri" sau "excavatori manuali de date". Ce ne facem insa in situatia in care avem "munti" de date? Cat de mare poate fi azi o baza de date dintr-o aplicatie oarecare? Un raspuns poate fi gasit in caseta "Studiu de caz 1: Observatorul astronomic Palomar II".

Bine, bine, pot spune scepticii, astronomia este un exemplu de utilizare exhaustiva a datelor. In alte domenii volumul datelor este mult mai mic. Sa ne gandim, de exemplu, la o clinica. Aici sunt mii de bolnavi, care au fiecare un volum considerabil de date ce rezulta din istoricul bolii, analize de laborator, imagini captate cu ecografe, angiografe nucleare etc. Considerand pentru o imagine numai 500 Ko, faceti un calcul sa vedeti cam ce volum ocupa aceste date. Situatia este si mai pregnanta in domeniul afacerilor. Astfel, un studiu realizat de META Grup in 1995 arata ca peste 19% din depozitele de date au peste 50 Giga baiti, iar in domeniul vanzarilor cu amanuntul, volumele vor fi mult mai mari.Deci, evident ca pentru astfel de volume de date amorfe, sunt necesare instrumente speciale pentru extragerea cunostintelor. Nu este de mirare ca s-a nascut o noua disciplina pe care cei mai multi o denumesc Data Mining (DM), altii o denumesc Knowledge Discovery (KD), altii Knowledge Discovery in Databases (KDD), altii Information Discovery (ID), altii Information Archeology (IA) etc. Fiecare denumire poate fi justificata in felul ei. Trebuie subliniat insa ca unii autori fac deosebire intre unele din tre acestea, de exemplu intre DM si KDD sau KD.

Ce este deci DM? Numarul definitiilor fiind foarte mare, vom alege doar doua, care ni se par mai simple si sugestive. "DM este extragerea informatiilor predictive ascunse din bazele mari de date", sau "torturarea datelor pana cand acestea se confeseaza" .

Componentele DM si KDD

Functia principala a DM este, deci, de a extrage modele de cunostinte din date. Pentru aceasta, DM utilizeaza o varietate de algoritmi din statistica, recunoasterea formelor, clasificare, logica fuzzy, machine learning, algoritmi genetici, retele neuron ale, vizualizarea datelor, etc. Varietatea de algoritmi poate fi grupata in principalele componente ale DM. Numarul acestor componente difera de la un autor la altul. Astfel, unii considera ca DM are 3 componente, altii, 4, etc. Noi consideram ca princip alele componente ale DM sunt:

• modelul - care, ca orice model informatic, se reprezinta printr-o functie intr-un spatiu unidimensional sau multidimensional (un ansamblu de functii), depinzand de parametri. El poate fi reprezentat fie ca o functie liniara de parametri, fie ca o functie de prob abilitate (de exemplu normala), fie ca o functie fuzzy, etc. Obtinerea modelului se realizeaza prin diferiti algoritmi, cum ar fi cei de clasificare si clusterizare;
• criteriile de preferinta - care pot fi de natura diferita, unele dintre acestea bazandu-se pe ordonare, altele pe interpolare sau cea mai buna aproximare;
• algoritmi de selectie - care conduc la selectarea a trei elemente importante care apar in DM, si anume: modelul, care se selecteaza din baza de modele, datele, care se selecteaza din baza de date si constituie parametri, si criteriul sau criteriile de preferinte, care se sele cteaza din baza de criterii;
• stabilirea abaterilor - care consta in general in algoritmi de determinare a deviatiei si stabilitatii; o categorie specifica de astfel de algoritmi sunt cei statistici, prin care se stabilesc abaterile modelului fata de ideal.

Bineinteles ca fiecare produs comercial utilizeaza mai multi algoritmi si in fiecare dintre ei se regasesc o parte sau toate componentele de mai sus in diferite proportii.

Autorii care fac deosebire intre DM si KDD considera KDD ca fiind un proces iterativ si interactiv complex, care include DM. Astfel, in cadrul KDD se considera ca extragerea cunostintelor se realizeaza in urmatorii pasi:

• invatarea domeniului aplicatiei - care consta in achizitia unor cunostinte despre starea initiala, precum si despre scopul aplicatiei;
• stabilirea setului de date - caruia i se va aplica procesul de extragere a cunostintelor; majoritatea autorilor atrag atentia asupra acestei faze, numite si faza de preprocesare;
• curatirea si selectarea datelor - care este un proces complex, specific depozitelor de date, in cadrul caruia se inlatura zgomotele, se reduc dimensiunile, se stabileste modul de inlocuire a datelor care lipsesc, etc.;
• aplicarea procedurilor de DM - care este de fapt pasul cel mai important al procesului KDD;
• interpretarea rezultatelor din punct de vedere al utilizatorului - care este o faza de decizie; daca acesta nu este multumit de rezultat, poate relua oricare dintre fazele precedente;
• utilizarea cunostintelor descoperite - care este faza finala; aceasta utilizare se realizeaza fie prin includerea lor in sisteme integrate de cunostinte fie, pur si simplu, prin rapoarte simple adresate celor interesati.

Este evident ca aceia care considera KD sau KDD sinonime cu DM, considera ca aceste faze sunt faze ale DM.

Stadiul actual al DM

Majoritatea autorilor sunt de parere ca stadiul actual al DM este cel de "arta".

Desi fisierele si bazele de date mari sunt bine cunoscute de mult timp, se poate considera ca primele investigatii in DM au inceput la sfarsitul anilor 80. Astfel, primele ateliere de lucru (workshop-uri) au avut loc in 1989, 1991, 1993 si 1994. De altfe l, rezultatele atelierului din 1994, completate si sistematizate, au fost introduse in cartea editata de U.M.Fayyad si altii3. Incepand din 1995, atelierele de lucru s-au transformat in conferinte anuale. Astfel, prima conferinta anuala a avut loc la Pa lais Des Congres din Montreal, Canada, in 20-21 august 1995. A doua conferinta anuala a avut loc la Portland, Oregon, SUA, in 2-4 august 1996 si s-a bucurat de un succes enorm, participand peste 500 de persoane. Principalele rezultate ale acestei conferinte au fost prezentate intr-un numar special al prestigioasei reviste Communications of ACM vol. 39, nr. 11, November, 1996. In sfarsit, in 1997 va avea loc cea de a treia confe rinta in domeniul DM si KDD, la Newport Beach, California, in perioada 14-17 August 1997. De altfel, in 1997 vor avea loc cel putin 11 manifestari de importanta majora in acest domeniu (vezi caseta "Data Mining si KDD: reuniuni majore in 1997").

In 1997 este anuntata aparitia primului numar al unei reviste destinate acestui domeniu, intitulata Data Mining and Knowledge Discovery. Ea se va adauga unei alte reviste gratuite pe Internet, KDD Nugget, care incepand din 1993 a reusit sa apara in 108 numere. Un site excelent, in care se poate gasi aceasta revista precum si multe alte informatii legate de DM si KDD, este cel al GTE, intretinut de Gregory Piatetsky-Shapiro de la GTE si de Michael Bedows de la Boston University. Numarul articolelor care se scriu despre acest domeniu este impresionant. Astfel, reviste de informatica cu o mare circulatie, ca Datamation, BYTE, LAN Magazine, alaturi de reviste cu o reputatie stiintifica deosebita, consacra numere sau sectiuni speciale domeniului. Alte reviste, cum ar fi Journal of Intelligent Information Systems (JIIS-Kluwer), Machine Learning, Intelligent Data Analysis (Elsevier), contin un numar insemnat de articole din acest domeniu. Alaturi de s iturile prezentate anterior, alte situri interesante unde pot fi gasite informatii legate de astfel de articole, white paper-uri etc., sunt in lista lui Michael Ley, in situl lui Thierry Van de Merckt sau in cel al lui Andy Prike.

Starea actuala a DM si KDD se datoreaza insa si faptului ca, spre deosebire de alte dezvoltari ale informaticii, cum au fost Internetul, obiectualitatea, retelele neuronale, algoritmii genetici, etc., care au pornit de la lumea academica, fiind ulterior preluata de cea a afacerilor, in cazul DM s-a intamplat invers, a pornit de la firmele puternice, cum sunt IBM, Microsoft, GTE, etc., lumea academica sesizand ulterior problema.

Cine sunt deci principalii producatori de DM si KDD? Desigur ca este dificil de trecut in revista pe toti si toate produsele intr-un domeniu atat de dinamic. Nici nu ne propunem acest lucru, doritorii putand gasi acestea in situl GTE15. Conform celor pr ezentate de autorii sitului respectiv, azi se naste o noua categorie de instrumente specifice DM, categorie denumita de acestia SITWARE.

Vom prezenta deci doar cateva exemple de producatori si domenii de utilizare. Poate cel mai semnificativ exemplu in domeniu este cazul IBM (caseta "Studiu de caz 2: IBM").

Alte firme mai interesante ar putea fi considerate:

HMC, care in toamna anului 1995 a elaborat o solutie mixta hard-soft, Marksman, la un pret de 48.000$. Produsul are facilitati de modelare predictiva pentru analiza bazelor de date destinate marketingului direct;

Information Discovery, care a introdus in acelasi an produsul MAP Discovery, ce utilizeaza combinatii intre statistica, inductie si algoritmi de construire a clusterelor si claselor; MAP Discovery ruleaza pe servere Sun UltraSPARC si HP9000;

Angoss Software din Toronto, care a lansat un produs DM, KnowledgeSeeker; ea a incheiat o intelegere cu firma Cognos pentru a include KnowledgeSeeker in produsul acesteia de EIS (Executive Information System).

Alte firme care se afirma in acest domeniu sunt DataMind, Thinking Machines, etc.

Poate si mai interesant decat de a trece in revista producatorii si produsele este sa prezentam putin piata DM. "DM este o piata instabila si nematurizata. Avem de perfectat tehnologia si sa o intelegem prin analize de afaceri. Dar trebuie supravietui t. Daca nu-l utilizezi in scopuri previzionale inaintea competitorilor tai, vei muri" spune directorul pentru tehnologii avansate a Gartner Group din Paris, citat in articolul din Datamation. In Figura 1, este redata segmentarea pietei DM, conform aceluiasi articol.

Legatura dintre DM si alte domenii ale informaticii

DM si KDD sunt foarte legate de o serie de domenii noi ale informaticii. Nu ne punem problema de a prezenta toate aceste legaturi. Subliniem, insa, ca cele mai apropiate domenii de DM si KDD sunt OLAP (On Line Analitic Processing) si DSS (Decision Suppo rt Systems). Avand in vedere faptul ca intentionam sa abordam tema OLAP si DSS intr-un articol viitor, nu vom intra acum in amanunte legate de aceste domenii. Exista multe prezentari, mai mult sau mai putin complete, despre ceea ce este OLAP si DSS. Con form acestora, OLAP este un mod de utilizare a depozitelor de date, utilizare care presupune pe de o parte un acces in timp real (OLTP - On Line Transactional Processing), iar pe de alta parte, o analiza multidimensionala (vectoriala) a bazelor de date mari. DSS este un ansamblu format din baze si depozite de date, precum si alte ansambluri de informatii utile, impreuna cu produse soft adecvate intocmirii rapoartelor, analizei datelor, precum si implementarii unor algoritmi de optimizare in vederea sprijinirii actului decizional al oamenilor de afaceri. Aceste doua domenii fiind foarte apropiate de DM, determina o serie de furnizori de OLAP sau DSS sa sustina ca livreaza DM. "Dand o interpretare slaba notiunii de Data Mining, vanzatorii OLAP pot spune ca se ocupa de DM" afirma Steve Smith, director de analize avansate la Pilot Software. "Una dintre liniile de demarcare clara dintre cele doua 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 in favoarea DSS. OLAP si DSS utilizeaza mai putini algoritmi si depind de cererile si ipotezele livrate de utilizator. In ceea ce priveste raspunsurile, diferenta dintre OLAP si DSS, pe de o parte, si DM si KDD, pe de alta par te, se poate asemana cu cea dintre raspunsurile date de o baza de date si una de cunostinte. Astfel, de exemplu, un mod tipic de a pune o intrebare in OLAP si DSS este: "Au cumparat persoanele din Cluj mai multe masini decat cele din Brasov in ultimul an?". Raspunsul OLAP si DSS este de forma: "Populatia din Cluj a cumparat 12.000 de masini, in timp ce in aceeasi perioada, cea din Brasov a cumparat 10.000". Acest raspuns este deci clar, dar se limiteaza la ipoteze, deci este rigid. Raspunsurile din DM si KDD sunt mult mai flexibile. In cazul lor, intrebarile se pun sub forma: "Da-mi un model care identifica caracteristica cea mai previzibila a populatiei care va cumpara masini" . Invatand din experienta trecuta, DM va raspunde sub forma: "Depinde de an si zona geografica. Astfel, de exemplu, populatia din Cluj a cumparat anul trecut mai multe masini (12.000) fata de cea din Brasov (10.000)". Avantajul este ca DM si KDD pot descoperi raspunsuri mai sofisticate si subtile, pe care OLAP si DSS nu le pot detecta.

Exista si multe alte diferente, dintre care cea mai importanta este modul de rationare. Astfel, rationarea in sistemele OLAP si DSS este deductiva, in timp ce in DM si KDD este inductiva.

Pe de alta parte, trebuie subliniat ca diferentele dintre DM, OLAP si DSS au tendinta sa dispara. Algoritmii si facilitatile DM au inceput sa fie incluse in produsele DSS si OLAP. De exemplu, AT&T, care este un mare utilizator si furnizor de OLAP, a in ceput sa lucreze la un produs DM, numit Nearest Neighbor System, care clasifica uti lizatorii sai dupa similaritati. La randul lor, si furnizorii de DSS au sisteme specifice de vizualizare a bazelor de date, deci includerea unor functionalitati de DM este o optiune normala a lor. Nu este deci de mirare ca marii furnizori de OLAP si DSS, cum sunt Pilot si Comshare, s-au orientat rapid catre DM.

Unul dintre domeniile preferate de utilizare a DM, de catre producatorii de DSS si OLAP este valorificarea Internetului. Acest fapt este normal, avand in vedere caracterul eterogen al bazelor si depozitelor de date in acest caz. Astfel, de exemplu, Arbo r Software a introdus un gateway Web la un pret de 10.000 de dolari, gateway care este un site intre serverul Web si o baza de date OLAP multidimensionala de tip Essbase a companiei. Produsul asigura citirea si scrierea usoara a analizei informatiilor de afaceri furnizate de browserul Web, ceea ce va usura raspandirea ei pe piata DSS, OLAP si DM.

In loc de concluzie

In ultimii ani, informatica a surprins omenirea, ca de atatea ori pana acum, printr-o serie de rezultate noi si inedite, cum au fost: aparitia si extinderea Internetului sub forma World Wide Web la scara planetara, aparitia tehnologiei agentilor intelig enti, a algoritmilor genetici, a depozitelor de date, a sistemelor fuzzy etc. Toate acestea au pornit insa de la lumea academica, fiind urgent preluate de cea a afacerilor. Asa cum am mai subliniat, DM si KDD au pornit invers, de la necesitatile de aface ri, mai exact, de la necesitatea extragerii cunostintelor din imensitatea de date in mijlocul careia se afla omul modern. Nu este de mirare deci ca firmele mari, cum sunt IBM, Microsoft, GTE etc., si-au format grupuri proprii de cercetare sau au format g rupuri de cercetare cu universitati puternice ca MIT, Stanford, Rutgers, Santafe etc. pe acest domeniu. Nu trebuie sa ne surprinda nici numarul mare de intalniri, conferinte, ateliere de lucru, grupuri de interes etc., in care se investesc acum sume mari de bani. Asa dupa cum am mai amintit, piata este in formare, domeniul in stare de arta, primele rezultate apar greu, deoarece aici este vorba de un domeniu multi si pluri disciplinar, dar lumea afacerilor simte ca este vorba de un avantaj strategic, iar cea a informaticii, ca poate pentru ea se deschide o noua era.

Studiu de caz 1

Observatorul astronomic Palomar II

Observatorul astronomic nr.2, de la Palomar (SUA-POSSII), a efectuat timp de sase ani, mai mult de 3000 de fotografii la rezolutia de 16 biti/pixel, fiecare fotografie avand 23.040 x 23.040 pixeli. S-au urmarit 2 miliarde de obiecte ceresti, fiecare obie ct avand masurate 40 de atribute, stabilite de astronomi. In felul acesta a rezultat o baza de date de 3 tera baiti. Problema fundamentala era de a clasifica aceste obiecte in corpuri ceresti si galaxii. Acest lucru evident nu era posibil sa se realizeze manual, asa ca s-a elaborat un instrument special, numit Sky Image Cataloging and Analysis Tool (SKI-CAT).

Studiu de caz 2

IBM

IBM - este de departe lider in domeniul depozitelor de date, OLAP si sistemelor expert destinate bazelor de date. Cifra sa de afaceri in acest domeniu se ridica la aproximativ 1 miliard de dolari anual si zilnic 20 milioane de utilizatori folosesc DB2 si IMS. Ele sunt implementate sub AIX, HP-UX, Solaris, OS/2 si mai nou Windows NT. De curand, acestea sunt implementate si pe calculatoare non-IBM.

In luna aprilie 1996, IBM a introdus un pachet DM numit The Inteligent Miner, care este un toolkit ce utilizeaza modelarea predictiva, segmentarea bazelor de date si analiza conexiunilor. Date legate de conceptia IBM pot fi obtinute din raportul tehnic a l Claudiei Gardner11. Pachetul DM include un toolkit, aplicatii si servicii cu 8 algoritmi avansati si 18 functii de preprocesare integrate (CAPI) intr-o interfata de programare care face partile interschimbabile. El poate opera pe Inteligent Data Server -ul IBM. Testul beta al toolkit-ului, precum si al aplicatiilor legate de acesta, a inceput sa poata fi utilizat in aprilie 1996 pe servere AIX precum si pe clienti AIX si Windows; versiunea finala a aparut in iulie 1996. Pretul de vanzare este intre 40. 000-50.000$. Lucreaza, deocamdata limitat, numai cu baze de date de tip DB2. Evident ca multi utilizatori ar dori folosirea lui si pe alte platforme. IBM a promis extinderea in acest an si pe alte platforme IBM, precum si non-IBM.