PROBLEMA DISCRETIZARII PENTRU METODELE

MULTIMILOR DIFUZE (ROUGH SETS - RS)

REZUMAT

Studiem relatia dintre problema micsorarii in teoria multimilor brute si problema separarii proprietatilor cu valoare reala. Luam in discutie problema cautarii unei multimi minime de taieturi a domeniilor de proprietati care pastreaza distingerea elementelor, oricare ar fi submultimea de proprietati aleasa cu cardinalul s (unde s este un parametru dat de utilizator). O asemenea procedura se separare (micsorare) permite sa se pastreze toate reducerile care contin cel putin s proprietati. Aratam ca ceasta problema de optimizare este un hard NP si este interesant de gasit metode euristice eficiente pentru a rezolva aceasta problema.

1. INTRODUCERE

Discretizarea proprietatilor reale este o cerinta importanta in explorarea datelor, in special pentru problema clasificarii. Rezultatele empirice arata ca aceasta calitate a metodelor de clasificare depinde de algoritmul de separare (reducere) folosit in etapa de preprocesare. In general, discretizarea (micsorarea) este un proces in care se urmareste impartirea domeniilor de proprietati pe intervale si unirea valorilor pe fiecare interval. Din acest motiv problema discretizarii poate fi definita ca o problema de cautare a unei multimi potrivite de taieturi (capetele de interval) pe domeniile de prop 242v2115c rietati.

De obicei cautam mutimi consistente de taieturi i.e. pastrand relatia de corespondenta intre obiecte din clase de decizie diferite [10,8]. In lucrari anterioare am analizat problema cautarii partilor de multime consistente si optime unde criteriile de optimizare erau diferite de numarul de taieturi (problema OD). A fost demonstrat ca o asemenea problema de optimizare a fost NP-hard [8]. Orice algoritm de discretizare reduce informatia din tabelele de decizie. Metoda noastra euristica pentru problema OD numita algoritmul MD produce o noua reprezentare diagramatica a unui algoritm (un nou tabel de decizie) cu numai o singura reducere. In cateva aplicatii bazate pe RS (ex. reducerea dinamica si metoda dinamica[1]), unde reducerile sunt un instrument important, nu este suficient sa obtii regulile (liniile) puternice.

Din acest motiv, intr-un anumit sens , am vrea sa obtinem mutimi de parti mai mari care sa produca un nou tabel de decizie micsorat care sa contina mai multe partitii si in acelasi timp care sa reduca informatia excedentara (superflua). In aceasta lucrare consideram problema cautarii de mutimi minimale de taieturi atat de importanta incat "salveaza" (pastreaza) distigerea intre obiecte in ceea ce priveste orice multime cu s proprietati.

Se poate arata ca aceasta problema numita problema separarii (partitionarii) optimale- s (s- problema OD) este totodata NP-hard, unde algorimul euristic este mai complicat decat in cazul problemei OD. Asemanator cu cazului problemei OD, noi propunem metoda bazata pe rartionare booleana pentru a rezolva problema OD-s.

2. PRELIMINARII

Un sistem informational [11] este o pereche de forma A=(U,A) , unde U este o multime nevida finita numita spatiu iar A este o multime finita de proprietati , i.e. a:U V_a , pentru a A unde V_a este numita valoarea multimii lui a. Elementele lui U sunt numite obiecte. O submultime nevida B A defineste un B- functie informatie data de Inf_B(x)=.

Pentru orice submultime de proprietati , B A o relatie echivalenta numita B-relatia de nedistinctie [11] notata IND(B) este definita de

IND(B)=

Elementele x, y care satisfac relatia IND(B) sunt nedistincte prin prisma proprietatilor B. Prin [x]_IND(B) notam clasa echivalenta a lui IND(B) prin x. O submultime minima (in sens de incluziune) a lui B cum ar fi IND(A)= IND(B) este numita o reducere a lui A.

Orice sistem de informatii de forma A=(U,A ) este numit un tabel de decizii unde d A este numit decizia si elementele lui A sunt numite conditii. Fie V_d=. Decizia d determina partitia a spatiului U unde C_k= pentru 1 k r(d). Multimea C_k este numita a k-a decizie a clasei de obiecte A.

