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 – 4. Zbiory przybliżone – MIM UW

Zagadnienia

4. Zbiory przybliżone

4.1. Zbiory przybliżone

4.1.1. Wprowadzenie do teorii zbiorów przybliżonych

4.1.1.1. Systemy informacyjne i tablice decyzyjne

  • Teoria zbiorów przybliżonych została wprowadzona w latach 80-tych przez prof. Zdzisława Pawlaka.

  • Głównym celem jest dostarczanie narzędzi dla problemu aproksymacji pojęć (zbiorów).

  • Zastosowania w systemach decyzyjnych:

    • Redukcja danych, selekcja ważnych atrybutów;

    • Generowanie reguł decyzyjnych;

    • Odkrywanie wzorców z danych: szablony, reguły asocjacyjne;

    • Odkrywanie zależności w danych.

\block

Definicja Jest to para \mathbb{S}=(U,A), gdzie

  • U – skończony niepusty zbiór obiektów (ang. cases, states, patients, observations …);

  • A – skończony, niepusty zbiór atrybutów. Każdy a\in A odpowiada pewnej funkcji a:U\rightarrow V_{a} zwanej wartościowaniem, gdzie V_{a} jest nazwana dziedziną atrybutu a.

Dla B\subseteq A, definiujemy

  • B-sygnatura obiektu x\in U (ang. B-information vector) jako

    {inf}_{B}(x)=\{(a,a(x)):a\in B\}
  • Zbiór sygnatur względem B o obiektach z U (ang. B-information set):

    INF(\mathbb{S})=\{ inf_{B}(x):x\in U\}

Tablica decyzyjna powstaje ze zwykłych tablic danych poprzez sprecyzowanie:

  • Atrybutów (nazwanych warunkowymi): cechy, których wartości na obiektach są dostępne, np. pomiary, parametry, dane osobowe, …

  • Decyzji (atrybut decyzyjny):, t.j. cecha “ukryta” związana z pewną znaną częściowo wiedzą o pewnym pojęciu:

    • Decyzja jest znana tylko dla obiektów z (treningowej) tablicy decyzyjnej;

    • Jest podana przez eksperta (np. lekarza) lub na podstawie późniejszych obserwacji (np. ocena giełdy);

    • Chcemy podać metodę jej wyznaczania dla dowolnych obiektów na podstawie wartości atrybutów warunkowych na tych obiektach.

\columns\column

4.5cm Przedstawiona tablica decyzyjna zawiera:

  • 8 obiektów będących opisami pacjentów

  • 3 atrybuty: Headache Muscle pain, Temp.

  • Decyzję stwierdzącą czy pacjent jest przeziębiony czy też nie. lub nie

\column

8cm \example
U Ból głowy Ból mięśni Temp. Grypa
p1 Tak Tak N Nie
p2 Tak Tak H Tak
p3 Tak Tak VH Tak
p4 Nie Tak N Nie
p5 Nie Nie H Nie
p6 Nie Tak VH Tak
p7 Nie Tak H Tak
p8 Nie Nie VH Nie

Dane są obiekty x,y\in U i zbiór atrybutów B\subset A, mówimy, że

  • x,yrozróżnialne przez B wtw, gdy istnieje a\in B taki, że a(x)\neq a(y);

  • x,ynierozróżnialne przez B, jeśli one są identyczne na B, tzn. a(x)=a(y) dla każdego a\in B;

  • [x]_{B} = zbiór obiektów nierozróżnialnych z x przez B.

  • Dla każdych obiektów x,y:

    • albo [x]_{B}=[y]_{B};

    • albo [x]_{B}\cap[y]_{B}=\emptyset.

  • Relacja

    x\  IND_{B}\  y:=x,y\text{ są nierozróżnialne przez }B

    jest relacją równoważności.

  • Każdy zbiór atrybutów B\subset A wyznacza podział zbioru obiektów na klasy nierozróżnialności.

Dla B=\{ Bólgłowy,Bólmięśni\}

\columns\column

4.5cm

  • obiekty p1,p2,p3 są nierozróżnialne;

  • są 3 klasy nierozróżnialności relacji IND_{B}:

    • [p1]_{B}=\{ p1,p2,p3\}

    • [p4]_{B}=\{ p4,p6,p7\}

    • [p5]_{B}=\{ p5,p8\}

\column

