<jupyter_start><jupyter_text>Decision TreesDecision trees are a supervised learning algorithm used for both classification and regression tasks. For this assignment we are going to take a look at classification. We can use decision trees for issues where we have numerical but also categorical input and target features. The decision tree algorithm you will be making will be based off the *ID3* algorithm as described in chapter 3 of the book "Machine Learning" by <NAME>, sections **3.1-3.4**.After building our own *ID3* tree, we will then use scikit-learn to explore numerical univariate decision trees and some possibilities for improving them. Besides working with data containing both categorical and numeric features, this assignment will give us a chance to study the following topics:* Dealing with a more realistic data set. The Iris dataset is useful to get started, as it just works out of the box, but real world datasets will almost always be a lot messier. Having to do some preprocessing to end up with a usable representation is extremely common.* Working with dataframes. `pandas` is a very popular Python library for Data Science that enables you to perform database-like operations on large datasets with great performance. It is a very useful tool to add to your arsenal.* Analysing the results of an algorithm. The results you get when you have (correctly) implemented the algorithm might surprise you. Trying to set up hypotheses about why this is the case and what you could do to improve / prevent / fix this, is a key skill in applying machine learning on real problems.  PandasBefore we start with the actual assignment, we will introduce `pandas` through a set of small exercises. For this we will use the book by the creator of `pandas`: "Python for Data Analysis". You won't have to read the whole book, but it will serve as a useful reference while you figure out how certain operations are done in `pandas`. We will always refer to the relevant pages, which are included in the *syllabus*.Below each of the exercises is a set of assertions that test whether you gave the correct answer.  Series [1 pt]Start by reading Python for Data Analysis pages 111-115 on Series.Create a `Series`-object named `earnings` containing the following *figures* and using the *sources* as its index.<jupyter_code># Ignore deprecation warnings
import warnings
warnings.filterwarnings("ignore")
import pandas as pd

earnings_sources = ["sales", "ads", "subscriptions", "donations"]
earnings_figures = [39041, 8702, 13200, 292]

### YOUR SOLUTION HERE
earnings = pd.Series(earnings_figures, index = earnings_sources)
earnings
assert type(earnings) is pd.Series, "Income has to be a Series"
assert list(earnings.index) == ["sales", "ads", "subscriptions", "donations"]
assert list(earnings) == [39041, 8702, 13200, 292]<jupyter_output><empty_output><jupyter_text>Create a `Series`-object named `expenses` using the same format as `earning` with the expenses *figures*. Then create another `Series`-object named `profit` with the profit figures for each category (earnings minus expenses). Lastly, create a variable `total_profit` containing the summed total of `profit`.<jupyter_code>expenses_sources = ["ads", "sales", "donations", "subscriptions"]
expenses_figures = [4713, 24282, 0, 3302]

### YOUR SOLUTION HERE
expenses = pd.Series(expenses_figures, expenses_sources)
profit = earnings - expenses
total_profit = profit.sum()
assert type(expenses) is pd.Series
assert type(profit) is pd.Series
float(total_profit)
assert list(profit) == [3989, 292, 14759, 9898]
assert total_profit == 28938<jupyter_output><empty_output><jupyter_text>DataFrames [1 pt]Next read Python for Data Analysis pages 115-120 on DataFrames.Create a `DataFrame` named `skittles` with the *columns* `amount` and `rating`, using the different colors as the *index*.|&nbsp;      | amount | rating ||------------|--------|--------|| **red**    | 7      | 3      || **green**  | 4      | 4      || **blue**   | 6      | 2      || **purple** | 5      | 4      || **pink**   | 6      | 3.5    |<jupyter_code>from pandas import DataFrame
### YOUR SOLUTION HERE
skittles = pd.DataFrame({'amount':[7,4,6,5,6], 'rating':[3,4,2,4,3.5]},index = ['red','green','blue','purple','pink'])
assert type(skittles) is DataFrame
assert list(skittles.index) == ["red", "green", "blue", "purple", "pink"]
assert list(skittles.columns) == ["amount", "rating"]
assert skittles.loc["red", "amount"] == 7
assert skittles.loc["blue", "rating"] == 2

solution = pd.read_msgpack(b'\x84\xa3typ\xadblock_manager\xa5klass\xa9DataFrame\xa4axes\x92\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x92\xa6amount\xa6rating\xa8compress\xc0\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x95\xa3red\xa5green\xa4blue\xa6purple\xa4pink\xa8compress\xc0\xa6blocks\x92\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x01\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xd7\x00\x01\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xc7(\x00\x00\x00\x00\x00\x00\x00\x08@\x00\x00\x00\x00\x00\x00\x10@\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x10@\x00\x00\x00\x00\x00\x00\x0c@\xa5shape\x92\x01\x05\xa5dtype\xa7float64\xa5klass\xaaFloatBlock\xa8compress\xc0\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x01\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xd7\x00\x00\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xc7(\x00\x07\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00\xa5shape\x92\x01\x05\xa5dtype\xa5int64\xa5klass\xa8IntBlock\xa8compress\xc0')
pd.testing.assert_frame_equal(skittles, solution)<jupyter_output><empty_output><jupyter_text>Calculate the average _rating_ of all the skittles and store it in a variable called `skittles_average`.<jupyter_code>### YOUR SOLUTION HERE
skittles_average = skittles['rating'].mean()
float(skittles_average)
assert skittles_average == 3.3<jupyter_output><empty_output><jupyter_text>Add a new column to the skittles `DataFrame` called `score`. The score of a color is equal to `amount * rating`.<jupyter_code>### YOUR SOLUTION HERE
skittles['score'] = skittles['amount']*skittles['rating']
assert "score" in skittles
solution = pd.read_msgpack(b'\x87\xa3typ\xa6series\xa5klass\xa6Series\xa4name\xa5score\xa5index\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x95\xa3red\xa5green\xa4blue\xa6purple\xa4pink\xa8compress\xc0\xa5dtype\xa7float64\xa4data\xc7(\x00\x00\x00\x00\x00\x00\x005@\x00\x00\x00\x00\x00\x000@\x00\x00\x00\x00\x00\x00(@\x00\x00\x00\x00\x00\x004@\x00\x00\x00\x00\x00\x005@\xa8compress\xc0')
pd.testing.assert_series_equal(skittles["score"], solution)<jupyter_output><empty_output><jupyter_text>(Re)Indexing [1 pt]Read Python for Data Analysis pages 122-128, Reindexing, Dropping entries, and "Indexing, selection, and filtering".Reindex the given `DataFrame` on columns 'a', 'c', and 'e', using indices 10, 20, 50, 60 and store the result in the same `frame` variable.<jupyter_code>import numpy as np

frame = DataFrame(np.arange(6 * 7.).reshape((6, 7)), index=[10, 20, 30, 40, 50, 60], columns=list('abcdefg'))

