model

相关模型介绍

分类模型

决策树

决策树(Decision Tree)算法是一种基本的分类与回归方法,是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。
决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树学习通常包括 3 个步骤: 特征选择、决策树的生成和决策树的修剪。

决策树场景

一个叫做 "二十个问题" 的游戏,游戏的规则很简单: 参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提 20 个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。
一个邮件分类系统,大致工作流程如下:
  • 首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。
  • 如果邮件不是来自这个域名,则检测邮件内容里是否包含单词 "曲棍球" , 如果包含则将邮件归类到 "需要及时处理的朋友邮件"。
  • 如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。
假如你了解足球,让你预测世界杯 32 个球队哪支球队是冠军
  • 在 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() 方法,伪代码如下所示:
1
def createBranch():
2
'''
3
此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion, 甚至是 dynamic programing。
4
'''
5
检测数据集中的所有数据的分类标签是否相同:
6
If so return 类标签
7
Else:
8
寻找划分数据集的最好特征(划分之后信息熵最小,也就是信息增益最大的特征)
9
划分数据集
10
创建分支节点
11
for 每个划分的子集
12
调用函数 createBranch (创建分支的函数)并增加返回结果到分支节点中
13
return 分支节点
Copied!

决策树开发流程

  • 收集数据: 可以使用任何方法。
  • 准备数据: 树构造算法 (这里使用的是ID3算法,只适用于标称型数据,这就是为什么数值型数据必须离散化。 还有其他的树构造算法,比如CART)。
  • 分析数据: 可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
  • 训练算法: 构造树的数据结构。
  • 测试算法: 使用训练好的树计算错误率。
  • 使用算法: 此步骤可以适用于任何监督学习任务,而使用决策树可以更好地理解数据的内在含义。

决策树算法特点

  • 优点: 计算复杂度不高,输出结果易于理解,数据有缺失也能跑,可以处理不相关特征。
  • 缺点: 容易过拟合。
  • 适用数据类型: 数值型和标称型。

决策树案例分析

实例一 鱼类非鱼类问题
决策树如下:
项目概述
根据以下 2 个特征,将动物分成两类: 鱼类和非鱼类。
特征:
  • 不浮出水面是否可以生存。
  • 是否有脚蹼(du 第三声)。
构造数据集
1
# 构造数据集
2
def create_data_set():
3
"""
4
:return: data_set 数据集, labels 标签数组
5
"""
6
data_set = [
7
[1, 1, 'yes'],
8
[1, 1, 'yes'],
9
[1, 0, 'no'],
10
[0, 1, 'no'],
11
[0, 1, 'no'],
12
[0, 0, 'no']
13
]
14
15
labels = ['no surfacing', 'flippers']
16
17
return data_set, labels
Copied!
计算香农熵(经验熵)shannonEnt
1
# 计算香农熵(经验熵)shannonEnt
2
def calc_shannon_ent(data_set):
3
"""
4
5
:param data_set: 数据集
6
:return: shannon_ent 香农熵
7
8
"""
9
10
# 计算 list 的长度,表示计算参与训练的数据量
11
num_entries = len(data_set)
12
# 计算分类标签 label 出现的次数
13
label_counts = {}
14
15
for feat_vec in data_set:
16
# 存储当前实例的标签存储,即每一行数据的最后一个数据代表的是标签
17
current_label = feat_vec[-1]
18
# 为所有可能的分类创建字典,如果当前值不存在,则扩展字典并将当前值加入字典。每个键值都记录了当前类别出现的次数。
19
if current_label not in label_counts.keys():
20
label_counts[current_label] = 0
21
label_counts[current_label] += 1
22
23
# 对于 label 标签的占比,求出 label 标签的香农熵
24
shannon_ent = 0.0
25
for key in label_counts:
26
# 使用所有类标签的发生频率计算类别出现的概率
27
prob = float(label_counts[key]) / num_entries
28
# 计算香农熵
29
shannon_ent -= prob * log(prob, 2)
30
31
return shannon_ent
Copied!
将指定特征值等于 value 的行剩下列作为子数据集
1
# 将指定特征值等于 value 的行剩下列作为子数据集
2
def split_data_set(data_set, index, value):
3
"""
4
(通过遍历 data_set 数据集,求出 index 对应的 column 列的值为 value 的行)
5
就是依据 index 列进行分类,如果index列的数据等于 value 的时候,就要将 index 划分到我们创建的新的数据集中
6
7
:param data_set: 数据集 待划分的数据集
8
:param index: 每一行的 index 列 划分数据集的特征
9
:param value: index 列对应的 value 值 需要返回的特征的值
10
:return:
11
ret_data_set 指定特征值等于 value 的行剩下列(不包含值等于该 value 的列)作为子数据集
12
"""
13
ret_data_set = []
14
for feat_vec in data_set:
15
# index 列为 value 的数据集[该数据集需要排除 index 列]
16
# 判断 index 列的值是否为 value
17
if feat_vec[index] == value:
18
# chop out index used for splitting
19
# [:index]表示前 index 行,即若 index 为 2,就是取 feat_vec 的前 2 行
20
reduced_feat_vec = feat_vec[:index]
21
'''
22
请百度查询一下: extend和append的区别
23
music_media.append(object) 向列表中添加一个对象object
24
music_media.extend(sequence) 把一个序列seq的内容添加到列表中 (跟 += 在list运用类似, music_media += sequence)
25
1、使用append的时候,是将object看作一个对象,整体打包添加到music_media对象中。
26
2、使用extend的时候,是将sequence看作一个序列,将这个序列和music_media序列合并,并放在其后面。
27
music_media = []
28
music_media.extend([1,2,3])
29
print music_media
30
#结果:
31
#[1, 2, 3]
32
33
music_media.append([4,5,6])
34
print music_media
35
#结果:
36
#[1, 2, 3, [4, 5, 6]]
37
38
music_media.extend([7,8,9])
39
print music_media
40
#结果:
41
#[1, 2, 3, [4, 5, 6], 7, 8, 9]
42
'''
43
# 取 index+1 行开始,后面的所有行数据
44
reduced_feat_vec.extend(feat_vec[index + 1:])
45
46
# 收集结果值 index 列为 value 的行[该行需要排除 index 列]
47
ret_data_set.append(reduced_feat_vec)
48
return ret_data_set
Copied!
选择信息增益最大的特征列
1
def choose_best_feature_to_split(data_set):
2
"""
3
:param data_set: 数据集
4
:return:
5
best_feature 最优的特征列
6
"""
7
# 求第一行有多少列的 Feature, 最后一列是 label 列
8
num_features = len(data_set[0]) - 1
9
# 数据集的原始信息熵
10
base_entropy = calc_shannon_ent(data_set)
11
# 最优的信息增益值, 和最优的 feature 编号
12
best_info_gain, best_feature = 0.0, -1
13
14
# iterate over all the features
15
for i in range(num_features):
16
# create a list of all the examples of this feature
17
# 获取对应的 feature 下的所有数据
18
feat_list = [example[i] for example in data_set]
19
# get a set of unique values
20
# 获取剔重后的集合,使用set对list数据进行去重
21
unique_vals = set(feat_list)
22
print("unique_vals:", unique_vals)
23
# 创建一个临时的信息熵
24
new_entropy = 0.0
25
# 遍历某一列的 value 集合,计算该列的信息熵
26
# 遍历当前特征中的所有唯一属性值,对每个唯一属性值划分一次数据集,计算数据集的新熵值,并对所有唯一特征值得到的熵求和。
27
for val in unique_vals:
28
sub_data_set = split_data_set(data_set, i, val)
29
# 计算概率
30
prob = len(sub_data_set) / float(len(data_set))
31
print("prob:", prob)
32
# 计算信息熵
33
new_entropy += prob * calc_shannon_ent(sub_data_set)
34
print("new_entropy:", new_entropy)
35
# gain[信息增益]: 划分数据集前后的信息变化, 获取信息熵最大的值
36
# 信息增益是熵的减少或者是数据无序度的减少。最后,比较所有特征中的信息增益,返回最好特征划分的索引值。
37
info_gain: float = base_entropy - new_entropy
38
print('info_gain=', info_gain, 'best_feature=', i, base_entropy, new_entropy)
39
if info_gain > best_info_gain:
40
best_info_gain = info_gain
41
best_feature = i
42
return best_feature
Copied!
构建决策树
1
def create_tree(data_set, labels):
2
"""
3
:param data_set: 数据集
4
:param labels: label 标签
5
:return: 返回决策树
6
"""
7
class_list = [example[-1] for example in data_set]
8
# 如果数据集的最后一列的第一个值出现的次数=整个集合的数量,也就说只有一个类别,就只直接返回结果就行
9
# 第一个停止条件: 所有的类标签完全相同,则直接返回该类标签。
10
# count() 函数是统计括号中的值在list中出现的次数
11
if class_list.count(class_list[0]) == len(class_list):
12
return class_list[0]
13
# 如果数据集只有 1 列,那么最初出现 label 次数最多的一类,作为结果
14
# 第二个停止条件: 使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组。
15
if len(data_set[0]) == 1:
16
return majority_cnt(class_list)
17
# 选择最优的列,得到最优列对应的label含义
18
best_feat = choose_best_feature_to_split(data_set)
19
# 获取label的名称
20
best_feat_label = labels[best_feat]
21
# 初始化myTree
22
my_tree = {best_feat_label: {}}
23
# 注: labels列表是可变对象,在PYTHON函数中作为参数时传址引用,能够被全局修改
24
# 所以这行代码导致函数外的同名变量被删除了元素,造成例句无法执行,提示'no surfacing' is not in list
25
del (labels[best_feat])
26
# 取出最优列,然后它的branch做分类
27
feat_vals = [example[best_feat] for example in data_set]
28
unique_vals = set(feat_vals)
29
for val in unique_vals:
30
# 求出剩余的标签label
31
sub_labels = labels[:]
32
# 遍历当前选择特征包含的所有属性值,在每个数据集划分上递归调用函数create_tree()
33
my_tree[best_feat_label][val] = create_tree(split_data_set(data_set, best_feat, val), sub_labels)
34
# print('myTree', val, my_tree)
35
return my_tree
Copied!
通过输入的特征,预测分类
1
def classify(input_tree, feat_labels, test_vec):
2
"""
3
给输入的节点,进行分类
4
:param input_tree: 决策树模型
5
:param feat_labels: feature标签对应的名称
6
:param test_vec: 测试输入的数据
7
:return:
8
class_label 分类的结果值,需要映射 label 才能知道名称
9
"""
10
# 获取 tree 的根节点对于的 key 值
11
first_str = list(input_tree.keys())[0]
12
# 通过key得到根节点对应的value
13
second_dict = input_tree[first_str]
14
# 判断根节点名称获取根节点在label中的先后顺序,这样就知道输入的testVec怎么开始对照树来做分类
15
feat_index = feat_labels.index(first_str)
16
# 测试数据,找到根节点对应的label位置,也就知道从输入的数据的第几位来开始分类
17
key = test_vec[feat_index]
18
feat_val = second_dict[key]
19
print('+++', first_str, 'xxx', second_dict, '---', key, '>>>', feat_val)
20
# 判断分枝是否结束: 判断 feat_val 是否是 dict 类型
21
if isinstance(feat_val, dict):
22
class_label = classify(feat_val, feat_labels, test_vec)
23
else:
24
class_label = feat_val
25
return class_label
Copied!
选择出现次数最多的一个结果
1
def majority_cnt(class_list):
2
"""
3
选择出现次数最多的一个结果
4
:param class_list: label 列的集合
5
:return: best_feature 最优的特征列
6
"""
7
# -----------majorityCnt的第一种方式 start------------------------------------
8
class_count = {}
9
for vote in class_list:
10
if vote not in class_count.keys():
11
class_count[vote] = 0
12
class_count[vote] += 1
13
# 倒叙排列classCount得到一个字典集合,然后取出第一个就是结果(yes/no),即出现次数最多的结果
14
sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True)
15
print('sortedClassCount:', sorted_class_count)
16
return sorted_class_count[0][0]
17
# -----------majorityCnt的第一种方式 end------------------------------------
18
19
# # -----------majorityCnt的第二种方式 start------------------------------------
20
# major_label = Counter(classList).most_common(1)[0]
21
# return major_label
22
# # -----------majorityCnt的第二种方式 end------------------------------------
Copied!

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