课程链接: 清华大学驭风计划

代码仓库：Victor94-king/MachineLearning: MachineLearning basic introduction (github.com)

驭风计划是由清华大学老师教授的，其分为四门课，包括: 机器学习(张敏教授) ， 深度学习(胡晓林教授), 计算机语言(刘知远教授) 以及数据结构与算法(邓俊辉教授)。本人是综合成绩第一名，除了数据结构与算法其他单科均为第一名。代码和报告均为本人自己实现，由于篇幅限制，只展示任务布置以及关键代码，如果需要报告或者代码可以私聊博主

机器学习部分授课老师为张敏教授，主要主要通过介绍决策树，线性回归，贝叶斯模型，SVM算法，K近邻算法，Kmeans算法以及集成学习算法等入门机器学习。

有任何疑问或者问题，也欢迎私信博主，大家可以相互讨论交流哟~~

任务介绍

本次以英雄联盟对局胜负预测任务为基础，要求实现决策树算法相关细节，加深对算法的理解，并了解做机器学习任务的大致流程。

英雄联盟（League of Legends，LoL）是一个多人在线竞技游戏，由拳头游戏（Riot Games）公司出品。在游戏中，每位玩家控制一位有独特技能的英雄，红蓝两支队伍各有五位玩家进行对战，目标是摧毁对方的基地水晶。水晶有多座防御塔保护，通常需要先摧毁一些防御塔再摧毁水晶。玩家所控制的英雄起初非常弱，需要不断击杀小兵、野怪和对方英雄来获得金币、经验。经验可以提升英雄等级和技能等级，金币可以用来购买装备提升攻击、防御等属性。对战过程中一般没有己方单位在附近的地点是没有视野的，即无法看到对面单位，双方可以通过使用守卫来监视某个地点，洞察对面走向、制定战术。

本数据集来自Kaggle，包含了9879场钻一到大师段位的单双排对局，对局双方几乎是同一水平。每条数据是前10分钟的对局情况，每支队伍有19个特征，红蓝双方共38个特征。这些特征包括英雄击杀、死亡，金钱、经验、等级情况等等。一局游戏一般会持续30至40分钟，但是实际前10分钟的局面很大程度上影响了之后胜负的走向。作为最成功的电子竞技游戏之一，对局数据、选手数据的量化与研究具有重要意义，可以启发游戏将来的发展和改进。

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

报告

核心代码

决策树的实现

