Wersja do oddania, Rozdzial 6 - Zbiory przyblizone, Rozdział III


  1. Zbiory przybliżone

Teoria zbiorów przybliżonych ma stosunkowo niedługą historię ponieważ jej podstawy zostały opracowane w latach siedemdziesiątych przez grupę polskich naukowców z IPI PAN i Uniwersytetu Warszawskiego pod kierownictwem Zdzisława Pawlaka. Jej założenia opublikowano w 1982 roku (Pawlak, 1982). Motorem powstania tej teorii była, pojawiająca się w praktycznych zastosowaniach konieczność analizy danych "nieostrych" czyli danych dotyczących obiektów, zjawisk, których nie możemy jednoznacznie odróżnić, a możemy je tylko, na podstawie ich charakterystyk, zaklasyfikować do pewnych grup.

Teoria zbiorów przybliżonych może zostać zastosowana w niżej wymienionych obszarach. Podając nazwy niektórych z tych obszarów przytoczono także ich nazwy angielskie, które są szerzej znane i lepiej utrwalone, niż odpowiednie terminy polskie.

Praktyczne wykorzystanie zbiorów przybliżonych obejmuje między innymi takie dziedziny jak medycyna, ekonomia, sterowanie. Opisy przykładów zastosowań z wymienionych dziedzin można znaleźć w (Mrózek, Płonka, 1999). W szczególności zbiory przybliżone należą do metod pozyskiwania wiedzy zawartej w danych i w konstrukcji regułowych baz wiedzy definiowanych poprzez zbiory warunków postaci:

IF {zbiór warunków} THEN {zbiór decyzji}

    1. Podstawowe pojęcia

Kluczowym zagadnieniem każdej metodologii analizy danych jest problem reprezentacji danych. Dla potrzeb teorii zbiorów przybliżonych (i nie tylko dla tych potrzeb, oczywiście) dane porządkuje się w postaci tablicy, której wiersze odpowiadają badanym obiektom, natomiast kolumny są etykietowane poprzez atrybuty (cechy) obiektów. Na przecięciu wiersza i kolumny pojawia się wartość atrybutu dla badanego obiektu. Tabele takiej postaci nazywa się niekiedy systemami informacyjnymi, chociaż w oczywisty sposób tabele takie nie wyczerpują klasy wszystkich możliwych systemów informatycznych.

W zapisie formalnym, operujemy na zbiorze obiektów (O), zbiorze atrybutów (A), zbiorze wartości (W) i definiujemy funkcję (f), która parze (obiekt, atrybut) przypisuje odpowiednią wartość atrybutu, czyli:

f: O × A → W

Jeżeli przyjmiemy, że zbiór obiektów zawiera n elementów (O={O1, ..., On}), a zbiór atrybutów jest m-elementowy (A={A1, ..., Am}) to system informacyjny będzie miał postać taką jak zaprezentowano w tabeli 1 oraz dla i=1, ..., n oraz j=1, ..., m będzie zachodziła równość:

f(Oi, Aj) = vij

Przykładowo: f(O1, A2) = v12

O\A

A1

...

Am

O1

v11

v1m

.

.

.

.

.

.

On

vn1

vnm

Tabela 1 Ogólna postać systemu informacyjnego.

W tabeli 2 zaprezentowano przykład prostego systemu informacyjnego zawierającego 10 obiektów i 5 atrybutów o dwuelementowym zbiorze wartości {0, 1}.

O\A

A1

A2

A3

A4

A5

O1

0

1

0

1

1

O2

0

1

0

1

1

O3

1

0

1

1

1

O4

1

1

1

0

1

O5

1

1

1

0

1

O6

1

1

1

0

1

O7

0

0

0

1

0

O8

0

0

0

1

0

O9

0

1

0

1

0

O10

0

1

0

1

0

Tabela 2 Przykład systemu informacyjnego.

Dla podzbioru P zbioru atrybutów A definiuje się relację P-nierozróżnialności (R(P)). Dwa obiekty są w relacji jeżeli mają te same wartości wszystkich atrybutów ze zbioru P, tzn.

Oi R(P) Oj f(Oi, a) = f(Oj, a) a P

Przykładowo, dla podzbioru atrybutów P={A1, A2, A3} z tabeli 2 między innymi obiekty O1 oraz O2 są w relacji R(P).

Relacja R(P) jest relacją równoważności, zatem dzieli zbiór obiektów na rozłączne klasy równoważności (R(P)*) takie, że obiekty należące do tej samej klasy są ze sobą w relacji R(P), czyli R(P)*={kP1, ..., kPN}, gdzie N - liczba klas równoważności. Klasę elementu x ze względu na relację R(P) będziemy oznaczać przez [x]R(P).

Dla systemu informacyjnego z tabeli 2 oraz zbioru atrybutów P={A1, A2, A3} otrzymamy 4 klasy równoważności:

R(P)*={kP1, kP2, kP3, kP4}

gdzie kP1 = {O1, O2, O9, O10}

kP2 = {O3}

kP3 = {O4, O5, O6}

kP4 = {O7, O8}

Relacja R(A), gdzie A={A1, ..., Am} dzieli natomiast zbiór obiektów na 5 klas równoważności:

kA1 = {O1, O2}, kA2 = {O3}, kA3 = {O4, O5, O6}, kA4 = {O7, O8}, kA5 = {O9, O10}

Zbiór obiektów O oraz relacja R(A) tworzy przestrzeń aproksymacji (O, R(A)), w której możemy aproksymować dowolny podzbiór zbioru obiektów konstruując dolną i górną aproksymację tego zbioru.

Dolną aproksymację zbioru X (tzw. obszar pozytywny POS(X), LOWER(X)) jest zbiór tych obiektów dla których klasy równoważności ze względu na relację R(A) zawierają się w zbiorze X. Formalnie można to zapisać następująco:

LOWER(X) = POS(X) = {x O: [x]R(A) X}

Górną aproksymacją zbioru X (UPPER(X)) stanowi zbiór tych obiektów, których klasy równoważności mają niepuste przecięcie z X, czyli

UPPER(X) = {x O: [x]R(A) X }

Ponadto definiuje się obszar negatywny zbioru X, który jest dopełnieniem górnej aproksymacji zbioru X w zbiorze O, czyli:

NEG(X) = O - UPPER(X)

oraz brzeg zbioru X:

BND(X) = UPPER(X) - LOWER(X)

Zbiór jest zbiorem przybliżonym jeżeli jego brzeg jest zbiorem niepustym, czyli dolna aproksymacja tego zbioru jest różna od górnej aproksymacji tego zbioru. Jeżeli dolna i górna aproksymacja zbioru są równe to wtedy zbiór jest dokładnie zdefiniowany.

Intuicyjnie, powyżej zdefiniowane obszary można zinterpretować następująco: obszar pozytywny zbioru X jest zbiorem tych obiektów, które na pewno należą do zbioru X, do obszaru negatywnego należą te obiekty, które na pewno nie należą do zbioru X, obszar brzegowy stanowią te obiekty, które być może należą do zbioru X. Graficzną ilustrację aproksymacji przykładowego zbioru X dla dwóch atrybutów, z których jeden może przyjmować 5 wartości, a drugi 7 zaprezentowano na rysunku się na rysunku 40.

0x08 graphic

- aproksymowany zbiór

- dolna aproksymacja (obszar pozytywny)

- brzeg zbioru

- obszar negatywny

Rys. 40 Ilustracja graficzna aproksymacji zbioru X.

Dla zbioru obiektów X = {O2, O3} z tablicy 2 dolną aproksymacją jest kA2 = {O3} (LOWER(X)={O3}), natomiast górną aproksymację stanowi kA1∪kA2={O1, O2}∪{O3}={O1, O2, O3} (UPPER(X)={O1, O2, O3}). Ponieważ dolna aproksymacja tego zbioru X jest równa górnej aproksymacji, zatem ten zbiór jest zbiorem przybliżonym. Zbiór Y={O1, O2} jest natomiast dokładnie zdefiniowany ponieważ jego dolna aproksymacja jest równa górnej aproksymacji (jest to klasa kA1={O1, O2}).

Podzbiór P zbioru atrybutów B⊆A jest reduktem zbioru atrybutów B jeżeli zbiór klas równoważności ze względu na relację R(P) jest identyczny ze zbiorem klas równoważności ze względu na relację R(B). Część wspólna wszystkich reduktów zbioru atrybutów B stanowi rdzeń. Intuicyjnie, rdzeń jest zbiorem tych atrybutów, które nie mogą być usunięte bez wpływu na opis obiektów.

Dla systemu informacyjnego z tabeli 2 zbiory atrybutów R={A1, A2, A3, A5} oraz S={A2, A3, A5} są reduktami zbioru atrybutów A. Rdzeniem zbioru atrybutów A jest natomiast zbiór {A2, A3, A5}.

W praktyce zachodzi konieczność podziału zbioru atrybutów na tzw. atrybuty warunkowe oraz atrybuty decyzyjne. Jeżeli jeszcze zmodyfikujemy interpretacje wartości pojawiających się w tabeli, to powstaje wtedy tzw. tablica decyzyjna. Formalną definicję tablicy decyzyjnej można znaleźć np. w (Mrózek, Płonka, 1999). Przykład tablicy decyzyjnej zamieszczono w tabeli 3, która powstała poprzez dodanie do tablicy 2 atrybutu decyzyjnego D.

O\A

A1

A2

A3

A4

A5

D

O1

0

1

0

1

1

1

O2

0

1

0

1

1

1

O3

1

0

1

1

1

2

O4

1

1

1

0

1

3

O5

1

1

1

0

1

3

O6

1

1

1

0

1

3

O7

0

0

0

1

0

4

O8

0

0

0

1

0

4

O9

0

1

0

1

0

5

O10

0

1

0

1

0

5

Tabela 3 Przykład tablicy decyzyjnej.

Każdy wiersz tabeli decyzyjnej stanowi regułę decyzyjną postaci:

IF {koniunkcja wartości atrybutów warunkowych} THEN {koniunkcja wartości atrybutów decyzyjnych}

Przykładowo pierwszy wiersz tabeli 3 można zinterpretować następująco:

Jeżeli A1=0 i A2=1 i A3=0 i A4=1 i A5=1 to D=1

Pojęcia reduktu i rdzenia można wykorzystać do analizy tablicy decyzyjnej, a w szczególności do redukcji liczby atrybutów warunkowych i decyzyjnych (Mrózek, Płonka, 1999)

    1. Analiza danych metodą zbiorów przybliżonych

Etapy analizy danych metodą zbiorów przybliżonych:

  1. wybór sposobu reprezentacji danych - określenie zbioru atrybutów i dziedziny każdego z atrybutów (dziedzina - zbiór wartości jakie może przyjmować dany atrybut),

  2. badanie zależności pomiędzy atrybutami - znalezienie rdzenia i reduktu zbioru atrybutów,

  3. aproksymacja zbiorów i rodziny zbiorów - skonstruowanie dolnej i górnej aproksymacji, obliczenie współczynników charakteryzujących jakość i dokładność aproksymacji,

  4. wykorzystanie wyników analizy - dla systemu informacyjnego redukt lub zbiór reduktów może stanowić podstawę komputerowej reprezentacji danych, dla tablicy decyzyjnej redukt lub zbiór reduktów stanowi regułową bazę wiedzy, która może zostać wykorzystana do wspomagania procesów decyzyjnych.

Electronic Bulletin of the Rough Set Community, hhtp://cs.uregina.ca/~roughset/rs.intro.txt

Relacja określona na zbiorze X jest relacją równoważności jeżeli jest zwrotna (aRa dla każdego a∈X), symetryczna (aRb=>bRa ∀a, b∈X) oraz przechodnia (aRb i bRc => aRc ∀a, b, c ∈X). Relacja równoważności dzieli zbiór X na rozłączne podzbiory (klasy) dające w sumie cały zbiór X [Kuratowski, 1975].

[Mrózek i in., 1999], s.27-28.

Definicje wspomnianych współczynników można znaleźć w [Mrózek i in., 1999].

145



Wyszukiwarka