Home >Documents >Gruparea (si clasificarea) fuzzy a Aspecte teoretice generale Gruparea tran™antƒ Metode...

Gruparea (si clasificarea) fuzzy a Aspecte teoretice generale Gruparea tran™antƒ Metode...

Date post:08-Feb-2018
Category:
View:220 times
Download:2 times
Share this document with a friend
Transcript:
  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Gruparea (si clasificarea)fuzzy a datelor

    Introducere

    Aspecte teoretice generale

    Gruparea tranant

    Metode 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-un

    set 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, clase

    de 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. pentru

    florile de iris: latimea si lungimea sepalei si latimea si lungimea petalei)

    n practica pot exista un numr mare de obiecte de grupat (eantioane) descrise

    prin mai multe trasaturi gruparea automat a datelor

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Este utilizata extensiv pentru aplicatii de:

    recunoasterea formelor (pattern recognition),

    extragere de caracteristici,

    segmentarea imaginilor,

    aproximarea functiilor,

    identificarea sistemelor

    data mining.

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

    centrul grupurilor (localizarea grupurilor)

    forma grupurilor

    gradul de apartenent al fiecarui obiect la fiecare grup

    In actiunea de grupare a datelor nu se cunoaste apriori valoarea dorita a

    iesirii, asadar gruparea datelor utilizeaz metode de invare

    nesupervizat:

    identifica anumite structuri inerente prezente intr-un set de obiecte, pe

    baza unei masuri de similitudine.

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    mprirea datelor in grupuri 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 a

    grupurilor si structurilor de date care sunt similare din intregul setul de

    date, fara a utiliza structuri de date cunoscute apriori.

    mprirea obiectelor n grupuri (clustere)

    Clasificarea datelor (classification) este procesul de generalizare a

    unei 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 Datele se reprezint sub forma de vectori N-dimensionali

    MiRxxxxx NiiNiii ...,,1,,]...,,,[ 21

    N numrul de trsturi ale fiecarui obiect (dimensiunea trasaturilor)

    M numrul de obiecte (dimensiunea setului de date)

    MNMM

    N

    N

    xxx

    xxx

    xxx

    X

    21

    22221

    11211

    trasaturi, j

    obiecte

    i

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

    a) K vectori centrele grupurilor

    b) Matricea gradelor de

    apartenena, cu dimensiunile M x K

    (M linii, K coloane)

    obiectul (exemplarul) i:

    Obiectivul gruparii este de a gasi

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Gruparea tranant (clasic)

    In gruparea transanta un obiect apartine n totalitate sau nu

    apartine deloc unui grup, adica gradul su de apartenenta la un

    anumit grup este fie 1, fie 0.

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

    K

    k

    k XC1

    KkXC

    KlkCC

    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):

    010

    100

    100

    100

    010

    010

    010

    001

    001

    001

    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

    (atipic), sau chiar zgomot

    (outlier)

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Cele mai frecvente situatii reale nu permit o astfel de grupare

    clara, neambigua; domeniile corespunzatoare claselor fiind mai

    degraba suprapuse

    In aceste cazuri este de preferat o partitionare in care un obiect

    poate apartine la mai multe grupuri in acelasi timp, cu grade

    diferite 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

    Msuri pentru distan Un factor important ce determina rezultatul partitionarii datelor

    este metoda de determinare a distantei dintre obiecte.

    distanta este masurata in spatiul trasaturilor

    Cea mai frecvent utilizata masura este norma euclidiana:

    distanta geometrica intre doua puncte din spatiul X.

    In cazul punctelor:

    ]...,,,[

    ;]...,,,[

    21

    21

    qNqqq

    pNppp

    xxxx

    xxxx

    2

    1

    2

    qp

    N

    j

    qjpjpq xxxxD

    exemplificare pentru

    spatiul bidimensional

    p-norma,

    p 1 numar real

  • 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 s se grupeze obiectele ce populeaz unspatiu multidimensional intr-un numar specificat de grupuri diferite.

    functia fcm din Fuzzy Logic Toolbox porneste cu o estimare initiala acentrelor 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 deapartenenta la fiecare grup

    Prin actualizarea iterativa a centrelor grupurilor si a gradelor deapartenenta a tuturor obiectelor, fcm deplaseaza iterativ centrele inlocatiile cele mai potrivite setului de date.

    Aceasta iterare (optimizare) se bazeaza pe minimizarea functiei obiectiv:suma ponderata a distantelor fiecrui obiect la fiecare centru de grup,ponderile fiind gradele de apartenenta a obiectelor la grupuri.

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSisteme cu logica nuantata

    Fuzzy C-means (FCM)

    2

    1 1

    ||||)( ki

    K

    k

    M

    i

    mik cxJ

    Functia obiectiv:

    )1/(2

    1 ||||

    ||||

    1

    m

    K

    j ji

    ki

    ik

    cx

    cx

    Gradele de apartenenta:

    m - constant mai mare ca 1 (tipic: 2) ce indic gradul de nuanare (fuzzines) a grupelor rezultate.

    Minimizarea J - suma distantelor pentru obiecte la centrele de grup,

    ponderate cu gradul de apartenenta al obiectelor la grupuri.

    Cu cat distanta este mai mica, cu atat ponderea (gradul de apartenenta la

    acea clasa) va fi mai mare

    Cu cat distanta este mai mare, cu atat ponderea (gradul de apartenenta la

    acea clasa) va fi mai mica

  • 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

    [CENTER, U, OBJ_FCN] = fcm(DATA, N_CLUSTER,OPTIONS)

    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 fiecare

    grup; fiecare rand contine gradele de apartenenta a unui punct la

    fiecare grup (in ordinea grupurilor)

    Valorile functiei obiectiv

    Functia matlab genfis3 genereaza automat un SLF (Sugeno sau

    Mamdani) pe baza rezultatelor furnizate de fcm. Acest slf poate

    fi utilizat cu rol de clasificator (sistem de recunoastere a

    formelor)

  • Gruparea (si clasificarea) fuzzy

    G. OlteanSi

Click here to load reader

Embed Size (px)
Recommended