<jupyter_start><jupyter_text>This notebook is inspired but not limited by *Machine Learning In Action*.e.g., the implementation of the algrithm is at a higher level.All rights deserved by Diane(<NAME>).  1. About ID3 1.1 Mechanism of ID3ID3 is a type of Decision Tree. Note that ID3 only work with nominal values. To build a ID3 tree is to select one feature, based on which the dataset in this branch is splitted into sub-branches, at a time recursively, until every item in the dataset of this branch is in the same class or there is no feature to split on. 1.1.1 Based on what, a feature is selected to split dataset at each step? One way used is **Information Gain**. Always choose the feature that gives you the highest information gain.$ information\ gain = entropy\ before\ splitting\ -\ entropy\ after\ splitting $where entropy after splitting is the sum of entropy of datasets in each sub-branch after splitting. 1.1.2 What's entropy? **Entropy** is expected value of **information**$Entropy = -\sum_{i=1}^{n} p(c_i)logp(c_i)$where $n$ is the number of the classes, $c_i$ stands for i_th class, $p(c_i)$ stands for the propobility of class i beening chosen.Actually, **information of class i** is $-logp(c_i)$. In another word, **Entropy** is expected value of **information of all classes**  1.2 Pros and Cons 1.21 Pros1. Easy for human to understand the result (e.g., If you need to get a loan from a bank and it get rejected. Isn't it more acceptable if the bank can explain based on what they mad this decision?).2. Computationally cheap.3. Can deal with irrelevant features (I don't understand where does this conclusion come from so far.). 1.22 Cons1. Prone to overfitting.  2. ID3 Tree Construction<jupyter_code># Creat demo dataset

import pandas as pd
import math
def creatData():
    data =[[1, 1, 'yes'],
           [1, 1, 'yes'],
           [1, 0, 'no'],
           [0, 1, 'no'],
           [0, 1, 'no']]

    featureName = ['no surfacing','flippers','label']
    
    return pd.DataFrame(data, columns=featureName)

data = creatData()
# tool function: calculate Entropy

import pandas as pd
def calEnt(data):
    p = data[data.columns[0]].groupby(data.label).count()/data.shape[0]
    entropy = 0
    for p_i in p:
        entropy -= p_i * log2(p_i)
    return entropy
# test
calEnt(data)
# tool function: split data by a given feature

def splitData(data, feature):
    values = set(data.iloc[:,feature])
#     return [i for i in values]
    return [data[data.iloc[:,feature]==i] for i in values]
# test
splitData(data, 1)
# tool function: finding the feature to split on

def findFeat(data):
    newEnt = []
    for i in range(len(data.columns)-1):
        newEnt.append(sum([calEnt(data) for data in splitData(data, i)]))
    return np.array(newEnt).argmin()    # the base entropy is the same, so we just neet to find the feature that give us the smallest new entropy
findFeat(data)
# building the tree
def treeBuilding(data):
    if(data.shape[1]==1):
        return str(data.label.max())
    elif(calEnt(data)==0):
        return str(data.label.max())
    else:
        thisTree = {}
        featFound = findFeat(data)
        newDatasets = splitData(data, featFound)
        featName = data.columns[featFound]
        thisTree[featName] = {}
        for i in newDatasets:
            thisTree[featName][str(i[featName].max())] = treeBuilding(i.drop(featName,axis=1))
    return thisTree
treeBuilding(data)<jupyter_output><empty_output><jupyter_text>2. Build Another Tree - Contact Lenses [download here](http://archive.ics.uci.edu/ml/machine-learning-databases/lenses/)<jupyter_code># Data Exploration
data = []
with open('./test_dataset/lenses.data') as f:
    for line in f.readlines():
        data.append(line.strip().split())
data = pd.DataFrame(data, columns=['number','age', 'prescript', 'astigmatic', 'tearRate','label'])
data.set_index(keys="number",inplace=True)
data.head()
treeBuilding(data)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11613228982580157, 'fraction_numerical': 0.012623074981065387, 'mean_word_length': 3.8140947752126366, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '478711', 'license': 'MIT', 'n_tokens_mistral': 1236, 'n_tokens_neox': 1204, 'n_words': 463, 'path': 'ID3.ipynb', 'repo_name': 'DianeSoHungry/ShallowMachineLearningCodeItOut', 'size': '3965'}