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

1、机器学习-决策树(ID3)算法及案例1基本原理决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路 径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理,计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是然后指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。采用递归的原则处理数据集，并得到了我们需要的决策树。2算法流程检测数据集中的每个子项是否属于同一分类:If是，则返回类别标签;Else计算

2、信息增益，寻找划分数据集的最好特征划分数据数据集创建分支节点(叶结点或决策结点)for每个划分的子集递归调用，并增加返回结果到分支节点中return分支结点算法的基本思想可以概括为:1）树以代表训练样本的根结点开始。2）如果样本都在同一个类.则该结点成为树叶，并记录该类。3）否则，算法选择最有分类能力的属性作为决策树的当前结点.4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若 干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到 的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。 一旦一个 属性只出现在一个结点上，就不必在该结点的任何后代考虑它

3、，直接标记类别。5）递归划分步骤仅当下列条件之一成立时停止: 给定结点的所有样本属于同一类。同时 没有剩余属性可以用来进一步划分样本.在这种情况下.使用多数表决, 将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记， 也可以存放该结点样本的类别分布这个主要可以用来剪枝。 如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类 生成叶子节点。算法中2）步所指的最优分类能力的属性。这个属性的选择是本算法种的关键 点，分裂属性的选择直接关系到此算法的优劣。一般来说可以用比较信息增益和信息增益率的方式来进行。其中信息增益的概念又会牵扯出熵的概念。 熵的概念是香农在研究信息量方

4、面 的提出的。它的计算公式是：In fo(D)=-p1log( p1)/log(2.0)-p2log( p2)/log(2.0)-p3log( p3)/log(2.0)+.-pNlog( pN) /log(2.0)(其中N表示所有的不同类别)HEntropv (S)- -Z log Pi7 = 1而信息增益为:Gai n( A)=l nfo(D)-l nfo(Da)情况下的信息量(熵)。其中Info(Da)数据集在属性A的Gain(A) = Enfropy (5)-工RJe 泊 q，()3算法的特点优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。缺点：可能

5、会产生过度匹配问题适用数据范围：数值型和标称型。4python代码实现1、创建初始数据集，用于测试 #功能：创建数据集#输入变量：空 #输出变量：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 surfac in g, fli pp ers#表示决策结点，也称特征标签retu rn data_set, labels2、计算给定数据集的信息熵 #功能：计算信息熵 #输入变量：da

6、ta set数据集 #输出变量：shannon ent信息熵 # def calc_sha nnon_en t(data_set):num_en tries = len( data_set) label_co unts = for feat_vec in data_set: curre nt_label = feat_vec-1# get相当于一条 if.else.语句#如果参数current_label不在字典中则返回参数0，#如果current label在字典中则返回current label对应的value值label_co un tscurre nt_label = label_c

7、oun ts.get(curre nt_label, 0) + 1shannon ent = 0.0for key in label_c oun ts:prob = float(label_c oun tskey)/num_en tries sha nnon_ent -= p rob*log( prob, 2)return shannon ent3、按照给定特征划分数据集。分类算法除了需要测量信息熵，还需要划分数据集，这就需要对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式。#功能：划分数据集 # 输入变量： data_set, axis, value#

8、数据集，数据集的特征，特征的值 #输出变量：ret_data_set,划分后的数据集 # def spli t_data_set(data_set, axis, value):ret_data_set =for feat_vec in data_set: if feat_vecaxis = value:#把axis特征位置之前和之后的特征值切出来#没有使用del函数的原因是，del会改变原始数据reduced_feat_vec = feat_vec:axis reduced_feat_vec.exte nd(feat_vecaxis+1:) ret_data_set.a ppen d(redu

9、ced_feat_vec)return ret data set4、遍历整个数据集，循环划分数据并计算信息熵，通过计算最大信息增益来找到最好的特征划分方式。具体做法是，遍历当前特征中的所有唯一属性值， 对每个特征划分一次数据集，然后计算数据集的新熵值，并对所有唯一特征值得到的熵求和。最后用所求的和值与原始信息熵相减，计算寻找最大信息增益。#功能：选择最好的数据集划分方式#输入变量：data set待划分的数据集#输出变量：best feature计算得出最好的划分数据集的特征 # def choose_best_feature_to_s plit(data_set):num_features

10、= len (data_setO) - 1 #最后一个是类别标签，所以特征属性长度为总长度减1base_entropy 二 calc_shannon_ent(data_set)# 计算数据集原始信息熵best_i nfo_ga in 二 0.0best feature = -1for i in xran ge( numfeatures):# feat_veci代表第i列的特征值，在for循环获取这一列的所有值feat_list = feat_veci for feat_vec in data_setun ique_vals = set(feat_list) # set函数得到的是一个无序不重复

