Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 5. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł – MIM UW

Zagadnienia

5. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1.1. Metody wnioskowań Boolowskich w szukaniu reduktów

5.1.1.1. Algebry Boola

\columns\column

9cm Algebra Boola Jest to struktura algebraiczna \definition

\mathcal{B}=(B,+,\cdot,0,1)

spełniająca następujące aksjomaty

- Przemienność:

(a+b)=(b+a)\mbox{ oraz }(a\cdot b)=(b\cdot a)

- Rozdzielność:

a\cdot(b+c)=(a\cdot b)+(a\cdot c),\mbox{ oraz}a+(b\cdot c)=(a+b)\cdot(a+c)

- Elementy neutralne:

a+0=a\text{ oraz }a\cdot 1=a

- Istnienie elementu komplementarnego:

a+\overline{a}=1\mbox{ and }a\cdot\overline{a}=0

*) Czasem negacja jest dodana do sygnatury algebry Boola.

  1. <+-> Algebra zbiorów: \mathbb{P}(X)=(2^{X},\cup,\cap,-,\emptyset,X);

  2. <+-> Rachunek zdań

    (\{ zdania\  logiczne\},\vee,\wedge,\neg,\bot,\top)
  3. <+-> Binarna algebra Boola \mathcal{B}_{2}=(\{ 0,1\},+,\cdot,0,1) to jest najmniejsza, ale najważniejsza algebra Boola w zastosowaniu.

    \begin{array}[]{c|c|c|c}x&y&x+y&x\cdot y\\
\hline 0&0&0&0\\
0&1&1&0\\
1&0&1&0\\
1&1&1&1\\
\hline\end{array}\qquad\begin{array}[]{c|c}x&\neg x\\
\hline 0&1\\
1&0\\
\end{array}

    Przykłady zastosowań:

    • projektowanie układów scalonych;

    • rachunek zdań.

Łączność (ang. Associative law):

\qquad(x+y)+z=x+(y+z)\mbox{ oraz }(x\cdot y)\cdot z=x\cdot(y\cdot z)

Idempotence:

\qquad\qquad x+x=x\quad oraz\quad x\cdot x=x(dual)

Działania z 0 i 1:

\qquad x+1=1\quad oraz\quad x\cdot 0=0(dual)

Pochłanienie (ang. Absorption laws):

\qquad(y\cdot x)+x=x\quad oraz\quad(y+x)\cdot x=x(dual)

Inwolocja (ang. Involution laws):

\qquad\overline{(\overline{x})}=x

