算法动态展示网站
 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
 树中任意节点具有孩子的数目，成为度。
 节点含孩子数目无限制的树成为广义树， general tree。
 树的平衡
 对于一棵树，如果树的所有叶子都位于同一层或者相差不超过一层。
 完全树
 树是平衡的，且底层所有叶子都位于树的左边，认为树是完全的。
 满树
 如果n元树所有的叶子都位于同一层且每个结点要么是叶子结点要么具有n个孩子，则称此树是满的。
 一般而言，含有m个元素的平衡n元树高度为lognm.
 
遍历
 
前序
 中序
 后序
 层序：创建结点队列，创建结果list，将根节点入队列，while(节点队列不为空){
 节点队列出队，当节点不为空，加入list，并将节点子女入队列，否则，加入空到结果列表中。
 }
 
对于表达式树
 
递归
 
public int evaluate(BinaryTreenode root){
int result, op1, op2;
if(root==null)
{
	result=0;
}
else{
	ExpressionTreeOp result=root.getElement();
	if(result.isOperator())
	{
	op1=evaluate(root.getLeft());
	op2=evaluate(root.getRight());
	result=Comput(temp.getOperator,op1,op2);
	}
else{
	result=temp.getValue();
}
	return result;
}
}
 
二叉搜索树
 
在二叉搜索树中：
 
   ① 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值；

   ② 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值；

   ③ 任意结点的左、右子树也分别为二叉搜索树。
 
插入一个节点
 1 看是否为空，为空成为根节点
 2. 不为空与根节点比较，比其小，根节点是否有左孩子，没有，插入
 3. 根节点有左孩子，递归，新的函数，传入element与根节点的左孩子，继续比较。
 
二叉搜索树中删除一个元素还不会
 
标注一下好难啊
 
AVL树
 
是由GM Adelson - Velsky和EM Landis于1962年发明的。为了纪念其发明者，这树结构被命名为AVL。
 AVL树可以定义为高度平衡二叉搜索树，其中每个节点与平衡因子相关联，该平衡因子通过从其左子树的子树中减去其右子树的高度来计算。
 如果每个节点的平衡因子在-1到1之间，则称树是平衡的，否则，树将是不平衡的并且需要平衡。
 平衡系数(k)=高度(左(k)) - 高度(右(k))
 如果任何节点的平衡因子为1，则意味着左子树比右子树高一级。如果任何节点的平衡因子为0，则意味着左子树和右子树包含相等的高度。如果任何节点的平衡因子是-1，则意味着左子树比右子树低一级。
 AVL树如下图所示。
 
 
堆
 
堆是一个完全二叉树，其中每一个节点都小雨或等于他的两个孩子
 最大堆：节点大于等于左右孩子
 最小堆：节点小于等于左右孩子。
 addElement: 先添加到最后，再向上与父元素进行兑换。
 removeMin:移除
 
Set
 
Map
 
containsKey()
 containsValue()
 get(key)
 put(key,value)
 
B 树 B+树
 
2-3查找树
 每个节点2个孩子（2节点）或3个孩子（3节点）
 2节点要么没有孩子，要么两个孩子，2节点只有一个元素
 3节点要么灭有孩子，要么三个孩子，3节点有2个元素，三个孩子分别是小于最小元素，大于最小小于大的，和大于大的
 对于这种树
 仍然是左小右大。
 2-3树插入删除操作，由于时间原因，仅仅只实现了插入操作。
 2-3树插入操作，分三类。
 1.在头节点插入这个可以直接生成一个二节点容纳就行。
 2.插入的是一个二节点直接将二节点升级成为三节点，保留原本的节点连接信息就ok了。
 3.插入的是三节点：虽然别人分了很多种情况，但他们都有一个本质，就是如果待插入位置如果是三节点那么就分解它，向上抛掷，如果上面也是三节点，那么仍然需要拆解，向上抛掷，…等到如果抛掷到头节点，如果头节点也是三节点那么说明，这个树高度不够存放这个结构，就需要分解头节点终止操作增加树的高度。因为在往上没有节点可以执行操作。
 那好我们假定我们记录的数据是1，2，3，4，5，6，7，8，9不失一般性，就从1开始按顺序插入模拟程序运行。
 原文：https://blog.csdn.net/qq_41657315/article/details/80571893
 
 
