任务介绍

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

Powered by a@antior.cn

本任务是希望同学们依据注释的要求，对代码中空缺部分进行填写，完成决策树模型的详细实现，根据已有的对局前10分钟特征信息，预测最后获胜方是蓝色方还是红色方，了解执行一个机器学习任务的大致流程，并提交代码和实验报告。第一次作业也是一个机器学习小实验的例子，之后的作业可能不再提供预处理等流程代码，由同学们自己设计实验完成代码编写。

导入工具包

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

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

读入数据

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

  1. csv_data = './data/high_diamond_ranked_10min.csv' # 数据路径
  2. data_df = pd.read_csv(csv_data, sep=',') # 读入csv文件为pandas的DataFrame
  3. data_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之间，等等。

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

增删特征

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

  1. drop_features = ['blueGoldDiff', 'redGoldDiff', 
  2.                  'blueExperienceDiff', 'redExperienceDiff', 
  3.                  'blueCSPerMin', 'redCSPerMin', 
  4.                  'blueGoldPerMin', 'redGoldPerMin'] # 需要舍去的特征列
  5. df = data_df.drop(columns=drop_features) # 舍去特征列
  6. info_names = [c[3:] for c in df.columns if c.startswith('red')] # 取出要作差值的特征名字（除去red前缀）
  7. drop_features = []
  8. for info in info_names: # 对于每个特征名字
  9.     df['br' + info] = df['blue' + info] - df['red' + info] # 构造一个新的特征，由蓝色特征减去红色特征，前缀为br
  10.     drop_features.append('red' + info)
  11. # 其中FirstBlood为首次击杀最多有一只队伍能获得，brFirstBlood=1为蓝，0为没有产生，-1为红
  12. drop_features.extend(['blueFirstBlood','redFirstBlood'])
  13. #print(drop_features)
  14. for c in drop_features:
  15.     print(c)
  16.     try:
  17.         df.drop(columns=c, inplace=True)
  18.     except:
  19.         continue
  20. #df = df.drop(columns=drop_features_red) 
  21. #df = df.drop(columns=['blueFirstBlood', 'redFirstBlood']) # 原有的FirstBlood可删除

重新打印数据

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

特征离散化

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

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

  1. discrete_df = df.copy() # 先复制一份数据
  3. def get_discrete_conf(df):
  4.     Sheet_discrete_list = []
  5.     for c in df.columns: # 遍历每一列特征，跳过标签列(label)
  6.         if c == 'blueWins':
  7.             continue
  8.         Sheet_discrete_list.append([c, get_discrete_conf_c(df, c)])
  9.     Sheet_discrete_dict = dict(Sheet_discrete_list)
  10.     print(Sheet_discrete_dict)
  11.     return Sheet_discrete_dict
  13. def get_discrete_conf_c(df, c, field_num = 5):
  14.     min_ = min(df[c])
  15.     max_ = max(df[c])
  16.     field = []
  17.     action = 1
  18.     normal = 0
  19.     if len(set(list(df[c])))<=5:
  20.         action = 0
  21.         discrete_conf = {
  22.             "action" : action,
  23.             "normal" : normal,
  24.             "min" : min_,
  25.             "max" : max_,
  26.             #"type" : type_,
  27.             "field" : field,
  28.         }
  29.         return discrete_conf
  30.     field = [-500, min(min(df[c]), df.quantile(.25)[c]), max(min(df[c]), df.quantile(.25)[c]), df.quantile(.5)[c], df.quantile(.75)[c]]
  31.     discrete_conf = {
  32.         "action" : action,
  33.         "normal" : normal,
  34.         "min" : min_,
  35.         "max" : max_,
  36.         #"type" : type_,
  37.         "field" : field,
  38.     }
  39.     return discrete_conf
  41. def get_discrete_column(discrete_conf, c, df_c):
  42.     if discrete_conf[c]['action'] == 0:
  43.         return df_c
  44.     values = discrete_conf[c]["field"]
  45.     for i in range(len(df_c)):
  46.         for j in values:
  47.             if df_c[i]>=j:
  48.                 df_c[i] = j
  49.     return df_c
  51. def get_discrete_data(discrete_conf, df):
  52.     for c in df.columns:
  53.         if c not in discrete_conf:
  54.             continue
  55.         discrete_column = get_discrete_column(discrete_conf, c, list(df[c]))
  56.         df[c] = discrete_column
  57.     return df
  59. discrete_conf = get_discrete_conf(df)
  60. discrete_df = get_discrete_data(discrete_conf, df)
  61. print(discrete_df)
  63. #discrete_df.drop(labels='blueWins',axis=1)
  65. '''for c in df.columns[1:]: # 遍历每一列特征，跳过标签列(label)
  66.     print(c)
  67.     print(Sheet_discrete_dict[c])
  68.     for index, row in df.iterrows():
  69.         #print(index)
  70.         #print(row[c])
  71.         tmp = get_discrete_value(Sheet_discrete_dict[c], row[c])
  72.         #print(tmp)
  73.         discrete_df[c][index] = tmp
  76. discrete_df.to_csv('data.csv')'''

数据集准备

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

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

决策树模型的实现

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

  1. # 定义决策树类
  2. from math import log
  3. import operator
  5. def majorityCnt(classList):
  6.     classCount = {}
  7.     for vote in classList:                                        #统计classList中每个元素出现的次数
  8.         if vote not in classCount.keys():
  9.             classCount[vote] = 0
  10.         classCount[vote] += 1
  11.     sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序
  12.     return sortedClassCount[0][0]                                #返回classList中出现次数最多的元素
  14. def splitDataSet(dataSet, axis, value):
  15.     retDataSet = []                                     #创建返回的数据集列表
  16.     for featVec in dataSet:                             #遍历数据集
  17.         if featVec[axis] == value:
  18.             reducedFeatVec = featVec[:axis]             #去掉axis特征
  19.             reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
  20.             retDataSet.append(reducedFeatVec)
  21.     return retDataSet                                   #返回划分后的数据集
  23. def calcShannonEnt(dataSet):
  24.     numEntires = len(dataSet)                        #返回数据集的行数
  25.     labelCounts = {}                                 #保存每个标签(Label)出现次数的字典
  26.     for featVec in dataSet:                          #对每组特征向量进行统计
  27.         currentLabel = featVec[-1]                   #提取标签(Label)信息
  28.         if currentLabel not in labelCounts.keys():   #如果标签(Label)没有放入统计次数的字典,添加进去
  29.             labelCounts[currentLabel] = 0
  30.         labelCounts[currentLabel] += 1               #Label计数
  31.     shannonEnt = 0.0                                 #经验熵(香农熵)
  32.     for key in labelCounts:                          #计算香农熵
  33.         prob = float(labelCounts[key]) / numEntires  #选择该标签(Label)的概率
  34.         shannonEnt -= prob * log(prob, 2)            #利用公式计算
  35.     return shannonEnt                                #返回经验熵(香农熵)
  37. def chooseBestFeatureToSplit(dataSet):
  38.     numFeatures = len(dataSet[0]) - 1                     #特征数量
  39.     baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
  40.     bestInfoGain = 0.0                                    #信息增益
  41.     bestFeature = -1                                      #最优特征的索引值
  42.     for i in range(numFeatures):                          #遍历所有特征
  43.         #获取dataSet的第i个所有特征
  44.         featList = [example[i] for example in dataSet]
  45.         uniqueVals = set(featList)                         #创建set集合{},元素不可重复
  46.         newEntropy = 0.0                                   #经验条件熵
  47.         for value in uniqueVals:                           #计算信息增益
  48.             subDataSet = splitDataSet(dataSet, i, value)           #subDataSet划分后的子集
  49.             #print(subDataSet)
  50.             prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
  51.             newEntropy += prob * calcShannonEnt(subDataSet)        #根据公式计算经验条件熵
  52.         infoGain = baseEntropy - newEntropy                        #信息增益
  53.         #print("第%d个特征的增益为%.3f" % (i, infoGain))             #打印每个特征的信息增益
  54.         if (infoGain > bestInfoGain):                              #计算信息增益
  55.             bestInfoGain = infoGain                                #更新信息增益，找到最大的信息增益
  56.             bestFeature = i                                        #记录信息增益最大的特征的索引值
  57.     return bestFeature                                             #返回信息增益最大的特征的索引值
  59. def traverse_node(inputTree, featLabels, testVec):
  60.     firstStr = next(iter(inputTree))             #获取决策树结点
  61.     secondDict = inputTree[firstStr]             #下一个字典
  62.     featIndex = featLabels.index(firstStr)
  63.     for key in secondDict.keys():
  64.         if testVec[featIndex] == key:
  65.             if type(secondDict[key]).__name__ == 'dict':
  66.                 classLabel = traverse_node(secondDict[key], featLabels, testVec)
  67.             else:
  68.                 classLabel = secondDict[key]
  69.     return classLabel
  72. class DecisionTree(object):
  73.     def __init__(self, classes, features, 
  74.                  max_depth=10, min_samples_split=10,
  75.                  impurity_t='entropy'
  76.                  ):
  77.         '''
  78.         传入一些可能用到的模型参数，也可能不会用到
  79.         classes表示模型分类总共有几类
  80.         features是每个特征的名字，也方便查询总的共特征数
  81.         max_depth表示构建决策树时的最大深度
  82.         min_samples_split表示构建决策树分裂节点时，如果到达该节点的样本数小于该值则不再分裂
  83.         impurity_t表示计算混杂度（不纯度）的计算方式，例如entropy或gini
  84.         '''  
  85.         self.classes = classes
  86.         self.features = features
  87.         self.max_depth = max_depth
  88.         self.min_samples_split = min_samples_split
  89.         self.impurity_t = impurity_t
  90.         self.root = None # 定义根节点，未训练时为空
  93.     '''
  94.     请实现决策树算法，使得fit函数和predict函数可以正常调用，跑通之后的测试代码，
  95.     要求之后测试代码输出的准确率大于0.6。
  97.     提示：
  98.     可以定义额外一些函数，例如
  99.     impurity()用来计算混杂度
  100.     gain()调用impurity用来计算信息增益
  101.     expand_node()训练时递归函数分裂节点，考虑不同情况
  102.         1. 无需分裂 或 达到分裂阈值
  103.         2. 调用gain()找到最佳分裂特征，递归调用expand_node
  104.         3. 找不到有用的分裂特征
  105.         fit函数调用该函数返回根节点
  106.     traverse_node()预测时遍历节点，考虑不同情况
  107.         1. 已经到达叶节点，则返回分类结果
  108.         2. 该特征取值在训练集中未出现过
  109.         3. 依据特征取值进入相应子节点，递归调用traverse_node
  110.     当然也可以有其他实现方式。
  112.     '''
  114.     def fit(self, dataSet, labels, featLabels = []):
  115.         print(len(labels))
  116.         print(len(dataSet[0]))
  117.         print(dataSet[0])
  118.         assert len(labels) == (len(dataSet[0])-1) # 输入数据的特征数目应该和模型定义时的特征数目相同
  119.         classList = [example[-1] for example in dataSet]
  121.         if len(dataSet[0]) <= self.min_samples_split:                                       #遍历完所有特征时返回出现次数最多的类标签
  122.             return majorityCnt(classList)
  123.         if (len(self.features)-len(labels))>=self.max_depth-2:
  124.             return majorityCnt(classList)
  125.         if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分
  126.             return classList[0]
  127.         if len(dataSet[0]) == 1:                                       #遍历完所有特征时返回出现次数最多的类标签
  128.             return majorityCnt(classList)
  129.         bestFeat = chooseBestFeatureToSplit(dataSet)                   #选择最优特征
  130.         bestFeatLabel = labels[bestFeat]                               #最优特征的标签
  131.         featLabels.append(bestFeatLabel)
  132.         myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
  133.         del(labels[bestFeat])                                          #删除已经使用特征标签
  134.         featValues = [example[bestFeat] for example in dataSet]        #得到训练集中所有最优特征的属性值
  135.         uniqueVals = set(featValues)                                   #去掉重复的属性值
  136.         for value in uniqueVals:
  137.             subLabels=labels[:]
  138.             #递归调用函数createTree(),遍历特征，创建决策树。
  139.             myTree[bestFeatLabel][value] = DT.fit(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)
  140.         return myTree
  142.     def predict(self, inputTree, features, dataSet):
  143.         assert len(dataSet.shape) == 1 or len(dataSet.shape) == 2 # 只能是1维或2维
  144.         if len(dataSet.shape) == 1:
  145.             return traverse_node(inputTree, features, dataSet)
  146.         else:
  147.             return np.array([traverse_node(inputTree, features, f) for f in dataSet])
  148.         '''
  149.         预测
  150.         输入feature可以是一个一维numpy数组也可以是一个二维numpy数组
  151.         如果是一维numpy（m）数组则是一个样本，包含m个特征，返回一个类别值
  152.         如果是二维numpy（n*m）数组则表示n个样本，每个样本包含m个特征，返回一个numpy一维数组
  154.         提示：一种可能的实现方式为
  155.         if len(feature.shape) == 1: # 如果是一个样本
  156.             return self.traverse_node(self.root, feature) # 从根节点开始路由
  157.         return np.array([self.traverse_node(self.root, f) for f in feature]) # 如果是很多个样本
  158.         '''
  160. # 定义决策树模型，传入算法参数
  164. DT = DecisionTree(classes=[0,1], features=feature_names.tolist(), max_depth=5, min_samples_split=10, impurity_t='gini')
  167. featLabels = []
  168. #myTree = createTree(dataSet, label, features, featLabels)
  169. #features = feature_names
  170. #print(len(features))
  171. #dataSet = list(x_train)
  172. #print(len(dataSet[0]))
  175. dataSet = np.hstack([np.matrix(x_train), np.matrix(y_train).T])
  176. print(dataSet.shape)
  177. dataSet = dataSet.tolist()
  178. print(len(feature_names))
  181. myTree = DT.fit(dataSet, feature_names.tolist()) # 在训练集上训练
  182. print(myTree)
  186. p_test = DT.predict(myTree, list(feature_names), x_test) # 在测试集上预测，获得预测值
  187. print(p_test) # 输出预测值
  188. #test_acc = accuracy_score(p_test, y_test) # 将测试预测值与测试集标签对比获得准确率
  189. #print('accuracy: {:.4f}'.format(test_acc)) # 输出准确率

模型效果计算

第一次模型测试结果可能不够好，可以先检查调试代码是否有bug，再尝试调整参数或者优化计算方法。

  1. Err = p_test-y_test
  2. ErrNum = 0
  3. for i in range(len(Err)):
  4.     if Err[i] != 0:
  5.         ErrNum = ErrNum + 1
  6. ErrRate = float(ErrNum)/len(Err)
  7. print(ErrRate)
  8. print(1-ErrRate)