11、数据集n ew_e ntropy 二 0.0#计算每种划分方式的信息熵for value in uniqu e_vals: sub_data_set = sp lit_data_set(data_set, i, value) prob = len (sub_data_set)/float(le n(data_set) n ew_e ntropy += p rob*calc_sha nnon_en t(sub_data_set)in fo_ga in 二 base_e ntropy - n ew_e ntropy if in fo_ga in best_i nfo_ga in:best_i nf

12、o_ga in 二 in fo_gain best feature = ireturn best feature 5递归构建决策树工作原理：得到原始数据集，然后基于最好的属性值划分数据集，由于第一特征值可能多于两个，因此可能存在大于两个分支的数据集划分。次划分之后，数据将被向下传递到树分支的下一个节点， 在这个节点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。递归结束条件是：第一、所有的类别标签（叶结点）完全相同。第二、使用完了所有的特征，仍然不能将数据集划分成仅包含唯一类别的分组,则挑选出次数最多的类别作为返回值。#功能：多数表决分类#输入变量：class list所有数据

13、的标签数组 #输出变量：sorted_class_count00出现次数最多的分类名称 # def majonty_vote_sort(class_list):class_co unt = for vote in class_list:class_cou ntvote = class_c oun t.get(vote, 0) + 1# items以列表方式返回字典中的键值对，iteritems以迭代器对象返回键值对，而键值对以元组方式存储，即这种方式(),()# op erator.itemgetter(0获取对象的第0个域的值，即返回的是key值# op erator.itemgetter(

14、1获取对象的第1个域的值，即返回的是 value通过该函数作用到对象上才能# op erator.itemgetter 定义了一个函数,获取值# reverse二True是按降序排序sorted_class_co unt = sorted(class_c oun t.iteritems(), key=op erator.itemgetter(1), reverse二True)return sorted_class_c oun t00 #功能：创建数 #输入变量：data_set, labels待分类数据集，标签#输出变量：my_tree决策树# def create_tree(data_set

15、, labels):class_list = exa mpl e-1 for exa mple in data_set#判断类别标签是否完全相同# cou nt()是列表内置的方法，可以统计某个元素在列表中出现的次数if class_list.co un t(class_list0) = len (class_list):return class_list0#遍历完所有特征时返回出现次数最多的if len( data_set0) = 1:return majority_vote_sort(class_list) best_feat = choose_best_feature_to_s plit

16、(data_set) best_feat_label = labelsbest_featmy_tree = best_feat_label: del(labelsbest_feat)#得到列表包含的所有属性值feat_values = exa mpl ebest_feat for exa mple in data_set uniq ue_vals = set(feat_values)for value in uniqu e_vals:sub_labels = labels: # :复制特征标签，为了保证循环调用函数 create_tree()不改变原始的内容ret_data_set = sp

17、lit_data_set(data_set, best_feat, value) my_treebest_feat_labelvalue = create_tree(ret_data_set, sub_labels)return my_tree 6测试代码 def main():my_data, my_labels = create_data_set() #my_data0-1 = maybe prin t my_data=, my_dataprin t my_labels=, my_labelssha nnon_ent = calc_sha nnon_en t(my_data) prin t

18、 sha nnon_en t=, sha nnon_entret_data_set = split_data_set(my_data, 1, 1) # 由第 1 个特征且特征值为1的数据集划分出来prin t ret_data_set=, ret_data_setbest_feature = choose_best_feature_to_s plit(my_data) prin t best_feature=, best_featuremy_tree = create_tree(my_data, my_labels) prin t my_tree=, my_treeif _name mai n

19、()main在进行案例分析前，先对决策树算法的分类函数进行测试。考虑到构造决策树非常耗时，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。这就需要利用python模块pickle序列化对象将决策树分类算法保存在磁盘中，并在需要的时候读取出来。1、测试决策树分类算法性能 #功能：决策树的分类函数# 输入变量：inpu t_tree, feat_labels, test_vec#决策树，分类标签，测试数据 #输出变量：class label类标签 # def classify(i npu t_tree, feat_labels, test_vec): first_str = in

20、pu t_tree.keys()O sec on d_dict = inpu t_treefirst_str class label = -1# index方法用于查找当前列表中第一个匹配first str变量的索引feat_i ndex = feat_labels.i ndex(first_str)for key in sec on d_dict.keys():if test_vecfeat_ in dex = key:if type(second_dictkey)._name_ = diet: class_label = classify(sec on d_dictkey, feat_la

21、bels, test_vec)else:class_label = sec on d_dictkeyreturn class label2、对决策树算法进行存储 #功能：将决策树存储到磁盘中#输入变量：inpu t_tree, file name决策树，存储的文件名# def store_tree(i npu t_tree, file name):import pi cklefw = open( file name, w)pickle.dump(input_tree, fw)#序列化，将数据写入到文件中fw.close()3、对决策树算法进行读取 #功能：从磁盘中读取决策树信息#输入变量：file name存储的文件名 # def grab_tree(file name):import P icklefr = open( file name, r)return pickle.load(fr) # 反序列化4、代码测试 def main():my_data, my_labels = create_data_set() prin t my_data=, my_data prin t my_label