Podręcznik

Systemy informacyjne i systemy decyzyjne są redukowalne co najmniej na dwa sposoby, tj. te same lub nierozróżnialne obiekty mogą być reprezentowane przez tablice wielokrotnie lub – niektóre atrybuty mogą być nadmiarowe [2.19]. Omówione w poprzednim podrozdziale relacje nierozróżnialności oraz zgodności mogą zostać wykorzystane do realizacji zadania redukcji. Nie należy ich traktować jako konkurencyjne techniki, lecz wręcz przeciwnie – jak pokazano w tym rozdziale – techniki, które wzajemnie się uzupełniają.

Niech  A = (U, A È D), gdzie A Ç D = Æ, będzie systemem decyzyjnym, gdzie zbiory A, D są odpowiednio zbiorami atrybutów warunkowych oraz decyzyjnych.

Każdy system informacyjny A generuje r-podziały P(A), P(D), gdzie atrybuty a_i gene­rują poszczególne r-podziały $\Pi_{a_i}$. r-podziały reprezentują klasy zgodności COM na zbiorze U. Niech B Í A będzie podzbiorem atrybutów oraz u_p, u_q Î U. Para (u_p, u_q) Î COM(B) wtedy i tylko wtedy gdy ρ(u_p, a_i) ~ ρ(u_q, a_i) dla każdego a_i Î B. Jeśli zapiszemy klasy zgodności COM(B) jako P(B),wtedy:

$\Pi ( B) =\bigcap\limits _{i:a_{i} \epsilon B} \Pi ( a_{i})$

Używając r-podziałów generowanych zbiorem atrybutów możemy wprowadzić pojęcie zależności funkcjonalnej pomiędzy rozłącznymi podzbiorami A oraz D. Mówimy, że D jest funkcjonalnie zależny od A (symbolicznie A Þ D), wtedy i tylko wtedy gdy P(A) jest nie większy niż P(D), (tzn. P(A) £ P(D)). W terminach systemów informacyjnych znaczy to, że zbiór atrybutów D zależy od zbioru atrybutów A. Inaczej mówiąc, jeśli tylko para obiektów nie może być rozróżniona atrybutami ze zbioru A, to również nie można tych obiektów rozróżnić atrybutami ze zbioru D.

Uproszczenie systemu decyzyjnego z punktu widzenia minimalnego zbioru atrybutów zachowujących zdolności klasyfikacyjne systemu (lub zależność funkcjonalną A Þ D) należy do zadań określanych mianem redukcji wiedzy. Redukcja wiedzy w systemach decyzyjnych polega na redukcji liczby atrybutów warunkowych, czyli wyznaczaniu tak zwanych reduktów oraz usuwaniu nadmiarowych obiektów/reguł.

Tablica 2.31

Zbiór B Í A jest reduktem systemu decyzyjnego A = (U, A È D) wtedy i tylko wtedy, gdy P(B) £ P(D) oraz nie istnieje podzbiór właściwy B’ zbioru B taki, że P(B’) £ P(D). Inaczej mówiąc, reduktem systemu decyzyjnego  A = (U, A È D), w którym A Þ D, jest zbiór B Í A taki, że B Þ D oraz nie istnieje podzbiór właściwy B’ zbioru B, gdzie B’ Þ D. Atrybut a Î A nazywamy atrybutem zbędnym w systemie decyzyjnym A wtedy i tylko wtedy, gdy P(A \ {<i>a</i>}) £ P(D), w przeciwnym przypadku a jest atrybutem niezbędnym. Zbiór wszystkich atrybutów niezbędnych nazywamy rdzeniem systemu decyzyjnego lub po prostu rdzeniem.