8cm \example
U Ból głowy Ból mięśni Temp. Grypa
p1 Tak Tak N Nie
p2 Tak Tak H Tak
p3 Tak Tak VH Tak
p4 Nie Tak N Nie
p5 Nie Nie H Nie
p6 Nie Tak VH Tak
p7 Nie Tak H Tak
p8 Nie Nie VH Nie

  • Każdy zbiór obiektów X (np. klasa decyzyjna, pojęcie) może być opisany za pomocą atrybutów ze zbioru B dokładnie lub w przybliżeniu

    • dokładny opis: jeśli X jest sumą pewnych klas nierozróznialności definiowanych przez B (ZBIORY DOKŁADNE)

    • przybliżony opis: w przeciwnym przypadku (ZBIORY PRZYBLIŻONE)

  • W obu przypadkach X może być opisany przez 2 “dokładne zbiory” zwane dolną i górną aproksymacją zbioru X

    \underline{B}(X)=\{ x:[x]_{B}\subset X\}\quad\overline{B}(X)=\{ x:[x]_{B}\cap X\neq\emptyset\}
  • Obszar brzegowy (ang. B-boundary region) pojęcia X zawiera obiekty, dla których nie możemy jednoznacznie zdecydować czy należą one do X czy nie na podstawie atrybutów z B

  • Obszar wewnętrzny (ang. B-inside region of X) zawiera obiekty, które możemy pewnie klasyfikować jako elementy pojęcia X mając do dyspozycji atrybuty z B.

  • Zbiór jest przybliżony (ang. rough set) jeśli obszar brzegowy jest niepusty, w przeciwnym przypadku zbiór jest nazwany dokładny (ang. crisp set).

\columns\column

6cmNiech B=\{ a_{1},a_{2}\} <2-> \onslide

\displaystyle IND(B)=\{ \displaystyle\{ 1,2\}, \displaystyle(sunny,hot)
\displaystyle\{ 3,13\}, \displaystyle(overcast,hot)
\displaystyle\{ 4,10,14\}, \displaystyle(rainy,mild)
\displaystyle\{ 5,6\}, \displaystyle(rainy,cool)
\displaystyle\{ 8,11\}, \displaystyle(sunny,mild)
\displaystyle\{ 7\},\{ 9\},\{ 12\}\}
\onslide

<3-> Chcemy aproksymować pojęcie definiowane przez klasę decyzyjną (play=no)

X=CLASS_{{no}}=\{ 1,2,6,8,14\}
\onslide

<4-> Aproksymacje pojęcia X:

\displaystyle\mathbf{L}_{B}(X) \displaystyle=\{ 1,2\}
\displaystyle\mathbf{U}_{B}(X) \displaystyle=\{ 1,2,{5},6,8,{11},{4},{10},14\}
\onslide

<5-> Reguła pewna:

\textbf{If }B(x)=(sunny,hot)\textbf{ then }d(x)={no}

\column

5.4cm \onslide<1->
{\mathbb{A}}\hfil\mid a_{1} a_{2} a_{3} a_{4}\hfil\mid d
ID\hfil\mid outlook temp. hum. windy\hfil\mid play
1\hfil\mid sunny hot high FALSE\hfil\mid no
2\hfil\mid sunny hot high TRUE\hfil\mid no
3\hfil\mid overcast hot high FALSE\hfil\mid yes
4\hfil\mid rainy mild high FALSE\hfil\mid yes
5\hfil\mid rainy cool normal FALSE\hfil\mid yes
6\hfil\mid rainy cool normal TRUE\hfil\mid no
7\hfil\mid overcast cool normal TRUE\hfil\mid yes
8\hfil\mid sunny mild high FALSE\hfil\mid no
9\hfil\mid sunny cool normal FALSE\hfil\mid yes
10\hfil\mid rainy mild normal FALSE\hfil\mid yes
11\hfil\mid sunny mild normal TRUE\hfil\mid yes
12\hfil\mid overcast mild high TRUE\hfil\mid yes
13\hfil\mid overcast hot normal FALSE\hfil\mid yes
14\hfil\mid rainy mild high TRUE\hfil\mid no

\onslide

<5-> Reguły przybliżone:

\displaystyle\textbf{If }B(x)=(rainy,cool)\textbf{ then }d(x)={no}
\displaystyle\textbf{If }B(x)=(rainy,mild)\textbf{ then }d(x)={no}
\displaystyle\textbf{If }B(x)=(sunny,mild)\textbf{ then }d(x)={no}
\block

Jakość aproksymacji (ang. accuracy of approximation)

\alpha _{B}(X)=\frac{|\underline{B}(X)|}{|\overline{B}(X)|}
  • 0\leq\alpha _{B}(X)\leq 1

  • Jeśli \alpha _{B}(X)=1, to zbiór X jest dokładnie definiowany przez B;

  • Jeśli \alpha _{B}(X)<1, to zbiór X jest aproksymacyjnie definiowany przez B;