### YOUR SOLUTION HERE
frame = frame.reindex(['a','c','e'], axis=1).loc[[10,20,50,60]]
frame
assert type(frame) == DataFrame
solution = pd.read_msgpack(b'\x84\xa3typ\xadblock_manager\xa5klass\xa9DataFrame\xa4axes\x92\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x93\xa1a\xa1c\xa1e\xa8compress\xc0\x86\xa3typ\xa5index\xa5klass\xaaInt64Index\xa4name\xc0\xa5dtype\xa5int64\xa4data\xc7 \x00\n\x00\x00\x00\x00\x00\x00\x00\x14\x00\x00\x00\x00\x00\x00\x002\x00\x00\x00\x00\x00\x00\x00<\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6blocks\x91\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x03\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xc7\x18\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xc7`\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x1c@\x00\x00\x00\x00\x00\x00<@\x00\x00\x00\x00\x00\x80A@\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00"@\x00\x00\x00\x00\x00\x00>@\x00\x00\x00\x00\x00\x80B@\x00\x00\x00\x00\x00\x00\x10@\x00\x00\x00\x00\x00\x00&@\x00\x00\x00\x00\x00\x00@@\x00\x00\x00\x00\x00\x80C@\xa5shape\x92\x03\x04\xa5dtype\xa7float64\xa5klass\xaaFloatBlock\xa8compress\xc0')
pd.testing.assert_frame_equal(frame, solution)<jupyter_output><empty_output><jupyter_text>Replace all values in the data frame that are *divisible by 3* with the value *0*, and once again store the result in the `frame` variable.<jupyter_code>frame = DataFrame(np.arange(6 * 7.).reshape((6, 7)), index=[10, 20, 30, 40, 50, 60], columns=list('abcdefg'))

### YOUR SOLUTION HERE
frame[frame % 3 == 0] = 0
frame
assert type(frame) == DataFrame

solution = pd.read_msgpack(b'\x84\xa3typ\xadblock_manager\xa5klass\xa9DataFrame\xa4axes\x92\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x97\xa1a\xa1b\xa1c\xa1d\xa1e\xa1f\xa1g\xa8compress\xc0\x86\xa3typ\xa5index\xa5klass\xaaInt64Index\xa4name\xc0\xa5dtype\xa5int64\xa4data\xc70\x00\n\x00\x00\x00\x00\x00\x00\x00\x14\x00\x00\x00\x00\x00\x00\x00\x1e\x00\x00\x00\x00\x00\x00\x00(\x00\x00\x00\x00\x00\x00\x002\x00\x00\x00\x00\x00\x00\x00<\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6blocks\x91\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x07\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xc78\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xc8\x01P\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x1c@\x00\x00\x00\x00\x00\x00,@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00<@\x00\x00\x00\x00\x00\x80A@\x00\x00\x00\x00\x00\x00\xf0?\x00\x00\x00\x00\x00\x00 @\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x006@\x00\x00\x00\x00\x00\x00=@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000@\x00\x00\x00\x00\x00\x007@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80B@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00$@\x00\x00\x00\x00\x00\x001@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00?@\x00\x00\x00\x00\x00\x00C@\x00\x00\x00\x00\x00\x00\x10@\x00\x00\x00\x00\x00\x00&@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x009@\x00\x00\x00\x00\x00\x00@@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x14@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x003@\x00\x00\x00\x00\x00\x00:@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00D@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00*@\x00\x00\x00\x00\x00\x004@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00A@\x00\x00\x00\x00\x00\x80D@\xa5shape\x92\x07\x06\xa5dtype\xa7float64\xa5klass\xaaFloatBlock\xa8compress\xc0')
pd.testing.assert_frame_equal(frame, solution)<jupyter_output><empty_output><jupyter_text>This completes this `pandas` introduction. Now lets move on to the actual decision tree assignment.  Predicting heart disease The data set we will be using for this assignment contains heart disease diagnosis results from 4 different hospitals. The data set can be found [here](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/). Download the dataset, and place the files in the same folder as this notebook.Lets start by looking at the [heart-disease.names](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/heart-disease.names) file, which contains a description of the data set. The file also gives an explanation for the values of the different variables, so when our tree is complete we can interpret the decision rules created by the algorithm. Some variables included here, like *9 cp: chest pain type*, with 4 labels for different types of chest pain, are clearly categorical. Then there are variables like *12 chol: serum cholestoral in mg/dl*, containing the concentration of cholesterol, an obvious numeric value. The ability to handle both of these types of data is something not many other machine learning algorithms can do effectively, so in theory a decision tree should be perfect for this data. Taking a first look [2 pts]Start by downloading the 4 `processed.X.data` files and loading them into a *Pandas DataFrame* with the function `pd.read_csv`. Do not forget to manually set the names of the columns! You can find these names listed in the [heart-disease.names](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/heart-disease.names) file. Create a list `data` that contains these four dataframes and print the dataset. You should see a couple of unexpected values pop up, which probably indicate a missing value. The file describing the data sets states that missing values are indicated by $-9.0$, but this doesn't seem to be the case.<jupyter_code>### YOUR SOLUTION HERE
file_names = ['va', 'hungarian', 'switzerland', 'cleveland']
column_names = ['age', 'sex', 'cp', 'trestbps', 'chol', 'fbs', 'restecg', 'thalach', 'exang', 'oldpeak', 'slope', 'ca', 'thal', 'num']
va = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.va.data', names=column_names, header=None)
hungarian = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.hungarian.data', names=column_names, header=None)
switzerland = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.switzerland.data', names=column_names, header=None)
cleveland = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.cleveland.data', names=column_names, header=None)
data = [va, hungarian, switzerland, cleveland]
data<jupyter_output><empty_output><jupyter_text>Lets inspect the scope of this problem by writing the `count_missing` function, which should count the number of missing elements for each feature / column of a data set. The function should thus return a *Series* of missing counts, one count for each column in the data set. We have provided you with the code to print some statistics.<jupyter_code>def count_missing(df):
    ### YOUR SOLUTION HERE
    return df[df=='?'].count()
for i in range(len(data)):
    print(f'Filename: {file_names[i]}')
    print(f'Rows: {len(data[i])}')
    
    # The following code makes sure that we print horizontally and not vertically
    print(f'Missing per column: \n{count_missing(data[i]).to_frame().T}')
    print()<jupyter_output>Filename: va
Rows: 200
Missing per column: 
   age  sex  cp  trestbps  chol  fbs  restecg  thalach  exang  oldpeak  slope  \
0    0    0   0        56     7    7        0       53     53       56    102   

    ca  thal  num  
0  198   166    0  

Filename: hungarian
Rows: 294
Missing per column: 
   age  sex  cp  trestbps  chol  fbs  restecg  thalach  exang  oldpeak  slope  \
0    0    0   0         1    23    8        1        1      1        0    190   

    ca  thal  num  
0  291   266    0  

Filename: switzerland
Rows: 123
Missing per column: 
   age  sex  cp  trestbps  chol  fbs  restecg  thalach  exang  oldpeak  slope  \
0    0    0   0         2     0   75        1        1      1        6     17   

    ca  thal  num  
0  118    52    0  