F 比e大，且e是一个点，插入，a比b小，先插入，发现是三个点，然后分裂，中间的b上去。
 

 
 按大小插入，达到3个之后就进行分裂，中间的上去。
 
** 2-4树**
 一个节点包含3个元素（4节点）要么没有孩子要么四个孩子
 
图
 
遍历：
 广度优先
 深度优先
 最小生成树：
 prim: 加点法：选择一个点，他周围最小的边对应的点加入，这个点和新加入的点构成新的集合，再选择他们周围最小的边，对应的节点加入。
 krustal ：加边法：选择最小的边依次加入 ，只要不成环即可。

1.本门课的作用（JavaScript的作用）所有基于Web的程序开发基础
 
2.一种计算机客户端脚本语言，主要在Web浏览器解释执行。
 
3.浏览器中Javascript，用于与用户交互，以及实现页面中各种动态特效
 
4.在HTML文件中，任何JavaScript代码必须放到<script>标签中
 
5.把JavaScript代码放到外部文件中，在HTML代码中直接引入该文件(外部文件定义为：*.js)
 
 
6.就算语法特点：
 
– 类C语言
 
– 弱类型：变量的数据类型可以任意转换
 
7. • 单行注释：//
 
  • 多行注释：/* */
 
8.JavaScript中5种内置数据类型：Number、String、Boolean、Undefined、Null
 
9. 获得变量在某一时刻的数据类型，使用typeof运算符
 
10. 转换为Number类型：parseInt()、parseFloat()
 
– 转换为String类型：原变量 + ‘’
 
– 转换为Boolean类型：变量之前加 !!
 
 
11. ==：值相等则为true
 
– ===：类型和值都须相同则为true
 
12.CSS选择器的作用：选择具有一定特征的元素，应用某一种样式
 
13.选择器就是一些公用的代码段
 
14.函数：完成特定功能的一段代码
 
– 可重用性
 
– 任务分解
 
函数的要素：函数名、函数参数、函数返回值
16.•JS中函数分类：
 
– JS内置函数：如parseInt( )、eval( )、alert( )、
 
– 自定义函数
 
使用function关键字定义函数
调用方式
– 直接调用  --通过事件触发
 
19.在函数体内，形参其实就是一个变量，函数调用时，一方面可以通过参数向函数传递
 
数据，另一方面也可以从函数获取数据。
 
return语句不带表达式时仍会返回值，该值为Undefined
在一个函数定义的函数体语句中出现对另一个函数的调用，这就是函数的嵌套调用
事件：能被JavaScript检测到的活动
– 用户动作（鼠标或键盘操作等）
 
– 状态变化（加载、改变文本框内容等）
 
常用事件类型
—页面加载事件 —图片事件 —表单事件 —键盘和鼠标事件
 
24.获得字符串的长度
 
– 通过字符串变量的length属性获得
 
25.根据位置截取一段子串
 
– 通过字符串变量的substr()方法
 
参数1：截取的开始位置
 
参数2：截取的长度
 
26.查找子串
 
– indexOf()方法，参数：要查找的子串
 
字符串定义： 单引号或双引号定义
字符串常用操作：
 
– 字符串长度：length属性
 
– 截取子串：substr( )方法
 
– 查找子串：indexOf( )方法
 
– 字符串连接运算符： + +=
 
数组用来在单独的变量中存储一系列的值
定义数组：
 
– 方式一：通过[ ]方式
 
例：var arr1 = [‘a’,‘b’,‘c’];
 
– 方式二：通过new Array方式
 
var arr2 =new Array(‘a’,‘b’,‘c’);
 
JavaScript：是一门基于对象的语言， 对象具有一些属性和行为
属性：
 
– 通过变量来表示
 
行为
 
– 通过函数来实现
 
30. 访问对象属性/方法
 
– 方式一：通过 对象名 . 属性名 、对象名 . 方法名( )
 
– 方式二：通过 对象名[“属性名” ]
 
 修改对象属性
 
– 直接赋值给对象属性
 
31.删除对象属性
 
– 使用delete关键字
 
构造函数的形参用于赋给对象的属性
在构造函数中，使用this指代对象
对象的属性和方法必须通过this访问
通过new 关键字来通过构造函数创建对象
JavaScript包含的对象
– 自定义对象
 
