机器学习算法推导amp实现树模型系列 [复制链接]

在过去的数篇文章中，我们围绕概率模型展开讨论，并通过Python手写实现算法。从本篇文章开始，我们将重点讨论机器学习中应用最为广泛的模块之一——树模型。今天就让我们从最经典的单一决策树ID3算法说起。

决策树介绍

我们知道，决策树模型是一种基本的分类与回归方法。寻找最优的决策树是一个NP难的问题，一般通过启发式方法，只能解决局部最优，还需要引入剪枝策略，实现全局最优。

因此决策树的重点在于特征的选择、树的生成、剪枝策略三个部分。下面我们介绍最经典的ID3算法，是如何选择特征并生成树的。

ID3特征选择

ID3算法是一种贪心算法，以信息学为基础，用来构造决策树，算法的核心是“信息熵”。在《机器学习算法推导实现——半朴素贝叶斯分类算法2》一文中，我们介绍过信息学相关知识。

信息熵描述的是对随机变量不确定性的度量，不确定性越大，信息熵值就越大：

条件熵表示在已知随机变量X的条件下随机变量Y的不确定性：

信息增益表示得只特征X的信息而使得Y的信息的不确定性减少的程度。决策树中的信息增益等价于互信息。

在ID3算法中，决策树应用信息增益准则选择特征，对同样的数据D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。

ID3树生成

我们知道了ID3是通过信息增益来选择特征的，具体生成树的时候，从根结点开始计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该结点的不同取值建立子结点；再对子结点递归调用以上方法，构建决策树；直到信息增益很小或者无特征可分为止。具体我们用以下步骤来展示下：

输入：训练数据集D，特征集A，阈值e。

输出：决策树T。

（1）如果D中所有实例属于同一类Ck，则返回结点，并将Ck作为该结点的类；

（2）如果A为空集，则返回结点，并将D中实例数最大的类Ck作为该结点的类；

（3）否则，按算法计算A中各特征的信息增益，选择信息增益最大的Ak特征；

（4）如果Ak所在结点的信息增益小于e，则返回结点，并将D中实例数最大的类Ck作为该结点的类；

（5）否则，对Ak的每一种取值可能ai，依次将结点数据集进行分割，形成子结点；

（6）对子结点递归调用第1~5步，生成树T。

今天我们就简单介绍ID3算法的内容，以后我们会继续补充介绍其他算法，以及连续值、缺失值、树剪枝等问题的处理。

Python实现

介绍ID3算法，我们要重点讲下Python实现。

首先，构建了结点类。这样每次迭代都可以递归调用，结点类包含着最优的划分特征、划分特征的值、该结点的值、该结点的深度、该结点的样本数量、子结点。

importnumpyasnpfromutilsimportcalculate_entropy,calculate_yproba#fromsklearn.treeimportDecisionTreeClassifier#树结点类classTreeNode(object):"""保存决策树的结点信息：1.划分特征2.划分特征的值3.结点的值（分类是各类别的概率，回归是具体的值）4.结点的深度5.结点样本数量6.子结点"""def__init__(self,best_feature,thres_list,node_value,node_depth,node_samples,child_node=None):self.feature_i=best_featureself.feature_thres=thres_listself.value=node_valueself.depth=node_depthself.n_samples=node_samplesself.childNode=child_node

其次，构建了基础树类。该类最重要的是构建决策树的方法，在此基础树类的基础上可以自由构建分类树和回归树。

classBaseTree(object)ef__init__(self,criterion,minloss):"""基础树的类，包括树的构造过程，树的预测过程等等。Parameters----------criterion:String树生成的准则.minlossloat树停止生长的最小误差，分类树和回归树以及不同的准则会有不同的损失计算函数.Returns-------None"""self.criterion=criterionself.minloss=minlossself.tree=Noneself._calculate_loss=None#结点Loss的计算方法self._calculate_nodevalue_method=None#结点值的计算方法self._search_feature_method=None#结点特征选择方法self._split_dataset_method=None#结点样本拆分方法def_build_tree(self,X,y,node_depth=0,column_name=None):"""树的构造方法。Parameters----------X:2D-Array该结点上的样本.y:1D-Array该结点上的标签，分类结果或者数值.node_depth:Int该结点的树深.column_nameist该结点上样本的列名称.Returns-------node:Class该结点的信息，无法再分返回None."""node_value=self._calculate_nodevalue_method(y)n_samples,n_features=X.shape#划分树的话，另child_node为None，条件如下：##1.无特征可分，##2.分类问题中信息熵很低，或者纯度很高，即loss很小的时候；##3.回归问题中loss很小的时候loss=self._calculate_loss(y)if(n_features==0)or(loss=self.minloss):node=TreeNode(None,None,node_value,node_depth,n_samples,None)returnnode#不停止划分的话，另child_node为字典：child_node={}##1.找到树的最优特征和划分方法best_feature,thres_list=self._search_feature_method(X,y,column_name)##2.遍历保存树的子结点forthresinthres_list:newx,newy,newcolumnname=self._split_dataset_method(X,y,best_feature,thres,column_name)new_depth=node_depth+1child_node[thres]=self._build_tree(newx,newy,new_depth,newcolumnname)node=TreeNode(best_feature,thres_list,node_value,node_depth,n_samples,child_node)returnnode