Filename: cleveland
Rows: 303
Missing per column: 
   age  sex  cp  trestbps  chol  fbs  restecg  thalach  exang  oldpeak  slope  \
0    0    0   0         0     0    0        0        0      0        0      0   

   ca  thal  num  
0   4  [...]<jupyter_text>Cleaning the data [1 pt]Looking at the results from the previous step, it seems like the sets from some hospitals are more complete than others. There are different approaches you might take to solve this, like replacing the missing values with the average value for that variable, or handling missing values within the algorithm in a seperate way. For now we will take the simplest approach, discarding any rows that contain missing values. This way we only use the complete patient records from each data set. We have concatenated all four DataFrames into a single DataFrame called `df`. Drop any rows containing a missing value. You can use pandas `pd.to_numeric` with keyword `errors='coerce'` to easily convert entries to floats. When trying to convert the missing values, the DataFrame will transform these into `NaN` (Not a Number) instead of a float. After you remove the rows with `NaN`, you should end up with about 300 patient records, most of which are from the Cleveland hospital. Each patient has 14 variables, one of which (the 14th variable) is the target variable.<jupyter_code>df = pd.concat(data, ignore_index=True)

### YOUR SOLUTION HERE
df = df.apply(pd.to_numeric, errors='coerce')
df = df.dropna()
assert len(df) == 299
assert len(df.columns) == 14

target = df.columns[-1]<jupyter_output><empty_output><jupyter_text>Lets take a look at how how often each label in the target variable actually occurs.<jupyter_code>from collections import Counter

Counter(df[target])<jupyter_output><empty_output><jupyter_text>We can see that the number of each of the labels of our target variable differs greatly. While there are 160 labels with the value $0$, we only have 13 labels with value $4$. In virtually all classification tasks, training data that contains different numbers of representatives from each class might result in a classifier that is biased towards the most common class. When applied to a test set that is similarly imbalanced, this classifier yields an optimistic accuracy estimate. In an extreme case, the classifier might assign every single test case to the majority class, thereby trivially achieving an accuracy equal to the proportion of test cases belonging to the majority class!In the description file ([heart-disease.names](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/heart-disease.names)) it says *Value 0:  50% diameter narrowing*, but it does not explain all the other values. It might be logical to assume that these are different degrees of narrowing, where $0$ would mean no disease and higher values would mean different levels of disease present. Because the distribution of the different values is so skewed however, for now we will just focus on classifying the difference between a value of $0$  and any of the higher values.Change the target column to contain a boolean value that is `True` if there is more than $50\%$ narrowing and `False` otherwise. Then print the counts.<jupyter_code>### YOUR SOLUTION HERE
df['num'] = df['num'].apply(lambda x: False if x == 0 else True)<jupyter_output><empty_output><jupyter_text>Categorical Decision TreesIf you have not yet read sections **3.1-3.4** of "Machine Learning" by <NAME>, do so now. The entire chapter 3 on Decision Trees is included in the syllabus.The main idea of decision trees is to find the feature that contains the most "information" and then split/group the dataset along the rows of this feature that have the same value. This process of finding the "most informative" feature and then splitting is repeated until we arrive at a stopping criterium.We will implement this process over several steps:- Generate splits from a given dataset- Calculate the Shannon entropy; a measure of the amount of information in a given dataset- Calculate the Information Gain for a given split- Combine these metrics into an algorithm that creates the Decision Tree Splits [3 pts]Before we can determine which of our features produce the most descriptive split, we must create each split. **A split is a grouping of rows in a dataset by each of the unique values in _one_ of the columns.**First, we need to determine what unique values are present in a column. Implement a function named `unique_values` that takes a dataframe `df` and a column name `m` and returns a list of the unique values in the given column. Test the function by entering a couple of the column names and see if the outcome is as expected.<jupyter_code>def unique_values(df, m):
    ### YOUR SOLUTION HERE
    return df[m].unique()
print(unique_values(df, 'age'))<jupyter_output>[56. 47. 63. 67. 37. 41. 62. 57. 53. 44. 52. 48. 54. 49. 64. 58. 60. 50.
 66. 43. 40. 69. 59. 42. 55. 61. 65. 71. 51. 46. 45. 39. 68. 34. 35. 29.
 70. 77. 38. 74. 76.]<jupyter_text>Now implement a function named `create_split` that takes a dataframe `df` and a column name `m` and returns a dictionary. This dictionary has the *unique column values* as its keys, and the split dataframes as its values. Remember that you just wrote a function for getting the unique keys! Each of the dataframes consist of only data rows that match with the same unique value. Simply put, the data frame rows are "grouped" by each of the different unique values from that column.*Note:* When adding each of the frames in the dictionary, remove the column that was used to create the split. We have already split it into its different unique values, so the information in that column is now redundant and further splits on this column would not be possible.You should end up with a dictionary that has a set of rows for each unique value in the given column. Test the function by entering a column name, and see if the outcome is as expected.<jupyter_code>def create_split(df, m):
    ### YOUR SOLUTION HERE
    keys = unique_values(df, m)
    return {k:df[df[m] == k].drop(columns = m) for k in keys}
