Ensembles of Classifiers Based on Decision Bireducts

W niniejszej rozprawie przedstawiamy pojęcie bireduktów decyzyjnych, które są rozszerzeniem reduktów decyzyjnych z teorii zbiorów przybliżonych, gdzie nacisk położony jest zarówno na podzbiór atrybutów opisujących decyzje jak i podzbiór obiektów, dla których ten opis jest prawidłowy. Badamy związek bireduktów decyzyjnych z przybliżonymi reduktami decyzyjnymi, które zostały opracowane na potrzeby przetwarzania dużych i zaszumionych danych. Pokazujemy, jak biredukty decyzyjne mogą być użyte jako klasyfikatory regułowe, które zapewniają większą elastyczność w przypisywaniu wartości decyzyjnych obiektom w porównaniu do metod bazujących na reduktach przybliżonych. Przedstawiamy teoretyczne wyniki dotyczące własności bireduktów decyzyjnych, jak również algorytmy służące ich efektywnemu obliczaniu. W szczególności pokazujemy, że zadanie szukania optymalnych bireduktów przy zadanych kryteriach jest zadaniem NP-trudnym.

W rozprawie omawiamy także kwestię tworzenia zespołów klasyfikatorów wykorzystujących biredukty decyzyjne. Przybliżone redukty decyzyjne wykorzystywane w zespole klasyfikatorów wspólnie mogą błędnie klasyfikować pewne obiekty. Tymczasem, dzięki elastyczności bireduktów decyzyjnych w kontekście wyboru obiektów, których wartości decyzyjne są prawidłowo opisywane przez dany zbiór atrybutów, w trakcie tworzenia zespołu klasyfikatorów możemy unikać powtarzania błędów popełnianych przez poszczególne klasyfikatory na tych samych obszarach danych treningowych.

Zespoły bireduktów decyzyjnych należy traktować jako zespoły klasyfikatorów interpretowalnych, gdzie każdy biredukt utożsamia się ze zbiorem prostych reguł decyzyjnych wyznaczanych przez dany podzbiór atrybutów. Jednym z istotnych aspektów interpretowalności w uczeniu maszynowym, który jest obecnie często wymagany w praktycznych zastosowaniach, jest także możliwość określenia istotności poszczególnych atrybutów wykorzystanych w przygotowywanych modelach. W związku z tym, w rozprawie pokazujemy jak określić istotność atrybutów wykorzystywanych przez zespoły bireduktów decyzyjnych. Ponadto, wprowadzamy nowe podejście do oceny i porównywania metod pomiaru istotności atrybutów bazujących na dowolnych metodach uczenia maszynowego.

Dla rezultatów przedstawionych w rozprawie prezentujemy intuicyjne przykłady, a praktyczną użyteczność bireduktów decyzyjnych pokazujemy w oparciu o wyniki eksperymentów przygotowanych na danych referencyjnych, jak i danych rzeczywistych związanych z praktycznymi zastosowaniami. Pokazujemy również kompleksowo studium przypadku, w którym zastosowane zostały zespoły bireduktów decyzyjnych do rozwiązania problemu decyzyjnego napotkanego podczas realizacji projektu dla firmy HR specjalizującej się w rekrutacji ekspertów IT.

In this dissertation, we present decision bireducts, an extension of decision reducts in the theory of rough sets, the emphasis of which is on both a subset of attributes which describes decisions and a subset of objects for which that description is valid. We investigate their relationship with approximate decision reducts which were developed to handle large and noisy data. Additionally, we demonstrate how decision bireducts can be used as rule-based classifiers that provide greater flexibility in assigning decision values to objects when compared to approximate decision reducts. Moreover, we present theoretical results on the properties of decision bireducts as well as algorithms for their effective computation. Furthermore, we show that obtaining optimal bireducts with respect to given criteria is an NP-hard task.

In the dissertation we also investigate an important aspect of creating ensembles of decision bireducts. Ensembles of classifiers based on different approximate decision reducts can repeatedly misclassify the same data instances. In contrast, decision bireducts provide flexibility in selecting objects whose decision values are accurately described by the given set of attributes. This flexibility enables us to verify and potentially influence the creation of the ensemble, that assures avoidance of repeating errors on the same areas of the training data.

One of the aspects of interpretability in machine learning, which is often required in practical applications, is the ability to report the importance of particular attributes used in the prepared models. Therefore we present decision bireducts ensembles ability to provide feature importance scores. Moreover, to further increase the usefulness of such results, we introduce an approach to the evaluation of attribute scores produced by any machine learning method.

The results presented in the dissertation are supported by examples, while the practical usefulness of decision bireducts is demonstrated by the results of prepared experiments on both benchmark and real-world data. We also comprehensively present a case study demonstrating the application of decision bireducts ensembles to a decision problem encountered while developing a solution for an HR company specializing in the recruitment of IT professionals.