# 定义决策树类
class DecisionTree(object):def __init__(self, classes, features, max_depth=10, min_samples_split=10,impurity_t='entropy'):'''传入一些可能用到的模型参数，也可能不会用到classes表示模型分类总共有几类features是每个特征的名字，也方便查询总的共特征数max_depth表示构建决策树时的最大深度min_samples_split表示构建决策树分裂节点时，如果到达该节点的样本数小于该值则不再分裂impurity_t表示计算混杂度（不纯度）的计算方式，例如entropy或gini'''  self.classes = classesself.features = featuresself.max_depth = max_depthself.min_samples_split = min_samples_splitself.impurity_t = impurity_tself.root = None # 定义根节点，未训练时为空'''请实现决策树算法，使得fit函数和predict函数可以正常调用，跑通之后的测试代码，要求之后测试代码输出的准确率大于0.6。提示：可以定义额外一些函数，例如impurity()用来计算混杂度gain()调用impurity用来计算信息增益expand_node()训练时递归函数分裂节点，考虑不同情况1. 无需分裂 或 达到分裂阈值2. 调用gain()找到最佳分裂特征，递归调用expand_node3. 找不到有用的分裂特征fit函数调用该函数返回根节点traverse_node()预测时遍历节点，考虑不同情况1. 已经到达叶节点，则返回分类结果2. 该特征取值在训练集中未出现过3. 依据特征取值进入相应子节点，递归调用traverse_node当然也可以有其他实现方式。'''def count_lable(self, lable):#为了不改变全局的lable的数据类型，在这里将其转换成Series 调用value_counts()函数lable = pd.Series(lable)return lable.value_counts()def impurity (self , lable):'输入对应的lable计算混杂度'number = len(lable) counts = self.count_lable(lable)possible = np.array([i / number for i in counts]) #计算每个count各自对应的pif self.impurity_t  == "entropy": return np.sum(-np.multiply(possible , np.log2(possible)))elif self.impurity_t == 'gini':return 1 - np.sum(np.power(possible , 2))def gain(self , features , lable):# '计算信息收益，并返回收益最大的特征列'feature_num     = features.shape[1]imputiry_start  = self.impurity(lable) #混杂度的初始值max_gain =  0for i in range(feature_num): ## 遍历m次特征feature_list = np.vstack((features[:,i],lable)).T   #第i特征与lable 进行拼接choices = np.unique(features[:,i]) # 特征的选择范围,返回一个列表feature_gain_impurity = 0 #初始化特征的混杂度for choice in choices: #对每一个选择，找到对应的标签以及对应的商choice_list = feature_list[feature_list[:,0] == choice]# 将choice_list的lable列输入计算得每个choice下的混乱度值feature_gain_impurity += (self.impurity(choice_list[:,1])*len(choice_list)) / len(lable)temp_gain = imputiry_start - feature_gain_impurity #每个特征的信息增益if temp_gain > max_gain:max_gain = temp_gain feature_index = ireturn feature_indexdef splitDataSet(self , features , feature_index, value , lable):"""作用是为了对于feature_index列值为value值的lable 作为子lable 返回,features 删除feature_indexs 返回在递归中，通过传入特征矩阵，对应的特征,查找特征的值，以及标签,返回的是删除已经用于生成树模型的特征以及标签，特征:其实直接删了features[feature_index]就可以，lable:删除在特征列等于value的lable就可以"""# lable (7903,) 需要转变成(7903,1) 才能拼接lable = lable.reshape(len(lable),1)features_temp = np.hstack((features,lable)) #返回一个带标签的特征矩阵subs = features_temp[features[:,feature_index] == value]  # 利用np的布尔索引sub_labels     = subs[:,-1]subs_features  = subs[: , :-1]subs_features = np.delete(subs_features, feature_index, axis=1) #删除feature_index列return  sub_labels , subs_features def expand_node(self, features , lable , depth):#情况1: 无需分裂 or 到达阈值直接返回样本最多的值majority_feature = self.count_lable(lable)#print(majority_feature.index[0])if len(majority_feature) == 1: #样本标签唯一return lable[0]if len(features)  <= self.min_samples_split:  # 样本个数小于阈值return majority_feature.index[0] if depth >= self.max_depth: #深度超过maxreturn majority_feature.index[0]if np.unique(features).shape[0] == features.shape[0] and len(majority_feature) != 1: print('所有样本的属性值一样但对应的标签不一致') #此处需要考虑噪声和未考虑全的特征print(depth)# 返回最大信息熵的特征的index,用于分裂feature_index = self.gain(features, lable)  #找到特征的属性值可能选项unique_values = np.unique(features[:,feature_index])#核心递归：构建一个嵌套字典结构{特征index:{value = {submytree }}}},对不同的value进行递归遍历myTree = { feature_index:{} }  # tree for value in unique_values:#新建一个splitDataSet 函数：传入特征矩阵, 最优的节点，寻找的值，标签 sublabels , subfeatures  = self.splitDataSet(features , feature_index, value , lable)#subfeatures = np.delete(features ,feature_index , axis = 1) myTree[feature_index][value] = self.expand_node(subfeatures , sublabels, depth = depth + 1)return myTreedef fit(self, feature, label):assert len(self.features) == len(feature[0]) # 输入数据的特征数目应该和模型定义时的特征数目相同'''训练模型feature为二维numpy(n*m)数组,每行表示一个样本,有m个特征label为一维numpy(n)数组，表示每个样本的分类标签提示：一种可能的实现方式为self.root = self.expand_node(feature, label, depth=1) # 从根节点开始分裂，模型记录根节点'''self.root = self.expand_node(feature, label, depth=1)def predict(self, feature):assert len(feature.shape) == 1 or len(feature.shape) == 2 # 只能是1维或2维'''预测输入feature可以是一个一维numpy数组也可以是一个二维numpy数组如果是一维numpy(m)数组则是一个样本,包含m个特征,返回一个类别值如果是二维numpy(n*m)数组则表示n个样本,每个样本包含m个特征,返回一个numpy一维数组提示：一种可能的实现方式为if len(feature.shape) == 1: # 如果是一个样本return self.traverse_node(self.root, feature) # 从根节点开始路由return np.array([self.traverse_node(self.root, f) for f in feature]) # 如果是很多个样本'''if len(feature.shape) == 1:  # 如果是一个样本return self.traverse_node(self.root, feature)  # 从根节点开始路由return np.array([self.traverse_node(self.root , single_feature) for single_feature in feature])  # 如果是很多个样本def traverse_node(self,node,feature):""" traverse_node()预测时遍历节点，考虑不同情况1. 已经到达叶节点，则返回分类结果2. 该特征取值在训练集中未出现过3. 依据特征取值进入相应子节点，递归调用traverse_node传入的是单个特征，返回的应该是预测的1/0"""#print(node)feature_index = [name for name in node.keys()][0] #找到每个节点的特征index,之后需要删除掉values = [value for value in node[feature_index].keys()] #所有取值的可能集合if feature[feature_index] not in values: feature[feature_index] = values[np.random.choice(len(values))] #未取过的值取在取值集合里随机取值if node[feature_index][feature[feature_index]] in self.classes :  # 到达叶节点return(node[feature_index][feature[feature_index]])subfeature = np.delete(feature,feature_index,axis=0) #删除已经用于查找的特征#print(subfeature.shape)return self.traverse_node(node[feature_index][feature[feature_index]],subfeature) # 如果是子叶节点，递归

