决策树例题经典案例（机器学习）

任务介绍

英雄联盟（League of Legends，LoL）是一个多人在线竞技游戏，由拳头游戏（Riot Games）公司出品。在游戏中，每位玩家控制一位有独特技能的英雄，红蓝两支队伍各有五位玩家进行对战，目标是摧毁对方的基地水晶。水晶有多座防御塔保护，通常需要先摧毁一些防御塔再摧毁水晶。玩家所控制的英雄起初非常弱，需要不断击杀小兵、野怪和对方英雄来获得金币、经验。经验可以提升英雄等级和技能等级，金币可以用来购买装备提升攻击、防御等属性。对战过程中一般没有己方单位在附近的地点是没有视野的，即无法看到对面单位，双方可以通过使用守卫来监视某个地点，洞察对面走向、制定战术。 本数据集来自Kaggle，包含了9879场钻一到大师段位的单双排对局，对局双方几乎是同一水平。每条数据是前10分钟的对局情况，每支队伍有19个特征，红蓝双方共38个特征。这些特征包括英雄击杀、死亡，金钱、经验、等级情况等等。一局游戏一般会持续30至40分钟，但是实际前10分钟的局面很大程度上影响了之后胜负的走向。作为最成功的电子竞技游戏之一，对局数据、选手数据的量化与研究具有重要意义，可以启发游戏将来的发展和改进。

本任务是希望同学们依据注释的要求，对代码中空缺部分进行填写，完成决策树模型的详细实现，根据已有的对局前10分钟特征信息，预测最后获胜方是蓝色方还是红色方。

导入工具包

pandas是数据分析和处理常用的工具包，非常适合处理行列表格数据。numpy是数学运算工具包，支持高效的矩阵、向量运算。sklearn是机器学习常用工具包，包括了一些已经实现好的简单模型和一些常用数据处理方法、评价指标等函数。

from collections import Counterimport pandas as pd # 数据处理import numpy as np # 数学运算from sklearn.model_selection import train_test_split, cross_validate # 划分数据集函数from sklearn.metrics import accuracy_score # 准确率函数RANDOM_SEED = 2020 # 固定随机种子

读入数据

假设数据文件放在./data/目录下，标准的csv文件可以用pandas里的read_csv()函数直接读入。文件共有40列，38个特征（红蓝方各19），1个标签列（blueWins），和一个对局标号（gameId）。对局标号不是标签也不是特征，可以舍去。

csv_data = './data/high_diamond_ranked_10min.csv' # 数据路径data_df = pd.read_csv(csv_data, sep=',') # 读入csv文件为pandas的DataFramedata_df = data_df.drop(columns='gameId') # 舍去对局标号列

数据概览

对于一个机器学习问题，在拿到任务和数据后，首先需要观察数据的情况，比如我们可以通过.iloc[0]取出数据的第一行并输出。不难看出每个特征都存成了float64浮点数，该对局蓝色方开局10分钟有小优势。同时也可以发现有些特征列是重复冗余的，比如blueGoldDiff表示蓝色队金币优势，redGoldDiff表示红色方金币优势，这两个特征是完全对称的互为相反数。blueCSPerMin是蓝色方每分钟击杀小兵数，它乘10就是10分钟所有小兵击杀数blueTotalMinionsKilled。在之后的特征处理过程中可以考虑去除这些冗余特征。 另外，pandas有非常方便的describe()函数，可以直接通过DataFrame进行调用，可以展示每一列数据的一些统计信息，对数据分布情况有大致了解，比如blueKills蓝色方击杀英雄数在前十分钟的平均数是6.14、方差为2.93，中位数是6，百分之五十以上的对局中该特征在4-8之间，等等。

print(data_df.iloc[0]) # 输出第一行数据data_df.describe() # 每列特征的简单统计信息

Out：

blueWins                            0.0blueWardsPlaced                    28.0blueWardsDestroyed                  2.0blueFirstBlood                      1.0blueKills                           9.0blueDeaths                          6.0blueAssists                        11.0blueEliteMonsters                   0.0blueDragons                         0.0blueHeralds                         0.0blueTowersDestroyed                 0.0blueTotalGold                   17210.0blueAvgLevel                        6.6blueTotalExperience             17039.0blueTotalMinionsKilled            195.0blueTotalJungleMinionsKilled       36.0blueGoldDiff                      643.0blueExperienceDiff                 -8.0blueCSPerMin                       19.5blueGoldPerMin                   1721.0redWardsPlaced                     15.0redWardsDestroyed                   6.0redFirstBlood                       0.0redKills                            6.0redDeaths                           9.0redAssists                          8.0redEliteMonsters                    0.0redDragons                          0.0redHeralds                          0.0redTowersDestroyed                  0.0redTotalGold                    16567.0redAvgLevel                         6.8redTotalExperience              17047.0redTotalMinionsKilled             197.0redTotalJungleMinionsKilled        55.0redGoldDiff                      -643.0redExperienceDiff                   8.0redCSPerMin                        19.7redGoldPerMin                    1656.7Name: 0, dtype: float64

增删特征

传统的机器学习模型大部分都是基于特征的，因此特征工程是机器学习中非常重要的一步。有时构造一个好的特征比改进一个模型带来的提升更大。这里简单展示一些特征处理的例子。首先，上面提到，特征列中有些特征信息是完全冗余的，会给模型带来不必要的计算量，可以去除。其次，相比于红蓝双方击杀、助攻的绝对值，可能双方击杀英雄的差值更能体现出当前对战的局势。因此，我们可以构造红蓝双方对应特征的差值。数据文件中已有的差值是金币差GoldDiff和经验差ExperienceDiff，实际上每个对应特征都可以构造这样的差值特征。

drop_features = ['blueGoldDiff', 'redGoldDiff',                 'blueExperienceDiff', 'redExperienceDiff',                 'blueCSPerMin', 'redCSPerMin',                 'blueGoldPerMin', 'redGoldPerMin'] # 需要舍去的特征列df = data_df.drop(columns=drop_features) # 舍去特征列info_names = [c[3:] for c in df.columns if c.startswith('red')] # 取出要作差值的特征名字（除去red前缀）for info in info_names: # 对于每个特征名字    df['br' + info] = df['blue' + info] - df['red' + info] # 构造一个新的特征，由蓝色特征减去红色特征，前缀为br# 其中FirstBlood为首次击杀最多有一只队伍能获得，brFirstBlood=1为蓝，0为没有产生，-1为红df = df.drop(columns=['blueFirstBlood', 'redFirstBlood']) # 原有的FirstBlood可删除

特征离散化

决策树ID3算法一般是基于离散特征的，本例中存在很多连续的数值特征，例如队伍金币。直接应用该算法每个值当作一个该特征的一个取值可能造成严重的过拟合，因此需要对特征进行离散化，即将一定范围内的值映射成一个值，例如对用户年龄特征，将0-10映射到0，11-18映射到1，19-25映射到2，25-30映射到3，等等类似，然后在决策树构建时使用映射后的值计算信息增益。

本小节要求实现特征离散化，请补全相关代码

pd.cut()discrete_df = df.copy() # 先复制一份数据for c in df.columns[1:]: # 遍历每一列特征，跳过标签列    '''    请离散化每一列特征，即discrete_df[c] = ...    提示：    对于有些特征本身取值就很少，可以跳过即 if ... : continue    对于其他特征，可以使用等区间离散化、等密度离散化或一些其他离散化方法    可参考使用pandas.cut或qcut    '''    if len(set(discrete_df[c]))>=10:        x=list(discrete_df[c])        y=pd.cut(x,5,labels=[0,1,2,3,4])        discrete_df[c]=ydiscrete_df.head(10)

数据集准备

构建机器学习模型前要构建训练和测试的数据集。在本例中首先需要分开标签和特征，标签是不能作为模型的输入特征的，就好比作业和试卷答案不能在做题和考试前就告诉学生。测试一个模型在一个任务上的效果至少需要训练集和测试集，训练集用来训练模型的参数，好比学生做作业获得知识，测试集用来测试模型效果，好比期末考试考察学生学习情况。测试集的样本不应该出现在训练集中，否则会造成模型效果估计偏高，好比考试时出的题如果是作业题中出现过的，会造成考试分数不能准确衡量学生的学习情况，估计值偏高。划分训练集和测试集有多种方法，下面首先介绍的是随机取一部分如20%作测试集，剩下作训练集。sklearn提供了相关工具函数train_test_split。sklearn的输入输出一般为numpy的array矩阵，需要先将pandas的DataFrame取出为numpy的array矩阵。

all_y = discrete_df['blueWins'] # 所有标签数据feature_names = discrete_df.columns[1:] # 所有特征的名称all_x = discrete_df[feature_names] # 所有原始特征值，pandas的DataFrame.values取出为numpy的array矩阵# 划分训练集和测试集x_train, x_test, y_train, y_test = train_test_split(all_x, all_y, test_size=0.2, random_state=RANDOM_SEED)all_y.shape, all_x.shape, x_train.shape, x_test.shape, y_train.shape, y_test.shape # 输出数据行列信息

((9879,), (9879, 43), (7903, 43), (1976, 43), (7903,), (1976,))

x_train,y_train = pd.DataFrame(x_train,columns=all_x.columns),pd.DataFrame(y_train,columns=all_x.columns)

决策树模型的实现

本小节要求实现决策树模型，请补全算法代码

Gini系数是一种度量落在决策树中某一个节点的样本分布不纯度的指标。假设数据集中样本一共有 个类别，在节点 中第 类样本的比例为 , ，则节点 的不纯度为

假设样本的类别为正负两类，假设某个节点一共有 10 个样本，包括 5 个正样本和 5 个负样本，则基尼系数为

假设另一个节点有 20 个样本，包含 15 个正样本和 5 个负样本，则基尼系数为

实现一个不纯度计算方法 gini ,它的输入是当前节点样本的标签序列 。 是 Pandas 的 Series结构。我们使用 value_counts 方法计算每一类样本的数量，然后借助 np.square 和 sum 函数计算其平方和。

1.1 定义决策树节点

创建一个表示决策树节点的类 TreeNode。决策树节点需要存储的最重要的信息为当前节点代表的特征 f 和切分点 v 。其次如果节点是非叶子节点，还需要存储左儿子节点 left 和右儿子节点 right。为了便于决策树进行预测，我们在每个节点中还要保存当前节点样本的分布 label_dist，它将在决策树生成时提供。在本案例的后续，我们还将把决策树绘制出来，为了方便绘制，我们给每一个节点还保存了节点的坐标信息 pos ，也将在决策树生成时计算。

决策树生成函数 generate 的主要流程为：

1 创建当前节点 current_node ,计算其样本分布 label_dist2 if 当前样本数量太少，决策树层数超过最大深度或者节点的基尼系数小于某个阈值节点不再分裂，返回 current_node3 else3.1 遍历所有候选特征和切分点对 ( , ),计算其基尼系数，找出最佳的分裂特征和切分点 ( _ , _ )3.2 根据 ( _ , _ )将数据子集分为两个子集 ( 1, 1) 和 ( 2, 2)3.3 使用 ( 1, 1)调用 generate 函数创建 current_node 的左儿子节点3.3 使用 ( 2, 2)调用 generate 函数创建 current_node 的左儿子节点4 返回当前节点 current_node

class TreeNode:    def __init__(self,x_pos,y_pos,layer,class_labels=[0,1,2]):        self.f = None #当前节点的切分特征        self.v = None #当前节点的切分点        self.left = None #左儿子节点        self.right = None #右儿子节点        self.pos = (x_pos,y_pos) # 节点坐标，可视化用        self.label_dist = None #当前节点样本的类分布        self.layer = layer        self.class_labels = class_labels    def __str__(self): #打印节点信息，可视化时的节点标签        if self.f != None:            return self.f + "\n<=" + str(round(self.v,2))        else:            return str(self.label_dist) + "\n(" + str(np.sum(self.label_dist)) + ")"    #对测试样本进行预测    def predict(self,x):        if self.f == None:            return self.class_labels[np.argmax(self.label_dist)]        elif x[self.f] <= self.v:            return self.left.predict(x)        else:            return self.right.predict(x)def gini(y):    return  1 - np.square(y.value_counts()/len(y)).sum()def generate(X,y,x_pos,y_pos,nodes,min_leaf_samples,max_depth,layer,class_labels):    current_node = TreeNode(x_pos,y_pos,layer,class_labels)#创建节点对象    current_node.label_dist = [len(y[y==v]) for v in class_labels] #当前节点类样本分布    nodes.append(current_node)    if(len(X) < min_leaf_samples or gini(y) < 0.1 or layer > max_depth): #判断是否需要生成子节点        return current_node    max_gini,best_f,best_v = 0,None,None    for f in X.columns: #特征遍历        for v in X[f].unique(): #取值遍历            y1,y2 = y[X[f] <= v],y[X[f] > v]            if (len(y1) >= min_leaf_samples and len(y2) >= min_leaf_samples):                imp_descent = gini(y) - gini(y1)*len(y1)/len(y) - gini(y2)*len(y2)/len(y) # 计算不纯度变化                if imp_descent > max_gini:                    max_gini,best_f,best_v = imp_descent,f,v    current_node.f,current_node.v = best_f,best_v    if(current_node.f != None):        current_node.left = generate(X[X[best_f] <= best_v],y[X[best_f] <= best_v],x_pos-(2**(max_depth-layer)),y_pos -1,nodes,min_leaf_samples,max_depth,layer + 1,class_labels)        current_node.right = generate(X[X[best_f] > best_v],y[X[best_f] > best_v],x_pos+ (2**(max_depth-layer)),y_pos -1,nodes,min_leaf_samples,max_depth,layer + 1,class_labels)    return current_nodedef decision_tree_classifier(X,y,min_leaf_samples,max_depth):    nodes = []    root = generate(X,y,0,0,nodes,min_leaf_samples=min_leaf_samples,max_depth=max_depth,layer=1,class_labels=y.unique())    return root,nodesroot,nodes = decision_tree_classifier(x_train,y_train,3,5)#生成决策树x_test

x_test.shape[0]

1976

result = []for i in range(x_test.shape[0]):    result.append(root.predict(x_test.iloc[i]))

re1 = [1,1,1,-1,-1,-1]re2 = [1,1,1,-1,-1,1]accuracy_score(re1,re2)

0.8333333333333334

accuracy_score(result, y_test.values)

0.7029352226720648

# 定义决策树模型，传入算法参数DT = DecisionTree(classes=[0,1], features=feature_names, max_depth=5, min_samples_split=10, impurity_t='gini')DT.fit(x_train, y_train) # 在训练集上训练p_test = DT.predict(x_test) # 在测试集上预测，获得预测值print(p_test) # 输出预测值test_acc = accuracy_score(p_test, y_test) # 将测试预测值与测试集标签对比获得准确率print('accuracy: {:.4f}'.format(test_acc)) # 输出准确率

总结

一个完整的机器学习任务包括：确定任务、数据分析、特征工程、数据集划分、模型设计、模型训练和效果测试、结果分析和调优等多个阶段，本案例以英雄联盟游戏胜负预测任务为例，给出了每个阶段的一些简单例子