<jupyter_start><jupyter_text>Python Implementation of Decision Tree Classifier  <NAME> Suppose you have a population. You want to divide this population into relevant subgroups based on specific features characterizing each subgroup, so that you can accurately predict outcomes associated with each subgroup. For instance, you could :* Use the list of the people on the Titanic, and by dividing them into subgroups depending on specific criteria (e.g. female vs male, passengers in 1st class vs 2nd and 3rd class, age class....) determines if they were (probably) going to survive or not.* Look at the people who bought product on your e-commerce website, divide this population into segments depending on specific features (e.g. returning visitors vs new visitors, localization, ...) and determines for future visitors if they are (probably) going to buy your product or not.In sum, you want to create a model that predicts the value of a target variable (e.g. survive/die; buy/not buy) based on simple decision rules inferred from the data features (e.g. female vs male, age, etc.). For instance, the picture below shows the probability of passengers of the Titanic to survive depending on their sex, age and number of spouses or siblings aboard. Note how each branching is based on answering a question (the decision rule) and how the graph looks like an inverted tree.![decision tree](https://upload.wikimedia.org/wikipedia/commons/f/f3/CART_tree_titanic_survivors.png)  0. The battle planThis tutorial is based on chapter 7 of Programming Collective Intelligence. The original code (for Python 2) is available on GitHub here. The code you found here is adapted to Python 3 and include comments I've added. This tutorial is self-contained and you don't need the book to understand it (though I would highly recommend you to buy it). I also only assume a basic understanding of Python and you have here all the necessary code to reproduce the results.For more explanations on decision trees I recommend looking at chapter 3 of Data Science for Business or watch this excellent video by Prof. <NAME>.Suppose we have a list of visitors. Our target attribute is if they bought a subscription to our service (possible values are None, Basic or Premium). To predict their behavior in a transparent way, we will use decision trees.We collected data on 16 visitors. The data is represented like this : Referer  | Country | Read FAQ |  of webpages visited |	Subscription (TARGET Attribute)-------- | ------- | -------- | --------------------- | -------------------------------Slashdot |	USA	   |    yes	  |         18	          |     NoneGoogle	 | France  |    yes	  |         23	          |    Premium  ...	 |   ...   |    ...	  |        ...            |     ...<jupyter_code>my_data=[['slashdot','USA','yes',18,'None'],
        ['google','France','yes',23,'Premium'],
        ['digg','USA','yes',24,'Basic'],
        ['kiwitobes','France','yes',23,'Basic'],
        ['google','UK','no',21,'Premium'],
        ['(direct)','New Zealand','no',12,'None'],
        ['(direct)','UK','no',21,'Basic'],
        ['google','USA','no',24,'Premium'],
        ['slashdot','France','yes',19,'None'],
        ['digg','USA','no',18,'None'],
        ['google','UK','no',18,'None'],
        ['kiwitobes','UK','no',19,'None'],
        ['digg','New Zealand','yes',12,'Basic'],
        ['slashdot','UK','no',21,'None'],
        ['google','UK','yes',18,'Basic'],
        ['kiwitobes','France','yes',19,'Basic']]<jupyter_output><empty_output><jupyter_text>In a nutshell : using our current data, we want to build a predictive model that will take the form of a tree, as shown below. This decision tree will help us classify future observations. For instance, according to this tree, if a new observation/visitor has Google as Referrer (1st decision node called 0:google), has read more than 21 pages (2nd decision node, on the right called 3:21), it will probably buy a Premium subscription - as already 3 previous observations have done (leaf Premium:3).NB : The answer to each question is "False" on the left branch, and "True" on the right branch. The first number refers to the number of the column (starting with column 0 = Referer as Python start to count with zero) that is concerned with the question.Note that not all features were used to classify observations (e.g. country is not used) and some features are used multiples times (e.g. referer). Indeed, we will see that our algorithm will pick up the best decision rules to split groups.![example tree](http://www.patricklamle.com/Tutorials/Decision%20tree%20python/fixed_treeview.jpg)  1. Dividing the set We now write a function to divide a set in 2 children sets. We will then try several divisions while keeping in mind that our goal is to have homogeneous groups with regard to the target attribute (e.g. a group of customer buying None, another buying Basic, etc.).<jupyter_code># Divides a set on a specific column. Can handle numeric or nominal values
def divideset(rows,column,value):
   # Make a function that tells us if a row is in the first group (true) or the second group (false)
   split_function=None
   if isinstance(value,int) or isinstance(value,float): # check if the value is a number i.e int or float
      split_function=lambda row:row[column]>=value
   else:
      split_function=lambda row:row[column]==value
   
   # Divide the rows into two sets and return them
   set1=[row for row in rows if split_function(row)]
   set2=[row for row in rows if not split_function(row)]
   return (set1,set2)<jupyter_output><empty_output><jupyter_text>* divideset() divides the set rows into 2 children sets, based on the criteria of the column number and the value that it takes. E.g. divideset(my_data,2,'yes') divides the set into 2 subsets based on the content of their column number 2 (i.e. the 3rd column as Python starts with 0) Read FAQ, depending if their value is yes or no.* If it the data is numeric, the True criterion is that the value in this column is greater than the given value. If the data is not numeric, split_function simply determines whether the column’s value is the same as value.* The data is divided into two sets, one where split_function returns True (set1) and one where it returns False (set2).<jupyter_code>divideset(my_data,2,'yes')<jupyter_output><empty_output><jupyter_text>* The function returns the inital dataset divided into 2 groups, depending of their attribute Read the FAQ (yes or no). Note that there are 2 lists, one for each child set.* We observe that the group of people having read the FAQ does not distinguish itself much from the group who has not with regard to the target attribute. In both subgroups we have a mix of None, Basic and Premium.<jupyter_code>divideset(my_data,3,20)<jupyter_output><empty_output><jupyter_text>* Here the division is  of page visited >20 and <20.* The division seems slightly better, but it's still difficult to draw conclusions. Which attribute should we chose? And based on what values (why 20 and not 21?)?* It would be nice to have an objective criterion to split a group. For that we introduce the concept of entropy.  2. Introducing Entropy If you look at our decision tree, you will notice that in each of the leaf nodes, there is only one category of subscription. This is quite logical, as otherwise we would not be able to make good predictions !Thus, our goal is to maximize the homogeneity/purity of each childset for each split with regard to the target attribute. That would enable us to classify well future observations.<jupyter_code># Create counts of possible results (the last column of each row is the result)
def uniquecounts(rows):
   results={}
   for row in rows:
      # The result is the last column
      r=row[len(row)-1]
      if r not in results: results[r]=0
      results[r]+=1
   return results<jupyter_output><empty_output><jupyter_text>For a given set, uniquecounts() gives the count of units depending on their values in target attribute.<jupyter_code>print(uniquecounts(my_data))<jupyter_output>{'None': 7, 'Premium': 3, 'Basic': 6}<jupyter_text>We observe that the 1st set is less homogeneous than the 2nd set. Still, we need a metrics to measure it. For that we use entropy.Entropy is basically the contrary of purity/homogenity within a set, with regard to the target attribute. As the graph below shows, the more mixed up the sets are, the higher their entropy. If there are 2 classes, entropy is maximum when a set contains 50% of each class and is null if the set is pure. Our goal is to reduce the entropy of the children sets when we split a set in comparison to the entropy in the parent set.![entropy](http://www.patricklamle.com/Tutorials/Decision%20tree%20python/entropy.jpg)<jupyter_code># Entropy is the sum of p(x)log(p(x)) across all 
# the different possible results
def entropy(rows):
   from math import log
   log2=lambda x:log(x)/log(2)  
   results=uniquecounts(rows)
   # Now calculate the entropy
   ent=0.0
   for r in results.keys():
      p=float(results[r])/len(rows)
      ent=ent-p*log2(p)
   return ent
set1,set2=divideset(my_data,3,20)
entropy(set1), entropy(set2)<jupyter_output><empty_output><jupyter_text>3. Building the tree recursively To see how good an attribute is, the algorithm first calculates the entropy of the whole group.Then it tries dividing up the group by the possible values of each attribute and calculates the entropy of the two new groups. To determine which attribute is the best to divide on, the information gain is calculated. Information gain is the difference between the current entropy and the weighted-average entropy of the two new groups. Intuitively, IG basically represents the extent to which you reduced entropy / obtained more homogeneous groups with your split in comparison with the group you had before the split. Comparing the IG for various splits based on different decision rules enable us to chose the "best" split.The algorithm calculates the information gain for every attribute and chooses the one with the highest information gain.We do it again and again<jupyter_code>class decisionnode:
  def __init__(self,col=-1,value=None,results=None,tb=None,fb=None):
    self.col=col
    self.value=value
    self.results=results
    self.tb=tb
    self.fb=fb<jupyter_output><empty_output><jupyter_text>* col is the column index of the criteria to be tested (e.g. Country is col 1)* value is the value that the column must match to get a true result. (e.g. if Country=value='France' then True)* tb and fb are decisionnodes, which are the next nodes in the tree if the result is true or false, respectively (e.g. go to node tb or fb).* results stores a dictionary of results for this branch. This is None for decision nodes and only contains the target attribute and the number of units for endpoints. (e.g. Basic:3) Look at the recursive part of buildtree() and printtree() below to better understand this class.<jupyter_code>def buildtree(rows,scoref=entropy): #rows is the set, either whole dataset or part of it in the recursive call, 
                                    #scoref is the method to measure heterogeneity. By default it's entropy.
  if len(rows)==0: return decisionnode() #len(rows) is the number of units in a set
  current_score=scoref(rows)

  # Set up some variables to track the best criteria
  best_gain=0.0
  best_criteria=None
  best_sets=None
  
  column_count=len(rows[0])-1   #count the # of attributes/columns. 
                                #It's -1 because the last one is the target attribute and it does not count.
  for col in range(0,column_count):
    # Generate the list of all possible different values in the considered column
    global column_values        #Added for debugging
    column_values={}            
    for row in rows:
       column_values[row[col]]=1   
    # Now try dividing the rows up for each value in this column
    for value in column_values.keys(): #the 'values' here are the keys of the dictionnary
      (set1,set2)=divideset(rows,col,value) #define set1 and set2 as the 2 children set of a division
      
      # Information gain
      p=float(len(set1))/len(rows) #p is the size of a child set relative to its parent
      gain=current_score-p*scoref(set1)-(1-p)*scoref(set2) #cf. formula information gain
      if gain>best_gain and len(set1)>0 and len(set2)>0: #set must not be empty
        best_gain=gain
        best_criteria=(col,value)
        best_sets=(set1,set2)
        
  # Create the sub branches   
  if best_gain>0:
    trueBranch=buildtree(best_sets[0])
    falseBranch=buildtree(best_sets[1])
    return decisionnode(col=best_criteria[0],value=best_criteria[1],
                        tb=trueBranch,fb=falseBranch)
  else:
    return decisionnode(results=uniquecounts(rows))<jupyter_output><empty_output><jupyter_text>Let's just look at the non recursive part :* rows refer to the considered set. For instance the whole dataset my_data, or later subgroups.* for col in range(0,column_count) : we loop through each column of attribute, except the target attribute    ** for row in rows : row is a row of the table ['slashdot', 'USA', 'yes', 18, 'None']. So the for loop iterates through each row. In other words, row=my_data[0], then row=my_data[1].    ** column_values[row[col]]=1 : It's basically used to create an entry in the dictionnary. The values do not matters, only the keys. Basically , we are in one column and iterate through all rows i.e we loop through all the attributes cells of a column , and we give to each cell content the value 1. This value does not matter. E.g. slashdot=1, Google=1.... When the entry already exists, it simply replace it with same value. Thus we will have several times slashdot=1. All this procedure is only to create a dictionnay with keys that are all possible values of attribute within a colum    ** At the end of an iteration of the for loop on col, we have a dictionnary of the form {1st possible value in that column:1, 2nd possible value in tha column, etc.}. E.g, {slashdot: 1, Google: 1, (direct): 1, etc} for the 1st column/attribute    ** for value in column_values.keys(): it iterates through each keys and use it to split (e.g. Google/Non-Google).    ** The formula to compute information gain is :        $$ IG(parent, children) = entropy_{parent} - (entropy_{child1} * prop_{child1} + entropy_{child2} * prop_{child2}) $$  To sum up: the algorithm looks at one column. It list all possible values in that column. It then attempt to split and compare the information gain to the best split until now. Then it go to the next column and do the same. At the end we keep the best split, i.e. the one who gave us the highest IG i.e. who reduced the most entropy i.e. who formed two homogeneous groups. The algorithm is then recursively applied to build the different branches.<jupyter_code>tree=buildtree(my_data)<jupyter_output><empty_output><jupyter_text>4. Classifying new observations Now that we have built our tree, we can feed new observations and classify them. The following code basically do what we could do manually by using the tree and answering the questions.<jupyter_code>def classify(observation,tree):
  if tree.results!=None:
    return tree.results
  else:
    v=observation[tree.col]
    branch=None
    if isinstance(v,int) or isinstance(v,float):
      if v>=tree.value: branch=tree.tb
      else: branch=tree.fb
    else:
      if v==tree.value: branch=tree.tb
      else: branch=tree.fb
    return classify(observation,branch)
classify(['(direct)','USA','yes',5],tree)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08412891651182162, 'fraction_numerical': 0.011084769654642147, 'mean_word_length': 3.996158770806658, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 53, 'https://': 1, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '603385', 'license': 'MIT', 'n_tokens_mistral': 4335, 'n_tokens_neox': 4136, 'n_words': 2061, 'path': 'Miscellaneous/ipynb/decision_tree.ipynb', 'repo_name': 'zhwa/notes', 'size': '15618'}