Prawa DeMorgana (ang. DeMorgan's laws):
\displaystyle\neg(x+y) \displaystyle=\neg x\cdot\neg y\quad oraz\quad\neg(x\cdot y)=\neg x+\neg y(dual)
Prawa konsensusu (ang. Consensus laws):
\displaystyle(x+y)\cdot(\overline{x}+z)\cdot(y+z) \displaystyle=(x+y)\cdot(\overline{x}+z)\text{ oraz }
\displaystyle(x\cdot y)+(\overline{x}\cdot z)+(y\cdot z) \displaystyle=(x\cdot b)+(\overline{x}\cdot z)
Zasada dualności:

Każda algebraiczna równość pozostaje prawdziwa jeśli zamieniamy operatory + na \cdot, \cdot na +, 0 na 1 oraz 1 na 0.

5.1.1.2. Funkcje Boolowskie i wnioskowanie Boolowskie

  • <+-> Każde odwzorowanie f:\{ 0,1\}^{n}\rightarrow\{ 0,1\} nazywamy (zupełną) funkcją Boolowską.

  • <+-> Funkcje Boolowskie \equiv formuły Boolowskie:

    • Stałe, zmienne, operatory \overline{\ }, + oraz .

    • Literały, mintermy (jednomiany), maxtermy, …

    • Kanoniczna postać dyzjunkcyjna (DNF), np. f=xy\overline{z}+x\overline{y}z+\overline{x}yz+xyz;

    • Kanoniczna postać koniunkcyjna (CNF), np. f=(x+y+z)(\overline{x}+y)

  • <+-> Term t=x_{{i_{1}}}...x_{{i_{m}}}\overline{x_{{j_{1}}}}...\overline{x_{{j_{k}}}} nazywamy implikantem funkcji f jeśli

    \forall _{{{\bf a}\in\{ 0,1\}^{n}}}\quad t({\bf a})=1\Rightarrow f({\bf a})=1

  • <+-> Implikant pierwszy: jest to implikant, który przestaje nim być po usunięciu dowolnego literału.

  • <+-> Kanoniczna postać Blake'a: każdą funkcję Boolowską można przedstawić jako sumę wszystkich jej imlikantów pierwszych:

    f=t_{1}+t_{2}+...+t_{k}

Wiele formuł reprezentuje tę samą funkcję;

\phi _{1}=xy\overline{z}+x\overline{y}z+\overline{x}yz+xyz

\phi _{2}=(x+y+z)(\overline{x}+y+z)(x+\overline{y}+z)(x+y+\overline{z})

\phi _{3}=xy+xz+yz

xy\overline{z} jest implikantem

xy jest implikantem pierwszym

x y z f
0 0 0 0
1 0 0 0
0 1 0 0
1 1 0 1
0 0 1 0
1 0 1 1
0 1 1 1
1 1 1 1
  • <+-> Niech \prec oznacza relację częściowego porządku w \{ 0,1\}^{n}

  • <+-> Funkcja f jest monotoniczna (niemalejąca) wtw, gdy dla każdych {\bf x,y}\in\{ 0,1\}^{n} jeśli \bf x\prec y to f({\bf x})\leq f({\bf y})

  • <+-> monotoniczne funkcje Boolowskie można zapisać bez użycia negacji.

  • <+-> term f^{{\prime}}=x_{{i_{1}}}\cdot x_{{i_{2}}}...\cdot x_{{i_{k}}} nazywamy implikantem pierwszym funkcji monotonicznej f jeśli

    • f^{{\prime}}({\bf x})\leqslant f({\bf x}) dla każdego wektora \bf x (jest implikantem)

    • każda funkcja większa od f^{{\prime}} nie jest implikantem

  • <+-> Np. funkcja

    f(x_{1},x_{2},x_{3})=(x_{1}+x_{2})(x_{2}+x3)

    posiada 2 implikanty pierwsze: f_{1}=x_{2} i f_{2}=x_{1}\wedge x_{3}

 

 

  1. Modelowanie: Kodowanie problemu za pomocą układu równań Boolowskich;

  2. Redukcja: Sprowadzenie układu równań do pojedynczego równania postaci f=0\quad\text{lub}\quad f=1

  3. Konstrukcja: Znalezienie wszystkich implikantów pierwszych funkcji f (konstrukcja kanonicznej postaci Blake'a);

  4. Dedukcja: Zastosowanie pewnej sekwencji wnioskowań transformujących implikanty pierwsze do rozwiązań problemu.

\columns\column

6cm <1-> \onslide 

Problem:

A,B,C,D are considering going to a party. Social constrains:

  • If A goes than B won't go and C will;

  • If B and D go, then either A or C (but not both) will go

  • If C goes and B does not, then D will go but A will not.

 

\onslide

<2-> Problem modeling:

\displaystyle\scriptsize A\rightarrow\overline{B}\wedge C \displaystyle\leftrightsquigarrow A(B+\overline{C}) \displaystyle=0
\displaystyle... \displaystyle\leftrightsquigarrow BD(AC+\overline{AC}) \displaystyle=0
\displaystyle... \displaystyle\leftrightsquigarrow\overline{B}C(A+\overline{D}) \displaystyle=0
\column

6cm

  • <3-> After reduction:

    f=A(B+\overline{C})+BD(AC+\overline{AC})+\overline{B}C(A+\overline{D})=0

  • <4-> Blake Canonical form: f=B\overline{C}D+\overline{B}C\overline{D}+A=0

  • <5-> Facts:

    \displaystyle BD \displaystyle\longrightarrow C
    \displaystyle C \displaystyle\longrightarrow B\vee D
    \displaystyle A \displaystyle\longrightarrow 0
  • <6-> Reasoning: (theorem proving)

    e.g., show that

    ”nobody can go alone.”

\columns\column

7cm

  • <+-> Problem SAT: czy równanie

    f(x_{1},...,x_{n})=1

    posiada rozwiązanie?

  • <+-> SAT odgrywa ważną rolę w teorii złożoności (twierdzenie Cooka, dowodzenie NP-zupełności …)

  • <+-> Każdy SAT-solver może być używany do rozwiązywania problemu planowania.

  • <+-> Blocks world problem: Po redukcji formuła boolowska nadal zawiera O(tk^{2}) zmiennych i O(tk^{3}) klauzuli (k,t - liczby bloków i kroków).

  • <+-> Np. Dla k=15, t=14, mamy 3016 zmiennych i 50457 klausuli

\column

5cm<4->\only

\only

<3->

  1. <+-> Konstrukcja funkcji odróżnialności:

    • Zmienne boolowskie: atrybuty a_{1},...,a_{k};

    • Klauzula:

      \phi _{{u,v}}=\bigvee\{ a\in A:a(u)\neq a(v)\}
    • Funkcja rozróżnialności:

      \mathcal{F}_{{\mathbb{S}}}(a_{1},...,a_{k})=\bigwedge _{{x,y\in U:dec(x)\neq dec(y)}}\phi _{{x,y}}(a_{1},...,a_{k})
  2. <+-> przekształcenie funkcji rozróżnialności do postaci DNF

  3. <+-> każdy implikant pierwszy odpowiada jednemu reduktowi;

Hurt. Jakość obsługi Jakość towaru Obok autostrady? Centrum? decyzja
ID a_{1} a_{2} a_{3} a_{4} dec
1 dobra dobra nie nie strata
2 dobra dobra nie tak strata
3 bdb dobra nie nie zysk
4 slaba super nie nie zysk
5 slaba niska tak nie zysk
6 slaba niska tak tak strata
7 bdb niska tak tak zysk
8 dobra super nie nie strata
9 dobra niska tak nie zysk
10 slaba super tak nie zysk
11 dobra super tak tak zysk
12 bdb super nie tak zysk
13 bdb dobra tak nie ?
14 slaba super nie tak ?
\mathbb{M} 1 2 6 8
3 a_{1} a_{1},a_{4} a_{1},a_{2},a_{3},a_{4} a_{1},a_{2}
4 a_{1},a_{2} a_{1},a_{2},a_{4} a_{2},a_{3},a_{4} a_{1}
5 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{4} a_{1},a_{2},a_{3}
7 a_{1},a_{2},a_{3},a_{4} a_{1},a_{2},a_{3} a_{1} a_{1},a_{2},a_{3},a_{4}
9 a_{2},a_{3} a_{2},a_{3},a_{4} a_{1},a_{4} a_{2},a_{3}
10 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{2},a_{4} a_{1},a_{3}
11 a_{2},a_{3},a_{4} a_{2},a_{3} a_{1},a_{2} a_{3},a_{4}
12 a_{1},a_{2},a_{4} a_{1},a_{2} a_{1},a_{2},a_{3} a_{1},a_{4}
\displaystyle f \displaystyle= \displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})
\displaystyle(\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})(\alpha _{2}\vee\alpha _{4})
\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})
\displaystyle f \displaystyle= \displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})
\displaystyle(\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})(\alpha _{2}\vee\alpha _{4})
\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})
  • <+-> usuwanie alternatyw regułą pochłaniania (t.j. p\wedge(p\vee q)\equiv p):

    \displaystyle f \displaystyle= \displaystyle(\alpha _{1})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})
  • <+-> sprowadzanie funkcji f z postaci CNF (koniunkcja alternatyw) do postaci DNF (alternatywa koniunkcji)

    \displaystyle f \displaystyle= \displaystyle\alpha _{1}\alpha _{4}\alpha _{2}\vee\alpha _{1}\alpha _{4}\alpha _{3}
  • <+-> Każdy składnik jest reduktem! Zatem mamy 2 redukty: R_{1}=\{ A_{1},A_{2},A_{4}\} i R_{2}=\{ A_{1},A_{3},A_{4}\}