– 内置对象
 
– 浏览器对象（BOM）
 
– 文档对象（DOM）
 
String对象处理字符串相关操作
– 获取字符长度
 
– 判断子串位置
 
– 截取子串
 
 
Array对象的使用
 
常用操作
 
– 获取数组长度
 
– 向数组末尾增加元素
 
– 从数组末尾获取元素
 
 
Math对象的使用
 
常用操作
 
– 四舍五入：Math. round( )
 
– 向下取整：Math.floor( )
 
– 生成随机数：Math.random( )
 
– 取到最大值：Math.max( )
 
– 取到最小值：Math.min( )
 
Date对象的使用
 
Date对象包含了一系列的日期时间处理的功能
 
– 创建Date对象，例： var now= new Date( );
 
•常用操作
 
– 获取当前日期时间： toLocaleString( )
 
– 获取年份、月份、日期：getFullYear()、 getMonth()、getDate()
 
– 获取小时、分钟、秒钟： getHours()、 getMinutes()、getSeconds()
 
JavaScript的对象就是一些属性和方法的集合
属性的实质是一些数据，在程序中用变量保存
方法的实质是一些行为，在程序中用函数实现
创建对象，使用{ } ，括号内部为属性名：属性值或方法名：方
法体，属性和属性间用逗号分隔
 
通过.符号访问对象中的属性或方法，通过[ ]访问对象中的属性或方法
BOM作用：•弹出窗口•计数器•自动跳转页面•获得浏览器信息•图片切换
44.BOM综述
 
BrowserObject浏览器提供的用户与浏览器窗口之间交互的对象及操作的接口。
 
Model 这些对象并不是独立存在的，对象与对象之间存在着层次结构，对象模型的作用就是描述这些层次结构。
 