总结

步骤:

1. 读取数据，观察并分析数据。看有无特征是否有线性关系，有无缺失的数据，缺失的数据可以进行填充/取均值等方式

2. 数据处理。由于决策树主要还是解决一些离散数据，所以需要利用qcut/cut函数进行离散化，将数据集映射到比较选值范围比较少的区间内，便于生成树，也避免了后期树优先选择范围较多的节点

3. 准备数据集(training/validation/testing):采用随机的方式，需要保证几个数据集没有重合的部分

4. 决策树类的构建：

   一）构造函数：可以输入一些决策树的属性,eg:最大深度，最大阈值，最小样本数量，混杂度，输出结果的范围，特征名等

   二）定义树的训练函数fit(feature , lable):从跟节点开始生长，返回值是一个多层的树结构(嵌套字典)并记录下来

   *三）定义根的生长函数expand_node(feature , lable , depth):这个函数是一个核心部分，递归。

   四) 定义最优节点取值index函数gain(feature,lable)

   五) 定义splitDataSet(feature,lable,feature_index,value)

   六) 定义辅助函数：包括计算混杂度函数，以及由于传入的lable是np.array没有value_counts()方法可以自己定义

   七) 定义预测函数prdict(feature):单独遍历feature里每一行(样本)的特征，返回的所有值作为行向量输出

   *八) 定义预测单数据的函数traverse_node(node,single_sample_feature)

5. 训练模型 -> 验证集上调整超参数/后剪枝叶 -> 得到测试集正确率

***) 难点：

1. (7932,)与(7932,1)是不一样的前者是行向量后者为列向量，但可以通过reshape后再进行数组拼接
2. 利用qcut函数将其等分，discrete_df[c].rank(method=“first”)是为了去重，qcut函数中不允许重复值切分。之后可以使用cut函数
3. 对于一些超参数的调整:由于决策树的特殊原因，始终可以让训练集上的正确率不断增加，但需要考虑过拟合的风险，在max_depth设成10层的时候，训练集的正确率高达80%但是测试集却下降到了60%