# model ## 相关模型介绍 ## 分类模型 ### 决策树 决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。 决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。 决策树学习通常包括 3 个步骤: 特征选择、决策树的生成和决策树的修剪。 #### 决策树场景 一个叫做 "二十个问题" 的游戏，游戏的规则很简单: 参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提 20 个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。 **一个邮件分类系统，大致工作流程如下**: ![邮件分类](https://blog.tommyyang.cn/img/ml/model/dt_email.png) * 首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。 * 如果邮件不是来自这个域名，则检测邮件内容里是否包含单词 "曲棍球" , 如果包含则将邮件归类到 "需要及时处理的朋友邮件"。 * 如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。 **假如你了解足球，让你预测世界杯 32 个球队哪支球队是冠军**： ![预测夺冠](https://blog.tommyyang.cn/img/ml/model/dt_32_champion.png) * 在 1-16 么？在 * 在 9-16 么？在 * 在 13-16 么？ 在 * 在 15 -16 么？ 在 * 是 15 么？ 不是 答案：16 号球队夺冠。 `tips` 最多通过 5 次机会就猜测出哪只球队是冠军球队。这个 5 代表的是 5 bit(比特)，相当于是 2^5=32，通过 5 bit 可以描述出这个信息量。 如果是 64 支球队，那么需要 6 bit 来描述这个信息量。 #### 信息熵(香农熵) 香农通过世界杯预测冠军的问题提出了信息熵，故信息熵也叫香农熵，信息熵用来度量信息量；信息量的度量等于不确定性的多少。 通过上述问题描述，相信读者已经了解了信息量的比特数和所有可能情况的对数函数 log 有关。（log32 = 5, log64 = 6）。 当然，如果是你对足球比较了解，通过历届球队的实力比较了解，以及世界杯参赛球队球星也比较了解。你可能会对一些球队能力的强弱进行分组， 因为你了解的信息量会多一些，所以猜测的不确定性就会小一些，从而你可能不需要 5 次就可以猜中。故香农提出了如下公式来计算信息熵： H(x) = -(P1 *logP1 + P2* logP2 + P3 *logP3 + ... + P32* logP32)， 其中P1、P2、P3...P32 分别代表 32 支球队夺冠的概率。 #### 信息增益 信息增益 = 信息熵 - 条件熵。 条件熵：在你得知一个信息(条件)后，得出结论还需要多少信息量。 信息增益越大，说明你得到的这个信息就越重要。 #### 决策树定义 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型: 内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。 用决策树对需要测试的实例进行分类: 从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。 #### 决策树工作原理 如何构造一个决策树? 使用 create\_branch() 方法，伪代码如下所示: ``` def createBranch(): ''' 此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion， 甚至是 dynamic programing。 ''' 检测数据集中的所有数据的分类标签是否相同: If so return 类标签 Else: 寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征） 划分数据集 创建分支节点 for 每个划分的子集 调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中 return 分支节点 ``` #### 决策树开发流程 * 收集数据: 可以使用任何方法。 * 准备数据: 树构造算法 (这里使用的是ID3算法，只适用于标称型数据，这就是为什么数值型数据必须离散化。 还有其他的树构造算法，比如CART)。 * 分析数据: 可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。 * 训练算法: 构造树的数据结构。 * 测试算法: 使用训练好的树计算错误率。 * 使用算法: 此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。 #### 决策树算法特点 * 优点: 计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。 * 缺点: 容易过拟合。 * 适用数据类型: 数值型和标称型。 #### 决策树案例分析 **实例一 鱼类非鱼类问题** 决策树如下： ![预测夺冠](https://blog.tommyyang.cn/img/ml/model/dt_fish.png) **项目概述** 根据以下 2 个特征，将动物分成两类: 鱼类和非鱼类。 特征: * 不浮出水面是否可以生存。 * 是否有脚蹼(du 第三声)。 **构造数据集** ```python # 构造数据集 def create_data_set(): """ :return: data_set 数据集, labels 标签数组 """ data_set = [ [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'], [0, 0, 'no'] ] labels = ['no surfacing', 'flippers'] return data_set, labels ``` **计算香农熵(经验熵)shannonEnt** ```python # 计算香农熵(经验熵)shannonEnt def calc_shannon_ent(data_set): """ :param data_set: 数据集 :return: shannon_ent 香农熵 """ # 计算 list 的长度，表示计算参与训练的数据量 num_entries = len(data_set) # 计算分类标签 label 出现的次数 label_counts = {} for feat_vec in data_set: # 存储当前实例的标签存储，即每一行数据的最后一个数据代表的是标签 current_label = feat_vec[-1] # 为所有可能的分类创建字典，如果当前值不存在，则扩展字典并将当前值加入字典。每个键值都记录了当前类别出现的次数。 if current_label not in label_counts.keys(): label_counts[current_label] = 0 label_counts[current_label] += 1 # 对于 label 标签的占比，求出 label 标签的香农熵 shannon_ent = 0.0 for key in label_counts: # 使用所有类标签的发生频率计算类别出现的概率 prob = float(label_counts[key]) / num_entries # 计算香农熵 shannon_ent -= prob * log(prob, 2) return shannon_ent ``` **将指定特征值等于 value 的行剩下列作为子数据集** ```python # 将指定特征值等于 value 的行剩下列作为子数据集 def split_data_set(data_set, index, value): """ (通过遍历 data_set 数据集，求出 index 对应的 column 列的值为 value 的行) 就是依据 index 列进行分类，如果index列的数据等于 value 的时候，就要将 index 划分到我们创建的新的数据集中 :param data_set: 数据集 待划分的数据集 :param index: 每一行的 index 列 划分数据集的特征 :param value: index 列对应的 value 值 需要返回的特征的值 :return: ret_data_set 指定特征值等于 value 的行剩下列(不包含值等于该 value 的列)作为子数据集 """ ret_data_set = [] for feat_vec in data_set: # index 列为 value 的数据集[该数据集需要排除 index 列] # 判断 index 列的值是否为 value if feat_vec[index] == value: # chop out index used for splitting # [:index]表示前 index 行，即若 index 为 2，就是取 feat_vec 的前 2 行 reduced_feat_vec = feat_vec[:index] ''' 请百度查询一下: extend和append的区别 music_media.append(object) 向列表中添加一个对象object music_media.extend(sequence) 把一个序列seq的内容添加到列表中 (跟 += 在list运用类似， music_media += sequence) 1、使用append的时候，是将object看作一个对象，整体打包添加到music_media对象中。 2、使用extend的时候，是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。 music_media = [] music_media.extend([1,2,3]) print music_media #结果: #[1, 2, 3] music_media.append([4,5,6]) print music_media #结果: #[1, 2, 3, [4, 5, 6]] music_media.extend([7,8,9]) print music_media #结果: #[1, 2, 3, [4, 5, 6], 7, 8, 9] ''' # 取 index+1 行开始，后面的所有行数据 reduced_feat_vec.extend(feat_vec[index + 1:]) # 收集结果值 index 列为 value 的行[该行需要排除 index 列] ret_data_set.append(reduced_feat_vec) return ret_data_set ``` **选择信息增益最大的特征列** ```python def choose_best_feature_to_split(data_set): """ :param data_set: 数据集 :return: best_feature 最优的特征列 """ # 求第一行有多少列的 Feature, 最后一列是 label 列 num_features = len(data_set[0]) - 1 # 数据集的原始信息熵 base_entropy = calc_shannon_ent(data_set) # 最优的信息增益值, 和最优的 feature 编号 best_info_gain, best_feature = 0.0, -1 # iterate over all the features for i in range(num_features): # create a list of all the examples of this feature # 获取对应的 feature 下的所有数据 feat_list = [example[i] for example in data_set] # get a set of unique values # 获取剔重后的集合，使用set对list数据进行去重 unique_vals = set(feat_list) print("unique_vals:", unique_vals) # 创建一个临时的信息熵 new_entropy = 0.0 # 遍历某一列的 value 集合，计算该列的信息熵 # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。 for val in unique_vals: sub_data_set = split_data_set(data_set, i, val) # 计算概率 prob = len(sub_data_set) / float(len(data_set)) print("prob:", prob) # 计算信息熵 new_entropy += prob * calc_shannon_ent(sub_data_set) print("new_entropy:", new_entropy) # gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值 # 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。 info_gain: float = base_entropy - new_entropy print('info_gain=', info_gain, 'best_feature=', i, base_entropy, new_entropy) if info_gain > best_info_gain: best_info_gain = info_gain best_feature = i return best_feature ``` **构建决策树** ```python def create_tree(data_set, labels): """ :param data_set: 数据集 :param labels: label 标签 :return: 返回决策树 """ class_list = [example[-1] for example in data_set] # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行 # 第一个停止条件: 所有的类标签完全相同，则直接返回该类标签。 # count() 函数是统计括号中的值在list中出现的次数 if class_list.count(class_list[0]) == len(class_list): return class_list[0] # 如果数据集只有 1 列，那么最初出现 label 次数最多的一类，作为结果 # 第二个停止条件: 使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。 if len(data_set[0]) == 1: return majority_cnt(class_list) # 选择最优的列，得到最优列对应的label含义 best_feat = choose_best_feature_to_split(data_set) # 获取label的名称 best_feat_label = labels[best_feat] # 初始化myTree my_tree = {best_feat_label: {}} # 注: labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改 # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list del (labels[best_feat]) # 取出最优列，然后它的branch做分类 feat_vals = [example[best_feat] for example in data_set] unique_vals = set(feat_vals) for val in unique_vals: # 求出剩余的标签label sub_labels = labels[:] # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数create_tree() my_tree[best_feat_label][val] = create_tree(split_data_set(data_set, best_feat, val), sub_labels) # print('myTree', val, my_tree) return my_tree ``` **通过输入的特征，预测分类** ```python def classify(input_tree, feat_labels, test_vec): """ 给输入的节点，进行分类 :param input_tree: 决策树模型 :param feat_labels: feature标签对应的名称 :param test_vec: 测试输入的数据 :return: class_label 分类的结果值，需要映射 label 才能知道名称 """ # 获取 tree 的根节点对于的 key 值 first_str = list(input_tree.keys())[0] # 通过key得到根节点对应的value second_dict = input_tree[first_str] # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类 feat_index = feat_labels.index(first_str) # 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类 key = test_vec[feat_index] feat_val = second_dict[key] print('+++', first_str, 'xxx', second_dict, '---', key, '>>>', feat_val) # 判断分枝是否结束: 判断 feat_val 是否是 dict 类型 if isinstance(feat_val, dict): class_label = classify(feat_val, feat_labels, test_vec) else: class_label = feat_val return class_label ``` **选择出现次数最多的一个结果** ```python def majority_cnt(class_list): """ 选择出现次数最多的一个结果 :param class_list: label 列的集合 :return: best_feature 最优的特征列 """ # -----------majorityCnt的第一种方式 start------------------------------------ class_count = {} for vote in class_list: if vote not in class_count.keys(): class_count[vote] = 0 class_count[vote] += 1 # 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果 sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True) print('sortedClassCount:', sorted_class_count) return sorted_class_count[0][0] # -----------majorityCnt的第一种方式 end------------------------------------ # # -----------majorityCnt的第二种方式 start------------------------------------ # major_label = Counter(classList).most_common(1)[0] # return major_label # # -----------majorityCnt的第二种方式 end------------------------------------ ``` ### GBDT GBDT: Gradient Boost Decision Tree。DT－Decision Tree决策树，GB是Gradient Boosting，是一种学习策略，GBDT的含义就是用Gradient Boosting的策略训练出来的DT模型。可以处理二分类问题。 ### LightGBM ### XGBoost #### 分类树与回归树 XGBoost是以CART回归树作为基本分类器。 分类树：分类树的样本输出都是以类别的形式，比如说判断用户会不会购买华为Mate40，判断西瓜是甜还是不甜。 回归树：回归树的样本输出是数值的形式，比如给某人发放房屋贷款的数额，给某人发放的红包金额。 #### Boost介绍 Boost可以用于回归和分类问题，它每一步会产生一个弱分类器 (如决策树)，然后通过加权累加起来变成一个强分类器。比如每一步都会产生一个f(x)，F(x)=sum(fi(x))，其实就是一堆分类器通过加权合并成一个强分类器。 #### 提升树 首先要明确一点，xgboost 是基于提升树的。 什么是提升树，简单说，就是一个模型表现不好，我继续按照原来模型表现不好的那部分训练第二个模型，依次类推。 来几个形象的比喻就是： 做题的时候，第一个人做一遍得到一个分数，第二个人去做第一个人做错的题目，第三个人去做第二个人做错的题目，以此类推，不停的去拟合从而可以使整张试卷分数可以得到100分（极端情况）。 把这个比喻替换到模型来说，就是真实值为100，第一个模型预测为90，差10分，第二个模型以10为目标值去训练并预测，预测值为7，差三分，第三个模型以3为目标值去训练并预测，以此类推。 ### Random Forests