5.1.1.3. Heurystyka Johnsona

  • <+-> Atrybut jest ważniejszy jeśli częściej występuje w klauzulach;

  • <+-> Selekcja: W każdym kroku wybierzmy atrybut, który najczęściej występuje w funkcji rozróżnialności;

  • <+-> Usuwanie: Usuwamy z tej funkcji te klauzule, które zawierają wybrany atrybut;

  • <+-> Powtarzamy Selekcja i Usuwanie dopóty, póki funkcja rozróżnialności zawiera jeszcze jakąś klazulę.

 

Heurystyka Johnsona

  1. Znaleźć atrybut, który występuje najczęściej w macierzy rozróżnialności;

  2. Usuwnąć wszystkie pola zawierające wybrany atrybut;

  3. Powtarzamy kroki 1 i 2 dopóki wszystkie pola macierzy są puste.

 

\mathbb{M} 1 2 6 8
3 a_{1} a_{1},a_{4} a_{1},a_{2},a_{3},a_{4} a_{1},a_{2}
4 a_{1},a_{2} a_{1},a_{2},a_{4} a_{2},a_{3},a_{4} a_{1}
5 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{4} a_{1},a_{2},a_{3}
7 a_{1},a_{2},a_{3},a_{4} a_{1},a_{2},a_{3} a_{1} a_{1},a_{2},a_{3},a_{4}
9 a_{2},a_{3} a_{2},a_{3},a_{4} a_{1},a_{4} a_{2},a_{3}
10 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{2},a_{4} a_{1},a_{3}
11 a_{2},a_{3},a_{4} a_{2},a_{3} a_{1},a_{2} a_{3},a_{4}
12 a_{1},a_{2},a_{4} a_{1},a_{2} a_{1},a_{2},a_{3} a_{1},a_{4}
  • W macierzy nierozróznialności z poprzedniego przykładu

    \qquada_{1} - występuje 23 razy \qquad a_{2} - występuje 23 razy

    \qquada_{3} - występuje 18 razy \qquad a_{4} - występuje 16 razy

  • Jeśli wybieramy a_{1}, to po usunięciu pól zawierających a_{1} zostało 9 niepustych pól macierzy nierozróżnialności. Wśród nich:

    a_{2} - występuje 7 razy \quad a_{3} - występuje 7 razy \quad a_{4} - występuje 6 razy

  • Jeśli wybieramy tym razem a_{2} to zostały 2 niepuste pola i wśród nich a_{4} jest zdecydowanym faworytem.

  • Możemy dostać w ten sposób redukt: R_{1}=\{ a_{1},a_{2},a_{4}\}.

  • Niech X=\{(u,v)\in U^{2}:dec(u)\neq dec(v)\};

  • Niech S_{{a_{i}}}=\{(u,v)\in X:a_{i}(u)\neq a_{i}(v)\};

  • Niech C^{{*}}\subset A będzie minimalnym reduktem, lecz C=\{ a_{1},...,a_{k}\} będzie reduktem znalezionym przez heurystykę Johnsona;

  • Załóżmy, że heurystyka Johnsona musi płacić 1zł za każdym razem, gdy dodała {a_{i}} do C.

  • Rozłóżmy ten koszt tym elementom, które zostały po raz pierwszy pokryte przez zbiór S_{{a_{i}}}

  • Niech c_{x} = koszt ponoszony przez x. Jeśli x jest pokryty po raz pierwszy przez a_{i}, to

    c_{x}=\frac{1}{|S_{{a_{i}}}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|}
  • Heurystyka Johnsona ponosi łączny koszt =|C|. Mamy

    |C|=\sum _{{x\in X}}c_{x}\leq\sum _{{a\in C^{*}}}\sum _{{x\in S_{{a}}}}c_{x}
  • Gdybyśmy pokazali, że dla dowolnego altrybutu a\in A

    \sum _{{x\in S_{{a}}}}c_{x}\leq H(|S_{{a}}|)

    gdzie H(n)=\sum _{{i=1}}^{n}\frac{1}{i}, wówczas możemy oszacować dalej:

    \displaystyle|C| \displaystyle\leq\sum _{{a\in C*}}\sum _{{x\in S_{{a}}}}c_{x}\leq|C^{*}|\cdot H(\max\{|S_{{a}}:a\in A|\})
    \displaystyle\leq|C^{*}|\cdot H(|X|)\leq|C^{*}|\cdot\ln(|X|+1)

 Lemat:

Dla dowolnego altrybutu a\in A

\sum _{{x\in S_{{a}}}}c_{x}\leq H(|S_{{a}}|)

 

Dowód:

  • Niech u_{i}=|S_{a}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|, mamy:

    u_{0}=|S_{a}|\geq...\geq u_{{i-1}}\geq u_{i}\geq...\geq u_{k}=0;

    gdzie k jest najmniejszym indeksem t., że S_{a}=S_{{a_{1}}}\cup...\cup S_{{a_{k}}}

  • Zatem

    \displaystyle\sum _{{x\in S_{a}}}{c_{x}} \displaystyle=\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{|S_{{a_{i}}}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|}
    \displaystyle\leq\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{u_{{i-1}}}\leq\sum _{{i=0}}^{k}(H(u_{{i-1}})-H(u_{i}))=H(|S_{a}|)

5.1.1.4. Inne heurystyki

  • ILP (Integer Linear Program)

  • Symulowane wyżarzanie (simulated annealing)

  • Algorytmy genetyczne

  • SAT solver

  • ???

Dana jest funkcja f:\{ 0,1\}^{n}\rightarrow\{ 0,1\} zapisana w postaci CNF za pomocą zmiennych x_{1},...,x_{n}

  1. Utwórz nowe zmienne \{ y_{1},...,y_{{2n}}\} odpowiadające literałom x_{1},\overline{x_{1}},...,x_{n},\overline{x_{n}};

  2. Dla każdej zmiennej x_{i}, utwórzmy nierówność y_{{2i-1}}+y_{{2i}}\leq 1

  3. Zamień każdą klausulę \omega _{i}=(l_{{i_{1}}}\vee...\vee l_{{i_{{n_{i}}}}}) na nierówność y_{{i_{1}}}+...+y_{{i_{{n_{i}}}}}\geq 1;

  4. Utwórzmy układ nierówności z poprzednich punktów:

    \mathbf{A}\mathbf{y}\geq\mathbf{b}
  5. Zagadnienie programowania liniowego liczb całkowitych (ILP) jest definiowane jako problem szukania

    \min\sum _{{i=1}}^{{n}}y_{i}\quad\text{ przy ograniczeniu:  }\mathbf{A}\mathbf{y}\geq\mathbf{b}.

