262080479

Każdy element macierzy Cy jest zbiorem atrybutów różniących i-ty i j-ty obiekt z U, pod warunkiem, że decyzje dla obiektów Uj oraz Uj są różne. W przypadku, gdy dec(uO = dec(uj), zbiór Cjj jest zbiorem pustym.

Na podstawie macierzy rozróżnialności tworzona jest funkcja rozróżnialności. Bezpośrednio z M(TD) tworzone jest wyrażenie boolowskie w postaci iloczynu sum (CNF), gdzie sumowanie jest po elementach (atrybutach) niepustego zbioru cij. Wyrażenie to jest następnie przekształcane do wyrażenia postaci „suma iloczynów” (DNF), którego składniki (po odpowiednim uproszczeniu) reprezentują minimalne zbiory atrybutów.

Nietrudno zauważyć, że w obu przypadkach cały proces obliczeniowy reduktów sprowadzić można do obliczania tzw. minimalnego pokrycia kolumnowego binarnej macierzy porównań.

Pokryciem kolumnowym macierzy porównań (zwanej również macierzą pokryć) M = [mij\, /e {1,..., w}, je {l,...,n} jest zbiór L <z {l,...,n} taki, że dla każdego i e {1,..., w} istnieje j e L, dla którego m/j = 1. Pokrycie kolumnowe nazywamy minimalnym, jeżeli nie istnieje L’ęL, który jest pokryciem macierzy M.

Tak definiowana macierz pokryć jest analogiem macierzy blokującej stosowanej w algorytmie ekspansji [5] wykorzystywanym w procesie minimalizacji funkcji boolowskich, jak też w metodzie uogólniania reguł decyzyjnych metodą ekspansji [5]. Z tych powodów metodę redukcji atrybutów zaproponowaną w niniejszej pracy nazywać można „redukcją atrybutów metodą uogólniania reguł decyzyjnych”.

1.5. Redukcja atrybutów metodą uogólniania reguł

Redukcja atrybutów metodą uogólniania reguł decyzyjnych przebiega trzyetapowo, a mianowicie:

■    w etapie pierwszym tworzy się macierze porównań M,

■    w etapie drugim następuje wyznaczenie tablic minimalnych pokryć M,

■    w etapie trzecim wyznacza się iloczyn kartezjański zbiorów obiektów (wierszy) wszystkich tablic minimalnych pokryć M.

Ostatni etap to analiza dużego zbioru wyników iloczynu kartezjańskiego, w tym etapie odrzucamy wszystkie powtarzające się wyniki oraz mające większe pokrycie kolumnowe. Powstały w ten sposób zbiór daje nam zbiór rozwiązań.

13