solution = pd.read_msgpack(b'\x84\xa3typ\xadblock_manager\xa5klass\xa9DataFrame\xa4axes\x92\x86\xa3typ\xa5index\xa5klass\xa5Index\xa4name\xc0\xa5dtype\xa6object\xa4data\x9d\xa3sex\xa2cp\xa8trestbps\xa4chol\xa3fbs\xa7restecg\xa7thalach\xa5exang\xa7oldpeak\xa5slope\xa2ca\xa4thal\xa3num\xa8compress\xc0\x86\xa3typ\xa5index\xa5klass\xaaInt64Index\xa4name\xc0\xa5dtype\xa5int64\xa4data\xd8\x00\xce\x02\x00\x00\x00\x00\x00\x00J\x03\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6blocks\x92\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x0c\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xc7`\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00\x07\x00\x00\x00\x00\x00\x00\x00\x08\x00\x00\x00\x00\x00\x00\x00\t\x00\x00\x00\x00\x00\x00\x00\n\x00\x00\x00\x00\x00\x00\x00\x0b\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xc7\xc0\x00\x00\x00\x00\x00\x00\x00\xf0?\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xf0?\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x80]@\x00\x00\x00\x00\x00\x80]@\x00\x00\x00\x00\x00\xc0f@\x00\x00\x00\x00\x00@j@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xc0e@\x00\x00\x00\x00\x00\x00h@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00ffffff\xe6?\x00\x00\x00\x00\x00\x00\xf0?\x00\x00\x00\x00\x00\x00\xf0?\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x08@\x00\x00\x00\x00\x00\x00\x08@\xa5shape\x92\x0c\x02\xa5dtype\xa7float64\xa5klass\xaaFloatBlock\xa8compress\xc0\x86\xa4locs\x86\xa3typ\xa7ndarray\xa5shape\x91\x01\xa4ndim\x01\xa5dtype\xa5int64\xa4data\xd7\x00\x0c\x00\x00\x00\x00\x00\x00\x00\xa8compress\xc0\xa6values\xd5\x00\x00\x00\xa5shape\x92\x01\x02\xa5dtype\xa4bool\xa5klass\xa9BoolBlock\xa8compress\xc0')
pd.testing.assert_frame_equal(create_split(df, 'age')[34], solution)<jupyter_output><empty_output><jupyter_text>Entropy [3 pts]There quite a few different definitions of what entropy is; all of them relate to the notion of chaos / order in a system, but the exact definition strongly depends on the context in which the term is used. Most commonly the term refers to thermodynamic entropy, where it is the describes the number possible configurations a thermodynamic system can have in a specific state. This is related to the idea of a universal entropy, as used in Asimov's classic short story [The Last Question](http://multivax.com/last_question.html). For decision trees we need the information theoretic entropy, or Shannon entropy, which says something about the amount of information contained in a distribution of data. The more ordered or one-sided the distribution is, the less bits we would need on average to express the exact distribution.We will use this measure of entropy to compare the results of decision tree splits to see which is the "most informative". For the heart disease problem there are now only 2 class labels we are considering, `True` if *vascular narrowing >= 50% diameter* and `False` otherwise. For a 2 class problem, the entropy is defined as:(3.1) $$\phi(p) = −p\ log_2(p) − (1 − p)\ log_2(1 − p)$$where $p$ is the ratio between between the labels for class 1 and class 2. First, write a `ratio` function to compute $p$. The function should, given a list of boolean values as class labels, return the ratio of `True` labels in the list, e.g. $1.0$ would indicate the list only contained `True`.<jupyter_code>def ratio(labels):
    ### YOUR SOLUTION HERE
    return sum(labels)/len(labels)<jupyter_output><empty_output><jupyter_text>Now lets assume that $p=0$; meaning there are no labels that equal `True`. The computation of $-0\ log_2(0)$ would then (correctly) result in a math error, however this could also just be defined as having the value $0$ (as it is multiplied by $0$). Write the function `entropy_sub` to compute the value of the log product ($-p\ log_2(p)$), making sure to return $0$ in the case that $p = 0$. Combine `ratio` and `entropy_sub` to compute the `entropy` of a list of boolean class labels (equation 3.1).<jupyter_code>import math

def entropy_sub(p):
    ### YOUR SOLUTION HERE
    if p == 0:
        return 0
    else:
        return -p*math.log(p,2)
def entropy(labels):
    ### YOUR SOLUTION HERE
    p = ratio(labels)
    return entropy_sub(p) + entropy_sub(1-p)<jupyter_output><empty_output><jupyter_text>Write a `plot_entropy` function to check whether the entropy function works correctly. This function should create many different lists of boolean labels of length N and compute ratio and entropy for each of these lists. Note that for a list of booleans of length 𝑁, there are only 𝑁+1 different possible ratios of labels you need to create. The x-axis of your plot should show the ratios and the y-axis their resulting entropies, which should produce a graph like Figure 3.2 in Mitchell. Show this plot at the end of your code and make sure it looks correct.<jupyter_code>import matplotlib.pyplot as plt

def plot_entropy(N):
    ### YOUR SOLUTION HERE
    ratios = [ratio([True]*i+[False]*(N-i)) for i in range(N+1)]
    entropys = [entropy([True]*i+[False]*(N-i)) for i in range(N+1)]
    plt.plot(ratios, entropys)
### YOUR SOLUTION HERE
plot_entropy(50)<jupyter_output><empty_output><jupyter_text>Information gain [3 pts]There are several metrics we can use to asses how good a split is in a decision tree. For this implemenation we will use the *Information Gain*, which is defined as the entropy of the original distribution $\phi(p)$, minus the entropy of the split distribution $I_m$ resulting from the split on variable $m$.(3.4a) $$IG_m = \phi(p) - I_m$$Information Gain measures how much the entropy changes from making a specific split, i.e. the gain in predictablity of the data as a result of making a distribution based on a specific variable. When a set of target labels is split on a variable $m$, two or more new lists are created, each with their own entropy. Combining the resulting entropies from a split into $s$ new sets is a simple weighted sum:(3.4b) $$I_m = \sum_{j=1}^s \frac{N_j}{N} \phi(p_j)$$where $N_j$ is the size of the $j^{th}$ split distribution, $p_j$ is the ratio of the target labels for that same $j^{th}$ distribution and $N$ is the size of the distribution before the split. Write the function `split_entropy` to compute $I_m$ for some list of target labels and a given `N`. The `split_labels` argument is a list containing $s$ different lists, each containing the target labels for one part of the split.<jupyter_code>def split_entropy(split_labels, N):
    ### YOUR SOLUTION HERE
    Im = 0
    for j in range(len(split_labels)):
        Im += len(split_labels[j])*entropy(split_labels[j])
    return Im/N<jupyter_output><empty_output><jupyter_text>Currently, our function `create_split` returns a dictionary where the keys are the unique entries present in the column chosen and the values are dataframes that contain the rows that have those unique entries. However, the function `split_entropy` expects a list wherein each element is a list of target labels.Write the function `get_split_labels` that accepts a `split` dictionary and `target` (the name of the column that contains the labels) and returns the `split_labels`. This returned list of lists should be of the same format as before, so it can be used directly as input for the `split_entropy` function.<jupyter_code>def get_split_labels(split, target):
    ### YOUR SOLUTION HERE
    return [split[k][target].tolist() for k in split.keys()]<jupyter_output><empty_output><jupyter_text>Write the `information_gain` function using your earlier functions `entropy` and `split_entropy`. Assume `split_labels` is a list containing $s$ different lists, each containing the target labels from one of each  of the splits. Remember that one split exists of all of the grouped unique values in a column of our data, thus, the total number of target labels given to this function is $N$ and the combination of all labels is $p$. You can use `pd.concat` to "glue" the different Series-objects together to compute $p$ directly.<jupyter_code>def information_gain(split_labels):
    ### YOUR SOLUTION HERE
    labels = [label for labels in split_labels for label in labels]
    return entropy(labels) - split_entropy(split_labels, len(labels))<jupyter_output><empty_output><jupyter_text>Below, we have created two assertions that check whether your functions were implemented correctly. **Explain why these assertions work.**Here we use 'num' as target, then `split` is a dictionary where the keys are True and False and the values are dataframes that contain the rows that have the keys. `split_labels` then is a list of two lists, one only consists of True, the other only False, so the entropy of the split distribution equals to 0 and the information gain equals to the entropy of the original distribution.<jupyter_code># We create a copy, because we remove the target in create_split, while it is needed for split_labels
test_df = df.copy()
target_copy = target + '_copy'
test_df[target_copy] = test_df[target]

split = create_split(test_df, target_copy)
split_labels = get_split_labels(split, target)

