# Decision Tree's

A learning algorithm that uses _information gain_ to measure how well a feature of the data distinguishes between different classes. Information gain is measured in terms of _entropy_.

Decision Tree's can be thought of as a compact representation of a function. In a binary classification scenario, this would mean that a decision tree represents a truth table. Decision tree's attempt to predict a qualitative (categorical) response by stratifying the predictor space into simpler regions. Concretely, the prediction space is divided into regions representing classes. Decision tree's can also be used in regression scenarios.

## MONK Dataset

In this notebook we'll use the [MONK Dataset](https://archive.ics.uci.edu/ml/datasets/MONK's+Problems) from UC Irvine's Machine Learning Repository. The MONK dataset is a collection of artificial data which spans two classes and distributed by some underlying function.

### True Functions

* MONK-1: $(a_1 = a_2) \wedge (a_5 = 1)$
* MONK-2: $a_i = 1 \text{ for exactly two } i \in \{1,2,\ldots,6\}$ 
* MONK-3: $(a_5 = 1 \wedge a_4 = 1) \vee (a_5 \neq 4 \wedge a_2 \neq 3)$

MONK-3 contains misclassified data (5%). In the case of noisy data, the learning algorithm may generate only partially consistent rules.

### Loading Data

Data will be accessible via a dictionary, e.g. `data['monks-1']['train']`


```python
from pathlib import Path

data_path = Path(__name__).resolve().parents[1] / 'data' / 'MONK'
m1_train = data_path / 'monks-1.train'
print("A single example from MONK-1")
with m1_train.open() as f: 
    print(f.readline())
```

    A single example from MONK-1
     1 1 1 1 1 3 1 data_5
    


Attribute information:
  1. class: 0, 1 
  2. a1:    1, 2, 3
  3. a2:    1, 2, 3
  4. a3:    1, 2
  5. a4:    1, 2, 3
  6. a5:    1, 2, 3, 4
  7. a6:    1, 2
  8. Id:    (A unique symbol for each instance)


```python
from typing import NamedTuple

data = {
    'monks-1': {
        'train': [],
        'test': [],
    },
    'monks-2': {
        'train': [],
        'test': [],
    },
    'monks-3': {
        'train': [],
        'test': [],
    },
}

class MonkDatum(NamedTuple):
    a: list
    label: int
    symbol: str
        
for key, subkeys in data.items():
    for subkey in subkeys:
        data_file = data_path / f"{key}.{subkey}"
        with data_file.open() as f:
            data[key][subkey] = [MonkDatum(a=line[1:7], label=line[0], symbol=line[7]) for line in (line.split() for line in f.readlines())]
        print(f"Loaded {key} {subkey} dataset")
```

    Loaded monks-1 train dataset
    Loaded monks-1 test dataset
    Loaded monks-2 train dataset
    Loaded monks-2 test dataset
    Loaded monks-3 train dataset
    Loaded monks-3 test dataset


## Entropy

Entropy is a measure of information. In natural language processing, entropy can be a measure of how much information there is in a grammar or how well a grammar fits a language. To compute entropy, establish a random variable $S$ over the class labels. . The entropy of any $S$ is.

\begin{equation}
\text{Entropy}(S) = - \sum_ip_i\log_2p_i
\end{equation}

$S$: A collection of samples

$p_i$: Proportion of examples of class $i$ in $S$. This is a probability function $p(x)$

In a binary classification problem, $\{0, 1\} \in S$, and the entropy of $S$ would become:

\begin{equation}
\text{Entropy}(S) = - p_0 \log_2 p_0 - p_1 \log_2 p_1
\end{equation}

The log can be measured in any base. In base 2, the units of entropy are *bits*. The intuition behind entropy is to think of it as a lower bound on the number of bits needed for an optimal length encoding scheme for some piece of information. 




```python


def entropy(S, p):
    """Compute entropy of S given probability function p"""
    pass
```

7f21bd1f474d3b42ab0bcb988b98e6a12b38a66f
ipynb
Jupyter Notebook
notebooks/Decision_Trees.ipynb
jandersson/ML-Notebooks
0962e5b44a25dd0bba1aab58c4800dd56db46bab
MIT
notebooks/Decision_Trees.ipynb
jandersson/ML-Notebooks
0962e5b44a25dd0bba1aab58c4800dd56db46bab
MIT
2020-03-24T15:28:15.000Z
2021-06-01T21:47:08.000Z
notebooks/Decision_Trees.ipynb
jandersson/ML-Notebooks
0962e5b44a25dd0bba1aab58c4800dd56db46bab
MIT
Qwen/Qwen-72B
1. YES
2. YES