## Klasyfikacja sekwencji DNA z użyciem drzewa decyzyjnego

### Treść zadania i przyjęte założenia

Celem projektu była implementacja algorytmu bazującego na C4.5, klasyfikującego sekwencje DNA i zbadanie jego działania dla różnych parametrów. Jako atrybuty przyjęliśmy kolejne nukleotydy w sekwencji DNA, zaś klasą była wartość 0 lub 1, oznaczająca czy dany przykład jest donorem (lub akceptorem - w zależności od zadania) czy też nie. W przypadku, gdy wartość jednego z atrybutów jest nieznana, sekwencja zawierająca taki atrybut jest ignorowana podczas budowania drzewa. Jeśli taka wartość pojawi się w fazie testowania, drzewo decyzyjne przypisze klasę najczęściej występującą w zbiorze danych. Decyzja o przycięciu drzewa, podejmowana jest po porównaniu dokładności drzewa pierwotnego (uzyskanego w działaniu algorytmu ID3) z drzewem przyciętym, przy czym dokładność jest badana na danych walidacyjnych, wydzielonych ze zbioru danych treningowych, które nie biorą udziału przy badaniu przyrostu informacji po podziale danych według wartości atrybutów. Jeśli większa dokładność klasyfikacji jest uzyskana po przycięciu drzewa, drzewo jest przycinane. Informacja mówiąca, na której pozycji znajduje się granica pomiędzy intronem a eksonem jest ignorowana.

### Podział prac

* Michał Szaknis - budowanie drzewa
* Kamil Przybyła - partycjonowanie zbioru danych, walidacja krzyżowa, testowanie dokładności i klasyfikacja

### Sposób realizacji

Projekt zrealizowano w języku C++20, z wykorzystaniem CMake'a do budowania projektu.

### Sposób uruchomienia

Usage ./dna <input file> <testing type> <testing param> <tree type> <prune param>
Where:
    <input file>            File with data to train.
    <testing type>          Either `split` to train tree with separate testing set
                            or `cross` to perform cross-validation.
    <testing param>         For `split` testing it's training set size in relation
                            to complete set. For `cross` it's number of partitions.
    <tree type>             Either `ID3` or `pruned`
    <prune param>           Optional param for `pruned` tree, it's the size of testing set
                            in relation to training set.
Examples:
    ./dna data/spliceDTrainKIS.dat split 0.8 pruned 0.1
    ./dna data/spliceDTrainKIS.dat split 0.8 id3
    ./dna data/spliceDTrainKIS.dat cross 3 id3
    ./dna data/spliceDTrainKIS.dat cross 3 pruned 0.2

### Opis zbiorów danych

#### Akceptory:

Zbiór danych składa się z 5788 sekwencji nukleotydów o stałej długości równej 90. Wartości atrybutów przyjmują wartości A, T, C, G oraz N w przypadku brakujących danych.

#### Donory:

Zbiór danych składa się z 5256 sekwencji nukleotydów o stałej długości równej 15. Wartości atrybutów przyjmują wartości A, T, C, G oraz N w przypadku brakujących danych.


### Statystyki

Pomiary wykonano za pośrednictwem skryptu `tools/benchmark.py` dla 25 uruchomień programu, z różnymi parametrami.

#### Wzajemne porównanie algorytmów

Wnioski:
* budowanie drzewa za pomocą naszego algorytmu jest bardziej czasochłonne, w porównaniu do ID3, gdyż ten pierwszy algorytm wymaga dodatkowego badania dokładności drzewa pierwotnego i przyciętego

#### Porównanie dokładności modelu Pruned dla różnych rozmiarów zbioru walidacyjnego

Wnioski:
* dla zbioru danych z akceptorami, najlepszą dokładność model osiąga dla zbioru walidacyjengo o rozmiarze 0.1, zaś dla zbioru z donorami dla 0.3; różnice są jednak bardzo nieznaczne

#### Porównanie algorytmów ID3 i Pruned z wydzielonym zbiorem testującym

Wnioski:
* algorytm Pruned uzyskuje większą dokładność niż ID3, co zapewne spowodowane jest zdolnością algorytmu do generalizowania na dane spoza danych treningowych, wynikającej z zastosowania obcinania
* zbiory danych miały bardzo nierówny rozkład klas, jednak mimo to, drzewo potrafiło klasyfikować sekwencje donorów z wysoką (~94%) skutecznością
* algorytm nie radził sobie równie dobrze z klasyfikacją akceptorów (dokładność była niewiele wyższa niż częstość występowania najpopularniejszej klasy), czego przyczyną może być duża liczba atrybutów (przestrzeń wszystkich możliwych danych jest znacznie większa niż danych zawartych w zbiorze, dodatkowo nierówny rozkład klas nie ułatwia zadania klasyfikacji)

#### Porównanie algorytmów ID3 i Pruned z walidacją krzyżową

Wnioski:
* zastosowanie walidacji krzyżowej nie spowodowało wzrostu dokładności modeli
* wzrostowi liczby części, na jakie dzielimy zbiór danych towarzyszy nieznaczny wzrost średniej dokładności modelu

### Czego się nauczyliśmy
* do poprawnego przycinania drzewa potrzebny jest dodatkowy zbiór, na którym drzewa nie jest trenowane
* obcięte drzewo ma lepsze do zdolności do generalizacji
* mimo bardzo niezbalansowanego zbioru danych trenujących, możliwe jest stworzenie całkiem dokładnego modelu