Partitii nuantate fuzzy

Concepte

Notiunea de multime nuantata, introdusa la mijlocul anilor 60 de catre L. A. Zadeh, reprezinta o generalizare naturala a conceptului clasic de multime. Ideea de la care s-a plecat a fost ca exista multe clase de obiecte care nu au granite nete.

Astfel de clase pot fi descrise utilizand multimi nuantate, care admit grade de aparenta situate intre 0 (neapartanenta totala) si unul (aparenta totala).

Definitie

O multime fuzzy (nuantata) peste o multime X nevida este o aplicatie

A : X

Caracteristici

A(x) desemneaza gradul de aparenta a lui x la multimea nuantata A. Se poate interpreta A(x) ca fiind gradul de plauzibilitate al afirmatiei ' x este un element din A'.

Complementarea unei multimi nuantate A(x) se defineste prin

si reprezinta cat de plauzibila este afirmatia ' x nu este un element a lui A'.

Daca L(X) este familia tuturor multimilor nuantate peste X atunci:

- (AUB)(x)=min(A(x)+B(x),1)

(AUB)(x)=max(A(x)+B(x)-1,0)

Multimile fuzzy A₁, , A_n ,n³ sunt disjuncte daca

j =1,.,n-1

Aceste multimi reprezinta o partitie finita nuantata a lui C din L(X) daca C=. Fiecare A_i se va numi atom al partitiei.

Daca A este o multime fuzzy peste X si tI atunci

A^t=

se numeste multime de nivel t a lui A.

Daca y este din X si a este un numar cu aI atunci multimea fuzzy definita prin

se numeste punct fuzzy(nuantat). Un punct fuzzy apartine unei multimi fuzzy A daca si numai daca pentru orice x din X.

Daca M si N sunt doua multimi clasice din spatiul metric, distanta dintre ele este

D(M, N) = inf(x, y) xIM , yIN

Daca A si B sunt doua multimi fuzzy, A, BIL(x) distanta dintre acestea este data de:

D(A, B)=

Distanta dintre un punct fuzzy si multimea A este

Distanta dintre doua puncte fuzzy si este

sau

Diametrul unei multimi fuzzy se defineste ca fiind numarul

Clasificare cu partitii fuzzy. Principii

Procesul de clasificare poate fi considerat ca fiind o operatie prin care o multime X de date este structurata in categorii semnificative. Admitem ca o categorie corespunde unei grupari, nor sau cluster, de puncte (obiecte), din X. In acest context submultimile lui X vor putea fi echivalate cu clase de obiecte. Problema determinarii categoriilor naturale si semnificative de obiecte din X revine asadar la detectarea structurii de clusteri ai multimii X. Dupa cum s-a mai amintit, clasele de obicte reale se pot suprapune partial si sau se pot interpatrunde. Daca un obiect cu caracteristici hibride este asigurat unei clase, comitem o eroare, care se traduce printr-o pierdere de informatie relativa la obiectul respectiv.

Rezulta ca existenta punctelor hibride sau izolate, a claselor care nu sunt separabile, constitue surse de ambiguitate si erori in procesul de clasificare. O metoda prin care putem face fata acestei ambiguitati este sa consideram clasele de obiecte ca fiind descrise de multimi fuzzy. In aceasta situatie un obiect va apartine simultan tuturor claselor de obiecte .

Daca un obiect face parte din nucleul unei clase, atunci gradul lui de apartenenta la acea clasa va fi aproape de 1 si apartenenta la celelalte clase neglijabila. Aceasta abordare este in concordanta cu faptul ca multe clase de obiecte reale nu au granite precise. Clasificarea obtinuta se va potrivi mai bine pe adevarata structura a datelor.

In multe probleme de clasificare ne intereseaza nu doar o clasificare a datelor ci si obtinerea unor prototipuri ale claselor. Prototipurile sunt elemente semnificative ale claselor sau valori tipice ale acestora. Prototipurile pot consta din puncte (valoarea medie, centrul de greutate a unei clase), puncte si drepte, combinatii de drepte, varietati liniare etc. In cazul in care nu avem informatii privind forma geometrica a claselor putem utiliza ca prtotip al unei clase o submultime a obiectelor de clasificat.

Functia criteriu. Algoritmul n-medii fuzzy

In continuare vom admite ca structura de clusteri a unei multimi de obiecte este descrisa de o partitie nuantata. Un atom al partitiei se va identifica cu o clasa de obiecte.

Fie o multime de obiecte, si partitia fuzzy care ne da numarul de clase in care este structurat . Fiecare multime fuzzy (atom) descrie o clasa de puncte. Daca admitem pentru acesti clusteri o forma de hipersfere, putem considera prototipul clasei ca fiind un punct, si anume centrul clusterului respectiv. Notam cu prototipul clasei .

Pentru a determina structura de clusteri a lui vom construi o functie criteriu folosind o masura de disimilaritate peste . Vom alege aceasta masura ca fiind patratul unei matrici d. Atunci disimilaritatea dintre un obiect si prototipul clase se va exprima in functie de o metrica locala indusa de distanta si . In constructia functiei criteriu va interveni deci o familie de n distante locale.

Fie si d o metrica pe . Metrica locala indusa de d si de multimea se defineste:

