相关模型介绍
分类模型
决策树
决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树学习通常包括 3 个步骤: 特征选择、决策树的生成和决策树的修剪。
决策树场景
一个叫做 "二十个问题" 的游戏，游戏的规则很简单: 参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提 20 个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。
一个邮件分类系统，大致工作流程如下:
首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。
如果邮件不是来自这个域名，则检测邮件内容里是否包含单词 "曲棍球" , 如果包含则将邮件归类到 "需要及时处理的朋友邮件"。
如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。
假如你了解足球，让你预测世界杯 32 个球队哪支球队是冠军：
答案：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)。
分析数据: 可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
使用算法: 此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。
决策树算法特点
优点: 计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
决策树案例分析
实例一 鱼类非鱼类问题
项目概述
根据以下 2 个特征，将动物分成两类: 鱼类和非鱼类。
特征:
构造数据集
# 构造数据集
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
# 计算香农熵(经验熵)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 的行剩下列作为子数据集
# 将指定特征值等于 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
选择信息增益最大的特征列
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
构建决策树
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
通过输入的特征，预测分类
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
选择出现次数最多的一个结果
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