Obliczymy niezbędność atrybutów dla tablicy decyzyjnej z tabl. 2.31. Skoro P(A \ {<i>a</i>₁}) £ P(D), a₁ jest zbędny dla zależności funkcjonalnej A Þ D. W przeci­wieństwie, a₃ jest atrybutem niezbędnym, gdyż P(A \ {<i>a</i>₃})  ≰  P(D) i wtedy po usunięciu atrybutu a₃ fakt ten manifestuje się sprzecznością wierszy w tablicy. Łatwo również wykazać, że zbiory B₁ = {<i>a</i>₁,<i>a</i>₃,a₅,<i>a</i>₆} oraz B₂ = {<i>a</i>₂,<i>a</i>₃,<i>a</i>₅,<i>a</i>₆}, są reduktami, gdyż P(a₁,a₃,a₅,a₆) £  P(D), P(a₂,a₃,a₅,a₆) £ P(D), a po usunięciu dowolnego a_i ze zbioru B₁ lub B₂, odpowiednia nierówność nie będzie spełniona. Uproszczona tablica systemu dla B₁ jest podana w tabl. 2.32.

Tablica 2.32

Pojęciami podstawowymi w algorytmie redukcji atrybutów są: macierz porównań oraz funkcja rozróżnialności. Można wtedy wykazać, że między reduktami systemu decyzyjnego  A, a implikantami funkcji rozróżnialności f_A , która w rzeczywistości jest monotoniczną funkcją boolowską, zachodzi następujący związek:

$\left\{a_{i_1},\ldots,a_{i_p}\right\}\in{\rm RED}_A$, wtedy i tylko wtedy, gdy $a_{i_1}\cdot\ldots\cdot\ a_{i_p}$ jest implikantem prostym $f_A$.

Natomiast, wyznaczenie implikantów prostych odbywa się – na przykład – za pomocą przekształcenia monotonicznej funkcji rozróżnialności w postaci iloczynu sum boolowskich do postaci sumy iloczynów. Zgodnie z podrozdziałem 2.6.2, można do tych obliczeń zastosować efektywny algorytm uzupełnienia funkcji boolowskiej.

Funkcja rozróżnialności dla systemu decyzyjnego z tabl. 2.31 jest następująca:

$f_A=a_3a_5a_6(a_1+a_2)$

Z dokonanego przeglądu systemów kla­syfikacji danych wynika, że stosowane w nich algorytmy redukcji atrybutów są mało sku­teczne. Potwierdzeniem tego przypuszczenia są eksperymenty przepro­wa­dzone ze znanym i powszechnie stosowanym do tych obliczeń systemem RSES [2.28]. Wyka­zano, że system ten nie radzi sobie z tablicami danych o dużej liczbie nieokreśloności. Wy­mownym przykładem jest często cytowana logis­tyczna baza danych trains (tabl. 2.37).

Tablica 2.37

Dla bazy trains program opracowany z zastosowa­niem metody uzupełnienia funkcji boolowskiej generuje 689 reduktów, natomiast RSES zaledwie 333 (z pominięciem opcji Don’t discern with missing values). Natomiast uruchomienie RSES dla opcji Don’t discern with missing values kończy się (po kilku godzinach obliczeń) komunikatem Not enough memory. Istotnym jest, że pominięcie opcji Don’t discern with missing values skutkuje uwzględnianiem brakujących wartości podczas tworzenia macierzy porównań. Inaczej mówiąc, w czasie wyznaczania zbioru atrybutów na których różnią się dwa wybrane obiekty, odróżniane są te o wartości NULL. W rezultacie takiego postępowania otrzymujemy wynik, który jest różny od zbioru wszystkich minimalnych zbiorów atrybutów.

Innym przykładem potwierdzającym bezwzględną przewagę metody uzupełnienia funkcji boolowskiej w me­todzie redukcji atrybutów jest funkcja KAZ (tabl. 2.38). Jest to funkcja 21 argumentów binarnych, często stosowana w testowaniu zaawansowanych narzędzi synte­zy logicznej. Otóż program RSES oblicza wszystkie 5574 redukty tej funkcji w ciągu 39 minut, natomiast opraco­wana i zaimplementowana procedura z zastosowaniem algorytmu uzupełnienia tworzy zbiór wszystkich 5574 reduktów w czasie 2.5 s.

Tablica 2.38