弹出提示窗口alert();例：window.alert(‘你确定要关闭此窗口吗？’);
  弹出确认窗口 confirm()； 例：window.confirm(‘你确定要关闭此窗口吗？’);
 
  弹出输入框 prompt()； 例：window.prompt(‘请输入你的评价, 1(满意) 2(一般)’);
 
  延迟执行 setTimeout()； – setTimeout( code , millisec )
 
           clearTimeout() – clearTimeout( id_of_settimeout )
 
  定时执行 setInterval() – setInterval( code , millisec ）;
 
           clearInterval() – clearInterval( id_of_setinterval
 
  打开/关闭窗口  open () ; close();
 
使用document对象 常用方法：document.write()
  子对象
 
– forms
 
– images
 
– links
 
– anchors
 
– location
 
   使用history对象 history对象可以访问浏览器窗口的浏览历史
 
子对象
 
-Back();  -forward();  -go();
 
   使用location对象 location对象包含当前窗口的URL信息。
 
   使用navigator对象 navigator对象包含浏览器的信息，浏览器的类型、版本信息都可以从中获取。
 
   使用srceen对象 screen对象包含客户端屏幕的相关信息。
 
子对象
 
-height();  -width();
 
47.DOM（Document Object Model）：文档对象模型
 
– 浏览器提供的操作HTML文档内容的应用程序接口
 
– 用于对文档进行动态操作，如增加文档内容、删除文档内容、修改文档内容等等
 
48.DOM的核心就是对DOM树的操作，即增加、删除、修改DOM树中的内容
 
DOM节点是一个对象（属性和方法）
访问DOM节点
通过id属性获得节点：
 
document.getElementById( )
 
•通过标签名获得所有同名标签：document(或某一节点对象).getElementsByTagName( )
 
•通过父节点获得子节点：node.childNodes[ ]、node.firstChild、node.lastChild
 
•通过子节点获得父节点：node.parentNode
 
•获得前后兄弟节点：node.previous(next)Sibling
 
51.获得某一元素节点的属性节点
 
– 标准方式获得属性：node.getAttribute(  name )
 
– 简单方式获得属性：node. attrName
 
•修改某一元素节点的属性节点
 
– 直接赋值给属性
 
52.获得某一元素节点的相关信息
 
– 节点类型：node.nodeType
 
– 节点标签名：node.nodeName
 
•获得文本节点的文本值：node.nodeValue
 
53.生成一个 DOM节点
 
– 生成一个元素节点： document.createElement( )
 
– 生成一个文本节点：document.createTextNode( )
 
•把生成的节点作为某一个节点（ node）的子节点
 
– 作为node节点的最后一个子节点：
 
node.appendChild( newNode )
 
– 插入到node节点中某一子节点之前：
 
node.insertBefore( newNode, oldNode )
 
54. 删除一个元素节点、文本节点
 
– 通过父节点删除本节点：myParent.removeChild(mySelfNode )
 
– 通过自己删除本节点：
 
mySelfNode.parentNode.removeChild(mySelfNode )
 
• 删除一个属性节点： node.attrName = ‘’;
 
55修改一个元素节点（新节点替换旧节点）：
 
oldNode.parentNode.replaceChild (newNode, oldNode )
 
•修改一个文本节点（替换文本值）：
 
textNode.nodeValue = “”;
 
•修改一个属性节点（覆盖原有属性）：
 
node.attrName = ‘newAttrValue’;
 
56.程序原则：
 
– 应尽量使用节点对象属性的方式来绑定事件处理函数
 
– 尽量避免HTML标记属性中绑定事件处理函数
 
57.DOM中每个元素结点都有一个style对象管理元素的样式
 
58访问样式表
 
使用document.styleSheets属性
 
– 包含了页面上所有样式表的引用
 
– 数组
 
•每个styleSheets属性指定一个cssRules集合，包含所有定义在样式表中的规则
 
– 注意：在IE中为“rules”
 
59.第三方库Prototype 、MooTools、Dojo Toolkit、
 
60jQuery的一大贡献就是将行为与结构分离
 
61jQuery选择器
 
基本功能
 
快速、精确地选择某一个（某一组）元素
 
返回该元素（组）的jQuery包装集
 
优势
 
 简洁
 
 强大
 
62选择器类别划分
 
 
 
 
标签选择器： var  div  =  $(‘div’);
 
类选择器： var  toHidden  =  $(‘.toHidden’);
 
ID选择器： var  toExten  =  $(‘#toExten’);
 
群选择器： var  nodes  =  $(‘div,  p,  ul,  ol’);
 
通用选择器：var  anyNodes  =  $(‘*’);
 
 
 
基本选择器
 
 层次选择器
 
 过滤选择器
 
 表单选择器
 
 表单过滤选择器
 
基本过滤器（下标从0开始）
 
         :first、:last、:not(selector)、:even、:odd、:eq(index)
 
         :gt(index)、:lt(index)
 
内容过滤选择器
 
          :contains(text)、:empty、:has(selector)
 
可见性过滤选择器：:hidden、:visible 
 
属性过滤选择器
 
         [attribute]、[attribute=value]、[attribute!=value]
 
第index个子元素（下标从1开始）
 
          :nth-child(index/even/odd/equation)
 
第1个子元素           :first-child
 
最后1个子元素：  :last-child
 
选取<input>、<textarea>、<select>和<button>元素   :input
 
选取所有文本框（<input type=“text”/>）  :text
 
选取所有密码框：                 :password
 
选取所有单选按钮：            :radio
 
选取所有多选按钮：            :checkbox
 
选取所有提交按钮：            :submit
 
选取所有重置按钮：            :reset
 
选取所有文件上传域：                 :file
 
选取所有图像按钮：            :image
 
选取所有按钮：                     :button
 
选取所有隐藏域（<input type=“hidden”/>）：       :hidden
 
选取所有可用元素：                 :enabled
 
选取所有不可用的元素：           :disabled
 
选取所有被选中的元素：       :checked
 
选取所有被选中的下拉列表项：:selected
 
使用选择器获取的对象为jQuery包装集（jQuery对象）
jQuery包装集和DOM对象转化
DOM→jQuery：使用  $( )  包装
 
jQuery→DOM：数组下标方式、get( )方法获得
 
文档就绪事件是jQuery中扩展的一个新事件
作用：替代window.onload事件
 
写法：
 
                          $(document).ready(function(){ //..文档就绪后的处理函数})
 
66.this在事件处理函数中，同原生JS一样，指代触发事件的DOM对象
 
通常通过$(this)的方法将DOM对象转换为jQuery对象
 
jq绑定事件的方法  -通过事件方法 -通过bind方法
jQuery文档操作
查找节点
 
插入节点
 
删除节点
 
设置和获取HTML、文本和值
 
69获取用户名控件节点
 
var $userName = $('input[name="username"]');
 
获取密码控件节点
 
var $pswd = $('input[name="pswd"]');
 
获取标题节点
 
var $h1 = $('h1');
 
70text()：返回或设置匹配元素的文本内容
 
返回匹配元素的文本内容
 
$p_con = $(‘p’).text()
 
设置匹配元素的文本内容
 
$p_content = $(‘p’).text(‘你不喜欢的水果是？’);
 
71设置和获取属性 ：attr()
 
设置属性：$(‘p’).attr(‘title’,‘最不爱的水果是’);
 
获取属性：$(‘p’).attr(‘title’);
 
删除属性：removeAttr()
 
$(‘p’).removeAttr(‘title);
 
72添加类：addClass()
 
向匹配的元素中追加一个类
 
$(‘li’).addClass(‘bgcolor’);
 
删除类：removeClass()
 
删除匹配的元素中指定的类
 
$(‘li’).removeClass(‘bgcolor’);
 
删除匹配元素的所有类
 
$(‘li’).removeClass();
 
73设置和获取匹配元素的CSS样式 ：css()
 
获取样式：$(‘li’).css(‘title’);
 
设置样式：$(‘li’).css(‘padding’,’15px’);
 
设置多个样式：$(‘li’).css({
 
 "color":"white",
 
  "font-size":"20px",
 
  "padding":"5px"
 
} )
 
74父节点
 
子节点
 
兄弟节点：silblings()
 
$sibNode s= $(‘ul’).siblings();
 
上一个节点：prev()
 
$preNode = $(‘ul’).prev()
 
下一个节点：next()   $nxtNode = $(‘ul’).next()
 
 

哈夫曼树，又称最优二叉树。
 
概念：
 
1.树的带权路径：所有叶子节点到根节点的路径加权和。
 
2.哈夫曼树：带权路径长度最短的二叉树。
 
特点：
 
1.每个节点的度只能为2或者0；
 
2.叶子结点数是N时，中间节点数为N-1，总结点树为2*N-1
 
3.哈夫曼编码：任意一个叶节点的编码都不是其他叶节点编码的前缀。
 
问题1：
 
1.为什么带权路径最短？
 
前提：带全路径所求的是叶子到根节点的长度，每个节点的度只能为0或者2
 
因为哈夫曼树的创建步骤是：每次取出节点中权最小的两个节点构树。得到的结果是，权数越小的节点，路径越长；权数越大的节点，路径越短。一颗树上的节点为N时，所有节点的连线共有N-1条，只要保证小权节点所占路径越大，大权路径越小，得到的带权路径长度才能越小。
 
 

 
 
2.哈夫曼编码为啥任意一个编码都不是其他编码的前缀？ 
 
因为这里所说的编码都是对叶子结点的编码。每个叶子节点的度都是0，是终结节点，没有其他节点经过。所以通过哈夫曼编码得到的结果不会存在歧义。所以在解码的时候，可以顺序读取编码，依次找编码对应得值，而不会出现走不通或者歧义的情况。
 

本章介绍关于决策树的知识，理论部分来自周老师的西瓜书，代码部分来自《机器学习实战》，有位作者对代码实现已经做了很好的介绍，有兴趣的朋友可以看一下，感谢作者。（https://www.cnblogs.com/dennis-liucd/p/7905793.html）。
 
一、基本流程
 
顾名思义，决策树是基于树结构来进行决策的，这也是人类在面临决策问题时一种很自然的处理机制。决策过程中提出的每一个问题都是对某个属性的“测试”，每个测试或是导出最终结论（分类结果），或是导出进一步需要判定的问题，其考虑范围是在上次决策结果的限定范围内进行的。
 
一般地，一棵决策树包含一个根结点、若干内部结点和若干叶结点；叶结点对应决策结果（样本最终的分类），其他每个结点则对应一个属性测试；每个结点包含的样本集合依据所选属性的取值被划分到相应的叶结点中去；根结点包含全部的样本。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树的学习算法是一个递归算法：
 
 
在决策树算法中，有三中情况会导致递归返回：（1）当前结点包含的样本全属于一个类别，无需划分；（2）当前属性集为空，或者所有样本在所选属性上的取值都相同，无法划分（解决思路：把当前结点标记为叶结点，将其类别设定为所含样本类别最多的类别）；（3）当前结点包含的样本集合为空（解决思路：把当前结点标记为叶结点，将其类别设置为其父结点中所含样本数目最多的类别）。
 
二、划分选择
 
由上面的决策树算法知，决策树学习的关键是第8行，即如何选取最优的划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
 
2.1信息增益
 
“信息熵”是度量样本集合纯度最常用的一种指标。假定当前集合中第类样本所占的比例为,则的信息熵定义为：
 
                                                                                 
 
的值越小，则的纯度越高。
 
假定离散属性有个可能的取值{}，若使用来对集合进行划分，则会产生个分支结点，其中第个分支结点包含了集合中所有属性上取值为的样本，记为。我们有上面的公式可以计算出该集合的信息熵，再考虑到不同的分支结点所包含的样本数目不同，给每个分支结点赋予权重||/||,即样本数越大，对分支结点的影响也就越大，于是可以计算出用属性对样本集进行划分所获得的“信息增益”：
 
                                                                  
 
一般而言，信息增益越大，则意味着使用属性来进行划分所获得的“纯度提升”越大。因此，我们在进行划分时，依次计算每个属性的信息增益，选取增益最大的特征作为最优划分属性。（著名的算法就是如此）
 
2.2增益率
 
当决策树产生的分支结点太多时，就出现了过拟合问题，这样的决策树不具有泛化能力。实际上，信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，著名的决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。信息增益率定义为：
 
                                                          
 
其中，属性的可能取值的数目越多，的取值就越大。
 
需要注意，增益率准则对可取值数目较少的属性有所偏好，因此，算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性作为划分属性。
 
2.3基尼指数
 
CART决策树（分类回归树，可用于分类和回归）使用“基尼指数”来选择划分属性。同样是基于决策树的生成是希望分支结点的纯度越高越好这样一个原则，我们还可以通过基尼系数这一指标来衡量样本集合的纯度，基尼系数定义为：
 
                                                                           
 
从概率论来看，Gini（D）反应了从数据集D中抽取两个样本，其类别不一致的概率。因此基尼系数越大，则表示样本集合的纯度越低。属性的基尼指数定义为：
 
                                                     。
 
于是，我们在属性候选集合A中选择那个使得划分后基尼指数最小的属性作为最优划分属性。
 
三、剪枝处理
 
现在来考虑一个问题：决策树是不是形态越丰富，分支越多，越复杂，分类越准确呢？显然是否定的。学习算法中存在着一个需要特别注意的问题：“过拟合”。换句话说就是学习过程中过度的学习了训练集的特点，把训练集自身的一些特点当作所有样本数据都具有的一般性质，也就是学的太过了，有一些不应该继续分支的结点继续进行划分了，导致分支过多过冗余。这样子反而会降低学习算法的泛化能力。剪枝对于决策树的泛化性能的提升是显著的，有实验研究表明[Mingers,1989a],在数据带有噪声时，通过剪枝甚至可以将决策树的泛化性能提高25%。
 
所以剪枝这一名词也因此得来，因为剪枝的目的就是剪去过多的分支！决策树剪枝的基本策略有“预剪枝”和“后剪枝”，两者的界定就是一个发生在决策树生成过程中，一个是发生在决策树生成后。
 
3.1预剪枝
 
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将该结点标记为叶结点。
 
我们可以通过留出法来对泛化性能进行评估。将样本集合分为训练集和验证集。在基于前面提到的几种属性划分选择的基础上，对比划分前后的验证集的准确率来进行泛化性能的评估。如果经过划分后，验证集的准确率提高了，则认为当前结点的划分对于泛化性能的提升是有意义的，否则不计划分。
 
通过预剪枝，不仅可以降低过拟合的风险，同时因为限制了无意义的结点划分，在训练和测试的计算成本上也有所优化。由以上论述，我们可以认识到预剪枝是判断当前结点对于泛化性能的影响，并没有考虑当前结点的后续结点是否有机会能够提升泛化性能，这是一种“贪心”的本质。这个策略带来的问题就是有可能会丢失那些在后续确实能提高泛化性能的结点，因此预剪枝带来欠拟合的风险。
 
3.2后剪枝
 
后剪枝是发生于决策树生成完成以后，从由底至上考虑每个非叶节点，若将该结点替换为叶节点能够给决策树带来泛化性能的提升的话，则将该结点替换为叶节点。因为后剪枝是在一棵完整的决策树的基础上从底至上考虑每个非叶节点，相对于预剪枝来说欠拟合风险很小，不过训练时间开销是比较大的。
 
四、连续与缺失值
 
4.1连续值处理
 
由于连续属性的可取值的数目不再有限，所以需要新的方法来对该属性进行划分。最简单的策略是采用二分法对连续属性进行处理，C4.5决策树就是采用这种方法。
 
划分的基本思路是选取一个划分点 t，将数据集 D  划分成 和两个子集（也就是划分后的子结点），其中包含属性a的取值不大于t的那些样本，包含了属性 a 不小于 t 的那些样本。那么，如何选择划分点 t 呢？
 
首先，将 D  中样本的属性a的所有取值按从小到大的顺序排列，记为{a1,a2,...,an}；
 
然后，选取每个子区间[ ,)的中点作为备选的划分点集合，即
 
                                                                        
 
最后，基于使划分后的信息增益最大的原则，在备选集合 Ta 中选出最优的划分点 t 。
 
                                                               
 
 
 
在这里有一点需要注意的是：
 
离散属性的划分中，作为当前结点划分依据的属性，再其分支结点将不再作为划分考虑。例如在判别西瓜的好坏分类中，我们第一个结点通过色泽分出了亮和暗，得出了亮和暗两个分支结点。那么接下来这两个分支结点将不再考虑西瓜的色泽属性了，因为在第一个结点已经明确划分出了哪些瓜是“亮”属性，哪些瓜是“暗“属性，离散属性的划分重点是判别”是什么“，所以不存在多次重复判别。
 
而连续属性不同，连续属性例如通过二分法来离散化，划分重点不是”是什么“，而是”区间内属性值的大小关系“，这是可以多次划分多次比较的。例如在区间0到1，第一个结点是以t=0.5进行划分，得出两个分支结点v1,v2。 在v1中0到0.5，我们可以再次选定一个划分点t=0.25，再次划分出分支结点。
 
这是连续属性与离散数学在划分时的一个区别。
 
4.2缺失值处理
 
在前面的讨论中，我们都是假定样本属性的值都不是缺失的，但现实情况下还是存在一些样本是缺失的。例如由于测试成本，隐私保护等等。
 
如果缺失属性样本较多的话，并且不做任何处理，简单的放弃不完整样本的话，显然对数据信息是极其浪费的。样本不能放弃，但是属性缺失我们不得不放弃，因为本身就缺失，我们不可能凭空随便插入一个值，所以我们只能在划分过程中进行处理，减小划分误差。总的来说需要我们考虑的问题有两个：
 
（1）如何在属性值缺失的情况下进行划分属性选择？
 
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
 
先讨论问题（1）:
 
我们给定训练集D和属性a，令表示D中在属性a上没有缺失值的样本集合，显然我们只能通过来判断属性a的优劣。假定属性a有V个可取值,令表示在属性a上取值为的样本子集，表示中属于第k类（k=1,2,...,|y|）的样本子集。假定我们为每个样本x赋予一个权重Wx,初值为1。同时定义：
 
①，表示对于属性a，无缺失的样本比例；
 
②，表示无缺失样本中，第k类所占比例；
 
③，表示无缺失样本在属性a上取值为的样本的比例；
 
基于上述推论，我们可以将信息增益的计算时推广为：
 
                                                          
 
其中
 
对于问题（2）：
 
出于缺失值的样本终归还是不是理想样本，估我们还是希望这样的非理想样本对于决策树的贡献减小，因此我们有如下策略：
 
若样本 x 在划分属性a上的取值已知，则将x划入与其对应的分支结点，并保持样本权重Wx不变。若样本x在划分属性a上的取值未知，则将样本x划入所有分支结点，且样本权重调整为。
 
 
 
五、多变量决策树
 
想象一下，若我们把样本的每个属性都视为坐标空间中的一个坐标轴，则由d个属性描述的样本就对应了d维空间中的一个数据点。对样本的分类就意味着在这个坐标空间中寻找不同类样本之间的分类边界。而我们前面提到的决策树在d维空间中形成的分类边界有一个特点：轴平行，如图4.11所示，这个样本集的属性只包括两个连续属性（密度，含糖率），它的分类边界由若干个与坐标轴平行的分段组成的。
 
                                                        
 
                                                        
 
如图4.10以及4.11所示，在图4.10的决策树上有几个分支结点，对应图4.11则有几段关于轴平行的分类边界。这样的分类边界的确取得了很好的解释性，但是这仅仅是二维小样本容量上的应用。如果样本很复杂，是多维的大样本，那么必须通过很多很多段的划分才能取得较好的近似，例如图4.10中的决策树需要4段分类边界。通过多段的分类边界去划分，显然时间开销是很大的，因此假如我们不局限于平行与轴的分类边界，考虑使用斜的划分边界，如图4.12所示，此时就引入了“多变量决策树”。
 
                                                     
 
“多变量决策树”与“普通决策树”相比，关键在于分支结点的属性测试的区别。“多变量决策树”的属性测试不再是单一的属性测试，而是对多个属性的线性组合进行测试。换句话说，对于分支结点的属性测试，我们不再是为每个结点寻找一个最优划分属性了，而是对每个分支结点建立一个合适的线性分类器()，例如图4.10中的数据集，我们通过多变量决策树生成如图4.13所示的决策树，并且其分类边界如图4.14所示。
 
                                                  
 
                                                    
 
 
 
六.常见的决策树分类方法
 
(1)、CLS算法：是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
 
(2)、ID3算法：对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
 
ID3算法的核心思想：根据样本子集属性取值的信息增益值的大小来选择决策属性(即决策树的非叶子结点)，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
 
ID3算法优点：方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。
 
ID3算法缺点：倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
 
(3)、C4.5算法：基于ID3算法的改进，主要包括：使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性。
 
(4)、SLIQ算法：该算法具有高可扩展性和高可伸缩性特质，适合对大型数据集进行处理。
 
(5)、CART(Classification and RegressionTrees, CART)算法：是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此，CART算法生成的决策树是结构简洁的二叉树。
 
分类回归树算法(Classification and Regression Trees,简称CART算法)是一种基于二分递归分割技术的算法。该算法是将当前的样本集，分为两个样本子集，这样做就使得每一个非叶子节点最多只有两个分支。因此，使用CART算法所建立的决策树是一棵二叉树，树的结构简单，与其它决策树算法相比，由该算法生成的决策树模型分类规则较少。
 
CART分类算法的基本思想是：对训练样本集进行递归划分自变量空间，并依次建立决策树模型，然后采用验证数据的方法进行树枝修剪，从而得到一颗符合要求的决策树分类模型。
 
CART分类算法和C4.5算法一样既可以处理离散型数据，也可以处理连续型数据。CART分类算法是根据基尼(gini)系数来选择测试属性，gini系数的值越小，划分效果越好。设样本集合为T，则T的gini系数值可由下式计算：
 
                                                                      
 
其中，pj是指类别j在样本集T中出现的概率。若我们将T划分为T1、T2两个子集，则此次划分的gini系数的值可由下式计算：
 
                                               
 
其中，s为样本集T中总样本的个数，s1为属于子集T1的样本个数，s2为属于子集T2的样本个数。
 
CART算法优点：除了具有一般决策树的高准确性、高效性、模式简单等特点外，还具有一些自身的特点。如，CART算法对目标变量和预测变量在概率分布上没有要求，这样就避免了因目标变量与预测变量概率分布的不同造成的结果；CART算法能够处理空缺值，这样就避免了因空缺值造成的偏差；CART算法能够处理孤立的叶子结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响；CART算法使用的是二元分支，能够充分地运用数据集中的全部数据，进而发现全部树的结构；比其它模型更容易理解，从模型中得到的规则能获得非常直观的解释。
 
CART算法缺点：CART算法是一种大容量样本集挖掘算法，当样本集比较小时不够稳定；要求被选择的属性只能产生两个子结点，当类别过多时，错误可能增加得比较快。