Podręcznik

7.1. Wprowadzenie

W praktyce, metody syntezy logicznej są wykorzystywane głównie do optymalizacji systemów cyfrowych, które przetwarzają sygnały binarne. Podstawowym zadaniem tych metod jest poprawa implementacji oraz odwzorowania systemów w różnej technologii. Jednakże można wykazać, że wiele metod syntezy logicznej, a w szczególności te wykorzystywane do optymalizacji kombinacyjnych układów logicznych, może być z powodzeniem zastosowanych w typowych zadaniach przetwarzania i wyszukiwania informacji, eksploracji danych, a także w dziedzinie systemów ekspertowych, maszynowego uczenia, czy sztucznej inteligencji [2.21], [2.22].

Przez eksplorację danych, znaną również pod nazwą odkrywania wiedzy w bazach danych, jest rozumiany proces automatycznego pozyskiwania znaczących, ale dotychczas nieznanych informacji z baz danych. Dlatego te informacje określa się jako „ukryte”, a celem jest te informacje wyekstrahować. W wyniku eksploracji danych można na pewnym poziomie abstrakcji: zdiagnozować pacjenta, przeprowadzić sondaż, np. przed wyborami prezydenckimi, klasyfikować dane internetowe, czy podjąć decyzję o przyznaniu bądź odrzuceniu kredytu.

W większości zastosowań głównym zadaniem eksploracji danych jest indukcja reguł decyzyjnych, które są obliczane na podstawie wyników badań i pomiarów zgromadzonych w bazie danych. Wygenerowane reguły (zwane również klasyfikatorami) umożliwiają podjęcie decyzji. Typowym przykładem bazy danych oraz jej analizy jest Wisconsin Breast Cancer Database (źródło: Dr William H. Wolberg, University of Wisconsin Hospital, Madison, Wisconsin, USA), w której diagnoza raka piersi jest realizowana za pomocą bazy danych o dziewięciu atrybutach, zgromadzonej dla 699 pacjentek [2.29].

Systemy decyzyjne i kombinacyjne układy logiczne są bardzo podobne. System decyzyjny jest zwykle opisany przez tablicę decyzyjną, natomiast kombinacyjny układ logiczny przez tablicę prawdy. Atrybuty warunkowe systemu decyzyjnego odpowiadają zmiennym wejściowym układu logicznego, a atrybuty decyzyjne – zmiennym wyjściowym. Stąd wiele pojęć z tych obydwu obszarów może być wzajemnie na siebie odwzorowanych, a podobieństwo systemów decyzyjnych oraz układów logicznych pozwala na wykorzystanie specjalistycznych metod syntezy logicznej w dziedzinie eksploracji danych.

Na przykład zadanie redukcji danych w systemach informacyjnych jest rozwiązywane przez minimalizację liczby cech (atrybutów/parametrów), a następnie usunięcie nadmiarowych obiektów. Podobnym zadaniem w dziedzinie syntezy logicznej jest redukcja argumentów.

Innym zagadnieniem eksploracji danych jest podejmowanie decyzji na podstawie wcześniej zgromadzonych danych. Polega ono na uogólnianiu wiedzy oraz indukowaniu reguł decyzyjnych. W wyniku indukcji otrzymuje się zbiór reguł logicznych, który pozwala podejmować decyzje nie tylko dla obiektów należących do bazy pierwotnej, dla której przeprowadzono obliczenia, ale przede wszystkim dla nowych obiektów do niej nie należących. Jest to bardzo ważne w przypadku zadań maszynowego uczenia. Analogicznym zagadnieniem do indukcji reguł z dziedziny eksploracji danych jest zagadnienie minimalizacji funkcji logicznych z dziedziny syntezy logicznej. Z uwagi na inne interpretacje i aplikacje te zagadnienia wydają się być zupełnie różne, aczkolwiek jest to stwierdzenie błędne.

Celem rozdziału jest wskazanie i omówienie możliwości zastosowania zaawansowanych algorytmów syntezy logicznej w typowych zadaniach eksploracji danych, takich jak: ekstrakcja cech, indukcja reguł decyzyjnych i wielu innych.