Introduzione alla Teoria degli Insiemi fuzzyig/lezioni-08-09/2-teoria-degli-insiemi-fuzzy.pdf ·...

10/11/2009

1

Metodi di Intelligenza Computazionale

per l’elaborazione di immagini

Dott.ssa Giovanna Castellano

[email protected]

Modulo IIModulo II

Introduzione alla Teoria degli Insiemi fuzzy

G. Castellano 2

10/11/2009

2

Concetto di insieme

• Secondo la logica classica, un insieme è definito come

– Qualunque aggregato (o collezione) di oggetti per il quale sia sempre possibile decidere se un generico oggetto appartiene oppure no all'aggregato stesso

• Il punto centrale della teoria degli insieme è la nozione di appartenenza ad un insieme

G. Castellano 3

Concetto di insieme

• Esempio:– Dato il dominio Z dell’età delle persone, vogliamo

determinare l’insieme A definito come “Insieme delle persone giovani in Z”.

• Per poter definire questo insieme occorre definire la funzione caratteristica di A, detta anche funzione di appartenenza all’insieme A

G. Castellano 4

( ) ∈

=altrimenti

AzsezA

0

1µ

10/11/2009

3

Concetto di insieme

• Per definire l’insieme A occorre stabilire una soglia Th sull’età delle persone da includere nell’insieme

• La funzione di appartenenza μA sarà così definita:

– Per es. fissiamo Th=20

G. Castellano 5

Concetto di insieme

• Nella logica classica il concetto di appartenenza ad un insieme si riferisce unicamente alla condizione VERO-FALSO

• La funzione di appartenenza di un insieme è una funzione booleana– Può assumere solo due valori• 1= appartenenza

• 0= non appartenenza

• L’insieme si dice “Crisp”

G. Castellano 6

{ }1,0: →ZAµ

10/11/2009

4

Concetto di insieme

• L’uso di un insieme crisp è limitativo per rappresentare un concetto sfumato come ad es. quello di “persona giovane” – Stando alla definizione dell’insieme A data prima,

possiamo dire che una persona la cui età è di 20 anni e 1 mese, non appartiene all’insieme, cioè non è giovane!

• È quindi necessario riformulare il concetto di insieme in modo più soft, introducendo l’idea di grado di appartenenza (membership)– In questo modo è possibile definire una persona “più”

o “meno” giovane all’interno dell’insieme

G. Castellano 7

Concetto di insieme fuzzy

• Definizione dell’insieme delle persone giovani

G. Castellano 8

CRISP FUZZY

Il concetto di insieme fuzzy estende il concetto di insieme crisp mediante l’introduzione di un grado di appartenenza

10/11/2009

5


• Mediante il grado di appartenenza all’insieme è possibile rappresentare affermazioni “vaghe” come:

– “ una persona di 15 anni è giovane”

– “ una persona di 22 anni è relativamente giovane”

– “ una persona di 27 anni è non tanto giovane”

G. Castellano 9


• In generale, un concetto sfumato (fuzzy) corrisponde ad un insieme di oggetti nel quale non c’è un confine ben preciso o definito tra gli oggetti che vi appartengono e quelli che non vi appartengono– Bello, giovane, chiaro, scuro, vicino, ecc …,

• Alcuni concetti non sono fuzzy:– Sposato, maschio, fratello, ecc …

• Gli insiemi fuzzy permettono di sviluppare il formalismo necessario a gestire concetti imprecisi e sfumati

10

10/11/2009

6

Teoria degli insiemi fuzzy

• La teoria degli insiemi fuzzy è stata introdotta più di 40 anni fa da Lotfi Zadeh.

– Zadeh L.A., “Fuzzy Sets”, Information and Control, vol.8

(1965) pp. 338-353

G. Castellano 11

Definizione di insieme fuzzy