assert entropy(test_df[target].tolist()) == information_gain(split_labels)
assert split_entropy(split_labels, len(test_df)) == 0.0<jupyter_output><empty_output><jupyter_text>ID3So far, we have determined the total purity of the dataset (entropy), and created the functions that enable us to determine what column of our data is the most informative (Information Gain). That leads us to the introduction of the *ID3* algorithm introduced by <NAME> in 1986. This algorithm can be used to create a categorical decision tree through a process of greedy iterations. Reread table 3.1 in Mitchell's 'Machine Learning', containing the pseudo-code for the algorithm.Our version of the *ID3* algorithm can be described as follows:1. *If the current dataset is pure (all rows have the same label), return the pure label.* Use the `unique_value` function for this.2. *If there are no more possible columns to split; return the most common label.*3. *Calculate the Information Gain of each possible split in the dataset.* First create splits for each of the columns in the dataset (except for the target column), then extract the label lists for each of these splits and use these to calculate the Information Gain of that split.4. *Pick the split with the largest Information Gain.*5. *Create a Node for this new/current branch of the tree.*6. *For each of the sub-datasets in the split, create a sub-tree (recursively call `ID3` with the sub-dataset) and use the sub-tree result as the branches of the tree created in step 5.*7. *Return the complete tree.*We have also provided you with a [namedtuple](https://docs.python.org/3/library/collections.htmlcollections.namedtuple) `Node` that can hold the name of the selected split column; `column_name`, the most common label in this node; `mode`, and a dictionary mapping to results of the split; `branches`, wherein the key is each of the 'unique values' possible, and the values are the result of the algorithm on the data available for that unique value.<jupyter_code>from collections import namedtuple

Node = namedtuple('Node', ['column_name',  'mode', 'branches'])<jupyter_output><empty_output><jupyter_text>ExampleLets take a look at an example before we start writing out the complete algorithm. Say we have the following data set and want to classify on the target column *Vegetable*:|&nbsp;         | Color  | Pits  | Vegetable ||---------------|--------|-------|-----------|| **Broccoli**  | Green  | False | True      || **Pear**      | Green  | True  | False     || **Strawberry**| Red    | False | False     || **Zucchini**  | Green  | False | True      || **Orange**    | Orange | True  | False     |We won't bother with computing the exact Information Gain here, but looking at the 2 possible columns and the distribution of the target column *Vegetable*, you might conclude that *Color* would be a good variable to split on.We can use the [*namedtuple*](https://docs.python.org/3/library/collections.htmlcollections.namedtuple) to create a `Node` in our Decision Tree and have it store all the relevant information at that level of the tree. The `column_name` to split on has already been chosen to be *Color* and the `mode` is the most common label of the target column in this node, so this would be *False*, as there are currently more fruits than vegetables in our data set. The `branches` would start out by just being the result of the `create_split` function, meaning there would be 3 new data frames, one for each *Color*. The whole `Node` would then look something like     Node(column_name='Color', mode=False, branches={                'Green': |&nbsp;         | Pits  | Vegetable ||---------------|-------|-----------|| **Broccoli**  | False | True      || **Pear**      | True  | False     || **Zucchini**  | False | True      |            'Orange':            |&nbsp;         | Pits  | Vegetable ||---------------|-------|-----------|| **Orange**    | True  | False     |            'Red':|&nbsp;         | Pits  | Vegetable ||---------------|-------|-----------|| **Strawberry**| False | False     |                        })    However, this is of course only 1 split of our data. The crucial step in the *ID3* algorithm is step **6**; recursively create the sub-trees. So we want to split each of these data sets again and if those produce new branches, we split those further *again*, etc. This is what creates the actual tree structure, the recursive splitting into nodes, each with new branches.As you hopefully remember from your first year, all recursions need base cases and that is what steps **1 and 2** are for. The *leaf nodes* are reached when we've already perfectly split the data or no more splits are possible, and in those cases we just return the predicted label. The whole purpose of the tree structure is to predict a label for the target column. So when we reach the end of some path in the Decision Tree, all we really care about is what the predicted target label would be at that leaf in the tree, and so that is the only information we will need to store there.Combining these steps, *any* branch in a `Node` should always point to another `Node` or the predicted label for that point in the tree. This means the example structure above, containing 3 data frames, would never actually be returned by the algorithm, as the recursive step to split each frame down to *leaf nodes* is still missing. The result of that would look something like    Node(column='Color', mode=False, branches={            'Green': Node(column='Pits', mode=True, branches={                                    False: True,                     True: False}),        'Orange': False,                'Red': False})Note that each terminal value (i.e. leaf node) is now either *True* or *False*, indicating the predicted label for the *Vegetable* column at that point in the tree. If we try and interpret this tree, there is only 1 case where it would predict that something is indeed a vegetable; when it is both *Green* and has *No Pits*. In all other cases this tree would predict it to be a fruit. Verify both the constructed tree and the resulting interpreted rule before moving on to implementation. Implementation [7 pts]Now that we know what the tree structure will look like, lets build the *ID3* algorithm. So far, we have already included step 5 and 7 for you. Step 5 expects the variables `column_name` and `mode` to already be defined by you, in order to create the `Node`, while the branches start out empty.Implement the other steps and see if your code produces that same tree on `test_df`, which contains the vegetable example. Note that the *white space* was added to make the example more readable, so your actual result should look like:    Node(column_name='Color', mode=False, branches={'Green': Node(column_name='Pits', mode=True, branches={False: True, True: False}), 'Orange': False, 'Red': False})For your convenience we will repeat the steps of the _ID3_ algorithm (this is the same text as you can find above):1. *If the current dataset is pure (all rows have the same label), return the pure label.* Use the `unique_value` function for this.2. *If there are no more possible columns to split; return the most common label.* HINT: You can use pandas [`mode()`](https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.mode.html).3. *Calculate the Information Gain of each possible split in the dataset.* First create splits for each of the columns in the dataset (except for the target column), then extract the label lists for each of these splits and use these to calculate the Information Gain of that split.4. *Pick the split with the largest Information Gain.*5. *Create a Node for this new/current branch of the tree.*6. *For each of the sub-datasets in the split, create a sub-tree (recursively call `ID3` with the sub-dataset) and use the sub-tree result as the branches of the tree created in step 5.*7. *Return the complete tree.*<jupyter_code>test_df = pd.DataFrame([['Green', False, True], ['Green', True, False], ['Red', False, False],
                        ['Green', False, True], ['Orange', True, False]],
                       index=['Broccoli', 'Pear', 'Strawberry', 'Zucchini', 'Orange'],
                       columns=['Color', 'Pits', 'Vegetable'])
                       
test_target = 'Vegetable'

def ID3(data, target):    
    # step 1
    ### YOUR SOLUTION HERE
    if len(unique_values(data, target)) == 1:
        return unique_values(data, target)[0]
    # step 2
    ### YOUR SOLUTION HERE
    label = data[target].value_counts().argmax()#.mode().bool()
    if data.shape[1] == 1:
        return label
    # step 3
    ### YOUR SOLUTION HERE
    splits = []
    IGs = []
    colnames = [col for col in data.columns if col != target]
    for col in colnames:
        split = create_split(data, col)
        splits.append(split)
        split_labels = get_split_labels(split, target)
        IGs.append(information_gain(split_labels))
    # step 4
    ### YOUR SOLUTION HERE
    ind = IGs.index(max(IGs))
    colname = colnames[ind]
    # step 5
    tree = Node(column_name = colname, mode = label, branches = splits[ind])    
    # step 6
    ### YOUR SOLUTION HERE
    for k in tree.branches.keys():
        tree.branches[k] = ID3(tree.branches[k], target)
    # step 7
    return tree

