前言最近打算系统学习机器学习的基础算法，避免眼高手低，决定把常用的机器学习基础算法全部实现加深印象。本文是该系列博客的第一篇，关于决策树（DecisionTree）的算法实现。在这篇文章中，我将对决策树种涉及的算法进行总结，并附上自己的相关实现代码。对应模型的所有算法代码和训练数据都会放在GitHub上（https://github.com/PytLab/MLBox）。在这篇文章中，我将通过MLiA的隐形眼镜处方数据集逐步构建决策树，并使用Graphviz可视化决策树。字面上的决策树学习决策树学习是根据数据的属性，使用树结构建立的决策模型。该模型可用于解决分类和回归问题。常见的算法有CART（ClassificationAndRegressionTree）、ID3、C4.5等，我们经常会根据数据集构建决策树。他的一项重要任务是为数据中包含的知识信息提取一系列规则。这些规则，也就是创建树结构的过程，就是机器学习的过程。决策树的结构以下面这个预测是否购买电脑的简单决策树为例。树中的内部节点代表某个属性，从节点派生出来的分支代表这个属性所有可能的取值，叶子节点代表最终判断结果的类型。借助Graphviz、matplotlib标注等可视化工具，我们创建的决策树模型可以被可视化并直接被人类理解。这是贝叶斯神经网络等算法所不具备的特性。决策树算法决策树算法主要是指在决策树的创建过程中，在分裂树（划分数据集）时选择最优特征的算法。其主要目的是选择一种特征，使分离后的数据集尽可能规则。也就是说，尽可能纯净。最大的原则就是：让无序的数据变得更有秩序。这里介绍三种常用的方法：信息增益、增益比和基尼不纯度。信息增益（Informationgain）涉及信息论中的一些概念：一个事件的信息量，信息熵，信息增益等。关于事件信息的通俗解释，可以看一个事件的信息量的答案ionZhihu:这个事件的概率的负对数信息熵是一个事件平均获得的信息量，即信息的期望值。任意一个序列都可以得到这个序列的信息熵，即在对这个序列进行分类后统计每一种类型的概率，然后用上面的公式计算，用Python实现如下：defget_shanno_entropy(self,values):'''根据给定列表中的值计算其ShannoEntropy'''uniq_vals=set(values)val_nums={key:values.count(key)forkeyinuniq_vals}probs=[v/len(values)fork,vinval_nums.items()]entropy=sum([-prob*log2(prob)forprobinprobs])returnentropyinformationgain我们会设置一组数据，经过这个集合划分后，数据的信息熵会发生变化。我们可以利用信息熵的计算公式计算分割后的子数据集的信息熵，计算它们的平均值（期望值）作为分割后的数据集的值。信息熵。与未分割数据的信息熵相比，新信息熵的减少就是信息增益。我一开始就误解了这一点，所以我写的代码无法创建正确的决策树。假设我们把数据集D分成kk份D1,D2,...,Dk，那么划分后的信息熵为：信息增益是两个信息熵的差这里我主要是利用信息增益来选择属性，具体实现代码如下：defchoose_best_split_feature(self,dataset,classes):'''根据信息增益确定分割数据的最佳特征：paramdataset：要分割的数据集：paramclasses：数据集对应的类型：返回：分割后的数据增益最大的属性索引'''base_entropy=self.get_shanno_entropy(classes)feat_num=len(dataset[0])entropy_gains=[]foriinrange(feat_num):splited_dict=self.split_dataset(dataset,classes,i)new_entropy=sum([len(sub_classes)/len(classes)*self.get_shanno_entropy(sub_classes)for_,(_,sub_classes)inplited_dict.items()])entropy_gains.append(base_entropy-new_entropy)returnentropy_gains.index(max(entropy_gains))gainratio增益比是一个扩展信息增益法的新思路，克服了信息增益带来的泛化能力弱的缺陷。因为根据信息增益的选择，总会倾向于选择分支多的属性，这样每个子集的信息熵都会最小。比如给每个数据加上一个唯一的id值特征，然后根据这个id值进行分类，以获得最大的信息增益，使得每个子集中的信息熵都为0，但是这样分类是没有意义的。没有任何泛化能力，类似于过拟合。因此，我们可以通过引入一个分割信息，即增益比，找到一个更适合衡量数据分割的标准。splitinformation的公式表示为：当然，SplitInfo可能趋近于0，此时增益比会变得很大，不可靠，所以有时需要在分母上加一个平滑函数。有关详细信息，请参阅参考部分。基尼不纯度（Giniimpurity）基尼不纯度的定义：其中m表示数据集D中类别的数量，pi表示某一类出现的概率。可以看出，当只有一种时，Giniimpurity的值为0，此时的impurity最低。数据集被分成k个子数据集的Giniimpurity可以通过下面的公式计算：这样我们就可以根据不纯的变化来选择最多的树分裂属性Treesplitting有一个选择最佳分裂属性的算法，Next，我们需要根据选择的属性进一步拆分树。所谓树的分裂无非就是将数据集按照选中的属性进行划分，然后在划分的总数据集中再次调用选择属性的方法，选择子数据集的中间属性。实现它的最好方法是递归。至于用什么数据结构来表示决策树，可以用Python中的字典来方便地表示决策树的嵌套。一棵树的根节点是属性，属性对应的值是一个新字典，其中键是属性可能的值，值是新的子树。下面是我使用Python基于数据集创建决策树的实现：defcreate_tree(self,dataset,classes,feat_names):'''根据当前数据集递归创建决策树:paramdataset:dataset:paramfeat_names:corresponding数据集中数据的特征名称：paramclasses：数据集中数据对应的类型：paramtree：以字典的形式返回决策树'''#如果数据集中只有一种类型，则停止树分裂iflen(set(classes))==1:returnclasses[0]#如果遍历完所有的特征，返回比例最大的类型iflen(feat_names)==0:returnet_majority(classes)#分裂创建新的子树树={}best_feat_idx=self.choose_best_split_feature(dataset,classes)feature=feat_names[best_feat_idx]tree[feature]={}#创建子数据集用于递归创建子树sub_feat_names=feat_names[:]sub_feat_names.pop(best_feat_idx)splited_dict=self.split_dataset（数据集，类，best_feat_idx）forfeat_val，(sub_dataset,sub_classes)insplited_dict.items():tree[feature][feat_val]=self.create_tree(sub_dataset,sub_classes,sub_feat_names)self.tree=treeself.feat_names=feat_namesreturntree树分裂有两种终止条件，一种是遍历所有的属性可以看到，在进行树分裂的时候，我们数据集中数据向量的长度在不断的缩短。当缩短为0时，表示数据集已经穷尽所有属性，无法再拆分。此时，我们选择最终子数据集中的模式放在叶子节点上，作为最终的分类结果。另一种是新划分的数据集中只有一种类型。如果某个节点指向的数据集都是同一类型的，那么即使没有遍历属性也不需要拆分。为了构建决策树，我使用了MLiA书中附带的隐形眼镜的数据。生成决策树，数据包含患者的眼部情况和医生推荐的隐形眼镜类型。首先导入数据，分离出与训练数据同类型的数据特征，生成决策树fromtreesimportDecisionTreeClassifierlense_labels=['age','prescript','astigmatic','tearRate']X=[]Y=[]withopen('lenses.txt','r')asf:forlineinf:comps=line.strip().split('\t')X.append(comps[:-1])Y.append(comps[-1])生成决策树：clf=DecisionTreeClassifier()clf.create_tree(X,Y,lense_labels)查看生成的决策树：In[2]:clf.treeOut[2]:{'tearRate':{'normal':{'散光'：{'不'：{'年龄'：{'pre'：'软'，'老花眼'：{'处方'：{'hyper'：'软'，'myope'：'nolenses'}},'young':'soft'}},'yes':{'prescript':{'hyper':{'age':{'pre':'nolenses','presbyopic':'nolenses','young':'hard'}},'myope':'hard'}}}},'reduced':'nolenses'}}直接将决策树可视化通过嵌套字典表示决策树不太容易让人理解。我们需要使用可视化工具来可视化树结构。在这里，我将使用Graphviz来可视化树结构。为此，实现了从字典表示的树中生成GraphvizDot文件内容的功能。大致思路是递归获取整棵树的所有节点和连接节点的边，然后将这些节点和边写成Dot格式的字符串写入文件。绘画。递归获取树的节点和边，其中uuid用于为每个节点添加一个id属性，以区分具有相同属性的节点。defget_nodes_edges(self,tree=None,root_node=None):'''返回树中的所有节点和Edge'''Node=namedtuple('Node',['id','label'])Edge=namedtuple('Edge',['start','end','label'])iftreeisNone:tree=self.treeiftype(tree)isnotdict:return[],[]nodes,edges=[],[]ifroot_nodeisNone:label=list(tree.keys())[0]root_node=Node._make([uuid.uuid4(),label])nodes.append(root_node)foredge_label,sub_treeintree[root_node.label].items():node_label=list(sub_tree.keys())[0]iftype(sub_tree)isdictelsesub_treesub_node=Node._make([uuid.uuid4(),node_label])nodes.append(sub_node)edge=Edge._make([root_node,sub_node,edge_label])edges.append(edge)sub_nodes,sub_edges=self.get_nodes_edges(sub_tree,root_node=sub_node)nodes.extend(sub_nodes)edges.extend(sub_edges)returnnodes,edges生成dot文件内容defdotify(self,tree=None):'''得到树的GraphvizDot文件内容'''iftreeisNone:tree=self.treecontent='digraphdecision_tree{\n'nodes,edges=self.get_nodes_edges(tree)fornodeinnodes:content+='"{}"[label="{}"];\n'.format(node.id,node.label)foredgeinedges:start,label,end=edge.start,edge.label,edge.endcontent+='"{}"->"{}"[label="{}"];\n'.format(start.id,end.id,label)content+='}'returncontent隐形眼镜数据生成Dot文件内容如下:digraphdecision_tree{“959b4c0c-1821-446d-94a1-c619c2decfcd”[label="call"];"18665160-b058-437f-9b2e-05df2eb55661"[label="to"];"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7"[label="你的"];"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd"[label="areyouunique"];"ca091fc7-8a4e-4970-9ec3-485a4628ad29"[label="02073162414"];"aac20872-1aac-499d-b2b5-caf0ef56eff3[label="ham"];"18aa8685-a6e8-4d76-bad5-ccea922bb14d"[label="spam"];"3f7f30b1-4dbb-4459-9f25-358ad3c6d50b"[label="spam"];"44d1f972-cd97-4636-b6e6-a389bf560656"[label="垃圾邮件"];"t;7f3c8562-69b5-47a9-8ee4-898bd4b6b506[label="i"];"a6f22325-8841-4a81-bc04-4e7485117aa1"[label="spam"];"c181fe42-fd3c-48db-968a-502f8dd462a4"[label="ldn"];"51b9477a-0326-4774-8622-24d1d869a283"[label="ham"];"16f6aecd-c675-4291-867c-6c64d27eb3fc"[label="spam"];"adb05303-813a-4fe0-bf98-c319eb70be48[label="spam"];"959b4c0c-1821-446d-94a1-c619c2decfcd"->"18665160-b058-437f-9b2e-05df2eb55661"[label="0"];"18665160-b058-437f-9b2e-05df2eb55661"->"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7"[label="0"];"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7"->"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd[label="0"];"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd"->"ca091fc7-8a4e-4970-9ec3-485a4628ad29"[label="0"];"ca091fc7-8a4e-4970-9ec3-485a4628ad29"->"aac20872-1aac-499d-b2b5-caf0ef56eff3"[label="0"];"ca091fc7-8a4e-4970-9ec3-485a4628ad29"->"18aa8685-a6e8-4d76-bad5-ccea922bb14d"[label=“1”];“bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd”->“3f7f30b1-4dbb-4459-9f25-358ad3c6d50b”[label="1"];"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7"->“44d1f972-cd97-4636-b6e6-a389bf560656”[label="1"];"18665160-b058-437f-9b2e-05df2eb55661"->"7f3c8562-69b5-47a9-8ee4-898bd4b6b506"[label="1"];“7f3c8562-69b5-47a9-8ee4-898bd4b6b506”->“a6f22325-8841-4a81-bc04-4e7485117aa1”[label="0"];"7f3c8562-69b5-47a9-8ee4-898bd4b6fd506"->4c1fe-48db-968a-502f8dd462a4[label="1"];"c181fe42-fd3c-48db-968a-502f8dd462a4"->"51b9477a-0326-4774-8622-24d1d869a283"[label="0"];"c181fe42-fd3c-48db-968a-502f8dd462a4"->"16f6aecd-c675-4291-867c-6c64d27eb3fc"[label="1"];"959b4c0c-1821-446d-94a1-c619c2decfcd"->"adb05303-8139af7-c3418"[label="1"];}所以我们可以使用Graphviz绘制决策树withopen('lenses.dot','w')asf:dot=clf.tree.dotify()f.write(dot)dot-Tgiflenses.dot-olenses.gif效果如下：利用生成的决策树对未知数据进行分类预测，主要是根据树中的节点递归寻找叶子节点这里的z可以进行递归优化，代码实现如下：defclassify(self,data_vect,feat_names=None,tree=None):'''根据构造的决策树对数据进行分类'''iftreeisNone:tree=self.treeiffeat_namesisNone:feat_names=self.feat_names#Recursivebasecase.iftype(tree)isnotdict:returntreefeature=list(tree.keys())[0]value=data_vect[feat_names.index(feature)]sub_tree=tree[feature][value]回归自我。classify(feat_names,data_vect,sub_tree)decisiontree的存储通过字典来表示决策树，这样我们就可以通过内置的pickle或者json模块存储到硬盘上，也可以从硬盘中读取树结构磁盘，这样在数据集非常大的时候，可以节省构建决策树的时间。defdump_tree(self,filename,tree=None):'''存储决策树'''iftreeisNone:tree=self.treewithopen(filename,'w')asf:pickle.dump(tree,f)defload_tree(self,filename):'''加载树结构'''withopen(filename,'r')asf:tree=pickle.load(f)self.tree=treereturntree总结step-by本文的-step实现实现了决策树的实现，其中使用ID3算法确定最佳划分属性，将构建的决策树通过Graphviz可视化。本文相关代码链接：https://github.com/PytLab/MLBox/tree/master/decision_tree参考：《Machine Learning in Action》数据挖掘系列（六）决策树分类算法