Pentru orice submultime de proprietati B A definim o relatie echivalenta B-relatia de nedistinctie si notata IND(B,d) dupa cum urmeaza:

IND(B,d)=

O submultime minima a lui B (in sensul de incluziune) cu proprietati din A cum ar fi IND(A,d)=IND(B,d) este numita restrictie relativa a lui A.

Fie A=(U,A ) un tabel de decizii si B A. Definim o functie _B:U 2 ,numita generalizarea deciziei in A, cu _B(x)=d([x]_IND(B)). Un tabel de decizii A este consistent (deterministic) daca card( _A(x))=1 pentru " x U. Altfel A este neconsistent (non-deterministic).

3. PROBLEMA DE OPTIMIZARE A RESTRICTIILOR

Fie A=(U,A ) un tabel de decizii unde U=; A= si d:U . Orice pereche (a,c) unde a A si c se numeste o taietura pe V_a. Pentru a A,orice multime de de taieturi pe V_a=[l_a,r_a] R defineste o partitie P_a=, unde l_a= c₀^a< c₀^a_­<.<c_ka^a< c_ka+1^a =r_a si V_a=[c₀^a,c₁^a) [c₁^a ,c₂^a) [c_ka^a,c_ka+1^a). De aceea orice multime de taieturi P= _{n A}P_a defineste un nou tabel de decizii A^P=(U,A^P ) unde A^p= pentru x U si i

Doua multimi de taieturi P ,P sunt echivalente ,i.e. P _AP, daca A^P=A^P . Relatia echivalenta _A are un numar finit de clase echivalente. In continuare nu vom face distinctie intre multimi echivalente de taieturi. Multimea de taieturi P este A consitent daca _{A= A^P} unde _A si _A^P sunt deciziile generalizate ale lui A si recpectiv A^P. Multimea taieturilor P^irr, A consistenta, este A ireductibila daca P nu este A consistenta pentru P P^irr. Multimea de taieturi P^opt este A- optim daca card(P^opt) card(P) pentru orice multime de taieturi.

Definitia 1

Multimea de taieturi P se numeste s-consistenta cu A (sau s-consistenta in micsorare) unde 1 s card(A) daca pentru orice subtabel de decizii B=(U, B ) cu s proprietati conditionate, multimea de taieturi P (B ) B-consistent.

Multimea de taieturi l-consistent va fi numita local consistenta si multimea de taietri k-consistenta (unde k=card(A)) va fi nmita pur si simplu consistenta .

Definitia 2

Multimea s-consistenta de taieturi P este numita s-ireductibila daca Q nu este s-consistenta pentru orice submultime potrivita Q P.

Definitia 3

Multimea de taieturi P este numita s-optima daca card(P) card(Q)pentru orice multime de taieturi s- consistenta.

Cand s=k=card(A), in loc de a spune ca multimea de taieturi este k-ireductibila sau k-optima spunem ca este ireductibila sau optima. Aratam ca orice multime de taieturi s- consistenta salveaza toate reducerile relative cu cardinal cel putiin egal cu s in urmatorul sens:

Propozitia 4

Daca P este o multime de taieturi de consistenta s in tabelulde decizii A=(U,A ) atunci pentru orice reducere relativa B din A B s multimea de proprietati individuale (discretizate) B^p este de asemenea o reducere relativa in tabelul de decizii distinct A^P.

Ilustrarea conceptelor se afla in Tabelul 1. Se poate vedea ca toate reducerile relative din tabelul 1 sunt egale cu R=,}. Multimea tuturor taieturilor posibile este egala cu C_A=C_a1 C_a2 C_a3 unde:

C_a1=

C_a2=

C_a3=

Multimea de taieturi s-optima pentru s=1,2,3 este urmatoarea:

1.5), ( a₁,2.5), ( a₁,3.5), ( a₁,4.5), ( a₁,5.5), ( a₁,6.5), ( a₁,7.5),}

P₂=

P

