机器学习方法与实践 课件ID3

决策树：ID3算法DecisionTree:IterativeDichotomiser3主讲：耿阳李敖计算机与信息技术学院视觉智能实验室（VisInt）BeijingJiaotong

University决策树引入给定当天的天气、温度、湿度和风力四个属性值，如何根据历史数据判断是否去打网球？决策树引入可通过构建如下决策树进行判断Outlook（天气状况）决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）Sunny决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）SunnyHighNormalNoYes决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）SunnyHighNormalNoYesOvercastYes决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）SunnyHighNormalNoYesOvercastYesWind（风力）Rain决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）SunnyHighNormalNoYesOvercastYesWind（风力）RainStrongWeakNoYes决策树引入可通过构建如下决策树进行判断Outlook（天气状况）Humidity（湿度）SunnyHighNormalNoYesOvercastYesWind（风力）RainStrongWeakNoYes如何根据历史数据构建一棵决策树？问题决策树引入从上述构建决策树的过程可以看出，每构建一个分支都是让一类属性值的不确定性降低的过程，直至建立最后的叶子结点得到确定的输出结果不确定性熵密切相关信息熵基本概念对于具有n个取值（类别）的随机变量（样本集）X，X的信息熵H(X)为：

信息熵基本概念对于具有n个取值（类别）的随机变量（样本集）X，X的信息熵H(X)为：

信息熵的意义：衡量了样本集的不确定性，熵越大不确定性越大

条件熵当存在两个随机变量X和Y时，如何在给定Y的条件下，度量X的不确定性？例如：如何在已知天气状况Y为晴天的情况下，求解湿度X的不确定性？条件熵基本概念当存在两个随机变量X和Y时，如何在给定Y的条件下，度量X的不确定性？例如：如何在已知天气状况Y的情况下，求解湿度X的不确定性？1.

条件概率的熵对于具有n个取值的随机变量X，给定随机变量Y的取值为v，在Y=v条件下的X的条件熵H(X|Y=v)为：即已知Y的具体取值条件下，X的信息熵（不确定性）2.条件熵进一步，对于具有n个取值的随机变量X，当给定随机变量Y时，X的条件熵H(X|Y)为：即具体的条件熵的期望信息增益当存在两个随机变量X和Y时，如何在给定Y的条件下，知道X的不确定性降低了多少？信息增益基本概念当存在两个随机变量X和Y时，如何在给定Y的条件下，知道X的不确定性降低了多少？

信息增益的意义：对于样本集X和其中的属性Y而言，信息增益衡量了属性Y已知的条件下，样本集X减少的不确定性；或使用属性Y划分样本集X能提升的纯度ID3算法基本概念

ID3算法示例以打网球问题为例：

ID3算法示例以打网球问题为例：

ID3算法示例以打网球问题为例：

ID3算法示例以打网球问题为例：

ID3算法示例以打网球问题为例：（5）属性Outlook具有三个值，对于样本子集XSunny，分别计算以属性Temperature,Humidity和Wind划分样本子集XSunny的信息增益ID3算法示例以打网球问题为例：

ID3算法示例以打网球问题为例：（5）属性Outlook具有三个值，对于样本子集XSunny，分别计算以属性Temperature,Humidity和Wind划分样本子集XSunny的信息增益

③

选择信息增益最大的属性Humidity作为子节点ID3算法示例以打网球问题为例：（6）同理，对于样本子集XOvercast,XRain，分别