262080487

Wstęp

Redukcja atrybutów/argumentów jest algorytmem stosowanym w dwóch odrębnych dziedzinach wiedzy, a mianowicie w zagadnieniach związanych z klasyfikacją danych (maszynowe uczenie, eksploracja danych itp.) oraz w zagadnieniach związanych z optymalizacją i syntezą logiczną układów cyfrowych. W obu przypadkach jest to problem polegający na redukowaniu nadmiarowych specyfikacji w tablicach danych (tablicach prawdy w układach logicznych) za pośrednictwem usuwania zbędnych atrybutów (argumentów). Uzyskiwane w wyniku takiego procesu tablice mogą być wykorzystywane do generowania uogólnionych reguł decyzyjnych albo do kolejnych etapów optymalizacji logicznej (w przypadku układów cyfrowych). Oczywiście dane wejściowe algorytmów redukcji są w obu przypadkach zasadniczo różne. Dla tablic danych mamy do czynienia z wielowartościowymi atrybutami warunkowymi i wielowartościowymi atrybutami decyzyjnymi. Dla tablic prawdy wartości argumentów i wartości funkcji są binarne. Jednocześnie całkowicie inaczej są interpretowane tzw. wartości nieokreślone. W tablicy danych wartość nieokreślona atrybutu warunkowego oznacza, że wartość tego atrybutu nie została ustalona, a w przypadku tablic funkcji logicznych nieokreśloność argumentu wektora wejściowego oznacza występowanie w specyfikacji wektorów o wszystkich możliwych wartościach danego argumentu. Oczywiście w samym procesie przetwarzania atrybut warunkowy jak też wartość sygnału wejściowego mogą być interpretowane tak samo. Można bowiem założyć, że nieznana wartość atrybutu warunkowego dopuszcza specyfikację pierwotną z każdą możliwą wartością tego atrybutu. W rozeznanej literaturze nie znaleziono jednak jednoznacznego sformułowania tego problemu. Zauważono natomiast, że wiele metod odkrywania wiedzy, w szczególności metod indukcji reguł decyzyjnych, nie jest przystosowanych do uwzględniania nieokreślonych wartości atrybutów.

Z kolei jeśli chodzi atrybuty decyzyjne i wartości funkcji logicznych, to w tym przypadku rozsądnym jest przyjmowanie założenia, że decyzja jest zawsze określona. Inaczej jest dla wartości funkcji logicznych, które z natury pracy układów cyfrowych mogą zakładać wartość nieokreśloną dla różnych wektorów wejściowych układu. Różnice w interpretacji mogą również występować na poziomie wyników. Jest bowiem zrozumiałe, że dla układów logicznych najlepsze są rozwiązania z najmniejszą liczbą argumentów. Natomiast w przypadku tablic danych, w których wartość atrybutu jest niejednokrotnie uzyskiwana za pośrednictwem skomplikowanych pomiarów, większa liczba atrybutów warunkowych (ale z pominięciem tych najbardziej kłopotliwych) jest do przyjęcia. Ale dynamiczny rozwój metod syntezy logicznej otwiera również potrzebę stosowania wszystkich reduktów w procedurach optymalizacji logicznej.

Dlatego przy założeniu opracowania w miarę uniwersalnego narzędzia do badań i tablic danych i tablic prawdy, jako główny cel niniejszej pracy przyjmuje się implementację algorytmu obliczającego wszystkie redukty, przy występowaniu nieokreśloności wyłącznie po stronie dziedziny funkcji specyfikujących dane. Takie założenia są istotne również z punktu widzenia eksperymentów, których wyniki będą wykorzystywane do dalszych obliczeń, za pomocą typowych narzędzi wykorzystujących zredukowane dane (LERS, ESPRESSO).

2