5.1.2. Systemy decyzyjne oparte o zbiory przybliżone

5.1.2.1. Reguły decyzyjne

Dla danego zbioru atrybutów A definiujemy język deskryptorów jako trójkę

\mathcal{L}(A)=(\mathbf{D},\{\vee,\wedge,\neg\},\mathbf{F})

gdzie

  • \mathbf{D} jest zbiorem deskryptorów

    \mathbf{D}=\{(a=v):a\in A\text{ and }v\in Val_{a}\};
  • \{\vee,\wedge,\neg\} jest zbiorem standardowych operatorów logicznych;

  • \mathbf{F} jest zbiorem formuł logicznych zbudowanych na deskryptorach z \mathbf{D}.

  • Dla każdego zbioru atrybutów B\subseteq A oznaczamy:

    \mathbf{D}|_{B}=\{(a=v):a\in B\text{ and }v\in Val_{a}\}, czyli zbiór deskryptorów obciętych do B.

    \mathbf{F}|_{B} zbiór formuł zbudowanych na \mathbf{D}|_{B}.

 

Semantyka:

Niech \mathbb{S}=(U,A) będzie tablicą informacyjną. Każda formuła \phi\in\mathbf{F}, jest (semantycznie) skojarzona ze zbiorem [[\phi]]_{{\mathbb{S}}} zawierającym obiekty spełniające \phi.

Formalnie możemy indukcyjnie definiować semantykę jak następująco:

