Podręcznik

Naturalną strategią indukcji reguł jest strategia dwustopniowej selekcji reguł. W strategii tej dla każdego obiektu u_i klasy K tworzy się zbiór wszystkich minimalnych reguł pozytywnych (ozn. R(u_i )). Suma zbiorów R(u_i ) dla wszystkich obiektów klasy K tworzy rodzinę minimalnych reguł tej klasy. Rodzina ta jest następnie poddawana procesowi selekcji, którego  celem jest wyznaczenie minimalnej rodziny minimalnych reguł. Zarówno w procesie uogólniania pojedynczego obiektu, jak też w procesie selekcji korzysta się z pojęcia pokrycia kolumnowego binarnej macierzy M, omawianym już w rozdz. 1.2.

Obliczanie pokrycia kolumnowego jest standardowym zadaniem polegającym na transformacji wyrażenia boolowskiego typu CNF (Conjunctive Normal Form) na wyrażenie DNF (Disjunctive Normal Form). W wyrażeniu CNF czynniki koniunkcji są dysjunkcjami zmiennych boolowskich etykietujących te kolumny M dla których w danym wierszu m_ij=1. Liczba czynników jest równa liczbie wierszy macierzy M. Istotnym problemem jest transformacja CNF na DNF, gdyż składniki wyrażenia DNF są koniunkcjami zmiennych reprezentujących kolumny macierzy M.

Zastosowanie pokrycia kolumnowego do uogólnienia reguły decyzyjnej obiektu u_i dotyczy tzw. macierzy rozróżnialności.

Macierz rozróżnialności tworzymy przez porównanie obiektu u_i z każdym obiektem u_j należącym do innej klasy decyzyjnej. Porównanie polega na utworzeniu binarnego wektora w, w którym na pozycja k jest wartość zero, jeśli wartość atrybut A_k(u_i) obiektu u_i jest taka sama jak wartość atrybutu A_k(u_j) obiektu u_j lub co najmniej jedna z tych wartości jest nieokreślona. W przeciwnym przypadku wartość składowej k  wektora w jest równa jeden. Zbiór wektorów w tworzy macierz rozróżnialności.

Z definicji macierzy rozróżnialności wynika, że aby uogólniona reguła obiektu u_i nie pokrywała zdanego obiektu innej klasy decyzyjnej, to w odpowiedniej R(u_i) należy  zostawić atrybuty, które odróżniają R(u_i) od każdego obiektu innej klasy decyzyjnej.

Istotę zjawiska możemy zaobserwować na hipotetycznym przykładzie reprezentującym wyniki sondażu przed wyborami prezydenckimi w pewnej republice.

Podstawowe znaczenie w metodzie ma procedura obliczająca pokrycie kolumnowe macierzy M. Ze względu na złożoność obliczeniową, zadanie generowania reguł nie jest zwykle możliwe do rozwiązania w czasie wielomianowym. W szczególności zbiór pokryć macierzy M  może zawierać zbyt wiele elementów, aby program mógł znaleźć rozwiązanie w rozsądnym czasie. W związku z tym zaproponowano zastosowanie algorytmu uzupełnienia funkcji boolowskiej.

Możliwość zastosowania  uzupełnienia funkcji boolowskiej do obliczenia wszystkich minimalnych pokryć kolumnowych macierzy binarnej M omówiona była w rozdz. 2.6.2. Na tej podstawie stwierdzamy: zamiast stosować transformację CNF na DNF wystar­czy obliczyć uzupełnienie funkcji boolowskiej reprezentowa­nej macierzą M. Metoda jest dokładnie przedstawiona w rozdz. 2.6.2, dlatego ograniczymy jej omówienie jedynie do obliczenia uzupełnienia macierzy M. Funkcja boolowska macierzy M oraz jej uzupełnienie podane są w tablicy 2.40.

Tablica 2.40

Procedura uzupełniania – jak wykazano w [2.17],[2.18] – jest bardzo szybka, zatem jej zastosowanie do indukcji reguł jest wskazane. Dysponując szybkim algorytmem indukcji reguł dla pojedynczych obiektów możemy pokusić się o indukcję dla wszystkich reguł danej klasy decyzyjnej i wybrać z nich reguły najogólniejsze, przeznaczone do następnego etapu selekcji. Przy takiej organizacji trzeba będzie jednak wprowadzić heurystyczne algorytmy selekcji.

Tablica pokryć umożliwia wybór (selekcję) takiego minimalnego zbioru reguł, który pokrywa wszystkie obiekty ustalonej klasy decyzyjnej. Minimalny zbiór reguł klasy decyzyjnej d = 1 można wyznaczyć obliczając minimalne pokrycie kolumnowe tablicy pokryć. W tym celu zapisujemy wiersze tablicy w postaci zbiorów kolumn wskazywanych przez pozycje jedynek w danym wierszu. Metoda selekcji pokryć zastosowana w proponowanym algorytmie indukcji oblicza wszystkie minimalne pokrycia kolumnowe metodą uzupełnienia funkcji boolowskiej, której specyfikacja (również jej uzupełnienia) jest podana w tabl. 2.42.

Tablica 2.42

Z zapisu uzupełnienia wynika, że wszystkie minimalne pokrycia kolumnowe są: R₂, R₄ oraz R₁, R₂, R₅. Oczywiście taki sam wyniki uzyskamy dokonując transformacji wyrażenia typu CNF na DNF:

r₂(r₁ + r₄) (r₂ + r₃ + r₅) (r₄ + r₅) = r₂r₄ + r₁ r₂r₅

Z powyższych rozważań wynika, że zadanie uogólnienia reguł decyzyjnych ustalonej klasy D_k jest analogiczne do zadania minimalizacji funkcji boolowskiej f= (F, R), w której wektory zbioru F odpowiadają obiektom klasy D_k, a zbiór R jest macierzą rozróżniającą. Złożoność obliczeniową tego problemu można oszacować złożonością obliczeniową zadania minimalizacji funkcji boolowskiej. Obliczeniem decydującym o eksplozji kombinatorycznej tego problemu jest zatem obliczenie wszystkich pokryć kolumnowych Tablicy Pokryć. O złożoności tego problemu decyduje szybko rosnąca (ze wzrostem liczby atrybutów) liczność rodziny minimalnych reguł klasy D_k.

Otóż w przypadku systemu decyzyjnego z tablicy 2.39 liczba wszystkich minimalnych  reguł jest 5:  tym samym odpowiednia tablica pokryć (tabl. 2.41) ma 5 kolumn. W rezultacie obliczenie minimalnych pokryć kolumnowych tej tablicy można wykonać „ręcznie” – jest widoczne „gołym okiem”. Zjawisko występującej w tym problemie eksplozji kombinatorycznej dobrze wyjaśnia przykład tablicy decyzyjnej podanej w tablicy 2.43.  W tym przypadku liczba wszystkich minimalnych reguł jest 68. Zatem odpowiednia tablica pokryć ma aż 68 kolumn, co znacznie utrudnia obliczenie uzupełnienia.

Tablica 2.43

Z powyższych rozważań wynika, że obliczenie uogólnionych reguł decyzyjnych dla rzeczywistych baz danych muszą być – przynajmniej dla tablicy pokrycia – realizowane algorytmami heurystycznymi. Natomiast rewelacyjna procedura uzupełniania (Complement) może być zastosowana wyłącznie do obliczania minimalnych pokryć kolumnowych macierzy rozróżnialności.

Należy pamiętać, że algorytm uzupełnienia funkcji boolowskiej (complement) jest algorytmem systematycznym. Uzyskuje najlepsze wyniki pokrycia, a co ważne dla generacji reguł, tworzy wszystkie rozwiązania problemu. Zalet tego algorytmu niestety nie da się zawsze wykorzystać, szczególnie dla bardziej złożonych problemów. Algorytm uzupełniania jest szczególnie wrażliwy na ilość kolumn w tablicy rozróżnialności. Praktyka pokazuje, że tablice rozróżnialności podczas uogólniania reguł zawierają zazwyczaj więcej obiektów (wierszy), niż kolumn (atrybutów), dlatego dla małych i średnich baz w rozumieniu ilości atrybutów (od 1 do 30 atrybutów) z powodzeniem używamy uzupełnienia. Niestety odwrotną strukturę posiadają tablice rozróżnialności reguł. Ilość kolumn jest zawsze niemniejsza niż ilość wierszy. Wynika to z faktu, że z każdego obiektu (wiersza) indukowana jest minimalnie jedna reguła.

Ograniczenia w stosowaniu algorytmu uzupełniania funkcji boolowskich spowodowały potrzebę użycia szybkich, heurystycznych algorytmów minimalizacji tablic boolowskich. Możliwe do zastosowania są dwa algorytmy iteracyjne: MaxCol i MinRow, omawiane poprzednio w rozdz. 2.4.2.

Algorytmy Complement, MaxCol, MinRow stanowią strategię indukcji reguł decyzyjnych, którą nazywać będziemy strategią dwustopniowej selekcji.

Regułowy system decyzyjny

Procedura dwustopniowej selekcji reguł składa się z następujących etapów.

1. Wyznaczenie macierzy rozróżnialności dla obiektu u_i ustalonej klasy decyzyjnej
2. Obliczenie wszystkich uogólnionych reguł obiektu u_i

Macierz rozróżnialności jest wykorzystywana do obliczenia wszystkich uogólnionych reguł obiektu u_i. Obliczenie zbiory wszystkich minimalnych reguł sprowadzić można do problemu obliczenia pokryć kolumnowych macierzy rozróżnialności.

Załóżmy, że kolumny macierzy rozróżnialności są indeksowane kolejnymi atrybutami warunkowymi tablicy decyzyjnej. Wtedy każde minimalne pokrycie kolumnowe tej macierzy jest zbiorem atrybutów warunkowych uogólnionej i minimalnej reguły decyzyjnej obiektu u_i. W celu utworzenia tej reguły atrybutom zbioru reprezentującego pokrycie kolumnowe przyporządkowuje się odpowiednie wartości obiektu u_i, czyli jeśli minimalny zbiór atrybutów jest {<i>a_i, a_j,…,a_k</i>} oraz obiekt u_i ma wartości atrybutów odpowiednio {<i>w_i, w_j,…,w_k</i>} to ugólnioną regułą jest:

( a_{i =} w_i ) & ( a_{j =} w_j ) & ( a_{k =} w_k ) = d_k

3. Obliczenie rodziny minimalnych ugólnionych reguł klasy decyzyjnej D_k

Powtarzając obliczenia z punków 1 i 2 dla każdego obiektu u_i ustalonej klasy decyzyjnej D_k uzyskuje się rodzinę minimalnych uogólnionych reguł klasy D_k:

R(D_k) = (r1,..., r_max)

Reguły wchodzące w skład tej rodziny stanowią zbiór najlepszych reguł reprezentujących wszystkie obiekty klasy D_k.

4. Wyznaczenie tablicy pokryć klasy D_k

Chcąc uzyskać minimalny zbiór reguł (niekoniecznie o najmniejszej liczności) reprezentujących klasę D_k  należy utworzyć tablicę pokryć (TP). Tablicą pokryć jest binarna tablica o liczbie kolumn n (n jest licznością rodziny R(D_k)) i liczbie wierszy równej k ( k – liczba obiektów klasy klasy D_k). Element TP(i,j) tej tablicy przyjmuje wartość 1, gdy reguła r_j  pokrywa obiekt u_i, w przeciwnym przypadku 0.

5. Obliczenie minimalnego zbioru uogólnionych reguł klasy D_k.

Minimalny zbiór uogólnionych reguł reprezentujących (pokrywających) klasę D_k można wyznaczyć obliczając minimalne pokrycie kolumnowe TP.

            Ze względu na złożoność obliczeniową, zadanie generowania reguł nie jest zwykle możliwe do rozwiązania w czasie wielomianowym. W szczególności zbiór pokryć macierzy M_p może zawierać zbyt wiele elementów, aby program mógł znaleźć rozwiązanie w rozsądnym czasie.