4.1.1.2. Redukty

  • W systemach decyzyjnych, nie wszystkie atrybuty są potrzebne do procesie podejmowania decyzji;

  • Chcemy wybrać pewne podzbiory atrybutów niezbędnych do tego celu;

  • Redukty to minimalne podzbiory atrybutów zachowujących charakterystykę całego zbioru atrybutów.

  • W teorii zbiorów przybliżonych, istnieją co najmniej 2 pojęcia reduktów: informacyjne i decyzyjne.

\block

Definicja reduktu informacyjnego Zbiór atrybutów B\subset A nazywamy reduktem tablicy decyzyjnej A wtw, gdy

  • B zachowuje rozróżnialność zbioru A:

    t.j. dla dowolnych obiektów x,y\in U,

    jeśli x,y są rozróżnialne przez A, to są również rozróżnialne przez B

  • B jest niezredukowalny:

    tzn. żaden właściwy podzbiór B nie zachowuje rozróżnialności zbioru A (t.j., B jest minimalny pod względem rozróżnialności)

\block

Definicja reduktu decyzyjnego Zbiór atrybutów B\subset A nazywamy reduktem tablicy A wtw, gdy

  • B zachowuje rozróżnialność zbioru A względem decyzji dec:

    t.j. dla dowolnych obiektów x,y\in U,

    jeśli dec(x)\neq dec(y) i x,y są rozróżnialne przez A, to są również rozróżnialne przez B

  • B jest niezredukowalny:

    tzn. żaden właściwy podzbiór B nie zachowuje rozróżnialności zbioru A (B jest minimalny pod względem rozróżnialności)

  • RED(\mathbb{S})= zbiór wszystkich reduktów tablicy decyzyjnej \mathbb{S};

  • Jeśli \mathbb{S}=(U,A\cup\{ dec\}) i |A|=n to

    |RED(\mathbb{S})|\leq\binom{n}{n/2}
  • rdzeń: zbiór atrybutów będących we wszystkich reduktach

    K=\bigcap _{{B\in RED(\mathbb{S})}}B.
  • Znaleźć rdzeń danej tablicy decyzyjnej;

  • Znaleźć jakiś redukt;

  • Znaleźć krótkie redukty;

  • Znaleźć długie redukty.

4.1.2. Złożoność problemu szukania reduktów

\onslide

<1-2> Problem najkrótszego reduktu \block

Dane:

Tablica decyzyjna \mathbb{S}=(U,A\cup\{ dec\});

Szukane:

“najkrótszy redukt tablicy decyzyjnej \mathbb{S}”, tzn. taki redukt decyzyjny B\in{\bf RED}(\mathbb{S},dec), że

\forall _{{X\in{\bf RED}(\mathbb{S},dec)}}|B|\leq|X|
\onslide

<2> Twierdzenie Problem szukania najkrótszego reduktu jest NP-zupełny. \block

  • <+-| alert@+> Ogólnie musimy pokazać, że jakiś znany NP-zupełny problem jest “łatwiejszy” od problemu najkrótszego reduktu;

  • <+-| alert@+> Wybierzmy problem minimalnego pokrycia wierzchołkami:

    “Dany jest graf G=(V,E). Znaleźć minimalny zbiór wierzchołków X\subset V o takiej własności, że każda krawędź z E posiada co najmniej jeden z końców w X.”

  • <+-| alert@+> Wielomianowa transformacja:

    \onslide

    <4->

    \onslide<5->\implies\onslide

    \mathbb{S}({\bf G}) a_{{v_{1}}} a_{{v_{2}}} a_{{v_{3}}} a_{{v_{4}}} a_{{v_{5}}} a^{*}
    x^{*} 0 0 0 0 0 0
    u_{{e_{1}}} 1 1 0 0 0 1
    u_{{e_{2}}} 1 0 0 1 0 1
    u_{{e_{3}}} 0 1 0 0 1 1
    u_{{e_{4}}} 0 1 0 1 0 1
    u_{{e_{5}}} 1 0 1 0 0 1
    u_{{e_{6}}} 0 0 1 0 1 1

  • <+-> Można też pokazać, że problem najkrótszego reduktu jest “łatwiejszy” niż znany problem “Minimal Hitting Set” (minimalny zbiór przecinający?)

    • Dane: Zbiór S i rodzina jego podzbiorów \{ S_{1},S_{2},...,S_{n}\}. Zbiór X\subset S nazywamy zbiórem przecinającym, jeśli X ma niepuste przecięcie z każdym ze zbiorów S_{1},S_{2},...,S_{n}.

    • Szukane: minimalny zbiór przecinający.

  • <+-> Te problemy są obliczeniowo równoważne!

    Czyli każdy algorytm dla jednego problemu można przeksztalcić w czasie wielomianowym na odpowiedni algorytmu dla drugiego problemu, który posiada te same cechy zlożonościowe.

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.