\displaystyle[[(a=v)]]_{{\mathbb{S}}} \displaystyle=\{ x\in U:a(x)=v\} (5.1)
\displaystyle[[\phi _{1}\vee\phi _{2}]]_{{\mathbb{S}}} \displaystyle=[[\phi _{1}]]_{{\mathbb{S}}}\cup[[\phi _{2}]]_{{\mathbb{S}}} (5.2)
\displaystyle[[\phi _{1}\wedge\phi _{2}]]_{{\mathbb{S}}} \displaystyle=[[\phi _{1}]]_{{\mathbb{S}}}\cap[[\phi _{2}]]_{{\mathbb{S}}} (5.3)
\displaystyle[[\neg\phi]]_{{\mathbb{S}}} \displaystyle=U\setminus[[\phi]]_{{\mathbb{S}}} (5.4)

 

Każda formuła \phi może być charakteryzowana przez:

  • length(\phi)= liczba deskryptorów w \phi;

  • support(\phi)=|[[\phi]]_{{\mathbb{S}}}|= liczba obiektów spełniających formułę

\definition

Definicja reguł decyzyjnych Niech \mathbb{S}=\{ U,A\cup\{ dec\}\} będzie tablicą decyzyjną. Regułą decyzyjną dla \mathbb{S} nazywamy formuły postaci:

\phi\Rightarrow\delta

gdzie \phi\in\mathbf{F}_{A} i \delta\in\mathbf{F}_{{dec}}.

Formułę \phi nazywamy poprzednikiem (lub założeniem) reguły \mathbf{r}, a \delta nazywamy następnikiem (lub tezą) reguły \mathbf{r}.

Oznaczamy poprzednik i następnik reguły \mathbf{r} przez prev(\mathbf{r}) oraz cons(\mathbf{r}).

\definition

Reguły atomowa: Są to reguły postaci:

\mathbf{r}\equiv(a_{{i_{1}}}=v_{1})\wedge...\wedge(a_{{i_{m}}}=v_{m})\Rightarrow(dec=k) (5.5)

Każda reguła decyzyjna {\bf r} postaci (5.5) może być charakteryzowana następującymi cechami:

length({\bf r}) = liczba deskryptorów występujących w założeniu reguły {\bf r}
[{\bf r}] = nośnik reguły {\bf r}, czyli zbiór obiektów z U spełniających założenie reguły {\bf r}
support({\bf r}) = liczba obiektów z U spełniających założenie reguły{\bf r}: support({\bf r})=card([{\bf r}])
confidence({\bf r}) = wiarygodność reguły {\bf r}: confidence({\bf r})=\frac{|[{\bf r}]\cap DEC_{k}|}{|[{\bf r}]|}

Mówimy, że reguła {\bf r} jest niesprzeczna z \mathbb{A} jeśli

confidence({\bf r})=1
\definition

Minimalne niesprzeczne reguły: Niech \mathbb{S}=(U,A\cup\{ dec\}) będzie daną tablicą decyzyjną. Niesprzeczną regułę

(a_{{i_{1}}}=v_{1})\wedge...\wedge(a_{{i_{m}}}=v_{m})\Rightarrow(dec=k)

nazywamy minimalną niesprzeczną regułą decyzyjną jeśli usunięcie któregokolwiek z deskryptorów spowoduje, że reguła przestaje być niesprzezcna z \mathbb{S}.

5.1.2.2. Regułowe systemy decyzyjne

Klasyfikatory regułowe dzialają w trzech fazach:

  1. Faza treningu: Generuje pewien zbiór reguł RULES({\mathbb{A}}) z danej tablicy decyzyjnej \mathbb{A}.

  2. Faza selekcji reguł: Szuka w RULES({\mathbb{A}}) tych reguł, które są wspierane przez obiekt x. Oznaczamy zbiór tych reguł przez MatchRules({\mathbb{A}},x).

  3. Faza klasyfikacji: wyznacza klasędecyzyjną dla x za pomocą reguł z MatchRules({\mathbb{A}},x) według następującego schematu:

    1. Jeśli MatchRules({\mathbb{A}},x) jest pusty: odpowiedź dla x jest ``NIEWIEM^{{\prime\prime}}, tzn. nie mamy podstaw, aby klasyfikować obiekt x do którejkolwiek z klas;

    2. Jeśli MatchRules({\mathbb{A}},x) zawiera tylko obiekty z k-tej klasy: wówczas dec(x)=k;

    3. Jeśli MatchRules({\mathbb{A}},x) zawiera reguły dla różnych klas decyzyjnych: wówczas decyzja dla x określimy za pomocą pewnego, ustalonego schematu głosowania między regułami z MatchRules({\mathbb{A}},x).

