Popis zobrazenı´ pomocı´ fuzzy logiky diplomova´ pra´ce
Ja´n Fro¨hlich ˇ VUT KM, FJFI, C
23. dubna 2009
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
1 / 25
Obsah 1
´ vod U Za´klady fuzzy logiky Popis zobrazenı´ pomocı´ fuzzy logiky Fuzzy logika v sˇirsˇ´ım smyslu Cı´le pra´ce Aproximace zobrazenı´
2
Vy´sledky Po cˇa´stech linea´rnı´ regrese Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´ Aproximace nelinea´rnı´ch zobrazenı´ Konstrukce tvrzenı´ Lukasiewiczovy logiky
3
Za´veˇr
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
2 / 25
´ vod U
Za´klady fuzzy logiky
Fuzzy logika
Uvazˇova´nı´ o cˇa´stecˇneˇ pravdivy´ch vy´rocı´ch rozsˇ´ırˇenı´ spojek, standardnı´ algebra na [0, 1], modus ponens, axiomy, bezespornost, u´plnost, . . . , popis zobrazenı´: eA (ϕ) = f (eA (v1 ), . . . , eA (vk ))
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
3 / 25
´ vod U
Za´klady fuzzy logiky
Konjunkce t-normy
bina´rnı´ operace t-norma t : [0, 1]2 → [0, 1]: 1
komutativita x t y = y t x,
2
asociativita x t (y t z) = (x t y) t z,
3
monotonie x≤y
4
implikuje x t z ≤ y t z,
omezenı´ shora 1 t x = x.
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
4 / 25
´ vod U
Za´klady fuzzy logiky
Implikace a reziduum t-normy pravidlo modus ponens (ϕ & (ϕ → ψ)) → ψ pozˇaduje se: x ⇒t y = 1 pra´veˇ tehdy, kdyzˇ x ≤ y , pravidlo modus ponens je tautologie
pravdivost za´veˇru ψ je zdola omezena pravdivostı´ prˇedpokladu, tj. stupneˇm soucˇasne´ pravdivosti vy´roku˚ ϕ a ϕ → ψ, prˇi interpretaci konjunkce v prˇedpokladu t-normou t : (x t (x ⇒t y)) ≤ y, reziduum ⇒t t-normy t je funkce ⇒t : [0, 1]2 → [0, 1]: x ⇒t y = sup{z | x t z ≤ y}.
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
5 / 25
´ vod U
Popis zobrazenı´ pomocı´ fuzzy logiky
Lukasiewiczova logika Interpretace spojek x ⊗ y := 0 ∨ (x + y − 1), x ⇒⊗ y := 1 ∧ (1 − x + y),
Reprezentace funkcı´ (0, 8 ⊕ 0, 7) ⊖ 0, 6 = 1 ⊖ 0, 6 = 0, 4 6= 1, 5 − 0, 6 = 0, 9, 0, 8 ⊕ (0, 7 ⊖ 0, 6) = 0, 8 ⊕ 0, 1 = 0, 9 = 0, 8 + 0, 1 = 0, 9, po cˇa´stech linea´rnı´ funkce s celocˇ´ıselny´mi koeficienty, V W ⊕m reprezentace funkce f : Φ = i∈pˆ Φhi & j∈qˆi ¬Ψgi,j i,j
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
6 / 25
´ vod U
Popis zobrazenı´ pomocı´ fuzzy logiky
Lukasiewiczova logika Interpretace spojek x ⊗ y := 0 ∨ (x + y − 1), x ⇒⊗ y := 1 ∧ (1 − x + y),
Reprezentace funkcı´ (0, 8 ⊕ 0, 7) ⊖ 0, 6 = 1 ⊖ 0, 6 = 0, 4 6= 1, 5 − 0, 6 = 0, 9, 0, 8 ⊕ (0, 7 ⊖ 0, 6) = 0, 8 ⊕ 0, 1 = 0, 9 = 0, 8 + 0, 1 = 0, 9, po cˇa´stech linea´rnı´ funkce s celocˇ´ıselny´mi koeficienty, V W ⊕m reprezentace funkce f : Φ = i∈pˆ Φhi & j∈qˆi ¬Ψgi,j i,j
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
6 / 25
´ vod U
Fuzzy logika v sˇirsˇ´ım smyslu
Fuzzifikace vstupu˚
http://www.mathworks.com/products/fuzzylogic/
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
7 / 25
´ vod U
Fuzzy logika v sˇirsˇ´ım smyslu
Fuzzy usuzova´nı´
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
8 / 25
´ vod U
Fuzzy logika v sˇirsˇ´ım smyslu
Fuzzy odvozova´nı´ a defuzifikace
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
9 / 25
´ vod U
Cı´le pra´ce
´ koly U
1 2
Implementovat algoritmus pro prˇevod zobrazenı´ na tvrzenı´ Aproximace dat a popis zobrazenı´ fuzzy logice: srozumitelnost tvrzenı´ vs. prˇesnost reprezentace, vy´rokova´ vs. predika´tova´ fuzzy logika, efektivita pro velke´ soubor dat a vysˇsˇ´ı dimenze
3
Navrhnout a implementovat algoritmy v MATLABu
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
10 / 25
´ vod U
Aproximace zobrazenı´
Cı´l: zadane´ body 1 0.8
f(x1)
0.6 0.4 0.2 0
0
0.2
0.4
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
11 / 25
´ vod U
Aproximace zobrazenı´
Cı´l: vy´sledna´ aproximace 1 1 3
0.8
f(x1)
0.6
0.4
0.2
0
2
0
0.2
0.4
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
12 / 25
´ vod U
Aproximace zobrazenı´
Volba vhodne´ho zpu˚sobu aproximace
Ota´zka srozumitelnosti prˇ´ıma´ u´meˇrnost, linea´rnı´ kombinace, nelinea´rnı´ za´vislost: soucˇin dvou promeˇnny´ch, oblast linearity — konvexnı´ mnohosteˇn Neˇktere´ zna´me´ metody aproximace umeˇle´ neuronove´ sı´t’eˇ (ANN), metoda opeˇrny´ch bodu˚ (SVM), geneticke´ algoritmy
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
13 / 25
´ vod U
Aproximace zobrazenı´
Volba vhodne´ho zpu˚sobu aproximace
Ota´zka srozumitelnosti prˇ´ıma´ u´meˇrnost, linea´rnı´ kombinace, nelinea´rnı´ za´vislost: soucˇin dvou promeˇnny´ch, oblast linearity — konvexnı´ mnohosteˇn Neˇktere´ zna´me´ metody aproximace umeˇle´ neuronove´ sı´t’eˇ (ANN), metoda opeˇrny´ch bodu˚ (SVM), geneticke´ algoritmy
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
13 / 25
´ vod U
Aproximace zobrazenı´
Evolucˇnı´ algoritmy a po cˇa´stech linea´rnı´ regrese
prohleda´va´nı´ prostoru rˇesˇenı´ jedinec, populace, ohodnocovacı´ funkce, selekce, mutace, krˇ´ızˇenı´, reprodukce predika´tova´ nebo vy´rokova´ logika hledat prˇ´ımo tvrzenı´ nebo funkci vstup: aproximace nebo soubor dat krite´ria optimalizace, konvergence populace efektivita
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
14 / 25
Vy´sledky
Po cˇa´stech linea´rnı´ regrese
Navrzˇeny´ postup Hleda´ se f : [0, 1]k → [0, 1]. Zada´no n bodu˚: xi ∈ [0, 1]k , yi ∈ [0, 1], i ∈ {1, . . . , n}. 1 2 3
Sestavı´ se kd-trie. Provede se linea´rnı´ regrese bodu˚ v bunˇka´ch. Rozlisˇ´ı se nosne´ a hranicˇnı´ bunˇky.
u´speˇsˇnost prolozˇenı´ koeficient urcˇenı´: R 2 = 4
soucˇet cˇtvercu˚ modelovy´ch hodnot celkovy´ soucˇet cˇtvercu˚
∈ [0, 1]
Sloucˇ´ı se bunˇky se stejnou za´vislostı´ (testova´nı´ linea´rnı´ch hypote´z).
nejveˇtsˇ´ı mozˇne´ konvexnı´ oblasti mı´ra konvexnosti: γ = ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
soucˇet objemu˚ sloucˇeny´ch buneˇk objem konvexnı´ho obalu vrcholu˚ bunˇky Popis zobrazenı´ pomocı´ fuzzy logiky
∈ (0, 1] 23. dubna 2009
15 / 25
Vy´sledky
Po cˇa´stech linea´rnı´ regrese
Navrzˇeny´ postup Hleda´ se f : [0, 1]k → [0, 1]. Zada´no n bodu˚: xi ∈ [0, 1]k , yi ∈ [0, 1], i ∈ {1, . . . , n}. 1
Sestavı´ se kd-trie. Prˇ´ıklad — dveˇ neza´visle´ promeˇnne´: 1 12
16
4
8
14
18
6
10
0.8
x
2
0.6
0.4 11
15
13
17
3
7
5
9
0.2
0
0
0.2
0.4
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
15 / 25
Vy´sledky
Po cˇa´stech linea´rnı´ regrese
Navrzˇeny´ postup Hleda´ se f : [0, 1]k → [0, 1]. Zada´no n bodu˚: xi ∈ [0, 1]k , yi ∈ [0, 1], i ∈ {1, . . . , n}. 1 2 3
Sestavı´ se kd-trie. Provede se linea´rnı´ regrese bodu˚ v bunˇka´ch. Rozlisˇ´ı se nosne´ a hranicˇnı´ bunˇky.
u´speˇsˇnost prolozˇenı´ koeficient urcˇenı´: R 2 = 4
soucˇet cˇtvercu˚ modelovy´ch hodnot celkovy´ soucˇet cˇtvercu˚
∈ [0, 1]
Sloucˇ´ı se bunˇky se stejnou za´vislostı´ (testova´nı´ linea´rnı´ch hypote´z).
nejveˇtsˇ´ı mozˇne´ konvexnı´ oblasti mı´ra konvexnosti: γ = ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
soucˇet objemu˚ sloucˇeny´ch buneˇk objem konvexnı´ho obalu vrcholu˚ bunˇky Popis zobrazenı´ pomocı´ fuzzy logiky
∈ (0, 1] 23. dubna 2009
15 / 25
Vy´sledky
Po cˇa´stech linea´rnı´ regrese
Navrzˇeny´ postup Hleda´ se f : [0, 1]k → [0, 1]. Zada´no n bodu˚: xi ∈ [0, 1]k , yi ∈ [0, 1], i ∈ {1, . . . , n}. 1 2 3
Sestavı´ se kd-trie. Provede se linea´rnı´ regrese bodu˚ v bunˇka´ch. Rozlisˇ´ı se nosne´ a hranicˇnı´ bunˇky.
u´speˇsˇnost prolozˇenı´ koeficient urcˇenı´: R 2 = 4
soucˇet cˇtvercu˚ modelovy´ch hodnot celkovy´ soucˇet cˇtvercu˚
∈ [0, 1]
Sloucˇ´ı se bunˇky se stejnou za´vislostı´ (testova´nı´ linea´rnı´ch hypote´z).
nejveˇtsˇ´ı mozˇne´ konvexnı´ oblasti mı´ra konvexnosti: γ = ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
soucˇet objemu˚ sloucˇeny´ch buneˇk objem konvexnı´ho obalu vrcholu˚ bunˇky Popis zobrazenı´ pomocı´ fuzzy logiky
∈ (0, 1] 23. dubna 2009
15 / 25
Vy´sledky
Po cˇa´stech linea´rnı´ regrese
Navrzˇeny´ postup Hleda´ se f : [0, 1]k → [0, 1]. Zada´no n bodu˚: xi ∈ [0, 1]k , yi ∈ [0, 1], i ∈ {1, . . . , n}. 1 2 3
Sestavı´ se kd-trie. Provede se linea´rnı´ regrese bodu˚ v bunˇka´ch. Rozlisˇ´ı se nosne´ a hranicˇnı´ bunˇky.
u´speˇsˇnost prolozˇenı´ koeficient urcˇenı´: R 2 = 4
soucˇet cˇtvercu˚ modelovy´ch hodnot celkovy´ soucˇet cˇtvercu˚
∈ [0, 1]
Sloucˇ´ı se bunˇky se stejnou za´vislostı´ (testova´nı´ linea´rnı´ch hypote´z).
nejveˇtsˇ´ı mozˇne´ konvexnı´ oblasti mı´ra konvexnosti: γ = ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
soucˇet objemu˚ sloucˇeny´ch buneˇk objem konvexnı´ho obalu vrcholu˚ bunˇky Popis zobrazenı´ pomocı´ fuzzy logiky
∈ (0, 1] 23. dubna 2009
15 / 25
Vy´sledky
Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´
Zadane´ body 1 0.8
f(x1)
0.6 0.4 0.2 0
0
0.2
0.4
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
16 / 25
Vy´sledky
Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´
kd-trie, linea´rnı´ regrese 1 7 15 5 0.8
14
11
10 18
3
f(x1)
0.6
13
6
0.4
0.2
0
16
4
0
0.2
0.4
8 0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
17 / 25
Vy´sledky
Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´
Sloucˇenı´ buneˇk se stejnou za´vislostı´ 1 31 15
22
26
0.8
38
3
f(x1)
0.6
0.4
0.2
0
4
0
0.2
0.4
35 16
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
18 / 25
Vy´sledky
Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´
Nalezenı´ oblastı´ linearity (klasifikace) 1
Linea´rnı´ klasifikacı´ se urcˇ´ı nadroviny oddeˇlujı´cı´ sousednı´ bunˇky.
2
Pomocı´ nalezeny´ch nadrovin se sestrojı´ konvexnı´ mnohosteˇny. 1 31
0.9
15
22
26
0.8
38
0.7 3 1
f(x )
0.6 0.5 0.4 0.3 0.2
4
35
16
0.1 0
0
0.2
0.4
0.6 x
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
0.8
1
1
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
19 / 25
Vy´sledky
Prˇ´ıklad: funkce jedne´ neza´visle´ promeˇnne´
Nalezenı´ oblastı´ linearity (pru˚secˇı´ky) 1
Urcˇ´ı se pru˚secˇ´ıky nadrovin sousednı´ch buneˇk.
2
Pru˚secˇ´ıky se promı´tnou do prostoru neza´visly´ch promeˇnny´ch. 1 31
0.9
15 26
0.8
38
22 0.7 3
1
f(x )
0.6 0.5 0.4 0.3 0.2
35
4
16
0.1 0
0
0.2
0.4
0.6 x
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
0.8
1
1
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
20 / 25
Vy´sledky
Aproximace nelinea´rnı´ch zobrazenı´
Hleda´nı´ oblastı´ extre´mu˚ 1
Naleznou se loka´lnı´ maxima.
2
V kazˇde´ oblasti maxima se provede kvadraticka´ regrese. 1 1 3
0.8
f(x1)
0.6
0.4
0.2
0
2
0
0.2
0.4
0.6
0.8
1
x1
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
21 / 25
Vy´sledky
Aproximace nelinea´rnı´ch zobrazenı´
Hleda´nı´ oblastı´ extre´mu˚ 1
Naleznou se loka´lnı´ maxima.
2
V kazˇde´ oblasti maxima se provede kvadraticka´ regrese. 1 1 0.8
3
f(x1)
0.6
0.4
0.2
0
2
0
0.2
0.4
0.6
0.8
1
x1
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
21 / 25
Vy´sledky
Konstrukce tvrzenı´ Lukasiewiczovy logiky
Prˇ´ıklad: po cˇa´stech linea´rnı´ funkce ...
26
38
35
1
f(x1)
0.8 0.6 0.4 0.2 0
0
0.2
0.4
0.6
0.8
1
x1 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
22 / 25
Vy´sledky
Konstrukce tvrzenı´ Lukasiewiczovy logiky
... reprezentace funkce v Lukasiewiczoveˇ logice „ `1
1
⊕
2
⊖
10
1´
&
2
“ `1 1 1 ´⊕2 ⊖ ⊕ϕ⊖ ∧ ¬ 2 10 2 « ⊕4 ” 1´ `1 ⊖ϕ⊖ ¬ 2 2 ∨ „ `1
2
⊕
3 10
⊕2
⊖ϕ
⊖
1´
&
2
“ `1 1 1´ ¬ ⊖ ⊕ϕ⊖ ∧ 2 10 2 « ⊕8 1 1´ ” `1 ⊕ ⊖ϕ⊖ ¬ 2 10 2 ∨ „ `1
2
⊕4
⊕ϕ
⊖
1´
&
2
“ `1 1 ´⊕16 ¬ ⊕ϕ⊖ ∧ 2 2 « `1 1 ´” ¬ ⊖ϕ⊖ 2 2 ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
23 / 25
Za´veˇr
Shrnutı´
Za´veˇr
Vlastnosti navrzˇeny´ch algoritmu˚: jednoduche´ nastavenı´ u´rovneˇ aproximace, oblasti linearity — konvexnı´ mnohosteˇny, umozˇnı´ nale´zt spojitou po cˇa´stech linea´rnı´ aproximaci, snadne´ nalezenı´ loka´lnı´ch extre´mu˚, regrese v oblastech extre´mu˚ usnadnı´ konstrukci predika´tu˚, vyuzˇ´ıva´ linea´rnı´ metody.
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
24 / 25
Diskuze
Ota´zky a odpoveˇdi
Deˇkuji za pozornost.
ˇ VUT ) Ja´n Fro¨hlich ( KM, FJFI, C
Popis zobrazenı´ pomocı´ fuzzy logiky
23. dubna 2009
25 / 25
