Construction and optimization of partial decision rules

Abstract

Tematyka pracy związana jest z badaniem algorytmów zachłannych dla konstruowania i optymalizacji częściowych (przybliżonych) reguł decyzyjnych. Przedstawione w pracy badania dotyczące częściowych reguł decyzyjnych opierają się na wynikach badan uzyskanych dla problemu częściowego pokrycia zbioru. Zostało udowodnione, ze biorąc pod uwagę pewne założenia dotyczące klasy NP, algorytm zachłanny pozwala uzyskać wyniki, bliskie wynikom uzyskiwanym przez najlepsze przybliżone wielomianowe algorytmy, dla minimalizacji długości częściowych reguł decyzyjnych oraz minimalizacji całkowitej wagi atrybutów tworzących częściową regułę decyzyjną. Na podstawie danych uzyskanych podczas pracy algorytmu zachłannego, dokonano oszacowania najlepszych górnych i dolnych granic minimalnej złożoności częściowych reguł decyzyjnych. Teoretyczne i eksperymentalne wyniki badan pokazały możliwości wykorzystania tych granic w praktycznych zastosowaniach. Dokonano także oszacowania granicy dokładności algorytmu zachłannego dla generowania częściowych reguł decyzyjnych, która nie zależy od liczby wierszy w rozważanej tablicy decyzyjnej. Biorąc pod uwagę pewne założenia dotyczące liczby wierszy i kolumn w tablicach decyzyjnych udowodniono, ze dla większości binarnych tablic decyzyjnych istnieją tylko krótkie, nieredukowalne częściowe reguły decyzyjne. Wyniki przeprowadzonych eksperymentów pozwoliły potwierdzić 0.5-hipoteze: dla większości tablic decyzyjnych algorytm zachłanny w każdej iteracji, podczas generowania częściowej reguły wybiera atrybut, który pozwala oddzielić przynajmniej 50% wierszy jeszcze nie oddzielonych. W przypadku klasyfikacji okazało się, że dokładność klasyfikatorów opartych na częściowych regułach decyzyjnych jest często lepsza, niż dokładność klasyfikatorów opartych na dokładnych regułach decyzyjnych.