I
T
P
W
ZPT
1
Tablice
decyzyjne
I
T
P
W
ZPT
1
Tablice
decyzyjne
I
T
P
W
ZPT
2
Synteza logiczna
Inżynieria informacji
Dekompozycja
funkcjonalna
Odwzorowanie technologiczne
FPGA
Hierarchiczne
podejmowanie decyzji
Minimalizacja F.B.
Redukcja
argumentów
Generacja reguł
decyzyjnych
Redukcja atrybutów
I
T
P
W
ZPT
3
Tablice i reguły decyzyjne
(a,1) (b,0) (d,1)
(e,1)
a b d e
1 1 0 1 1
2 1 0 0 1
3 0 0 0 0
4 1 1 1 0
5 1 1 2 2
6 2 2 2 2
Atrybuty
Ich
wartości
Operatory
redukcja atrybutów
redukcja (generacja) reguł
decyzyjnych
I
T
P
W
ZPT
4
Przykład tablicy decyzyjnej
Atrybuty: wiek
płeć
Stan
cywilny
zawód
Klasa
decyzyjna
x
1
20 Female Married Farm
1
x
2
17 Female Single
Farm
2
x
3
25 Male
Single
Business
3
x
4
16 Female Single
Farm
2
x
5
38 Male
Single
Business
3
x
6
25 Female Single
Pleasure
4
x
7
48 Female Single
Pleasure
4
x
8
20 Female Single
Farm
2
x
9
21 Male
Married Business
5
x
10
22 Male
Married Business
5
x
11
23 Male
Married Business
5
x
12
24 Male
Married Business
5
I
T
P
W
ZPT
5
Reguły decyzyjne generowane
z tablicy decyzyjnej
(Age, 20) (Marital_Status, Married)
(Class, 1),
(Age 16)
(Class, 2),
(Age, 17)
(Class, 2),
(Age, 20) (Marital_Status, Single)
(Class, 2),
(Age, 25) (Gender, Male)
(Class, 3),
(Age, 38)
(Class, 3),
(Age, 25) (Gender, Female)
(Class, 4)
(Age, 48)
(Class, 4),
(Age, 21)
(Class, 5),
(Age, 22)
(Class, 5),
(Age, 23)
(Class, 5),
(Age, 24)
(Class, 5).
I
T
P
W
ZPT
6
Generacja reguł
Metoda analogiczna do ekspansji:
Tworzy się macierz porównań M,
Wyznacza minimalne pokrycie M,
Atrybutami reguły minimalnej są atrybuty
należące do minimalnego pokrycia M.
I
T
P
W
ZPT
7
Przykład generacji reguł
U a b c d e
1 1 0 0 1 1
2 1 0 0 0 1
3 0 0 0 0 0
4 1 1 0 1 0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2
Tablica decyzyjna
a b c d e
1 0 – – 1
0 – – – 0
– 1 – 1 0
– – – 2 2
Tablica reguł minimalnych
I
T
P
W
ZPT
8
Przykład: uogólniamy U
1
U a b c d e
1
1 0 0 1
1
2 1 0 0 0 1
3
0 0 0 0
0
4
1 1 0 1
0
5
1 1 0 2
2
6
2 2 0 2
2
7
2 2 2 2
2
Macierz M powstaje przez porównanie obiektów: (u
1
, u
3
),
(u
1
, u
4
),
..., (u
1
, u
7
). Wynikiem porównania są wiersze M.
Dla takich samych wartości atrybutów odpowiedni m=0,
dla różnych m=1.
1
1
1
1
1
0
1
1
1
0
1
0
0
0
1
0
1
0
0
1
d
c
b
a
M
I
T
P
W
ZPT
9
Przykład: uogólniamy U
1
Minimalne pokrycia są:
{a,b} oraz {b,d},
1
1
1
1
1
0
1
1
1
0
1
0
0
0
1
0
1
0
0
1
d
c
b
a
M
a, b, c, d
a, b, d
b, d
b
a, d
Wyznaczone na ich podstawie minimalne reguły:
(a,1) & (b,0) (e,1)
(b,0) & (d,1) (e,1)
U a b c d e
1
1 0 0 1
1
2 1 0 0 0 1
U a b c d e
1
1 0 - -
1
2 1 0 0 0 1
I
T
P
W
ZPT
10
Przykład generacji reguł cd.
U a b c d e
1
1 0 - -
1
2 1 0 0 0 1
Po uogólnieniu obiektu u
1
u
2
.
u
2
można usunąć
U
a
b
c
d
e
1
1
0
-
-
1
2
1
0
0
0
1
3
0
0
0
0
0
4
1
1
0
1
0
5
1
1
0
2
2
6
2
2
0
2
2
7
2
2
2
2
2
I
T
P
W
ZPT
11
Przykład generacji reguł c.d.
1
1
1
1
1
0
1
1
1
0
1
1
0
0
0
1
1
0
0
1
d
c
b
a
U a b c d e
1 1 0 0 1 1
2 1 0 0 0 1
3
0 0 0 0
0
4
1 1 0 1
0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2
(a,0) (e,0)
(b,1) & (d,1) (e,0)
1
1
1
1
1
0
1
1
1
0
0
0
1
0
1
0
0
0
1
0
d
c
b
a
Dla obiektu u3
Dla obiektu u4
1101
0
0000
1
1
Niestety po uogólnieniu ani u
3
nie pokrywa u
4
, ani u
4
nie pokrywa u
3
I
T
P
W
ZPT
12
Przykład generacji reguł c.d.
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
0
d
c
b
a
U a b c d e
1 1 0 0 1 1
2 1 0 0 0 1
3 0 0 0 0 0
4 1 1 0 1 0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2
(d,2) (e,2)
Dla obiektu u5
2
u
6
, u
7
I
T
P
W
ZPT
13
Reguły minimalne
a b c d e
1 0 – – 1
0 – – – 0
– 1 – 1 0
– – – 2 2
(a,1) & (b,0) (e,1)
(a,0) (e,0)
(b,1) & (d,1) (e,0)
(d,2) (e,2)
(a,1) & (b,0) (e,1)
(a,0) (b,1) & (d,1) (e,0)
(d,2) (e,2)
w innym zapisie:
I
T
P
W
ZPT
14
Zastosowania
U a b c d e
1 1 0 0 1 1
2 1 0 0 0 1
3 0 0 0 0 0
4 1 1 0 1 0
5 1 1 0 2 2
6 2 2 0 2 2
7 2 2 2 2 2
Pierwotna tablica decyzyjna
a b c d e
1 0 – – 1
0 – – – 0
– 1 – 1 0
– – – 2 2
Tablica reguł minimalnych
Takie metody stosuje się w przypadkach, gdy dysponuje się zbiorem
obiektów, których przynależność do odpowiedniej klasy jest znana,
a celem jest identyfikacja nieznanych reguł klasyfikacji.
a=1,b=1, c=1, d=
1
Jaka decyzja?
Decyzja
e=0
I
T
P
W
ZPT
15
Sytuacja ta występuje np. przy wnioskach kredytowych składanych w bankach.
Ponieważ część z nich jest akceptowana, a część odrzucana, można dane
zebrane w dłuższym okresie czasu zapisać w tablicy decyzyjnej,
uogólnić i dalej stosować w uproszczonej formie do podejmowania decyzji.
Klientów charakteryzuje się za pomocą następujących cech
jakościowych i ilościowych:
- Sytuacja zawodowa: B (bezrobotny), P (pracujący)
- przeznaczenie kredytu: komputer (K), sprzęt audio (A), biżuteria (B)…
- wiek w latach
- stan konta
Zastosowania
Przykładowo:
I
T
P
W
ZPT
Przykładowa tablica danych...
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10 Klasa
P
K
K
S
nie
18
200
20
15
1
tak
P
K
K
S
nie
20
100
20
20
2
tak
B
K
K
R
tak
25
50
40
12
0
nie
•
•
•
P
S
M
R
nie
21
150
0
30
20
3
tak
P
S
M
S
nie
25
150
0
100
20
2
tak
P
S
M
R
nie
38
100
0
100
20
15
tak
16
Przeznaczenie:
Komp., sam.
wiek
Stan konta
Staż pracy w danym
zakładzie pracy
Sytuacja
zawodowa
I
T
P
W
ZPT
17
Zastosowania
[wiek > 25] & [stan konta > 70] & [staż pracy >
2]
tak
[płeć = kobieta] & [wiek < 25]
nie
…….
Po uogólnieniu reguł decyzyjnych…
LERS
I
T
P
W
ZPT
18
Reguły minimalne
LERS
.i 7
.o 1
.type fr
.p 9
1000101 0
1011110 0
1101110 0
1110111 0
0100101 1
1000110 1
1010000 1
1010110 1
1110101 1
.e
< a a a a a a a d >
[ x1 x2 x3 x4 x5 x6 x7 d ]
1 0 0 0 1 0 1 0
1 0 1 1 1 1 0 0
1 1 0 1 1 1 0 0
1 1 1 0 1 1 1 0
0 1 0 0 1 0 1 1
1 0 0 0 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 1
ESPRESSO
6
2
7
4
x
x
x
x
f
(x4,1) -> (d,0)
(x7,1) & (x1,1) & (x3,0) -> (d,0)
(x2,1) & (x6,1) -> (d,0)
(x4,0) & (x2,0) & (x6,1) -> (d,1)
(x6,0) & (x2,1) -> (d,1)
(x5,0) -> (d,1)
5
2
6
6
2
4
x
x
x
x
x
x
f
I
T
P
W
ZPT
19
Redukcja atrybutów
a
1
a
2
a
3
a
4
a
5
a
6
d
1
0
1
0
1
0
0
1
2
1
0
0
0
1
3
2
3
1
1
0
2
2
3
3
4
1
1
0
2
3
3
2
5
1
1
1
0
2
3
4
6
0
0
2
0
2
3
1
7
1
1
2
0
2
2
5
8
1
1
2
0
2
3
6
9
1
0
2
2
1
3
6
10
1
1
2
2
3
1
7
a
1
a
3
a
5
a
6
d
1
0
0
0
0
1
2
1
0
1
3
2
3
1
0
2
3
3
4
1
0
3
3
2
5
1
1
2
3
4
6
0
2
2
3
1
7
1
2
2
2
5
8
1
2
2
3
6
9
1
2
1
3
6
10
1
2
3
1
7
Redukty: {a
1
, a
3
, a
5
, a
6
} {a
2
, a
3
, a
5
,
a
6
}
I
T
P
W
ZPT
20
Przykład redukcji atrybutów
3
3
1
2
3
2
0
0
1
0
a
4
2
2
0
0
2
0
0
1
0
0
a
5
1
1
2
2
1
7
4
0
0
1
0
9
3
1
1
0
0
8
4
0
2
2
2
1
0
2
0
2
2
1
6
3
1
0
1
0
5
2
1
1
1
0
4
2
1
2
2
1
3
1
0
1
0
0
2
1
0
0
0
0
1
d
a
6
a
3
a
2
a
1
ponieważ wiersze 6 i 10
różnią się na pozycji a
1
a
1
a
6
a wiersze 2 i 8
różnią się na
pozycji a
6
I
T
P
W
ZPT
21
Przykład redukcji atrybutów
3
3
1
2
3
2
0
0
1
0
a
4
2
2
0
0
2
0
0
1
0
0
a
5
1
1
2
2
1
7
4
0
0
1
0
9
3
1
1
0
0
8
4
0
2
2
2
1
0
2
0
2
2
1
6
3
1
0
1
0
5
2
1
1
1
0
4
2
1
2
2
1
3
1
0
1
0
0
2
1
0
0
0
0
1
d
a
6
a
3
a
2
a
1
10)
;
3,6,7
;
,9
(1,2,4,5,8
P
1
3,4,5,7,8)
;
0
(1,2,6,9,1
P
6
9,10)
;
5,8
;
3,4,6
;
(1,2,7
P
D
(10)
;
(3)(7)
;
(6)
;
(4)(5,8)
;
(1,2)(9)
P
|
P
P
D
6
1
I
T
P
W
ZPT
22
Przykład redukcji atrybutów
3
3
1
2
3
2
0
0
1
0
a
4
2
2
0
0
2
0
0
1
0
0
a
5
1
1
2
2
1
7
4
0
0
1
0
9
3
1
1
0
0
8
4
0
2
2
2
1
0
2
0
2
2
1
6
3
1
0
1
0
5
2
1
1
1
0
4
2
1
2
2
1
3
1
0
1
0
0
2
1
0
0
0
0
1
d
a
6
a
3
a
2
a
1
a
2
, a
4
, a
5
(10)
;
(3)(7)
;
(6)
;
(4)(5,8)
;
(1,2)(9)
P
|
P
P
D
6
1
1,9
2,9
4,5
4,8
3,7
(a
4
+ a
2
) (a
4
+ a
3
) (a
4
+ a
5
) = a
4
+
a
2
a
3
a
5
a
2
, a
3
, a
4
,
a
5
a
3
, a
4
a
2
, a
4
a
4
, a
5
{a
1
, a
4
, a
6
}
{a
1
, a
2
, a
3
, a
5
, a
6
}
I
T
P
W
ZPT
23
Dekompozycja tablic decyzyjnych
B
A
G
H
Decyzja
końcowa
Atrybuty
Tablica
decyzyjna
Decyzja
pośrednia
Atrybuty
I
T
P
W
ZPT
24
Dekompozycja tablic decyzyjnych
F = H(A,G(B))
G
P(B):
P(A)
G
P
D
B
A
G
H
Decyzja
końcowa
Decyzja
pośrednia
I
T
P
W
ZPT
25
Przykład dekompozycji TD
(10)
;
(3)(7)
;
(6)
;
(4)(5,8)
;
(1,2)(9)
P
|
P
D
U
3
3
1
2
3
2
0
0
1
0
a
4
2
2
0
0
2
0
0
1
0
0
a
5
1
1
2
2
1
7
4
0
0
1
0
9
3
1
1
0
0
8
4
0
2
2
2
1
0
2
0
2
2
1
6
3
1
0
1
0
5
2
1
1
1
0
4
2
1
2
2
1
3
1
0
1
0
0
2
1
0
0
0
0
1
d
a
6
a
3
a
2
a
1
A =
{a
4
, a
5
,
a
6
}
B =
{a
1
, a
2
,
a
3
}
)
8
;
6,9,10
;
5,7
;
4
;
3
;
2
;
1
(
P(A)
)
10
;
5,9
;
4
;
3,6,7
;
2,8
;
1
(
P(B)
)
9,10
;
5,8
;
3,4,6
;
1,2,7
(
P
D
)
5,9,10
;
7,8
1,2,3,4,6,
(
G
I
T
P
W
ZPT
26
Przykład c.d.
F
a
1
a
2
a
3
g
1
0
0
0
1
2
0
0
1
1
3
1
2
2
1
4
0
1
1
1
5
0
1
0
2
6
2
2
2
2
a
4
a
5
a
6
g
d
1
0
0
0
1
1
2
1
0
0
1
1
3
0
1
1
1
2
4
0
0
1
1
2
5
2
0
1
2
3
6
3
2
0
1
2
7
2
0
1
1
1
8
1
0
1
1
3
9
3
2
0
2
4
G:
H:
I
T
P
W
ZPT
27
Kompresja danych
S
F
= 130 jednostek
S
G
= 42 jednostki
S
H
= 72 jednostki
S = pq
i
Dekompozycja
S
G
+ S
H
= 87% S
F
I
T
P
W
ZPT
28
Przykład
!, D e c is io n ta b le f o r h o u s e o f r e p s . !,
< D A A A A A A A A A A A A A A A A >
!,
[ C L A S S - N A M E H A N D I C A P P E D - I N F A N T S W A T E R - P R O J E C T - C O S T - S H A R I N G
A D O P T I O N - O F - T H E - B U D G E T - R E S O L U T I O N P H Y S I C I A N - F E E - F R E E Z E E L -
S A L V A D O R - A I D R E L I G I O U S - G R O U P S - I N - S C H O O L S A N T I - S A T E L L I T E - T E S T - B A N
A I D - T O - N I C A R A G U A N - C O N T R A S M X - M I S S I L E I M M I G R A T I O N
S Y N F U E L S - C O R P O R A T I O N - C U T B A C K E D U C A T I O N - S P E N D I N G S U P E R F U N D -
R I G H T - T O - S U E C R I M E D U T Y - F R E E - E X P O R T S E X P O R T - A D M I N I S T R A T I O N - A C T -
S O U T H - A F R I C A ]
!,
!, N o w th e d a ta
!,
d e m o c r a t
n y y n y y n n n n n n y y y y
r e p u b lic a n
n y n y y y n n n n n y y y n y
r e p u b lic a n
n n y y y y n n y y n y y y n y
d e m o c r a t
n n y n n n y y y y n n n n n y
. . . . . . . . . . . .
. . . . . . . . . . . .
68%
kompresji
danych
I
T
P
W
ZPT
29
I
T
P
W
ZPT
30
Przykład: zastosowanie dekompozycji w
nauczaniu sieci neuronowych
Przykłady
rd53 rd73 rd84 root s8 sao2 sqrt8 xor5 z4
Czas [s] 17
233 1200 1200 165 4004 470 432 108
Bez
dekompozycji Liczba
błędów
0
0
5
5
0
106
0
0
0
Czas [s] 9
29
53
661 26 586
52
67 56
Z
dekompozycją Liczba
błędów
0
0
0
0
0
0
0
0
0
I
T
P
W
ZPT
31
PODSUMOWANIE
Zagadnienia syntezy logicznej znajdują
szerokie zastosowanie w wielu dziedzinach
techniki:
w technice cyfrowej
w inżynierii informacji
w kryptografii
w sieciach neuronowych
Znaczenie syntezy logicznej ciągle
wzrasta, a USSL stają się niezbędnym
narzędziem w projektowaniu układów i
systemów cyfrowych
Uniwersyteckie Systemy Syntezy Logicznej:
SIS, (Espresso, NOVA, ...), ... DEMAIN