机器学习--决策树(ID3)算法及案例..doc

机器学习--决策树(ID3)算法及案例 1基本原理 ? ? 决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下， 2算法流程 ????????If 是，则返回类别标签； ????? ??Else????????????? ???????????计算信息增益，寻找划分数据集的最好特征?????????? ?????????? 划分数据数据集 ?????????? 创建分支节点（叶结点或决策结点） ?????????????? for 每个划分的子集 ?????????????????? 递归调用，并增加返回结果到分支节点中 ???????????return 分支结点 算法的基本思想可以概括为： ? ??1）树以代表训练样本的根结点开始。 ? ? 2）如果样本都在同一个类．则该结点成为树叶，并记录该类。 ? ? 3）否则，算法选择最有分类能力的属性作为决策树的当前结点． ? ? 4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。 ? ? 5）递归划分步骤仅当下列条件之一成立时停止： ? ? ①给定结点的所有样本属于同一类。 ? ? ②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。 ? ? ③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。 ? 算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。 ? ?一般来说可以用比较信息增益和信息增益率的方式来进行。 ? 其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是： ? ? Info(D)=-p1log(p1)/log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+...-pNlog(pN)/log(2.0) ? ?(其中N表示所有的不同类别) ? 而信息增益为： ? ? ? ? ? ? Gain(A)=Info(D)-Info(Da) ? ? ? ? ? ? 其中Info(Da)数据集在属性A的情况下的信息量(熵)。 3算法的特点 ????优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。 ????缺点：可能会产生过度匹配问题 ????适用数据范围：数值型和标称型。 4python代码实现 #######################################功能：创建数据集#输入变量：空#输出变量：data_set, labels 数据集，标签######################################def create_data_set(): ??? data_set = [[1, 1, yes], ???????????????? [1, 1, yes],??????????????? [1, 0, no],??????????????? [0, 1, no],??????????????? [0, 1, no]] ? ?# ?数据集最后一列表示叶结点，也称类别标签??? labels = [no surfacing, flippers] ? #?表示决策结点，也称特征标签 ??? return data_set, labels ##############################功能：计算信息熵#输入变量：data_set 数据集#输出变量：shannon_ent 信息熵#############################def calc_shannon_ent(data_set): ??? num_entries = len(data_set)??? label_counts = {} ??? for feat_vec in data_set:??????? current_label = feat_vec[-1]??????? # get相当于一条if...else...语句??????? # 如果参数current_label不在字典中