Tabel 1. Tabel de decizie cu 10 obiecte, trei proprietati si trei clase de  decizii. Tabelul discretizat A^P2 este prezentat in partea dreapta.

Se poate observa ca tabelul A^P2 va avea ambele reduceri si , dar tabelul A^P3 va avea doar reducerea .

4. Rationament Boolean pentru problema separarii

Fie un table de decizii A=(U,A ) unde U= si A=. Notam cu C_am= multimea tuturor taieturilor posibile cu proprietatea a_m pentru m=1,.,k si cu P_am= multimea de variabile de tip boolean care le corespunde.

Pentru orice obiecte u_i, u_j U cu d(u_I) d(u_j) si pentru orice proprietate a_m A definim multimea de taieturi C_am^{i, j} cu urmatoarea distinctie intre u_i si u_j:

C_am^{i, j}=

Notam cu C_B^{i, j} unde B A multimea de taieturi cu proprietati din B cu distinctia intre u_i si u_j data de C_B^{i, j} = _{am B} C_am^{i j}.

Functia booleana y_B^{i, j} functia de distinctie intre u_i si u_j pe multimea B data de expresia:

y_B^{i, j} P_B^{i, j} , unde P_B^{i, j} este multimea variabilelor boolean corespunzatoare taieturilor C_B^{i, j}. Putem spune ca multimea de taieturi P satisface functia y_B^{i, j} daca  P C_B^{i, j}

Functia de distinctie boolean pentru multimea de proprietati B este definita de