tree = ID3(test_df, test_target)
print(tree)<jupyter_output>Node(column_name='Color', mode=False, branches={'Green': Node(column_name='Pits', mode=True, branches={False: True, True: False}), 'Red': False, 'Orange': False})<jupyter_text>Now that we have built a tree, it is important to realise that this algorithm *does not* search the entire space of possible trees for the best possible decision tree, but instead opts for the step at each node that will make the most progress at that moment. The tree that results from these locally optimal choices might not be globally optimal (although that happens to be the case for this small toy example). Classify [2 pts]With this complete tree classifying a new data-entry is pretty easy! Implement the `classify` function, which accepts a tree (a variable containing a `Node` representing the root of the tree), and a *single row* of a DataFrame, i.e. a Series. The function should return the predicted target label for that one row of data.Continuing the example from before; we have a new element from that same data set, but we don't yet know if it would be considered a vegetable, so we want to try and use our decision tree to predict if it is, e.g.|&nbsp;         | Color  | Pits  ||---------------|--------|-------|| **Tomato**    | Red    | False |The function should move through the relevant branches down the tree based on the `column_name` at each node and the corresponding value of the row we are trying to predict. There are 3 options at each branch:1. There is another Node attached to this branch, meaning we should continue further down the tree.2. This branch leads to a *leaf node*, meaning we now have a predicted label for the row we can return.3. The value from the column in our row actually does not have corresponding branch in this node. In that case the function should return the most common label in that node.<jupyter_code>def classify(tree, row):
    ### YOUR SOLUTION HERE
    if row[tree.column_name] not in tree.branches.keys():
        return tree.mode
    elif type(tree.branches[row[tree.column_name]]) == Node:
        return classify(tree.branches[row[tree.column_name]], row)
    else:
        return tree.branches[row[tree.column_name]]

test_tomato = pd.Series(['Red', False], index=['Color', 'Pits'])
assert not classify(tree, test_tomato), "Tomato is a fruit!"

test_grape = pd.Series(['Blue', True], index=['Color', 'Pits'])
assert not classify(tree, test_grape), "Grape is a fruit!"<jupyter_output><empty_output><jupyter_text>Note that the 3rd option can occur as it is possible the categorical value that is being classified was not present in the training set at that point in the tree. This means that even though there are more branches further down the tree, none of them match the row we are trying to classify. Therefore, the best prediction we can possible give for that row, is simply the most common target label that was present in the training set at that node in the tree.It could be the case that we have never seen this categorical value in our training set before at all, as with the grape example above. However, it is also possible that a specific categorical value *did* occur in our training set, but still some nodes *do not* have a branch for that value.**Explain when this might occur and why returning the most common target label is still a valid solution.**It might occur when feature 1 is splitted first and then in a subtree a node of feature 2 is to be splitted, but the node of feature 2 may not have all categories of feature 2 because when feature 1 is splitted, some of categories of feature 2 are splitted to another subtree.  The nodes which *do not* have a branch for that a specific categorical value could not be the root node, which means there are other more important features. The current note is not as determinant as the nodes closer to the root. So although the current subtree do not have some specific categorical values which are in other subtrees, we still need to make decision according to the decision tree from top to bottom, so returning the most common target label is still a valid solution.  Validation [4 pts]With all these elements complete, we can start applying the *ID3* algorithm on the heart disease data set and see how well it can predict the *Vascular narrowing* based on the other features describing each patient.Before we see the accuracy of our Decision Tree, we need to create a validation split. Split the DataFrame into `train` and `test` using a ratio of $0.7$ with [sklearn's `train_test_split` function](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html).<jupyter_code>from sklearn.model_selection import train_test_split

### YOUR SOLUTION HERE
train, test = train_test_split(df, train_size=0.7)<jupyter_output><empty_output><jupyter_text>We will also need to split the train and test DataFrames into categorical and numerical features, using `cat_num_split`. This could be done manually by taking a good look at the description file ([heart-disease.names](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/heart-disease.names)), but it can also be done by counting the amount of unique values present in a column. As an rule of thumb, it is probably unlikely there are more than 10 different categorical values for any one column, while it is seems very likely that there are more than 10 different numerical values for a column present in the data.Use the `unique_values` function from earlier and select the variables that have no more than the `threshold` argument number of unique values as categorical variables and all others as numerical variables. The categorical variables are all whole numbers, so the resulting 2d-array should be of type `int` and the numeric variables array should of type `float`, for which you can use pandas `astype` method. Remember that both dataframes should have the target column.Apply this function to separate out the categorical and numerical features for both the training and the test set.<jupyter_code>def cat_num_split(df, target, threshold=10):
    ### YOUR SOLUTION HERE
    cat_name =  [col for col in df.columns if len(unique_values(df, col)) <= threshold and col != target]
    num_name = [col for col in df.columns if len(unique_values(df, col)) > threshold and col != target]
    df_cat, df_num = df[cat_name].astype(int), df[num_name].astype(float)
    df_cat[target], df_num[target] = df[target],  df[target]
    return df_cat, df_num
train_cat, train_num = cat_num_split(train, target)
test_cat, test_num = cat_num_split(test, target)<jupyter_output><empty_output><jupyter_text>Finally, write the function `validate` that takes a decision tree, a dataframe of testing sample, and the target column name. It should `classify` all rows in the dataframe using the decision tree and return the percentage of elements that was classified correctly. Create a decision tree fitted to the categorical training data created above. Validate the results by computing both the train and test accuracy using the categorical features of the heart disease data set.<jupyter_code>def validate(tree, df, target):
    ### YOUR SOLUTION HERE
    df_features, df_labels = df.drop([target], axis=1), df[target]
    prediction = [classify(tree, row) for index, row in df_features.iterrows()]
    accuracy = sum(prediction == df_labels)/len(prediction)
    return accuracy
### YOUR SOLUTION HERE
tree = ID3(train_cat, target)
print('Training accuracy: ' + str(validate(tree, train_cat, target)))
print('Testing accuracy: ' + str(validate(tree, test_cat, target)))<jupyter_output>Training accuracy: 0.9521531100478469
Testing accuracy: 0.7111111111111111<jupyter_text>Numerical Decision Tree [2 pts]Now that our Categorical Decision Tree is done, we will take a look at a Numerical Decision tree. Start by reading section **3.7.2** from Mitchell. As stated there, it is possible to extend the Categorical Decision Tree to also include numerical boundaries. We could then use this to even select the best Information Gain from *both* the categorical *and* the numerical splits at each node.However, for now we will focus a model that can *only* make numerical splits, as that is what the `scikit-learn` library provides straight out of the box: The [DecisionTreeClassifier](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.htmlsklearn.tree.DecisionTreeClassifier) is a class that can build a decision tree from numerical data, and so we won't have to implement this tree from scratch.The most important difference between categorical and numerical decision trees is the way the data is split. In categorical data, it is easy to split the tree into the $N$ categories that are present in the data. This is impossible to do in numerical data, as there are infinitely many categories. Categorical Decision trees therefore use binary splits or a so called split boundary; where with each split we create one branch with values smaller than the boundary, and one branch with values greater than or equal to the boundary.This boundary for a column can be determined by trying every possible split boundary available for the set of values. This is done by first sorting the samples and then trying every split half way between two neighbouring values that have different labels. This means there can be as many splits as there are samples, and as such this method is computationally very expensive. An alternative, simpler method that is often used, is trying some amount of random splits for a column and picking the best random split among them.Note that repeated binary splits on the same numerical variable be used to create many different "decision regions" for the same variable. For example, consider a label where you want a variable to be above or equal to 3.4, but below 4.8. Here you would need two splits; a first split with 3.4 as the boundary and then in the "greater equal branch" of that split, another split boundary of 4.8 on that same variable. This means that while the feature that was split on could be ignored in further splits in the case of a Categorical Decision tree, this is not the case for Numerical Decision Trees, and repeated splits on the same variable can actually greatly improve accuracy.Implement a Numerical Tree Classifier using a `sklearn.tree.DecisionTreeClassifier` and its `fit` and `predict` functions.  Train it using the numerical part of the dataset you split out earlier, and print the training and test accuracies (this can easily be done through the `metrics.accuracy_score` method from the `metrics` module). Note that the `fit` function of the classifier requires you to separate the target column from the dataframe and provide the training set as `X` and `y`; you can use `.drop(target, axis=1)` for this, as it returns a new dataframe, but without the target class column.<jupyter_code>from sklearn.tree import DecisionTreeClassifier
from sklearn import metrics

### YOUR SOLUTION HERE
X, y = train_num.drop([target], axis=1), train_num[target]
clf = DecisionTreeClassifier()
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test_num.drop([target], axis=1), test_num[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))<jupyter_output>Training accuracy: 1.0
Testing accuracy: 0.6222222222222222<jupyter_text>The scikit-learn Decision Trees implemenation is specifically intended for numerical features. This might not be immideately obvious, but if we read the documentation on [Decision Trees](https://scikit-learn.org/stable/modules/tree.htmltree-algorithms-id3-c4-5-c5-0-and-cart) and see what algorithms it uses, we find:```scikit-learn uses an optimised version of the CART algorithm; however, scikit-learn implementation does not support categorical variables for now.```Even if it does not actually support catagorical data, you can *still* make this implementation work, provided that you give each category a number. **Note: This is not recommended (discouraged even), as this suggests that there is an ordering (the numerical order) to the categorical data.** For many models, saying category 1 is before category 3, and category 2 is somewhere in between them, can really screw up your predictions.Even though this is not recommended, since our data already has integer numbers for each of the categories we could easily try and see what works. Train a Numerical Tree Classifier using `sklearn.DecisionTreeClassifier` using the categorical data, and print the training and test accuracies. Next, train using the complete training data, i.e. categorical and numerical combined and also report the training and testing accuracies.*Note: the linked page on Decision Trees contains more useful information and hints if you plan to use this model on any projects of your own, so it might be worth reading through.*<jupyter_code>### YOUR SOLUTION HERE
print('Categorical data:')
X, y = train_cat.drop([target], axis=1), train_cat[target]
clf = DecisionTreeClassifier()
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test_cat.drop([target], axis=1), test_cat[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))

