grupare clasificare fuzzy

Click here to load reader

Post on 20-Jan-2016

53 views

Category:

Documents

0 download

Embed Size (px)

DESCRIPTION

Gruparea (si clasificarea)fuzzya datelor

TRANSCRIPT

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Gruparea (si clasificarea)fuzzy a datelor

    IntroducereAspecte teoretice generale Gruparea tranantMetode fuzzy FCM SC

    Utilizarea metodelor fuzzy n matlab. Exemplificare

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Introducere (1) Obiectivul gruprii datelor:

    mprirea setului de date n grupuri (clustere, clase) de date similare

    Scopul gruparii este de a identifica grupurile naturale de date dintr-unset mare de date care reprezint comportarea unui sistem.

    Exemple de obiecte de grupat (clasificat, recunoscut): clientii unei banci, email-uri,zone de interes din imagini, persoane sanatoase sau bolnave, sortimente de vin, clasede flori, regiuni ale unor functii neliniare multivariabile, etc.

    mpartirea in grupuri se realizeaz pe baza unei mulimi de trsturi(caracteristici, atribute, proprietati) ce descriu fiecare form sau obiect (ex. pentruflorile de iris: latimea si lungimea sepalei si latimea si lungimea petalei)

    n practica pot exista un numr mare de obiecte de grupat (eantioane) descriseprin mai multe trasaturi gruparea automat a datelor

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Gruparea este una dintre metodele utilizate la identificarea sistemelor, adic dezvoltarea unui model al funcionrii sistemului cunoscnd seturi de date intrare-ieire.

    Gruparea este o metoda fundamentala de analiza a datelor. Este utilizata extensiv pentru recunoasterea formelor, extragere de caracteristici,cuantizarea vectorilor, segmentarea imaginilor, aproximarea functiilor si datamining. In actiunea de grupare a datelor nu avem la dispozitie valoarea dorita a iesirii,asadar gruparea datelor utilizeaz metode de invare nesupervizat:

    identifica anumite structuri inerente prezente intr-un set de obiecte, pe bazaunei masuri de similitudine.

    Introducere (2) Rezultatul gruprii: o structura fixa a datelor

    centrul grupurilor (localizarea grupurilor) forma grupurilor gradul de apartenent al fiecarui obiect la fiecare grup

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    mprirea datelor trebuie sa aiba doua caracteristici:

    omogenitate in grupuri; obiectele din acelasi grup trebuie sa fie cat se poate de asemanatoare ntre ele

    eterogeneitate intre grupuri; obiectele din grupuri diferite sa fie cat se poate de diferite unele de altele

    cea mai potrivita masura a similitudini dintre obiecte este distanta dintre obiecte, de exemplu distanta euclidiana

    Exemplu de grupare in spatiul bidimensional

    Introducere (3)

    grupare

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Introducere (4)

    Gruparea datelor (clustering) este procesul de descoperire agrupurilor si structurilor de date care sunt similare din intregul setul dedate, fara a utiliza structuri de date cunoscute apriori.

    mprirea obiectelor n grupuri (clustere)

    Clasificarea datelor (classification) este procesul de generalizare aunei structuri cunoscute pentru a fi aplicata la date noi.Repartizarea unui obiect nou la unul dintre grupuri (clustere).

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Aspecte teoretice generale Datele se reprezinta sub forma de vectori N-dimensionali

    MiRxxxxx NiiNiii ...,,1,,]...,,,[ 21 ==N numarul de trasaturi ale fiecarui obiect (dimensiunea trasaturilor)

    M numarul de obiecte (dimensiunea setului de date)

    =

    MNMM

    N

    N

    xxx

    xxxxxx

    X

    LMMMM

    LL

    21

    22221

    11211

    caracteristici, jobiecte

    i

    Kkxxxc kNkkK ...,,1,]...,,,[ 21 ==

    Obiectivele gruparii sunt de a gasia) K vectori centrele grupurilor

    b) Matricea gradelor de apartenena, cu dimensiunile M x K (M linii, K coloane)

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Gruparea tranant In gruparea transanta un obiect apartine in totalitate sau nu

    apartine deloc unui grup, adica gradul su de apartenenta la unanumit grup este fie 1, fie 0.

    Pentru o partitionare in K grupuri, Ck, k=1, , K

    UK

    kk XC

    1==

    KkXCKlkCC

    k

    lk

    =

    1,1,

    Fiecare obiect apartine unui grup

    nu exista grupuri vide

    nu exista niciun grup care s contina toate obiectele.

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Exemplificare Grupare (partitionare in trei grupuri):

    =

    010100100100010010010001001001

    U

    321 G,G,G

    321 GGG

    matricea gradelor de apartenenta

    Obiectul x10 este plasat in grupul G2 desi in mod intuitiv nu ar trebui inclus in nici unul dintre grupuri

    x10 poate fi considerat ca un punct exceptional sau punct atipic, sau chiar zgomot

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Cele mai frecvente situatii reale nu permit o astfel de grupareclara, neambigua domeniile corespunzatoare claselor fiind maidegraba suprapuse

    In aceste cazuri este de preferat o partitionare in care un obiectpoate apartine la mai multe grupuri in acelasi timp, cu gradediferite de apartenenta, in domeniul [0, 1]

    Exista 2 tipuri de astfel de partitionari: fuzzy posibilistic

    astfel x10, ar putea apartine cu diferite grade de apartenenta la toate cele trei grupuri, intuitiv o valoare foarte scazuta, de exemplu 0.1, caz in care conditia de partitie (fuzzy) ca suma gradelor de apartenenta la toate grupurile sa fie 1 nu mai este indeplinita

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Masuri pentru distanta Un factor important ce determina rezultatul partitionarii datelor

    este metoda de determinare a distantei dintre obiecte. distanta este masurata in spatiul caracteristicilor

    Cea mai frecvent utilizata masura este norma euclidiana:distanta geometrica intre doua puncte din spatiul X.

    In cazul punctelor:

    ]...,,,[

    ;]...,,,[

    21

    21

    qNqqq

    pNppp

    xxxxxxxx

    ==

    ( )2

    1

    2qp

    N

    jqjpjpq xxxxD ==

    =

    exemplificare pentru spatiul bidimensional al caracteristicilor

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Fuzzy C-means (FCM) Fuzzy c-means (FCM) este o metoda de grupare a datelor in care fiecare

    obiect apartine unui grup intr-un anumit grad specificat de gradul deapartenenta

    Metoda a fost introdusa de Jim Bezdek in 1981 Este o metoda care arata cum sa se grupeze obiectele ce populeaza un

    spatiu multidimensional intr-un numar specificat de grupuri diferite. functia fcm din Fuzzy Logic Toolbox porneste cu o estimare initiala a

    centrelor grupurilor, menite sa marcheze locatia medie a fiecarui grup. Estimarea initiala a centrelor este, cel mai probabil, incorecta. In plus, fcm atribuie initial in mod aleator fiecarui obiect un grad de

    apartenenta la fiecare grup Prin actualizarea iterativa a centrelor grupurilor si a gradelor de

    apartenenta a tuturor obiectelor, fcm deplaseaza iterativ centrele inlocatiile cele mai potrivite setului de date.

    Aceasta iterare (optimizare) se bazeaza pe minimizarea functiei obiectivce reprezinta suma distantelor fiecrui obiect la fiecare centru degrup, ponderate cu gradele de apartenenta al obiectelor la grupuri.

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Fuzzy C-means (FCM) in Matlab

    In Fuzzy Logic Toolbox exista functia fcm Functia ntoarce: Matricea centrelor: o matrice cu centrele grupurilor; fiecare rand

    al matricii contine coordonatele unui centru de grup Matricea gradelor de apartenenta: matricea contine gradele de

    apartenenta a fiecarui punct (obiect) din setul de date la fiecaregrup; fiecare rand contine gradele de apartenenta a unui punct lafiecare grup (in ordinea grupurilor)

    Functia matlab genfis3 genereaza automat un SLF (Sugeno sauMamdani) pe baza rezultatelor furnizate de fcm. Acest slf poatefi utilizat cu rol de clasificator (sistem de recunoastere aformelor)

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Se pot construi multimi fuzzy corespunzatoare fiecarei dimensiuni (caracteristici) a datelor (acestea ar trebuie ordonate crescator)

    In general centrele grupurilor nu coincid cu nici un obiect de clasificat

    FCM

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Clasificarea substractiv

    Trebuie precizat valoarea unei raze ce specific domeniul de influenal centrului n fiecare dimensiune a datelor, presupunnd c datele se afl n interiorul unei hipercutii unitate

    Algoritm rapid, ntr-o singur trecere, fr optimizareDetermina numrul de grupuri i centrele grupurilor dintr-un set de date

    1. Presupune c fiecare punct de date este un potenial centru de grup i calculeaz probabilitatea ca acesta s defineasc un centru pe baza densitii punctelor nconjurtoare

    2. Selecteaz punctul cu cel mai mare potenial ca fiind primul centru de grup

    3. nltur toate punctele din vecintatea centrului determinat anterior (n conformitate cu raza precizat) n scopul determinrii urmtorului grupi a centrului ei

    4. Continua acest proces pn cnd toate datele se afl n raza de influen a unui centru de grup.

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme c