Podręcznik

Najprostszym algorytmem heurystycznym indukcji reguł jest sekwencyjne pokrywanie (sequential covering). W algorytmie tym tworzona jest reguła pokrywająca część obiektów bazowego zbioru treningowego danej klasy decyzyjnej, a obiekty spełniające tę regułę są usuwane. Proces jest powtarzany dla pozostałych obiektów, aż do pokrycia wszystkich obiektów tej klasy. Taką samą procedurę stosuje się dla wszystkich pozostałych klas decyzyjnych.

Tablica 2.44

Dla systemu decyzyjnego A podanego w tabl. 2.44, w którym a, b, c, d są atrybutami warunkowymi, natomiast e jest atrybutem decyzyjnym, obliczymy reguły decyzyjne dla klasy e = 1.

Najpierw obliczymy macierz M₁ generowaną obiektem u₁ (pierwszy wiersz tablicy). Porównując u₁ z każdym obiektem z klasy nie należącym do klasy decyzyjnej e = 1, otrzymujemy następującą macierz porównań M₁:

$\mathbf{M}_{1} =\begin{matrix} \begin{array}{ c c c c } a & b & c & d \end{array}\\ \begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 \end{bmatrix} \end{matrix}$

Łatwo wykazać, że minimalne pokrycia kolumnowe dla M₁, to: {<i>a</i>, <i>b</i>} oraz {<i>b</i>, <i>d</i>}, tzn.

            (a + d)(b)(b + d)(a + b + d)(a + b + c + d) = ab + bd

Pokrycia te można obliczyć wykorzystując również algorytm uzupełnienia funkcji boolowskiej przedstawiony w podrozdziale 2.5. Wyznaczone w ten sposób minimalne reguły wynoszą odpowiednio:

            (a,1) & (b,0) ® (e,1)

            (b,0) & (d,1) ® (e,1)

Podobnie dla obiektu u₂ mamy:

$\mathbf{M}_{2} =\begin{matrix} \begin{array}{ c c c c } a & b & c & d \end{array}\\ \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 \end{bmatrix} \end{matrix}$

czyli minimalne reguły to:

            (a,1) & (b,0) ® (e,1)

            (a,1) & (d,0) ® (e,1)

Łatwo zauważyć, że reguła (a,1) & (b,0) ® (e,1), podobnie jak w metodzie ekspansji funkcji boolowskiej, pokrywa wszystkie reguły pierwotne systemu decyzyjnego A i klasy e = 1.

Postępując analogicznie dla pozostałych klas decyzyjnych, tzn. e = 0 oraz dla e = 2, otrzymujemy następujące reguły uogólnione (jedno z możliwych rozwiązań):

            (a,1) & (b,0) ® (e,1)

            (a,0) ® (e,0)

            (b,1) & (d,1) ® (e,0)

            (d,2) ® (e,2)

lub w innym zapisie:

            (a,1) & (b,0) ® (e,1)

            (a,0) Ú (b,1) & (d,1) ® (e,0)

            (d,2) ® (e,2)

Tablicowy zapis powyższych reguł podano w tablicy 2.45. Można również zauważyć, że w wyniku indukcji reguł uległ redukcji argument c, co oznacza, że jest on atrybutem zbędnym.

Tablica 2.45