print('Complete data:')
X, y = train.drop([target], axis=1), train[target]
clf = DecisionTreeClassifier()
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test.drop([target], axis=1), test[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))<jupyter_output>Categorical data:
Training accuracy: 0.9521531100478469
Testing accuracy: 0.8111111111111111
Complete data:
Training accuracy: 1.0
Testing accuracy: 0.7666666666666667<jupyter_text>Analysis questions [4 pts]Answer these questions about the results. Chapter 3.5 from Mitchell's 'Machine Learning' might contain some hints. Write your answers below each question in this cell.**Why does the training accuracy for numerical splits become 1.0 (i.e. a perfect fit), but remains lower for categorical splits?**The searching for space of hypothese by numerical splits is continuous and precise, it can correctly classifies each of the training data which it is discrete by categorical splits then it cann't fit all the data points.**Explain how it is possible that the testing accuracy using only the categorical variables is higher than the testing accuracy using the categorical and numeric variables combined. What property of the Decision Tree causes this?**It is because of overfitting. When using the categorical and numeric variables combined, the tree becauses really complicated and it also learns the noise from the data and its ability to generalize because very low.  There is a high probability of overfitting in decision tree.**While using categorical data as if it is numerical is generally not recommended, in Decision Trees it doesn't seem as problematic. In fact, we could always reproduce a discrete split using a combination of numeric splits on that same variable. Explain how many splits we would need and what the structure might look like.**We would need `n-1` splits when we have `n` catogories on a variable, then we get `n` continuous intervals.**Aside from just being possible, here the results of using the Numerical Decision Tree of scikit-learn actually seem much better on catagorical data than those of an actual Catagorical Decision Tree. Give a hypothesis on what property of the data might cause this and motivate it with a logical argument.**Maybe the catagorical data has an order, for example, the discrete number could represent degree so that it actually has a similar meaning as continuos variable.  Preventing overfitting [1 pt]As we now know, trees learn by beginning with **the full training set** and greedily adding conditions that maximize each child nodes' label purity. As the tree grows, each node adds another condition resulting in smaller subgroups. In fact, the number of leaf-nodes grows exponentially as we add more depth to the tree and in just a few splits a training set with thousands of examples can be reduced to a set of leaves with sizes around 1-20, which lack statistical validity. Since our implementation will continue separating nodes until they are either pure or no more conditions can be set to further improve purity, it is very probable that we force our tree to overfit.There are several techniques that deal with tree overfitting. It is possible to prune the tree, for example by removing leaves once the tree is complete, or by preventing it from growing as deep in the first place by setting a threshold on the minimum Information Gain. For more detail on this, read section **3.7.1** from Mitchell's 'Machine Learning'.Scikit-learn's [DecisionTreeClassifier](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.htmlsklearn.tree.DecisionTreeClassifier) has several argument options to help prevent overfitting. Probably the easiest to get started with is `min_samples_split`, which sets what the minimum number of samples in a node should be before it can be split. If a node has less samples than this number, it will not be split further and the predicted label just becomes the most common label at that node.Try several values for `min_samples_split` and give a value that definitely still overfits, that definitely causes underfitting and the value you think gives the best fit on the data. Report the training and testing accuracy for each.<jupyter_code>### YOUR SOLUTION HERE
print('Overfitting(min_samples_split=2):')
X, y = train.drop([target], axis=1), train[target]
clf = DecisionTreeClassifier(min_samples_split=2)
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test.drop([target], axis=1), test[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))