然后，构建分类树类。主要包括搜索最优特征的方法、拆分数据集的方法、训练的方法。

#分类树classDecisionTreeClassifier(BaseTree)ef__init__(self,criterion,minloss):"""分类树的方法类Parameters----------criterion:String分类树的准则，可选"entropy","gini"，默认"entropy".minlossloat树停止生长的最小误差，分类树和回归树以及不同的准则会有不同的损失计算函数.Returns-------None."""super(DecisionTreeClassifier,self).__init__(criterion,minloss)def__search_feature_entropy(self,X,y,column_name=None)根据特征值、标签值、根信息熵计算信息增益defcalculate_gain_entropy(xarray,yarray,root_entropy)Set=np.unique(xarray)Di=[sum(xarray==value)/len(xarray)forvalueinxSet]Child_entropy=[calculate_entropy(y[np.nonzero(xarray==value)[0]])forvalueinxSet]gain_entropy=root_entropy-np.dot(Di,Child_entropy)returngain_entropy,list(xSet)#遍历特征，找到最大信息增益的特征n_samples,n_features=X.shapebest_gain_entropy=0best_feature_index=Nonebest_thres_list=Noneentropy0=calculate_entropy(y)foridxinrange(n_features)ain_entropy,thres_list=calculate_gain_entropy(X[:,idx],y,entropy0)ifgain_entropybest_gain_entropy:best_gain_entropy=gain_entropybest_feature_index=idxbest_thres_list=thres_listreturncolumn_name[best_feature_index],best_thres_listdef__split_dataset_entropy(self,X,y,best_feature,feature_thres,column_name):best_feature_idx=column_name.index(best_feature)newx,newy,newcolumnname=np.copy(X),np.copy(y),list(np.copy(column_name))newx=np.delete(newx[np.nonzero(X[:,best_feature_idx]==feature_thres)[0],:],best_feature_idx,axis=1)newy=newy[np.nonzero(X[:,best_feature_idx]==feature_thres)[0]]newcolumnname.remove(best_feature)returnnewx,newy,newcolumnnamedeffit(self,X,y)赋值训练要用到的方法self._calculate_loss=calculate_entropyself._calculate_nodevalue_method=calculate_yprobaself._search_feature_method=self.__search_feature_entropyself._split_dataset_method=self.__split_dataset_entropy#构建树self.tree=self._build_tree(X,y,column_name=list(range(X.shape[1])))

最后，写好ID3分类决策树后，我们用以下数据集（申请贷款样本数据集）来做下测试。

if__name__=="__main__"=np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2],[0,0,1,1,0,0,0,1,0,0,0,0,1,1,0],[0,0,0,1,0,0,0,1,1,1,1,1,0,0,0],[0,1,1,0,0,0,1,1,2,2,2,1,1,2,0]]).Ty=np.array([0,0,1,1,0,0,0,1,1,1,1,1,1,1,0])#ID3分类树tree_id3_classifier=DecisionTreeClassifier(criterion="entropy",minloss=0.)tree_id3_classifier.fit(X,y)tree_id3_classifier.tree

我们会发现，通过ID3算法对该数据集进行训练，只需要分2次就足够了，训练结果如图所示。

1.第一层通过“有房子”特征，划分为“有房”和“无房”：

1.1其中“有房”的无需再分，都是贷款的人；

1.2其中“无房”的再根据“有工作”特征，划分为“有工作”和“无工作”：

1.2.1“有工作”的都是贷款的人；

1.2.2“无工作”的都是不贷款的人。

以上就是本次决策树ID3算法的全部内容，谢谢阅读。