• Dato un dominio Z, con z generico elemento di Z, un insieme fuzzy A in Z è caratterizzato da una funzione di appartenenza (membership) μA(z) che associa ad ogni elemento di Z un numero reale nell’intervallo[0,1].

• Il valore di μA(z) rappresenta il grado di appartenenza di z in A– Per μA(z)=1 diremo che z appartiene sicuramente ad A– Per μA(z)=0 diremo che z non appartiene ad A– Per 0<μA(z)<1 diremo che z appartiene parzialmente

ad A, con un grado di appartenenza indicato da μA(z)G. Castellano 12

[ ]1,0: →ZAµ

10/11/2009

7


• Un insieme crisp è un caso speciale di insieme fuzzy

– La funzione di membership assume unicamente valori 0 e 1

G. Castellano 13


• Un insieme fuzzy è composto da coppie ordinate di elementi del tipo:

• Quando il dominio Z è continuo, l’insieme A può essere composto da un numero infinito di elementi.

• Quando il dominio Z è discreto, è possibile esplicitare tutti gli elementi dell’insieme A. – Per esempio, nel caso dell’insieme delle persone giovani,

considerando l’età come dominio discreto (n. anni), abbiamo:

G. Castellano 14

10/11/2009

8

Funzioni di membership

G. Castellano 15

>


G. Castellano 16

10/11/2009

9


G. Castellano 17


G. Castellano 18

10/11/2009

10


G. Castellano 19


G. Castellano 20

10/11/2009

11

Qualche altra definizione

• Dato l’insieme fuzzy A definito sul dominio Z, si definiscono:

– Supporto di A:

– Core di A:

– α-cut di A:

21

corecore

supportosupporto

αα

αα--cutcut

( ){ }0>∈= zZzS AA µ

( ){ }1=∈= zZzC AA µ

[ ] ( ){ }αµα ≥∈= zZzA A

Qualche altra definizione

• Insiemi fuzzy particolari

– fuzzy singleton

– fuzzy set universale

– fuzzy set vuoto

– fuzzy set normale

22

( ) ( ) ZzCZzz AA =⇔∈∀= 0.1µ

( ) { }0zzSA =

( ) ( ) ∅=⇔∈∀= zSZzz AA 0.0µ

( ) 1=zmax Axµ

10/11/2009

12

Fuzzy logic in Java

• FuzzyJ Toolkit è una libreria di classi Java sviluppate dal National Research Council dell’istituto canadese per l’Information Technology che permette di manipolare concetti fuzzy– http://www.nrc-cnrc.gc.ca/eng/projects/iit/fuzzyj-toolkit.html

• L’API è costituita da due package:– nrc.fuzzy: permette di utilizzare la libreria in modalità

standalone per creare regole fuzzy ed effettuare ragionamenti in ambiente Java;

