网站侧边栏导航,wordpress 报名插件,网页游戏网站那个好,微信网站建设需要那些资料在计算机科学中#xff0c;树是一种很重要的数据结构#xff0c;比如我们最为熟悉的二叉查找树#xff08;Binary Search Tree#xff09;#xff0c;红黑树#xff08;Red-Black Tree#xff09;等#xff0c;通过引入树这种数据结构#xff0c;我们可以很快地缩小问… 在计算机科学中树是一种很重要的数据结构比如我们最为熟悉的二叉查找树Binary Search Tree红黑树Red-Black Tree等通过引入树这种数据结构我们可以很快地缩小问题规模实现高效的查找。在监督学习中面对样本中复杂多样的特征选取什么样的策略可以实现较高的学习效率和较好的分类效果一直是科学家们探索的目标。那么树这种结构到底可以如何用于机器学习中呢我们先从一个游戏开始。我们应该都玩过或者听过这么一种游戏游戏中出题者写下一个明星的名字其他人需要猜出这个人是谁。当然如果游戏规则仅此而已的话几乎是无法猜出来的因为问题的规模太大了。为了降低游戏的难度答题者可以向出题者问问题而出题者必须准确回答是或者否答题者依据回答提出下一个问题如果能够在指定次数内确定谜底即为胜出。加入了问答规则之后我们是否有可能猜出谜底呢我们先实验一下现在我已经写下了一个影视明星的名字而你和我的问答记录如下是男的吗Y是亚洲人吗Y是中国人吗N是印度人吗Y ……虽然只有短短四个问题但是我们已经把答案的范围大大缩小了那么接下第5个问题你应该如何问呢我相信你应该基本可以锁定答案了因为我看过的印度电影就那么几部。我们将上面的信息结构化如下图所示在上面的游戏中我们针对性的提出问题每一个问题都可以将我们的答案范围缩小在提问中和回答者有相同知识背景的前提下得出答案的难度比我们想象的要小很多。回到我们最初的问题中如何将树结构用于机器学习中结合上面的图我们可以看出在每一个节点依据问题答案可以将答案划分为左右两个分支左分支代表的是Yes右分支代表的是No虽然为了简化我们只画出了其中的一条路径但是也可以明显看出这是一个树形结构这便是决策树的原型。1.决策树算法简介我们面对的样本通常具有很多个特征正所谓对事物的判断不能只从一个角度那如何结合不同的特征呢决策树算法的思想是先从一个特征入手就如同我们上面的游戏中一样既然无法直接分类那就先根据一个特征进行分类虽然分类结果达不到理想效果但是通过这次分类我们的问题规模变小了同时分类后的子集相比原来的样本集更加易于分类了。然后针对上一次分类后的样本子集重复这个过程。在理想的情况下经过多层的决策分类我们将得到完全纯净的子集也就是每一个子集中的样本都属于同一个分类。比如上图中平面坐标中的六个点我们无法通过其x坐标或者y坐标直接就将两类点分开。采用决策树算法思想我们先依据y坐标将六个点划分为两个子类如水平线所示水平线上面的两个点是同一个分类但是水平线之下的四个点是不纯净的。但是没关系我们对这四个点进行再次分类这次我们以x左边分类见图中的竖线通过两层分类我们实现了对样本点的完全分类。这样我们的决策树的伪代码实现如下if y a: output dotelse: if x b: output cross else: output dot由这个分类的过程形成一个树形的判决模型树的每一个非叶子节点都是一个特征分割点叶子节点是最终的决策分类。如下图所示将新样本输入决策树进行判决时就是将样本在决策树上自顶向下依据决策树的节点规则进行遍历最终落入的叶子节点就是该样本所属的分类。2.决策树算法流程上面我们介绍决策树算法的思想可以简单归纳为如下两点每次选择其中一个特征对样本集进行分类对分类后的子集递归进行步骤1看起来是不是也太简单了呢实际上每一个步骤我们还有很多考虑的。在第一个步骤中我们需要考虑的一个最重要的策略是选取什么样的特征可以实现最好的分类效果而所谓的分类效果好坏必然也需要一个评价的指标。在上文中我们都用纯净来说明分类效果好那何为纯净呢直观来说就是集合中样本所属类别比较集中最理想的是样本都属于同一个分类。样本集的纯度可以用熵来进行衡量。在信息论中熵代表了一个系统的混乱程度熵越大说明我们的数据集纯度越低当我们的数据集都是同一个类别的时候熵为0熵的计算公式如下其中P(xi)表示概率b在此处取2。比如抛硬币的时候正面的概率就是1/2反面的概率也是1/2那么这个过程的熵为可见由于抛硬币是一个完全随机事件其结果正面和反面是等概率的所以具有很高的熵。假如我们观察的是硬币最终飞行的方向那么硬币最后往下落的概率是1往天上飞的概率是0带入上面的公式中可以得到这个过程的熵为0所以熵越小结果的可预测性就越强。在决策树的生成过程中我们的目标就是要划分后的子集中其熵最小这样后续的的迭代中就更容易对其进行分类。既然是递归过程那么就需要制定递归的停止规则。在两种情况下我们停止进一步对子集进行划分其一是划分已经达到可以理想效果了另外一种就是进一步划分收效甚微不值得再继续了。用专业术语总结终止条件有以下几个子集的熵达到阈值子集规模够小进一步划分的增益小于阈值其中条件3中的增益代表的是一次划分对数据纯度的提升效果也就是划分以后熵减少越多说明增益越大那么这次划分也就越有价值增益的计算公式如下Gain上述公式可以理解为计算这次划分之后两个子集的熵之和相对划分之前的熵减少了多少需要注意的是计算子集的熵之和需要乘上各个子集的权重权重的计算方法是子集的规模占分割前父集的比重比如划分前熵为e划分为子集A和B大小分别为m和n熵分别为e1和e2那么增益就是e - m/(m n) * e1 - n/(m n) * e2。3. 决策树算法实现有了上述概念我们就可以开始开始决策树的训练了训练过程分为选取特征分割样本集计算增益如果增益够大将分割后的样本集作为决策树的子节点否则停止分割递归执行上两步上述步骤是依照ID3的算法思想依据信息增益进行特征选取和分裂除此之外还有C4.5以及CART等决策树算法。算法框架如下class DecisionTree(object): def fit(self, X, y): # 依据输入样本生成决策树 self.root self._build_tree(X, y) def _build_tree(self, X, y, current_depth0): #1. 选取最佳分割特征生成左右节点 #2. 针对左右节点递归生成子树 def predict_value(self, x, treeNone): # 将输入样本传入决策树中自顶向下进行判定 # 到达叶子节点即为预测值在上述代码中实现决策树的关键是递归构造子树的过程为了实现这个过程我们需要做好三件事分别是节点的定义最佳分割特征的选择递归生成子树。3.1 节点定义决策树的目的是用于分类预测即各个节点需要选取输入样本的特征进行规则判定最终决定样本归属到哪一棵子树基于这个目的决策树的每一个节点需要包含以下几个关键信息判决特征当前节点针对哪一个特征进行判决判决规则对于二类问题这个规则一般是一个布尔表达式左子树判决为TRUE的样本右子树判决为FALSE的样本决策树节点的定义代码如下所示class DecisionNode(): def __init__(self, feature_iNone, thresholdNone, valueNone, true_branchNone, false_branchNone): self.feature_i feature_i # 用于测试的特征对应的索引 self.threshold threshold # 判断规则threshold为true self.value value # 如果是叶子节点用于保存预测结果 self.true_branch true_branch # 左子树 self.false_branch false_branch # 右子树3.2 特征选取特征选取是构造决策树最关键的步骤其目的是选出能够实现分割结果最纯净的那个特征其操作流程的代码如下# 遍历样本集中的所有特征针对每一个特征计算最佳分割点# 再选取最佳的分割特征for feature_i in range(n_features): # 遍历集合中某个特征的所有取值 for threshold in unique_values: # 以当前特征值作为阈值进行分割 Xy1, Xy2 divide_on_feature(X_y, feature_i, threshold) # 计算分割后的增益 gain gain(y, y1, y2) # 记录最佳分割特征最佳分割阈值 if gain largest_gain: largest_gain gain best_criteria { feature_i: feature_i, threshold: threshold }3.3 节点分裂节点分裂的时候有两条处理分支如果增益够大就分裂为左右子树如果增益很小就停止分裂将这个节点直接作为叶子节点。节点分裂和Gain分割后增益的计算可以做一个优化在上一个步骤中我们寻找最优分割点的时候其实就可以将最佳分裂子集和Gain计算并保存下来将上一步中的for循环改写为# 以当前特征值作为阈值进行分割Xy1, Xy2 divide_on_feature(X_y, feature_i, threshold)# 计算分割后的熵gain gain(y, y1, y2)# 记录最佳分割特征最佳分割阈值if gain largest_gain: largest_gain gain best_criteria { feature_i: feature_i, threshold: threshold , } best_sets { left: Xy1, right: Xy2, gain: gain }为了防止过拟合需要设置合适的停止条件比如设置Gain的阈值如果Gain比较小就没有必要继续进行分割所以接下来我们就可以依据gain来决定分割策略if best_sets[gain] MIN_GAIN: # 对best_sets[left]进一步构造子树并作为父节点的左子树 # 对best_sets[right]进一步构造子树并作为父节点的右子树 ...else: # 直接将父节点作为叶子节点 ...下面我们结合一组实验数据来学习决策树的训练方法。实验数据来源于这里下表中的数据是一组消费调查结果我们训练决策树的目的就是构造一个分类算法使得有新的用户数据时我们依据训练结果去推断一个用户是否购买这个商品AGEEDUCATIONINCOMEMARITAL STATUSPURCHASE?36-55master’shighsingleyes18-35high schoollowsingleno36-55master’slowsingleyes18-35bachelor’shighsingleno 18high schoollowsingleyes18-35bachelor’shighmarriedno36-55bachelor’slowmarriedno 55bachelor’shighsingleyes36-55master’slowmarriedno 55master’slowmarriedyes36-55master’shighsingleyes 55master’shighsingleyes18high schoolhighsingleno36-55master’slowsingleyes36-55high schoollowsingleyes 18high schoollowmarriedyes18-35bachelor’shighmarriedno 55high schoolhighmarriedyes 55bachelor’slowsingleyes36-55high schoolhighmarriedno从表中可以看出我们一共有20组调查样本每一组样本包含四个特征分别是年龄段学历收入婚姻状况而最后一列是所属分类在这个问题中就代表是否购买了该产品。监督学习就是在每一个样本都有正确答案的前提下用算法预测结果然后根据预测情况的好坏调整算法参数。在决策树中预测的过程就是依据各个特征划分样本集评价预测结果的好坏标准是划分结果的纯度。为了方便处理我们对样本数据进行了简化将年龄特征按照样本的特点转化为离散的数据比如小于18对应018对应118-35对应236-55对应3大于55对应4以此类推同样其他的特征也一样最数字化处理教育水平分别映射为0(hight school)1(bachelor’s)2(master’s)收入映射为0(low)和1(hight), 婚姻状况同样映射为0(single), 1(married)最终处理后的样本放到一个numpy矩阵中如下所示X_y np.array( [[3, 2, 1, 0, 1], [2, 0, 0, 0, 0], [3, 2, 0, 0, 1], [2, 1, 1, 0, 0], [0, 0, 0, 0, 1], [2, 1, 1, 1, 0], [3, 1, 0, 1, 0], [4, 1, 1, 0, 1], [3, 2, 0, 1, 0], [4, 2, 0, 1, 1], [3, 2, 1, 0, 1], [4, 2, 1, 0, 1], [1, 0, 1, 0, 0], [3, 2, 0, 0, 1], [3, 0, 0, 0, 1], [0, 0, 0, 1, 1], [2, 1, 1, 1, 0], [4, 0, 1, 1, 1], [4, 1, 0, 0, 1], [3, 0, 1, 1, 0]] )4. 新样本预测依照上面的算法构造决策树我们将决策树打印出来如下所示-- Classification Tree --0 : 4? T - 1 F - 3 : 1? T - 0 : 2? T - 0 F - 1 F - 0 : 3? T - 1 F - 0 : 1? T - 0 F - 1其中冒号前代表选择的分割特征冒号后面代表判别规则二者组合起来就是一个决策树的非叶子节点每个非叶子节点进一步分割为分为True和False分支对于叶子节点箭头后面表示最终分类0表示不购买1表示购买。由于我们的数据做过简化所以上述结果不太直观我们将对应的特征以及判断规则翻译一下年龄 : 大于55? 是 - 购买 否 - 收入 : 高? 是 - 年龄 : 大于18? 是 - 不购买 否 - 购买 否 - 年龄 : 大于36? 是 - 购买 否 - 年龄 : 大于等于18? 是 - 不购买 否 - 购买决策树构造完之后我们就可以用来进行新样本的分类了。决策树的预测过程十分容易理解只需要将从根节点开始按照节点定义的规则进行判决选择对应的子树并重复这个过程直到叶子节点即可。决策树的预测功能实现代码如下def predict_value(self, x, treeNone): # 如果当前节点是叶子节点直接输出其值 if tree.value is not None: return tree.value # 否则将x按照当前节点的规则进行判决 # 如果判决为true选择左子树否则选择右子树 feature_value x[tree.feature_i] if feature_value tree.threshold: branch tree.true_branch else: branch tree.false_branch # 在选中的子树上递归进行判断 return self.predict_value(x, branch)5. 总结决策树是一种简单常用的分类器通过训练好的决策树可以实现对未知的数据进行高效分类。从我们的例子中也可以看出决策树模型具有较好的可读性和描述性有助于辅助人工分析此外决策树的分类效率高一次构建后可以反复使用而且每一次预测的计算次数不超过决策树的深度。当然决策树也有其缺点。对于连续的特征比较难以处理对于多分类问题计算量和准确率都不理想。此外在实际应用中由于其最底层叶子节点是通过父节点中的单一规则生成的所以通过手动修改样本特征比较容易欺骗分类器比如在拦击邮件识别系统中用户可能通过修改某一个关键特征就可以骗过垃圾邮件识别系统。从实现上来讲由于树的生成采用的是递归随着样本规模的增大计算量以及内存消耗会变得越来越大。此外过拟合也是决策树面临的一个问题完全训练的决策树(未进行剪纸未限制Gain的阈值)能够100%准确地预测训练样本因为其是对训练样本的完全拟合但是对与训练样本以外的样本其预测效果可能会不理想这就是过拟合。解决决策树的过拟合除了上文说到的通过设置Gain的阈值作为停止条件之外通常还需要对决策树进行剪枝常用的剪枝策略有Pessimistic Error Pruning悲观错误剪枝Minimum Error Pruning最小误差剪枝Cost-Complexity Pruning代价复杂剪枝 Error-Based Pruning基于错误的剪枝即对每一个节点都用一组测试数据集进行测试如果分裂之后能够降低错误率再继续分裂为两棵子树否则直接作为叶子节点。Critical Value Pruning关键值剪枝这就是上文中提到的设置Gain的阈值作为停止条件。我们以最简单的方式展示了ID3决策树的实现方式如果想要了解不同类型的决策树的差别可以参考(https://www.quora.com/What-are-the-differences-between-ID3-C4-5-and-CART)。另外关于各种机器学习算法的实现强烈推荐参考Github仓库ML-From-Scratch下载代码之后通过pip install -r requirements.txt安装依赖库即可运行代码。来源 ZPPennywww.jianshu.com/p/c4d0837e9439