(5.1)

Disimilaritatea dintre un punct si prototipul al clasei se defineste ca fiind:

(5.2)

Si se interpreteaza drept o masura a inadecvarii reprezentarii punctului x^y prin prototipul .

Deoarece este unul din punctele lui (chiar daca este artificial construit) este plauzibil sa presupunem ca dintre toate punctele multimi , are mai mare grad de apartenenta la clasa fuzzy pe care o reprezinta. Deci:

(5.3)

Rezulta ca:

Asadar disimilaritatea dintre si este data de:

(5.4)

Masura a inadecvarii reprezentarii clasei prin prototipul se defineste prin:

(5.5)

sau inlocuind (4) rezulta:

(5.6)

Important

-O partitie fuzzy se poate reprezenta printr-un matrice A cu n linii si p coloane, unde:

Vom nota cu multimea acestor matrici cu elemente in [0,1] si suma elementelor fiecarei coloane egale cu 1.

-Inadecvarea reprezentarii partitiei fuzzy prin se poate exprima cu ajutorul unei functii:

y: x de forma:

(5.7).

Problema de clasificare revine la determinarea partitiei fuzzy P si a reprezentarii pentru care inadecvarea J(P,k) este minima, adica la rezolvarea urmatoarei probleme de minim:

(5.8)

Intuitiv, a minimiza J inseamna a cere grade de apartenenta mici la pentru acele puncte din pentru care disimilaritatea dintre punctul respectiv si prototipul clasei este mare. Grade de apartenenta mari sunt reclamate de punctele pentru care disimilaritatea este mica.

Deoarece nu exista o metoda pentru rezolvarea exacta a lui (5.8) se recurge la o metoda aproximativa pentru determinarea unei solutii locale. Problema se rezolva folosind o metoda iterativa in care J se minimizeaza succesiv in raport cu P, respectiv L. Pornind de la o partitie P¹ arbitrara se construieste o reprezentare L¹ pentru care functia J(P¹,) are valoare minima. Se cauta apoi o noua partitie P² care sa minimizeze functia J(). Se obtine un sir de partitii fuzzy si un sir de reprezentari ale acestor partitii. Procesul se opreste cand norma diferentei dintre doua partitii succesive este suficient de mica.

Teorema

Minimul functiei este realizata de partitia fuzzy cu

(5.9)

Minimul functiei este realizata de cu:

(5.10)

in care (A₁,.,A_n) este o partitie nuantata a lui X daca si numai daca

(5.11)

Algoritmul n-medii FUZZY (FUZZY/ISODATA)

P1. Se alege o partitie arbitrara a lui X.

P2. Se calculeaza prototipurile acestei partitii cu formula

P3. Se determina o noua partitie P² ai carei atomi sunt dati de formula

P4. Daca atunci STOP. In caz contrar se pune si se merge la pasul P2.

Comentarii

O valoare adecvata pentru este 10^-5.

Cazul este putin probabil sa apara. In aceasta situatie vom pune:

Interpretarea unei partitii fuzzy

Partitia fuzzy rezultata in urma procesului de informatie privind apartenenta punctelor la clasele stabilite. Aceasta informatie poate fi in intregime utila, dar uneori greu de interpretat. Cel putin pentru o analiza preliminara a rezultatelor este necesar sa convertim partitiile clasice. O partitie clasica ce aproximeaza partitia nuantata, chiar daca este mai saraca in determinari poate oferi o imagine suficient de fidela asupra structurii datelor. Practic, aceasta problema se poate rezolva atasind fiecare punct clasei la care are gradul de apartenenta maxim . Cu alte cuvinte, daca este o partitie fuzzy, construim partitia clasica punand (1)

O alta posibilitate, mai putin intuitiva, de a obtine o partitie clasica este de a se cauta descompunerea partitiei fuzzy in partitii clasice. Termenul descompunerii avind coeficientul maxim este considerat ca fiind partitia clasica ce reprezinta cel mai bine partitia fuzzy data. Am putea vorbi de descompunerea convexa a unei partitii identificind o partitie cu o matrice [A] unde .

Consideram notatiile

(2)

(3)

unde definesc multimea matricilor clasice nedegenerate si --------- Se pune problema unei caracterizari complete a multimii . Aceasta caracterizare ne-ar furniza o conditie necesara si suficienta pe care trebuie sa o indeplineasca o partitie fuzzy pentru a se putea scrie sub forma unei combinatii convexe de partitii clasice nedegenerate.

Teorema

Daca atunci urma toarele conditii sunt echivalente

(1) (2)

Demonstratie.Se va demonstra implicatia (1)

Daca ,atunci exista si astfel incat

Deoarece matricile corespund la partitii clasice nedegenerate rezulta ca:

si deci:

Putem atunci scrie

Concluzie

Partitia admite asadar o descompunere convexa nedegenerata daca si numai daca pentru oricare .

Exemplu

Consideram partitia fuzzy reprezentata prin matricea

Suma elementelor fiecarei linii este mai mare decat 1 deci, conform teoremei enuntate mai sus matricea A admite descompunerea convexa:

Rezulta ca este aproximata prin partitia clasica avand coeficientul 0.3.Aceasta partitie este:

, ,