– nrc.fuzzy.jess: permette l’integrazione delle funzionalità offerte dal package nrc.fuzzy con Jess(http://herzberg.ca.sandia.gov/jess/) la shell per sistemi esperti sviluppata nei Sandia National Laboratories.

23

Insiemi fuzzy in FuzzyJ

• La classe del toolkit FuzzyJ che implementa gli insiemi fuzzy è FuzzySet– permette di rappresentare gli insiemi fuzzy come

un insieme di coppie ui/xi, dove ui è il valore di membership per il numero reale xi

{ u1/x1 , u2/x2 , ... , un/xn }

con i valori xi in ordine crescente. • I valori precedenti ad x1 hanno la stessa membership di

x1 mentre i valori successivi ad xn hanno la stessa membership di xn

24

10/11/2009

13

Insiemi fuzzy in FuzzyJ

• Esempio di codice per la creazione di un FuzzySet (triangolare) così definito

{ 0.0/0.3, 1.0/0.5, 0.0/0.7 }

25

FuzzySet fSet = new triangleFuzzySet( 0.3, 0.5, 0.7 );

Funzioni di membership in FuzzyJ

SFuzzySetSFuzzySet • La libreria FuzzyJ mette a disposizione

diverse tipologie di funzioni di membership organizzate gerarchicamente

26

10/11/2009

14

Funzioni di membership in FuzzyJ

• Gli insiemi di tipologia LRFuzzySet possono essere rappresentati in diagrammi con tre parti distinte: – una parte sinistra con valori di membership crescenti – una parte destra con valori di membership descrescenti– una parte centrale con tutti i valori di membership uguali ad 1

• Un esempio di FuzzySet di questa tipologia sono quelli di forma trapezoidale (TrapezoidFuzzySet)

27

Confronto tra fuzzy set

• Inclusione

• Uguaglianza

• Similarità (in termini di distanza)

– distanza di Hamming

– distanza Euclidea

– ...

28

ZzzzBA BA ∈∀≤⇔⊆ )()( µµ AA

BB

( ) ( ) ( )∫ −=Z

BA dzzzBAd µµ,

( ) ( ) ( )[ ]∫ −=Z

BA dzzzBAd2

, µµ

ZzzzBA BA ∈∀=⇔= )()( µµ

10/11/2009

15

Operazioni su insiemi fuzzy

• Complemento

– Dato un insieme fuzzy A, si definisce complemento di A, e si indica con ¬A, oppure Not(A), l'insieme fuzzy con funzione di membership tale che

29

( ) ( ) Zzzz AA ∈∀−=¬ µµ 1

AA


• Unione

– Dati due insiemi fuzzy A e B, si definisce unione di A e B, e si indica con A U B, l’insieme fuzzy con funzione di membership tale che

dove σ è un operatore chiamato S-norm o T-conorm, che può essere implementato in vari modi

30

( ) ( ) ( )( ) Zzzzz BABA ∈∀=∪ µµσµ ,

10/11/2009

16


• L’operatore T-conorm (Triangular conorm) è unafunzione

• Gode delle seguenti proprietà:– simmetrica, associativa, monotona, con elemento neutroneutro 0 0

• Esempi

31

[ ] [ ] [ ]1,01,01,0: →×σ

Massimo

Somma

Somma limitata

( ) { }bamaxba ,, =σ

( ) abbaba −+=,σ

( ) { }baminba += ,1,σ


• Unione di insiemi fuzzy mediante massimo

32

( ) ( ) ( )( )zzz BAZz

BA µµµ ,max∈

∪ =

10/11/2009

17


• Intersezione

– Dati due insiemi fuzzy A e B, si definisce intersezione di A e B, e si indica con A∩B , l’insieme fuzzy con funzione di membership tale che

dove τ è un operatore chiamato T-norm che può essere implementato in vari modi

33

( ) ( ) ( )( )xxx BABA µµτµ ,=∩


• L’operatore T-norm (Triangular norm) è unafunzione

• Gode delle seguenti proprietà:– simmetrica, associativa, monotona, con elemento neutro 1

• Esempi

34

[ ] [ ] [ ]1,01,01,0: →×τ

minimo

prodotto

prodotto limitato

( ) { }baminba ,, =τ

( ) abba =,τ

( ) { }1,0, −+= bamaxbaτ

10/11/2009

18


• Intersezione di insiemi fuzzy mediante minimo

35

( ) ( ) ( )( )zzz BAZz

BA µµµ ,min∈

∩ =


• Prodotto cartesiano di insiemi fuzzy – Dato l’insieme fuzzy A definito sul dominio X e

l’insieme fuzzy B definito sul dominio Y, si definisceprodotto cartesiano di A per B, e si indica con l’insieme fuzzy con funzione di membership

– dove τ è un operatore T-norm

– è un insieme fuzzy bi-dimensionale in

36

[ ]( ) ( ) ( )( )yxyx

YX

BABA

BA

µµτµ

µ

,,

1,0:

=

→×

×

×

BA×

BA× YX ×

10/11/2009

19


37

A

X

Y

B

BA×

Prodotto cartesiano di insiemi fuzzy

Operazioni su insiemi fuzzy in FuzzyJ

• Per implementare le operazioni sugli insiemi fuzzy si utilizzano i metodi della classe FuzzySet:

– Complemento (fuzzyComplement):

• restituisce il complemento dei valori di membershipdei punti utilizzati per la creazione del FuzzySet

38

10/11/2009

20


– Unione (fuzzyUnion):

• restituisce l’unione di due insiemi fuzzy

• per ogni x, il corrispondente valore di membership al nuovo insieme è calcolato come il massimo dei valori di membership dei due insieme fuzzy

• L’unione è il sinonimo dell’operatore logico OR.

39


– Intersezione (fuzzyIntersection):

• restituisce l’intersezione di due insiemi fuzzy e quindi (in FuzzyJ), per ogni x, il corrispondente valore di membership del nuovo insieme è calcolato come il minimo dei valori di membership dei due insieme fuzzy

40

10/11/2009

21

Variabili fuzzy

• Una variabile i cui valori sono insiemi fuzzy viene detta variabile fuzzy– Un valore della variabile può essere etichettato con un termine

che ne indica il concetto in forma linguistica, quindi è anche detto fuzzy term

• Esempio– La variabile “età di una persona” può essere definita mediante

tre fuzzy term (concetti o attributi fuzzy)

41

1

0.5

0

10 20 30 40 50 60 70 80 età

GIOVANE ADULTO ANZIANO

Variabili fuzzy

• Un aspetto fondamentale nella definizione di unavariabile fuzzy è stabilire il numero di valori fuzzy (livello di granularità)– non esistono regole per stabilirlo– una linea guida è definirne minimo 3, massimo 7

• Occorre rispettare dei vincoli– Coverage: ogni elemento del dominio deve

appartenere almeno ad un insieme fuzzy

42

10/11/2009

22

Variabili fuzzy

• Come distribuire i fuzzy set ?

43

Più robustezza al rumore Più precisione dove è necessario

Variabili fuzzy

• La definizione dei valori fuzzy da associare ad una variabile non è univoca

• Può essere effettuata – Manualmente• in base alla conoscenza dell’esperto del dominio

– Problema: soggettività nella definizione

– Automaticamente• In base ai dati empirici relativi al dominio

– Si applicano algoritmi di apprendimento delle reti neurali �Modelli Neuro-Fuzzy

G. Castellano 44

10/11/2009

23

Variabili fuzzy in FuzzyJ

• Una variabile fuzzy è implementata dalla classe FuzzyVariable.

• Le istanze di questa classe sono costituite da:– nome della variabile;

– universo del discorso, cioè un range di variabilità definito da un limite inferiore ed uno superiore di possibili valori della variabile;

– unità di misura in formato testuale;

– insieme di termini fuzzy usati per descrivere concetti fuzzy associati alla variabile.

G. Castellano 45


• Esempio di codice Java per la creazione di una variabile fuzzy per la temperatura:

G. Castellano 46

// Temperature has terms cold, medium and hot

FuzzyVariable Temp = new FuzzyVariable("temperature", 0.0, 100.0, "Degrees C");

Temp.addTerm(“Cold", new TrapezoidFuzzySet(0, 0, 5.0, 15.0));

Temp.addTerm(“Medium", new TrapezoidFuzzySet(5.0, 15.0, 25.0, 35.0));

Temp.addTerm(“Hot", new SFuzzySet(25.0, 35.0));

// medium can also be defined as:

// Temp.addTerm("medium", "not hot and not cold");

10/11/2009

24


• Gli insiemi fuzzy possono essere utilizzati per definire i termini linguistici di una variabile fuzzy

• Esempio: codice per definire una variabile fuzzy con due FuzzySet: – ZFuzzySet e SFuzzySet

G. Castellano 47

FuzzyVariable age = new FuzzyVariable(“age”, 0, 120, “years”);

age.addTerm(“young”, new ZFuzzySet(25, 50));

age.addTerm(“old”, new SFuzzySet(45, 65));

0 12050 6525

Valori fuzzy in FuzzyJ

• Un valore fuzzy permette di creare uno specifico concetto fuzzy per una variabile fuzzy, cioè associa ad una FuzzyVariableun’espressione linguistica che descrive un concetto fuzzy.

• La classe del toolkit FuzzyJ che permette la creazione di valori fuzzyè FuzzyValue.– Ad es. è possibile aggiungere alla variabile temp (temperature)

precedentemente definita un FuzzyValue che rappresenta il concetto “very hot or cold”

G. Castellano 48

FuzzyValue badTemp = null;

badTemp = new FuzzyValue(temp, "very Hot or Cold");

10/11/2009

25

Insiemi fuzzy e valori fuzzy

• Differenza tra insieme fuzzy e valore fuzzy in FuzzyJ:

– un FuzzySet è usato per definire la forma di un insieme fuzzy e non è legato ad alcun concetto;

– un FuzzyValue associa un FuzzySet ad una FuzzyVariable attribuendo, quindi, un significato all’insieme fuzzy.

• i termini associati alla variabile sono conservati internamente come valori fuzzy

G. Castellano 49

Modificatori fuzzy in FuzzyJ

• Un modificatore fuzzy modifica la forma di un insieme fuzzy in modo tale da adattarla al significato di un concetto che si vuole rappresentare

• I modificatori sono usati in espressioni linguistiche – Es. (very Hot or Cold)

• L’insieme dei modificatori di un FuzzyValuedisponibili nel toolkit FuzzyJ è costituito dai metodi della classe Modifiers

G. Castellano 50

10/11/2009

26


• not

– restituisce il complemento del FuzzyValue passato come argomento

• norm

– Normalizza il FuzzyValue passato come argomento in modo tale che almeno un punto abbia membership uguale ad 1;

51

not

norm


• more_or_less– aumenta di un fattore pari ad 1/3 tutti i valori di membership del FuzzyValue passato come argomento;

• somewhat

– aumenta di un fattore pari ad 1/2 tutti i valori di membershipdel FuzzyValue passato come argomento;

52

somewhat

more_or_less

10/11/2009

27


• plus– aumenta di un fattore pari ad 1.25 tutti i valori di membership

del FuzzyValue passato come argomento;

• very– aumenta di un fattore pari a 2 tutti i valori di membership del FuzzyValue passato come argomento;

53

plus

very


• extremely– aumenta di un fattore pari a 3 tutti i valori di membership del

FuzzyValue passato come argomento

• intensify

– esegue una modifica al FuzzyValue passato come argomento che enfatizza la sezione con membership>0.5 e minimizza la sezione con membership ≤ 0.5;

54

extremely

intensify

10/11/2009

28

Modificatori fuzzy in FuzzyJ• slightly– esegue la seguente modifica al FuzzyValue

passato come argomento:

intensify [ norm (plus A AND not very A) ]

G. Castellano 55

not very

plus

AND

norm

Modificatori fuzzy in FuzzyJ• above

– identifica il primo valore in cui viene raggiunto il massimo valore di membership. Tutti i valori di membership sotto questo punto sono settati a 0, mentre quelli superiori sono settati a 1-y

• below– identifica il primo valore in cui viene raggiunto il massimo valore di

membership. Tutti i valori di membership sopra questo punto sono settati a 0, mentre quelli inferiori sono settati a 1-y.

56

above

below

Introduzione alla Teoria degli Insiemi fuzzyig/lezioni-08-09/2-teoria-degli-insiemi-fuzzy.pdf ·...

Documents

Transcript of Introduzione alla Teoria degli Insiemi fuzzyig/lezioni-08-09/2-teoria-degli-insiemi-fuzzy.pdf ·...