返回主目录
返回决策树目录
上一章：机器篇——决策树(一)
下一章：机器篇——决策树(三)
本小节，细说 Hunt 算法(卡方检验)，下一小节开始细说 ID3 算法。
二. 算法细说
1. 决策树的起源
hunt 算法是许多决策树算法的基础，包括 ID3、C4.5、CART等。Hunt 算法通过递归方式建立决策树
2. Hunt 算法(卡方检验)
(1). 定义
卡方检验是一种用途很广的计数资料的假设检验方法。它属于非参数检验的范畴，主要是比较两个及以上样本率(构成比)以及两个分类变量的关联性分析。其根本思想就是在大于比较理论频数和实际频数的吻合程度或拟合优化程度问题。
(2). 卡方检验的基本思想
①. 卡方检验是以 分布为基础的一种常用假设检验方法，它的无效假设 是：观察频数与期望频数没有差别
②. 首先假设 成立，基于此前提，计算出 值，它表示观察值与理论值之间的偏离程度。根据 分布及自由度可以确定在 假设成立的情况下获得当前统计量及更极端情况下的概率 。如果 值很小，说明观察值与理论值偏离程度太大，应当拒绝无效假设，表示比较资料之间有显著差异；否则就不能拒绝无效假设，尚能认为样本所代表的实际情况和理论假设有差别。
(3). 卡方值的计算与意义
值表示观察值与理论值之间的偏离程度。计算这种偏离程度的思路如下：
①. 设 代表某个类别的观察频数， 代表基于 计算出的期望频数， 与 之差称为残差。
②. 显然，残差可以表示某一个类别观察值和理论值的偏差程度。但如果将残差简单相加以表示各类观察频数与期望频数的差别，则有一定的不足之处。因为残差有正有负，相加之后会彼此抵消，总和仍然为零，为此，可以将残差平方之后求和。
③. 另一方面，残差大小是一个相对的概念，相对于期望频数为 10 时，期望频数为 20 的残差非常大，但相对于期望频数为 1000 的 20 残差就很小了。考虑到这一点，人们又将残差平方除以期望频数再求和，以估计观察频数与期望频数的差别。
④. 进行上述操作后，就得到了常用的 统计量，其计算公式为：
：为 水平的观察频数
：为 水平的期望频数
：为总频数
：为 水平的期望频数概率，
：为单元格数
自由度： (行数 - 1)(列数 - 1)
对于四表格，自由度：
当 比较大时， 统计量近似服从 (计算 时用到的参数个数)这个自由度的卡方分布。
⑤. 由卡方的计算公式可知，当观察频数与期望频数完全一致时，
观察频数与期望频数越接近，两者之间的差异越小， 值越小；
反之，观察频数与期望频数差别越大，两者之间的差异越大， 值越大；
换言之，大的 值表明观察频数远离期望频数，即表明远离假设。
小的 值表明观察频数接近期望频数，接近假设。因此， 是观察频数与期望频数之间距离的一种度量指标，也是假设成立与否的度量指标。如果 值小，就倾向于不拒绝 ，至于 在每个具体研究中研究要大到什么程度才拒绝 ，则要借住与卡方分布求出所对应的 值来确定。
(4). 卡方检验的样本要求
卡方分布本身是连续型分布，但是，在分布资料的统计分析中，显然频数只能以整数形式出现，因此计算出的统计量是非连续的。只有当样本量比较充足时，才可以忽略两者间的差异，否则将可能导致较大的偏差。具体而言，一般认为对于卡方检验中的每一个单元格，要求其最小期望频数均大于1，且至少有 的单元格期望频数大于 5，此时使用卡方分布算出的概率值才是准确的。如果数据不符合要求，可以采用确切概率进行概率计算。
(5). 卡方检验的类型
①. 四格表资料的卡方检验
四格表资料的卡方检验用于进行两个概率或两个构成比的比较。
a. 专用公式
若四格表资料四个格子的频数分布为：，则四格表资料卡方检验的卡方值为：
b. 四格卡方公式的推导
假设 ：
事件 患病与事件 吸烟 没有关系。将表中 “观测值” 用字母表示，则得到下表：
事件的估计数量为：
事件的估计数量为：
事件的估计数量为：
事件的估计数量为：
卡方统计量：
：为观测值
：为预测值
c. 应用条件
要求样本含量大于40且每个格子中的理论频数不应小于5。当样本含量大于40，但理论频数有小于5的情况需要校正，当样本含量小于40，只能用确切概率计算概率。
②. 行 X 列 表 资料的卡方检验
行 X 列 表 资料的卡方检验用于多个概率或多个构成比的比较。
a. 专用公式：
r 行 c 列表 资料的卡方检验的卡方值：
b. 应用条件：
要求每个格子中的理论频数 T 大于 5 或 1 < T < 5 的格子数不超过总格子数的 。当 T < 5 或 1 < T < 5 的格子数较多时，可采用并列并行，或删列删行，增大样本含量的办法使其符合 行 X 列 表 资料 卡方检验的应用条件。而多个概率的两两比较可采用 行 X 列 表 分割的办法
③. 列联表资料的卡方检验
同一组对象，观察每一个个体对两种分类方法的表现，结果构成双向交叉排列的统计表就是列联表。
a. 列联表的卡方检验
列联表的卡方检验用于 列联表的相关分析，卡方值的计算和检验过程与 行 X 列 表资料的卡方检验相同。
b. 列联表的卡方检验
列联表的卡方检验又称配对记数资料或配对四格表资料的卡方检验，根据卡方值计算公式的不同，可以达到不同的目的。当用一般四格表的卡方检验计算时，卡方值：
此时用于进行配对四格表的相关分析，如考察两种检验方法的结果有无关系。
当卡方值为：
此时卡方检验用来进行四表格的差异检验，如考察两种检验方法的验出率有无差别。
c. 列联表卡方检验应用中的注意事项与 表的卡方检验相同。
④. 卡方检验的应用条件
适用于四格表应用条件
a. 随机样本数据。两个独立样本比较可以分为以下 3 种情况：
(a). 所有的理论数 ，并且总样本量 ，用 Pearson 卡方进行检验
(b). 如果理论数 但 ，并且 ，用连续性校正的卡方进行检验。
(c). 如果有理论数 或 ，则用 Fisher's 检验。
b. 卡方检验的理论频数不能太小
表卡方检验的应用条件
a. 表中理论数小于 5 的格子不能超过 。
b. 不能有小于 1 的理论数。如果实验中有不符合 表的卡方检验，可以通过增加样本数、列合并来实现。
(6). 卡方检验的用途
卡方检验最常见的用途就是考察某无序分类变量水平在两组或多组间的分布是否一致。实际上，除了此用途之外，卡方检验还有更广泛的应用。具体而言，其用途主要包括以下几个方面：
①. 检验某个连续变量的分布是否与某种理论分布相一致。如是否符合正态分布，是否服从均匀分布，是否服从 Pearson 分布等
②. 检验某个分类变量各类的出现概率是否等于指定概率
③. 检验某两个分类变量是否相互独立
④. 检验控制某种或某几种分类因素的作用以后，另两种分类变量是否相互独立
⑤. 检验某两种方法的结果是否一致。
(7). Hunt 算法步骤
①. 如果 中所有数据都属于同一个类 ，则 是叶节点，用 标识。
②. 如果 中包含属于多个类的数据，则选择一个属性，将数据划分为较小子集。创建子节点，将数据按属性放入子节点中，然后递归调用算法。
注： ①. 如果没有可以选择的属性，则该节点为叶子节点，类标号为父节点上较多数的类。
②. 如果与 相关的数据均为一个属性，则不可以继续划分，类标号为多数类。
(8). CHAID 决策树算法伪代码
函数：
输入：训练集数据 ，训练集数据属性集合
输出：CHAID 决策树
a. if 样本 全部属于同一个类别 ：
b. 创建一个叶子节点，并标记类标号为
c. return
d. else：
e. 计算属性集 中目标属性与其他每一个属性的卡方值，取卡方值最大的属性
f. 创建节点，取属性 为该节点的决策属性
g. for 节点属性 的每个可能的取值 ：
h. 为该节点添加一个新的分支，假设 为属性 取值为 的样本子集
i. if 样本 全部属于同一个类别 ：
j. 为该分支添加一个叶子节点，并标记类标号为
k. else：
l. 递归调用 ，为该分支创建子树
上面的伪代码为 python 的缩进格式。
返回主目录
返回决策树目录
上一章：机器篇——决策树(一)
下一章：机器篇——决策树(三)