d(ui d(uj) d(ui)d(ui

F_B y_B^{i, j}

Spunem ca multimea de taieturi P satisface functia F_B daca P satisface functia y_B^{i, j} pentru orice i si j cu proprietatea d(u_i) d(u_j). In lucrari anterioare am considerat functia de distinctie de tip boolean pentru tabelul A definit de F_A F_A si a fost demonstrat ca orice multime de taieturi este consistenta daca satisface functia F_A

Teorema 5

Multimea de taieturi P este optima daca multimea de variabile de tip boolean corespunzatoare lui P este o implicatie principala a lui F_A

Acest fapt ne permite sa construim un algoritm eficient cautand multimi de taieturi semioptime aplicand aproximarea algoritmului (algoritmul lacom) pentru prelucrarea implicatiei principale a functiei F_A

5. Proprietati si generalizari

In acest capitol analizam posibilitatile interesante ale unei multimi de taieturi de consistenta s.

Pentru inceput discutam depre complexitatea optimizarii problemei in legatura cu multimea de taieturi optima s.

Teorema 6

Pentru orice tabel de decizii dat A=(U,A ) si un parametru intreg s, problema cautariiunei multimi de taieturi optime s este:

1. DTIME (kn log n) pentru s=1;

2. NP-hard pentru orice s

Demonstratie:

Afirmatia 1. este evidenta. Pentru a demonstra 2. amintim urmatoarea teorema[5]: Problema cautarii unei multimi optime de taieturi in tabelele de decizii cu doua conditii de proprietati este NP-hard.

Sa generalizam F_B introdus in fragmentul anterior si sa definim functia boolean F_s ,astfel incat oricare multime de taieturi optime s, sa corespnda implcatiei F_s ;i.e.

B =s

F_s F_B

ks

Se poate observa ca numarul de conditii y_B^{i, j} in functia boolean F_s este egal cu de ori conflict (A)=card=O(n²) fiind numarul de perechi

k s

de obiecte cu diferite valori de decizii. De aceea orice algoritm lacom care cauta o reducere minima a functiei F_s are nevoie de O (n² ) pasi pentru a compila numarul de conditii satisfacute de orice taietura data.

Functia F_s mai poate fi scrisa astfel

d(ui d(uj B =s

F_s y_B^{i, j}

Pentru orice pereche de obiecte u_i , u_j astfel incat d(u_i d(u_j) notam multimea de proprietati care disting u_I de u_j cu

A_{i ,j}

Propozitia 7

Daca (|A_I,j| k-s+1) atunci |B|=Sy^I,J_B= a_m A_I,j. In consecinta avem teorema numarul 8.

Teorema 8

Fie k_I,j=min. Atunci multimea de taieturi P satisface functia F_s daca pentru orice pereche de obiecte u_I, u_j astfel incat d(u_i) d(u_j), sunt k_I,j proprietati am₁,., am_ki,j astfel incat P sa satisfaca toate functiile y^m1_{I, j} y^mki,j_{I, j} ie P C^mi_I,j pentru i=1,.k_I,j.

Ultima teorema spune ca se poate folosi un algoritm de individualizare mai eficient decat algoritmul "greedy", algoritm care va fi prezentat in capitolul urmator. Concluzionam cu faptul ca consistenta s este monotona in ceea ce priveste s. In particular acest lucru inseamna ca multimea de taieturi s optima se poate reduce pentru a se obtine (s+1) multimi de taieturi.

Propozitia 9

Pentru oricarte tabel de decizii A=(U,A ), card(A)=k si pentru orice intreg s , daca multimea de taieturi P este consistenta s cu A, atunci P este de asemeni consistenta (s+1) cu A.

Algoritmul framework

In lucrarile precedente [8,9] am prezentat algoritmul de individualizare numit MD (de maxim discernamant) euristic pentru problema de individualizare total optimizata (k optimal). Aceasta are o versiune de algoritm greedy aplicat functiei booleene F_k . Principala idee a acestei metode este bazata pe constructia si analiza unui nou tablel de decizii.

A^*=(U^*,A^*), unde

U^*=

A^*=, unde c((u_i,u_j))= 1 daca c discerne u_i de u_j

0 in rest

Tabloul consta in O(nk) proprietati (taieturi) si O(n²) obiecte (vezi tabelul 2). Notam cu Disc(a,c) gradul de diferentiere a taieturii (a,c) care este definit ca numar de perechi de obiecte din diferite clase de decizii (sau numarul de obiecte in tabelul A^*) diferentiat prin c. Algoritmul euristic MD cauta o taietura (a,c) A^* cu cel mai mare grad de diferentiere Disc(a,c). Atunci mutam taietura (a,c) din A^* si o atribuim multimii de taieturi P si eliminam din U^* toate perechile de obiecte differentiate de c. Algoritmul se continua pana cand U^*= . Am demonstrat in [9] ca MD euristic este foarte efficient, pentru a determina cea mai buna taietura in O(kn) utilizand numai O(kn) spatii.

Putem modifica acest algoritm in problema discretizarii s optima aplicand teorema 8. La inceput dam numarul cerut de taieturi k_ij si multimea proprietatilor de diferentiere L_ij:= in care fiecare pereche de obiecte (u_i,u_j) u^* (vezi teorema 8). Apoi cautam o taietura (a,c). Eliminam perechi din U^* astfel incat (u_i,u_j) cu L_ij =k_ij. Algoritmul se continua pana cand U^*=

Tabelul 2. Un fragment al tabelului temporar A^* construit din din A

In figura 1 aratam toate taieturile posibile pentru tabelul de decizie A (prezentat in Tabelul 1). Tabelul A^* (vezi Tabelul 2) consta in 33 de perechi de obiecte de clase de decizie diferite. Pentru s=d, numarul de taieturi cerute k_ij pentru toate perechile (u_i,u_j) U^* (vezi teorema 8) sunt egale cu 2 exceptand k₃₄=1. Algoritmul incepe cu alegerea celei mai bune taieturi (a₃,4.0) distingand 20 de perechi de obiecte din A. In pasul urmator va fi aleasa taietura (a₁,3.5) pentru ca 17 perechi de obiecte sunt differentiate de aceasta taietura. Dupa aceast pas pot fi eliminate 9 perechi de obiecte din U* e.g. (u₁,u₆), (u₁,u₇) (u₁,u₈), (u₂,u₅),.pentru ca ele date de 2 taieturi cu proprietati diferite. Cand algoritmul se opreste putem elimina cateva taieturi suplimentare pentru a obtine multimea de taieturi P₂, prezentata in sectiunea 3.

Fig.1 Ilustrarea taieturilor din tabelul A. Obiectele sunt marcate cu etichete in functie de valorile lor de decizie

Concluzie: am prezentat metoda de discretizare cu referire la distinctia dintre obiecte si parti relative cu numar de elemente mai mare decat s, pentru un parametru s dat de utilizator. Am propus o metoda de rezolvare a acestei metode bazandu-ne pe abordarea rationamentelor booleene.

ROSE - IMPLEMENTAREA SOFTWARE PE BAZA
TEORIEI MULŢIMILOR DIFUZE

INTRODUCERE. ROSE (Rough Set Data Explorer) este un sistem software modular care implementeaza elementele de baza ale teoriei multimilor brute si tehnici de reguli ale descoperirii. A fost creat în Laboratorul Sistemelor Suport de Inteligenta Decizionala al Institutului de stiinte Informationale în Poznan, bazându-se pe 14 ani de experienta în domeniul teoriei multimilor brute bazata pe descoperirea informatiei si analiza decizionala.

Toate compilatiile sunt bazate pe multimile brute fundamentale introduse de Z. Pawlah [6]. Una dintre expansiunile implementate aplica modelul multimilor brute de precizie variabila definit de W. ZIARKO [14]. Este utilizat în mod deosebit în analiza multimilor de date cu regiuni mari - de limita.

Sistemul ROSE este un succesor al sistemelor ROUGH DAS si Rough Class [3] [5] [10]. Rough Das este din punct de vedere istoric una dintre primele implementari de succes ale teoriei brute a multimilor, care a fost utilizat în multe aplicatii din viata cotidiana.

Datorita limitelor sistemului Rough Das, în special incapacitatea de a utiliza pe deplin computerele disponibile, era necesar sa se realizeze si sa se implementeze un nou software. Rose a debutat sub forma câtorva module separate care mai târziu au fost reunite într-un singur sistem. Mai întâi am fost motivati sa cream ingineria procesarii lucrând pe computere mai performante (e.g. statiile de lucru UNIX) care sa permita analiza mai rapida a unor mari multimi de date. Apoi am ajuns în punctul în care sa cream un program cât mai accesibil utilizatorului si atunci am ales MICROSOFT WINDOWS ca platforma de baza.

Asa ca modulele pot fi reconstruite separat si reprocesate fara prea multa interventie din partea utilizatorului. Singurul component care este strict dependent de platforma de baza este interfata grafica utilizata (GUI). Toate acestea sunt garantii pentru usoara sa adaptabilitate pentru sisteme de operare si platforme în viitor.

Programul ROSE este un sistem software interactiv care functioneaza sub 32 BIT GUI în sistemele de operare (WINDOWS 95/NT) pe mecanisme P.C. compatibile.

Modulele de centru au fost scrise în limbajul de programare C++ (cu bibliotecile OBJECT WINDOWS) si BORLAND DELPHI.

Sistemul consta într-un utilizator grafic de interfata (GUI) si o multime de module de computer separate.

Modulele sunt independente la nivel de platforma si pot fi procesate pentru diferite scopuri incluzând si mecanismele UNIX GUI actioneaza cu acoperire pe toate modulele informationale. De aceea este destul de usor de adaugat noi module la sistemul Rose si aceasta este o calitate importanta. Acest lucru garanteaza o expansiune mai mare în viitor.

ROSE este construit astfel încât sa poata fi usor de utilizat pe sistemul POINT AND CLICK, condus prin MENIU, unealta accesibila pentru utilizator în vederea explorarii si analizei de date. Este destinat atât expertilor cât si utilizatorilor amatori care vor sa faca analiza de date. Sistemul comunica cu utilizatorii folosind ferestre de dialog si toate rezultatele sunt reprezentate în mediul înconjurator.

Datele pot fi editate folosind o suprafata de întindere pe post de interfata.

INPUT/OUTPUT DATA

ROSE accepta datele intrate sub forma unui tabel în care liniile corespund obiectelor (cazuri, observatii etc.) si coloanele corespund caracteristicilor acestora. Caracteristicile sunt împartite într-o multime disjuncta de trasaturi conditionale si trasaturi decizionale, prima categorie implicând rezultatele diverselor teste iar a doua apartenenta în clase, cu alte cuvinte categorisirea lor. Datele sunt stocate într-un fisier foarte clar conform unei sintaxe definite (I.S.F.). ROSE poate de asemenea sa introduca date stocate de predecesorul sau Rouch Das si sa o exporte altor câteva formaturi (incluzând fisiere acceptate de sistemul LERS).

Specificatia fisierului ISF permite existenta numelor lungi de atribute (pâna la 30 de caractere alfanumerice) si a sirurilor de caractere ca si valori ale atributelor (cum ar fi "high" si "low") pe lânga valori reale si întregi. Pentru ca este un fisier text simplu poate fi transferat între diferite sisteme de operare fara modificari. Este de asemenea simpla editarea si verificarea corectitudinii datelor continute în fisier.

Formatul fisierului are o structura deschisa. Este divizat în sectiuni si este posibila adaugarea unor noi sectiuni pâna atunci nedefinite pentru utilizare ulterioara. Utilizatorul poate ignora unele dintre atribute doar schimbând tipul (calificarea) atributelor.

Exceptând vizualizarea în GUI toate rezultatele sunt de asemenea scrise în fisiere texte simple, asa încât ele pot fi citite si în afara sistemului, si usor convertite în alte formate de fisier.

TRĂSĂTURI

Trasaturile oferite în mod curent de modulele de calcul includ:

validarea si preprocesarea datelor

discretizarea automata a atributelor evaluate în mod continuu în functie de metoda Fayyod si Irani precum si discretizarea condusa de utilizator

estimare calitativa a capacitatii atributelor de a aproxima clasificarea obiectelor, utilizând extensia de model Rouch Set standard sau de model cu precizie variabila

gasind miezul (esenta) atributelor si cautând reduceri în tabelul informational (ori toate reducerile ori o populatie de reduceri de marime predeterminata) folosind câteva metode ca algoritmul lui S. Romansky si algoritmul modificat al lui A. Skowron [8]

examinarea semnificatiei (importantei) relative a unui atribut dat în clasificarea obiectelor, observând schimbarile în calitatea clasificarilor

reducerea atributelor inutile si selectând cele mai importante atribute pentru clasificarea obiectelor; sunt disponibile câteva tehnici care sustin alegerea (varianta). O submultime de atribute asigurând o calitate satisfacatoare a clasificarii (ex. tehnica adaugarii celor mai discriminatorii atribute la mediu)

inducerea regulilor de decizie folosind ori algoritmul LEM2 [2] ori algoritmul Explore [4][13]

postprocesarea regulilor induse, ex. reducerea (eliminarea); cautarea de reguli interesante în concordanta cu interogarile definite de utilizator

folosirea (aplicarea) regulilor de decizie pentru clasificarea noilor obiecte folosind diferite tehnici de potrivire a regulilor, în particular o abordare originala bazata pe relatia de apropriere evaluata

evaluarea seturilor de reguli de decizie utilizând tehnica de validare încrucisata k-fold.

Va fi destul de usor sa se adauge noi module sistemului datorita arhitecturii sale deschise.

REMARCI FINALE

În viitorul apropiat planuim sa adaugam noi capacitati (posibilitati) sistemului nostru, cum ar fi generatia de incrementare prin reducere, lucrul cu tabele informationale incomplete, lucru cu relatii de semiclaritate pentru aproximari grosiere, lucrul cu relatii de dominanta (conducere) pentru aproximare grosiera a problemelor de clasificare pe mai multe criterii, lucrul cu relatii de dominanta si cu tabele de comparatie pe perechi a alegerii pe criterii multiple pentru aproximare grosiera si problem de clasificare.

Sistemul ROSE precum si predecesorul sau Rough Das au fost aplicate la multe seturi de date din viata reala. Referintele la aceste aplicatii sunt date, de exemplu în [5]. Câteva dintre cele mai importante domenii de aplicare sunt medicina, farmacia, diagnostice tehnice, stiinta finantelor si a managementului, analiza imaginii si a sunetului, geologie, evaluarea proiectului software.