5.1.2.3. Szukanie minimalnych reguł decyzyjnych

  • Każda reguła powstaje poprzez skracanie opisu jakiegoś obiektu.

  • Redukty lokalne

  • Te same heurystyki dla reduktów decyzyjnych.

Hurt. Jakość obsługi Jakość towaru Obok autostrady? Centrum? decyzja
ID a_{1} a_{2} a_{3} a_{4} dec
1 dobra dobra nie nie strata
2 dobra dobra nie tak strata
3 bdb dobra nie nie zysk
4 slaba super nie nie zysk
5 slaba niska tak nie zysk
6 slaba niska tak tak strata
7 bdb niska tak tak zysk
8 dobra super nie nie strata
9 dobra niska tak nie zysk
10 slaba super tak nie zysk
11 dobra super tak tak zysk
12 bdb super nie tak zysk
13 bdb dobra tak nie ?
14 slaba super nie tak ?
\mathbb{M} 1 2 6 8
3 a_{1} a_{1},a_{4} a_{1},a_{2},a_{3},a_{4} a_{1},a_{2}
4 a_{1},a_{2} a_{1},a_{2},a_{4} a_{2},a_{3},a_{4} a_{1}
5 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{4} a_{1},a_{2},a_{3}
7 a_{1},a_{2},a_{3},a_{4} a_{1},a_{2},a_{3} a_{1} a_{1},a_{2},a_{3},a_{4}
9 a_{2},a_{3} a_{2},a_{3},a_{4} a_{1},a_{4} a_{2},a_{3}
10 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{2},a_{4} a_{1},a_{3}
11 a_{2},a_{3},a_{4} a_{2},a_{3} a_{1},a_{2} a_{3},a_{4}
12 a_{1},a_{2},a_{4} a_{1},a_{2} a_{1},a_{2},a_{3} a_{1},a_{4}
\displaystyle f_{{u_{3}}} \displaystyle= \displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})=\alpha _{1}

Reguły:

(a_{1}=\text{bdb})\implies dec=\text{zysk}
\mathbb{M} 1 2 6 8
3 a_{1} a_{1},a_{4} a_{1},a_{2},a_{3},a_{4} a_{1},a_{2}
4 a_{1},a_{2} a_{1},a_{2},a_{4} a_{2},a_{3},a_{4} a_{1}
5 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{4} a_{1},a_{2},a_{3}
7 a_{1},a_{2},a_{3},a_{4} a_{1},a_{2},a_{3} a_{1} a_{1},a_{2},a_{3},a_{4}
9 a_{2},a_{3} a_{2},a_{3},a_{4} a_{1},a_{4} a_{2},a_{3}
10 a_{1},a_{2},a_{3} a_{1},a_{2},a_{3},a_{4} a_{2},a_{4} a_{1},a_{3}
11 a_{2},a_{3},a_{4} a_{2},a_{3} a_{1},a_{2} a_{3},a_{4}
12 a_{1},a_{2},a_{4} a_{1},a_{2} a_{1},a_{2},a_{3} a_{1},a_{4}
\displaystyle f_{{u_{8}}} \displaystyle= \displaystyle(\alpha _{1}\vee\alpha _{2})(\alpha _{1})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{2}\vee\alpha _{3})
\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{4})
\displaystyle= \displaystyle\alpha _{1}(\alpha _{2}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})=\alpha _{1}\alpha _{3}\vee\alpha _{1}\alpha _{2}\alpha _{4}

Reguły:

  • (a_{1}=\text{dobra})\wedge(a_{3}=\text{nie})\implies dec=\text{strata}

  • (a_{1}=\text{dobra})\wedge(a_{2}=\text{super})\wedge(a_{4}=nie)\implies dec=\text{strata}

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.