Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload


loading...



















































PROBLEMA DISCRETIZARII PENTRU METODELE MULTIMILOR DIFUZE (ROUGH SETS - RS)

Matematica




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 Va , pentru a A unde Va este numita valoarea multimii lui a. Elementele lui U sunt numite obiecte. O submultime nevida B A defineste un B- functie informatie data de InfB(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 Vd=. Decizia d determina partitia a spatiului U unde Ck= pentru 1 k r(d). Multimea Ck 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 Va. Pentru a A,orice multime de de taieturi pe Va=[la,ra] R defineste o partitie Pa=, unde la= c0a< c0a­<.<ckaa< cka+1a =ra si Va=[c0a,c1a) [c1a ,c2a) [ckaa,cka+1a). De aceea orice multime de taieturi P= n APa defineste un nou tabel de decizii AP=(U,AP ) unde Ap= pentru x U si i

Doua multimi de taieturi P ,P sunt echivalente ,i.e. P AP, daca AP=AP . 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 AP. Multimea taieturilor Pirr, A consistenta, este A ireductibila daca P nu este A consistenta pentru P Pirr. Multimea de taieturi Popt este A- optim daca card(Popt) 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) Bp este de asemenea o reducere relativa in tabelul de decizii distinct AP.

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 CA=Ca1 Ca2 Ca3 unde:

Ca1=

Ca2=

Ca3=

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

1.5), ( a1,2.5), ( a1,3.5), ( a1,4.5), ( a1,5.5), ( a1,6.5), ( a1,7.5),}

P2=

P

A

a1

a2

a3

d

a1P2

a2P2

A3P2

D

u1

u2

u3

u4

u5



u6

u7

u8

u9

u10

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

Se poate observa ca tabelul AP2 va avea ambele reduceri si , dar tabelul AP3 va avea doar reducerea .

4. Rationament Boolean pentru problema separarii

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

Pentru orice obiecte ui, uj U cu d(uI) d(uj) si pentru orice proprietate am A definim multimea de taieturi Cami, j cu urmatoarea distinctie intre ui si uj:

Cami, j=

Notam cu CBi, j unde B A multimea de taieturi cu proprietati din B cu distinctia intre ui si uj data de CBi, j = am B Cami j.

Functia booleana yBi, j functia de distinctie intre ui si uj pe multimea B data de expresia:

yBi, j PBi, j , unde PBi, j este multimea variabilelor boolean corespunzatoare taieturilor CBi, j. Putem spune ca multimea de taieturi P satisface functia yBi, j daca  P CBi, j

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

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

 
FB yBi, j

Spunem ca multimea de taieturi P satisface functia FB daca P satisface functia yBi, j pentru orice i si j cu proprietatea d(ui) d(uj). In lucrari anterioare am considerat functia de distinctie de tip boolean pentru tabelul A definit de FA FA si a fost demonstrat ca orice multime de taieturi este consistenta daca satisface functia FA

Teorema 5

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

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 FA

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 FB introdus in fragmentul anterior si sa definim functia boolean Fs ,astfel incat oricare multime de taieturi optime s, sa corespnda implcatiei Fs ;i.e.

B =s

 
Fs FB

ks

 
Se poate observa ca numarul de conditii yBi, j in functia boolean Fs este egal cu de ori conflict (A)=card=O(n2) 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 Fs are nevoie de O (n2 ) pasi pentru a compila numarul de conditii satisfacute de orice taietura data.

Functia Fs mai poate fi scrisa astfel

d(ui d(uj B =s

 
Fs yBi, j

Pentru orice pereche de obiecte ui , uj astfel incat d(ui d(uj) notam multimea de proprietati care disting uI de uj cu

Ai ,j



Propozitia 7

Daca (|AI,j| k-s+1) atunci |B|=SyI,JB= am AI,j. In consecinta avem teorema numarul 8.

Teorema 8

Fie kI,j=min. Atunci multimea de taieturi P satisface functia Fs daca pentru orice pereche de obiecte uI, uj astfel incat d(ui) d(uj), sunt kI,j proprietati am1,., amki,j astfel incat P sa satisfaca toate functiile ym1I, j ymki,jI, j ie P CmiI,j pentru i=1,.kI,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 Fk . Principala idee a acestei metode este bazata pe constructia si analiza unui nou tablel de decizii.

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

U*=

A*=, unde c((ui,uj))= 1 daca c discerne ui de uj

0 in rest

Tabloul consta in O(nk) proprietati (taieturi) si O(n2) 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 kij si multimea proprietatilor de diferentiere Lij:= in care fiecare pereche de obiecte (ui,uj) u* (vezi teorema 8). Apoi cautam o taietura (a,c). Eliminam perechi din U* astfel incat (ui,uj) cu Lij =kij. Algoritmul se continua pana cand U*=

A*

a1

a2

a3

(u1,u2)

(u1,u3)

(u1,u4)

(u1,u6)

(u1,u7)

(u1,u8)

(u2,u3)



(u2,u5)

(u3,u4)

(u8,u10)

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 kij pentru toate perechile (ui,uj) U* (vezi teorema 8) sunt egale cu 2 exceptand k34=1. Algoritmul incepe cu alegerea celei mai bune taieturi (a3,4.0) distingand 20 de perechi de obiecte din A. In pasul urmator va fi aleasa taietura (a1,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. (u1,u6), (u1,u7) (u1,u8), (u2,u5),.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 P2, 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

REZUMAT

Aceasta lucrare descrie pachetul de SOFTWARE intitulat ROSE. Este un sistem interactiv modular realizat pentru analiza si descoperirea informatiei bazat pe teoria multimilor brute (R.S.) aplicate la computerele P.C.

El implementeaza teoria clasica a multimilor brute pe masura ce expansiunea lui s-a bazat pe modele variate de precizie. El include generatia de reguli decizionale pentru clasificarea sistemelor si descoperirea informatiilor.

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.



loading...








Document Info


Accesari: 1823
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate

Copyright © Contact (SCRIGROUP Int. 2020 )