Implementarea Unor Algoritmi Pentru Generarea de Cunostinte
Cuprins:
=== Fundamentarea teoretica ===
Cuprins:
CAPITOLUL 1. INTRODUCERE
1.1. Ce este Data Mining?
Data mining este un instrument modern și puternic al TI&C (Tehnologia Informației și Comunicațiilor), instrument ce poate fi folosit pentru extragerea unor informații utile dar încă necunoscute. Acest instrument automatizează procesul de descoperire a unor relații și combinații în datele brute, iar rezultatele găsite ar putea fi încadrate într-un sistem automat de suport al deciziei. [med07]
Pentru început să considerăm tranzacții (coșuri de cumpărături) obținute de la un magazin. Aceasta implică extragerea valorilor atributelor (bunurile cumpărate de un client) pentru fiecare tranzacție, separate prin virgulă. Secvențe de interes din trei tranzacții sunt prezentate mai jos.
lapte Smith, pâine Sunshine, zahăr GIS;
lapte Pauls, pâine Franklin, biscuit Sunshine;
lapte Yeung, pâine B&G, ciocolată Sunshine;
Primul client a cumpărat lapte Smith, pâine Sunshine și zahăr GIS; ș.a.m.d. .Fiecare dată (element) este formată din produs și marcă. De exemplu “lapte Smith” este format din produsul “lapte” și marca “Smith”.
În trecut cele mai experimentate persoane de decizie ale magazinului extrăgeau șabloane cum ar fi “când un client cumpără lapte el/ea cumpără și pâine” (folositor pentru a prezice comportamentul clientului) și “clienții preferă să cumpere produse Sunshine” (folositor pentru a estima vânzările unui produs nou). Aceste persoane de decizie ar putea necesita ani de cunoaștere generală și cunoaștere despre anumite asocieri pentru a face selecții eficiente asupra datelor.
Data mining poate fi folosit pentru a descoperi informația utilă din date de forma “când un client cumpără lapte el/ea cumpără și pâine” și “clienții preferă să cumpere produse Sunshine”.
Strict vorbind, data mining este un proces de descoperire a informațiilor valoroase din cantități mari de date stocate în baze de date, arhive de date sau alte forme de stocare a informațiilor. Aceste informații valoroase pot fi șabloane, asocieri, modificări, anomalii și structuri semnificative. Cu alte cuvinte, data mining încearcă să extragă cunoștințe potențial utile dintr-o cantitate de date.
Data mining diferă de statistica tradițională în aceea că inferența statistică formală este bazată pe presupuneri, în sensul că întâi se formulează o ipoteză, iar apoi, pentru validare, se verifică datele existente. Data mining, în contrast, se bazează pe descoperire, în sensul că șabloanele și ipotezele sunt extrase direct din date. Cu alte cuvinte data minig se bazează pe date în timp ce statistica se bazează pe capacitățile umane.
Unul din domeniile importante din data mining este extragerea regulilor de asociere. Încă de la începuturile sale acest domeniu a primit o atenție sporită. Extragerea regulilor de asociere a fost dezvoltată în principal pentru a identifica acele relații puternic asociate între seturile de elemente care apar frecvent și sunt puternic corelate. Regulile de asociere ne permit să detectăm elementele care apar frecvent împreună în cadrul unei aplicații.[Zha02]
1.2. De ce avem nevoie de data mining?
Există două motive principale pentru care data mining este necesar.
1 – Sarcina de a găsi șabloanele cu adevărat utile așa cum a fost prezentată anterior poate fi descurajantă pentru mai puțin experimentate persoane de decizie datorită faptului că posibilele șabloane în cazul celor trei tranzacții nu sunt de obicei aparente.
2 – Cantitatea de date în majoritatea aplicațiilor este mult prea mare pentru analiză manuală.
În primul rând, persoanele de decizie mai experimantate sunt capabile să rezume datele de forma “lapte Smith, lapte Pauls, lapte Yeung” în “lapte” și “pâine B&G, pâine Franklin, pâine Sunshine” în “pâine” pentru șablonul “când un client cumpără lapte el/ea cumpără și pâine”. În acest fel, datele din secțiunea anterioară pot fi înlocuite cu:
lapte, pâine, zahăr
lapte, pâine, biscuiți
lapte, pâine, ciocolată
După aceasta o posibilă asociere devine clară. De asemenea informația de forma “lapte Smith” este împărțită în “lapte” și “Smith” pentru șablonul “clienților preferă să cumpere produse Sunshine” în vederea prezicerii vânzărilor unui nou produs. O secvență de porțiuni din informația anterioară este:
Smith, Sunshine, GIS
Pauls, Franklin, Sunshine
Yeung, B&G, Sunshine
În acest fel se poate extrage șablonul “clineții preferă să cumpere produse Sunshine”.
Mai există și alte șabloane utile, cum sunt asocierile negative și cauzalitatea, care sunt ascunse în informație. Chiar și persoanele cu experiență de decizie experimentate pot găsi această sarcină extrem de dificilă datorită cantității de informație mult prea mari pentru a fi analizată manual. Data mining este folosit pentru a dezvolta tehnici si unelte de asistare a persoanelor de decizie, experimentate sau neexperimentate, în munca de analiză și procesare a informației.
Pe de altă parte, dorința de îmbunătățire a profitabilității comerciale are ca efect creșterea timpului pe care companiile îl acordă identificării posibilităților de vânzări și investiții. Cantități imense de informație sunt stocate în bazele de date pentru scopuri decizionale. Pentru o perspectivă mai bună asupra situației vom da câteva exemple:
Sistemul NASA de observare a Pamantului (Earth Observing System – EOS), cu care sunt dotați sateliții de pe orbită, și alte instrumente spațiale transmit zilnic un terabyte de informație către stațiile receptoare.
În anul 2000 o companie de top avea nevoie de un spațiu de stocare a datelor de 400 terabytes.
Prin folosirea crescândă a bazelor de date, nevoia de a putea manipula cantitățile mari de date generate, este astăzi critică. Este estimat că doar 5-10% din bazele de date comerciale au fost analizate până în prezent. Așa cum arătau Massey și Newing tehnologia cu baze de date a reușit în a înregistra și manipula informația, dar a eșuat în a transforma această informație într-o armă strategică cheie pentru îmbunătățirea performanțelor afacerilor. Capacitatea și dimensiunile mari ale bazelor de date duc la imposibilitatea analizării umane tradiționale.
Data mining încorporează tehnologii de analizare a informației din bazele de date foarte mari și poate identifica potențiale șabloane utile în cadrul informației. De asemenea, data mining a devenit foarte important în industria informațională, datorită disponibilității mari de cantități imense de date în format electronic și a nevoii iminente de a transforma aceste date în informație utilă și cunoștințe pentru diverse aplicații incluzând studii de piață, managementul afacerilor și suport pentru decizii.[Zha02]
1.3. Descoperirea de cunoștințe în bazele de date
Noțiunea de data mining mai este cunoscută și ca “descoperirea cunoștințelor în baze de date”, cu toate că unii cercetători consideră procesul de data mining ca o etapă importantă în descoperirea cunoștințelor.
Descoperirea cunoștințelor ca proces este constituit din secvențe iterative ale următorilor pași:
curățarea datelor (pentru a înlătura datele irelevante);
integrarea datelor (unde mai multe surse de date pot fi combinate);
selecția datelor (unde datele relevante sarcinilor de analiză sunt extrase din bazele de date);
transformarea datelor (unde datele sunt transformate sau consolidate în forme apropiate pentru următorul stadiu);
analiza datelor (un proces esențial unde metode inteligente sunt aplicate în vederea extragerii de structuri, modele de date)
evaluarea structurilor, modelelor (pentru a identifica modelele interesante reprezentând cunoștințe);
prezentarea cunoștințelor (unde sunt folosite tehnici de vizualizarea și reprezentare a cunoștințelor într-un format accesibil utilizatorului).[Zah05]
1.4. Domenii de aplicare
Data mining se aplică asupra unei mari categorii de date structurate în diverse moduri, cum ar fi: baze de date relaționale, depozite de date, baze de date tranzacționale (unde fiecare înregistrare reprezintă o tranzacție), sisteme de baze de date avansate (unde se includ date multimedia și hypertext, WWW ș.a.). Prin urmare, aria de aplicații a acestei tehnologii informaționale este foarte largă: de la afaceri, medicină, știință, inginerie până la jocuri, media, lumi virtuale și sateliți.
Data mining poate fi integrat cu succes asupra domeniului economic, distingându-se două tipuri de arii de aplicații: aplicații specifice serviciilor și producției industriale și aplicații restrânse asupra unor ramuri. În cadrul unor întreprinderi, data mining se poate aplica asupra unor departamente diverse, rezultatele fiind de mult ajutor conducerii de la toate nivelurile.
Marketingul se pretează foarte bine acestei tehnologii prin activitățile întreprinse în acest departament cu referire la: statistici, prezicerea comportamentului grupurilor, identificarea preferințelor, lansarea de campanii de marketing, publicitate în media etc. Toate acestea necesită analiza unor variabile. Instrumentele data mining oferă posibilitatea luării în calcul a sute de variabile, ca de exexmplu informațiile demografice cuplate cu un istoric al cumpărărilor etc. O altă problemă cu care se confruntă marile companii este cea a pierderii clienților. Cu ajutorul noii tehnologii se pot identifica și izola caracteristicile clienților care arată neloialitatea acestora față de produs sau serviciu. În acest mod, costurile rezolvării acestei probleme scad foarte mult, managementul având în permanență la dispoziție informațiile necesare elaborării politicilor de păstrare a clienților și de atragere a altor clienți. Alte aplicații data mining se concentrează asupra descoperirii modelelor care să ajute departamentului de marketing în luarea deciziilor.
Activitatea de control este de asemenea un domeniu care oferă o bază de aplicare a proceselor data mining. Din cauza multitudinii de obiecte la care se referă controlul (produse, clienți, canale de distribuție, regiuni etc.) precum și a aspectelor relevante rezultate din această activitate, sunt necesare metode care sa analizeze automat volumul mare de date – data mining. Modelele rezultate sunt de regulă o combinare a anumitor atribute și indicatori. De exemplu, un rezultat interesant ar fi acela că rata profitului (indicator) unui anumit grup de articole (atribute) este regulat constant foarte mare. Domeniul costurilor este de asemenea pretabil analizei de tip data mining. Aici interesează în mod special identificarea trendurilor pincipalilor indicatori ai afacerii (profit, prețuri, costuri de productii, contribuția marginală etc)
Rezultatele oferite de aplicațiile data mining în producție conducerii pot lua forma răspunsurilor la întrebări privind capacitatea de utilizare a unor utilaje folosite într-o anumită ordine, descoperirea unor întrerupei necunoscute în procesul producției, descoperirea unor dependențe necunoscute între calitatea produsului și procesul de producție.
Un alt domeniu este cel al auditului intern și extern. Capacitatea sistemelor Data mining de identificare automată de șabloane oferă noi posibilități permite organelor de control în descoperirea fraudelor. De exemplu, o companie de telefoane se poate folosi de data mining, prin identificarea unor șabloane neobișnuite, pentru a descoperi fraudele privind clonarea de celulare. daca un client începe dintr-odată să telefoneze într-un mod cu totul aparte, compania este alertată în mod automat.
Data mining oferă avantaje deosebite băncilor datorită capacității sale de previziune financiară, de control, de evaluare a gradului de risc al acordării de credite. Câteva din avantajele folosirii sistemului în activitatea bancară sunt prezentate în continuare: identifică modele de fraudă a utilizării de card-uri, identifică clienții lodiali, prezice comportamentul clienților de card-uri, oferă informații referitoare la cheltuielile unor anumite grupuri de clienți, descoperă corelații ascunse între diferiți indicatori financiari etc. Nu în ultimul rând, informațiile oferite de către data mining pot fi utilizate în acordarea de credite.
Asigurările pot beneficia și ele de pe urma folosirii sistemelor data mining pentru a previziona ce clienți vor cumpăra noi polițe sau pentru a identifica modele în comportamentul clienților cu risc mărit sau pentru a preveni fraudele.
Data mining are aplicație și în medicină, de exemplu, pentru a caracteriza comportamentul pacientului sau pentru a identifica terapii de succes pentru diverse boli.[Zah05]
1.5. Tema proiectului și obiectivele vizate
Pe fundalul situației actuale de creștere a capacității de stocare a datelor, extragerea informațiilor cu adevărat utile, referite prin termenul de cunoștințe, devine atât o necesitate cât și un avantaj major. Totodată procesul de extragere a cunoștințelor devine anevois și consumator de timp datorită cantității imense de date acumulate. Evoluția tehnologică însă, permite dezvoltarea unor aplicații automatizate care să înlocuiască factorul uman în procesul de extragere a acestor informații.
Proiectul de față are ca scop realizarea unei aplicații de implementare a unor algoritmi de generare de cunoștințe având la bază un studiu privind conceptele de data mining, reguli de asociere și seturi frecvente de elemente.
Partea teoretică a proiectului urmărește clarificarea noțiunilor de reguli de asociere și seturi frecvente de elemente, privite ca și cunoștințe din punct de vedere informațional. Totodată se vor exemplifica câteva variante de implementare a unor algoritmi care au ca scop extragerea acestor tipuri de cunoștinte.
Aplicația a fost concepută pentru a putea verifica funcționarea practică a strategiilor de extragere a cunoștințelor prezentate în partea teoretică a lucrării. Pentru aceasta este necesară selectarea unui set de date și a algoritmului dorit. Aplicația oferă posibilitatea vizualizării rezultatelor obținute în cazul diferitelor seturi de date pentru a putea fi mai atent studiate și comparate. De asemenea utilizatorului îi este permisă crearea unui set de date în vederea verificării modului de aplicare și execuție a algoritmilor.
1.6. Structura proiectului
Capitolul 1. – INTRODUCERE – urmărește o încadrare a lucrării în domeniul data mining și al descoperirii de cunoștințe din bazele de date. Sunt prezentate câteva variante de a defini domeniul data mining utilizând și câteva exemplificări pentru o mai bună înțelegere. Subcapitolul 1.2. furnizează motivația dezvoltării și necesitetea explorării acestui domeniu al tehnologiei informaționale. Se continuă prin a expune pașii care trebuie parcurși în procesul de descoperire a cunoștințelor, urmând ca în subcapitolul 1.4. să se evidențieze domeniile de aplicare și utilizare a data mining. Tot în partea introductivă este prezentată tema si obiectivele acestei lucrări.
Capitolul 2. – Fundamentarea teoretică – prezintă noțiuni de bază din domeniu data mining folosite ca fundament pentru dezvoltarea aplicativă. Se urmărește clarificarea conceptelor de reguli de asociere, reguli negative de asociere și cauzalitate în bazele de date, precum și a modului în care acestea pot fi măsurate și aplicate.
Capitolul 3. – Specificațiile aplicației – furninzează un set de cerințe pentru ulterioara proiectare de detaliu a aplicației. Mai întâi se prezintă o scurtă descriere a părții aplicative. În subcapitolul 3.2 sunt specificate funcțiile îndeplinite de către aplicație, continuând în subcapitolul 3.3. cu o descriere a interfeței cu utilizatorul și a facilităților ei. Urmează o prezentare a tipului de baze de date utilizate și a modului în care aplicația comunică cu acestea. În subcapitolul 3.6. se realizează un scurt studiu al situațiilor de defectare ce pot apărea și modul lor de soluționare.
Capitolul 4. – Proiectarea de detaliu – începe cu o scurtă argumentare a alegerii mediului de dezvoltare, prin sublinierea avantajelor luate în considerare. Subcapitolul 4.1. relatează modul de conectare al aplicației la o bază de date folosind tehnologia ADO.NET. Descrierea claselor și rolului acestora se regăsește în subcapitolul 4.2. Se continuă cu o prezentare a principalelor structuri de date utilizate în cadrul aplicației și structura fisierelor folosite, în subcapitolele 4.4. și 4.5. Sunt prezentate și câteva proceduri cu o importanță mai mare pentru aplicație.
Capitolul 5. – Utilizarea aplicației – se dorește a fi un ghid de utilizare cât mai amănunțit. Pentru a oferi unui utilizator, cu minime cunoștințe de întrebuințare a calculatoarelor, posibilitatea folosiri aplicației la potențialul maxim.
Capitolul 6. – Realizarea punerea în funcțiune și rezultate experimantale – face refereire la modul în care s-a realizat aplicația, resursele necerase pentru rulare și, în subcapitolul 6.3., sunt enumerate prin imagini ale ferestrei aplicației rezultatele obținute pentru dieferite situații de utilizare.
Capitolul 7. – Concluzii – conține un rezumat al obiectivelor realizate pe parcursul lucrării
și o prezentare succintă a principalelor caracteristici ale aplicației practice. De asemenea sunt expuse și câteva posibile direcții de dezvoltare ale aplicației.
CAPITOLUL 2. FUNDAMENTAREA TEORETICĂ
2.1. Reguli de asociere
2.1.1. Concepte de bază
Extragerea regulilor de asociere poate fi definită formal după cum urmează:
este o mulțime de literali sau elemente. De exemplu bunuri, cum ar fi lapte, zahăr și pâine, care se găsesc de cumpărat într-un magazin sunt elemente; și este un obiect, unde este o valoare de domeniu al atributului , în relația .
X este un set de elemente dacă este o submulțime a lui I. De exemplu o mulțime de articole de achiziționat dintr-un magazin este un set de elemente; și o mulțime este un set de elemente pentru relația unde PID este o cheie.
este o mulțime de tranzacții, numită bază de date, unde fiecare tranzacție are asociate un identificator tid și un set de elemente t-itemset, t = (tid,t-itemset). De exemplu, coșul cu cumpărături trecut pe la casă este o tranzacție; un n-uplu (v1, …,vn) al relației este o tranzacție.
O tranzacție t conține un set X de elemente dacă, pentru toate elementele , i este un t-itemset. De exemplu, un coș cu cumpărături care conține toate elementele din X trecut pe la casă; pentru orice din X , vi apare pe poziția i în n-uplu (v1, …,vn).
Un set X de elemente într-o bază de date D are un suport, notat prin (sau p(X)). Acesta este raportul tranzacțiilor din D care conțin setul X. Sau :
,
unde .
Un set X de elemente dintr-o bază de date D este numit set frecvent de elemente dacă suportul său este mai mare sau egal decât pragul minim al suportului (minsupp) dat de utilizatori sau specialiști.
Negarea unui set X de elemente este . Suportul pentru este .
O regulă de asociere este o implicație , unde seturile X și Y de elemente sunt disjuncte.
Orice regulă de asociere are doi indicatori calitativi: suportul și încrederea, definiți astfel:
-suportul unei reguli este suportul setului ;
-încrederea unei reguli se notează ca fiind raportul sau .
Cu alte cuvinte suport = frecvența de apariție a unui șablon; încrederea = tăria implicației.[Zha02]
Principiul suport-încredere: Fie I mulțimea tuturor elementelor dintr-o bază de date D, mulțimi de elemente, , și . Suportul minim (minsupp) precum și încrederea minimă (minconf) sunt date de către utilizatori sau experți. Atunci este o regulă validă dacă:
(1) ;
(2) .
Descoperirea regulilor de asociere poate fi împărțită în două sub-probleme:
– Generarea tuturor seturilor de elemente care au suportul mai mare sau egal cu un minim prestabilit. Adică generarea tuturor seturilor frecvente de elemente.
– Generarea tuturor regulilor având cel puțin o încredere minimă prestabilită, astfel: Pentru fiecare mulțime frecventă X de elemente și orice , fie . Dacă încrederea regulii este mai mare sau egală cu încrederea minimă prestabilită (sau ), atunci ea poate fi extrasă ca o regulă validă.
2.1.2. Căutarea seturilor frecvente de elemente
Identificarea seturilor frecvente de elemente este una dintre cele mai importante probleme cu care se confruntă comunitatea specialiștilor în data mining. S-au elaborat o serie de algoritmi de extragere a seturilor frecvente de elemente din bazele de date foarte mari. “Apriori” este un binecunoscut și foarte folosit algoritm pentru descoperirea mulțimilor frecvente de elemente. Pentru eficiență s-au construit mai multe variante ale acestei abordări, cum sunt algoritmul “hash-based” și algoritmul “OPUS-based“.[Zha02]
2.1.2.1. Algoritmul Apriori
Algoritmul Apriori are la bază tehnica Breath-first de căutare pe nivel. Denumirea algoritmului derivă de la faptul că folosește cunoștințe generate anterior (apriori) pentru a generea noi cunoștințe. Se pornește de la seturile frecvente cu un singur element, pentru a genera seturile frecvente cu două elemente; apoi, pe baza seturilor frecvente de două elemente se generează seturile frecvente cu trei elemente, apoi seturile frecvente de patru elemente, ș.a.m.d. până când nu mai pot fi găsite seturi frecvente cu k elemente. Pentru fiecare mulțime de seturi frecvente cu k elemente este necesară o parcurgere a bazei de date.
Complexitatea unui sistem de extragere a regulilor de asociere este puternic dependent de complexitatea algoritmului de identificare a mulțimilor frecvente de elemente. [apr07]
Algoritmul FrequentItemsets prezentat în cele ce urmează este folosit pentru a genera toate seturile frecvente de elemente dintr-o bază de date specificată. Acesta reprezintă o formă a algoritmului Apriori. Parametrul dbsize reprezintă numărul total de tranzacții din baza de date.
Algoritm FrequentItemsets
begin
intrări: D – data set; minsupp – suportul minim
ieșiri: L – mulțimile frecvente de elemente;
fie setul de mulțimi frecvente ;
fie setul frontieră ;
while do begin
fie mulțimea candidat ;
forall tranzacții t din baza de date do
forall seturi f de elemente din F do
if t conține f then begin
fie mulțimi candidat de elemente care sunt extensii ale f și conținute în t;
forall seturi din do
if then
else
end
fie;
forall seturi c de elemente din C do begin
if then
if c poate fi folosit ca frontieră în pasul următor then
end
end
end
Algoritmul “Apriori” parcurge de mai multe ori o bază de date specificată. Setul frontieră pentru o parcurgere este format din acele mulțimi care sunt extinse în parcurgere. La fiecare parcurgere suportul anumitor mulțimi de elemente este măsurat. Aceste mulțimi de elemente, denumite ca mulțimi candidat de elemente, sunt derivate din mulțimile de elemente conținute în setul frontieră și elementele din tranzacția curentă.[Zha02]
Fiecare set de elemente are asociat un contor care păstrează numărul de apariții ale setului respectiv în baza de date. Acest contor este pus pe zero când un set de elemente este creat.
Inițial, setul frontieră conține un singur element, iar acela este mulțimea vidă. La sfârșitul unei parcurgeri, suportul unei mulțimi candidat este comparat cu minsupp pentru a stabili dacă este mulțime frecventă. În același timp, se stabilește dacă acest set de elemente trebuie adăugat în setul frontieră pentru parcurgerea următoare. Algoritmul se sfârșește când setul frontieră devine vid. Contorul care păstrează numărul de apariții ale unei mulțimi de elemente în baza de date este păstrat la adaugarea acesteia în setul de mulțimi frecvente și/sau în mulțimea frontieră.
Însă, pentru o bază de date mare, algoritmul FrequentItemsets folosit pentru a detecta seturile frecvente de elemente, presupune o căutare cu puține informații euristice într-un spațiu de căutare cu număr de elemente ce crește exponențial. Acest algoritm poate suferi de depășiri ale capacității computaționale dacă numărul de mulțimi frecvente de elemente este foarte mare. Spre exemplu presupunem o bază de date cu 1000 de elemente, numărul mediu de elemente într-o tranzacție fiind 6. În acest caz există aproape 1015 posibile seturi de elemente pentru a fi numărate în baza de date.[Zha02]
2.1.2.2. Identificarea seturilor interesante de elemente
Definiție: (varianta Piatetsky-Shapiro)
Fie I mulțimea elementelor dintr-o bază de date TD, seturi de elemente, , și . Fie minsupp, minconf și mininterest > 0 date de utilizatori sau specialiști. Atunci poate fi extrasă ca o regulă validă de interes dacă:
(1) ;
(2) ;
(3) .
Ținând cont de această definiție, dacă atunci nu poate fi extrasă ca o regulă. De fapt, în teoria probabilităților semnifică faptul că X este aproximativ independent de Y. cu alte cuvinte, dacă , regulaprezintă interes, iar se numește set interesant de elemente, unde mininterest este o valoare minimă a interesului, specificată de utilizatori. În celălalt caz, dacă , regula nu prezintă interes, iar se numește set neinteresant de element. Ținând cont de acestea putem elabora un algoritm mai rapid pentru găsirea tuturor seturilor interesante de elemente dintr-o bază de date specificată.
Multe dintre seturile frecvente de elemente sunt legate de reguli care nu prezintă interes. Dacă sunt extrase doar mulțimile frecvente interesante, spațiul de căutare poate fi mult redus.
În mod normal, algoritmul “Apriori” este folosit pentru a genera toate seturile frecvente de elemente dintr-o bază de date. Cu algoritmul următor se vor genera doar seturile frecvente interesante, cele neinteresante fiind eliminate.
Algoritm FrequentItemsetsbyPruning
begin
intrări: D – data set; minsupp – suportul minim; mininterest – interesul minim
ieșiri: F_set – mulțimi frecvente de elemente;
fie setul de mulțimi frecvente ;
fie ;
fie
for ( )do begin
fie ;
forall tranzacții t din D do begin
fie mulțimi de k elemente din t și conținute în Ck;
forall seturi A de elemente din Ct do
end
fie
for orice set i de elemente din Lk do
if setul i este neinteresant then
end
end
Algoritmul FrequentItemsetsbyPruning este folosit pentru a genera toate seturile frecvente interesante de elemente din bazade date D. Deoarece acest algoritm se aseamănă cu cel anterior, vom prezenta doar diferențele dintre ele. Bucla for principală generează toate seturile , cu , unde este mulțimea tuturor seturilor frecvente cu k elemente din D generate în pasul k al algoritmului, și are condiția de oprire . Pentru trebuie să eliminăm toate seturile neinteresante de k elemente din . Adică pentru orice set i de elemente din , dacă pentru orice pereche X,Y cu , atunci i este un set neinteresant de elemente și trebuie eliminat din .
După ce toate seturile frecvente neinteresante sunt eliminate, spațiul de căutare pentru extragerea seturilor frecvente de elemente este evident redus și toate datele pot fi păstrate în memorie.[Zha02]
2.2. Reguli negative de asociere
2.2.1. Generalități
Modul tradițional de extregere al regulilor de asociere s-a concentrat mai ales pe identificarea relațiilor puternic asociate între seturile de elemente frecvente. Regulile de asociere ne permit să detectăm acele elemente care apar de obicei împreună. Regulile de asociere care au la bază principiul suport-încredere sunt reguli pozitive. Ele indică faptul că prezența unor seturi de elemente implică prezența altor seturi de elemente în aceeași tranzacție.
În aplicații o regulă de forma este folosită pentru a prezice faptul că “dacă apare A, atunci în general apare și B”. O regulă de forma prezice faptul că prezența lui A în tranzacție implică cel mai probabil lipsa lui C din aceeași tranzacție. Acest tip de reguli se numesc reguli negative. Regulile negative indică faptul că prezența unor seturi de elemente implică absența altor seturi de elemnete în aceeași tranzacție.
Există două motive care justifică extragerea atât a regulilor pozitive de asociere cât și a celor negative.
Primul motiv ar fi acela că luarea deciziilor în multe aplicații presupune de multe ori luarea în considerație atât a unui număr de factori, iar aceștia se pot constitui în avantaje sau dezavantaje. Pentru a minimiza impactul negativ și a maximiza posibilul beneficiu, trebuie văzut care dintre factorii cu efect secundar va apărea mai rar sau deloc atunci când apar avantajele dorite. Regulile negative de asociere de forma sunt foarte importante în luarea decizilor pentru că ne spune că C (care poate fi un dezavantaj) apare rar atunci când apare A (care poate fi un avantaj).
Al doilea motiv ar fi acela că experiența în domeniul științei și al ingineriei arată relațiile negative au un rol la fel de important ca cele pozitive. Regulile de asociere de tipul descriu un alt tip de relatie intre seturile de elemente: negarea. De aceea regulile negative de asociere pot fi la fel de importante ca cele pozitive în analiza asocierilor, însă ele sunt ascunse și deosebite.
Identificarea regulilor negative de asociere necesită descoperirea seturilor rare de elemente din baza de date. Algoritmii anteriori sunt folosiți pentru extragerea doar a seturilor frecvente de elemente, de aceeea nu sunt potriviți pentru extragerea regulilor negative de asociere.
Pe de altă parte identificarea seturilor rare de elemente va necesita prelucrarea unui spațiu de căutare de dimensiuni exponențiale. Pentru a rezolva aceste probleme, vom prezenta un algoritm de extragere nu numai a tuturor seturilor pozitive de interes ci și a tuturor seturilor negative de interes din baza de date. Principalul avantaj al acestui algoritm este reducerea spațiului de căutare format din toate elementele și toate seturile posibile de elemente din baza de date.[Zha02]
2.2.2. Seturi pozitive de interes
Formula reprezintă interesul regulii Y dat fiind X și este unul dintre principalii indicatori de incertitudine ai regulilor de asociere.
În general dacă regula este de interes. Strict vorbind dacă:
(1) ;
(2) ;
(3) și
(4)
atunci este o regulă validă de asociere, unde mininterest este specificat de utilizatori, și se numește set pozitiv de interes.
În cazul contrar, dacă i este un set pozitiv de interes, atunci există cel puțin o expresi de forma astfel încât X și Y satisfac cele 4 condiții de mai sus.
2.2.3. Seturi negative de interes
Pentru a extrage reguli negative de asociere, trebuie generate toate seturile de elemente pentru astfel de reguli. De exemplu dacă se poate găsi regula (sau sau ) înseamnă că este indeplinită condiția (sau respectiv ). Ceea ce înseamnă că poate fi îndelinită condiția , iar setul de elemente nu poate fi genereat ca set frecvent de elemente cu ajutorul algoritmilor convenționali. Cu alte cuvinte poate fi un set rar de elemente. Totuși numărul seturilor rare de elemente dintr-o bază de date este de obicei prea mare pentru ca acestea să poată fi ușor manipulate. De aceea trebuie alese doar seturile rare care prezintă interes pentru aplicație. Pentru aceasta este necesară definirea unor condiții de recunoaștere a acestor seturi de elemente.
În general în cazul bazelor de date foarte mari, dacă A este un set frecvent de elemente și B este un set rar de elemente, cu o singură apariție în baza de date, atunci se spune că este o regulă negativă validă având proprietatea că , iar . Aceasta înseamnă că: și . Aceasta înseamnă că regula este validă. Într-o bază de date pot apare mai multe astfel de seturi de elemente. Cu toate acestea cele care atrag atenția sunt de obicei seturile frecvente de elemente. De aceea majoritatea șabloanelor extrase din bazele de date se referă în general la seturile frecvente de elemente. Înseamnă că dacă (sau sau ) este o regulă negativă de interes, A și B implică numai seturi frecvente de elemente. Acesta este unul dintre prinicpalele motive pentru identificarea regulilor negative de asociere.
Pentru aplicații seturile de elemente incluse în regulile negfative de asociere de forma (sau sau ) trebuie să îndeplinească următoarele condiții:
(1) ;
(2) și ;
(3) (sau sau ).
Condiția (2) asigură semnificația probabilistică a regulilor negative de asociere. Celelalte asigură validitatea regulilor. În general un set rar i de elemente se numește set negativ de elemente dcă există cel puțin o expresie astfel încât A și B să Indeplinească cele trei condiții de mai sus.
Ținând cont de definiția Piatetsky-Shapiro, dacă , regula este de interes. Putem spune că dacă:
(1) ;
(2) , și ;
(3) ;
(4)
atunci este o regulă negativă de interes, unde mininterest este o valoare de prag specificată de către utilizatori, iar este un set negativ de interes. Altfel regula nu prezintă interes, iar este un set neinteresant de elemente. În concluzie seturile neinteresante de elemente sunt acele seturi de elemente din baza de date care exclud atât seturile de interes pozitive cât și cele negative. Aceste seturi trebuie eliminate pentru a reduce spațiul de căutare.
Pe de altă parte dacă i este un set negativ de interes atunci există cel puțin o expresie de forma astfel încât una din regulile , sau este o regulă negativă de interes validă.[Zha02]
2.2.4. Căutarea seturilor interesante de elemente
După cum s-a văzut, algoritmul “Apriori” identifică doar seturile frecvente de elemente, neincluzându-le pe cele rare. Pe de altă parte, folosește doar puține informații euristice pentru a parcurge un spațiu de căutare de dimensiuni exponențiale. Cu toate acestea algoritmul poate suferi de depășiri computaționale mari dacă numărul seturilor frecvente de elemente este foarte mare. Următorul algoritm este proiectat să extragă toate seturile, pozitive și negative, de interes.
Procedură InterestItemsetsbyPruning
begin
intrări: D – data set; minsupp – suportul minim; mininterest – interesul minim
ieșiri: PL – seturi pozitive de interes; NL – seturi negative de interes;
fie ;
fie ;
fie ;
fie
for ( )do begin
fie ;
forall tranzacții t din D do begin
fie mulțimi de k elemente din t și conținute în Temk;
forall seturi A de elemente din Temt do
end
fie ;
fie
fie ;
fie ;
for orice set i de elemente din Lk do
if setul i este neinteresant then
fie ;
for orice set i de elemente din Sk do
if setul i este neinteresant then
end
end
Procedura InterestItemsetbyPruning este folosită pentru a genera toate seturile pozitive și negative de interes dintr-o bază de date D, unde PL este mulțimea tuturor seturilor pozitive (frecvente) interesante de elemente din D, iar NL este mulțimea tuturor seturilor negative (rare) interesante de elemente din D. Cu toate că PL și NL conțin numai seturi pozitive respectiv negative de interes, toate seturile de elemente din Frequenti (i>0) trebuie păstrate pentru a genera următoarele seturi negative de interes. Ca urmare sunt trei tipuri de mulțimi care trebuie păstrate pe parcursul execuției algoritmului.
Inițializarea algoritmului constă în inițializarea celor două mulțimi PL și NL, cu mulțimea vidă. În pasul următor se generează mulțimea tuturor seturilor frecvente de un element – Frequent1 – care este apoi adăugat în PL.
Bucla for principală generează toate mulțimile Lk și Sk cu , unde Lk este mulțimea tuturor seturilor pozitive de k elemente din D generate în pasul k al algoritmului, iar Sk este muțimea tuturor seturilor negative de k elemente din D generate în același pas k al algoritmului. Condiția de oprire a buclei este ca ambele muțimi Lk și Sk să fie vide (). Fiecare pas k al algoritmului (al buclei principale) are 5 etape după cum urmează.
Prima etapă reprezintă generearea mulțimii Temk a tuturor seturilor de k elemente din D, unde fiecare set din Temk este reuniunea a două seturi din Frequenti, cu . Adică pentru un set A din Frequenti0 și un set B din Frequenti1, cu , dacă este un set de k elemente, atunci este adăugat în Temk. În a doua etapă pentru fiecare element din Temk este reținut și numărul aparițiilor în baza de date. A treia etapă constă în generarea mulțimilor Ck , Frequentk , Lk și Nk . Ck este mulțimea tutror posibilelor seturi frecvente de k elemente din Temk, astfel încât fiecare astfel de set din Ck să conțină ca subset cel puțin un set din Lk-1. Atât mulțimea Frequentk cât și Lk reprezintă mulțimea tuturor seturilor frecvente de k elemente din Ck, pentru care suportul este mai mare sau egal cu minsupp, fiind numărul total de tranzacții din baza de date D. Cu alte cuvinte Lk reprezintă mulțimea tuturor seturilor pozitive de k elemente din Ck. Nk este mulțimea tuturor seturilor rare de k elemente din Temk, unde suporturile acestora sunt mai mici decât minsupp. Altfel spus este mulțimea tuturor posibilelor seturi negative de k elemente din Temk.
În etapele 4 și 5 ale unui pas al algoritmului sunt selectate doar seturile interesante de k elemente, cele pozitive respectiv cele negative. În a patra etapă se verifică dacă un set i din mulțimea Lk satisface condiția pentru orice expresie de forma , cu X și Y din i. Dacă această condiție este îndeplinită atunci setul i este considerat set neinteresant și este eliminat din Lk. După ce au fost eliminate toate seturile neinteresante din Lk, mulțimea este adăugată la mulțimea PL. În a cincea etapă se generează Sk ca fiind mulțimea tuturor seturilor negative din Nk. Se verifică dacă un set i din mulțimea Sk satisface condiția pentru orice expresie de forma , cu X și Y din i. Dacă această condiție este îndeplinită atunci setul i este considerat set neinteresant și este eliminat din Sk. După ce au fost eliminate toate seturile neinteresante din Sk, mulțimea este adăugată la mulțimea NL. [Zha02]
2.2.5. Reguli negative interesante de asociere
Definiție: rata de probabilitate pentru două seturi X și Y de elemente
Definiție: reguli de interes
Fie I o mulțime de seturi de elemente dintr-o bază de date TD, fie un set de elemente, , și . De asemenea, minsupp, minconf și mininterest >0 sunt date de utilizatori sau specialiști. Atunci:
(1) dacă , , , și , atunci poate fi extrasă ca o regulă de interes;
(2) dacă , , , și , atunci poate fi extrasă ca o regulă de interes;
(3) dacă , , , și , atunci poate fi extrasă ca o regulă de interes;
(4) dacă , , , și , atunci poate fi extrasă ca o regulă de interes.
Această definiție afirmă existența a patru tipuri de reguli de asociere de interes. Primul caz definește regulile interesante pozitive de asociere, iar cazurile (2),(3),(4) definesc reguli interesante negative de asociere. Relațiile de forma garantează faptul că regula de asociere se stabilește între seturi frecvente de elemente, relațiile garantează că regula prezintă interes, iar relațiile reprezintă condiția ca regulile să fie valide și de încredere.
Problema extragerii regulilor de asociere cu ajutorul algoritmului PRModel propus poate fi împărțită în două etape:
(1) generarea mulțimilor PL, formată din toate seturile pozitive de elemente, și NL, formată dint totalitatea seturilor negative de elemente;
(2) generarea tuturor regulilor de forma sau din PL și a tutror regulilor de forma sau , sau din NL
Algoritm PRModel
begin
intrări: D – data set; minsupp – suportul minim; mininterest – interesul minim; minconf – încrederea minimă
ieșiri: – reguli de asociere;
call procedură InterestItemsetsbyPruning
//generarea regulilor pozitive
forall seturi frecvente A din PL do
forall perechi de seturi X,Y cu și do begin
if then begin
if then
output
if then
output
endif
end
//generarea regulilor negative
forall seturi A de elemente din NL do
forall perechi de seturi X,Y cu și do begin
if , ,
if then begin
if then
output
if then
output
endif
if , ,
if then begin
if then
output
if then
output
endif
end
end
Algoritmul PRModel generează nu numai toate regulile pozitive din PL, dar și pe cele negative din NL. Prin apelul procedurii InterestItemsetsbyPruning se inițializează algoritmul prin completarea mulțimilor PL și NL cu totalitatea seturilor interesante pozitive respectiv negative de elemente din baza de date D.
În a doua etapă a algoritmului se generează mai întâi toate regulile pozitive de interes de forma din mulțimea PL, unde . Dacă atunci este extrasă ca o regulă validă având încrederea și suportul . Dacă atunci este extrasă ca o regulă validă având încrederea și suportul .
Algoritmul continuă cu generarea tuturor regulilor negative de forma sau sau sau din NL. Se verifică îndeplinirea condițiilor de suport și interes minim: , , , . Aceste condiții fiind îndeplinite, se testează dacă atunci este extrasă ca fiind o regulă validă de interes cu încrederea și suportul , iar dacă atunci este extrasă ca fiind regulă validă de interes, având încrederea și suportul .
Pentru condițiile de suport și interes minim, , , îndeplinite, dacă atunci este extrasă ca regulă validă de interes cu încrederea și suportul , iar dacă atunci este extrasă ca regulă validă de interes cu încrederea și suportul .[Zha02]
2.3. Cauzalitatea în bazele de date
2.3.1. Definiții
Presupunând că I este un set de elemente dintr-o bază de date D, un subset de elemente de același tip, din I, este numit element cantitativ (quantitative item). O variabilă-element este o variabilă ce reprezintă un set de elemente cantitative într-o mulțime de astfel de seturi aparținând aceluiași domeniu de valori.
O regulă de asociere între elemente este o relație de forma:
, unde A și B sunt seturi de elemente din baza de date, cu . O astfel de regulă are atât suportul cât și încrederea mai mari decât suportul respectiv încrederea minimă (valori prestabilite minsupp respectiv minconf).
O regulă de asociere între elemente cantitative (regulă cantitativă) este o relație de forma:
, unde atribut1 și atribut2 sunt atribute (proprietăți), valoare1 și valoare2 sunt submulțimi ale domeniilor de valori ale atributelor atribut1 respectiv atribut2, iar și sunt elemente cantitative.
O regulă cauzală este o relație de forma:
, unde X și Y sunt variabile cu valori în domeniile R(X) și respectiv R(Y). În acest caz se numește valoare punctuală a lui X, x fiind un element cantitativ.
Cauzalitatea într-o bază de date este reprezentată de o regulă de forma , cu o matrice de probabilitate MY|X definită după relația:
, unde sunt probabilități , i=1,2,…,m și j=1,2,…n.
Se numește element-cantitativ “rău” acel element cantitativ pentru care există reguli de asociere care nu pot fi generalizate în regula cauzală asociată. Dacă două elemente cantitative pot fi compuse într-un nou element cantitativ,care nu este rău, spunem că cele două elemnte cantitative “nu sunt rele”. Dacă un element cantitativ nu poate fi compus cu niciun alt element cantitativ într-un alt element cantitativ non-rău atunci îl numim element cantitativ “bun”.
De asemenea, dacă o variabilă-element poate face ca o regulă cantitativă să nu poată fi generalizată într-o regulă cauzală, aceasta se numește variabilă-element “rea”. Dacă două variabile-element pot fi compuse într-o nouă variabilă-element care nu este o variabilă-element rea, atunci ele se numesc variabile-element “non-rele”. Dacă o variabilă-element nu poate fi compusă cu nicio altă variabilă-element pentru a forma o variabilă-element non-rea, atunci ea se numește variabilă-element “bună”.
Pentru orice două seturi i1, i2 de elemente, spunem că i1, i2 se numesc proprietate-tolerante dacă și numai dacă i1 și i2 au aceeași proprietate, atribut sau constrângere. De asemenea i1, i2 se numesc asociat-tolerante dacă și numai dacă pentru orice set i3 de elemente este verificată relația .
Două elemente cantitative q1, q2 sunt proprietate-tolerante dacă și numai dacă q1 și q2 au aceeași proprietate, atribut sau constrângere. De asemenea q1 și q2 se numesc asociat-tolerante dacă și numai dacă pentru orice element cantitativ q3 relația este verificată.
Două variabile-element X1 și X2 e numesc proprietate-tolerante dacă și numai dacă X1 și X2 au aceeași proprietate, atribut sau constrângere. X1 și X2 se numesc asociat-tolerante dacă și numai dacă pentru orice variabilă Y are loc relația .[Zha02]
2.3.2. Partiționarea datelor
O partiție care poate cauza apariția unor elemente cantitative rele sau a unor variabile-element rele, se numește o partiție rea. O partiție care poate cauza apariția unor elemente cantitative non-rele sau a unor variabile-element non-rele se numește o partiție non-rea. Dacă toate elementele cantitative și toate variabilele-element dintr-o partiție sunt bune atunci aceasta se numește partiție bună.
Fie D o bază de date și I setul tuturor elementelor din D. Un model de partiționare poate fi descris după cum urmează:
(1) generarea proprietăților, atributelor și constrângerilor relative pentru D;
(2) generarea mulțimii QI a tuturor elementelor cantitative din D, pe baza constrângerilor generate anterior, unde toate elementele cantitative formează o partiție a lui I;
(3) optimizarea tuturor elementelo cantitative prin descompunerea și compunerea elementelor cantitative;
(4) generarea mulțimii IV a tuturor variabilelor-element, pe baza proprietățiilor și atributelor generate anterior, unde toate variabilele-element formează o partiție a mulțimii QI și fiecare variabilă-element are asociat un element cantitativ pentru valorile punctuale. Aceasta înseamnă că fiecare variabilă-element poate fi privită ca o mulțime de elemente cantitative cu aceeași proprietate (atribut).
(5) optimizarea tuturor variabilelor-element, prin descompunerea și compunerea lor.
La generarea elementelor cantitative și a variabilelor-element prin partiționare, trebuie considerate toate datele din baza de date pentru a obține o partiție bună a datelor. Deoarece bazele de date reale sunt de multe ori foarte mari procesul de partiționare este consumator de timp.[Zha02]
2.3.3. Descompunerea și compunerea elementelor cantitative
Pentru a găsi o partiție bună pentru o anumită bază de date, elementele cantitative obținute pentru o proprietate trebuie optimizate. O posibilă metodă de optimizare a elementelor cantitative este următoarea
Procedură DecComposeQI
begin
intrări: I – setul tuturor elementelor; QI – mulțimea tuturor elementelor cantitative pentru proprietatea considerată
ieșiri: OQI – mulțimea elementelor cantitative optimizate
fie ;
fie ;
for orice q din qset do
if q este un element cantitativ “rău” then
if i1,i2 nu sunt asociat-tolerante then
descompune q în două elemente cantitative componente q1 și q2 asfel încât ;
fie ;
endif
for orice q1, q2 din qset do
if q1 și q2 sunt proprietate-tolerante then
if q1 și q2 sunt asociat-tolerante then
compune q1 și q2 într-un nou element cantitativ q astfel încât și q nu este un element cantitativ “rău”
fie ;
endif
fie ;
output OQI;
end
Procedura DecComposeQI este utilizată pentru a genera mulțimea OQI a elementelor cantitative optimizate, prin descompunerea elementelor cantitative rele și compunerea elementelor cantitative (proprietate- sau asociat-) tolerante. Procedura cuprinde trei etape după cum urmează.
În prima etapă sunt descompuse elementele cantitative “rele” din mulțimea totală de elemente cantitative ale proprietății. Aceste elemente cantitative “rele” sunt descompuse în câte două elemente cantitative care nu sunt asociat-tolerante.
A doua etapă compune orice două elemente cantitative tolerante din QI. Cu alte cuvinte orice două elemente cantitative tolerante sunt compuse într-un nou element cantitativ “non-rău”.
Ultima etapă a procedurii constă în returnarea mulțimii de elemente cantitative optimizate.[Zha02]
2.3.4. Descompunerea și compunerea variabilelor-element
Potrivit modelului de partiționare prezentat anterior, o proprietate a elementelor poate fi considerată o variabilă-element.
Pentru a putea extrage reguli cauzale, partiția considerată nu trebuie sa conțină variabile-element și elemente cantiataive “rele”, nici chiar variabile-element “non-rele” decât în cazurile în care sunt explicit necesare. Pentru aceasta se prezintă o posibilă metodă de optimizare a variabileleor-element dintr-o partiție.
Procedură DecComposeIV
begin
intrări: QI – mulțimea tuturor elementelor cantitative; IV – mulțimea tuturor variabilelor-element asociate proprietății
ieșiri: OIV – mulțimea variabilelor-element optimizate
fie ;
fie ;
for orice X din vset do
if X este o variabilă-element “rea” then
if nu sunt asociat-tolerante then
descompune X în două variabile-element X1 și X2 asfel încât ;
fie ;
endif
for orice X1, X2 din vset do
if X1 și X2 sunt proprietate-tolerante then
if X1 și X2 sunt asociat-tolerante then
compune X1 și X2 într-o nouă variabilă-element X astfel încât și X nu este o variabilă-element “rea”
fie ;
endif
fie ;
output OIV;
end
Procedura DecComposeIV generează o mulțime OIV formată din variabilele-element optimizate, prin descompunerea variabilelor-element “rele” și compunerea variabilelor-element (proprietate- sau asociat-) tolerante. Asemănător cu procedura anterioară și aceast algoritm de optimizare se desfășoară în trei etape.
În prima etapă sunt descompuse variabilele-element “rele” din mulțimea totală de variabile-element ale proprietății. Aceste variabile-element “rele” sunt descompuse în câte două variabile-element care nu sunt asociat-tolerante.
A doua etapă compune orice două variabile-element tolerante din IV. Cu alte cuvinte orice două variabile-element tolerante sunt compuse într-o nouă variabilă-element “non-rea”.
Ultima etapă a procedurii constă în returnarea mulțimii de variabile-element optimizate.[Zha02]
2.3.5. Procedura de partiționare
Se va elabora un algoritm de partiționare a datelor, folosind cele două proceduri prezentate anterior de generare a mulțimilor elementelor cantitative optimizate respectiv a variabilelor-element optimizate.
Procedură PartitionData
begin
intrări: D – baza de date; Tabel – tabel conținând ierarhiile conceptelor din baza de date; I – mulțimea tuturor elementelor din D
ieșiri: OQI – mulțimea elementelor cantitative optimizate, OIV – mulțimea variabilelor-element optimizate
generarea Sp – mulțimea proprietăților, Sa – mulțimea atributelor conform tabelei Tabel, Sc – mulțimea constrângerilor din D
;
;
fie totalitatea elementelor din D;
for do begin
generare qc din I
if then
fie ;
endfor
for fiecare element i din I do
if i nu e conținut în niciun element cantitativ then begin
fie
fie
endif
call procedură DecComposeQI
for do begin
generare xa din QI
if then
fie ;
endfor
for fiecare element q din QI do
if q nu e valoare a niciunei variabile-element then begin
fie
fie
endif
call procedură DecComposeIV
end
Procedura generează o partiție a unei anumite baze de date pentru a obține un set de elemente cantitative optimizate OQI și un set de variabile-element optimizate OIV. Prima etapă a procedurii o reprezintă inițializarea seturilor QI, IV cu mulțimea vidă, generarea mulțimilor Sp, Sc, Sa și a mulțimii I a tuturor elementelor din baza de date.
A doua etapă a procedurii constă în generarea setului QI de elemente cantitative bazate pe elementele mulțimii I. Elementele mulțimii I sunt împărțite în submulțimi funcție de un set de constrângeri Sc , asfel încât toate aceste submulțimi să fie disjuncte două câte două. Apoi fiecare element rămas în I este considerat ca o submulțime separată. Se obține astfel o primă împărțire a datelor în elemente cantitative.
Aceste elemente cantitative sunt optimizate prin intermediul procedurii DecComposeQI în a treia etapă a procedurii obținându-se setul OQI.
A patra etapă reprezintă generarea setului IV de variabile-element bazate pe elementele setului OQI. Elementele setului OQI sunt împărțite în subseturi în funcție de condițiile cuprinse în seturile Sp și Sa, astfel încât aceste subseturi să fie disjuncte două câte două. Fiecare dintre elementele cantitative rămase în OQI sunt apoi considerate ca subseturi separate. În urma acestui procedeu se obține o primă împărțire a elementelor cantitative în variabile-element.
Variabilele-element obținute se optimizează cu ajutorul procedurii DecComposeIV în ultima etapă a procedurii de partiționare a datelor dintr-o bază de date specificată.[Zha02]
2.3.6. Reguli cauzale de interes
În cazul în care o variabilă-element X influențează o altă variabilă-element Y pentru doar una sau prea puține valori punctuale, matricea de probabilitate aferentă va conține multă informație nefolositoare. O regulă cauzală ar fi mai puțin eficientă de cât o regulă de asociere.
De aceea se stabilesc trei condiții care trebuie îndeplinite pentru ca o regulă cauzală să prezinte interes:
(1) trebuie să existe suficiente probabilități p(yi|xj) în MY|X care să fie mai mari sau egale decât minconf;
(2) pentru o valoare punctuală p(yi|xj) din MY|X
(3) aceste valori punctuale trebuie să verifice de asemenea definiția Piatetsky-Shapiro, sau p(yi|xj)- p(xj) trebuie să fie mai mare sau egal cu o valoare λ, dată de utilizatori.
Presupunând că QI este un set de elemente cantitative dintr-o bază de date D, X și Y sunt variabile element din D, , , , , iar minsupp, minconf, γ>0, α>0, λ>0 și η>0 sunt date de către utilizatori sau specialiști. Unde γ este numărul minim de seturi de elemente cu suportul mai mare sau egal decât minsupp, η este numărul minim de probabilități, α este numărul minim de probabilități care verifică definiția Piatetsky-Shapiro. Se spune că este o regulă cauzală de interes dacă are destule perechi de valori punctuale (yi,xj) în matricea MY|X astfel încât , și
Teoremă: Fie QI un set de elemente cantitative dintr-o bază de date D, X și Y sunt variabile element din D, , , , și , iar minsupp, minconf, γ>0, α>0, λ>0 și η>0 sunt date de către utilizatori sau specialiști. Fie:
(1) ;
(2) ;
(3) .
Regula cauzală prezintă interes dacă și numai dacă se verifică următoarea condiție .
O variantă de algoritm pentru extragerea regulilor cauzale din baza de date este următoarea:
Algoritm CausalityDB
begin
intrări: D – baza de date; minsupp, minconf, α, λ, η – valori date de utilizatori
ieșiri: – regula cauzală, MY|X – matricea de probabilitate condițională pentru Y având dat X
call procedură PartitionData
for do
for fiecare și fiecare do begin
fie ;
fie ca regulă candidat cu matricea de probabilitate condițională MY|X
endfor
for fiecare regulă R având MY|X extrasă din CRSET do begin
fie
fie
fie
if then
generate reguli de asociere pentru mulțimea Ssupport;
else if then
generate reguli de asociere pentru mulțimea Sconf;
else if then
generate reguli de asociere pentru mulțimea Sdepend;
else fie ca o regulă de interes, având matricea de probabilitate condițională MY|X ;
endfor
call procedură RefineRules(NewCRSET,RSET);
output RSET;
end
Algoritmul CausalityDB extrage toate regulile cauzale de forma asociate matricei de probabilitate condițională MY|X, dintr-o bază de date specificată.
În prima etapă a algoritmului este apelată procedura PartitionData, pentru o preprocesare a datelor astfel încât să fie generate toate elementele cantitative și variabilele-element posibile din baza de date D.
A doua etapă generează matricea de probabilitate condițională MY|X pentru fiecare pereche de variabile-element (X,Y) prin calcularea suportului fiecărui element cantitativ asociat. Aceste reguli sunt apoi adăugate în mulțimea CRSET.
A treia etapa a algoritmului constă în determinarea și returnarea doar a regulilor candidat din CRSET care prezintă inters. [Zha02]
CAPITOLUL 3. SPECIFICAȚIILE APLICAȚIEI
3.1. Scurtă descriere
Sistemul are ca scop implementarea unor algoritmi de generare de cunoștințe. Aplicația permite execuția unor algoritmi de data mining pentru extragerea de cunoștințe dintr-o bază de date tranzacțională; algoritmii pot extrage atât seturi frecvente de elemente cât și reguli de asociere între seturile de elemente. De asemenea este posibilă crearea unor tabele de date generate random dintr-o mulțime de valori specificată, în vederea testării algoritmilor implementați.
3.2. Funcțiile sistemului
Din punct de vedere al rolului lor, se pot distinge trei categorii principale:
funcțiile de intrare sunt reprezentate de acele funcții care furnizează setul de date pentru prelucrare:
– selectarea bazei de date prin intermediul unei ferestre de dialog
– încărcarea setului de date în memorie în vederea prelucrării acestora cu ajutorul algoritmilor;
– selectarea unei baze de date pentru crearea unui nou set de date;
– crearea unei structuri de tabel pentru noul set de date;
– generarea random a setului de date conform specificațiilor utilizatorului;
– completarea setului de date prin adăugarea unui alt set de date existent;
funcțiile de prelucrare reprezentate de:
– execuția unui algoritm selectat conform unor parametrii corespunzători, specificați de utilizator;
funcțiile de ieșire ce cuprind:
– afișarea rezultatelor în urma execuției algoritmilor;
– salvarea rezultatelor în format text;
– afișarea datelor de prelucrat în format tabelar;
– afișarea unor mesaje de eroare sau de reușită în funcție de situația apărută;
3.3. Interfața cu utilizatorul
Interfața cu utilizatorul este formată din trei ferestre.
Fereastra principală este destinată selectării setului de date pe care se va testa algoritmul de asemenea selectat de utilizator și afișarea rezultatelor în urma execuției.
Fig. 1 – Fereastra principală a aplicației
Selecția bazei de date se va realiza prin intermediul unei ferestre de dialog și specificarea de la tastatură a tabelului ce conține datele. Încărcarea setului de date presupune și afișarea lor implicită într-o nouă fereastră sub formă de tabel.
Fig. 2 – Fereastra de afișare a setului de date
Algoritmul dorit pentru a fi executat va putea fi selectat dintr-o listă, iar selecția unui algoritm va permite citirea de la tastatură a parametrilor corespunzători. În jumătatea de jos a ferestrei vor fi afișate rezultatele execuției algoritmilor.
Tot din fereastra principală se pot salva în format text rezultatele obținute prin accesarea opțiunii “Save results” din meniul “File”.
Din meniul “Dataset” opțiunea “Generate data”, se deschide o nouă fereastră pentru generarea unui nou set de date conform cerințelor utilizatorului.
Noua fereastră permite din nou selecția unei baze de date în care va fi salvat sub formă de tabel setul de date nou generate.
Trebuie specificat mai întâi numele noului tabel care va conține datele. De asemenea se permite specificate tot de către utilizator a numelui și tipului fiecărei coloane din tabel. Lista de coloane va fi afișată în partea dreapta pentru a putea fi ușor verificată și/sau modificată de catre utilizator înainte de crearea structurii tabelului.
Crearea structurii de tabel va fi semnalizată printr-un mesaj corespunzător și în cazul reușitei și în cazul eșecului datorită apariției unei erori.
Din aceeași fereastră este permisă și completarea tabelului cu datele propriu-zise. Utilizatorul poate specifica modul de generare a setului de date fie prin citirea de la tastatură a unor parametrii (numărul de rânduri din tabel, setul de valori pentru fiecare coloană), fie prin adăugarea datelor existente într-un alt tabel cu aceeași structură.
Ca și în cazul generării structurii tabelului, și operația de completare a datelor va fi semnalizată printr-un mesaj de reușită respectiv de eroare în funcție de situație.
3.4. Structuri de baze de date și fișiere
Seturile de date folosite pentru rularea algoritmilor vor fi păstrate în format de tabel, în baze de date de tip .mdb (Microsoft Access DataBase).
Pentru păstrara rezultatelor afișate se va folosi formatul de fișiere text.
3.5. Comunicarea cu alte sisteme
Pentru interfațarea cu o bază de date se va utiliza biblioteca ADO.NET. Tehnologia folosită de această bibliotecă necesită un obiect de tip conexiune pentru stabilirea unei conexiuni cu o bază de date.
3.6. Analiza de risc
Aplicația este de tip desktop obișnuită, de aceea nu necesită o siguranță deosebită în funcționare. Totuși, se pot lua în calcul anumite situații de funcționare degradată. Se poate construi chiar o ierarhie a situațiilor de risc care pot să apară:
• Nivel de risc 1: situațiile de utilizare incorectă a aplicației. Acest caz este tratat prin afișarea unui mesaj corespunzător de eroare la nivelul interfeței cu utilizatorul.
• Nivel de risc 2: o situație critică ce poate apărea și care duce la întreruperea
automată a rulării programului este cea de supraîncărcare a memoriei sistemului pe care
rulează aplicația (stackoverflow).
3.7. Planificarea lucrărilor
Această lucrare a fost realizată în intervalul de timp începând din ianuarie 2007,
până în iunie 2007. Studierea temei alese și elaborarea specificațiilor s-a întins pe o perioadă de aproximativ 8 săptămâni, etapa de proiectare și implementare a necesitat 8 săptămâni, iar testarea și punerea în funcțiune a celor realizate a solicitat 4 săptămâni.
Resursele utilizate sunt un sistem de calcul cu mediul Visual Studio .NET 2005 și pachetul Microsoft Office, pentru etapa de proiectare și implementare, respectiv două sisteme de calcul cu Framework-ul .NET și pachetul Microsoft Office pentru stadiile de testare ale lucrării.
CAPITOLUL 4. PROIECTAREA DE DETALIU
Programul a fost dezvoltat folosind mediul de programare Visual C# .NET 2005. La
alegerea acestui mediu au fost luate în considerare următoarele considerente:
• faptul că este un mediu de dezvoltare vizual
• mediul .NET permite utilizarea tehnologiei ADO.NET pentru manipularea seturilor de date cu ajutorul unui obiect de tip DataSet care este relativ ușor de creat, extrem de puternic ca funcționalitate, permanent deconectat de baza de date și general disponibil pentru orice tip de furnizor de date (servere de baze de date)
• disponibilitatea tehnologiilor de orientare pe obiecte. Caracteristica de bază a limbajelor de programare orientate pe obiecte este utilizarea claselor pentru a defini natura unui obiect. Un obiect poate fi considerat o entitate care încorporează atât structuri de date cât și comportament. Printre alte caracteristici importante ale limbajelor de programare orientate pe obiecte se numără:
o moștenirea (inheritance), care se realizează prin încorporarea unei clase în declararea altei clase, ducând astfel la crearea unei ierarhii
o supraîncărcarea (overloading) constă din două sau mai multe funcții care au
același nume, însă diferă prin declarațiile parametrilor
• posibilitatea de a scrie programe care îndeplinesc mai multe sarcini în mod paralel sau
cvasiparalel, rulând pe fire de execuție separate, proces cunoscut sub denumirea de
multithreading. Acest mecanism duce la o creștere a vitezei de răspuns a sistemului la
acțiunile utilizatorului.
• tratarea structurată a excepțiilor prin utilizarea unui mecanism de tip Try…Catch…Finally
• asemănarea sintaxei limbajului C# cu cele ale limbajelor C, C++ studiate în facultate
Toate aceste facilități au dus la concluzia că tehnologia .NET și mediul Visual C# sunt
optime pentru dezvoltarea unei lucrări ca cea de față.
4.1. Arhitectura programului
Tehnologia ADO.NET pentru interacțiunea cu baze de date
Ado.net oferă două categorii de provideri de date (un data provider asigurând puntea de legătură între sursa de date, de regulă baza de date, și aplicația client), înglobați în două namespace-uri distincte:
-SQL Server .NET Data Provider – pentru operarea cu Microsoft SQL Server – clase de obiecte conținute în nemespace-ul System.Data.SqlClient
-OLE DB .NET Data Provider – pentru operarea cu surse de date suportând tehnologia Object Linking Embedding DataBase – clase de obiecte conținute în namespace-ul System.Data.OleDb
Obiectele Connection, Command, DataReader, DataAdapter reprezintă nucleul de bază al ADO.NET.
Clasa OleDbConnection face parte din namespace-ul System.Data.OleDb; reprezintă o conexiune unică la o sursă de date (în cazul nostru baza de date) și are ca parametrii de instanțiere:
Provider – provider-ul de date, pentru MicrosoftAccess valoarea acestui parametru va fi “Microsoft.Jet.OLEDB.4.0”
DataSource – calea și numele bazei de date
Dintre metodele clasei OleDbConnection sunt amintite cele mai importante:
Open() – deschiderea conexiunii cu baza de date conform celor specificate prin parametrii de instanțiere
Close() – închiderea conexiunii cu baza de date
Clasa OleDbCommand face parte din namespace-ul System.Data.OleDb; este reprezentată printr-o comandă SQL sau o procedură stocată care urmează a fi executată asupra setului de date și are ca membrii importanți din punct de vedere al aplicației de față:
CommandText – textul comenzii sql care urmează a fi executată
Connection – conexiunea către sursa de date pe care se va executa comanda
Ca metode principale ale acestei clase:
ExecuteNonQuery() – returnează numărul de linii afectate în urma execuției unei comenzi SQL ce nu returnează date
Clasa OleDbDataAdapter face parte din namespace-ul System.Data.OleDb; această clasă este o punte de legătură între clasa DataSet și sursa (baza) de date care permite prelucrarea datelor în lipsa unei conexini deschise; prin intermediul acestei clase datele de la sursă sunt încărcate în memoria locală într-un obiect DataSet și pot fi transmise de la obiectul DataSet spre baza de date; parametrii de instanțiere ai acestei clase:
sqlString – stringul de interogare; este necesar ca acest string să reprezinte o comandă SQL de tipul SELECT
Connection – reprezintă conexiunea utilizată;
Ca metode este amintită:
Fill(DataSet) – încarcă datele din baza de date în memoria locală într-un obiect de tipul DataSet specificat ca parametru, pentru o prelucrare mai rapidă și lipsită de riscuri;
Clasa DataSet – face parte din namespace-ul System.Data și reprezintă unul din componentele de bază ale arhitecturii ADO.NET; păstrează în memorie setul de datele selectat din baza de date permițând astfel întreruperea conexiunii cu baza de date și conferind o manipulare mai ușoară, mai rapidă și mai sigură a datelor. Ca membrii de interes pentru aplicație:
Tables[index] – pentru referirea datelor sub formă de tabel
4.2. Descrierea componentelor
Produsul program prezentat este format dintr-un singur program care înglobează toate funcțiile aplicației. Acesta este însă compus din trei clase principale care la rândul lor înglobează diferite funcționalități pentru a realiza obiectivele propuse.
Clasa AlgorithmForm – conține funcțiile necesare pentru implementarea algoritmilor de generarea a cunoștințelor.Tot prin intermediul acestei clase este asigurată interacțiunea cu utilizatorul. Clasa conține implementările algoritmilor, împreună cu un set de funcții auxiliare necesare, și implementările funcționalităților controalelor menite să asigure interacțiunea dintre utilizator și program. Principalele metode ale acestei clase sunt cele patru proceduri de extragere a cunoștințelor. Metoda FrequentItemsets realizează o implementare a clasicului algoritm Apriori, având ca parametrii setul de date, sub forma unui obiect DataSet, și o valoare de tipul float care reprezintă suportul minim. În urma execuției procedura afișează rezultatele obținute în zona alocată vizualizării lor. Metoda FrequentItemsetsbyPruning încorporează o implementare îmbunătățită a unui algoritm Apriori, având ca parametrii setul de date, de asemenea sub forma unui obiect DataSet și două valori de tipul float reprezenând valoarea de prag pentru suport și gradul minim de interes. Din nou execuția procedurii se încheie cu afișarea rezultatelor în zona de vizualizare. În cadrul metodei PRModel primul pas este de a apela procedura InterestItemsetsbyPruning pentru a obține seturile de elemente folosite apoi în generarea regulilor de asociere, iar ultimul pas al metodei îl constituie afișarea regulilor în zona de vizualizare a rezultatelor. Metoda primește ca parametrii setul de date și trei valori de tipul float reprezentând pragurile minime pentru suportul, încrederea și interesul regulilor ce urmează a fi extrase. A patra metodă principală conținută în clasa AlgorithmForm este CausalityDB reprezentând implementarea algoritmului de extragere a regulilor cauzale. Ca și celelalte metode amintite unul dintre parametrii este setul de date care urmează a fi explorat. De asemenea este nevoie de precizarea valorilor mnime pentru suport și încredere. Algoritmul necesită o partiționare anterioară a datelor pentru a extrage regulile cauzale aferente partiției în cauză. Aceasta se realizează prin apelul procedurii PartitionData care furnizează seturile de variabile-element și de elemente-cantitative.
Clasa DisplayForm – reprezintă clasa necesară pentru afișarea setului de date sub formă de tabel. Această clasă se instanțiază din clasa AlgorithmForm și permite utilizatorului să urmărească setul de date încărcat și să analizeze prin comparație rezultatele obținute.
Clasa DataSetForm – reprezintă clasa cu ajutorul careia se oferă utilizatorului posibilitatea de a crea propriul set de date. În vederea testării și studierii mai amănunțite a rezultatelor obținute s-a creat acestă clasă care are ca metode principale CreateTable și FillTable. Prin intermediul metodei CreateTable se crează structura tabelului în care va fi înregistrat noul set de date. Metoda utilizează tehnologia ADO.NET pentru a se conecta la baza de date în care se vor reține noile date generate. Cu ajutorul metodei FillTable clasa DataSetForm oferă posibilitatea de a genera un set de date aleatoare, dar care să respecte anumite condiții specificate de către utilizator. Pentru a specifica aceste condiții de generare a noilor date utilizatorul se folosește de interfața grafică intuitivă pusă la dispoziție prin intermediul acestei clase.
4.3. Principalele structuri de date
Întregul mecanism de generare al cunoștințelor se bazează pe noțiunea matematică de mulțime de mulțimi implementată în aplicație prin structura de listă cu subliste.
Caracteristic acestui tip de structură sunt dimensiunile variabile atât a listei principale cât și a sublistelor. Deoarece nici numărul, nici dimensiunea seturilor frecvente de elemente nu sunt cunoscute de la început, dar ele pot ajunge la valori destul de mari, este nevoie de o structură care poate fi ușor extinsă pe parcursul aplicației fără a ocupa memoria sistemului decât dacă ea conține date.
Pentru aplicația de față s-a folosit clasa ArrayList care face parte din namespace-ul System.Collections. Această clasă permite manipularea structurilor de tip listă de obiecte. De asemenea procedurile de alocare și eliberare a memoriei sunt implementate în cadul clasei ușurând astfel sarcina programatorului. Printre alte facilități clasa ArrayList mai permite și transformarea elementelor din tipul Object în orice alt tip chiar și ArrayList, obținând astfel structura de listă cu subliste. Referirea unui obiect din listă se face prin intermediul unui index asociat fiecărui element.
Câțiva membri și câteva metode ale clasei, utile în cadrul aplicației de față sunt:
Count – membru ce conține numărul total de elemente din listă;
Add și AddRange – metode ce permit adăugarea unui nou element în listă respectiv adăugarea unui set de elemente dintr-o listă în alta;
Clear – metodă ce permite ștergera tuturor elementelor din listă;
Contains – verifică dacă un element există în listă sau nu;
Remove și RemoveAt – elimină din listă prima apariție a unui element specificat respectiv elimină elementul de pe poziția specificată;
Conceptul de cauzalitate în bazele de date are la bază noțiunea de probabilitate.
În cazul regulilor cauzale este necesară o structură de tipul matrice având ca elemente valori ale probabilităților condiționale aferente regulii respective. Această structură numită martice de probabilitate trebuie să permită referirea unui element prin specificarea valorilor punctuale ale variabilelor-element între care se stabilește regula.
Clasa ProbabilityMatrix – implementează structura de matrice de probabilitate
Membrii clasei:
Xname și Yname – de tipul string cu acces public, reprezintă variabilele-element X respectiv Y din regula cauzală ;
X și Y – de tipul string[] cu acces public, reprezintă sirurile de valori punctuale ale celor două variabile-element din cadrul regulii cauzale aferente matricei;
Myx – de tipul float[,] cu acces public, reprezintă matricea propriu-zisă conținând valorile probabilităților condiționale aferente perechilor de valori punctuale.
Metodele clasei ProbabilityMatrix:
public ProbabilityMatrix(){} – constructorul fără parametrii al clasei;
public ProbabilityMatrix(string name_x, int m, string name_y,int n) –constructorul cu parametrii al clasei;
public void FillX(string[] source), public void FillY(string[] source) – metodele pentru atribuirea șirurilor de valori punctuale aferente fiecărei variabile-element X respectiv Y;
public void SetElemMyx (string valX, string valY, float probab) – atribuirea valorii elementului din Myx corespunzător valorilor punctuale valX și valY ale variabilelor-element X respectiv Y;
public float GetElemMyx (string valX, string valY) – returnează valoarea elementului din Myx corespunzător valorilor punctuale valX și valY ale variabilelor-element X respectiv Y;
4.4. Structuri de fișiere
Produsul program are facilitatea de a salva rezultatele obținute în fișiere de tip text, în diferite momente ale rulării aplicației.
Seturile de date sunt păstrate în tabele având o anumită structură. Prima coloană a tabelului va conține un identificator al tranzacției sau un număr curent, pentru o identificare mai ușoară a tranzacțiilor. Următoarele coloane conțin datele propriu-zise care urmează a fi explorate în procedeul de extragere a cunoștințelor.
4.5. Proceduri
Dat fiind specificul aplicației expunerea procedurile de implementare a algoritmilor reprezintă un avantaj în procesul de înțelegere a modului de extragere de cunoștințe din bazele de date.
Procedura de implementare a algoritmului Apriori prezentat în capitolul 2.1.2.1.:
public void Frequent_Itemsets(DataSet ds,float minsupp)
{
ArrayList F_set = new ArrayList(); //multime de multimi
ArrayList L = new ArrayList(); //multime de multimi
ArrayList C = new ArrayList(); //multime de multimi
ArrayList Cf_set = new ArrayList(); //multime de multimi
ArrayList cf = new ArrayList(); //multime
ArrayList f = new ArrayList(); //multime
ArrayList t = new ArrayList(); //multime
int dbsize;
int dbcols;
dbsize=ds.Tables[0].Rows.Count;
dbcols=ds.Tables[0].Columns.Count;
F_set.Add(new ArrayList());
L.Add(new ArrayList());
while (F_set.Count != 0)
{
C.Clear();
C.Add(new ArrayList());
//parcurgerea bazei de date
for (int i=0; i<dbsize; i++)
{
//extragerea unei tranzactii din baza de date in //ArrayList t
t.Clear();
t.AddRange(get_DB_row(ds,i,1));
//parcurgerea multimii frontiera
for (int j=0; j<F_set.Count; j++)
{
f.Clear();
f.AddRange((ArrayList)F_set[j]);
if (A_includes_B(t,f))
{
Cf_set.Clear();
//generarea Cf -multimea de posibili candidati din tranzactia curenta
for (int k=0; k<t.Count; k++)
{
cf.Clear();
cf.AddRange(f);
if (! f.Contains(t[k]))
cf.Add(t[k]);
else
continue;
if (A_includes_B(t,cf))
{
Cf_set.Add(new ArrayList());
((ArrayList)Cf_set[Cf_set.Count-1]).AddRange(cf);
}
}//END generare Cf
//incrementare contor pt fiecare itemset din multiea de candidati
for(int k=0; k<Cf_set.Count; k++)
{
cf.Clear();
cf.AddRange((ArrayList)Cf_set[k]);
int pozitie=0;
pozitie=A_contains_B(C,cf,1);
if (pozitie!=-1)
{
((ArrayList)C[0])[pozitie-1]=(int)(((ArrayList)C[0])[pozitie-1])+1;
}
else
{
((ArrayList)C[0]).Add((int)1);
C.Add(new ArrayList());
((ArrayList)C[C.Count-1]).AddRange((ArrayList)cf);
}
}// END parcurgerea multimii Cf_set
}// END if t contine cf
}//END parcurgerea multimii frontiera
}//END parcurgerea bazei de date
F_set.Clear();
int c_count=0;
int nr_elem=0;
for (int k=1; k<C.Count; k++)
{
nr_elem=((ArrayList)C[k]).Count;
c_count=(int)((ArrayList)C[0])[k-1]/nr_elem;
float freq;
freq=((float)c_count/dbsize);
if (freq >= minsupp)
{
((ArrayList)L[0]).Add(c_count);
L.Add(new ArrayList());
((ArrayList)L[L.Count-1]).AddRange((ArrayList)C[k]);
F_set.Add(new ArrayList());
((ArrayList)F_set[F_set.Count-1]).AddRange((ArrayList)C[k]);
}
}
}//END while F_set nu e vida
//afisare rezultate
richTextBox1.AppendText("\nFrequent itemsets:\n");
if (L.Count>1)
{
display_sets_and_frequency(L);
}
else
{
richTextBox1.AppendText(" Nu exista seturi frecvente de elemente\n");
}
}
Procedura de implementare a algoritmului Apriori îmbunătățit prezentat în capitolul 2.1.2.2.:
public void Frequent_Itemsets_by_Pruning(DataSet ds,float minsupp,float mininterest)
{
ArrayList Fset = new ArrayList();
ArrayList L = new ArrayList();
ArrayList Lk = new ArrayList();
ArrayList Ck = new ArrayList();
ArrayList I = new ArrayList();
int dbsize;
int dbcols;
dbsize = ds.Tables[0].Rows.Count;
dbcols = ds.Tables[0].Columns.Count;
I.AddRange(get_DB_itemset(ds));
//L<-frequent_1_item_sets;
L.Add(new ArrayList());
for (int i=1; i<I.Count; i++)
{
int aux;
float freq;
aux=(int)((ArrayList)I[0])[i-1];
freq=((float)aux)/dbsize;
if (freq >= minsupp)
{
((ArrayList)L[0]).Add(aux);
L.Add(new ArrayList());
((ArrayList)L[L.Count-1]).AddRange((ArrayList)I[i]);
}
}
ArrayList c = new ArrayList();
ArrayList elemL = new ArrayList();
ArrayList aux1 = new ArrayList();
Fset.AddRange(L);
//generare seturi Lk
for (int k=2; L.Count>1; k++)
{
//generare Ck
Ck.Clear();
Ck.Add(new ArrayList());
elemL.Clear();
elemL.AddRange(get_elements(L,1));
for (int i=1; i<L.Count; i++)
{
c.Clear();
aux1.Clear();
c.AddRange(((ArrayList)L[i]));
aux1.AddRange(c);
aux1.RemoveAt(aux1.Count-1);
for (int j=0; j<elemL.Count; j++)
{
if (! c.Contains(elemL[j]))
{
c.Add(elemL[j]); //k elemente
aux1.Add(elemL[j]);
if ((A_contains_B(L,aux1,1)!=-1)&&(A_contains_B(Ck,c,1)==-1))
{
((ArrayList)Ck[0]).Add(0);
Ck.Add(new ArrayList());
((ArrayList)Ck[Ck.Count-1]).AddRange(c);
}
c.Remove(elemL[j]);
aux1.Remove(elemL[j]);
}
}
}
//contorizarea aparitiilor elem din Ck in BD
ArrayList t = new ArrayList();
for (int i=0; i<dbsize; i++)
{
//t.AddRange(get_DB_row(ds,i,1));
t.Clear();
t.AddRange(get_DB_row(ds,i,1));
for(int j=1; j<Ck.Count; j++)
{
if (A_includes_B(t,(ArrayList)Ck[j]))
((ArrayList)Ck[0])[j-1]=(int)(((ArrayList)Ck[0])[j-1]) +1;
}
}
//generare Lk
Lk.Clear();
Lk.Add(new ArrayList());
for (int i=1; i<Ck.Count; i++)
{
int c_count=(int)((ArrayList)Ck[0])[i-1];
float supp=(float)c_count/dbsize;
if (supp>=minsupp)
{
((ArrayList)Lk[0]).Add(c_count);
Lk.Add(new ArrayList());
((ArrayList)Lk[Lk.Count-1]).AddRange((ArrayList)Ck[i]);
}
}
//pruning
for (int i=Lk.Count-1; i>0; i–)
{
if (is_uninteresting(ds,(ArrayList)Lk[i],mininterest))
{
((ArrayList)Lk[0]).RemoveAt(i-1);
Lk.RemoveAt(i);
}
}
L.Clear();
L.AddRange(Lk);
((ArrayList)Fset[0]).AddRange((ArrayList)Lk[0]);
Lk.RemoveAt(0);
Fset.AddRange(Lk);
}
//afisare rezultate
richTextBox1.AppendText("\nFrequent itemsets with pruning:\n");
if (Fset.Count>1)
{
display_sets_and_frequency(L);
}
else
{
richTextBox1.AppendText(" Nu exista seturi frecvente de elemente\n");
}
}
Procedura de implementare a algoritmului PRModel prezentat în capitolul 2.2.5.:
public void PRModel(DataSet ds, float minsupp, float minconf, float mininterest)
{
ArrayList PL= new ArrayList();
ArrayList NL= new ArrayList();
int dbsize=ds.Tables[0].Rows.Count;
Interest_Itemsets_by_Pruning(ds,minsupp,mininterest,PL,NL);
richTextBox1.AppendText("\nREGULI:\n");
//generare reguli pozitive: A->B
ArrayList A = new ArrayList();
ArrayList B = new ArrayList();
ArrayList multime = new ArrayList();
for (int i=1; i<PL.Count; i++)
{
multime.Clear();
multime.AddRange((ArrayList)PL[i]);
if (multime.Count>1)
{
int cont=0;
while(cont<multime.Count)
{
for (int k1=cont; k1<multime.Count; k1++)
if (!A.Contains(multime[k1])&& (A.Count+1)<multime.Count)
{
A.Add(multime[k1]);
B.Clear();
B.AddRange(multime);
for(int aux=0; aux<A.Count; aux++)
{
B.Remove(A[aux]);
}
//prelucrare
int[] nr_app=new int[6];
nr_app=counting(ds,A,B);
float supp_AB=(float)nr_app[2]/dbsize;
float supp_A=(float)nr_app[0]/dbsize;
float supp_B=(float)nr_app[1]/dbsize;
if((supp_AB-supp_A*supp_B)>= mininterest)
{
float conf=PR(supp_AB,supp_A,supp_B);
if(conf>=minconf)
display_rule(A,B,1,conf,supp_AB);
}
if (A.Count>=2)
{
cont=multime.IndexOf(A[A.Count-2])+1;
A.RemoveRange(A.Count-2,2);
}
else
{
cont=multime.IndexOf(A[A.Count-1])+1;
A.RemoveAt(A.Count-1);
}
}//END while
}
}
//END generare reguli pozitive
//generare reguli negative: A->notB, B->notA, notA->notB
for(int i=1; i<NL.Count; i++)
{
multime.Clear();
multime.AddRange((ArrayList)NL[i]);
if (multime.Count>1)
{
//generare submultimi A,B a.i. AUB=NL[i]
int cont=0;
while(cont<multime.Count)
{
for (int k1=cont; k1<multime.Count; k1++)
if (!A.Contains(multime[k1])&& (A.Count+1)<multime.Count)
{
A.Add(multime[k1]);
B.Clear();
B.AddRange(multime);
for(int aux=0; aux<A.Count; aux++)
{
B.Remove(A[aux]);
}
//prelucrare
int[] nr_app=new int[6];
nr_app=counting(ds,A,B);
float supp_A=(float)nr_app[0]/dbsize;
float supp_B=(float)nr_app[1]/dbsize;
float supp_notA=1-supp_A;
float supp_notB=1-supp_B;
float supp_BnotA=(float)nr_app[4]/dbsize;
float supp_notAnotB=(float)nr_app[5]/dbsize;
if(supp_A>=minsupp && supp_B>=minsupp && supp_BnotA>=minsupp)
{
if (supp_BnotA-supp_notA*supp_B >=mininterest)
{
if(PR(supp_BnotA,supp_B,supp_notA)>=minconf)
{
display_rule(A,B,3,PR(supp_BnotA,supp_B,supp_notA),supp_BnotA);
}
if(PR(supp_BnotA,supp_notA,supp_B)>=minconf)
{
display_rule(B,A,2,PR(supp_BnotA,supp_notA,supp_B),supp_BnotA);
}
}
}
if(supp_A>=minsupp && supp_B>=minsupp && supp_notAnotB>=minsupp)
{
if (supp_notAnotB-supp_notA*supp_notB>=mininterest)
{
if(PR(supp_notAnotB,supp_notB,supp_notA)>=minconf)
{
display_rule(A,B,4,PR(supp_notAnotB,supp_notB,supp_notA),supp_notAnotB);
}
if(PR(supp_notAnotB,supp_notA,supp_notB)>=minconf)
{
display_rule(B,A,4,PR(supp_notAnotB,supp_notA,supp_notB),supp_notAnotB);
}
}
}
}
if (A.Count>=2)
{
cont=multime.IndexOf(A[A.Count-2])+1;
A.RemoveRange(A.Count-2,2);
}
else
{
cont=multime.IndexOf(A[A.Count-1])+1;
A.RemoveAt(A.Count-1);
}
}//END while
}
}
}
Procedura CausalityDB prezentată în capitolul 2.3.6.:
public void CausalityDB(DataSet ds, float minsupp, float minconf,float alfa, float lambda, float eta)
{
ArrayList OIV=new ArrayList();
string[] rx;
string[] ry;
ArrayList itemvarDom=new ArrayList();
ProbabilityMatrix M;
OIV.AddRange(PartitionData(ds));
itemvarDom.AddRange(get_ItemvarDomains(ds));
int dbsize=ds.Tables[0].Rows.Count;
foreach (string X in OIV )
foreach (string Y in OIV)
{
if (X!=Y)
{
//domeniile de valori pt elem-varialbile X, resp Y
rx=R(X,itemvarDom);
ry=R(Y,itemvarDom);
M=new ProbabilityMatrix(X,rx.Length,Y,ry.Length);
M.FillX(rx);
M.FillY(ry);
//matricea de probabilitate
foreach(string a in rx)
foreach(string b in ry)
{
ArrayList A=new ArrayList();
ArrayList B=new ArrayList();
A.Add(a.ToString());
B.Add(b.ToString());
int[] app=counting(ds,A,B);
float pr=(float)app[2]/app[0];
pr=(float)Math.Round(pr,3);
M.SetElemMyx(a,b,pr);
pair xy=new pair(a,b,(float)app[2]/dbsize);
richTextBox1.AppendText("\nItem Variables: ");
richTextBox1.AppendText("\n "+X+": ");
display(rx,0);
richTextBox1.AppendText("\n "+Y+": ");
display(ry,0);
richTextBox1.AppendText("\nProbability Matrix: \n");
for(int i=0;i<rx.Length;i++)
{
for(int j=0;j<ry.Length;j++)
{
richTextBox1.AppendText(M.GetElemMyx(rx[i],ry[j]).ToString()+" ");
}
richTextBox1.AppendText("\n");
}
}
}
}
CAPITOLUL 5. UTILIZAREA APLICAȚIEI
Aplicația este o aplicație de tip desktop cu un singur modul.
Fereastra principală perminte selectarea setului de date pe care se vor rula algoritmii, executarea algoritmilor și vizualizarea rezultatelor.
Fig. 3 – Fereastra principală a aplicației
Butonul “Select database” deschide o fereastră dialog de selecție a unei baze de date și afișează selecția în textbox-ul aferent. După selecția bazei de date se specifică numele tabelului dorit. Apăsarea butonului “Load dataset” afișează o nouă formă care conține datele dorite sub formă tabelară și totodată încarcă setul de date specificat, în memorie.
Fig. 4 – Fereastra de afișare a setului de date
Odată cu încărcarea setului de date se poate alege și algoritmul dorit.
Fig. 5 – Selectarea unui algoritm și validarea secțiunii de citire a parametrilor corespunzători
La schimbarea selecției algoritmului, în partea dreaptă a ferestrei se pot atribui valori și parametrilor aferenți fiecărui algoritm. În funcție de algoritmul selectat sunt validate textbox-urile de citire a parametrilor corespunzători elgoritmului. Parametrii sunt inițializați la o anumită valoare pentru a ușura utilizarea aplicației.
Fig. 6 – Modificarea validării secțiunii de citire a parametrilor în funcție de algoritmul selectat
Execuția unui algoritm se realizează prin apăsarea butonului “Execute”. În urma rulării unui algoritm rezultatele vor fi afișate în format text, în zona de vizualizare.
Pentru ștergerea rezultatelor se apasă butonul “Clear results”, altfel rezultatele ulterioare vor fi afișate în continuarea afișajului existent.
Fig. 7 – Afișarea rezultatelor în urma execuției algorimilor aleși – rezultatele din figură corespund tabelului din figura Fig. 2 prezentată anterior
Afișajul din zona de vizualizare a rezultatelor poate fi salvat în format text pentru o studiere ulterioară mai aprofundată. Salvarea se face din meniul “File/Save results”.
Bara de meniuri a ferestrei principale mai conține și meniul “Dataset” care permite prin alegerea opțiunii “Generate data”, generarea unui set de date în vederea testării algoritmilor. Setul de date este reprezentat în forma unui tabel dintr-o bază de date Microsoft Access (.mdb).
Generarea setului de date se face prin intermediul unei noi ferestre afișată la selecția opțiunii “Dataset/Generate data”. Această fereastră este împărțită în două secțiuni principale: “Table structure” și “Table data”.
Primul pas în generarea unui set de date este selecția unei baze de date existente pentru a putea crea un nou tabel de date.
Odată selectată baza de date, se poate crea structura tabelului. Trebuie specificate un nume de tabel și cel puțin o coloană. Coloanele sunt afișate în lista din partea dreaptă având formatul “nume_coloană tip_date”. Numele coloanei este citit de la tastatură, iar tipul poate fi atât citit de la tastatură cât și ales dintr-o listă cu desfășurare. Acestea sunt apoi adăugate în listă cu ajutorul butonului “Add column”. Cu ajutorul butonului “Remove column” este ștearsă din listă coloana de tabel selectată.
Generarea structurii tabelului se realizează prin apăsarea butonului “Create table”; butonul “Cancel” alăturat șterge atât numele tabelului cât și lista de coloane. Structurii specificate de utilizator i se adaugă o coloană “nr_crt” de tipul autonumber, pentru o identificare mai ușoară a tranzacțiilor din tabel. Acest câmp nu are nici o influență asupra algoritmilor și nu este vizibil utilizatorului decât în cadrul afișării tabelului după încărcarea datelor, din fereastra principală.
Fig. 8 – Fereastra de generare a setului de date secțiunea de generare a structurii tabelului – în cazul în care generarea structurii tabelului a decurs normal se afișează un mesaj de reușită
După ce a fost creată structura tabelului, în secțiunea “Table data” este disponibilă o listă cu desfășurare conținând coloanele specificate în secțiunea anterioară de către utilizator.
Umplerea tabelului cu date se poate face în două moduri: prin generare de noi date, sau prin adăugarea unui set de date deja creat. Modul implicit de umplere este prin generare de noi date, astfel că toate câmpurile de citire a datelor sunt valide. Trebuie specificate numărul de rânduri (tranzacții) din tabel și lista de valori aferente fiecărei coloane. Aceste liste de valori sunt citite de la tastatură, iar elementele lor trebuie separate prin caracterul “;”. Prin butonul “Add values” listele de valori sunt adăugate împreună cu coloana corespunzătoare în cele două listbox-uri din partea de jos a ferestrei. De asemenea o listă de valori poate fi și ștearsă.
Al doilea mod de completare cu date a tabelului este prin adăugarea înregistrărilor unui tabel cu aceeași structură în continuarea datelor existente (fie generate după modul prezentat anterior, fie existente în tabel la deschiderea acestuia). Pentru aceasta utilizatorul trebuie să bifeze check-boxul “Append table”, moment în care seinvalidează zonele de citire a datelor din secțiunea “Table data” și se validează cele două câmpuri de citire a numelui tabelului care urmează să fie adăugat și a bazei de date din care face parte.
Se trece apoi la generarea propriu-zisă de date prin apăsarea butonului “Fill table”. În cazul în care se reușește generarea tuturor datelor din tabel respectiv adăugarea tabelului specificat la cel nou creat, se afișează un mesaj de reușită, în caz contrar se afișează un mesaj de eroare.
Fig. 9 – Fereastra de generare a setului de date secțiunea de generare a datelor propriu-zise – în cazul în care generarea propriu-zisă a decurs normal se afișează un mesaj de reușită
Fig. 10 – Fereastra de afișare a tabelului de date – se poate verifica generarea conform specificațiilor utilizatorului a setului de date
CAPITOLUL 6. REALIZAREA, PUNEREA ÎN FUNCȚIUNE ȘI REZULTATE EXPERIMENTALE
6.1. Realizarea programului
Programul a fost realizat în mediul VisualStudio.NET 2005, în limbajul C# datorită avantajelor prezentate deja în capitolul 4.
Pentru a asigura calitatea unui produs software este necesară o testare și o verificare
riguroasă a produsului.
Există și o configurație a mediului de programare care este dedicată detecției și
corecției de erori, care poartă denumirea de Debug. Pe parcursul dezvoltării aplicației a fost
utilizată opțiunea Debug, pentru fixarea diverselor erori.
O regulă utilă în evitarea erorilor uzuale este parcurgerea linie cu linie a oricărei porțiuni
noi de cod. După scrierea unei astfel de porțiuni este indicată rularea programului în mod Debug
introducând un punct de oprire (breakpoint) înaintea apelării noului cod și vor fi urmărite
variabilele și tot mecanismul nou implementat.
La testarea unui produs soft este de dorit ca datele de intrare să acopere toate variantele
posibile, testând astfel toate căile de execuție ale codului.
6.2. Punerea în funcțiune
Pentru o bună funcționare a aplicației este necesar un sistem de calcul PC având o memorie 512 Mb RAM și o capacitate de stocare de minim 4 Gb HDD, care funcționează la o frecvență de minim 2.2 GHz, pe care să ruleze un sistem de operare WindowsXP. De asemenea este necesar un sistem de gestiune a bazelor de date Microsoft Access și existența Microsoft .NET Framework minim versiune 2.0.
6.3. Rezultate experimentale
Rezultatele experimentale constă în cunoștințele obținute prin rularea aplicației.
Pentru un studiu mai amănunțit asupra rezultatelor se vor prezenta câteva situații studiate.
O primă situație studiată a fost ezultatele obținute de diferiții algoritmi pe același set de date. Considerând un set de date ca cel din figură, de interes pur experimental, se execută pe rând trei dintre algoritmii implementați.
Pentru aceeași parametrii comuni (suportul minim) se vor extrage următoarele cunoștințe:
– rezultatele algoritmilor Apriori și FrequentItemsetsbyPruning:
Pentru setul de date considerat este ușor de verificat validitatea rezulatelor obținute.
Se poate observa că algoritmul FrequentItemsetsbyPruning a extras mai puține cunoștințe din același set de date și având același parametru de suport minim. Este evident însă că acest lucru se datorează condiției de interes minim care nu e luată în considerare de varianta Apriori a descoperirii seturilor frecvente. Numărul mai redus al cunoștintelor obținute nu reprezintă un impediment, ci reprezintă o îmbunătățire prin aceea că este o dovadă a reducerii dimensiunii spațiului de căutare a seturilor frecvente.
În cazul algoritmului PRModel, executat pentru aceleași valori ale parametrilor “setul de date”, “suportul minim” și “interesul minim”s-au obținut rezultatele:
Se poate observa că o parte din seturile frecvente de elemente descoperite și de strategiile anterioare au fost de data aceasta tratate ca reguli pozitive de asociere. Păstrând aceiași parametrii minsupp și mininterest au fost extrase aceleași seturi frecvente. Cu toate acestea algoritmul PRModel a descoperit cunoștințe care implică lipsa unor seturi de elemente, ceea ce algoritmii anteriori nu au reușit. Și în cazul acestui algoritm setul de date foarte sumar permite o verificare manuală a acurateții rezultatelor.
În cazul algoritmului CausalityDB nu are sens execuția pe acest set de date.
Experimentul anterior a permis atât compararea rezultatelor cât și verificarea funcționării corecte, conform definițiilor prezentate în capitolul 2, a trei dintre algoritmii prezentați. Pentru a verifica ultimul algoritm se va face uz de rezultatele obținute prin execuția celorlalți, considerând un alt set de date, dar de această dată cu o semnificație mai aproape de realitate. Astfel vom considera un set de date, reprezentând nivelul de educație și nivelul de salarizare al personalului dintr-o instituție, cu 30000 de tranzacții.
Vom considera parametrii ca având valorile: minsupp=0.3, mininterest=0.07 și minconf=0.4.
Prin execuția algoritmilor Apriori și FrequentItemsetsbyPruning s-au obținut rezultatele:
De data aceasta se poate observa că cei doi algoritmi s-au concluzionat cu aceleași rezultate. Valoarea parametrului mininterest nu a influențat vizibil spațiul de căutare a seturilor frecvente în cazul algoritmului FrequentItemsetsbyPruning.
Pentru algoritmul PRModel structura setului de date face ca extragerea unor cunoștințe sub forma regulilor de asociere să nu aibă prea mut sens. De aceea pentru cunoștințele sub forma de reguli se va utiliza algoritmul CausalityDB pentru a extrage regulile cauzale care au rost în cazul setului de date prezentat. Astfel s-au obținut rezultatele:
Se pot observa regulile cauzale sub forma de imlicație alături de matricea de probabilitate aferentă fiecărei reguli. Se poate spune că acest tip de reguli înglobează mai multe reguli de asociere în vederea determinării unei dependențe cauzale între clasele de elemente. O vizualizare a rezultatelor duce la concluzia că regula cauzală “education->salary” prezintă o încredere mai mare decât regula inversă. Aceasta se poate observa prin compararea valorilor maxime ale probabilităților din matricea aferentă primei reguli cu cele din a doua matrice.
CAPITOLUL 7. CONCLUZII
7.1. Ce s-a realizat
Pe fundalul situației actuale de creștere a capacității de stocare a datelor, extragerea informațiilor cu adevărat utile, referite prin termenul de cunoștințe, devine atât o necesitate cât și un avantaj major. Totodată procesul de extragere a cunoștințelor devine anevois și consumator de timp datorită cantității imense de date acumulate. Evoluția tehnologică însă, permite dezvoltarea unor aplicații automatizate care să înlocuiască factorul uman în procesul de extragere a acestor informații.
Proiectul conține o parte teoretică și o parte aplicativă.
Partea teoretică a proiectului începe prin a defini conceptul de data mining și descoperire a cunoștințelor din bazele de date. Se prezintă importanța și necesitatea explorării acestui domeniu și sunt enumerați pașii care trebuie parcurși pentru a extrage cunoștinte din seturile de date. Sunt exemplificate domeniile de aplicare ale conceptului de data mining.
Studiul teoretic insistă asupra noțiunii de cunoștințe sub forma seturilor frecvente de elemente și a regulilor de asociere, și de asemenea, asupra modului în care acestea pot fi extrase din seturile de date. Se prezintă diferite moduri de “a măsura” datele pentru a recunoaște care dintre ele reprezintă cunoștințe și cateva variante de implementare a unor algoritmi de extragere a acestor informații utile.
Aplicația verifică funcționarea practică a strategiilor de extragere a cunoștințelor prezentate în partea teoretică a lucrării. Pentru aceasta este necesară selectarea unui set de date și a algoritmului dorit. Aplicația oferă posibilitatea vizualizării rezultatelor obținute în cazul diferitelor seturi de date pentru a putea fi mai atent studiate și comparate. De asemenea utilizatorului îi este permisă crearea unui set de date în vederea verificării modului de aplicare și execuție a algoritmilor.
Aplicația ar putea fi utilizată ca un intermediar între diferite alte aplicații, unele care să furnizeze seturile de date și unele care să aibă capacitate decizională.
Studiind atât partea teoretică, cât și cea practică, se ajunge la concluzia că dezvoltarea aplicativă confirmă cele expuse la nivel teoretic și ilustrează în mod corect felul în care se manifestă algoritmii de extragere a cunoștințelor din bazele de date.
7.2. Direcții de dezvoltare
O posibilă variantă de dezvoltare a aplicației practice este cea a parametrizării modulelor pentru diferite structuri ale bazelor de date. De asemenea s-ar putea extinde aplicația pentru a funcționa pe sisteme aflate la distanță.
BIBLIOGRAFIE:
[Zha02] Chengqi Zhang, Shichao Zhang (2002) – “Association Rule Mining – Models and Algorithms”, Ed. Springer Australia
[Zah05] Mihai Horia Zaharia, Aflori Cristian, Șova Ioan, Amarandei Cristian, Florin Leon (2005) – “Prototipul unui sistem GIS WEB inteligent pentru extragerea cunoștințelor din baze de date folosind agenți inteligenți – Raport de cercetare” – Revista de Politica Stiinței și Scientometrie număr special
[Fil06] Filip Ioan (2006) – Tehnologii de programare cu baze de date – note de curs și laborator
[med07] note de curs(2007) – Facultatea de medicină și farmacie “Carol Davila” București – http://www.univermed-cdgm.ro/dwl/DoctCursS_2007.pdf
[apr07] note de curs Sisteme expert și data mining(2007) – Facultatea de Inginerie
Universitatea “Lucian Blaga” din Sibiu – http://webspace.ulbsibiu.ro/daniel.morariu/html/StudentDocs/Apriori.pdf
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Implementarea Unor Algoritmi Pentru Generarea de Cunostinte (ID: 134339)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.