print('Underfitting(min_samples_split=100):')
X, y = train.drop([target], axis=1), train[target]
clf = DecisionTreeClassifier(min_samples_split=100)
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test.drop([target], axis=1), test[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))

print('Best fit(min_samples_split=20):')
X, y = train.drop([target], axis=1), train[target]
clf = DecisionTreeClassifier(min_samples_split=20)
clf = clf.fit(X, y)
y_pred = clf.predict(X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))
X, y = test.drop([target], axis=1), test[target]
y_pred = clf.predict(X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))<jupyter_output>Overfitting(min_samples_split=2):
Training accuracy: 1.0
Testing accuracy: 0.7666666666666667
Underfitting(min_samples_split=100):
Training accuracy: 0.784688995215311
Testing accuracy: 0.7333333333333333
Best fit(min_samples_split=20):
Training accuracy: 0.8708133971291866
Testing accuracy: 0.7555555555555555<jupyter_text>**Which minimum split size gives the best fit on the data? Explain why you choose this value.**I choose 20 as the best minimum split size since it is a suitable number for the training data which contains 209 rows. It balances the training accuracy and testing accuracy and perfroms well in both training and testing data.  Plotting the Decision Tree [1 pt]Sklearn also comes with a tool that can actually plot the whole decision tree. However, plotting the complete tree would be a bit hard to read, as it wouldn't really fit in the figure. We can again use another `DecisionTreeClassifier` argument to limit the size of the tree. Here using `max_depth` makes the most sense, as we want uniformly cut the tree at certain depth for the plot.Fit a decision tree of a limited depth and call it `d_tree`. The code below will already plot it. Make sure it the tree small enough so you can read off the values in the plot. If not, reduce the `max_depth` further.<jupyter_code>from sklearn import tree
from matplotlib.pyplot import figure

### YOUR SOLUTION HERE
X, y = train.drop([target], axis=1), train[target]
clf = tree.DecisionTreeClassifier(max_depth=3)
d_tree = clf.fit(X, y)
figure(figsize=(15, 10))
tree.plot_tree(d_tree, feature_names=df.columns.values,
               class_names=['Healthy', 'Heart Disease'], impurity=False);<jupyter_output><empty_output><jupyter_text>**Try to read out the boundaries set in the decision tree. Refer back to the [heart-disease.names](https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/heart-disease.names) if you don't know what a variable means. What parameters seem to be the best indicators for heart disease?**`thal`, `ca`(number of major vessels (0-3) colored by flourosopy),  `cp`(chest pain type) seem to be the best indicators for heart disease.**Explain why considering a very reduced version of the tree should still give some insight in the important factors of heart disease.**The node splitting process of decision tree depends on the information gain. The information gains of factors decrease from top to bottom, so those important factors will be near the root of the tree and we can know them by considering a very reduced version of the tree.  Random Forests [4 pts]A method for reducing overfitting that is not discussed in Mitchell's book is the ensemble approach. In an ensemble approach multiple models are trained on (variations of) the original dataset, and then used to give a combined prediction. A commonly used ensemble method for decision trees is Random Forest. The essence of Random Forest classification is to have many decision trees that have all been trained on a random subset of features with randomly drawn sample rows. These decision trees then all predict on unseen samples and a majority vote is used as the final prediciton. This procedure usually leads to better model performance; while the predictions of a single tree are highly sensitive to noise in the training data; the average of many trees trained on very similar data is not.We will be implementing a simple but effective variant Random Forest that creates a small sample of all training data and trains several of scikit's `DecisionTreeClassifier`s on a random subset of features. First, we will need to create the forest. Implement `create_forest` that should accept `n_trees` the number of trees that should be in the forest, and returns a list containing all of the `DecisionTreeClassifier` objects. Check the [docs](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.htmlsklearn.tree.DecisionTreeClassifier) for a way to change the maximum amount of features used in the tree to the square root of the number of features and use it when creating the classifiers. *This is an easy way to limit the number of features used in the classifier and will help to differentiate all the models learned by each of the trees.*<jupyter_code>def create_forest(n_trees):
    ### YOUR SOLUTION HERE
    return [DecisionTreeClassifier(max_features='sqrt') for i in range(n_trees)]<jupyter_output><empty_output><jupyter_text>Now implement the function `train_forest` that accepts a `forest` (a list of `DecisionTreeClassifier` objects) and trains each of the trees with `ratio` samples from `data`. *Training each of the trees on different random subsets of the data will also help to differentiate all the models learned by each of the trees.*Hint: use the pandas `sample` method to create your subsets.<jupyter_code>def train_forest(forest, data, target, ratio=0.5):
    ### YOUR SOLUTION HERE
    for i in range(len(forest)):
        df = data.sample(frac = 0.5)
        X, y = df.drop([target], axis=1), df[target]
        forest[i] = forest[i].fit(X, y)
    return forest<jupyter_output><empty_output><jupyter_text>Implement the function `predict_forest` that accepts a `forest` and predicts the target label for the passed `data`.Hint: since we only have two possible predictions, `True` and `False`, which are equal to 1 and 0 respectively, we can just add all predictions of all trees together, adding 1 or 0 for each. If we then divide the total prediction by the number of trees, we end up with an 'average vote' that can be rounded to be either 1 or 0; `True` or `False`.<jupyter_code>def predict_forest(forest, data):
    ### YOUR SOLUTION HERE
    votes = np.array([tree.predict(data).astype(int) for tree in forest])
    pred = np.mean(votes, axis=0).round()
    return pred<jupyter_output><empty_output><jupyter_text>Now, create a random forest with 1000 trees, each using only 3 or 4 random features ($\approx \sqrt{13}$) and train each forest with a 50% random sample of the complete training data. Print out the train and testing accuracy. Does this result improve over using just 1 tree?<jupyter_code>### YOUR SOLUTION HERE
forest = create_forest(1000)
forest = train_forest(forest, df, target, ratio=0.5)

X, y = train.drop([target], axis=1), train[target]
y_pred = predict_forest(forest, X)
print('Training accuracy: ' + str(metrics.accuracy_score(y, y_pred)))

X, y = test.drop([target], axis=1), test[target]
y_pred = predict_forest(forest, X)
print('Testing accuracy: ' + str(metrics.accuracy_score(y, y_pred)))<jupyter_output>Training accuracy: 1.0
Testing accuracy: 1.0
{'fraction_non_alphanumeric': 0.09332099570711284, 'fraction_numerical': 0.04825326517300487, 'mean_word_length': 4.47814525511052, 'pattern_counts': {'":': 0, '<': 141, '<?xml version=': 0, '>': 139, 'https://': 18, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 7, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '35', 'dir': 'jupyter-structured-clean-dedup', 'id': '386968', 'license': 'MIT', 'n_tokens_mistral': 22019, 'n_tokens_neox': 19948, 'n_words': 7966, 'path': 'Jiang_Assignment_4.ipynb', 'repo_name': 'snowhite2018/Leren', 'size': '65941'}