相亲
示例：
现想象一个女孩的母亲要给这个女孩介绍男朋侪，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等环境。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决议过程就是典型的分类树决议。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见（二分类）。
决议树
决议树（decision tree）
决议树特点
- 决议树是一个 if - else 规则集合，从根节点到叶子节点的一条路径，构成一条规则。
- 所有规则具备一个紧张性子：互斥而且完备。
- 节点：内部节点和叶子节点。内部节点表示一个特性。叶子节点对应一个决议效果。
办理的题目
优点
- 易于理解，模子可读性强
- 分类速度快，决议待见： O ( l o g 2 m ) O(log_2m) O(log2m),m 为样本特性数。
- 既可以处理离散值也可以处理一连值。很多算法只是专注离散值大概一连值。
- 相比其他算法需要更少的特性工程（比如：不需要特性标准化，可以很优点理字段缺失值，不用关心特性间是否相互依靠，主动组合多个特性）
- 可以处理多维度输出的分类题目。
- 对于异常点的容错本事好，健壮性高。
- 可以交织验证的剪枝来选择模子，从而进步泛化本事。
缺点：
- 非常容易过拟合，导致泛化本事不强。
- 决议树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法办理。
- 寻找最优的决议树是一个NP难的题目，我们一样平常是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
- 有些比力复杂的关系，决议树很难学习，比如异或。这个就没有办法了，一样平常这种关系可以换神经网络分类方法来办理。
- 假如某些特性的样本比例过大，生成决议树容易偏向于这些特性。这个可以通过调节样本权重来改善。
比力幸运的是，防止过拟合的方法很多：
- 限制树的最大深度
- 限制叶子节点的最少样本数目。
- 限制节点分裂时的最小样本数目。
- 吸取 bagging 的思想对训练样本采样（subsample），使用部分训练样本进行训练单棵树。
- 鉴戒随机丛林的思想在学习单棵树时，只接纳一部分特性。
- 在目的函数中添加正则项，处罚复杂的树结构。
决议树学习步骤
常见的决议树算法
- ID3 算法：使用信息增益，寻找最优特性
- C4.5 算法：使用信息增益比，寻找最优特性
- CART（classification and regression tree） 算法：使用基尼系数，寻找最优特性。
生成决议树
决议树的生成是一个递归过程，递归选择最优特性，并根据该特性对训练数据进行划分，使每个子数集有一个最好的分类。
递归过程中，有三种环境会导致递归结束。
- 当前节点包罗的样本全属于一个类别，无需再划分。
- 当前属性集为空，大概所有样本在所有属性上取值相同，无法划分。
- 当前节点包罗的样本集合为空，不能划分。
输入：训练集 D = [ ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) ] D = [\,(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\,] D=[(x1,y1),(x2,y2),...,(xm,ym)]
属性集 $ = [, a_1,a_2,…,a_d ,] $
TreeGenerate( D , A )
生成节点 node
if D 中样本全属于同一类别 C:
将 node 标记为 C 类的叶子节点
return
if len(A) == 0 or D 中样本在 A 上取中相同：
将 node 标记为叶子节点，其类别标记为 D 中样本最多的类。
return
从 A 中选择出最优划分属性： a ∗ a_* a∗
for a ∗ a_* a∗ in a ∗ v a_*^v a∗v：
为 node 生成一个分支，令 $D_v = $ D 中在 a ∗ a_* a∗ 上取中为 a ∗ v a_*^v a∗v 的样本子集。
if len( D v D_v Dv) == 0:
将分支节点标记为叶子节点，其类别标记为 D 中样本最多的类。
return
else:
TreeGenerate( D v , A / a ∗ D_v, A / {a_*} Dv,A/a∗)
return node
决议树代码
- # 决策树
- import math
- class DecisionTree():
- def create_tree(self, data_set, labels):
- class_list = [example[0] for example in data_set]
- # data_set 中的样本，类别完全相同，停止划分
- if class_list.count(class_list[0]) == len(class_list):
- return class_list[0]
- # 只有一个特征
- if len(labels) == 0 or len(data_set[0]) == 1:
- return self.majority_count(class_list)
- # 选择最优特征划分
- best_feat = self.choose_best_feature(data_set)
- best_feat_label = labels[best_feat]
- my_tree = {best_feat_label: {}}
- del (labels[best_feat])
- feat_value_set = set([example[best_feat] for example in data_set])
- for value in feat_value_set:
- sub_labels = labels[:]
- sub_list = self.split_data_set(data_set, best_feat, value)
- if len(sub_list) == 0:
- my_tree[best_feat_label][value] = self.majority_count(class_list)
- else:
- my_tree[best_feat_label][value] = self.create_tree(sub_list, sub_labels)
- return my_tree
- # 样本中类别最多
- @staticmethod
- def majority_count(class_list):
- class_count = {}
- for vote in class_list:
- class_count[vote] += class_count.get(vote, 0) + 1
- return sorted(class_count.items(), key=lambda x: x[1], reverse=True)[0][0]
- # 使用增益率进行特征选择
- def choose_best_feature(self, data_set):
- num_features = len(data_set[0]) - 1
- base_ent = self.calc_shannon_ent(data_set)
- best_info_gain_ratio = 0.0
- best_feature = -1
- for i in range(num_features):
- feat_set = set(example[i] for example in data_set)
- new_ent = 0.0
- split_info = 0.0
- for value in feat_set:
- sub_data_set = self.split_data_set(data_set, i, value)
- prod = len(sub_data_set) / float(len(data_set))
- new_ent += prod * self.calc_shannon_ent(sub_data_set)
- split_info += -prod * math.log2(prod)
- info_gain = base_ent - new_ent
- if info_gain == 0: continue
- info_gain_ratio = info_gain / split_info
- if info_gain_ratio > best_info_gain_ratio:
- best_info_gain_ratio = info_gain_ratio
- best_feature = i
- return best_feature
- # 计算熵：
- @staticmethod
- def calc_shannon_ent(data_set):
- label_count = {}
- for feat_vec in data_set:
- label = feat_vec[0]
- label_count[label] = label_count.get(label, 0) + 1
- shannon_ent = 0.0
- n = len(data_set)
- for label, count in label_count.items():
- prob = float(count) / n
- shannon_ent -= prob * math.log(prob, 2)
- return shannon_ent
- # 离散型特征，分隔数据集
- @staticmethod
- def split_data_set(data_set, axis, value):
- result = []
- for feat_vec in data_set:
- if feat_vec[axis] != value: continue
- result.append(feat_vec[:axis] + feat_vec[axis + 1:])
- return result
决议树生成过程，一个关键步骤，选择最优特性进行划分。
我们希望决议树的分支节点包罗的样本属于同一类别，即节点的“纯度”（purity）越来越高。
信息增益
信息熵（information enthropy）
熵度量事物的不确定性，越不确定的事物，它的熵越大。
E n t ( X ) = − ∑ i = 1 n p i l o g 2 p i Ent(X) = -\sum_{i=1}^{n}{p_i log_2 p_i} Ent(X)=−∑i=1npilog2pi
- n：X 的 n 种差别的离散值
- p i p_i pi：X 取值为 i 的概率
$Ent(D) $ 的值越小，D 的纯度越高。
例子：假设 X 有两个取值A，B。P(A) =0.5，P(B) =0.5。
那么 X 具有的不确定性： E n t ( X ) = − ( 0.5 ∗ l o g 2 0.5 + 0.5 ∗ l o g 2 0.5 ) = l o g 2 2 = 1 Ent(X)=-(0.5*log_2{0.5}+0.5*log_2{0.5})=log_2{2}=1 Ent(X)=−(0.5∗log20.5+0.5∗log20.5)=log22=1
假设 X 有两个取值A，B。P(A) =1/3，P(B) =2/3。
那么 X 具有的不确定性： E n t ( X ) = − ( 1 3 ∗ l o g 2 1 3 + 2 3 ∗ l o g 2 2 3 ) Ent(X)=-(\frac{1}{3}*log_2{\frac{1}{3}}+\frac{2}{3}*log_2{\frac{2}{3}}) Ent(X)=−(31∗log231+32∗log232)
= 1 3 l o g 2 3 − 2 3 l o g 2 2 3 =\frac{1}{3}log_23-\frac{2}{3}log_2\frac{2}{3} =31log23−32log232
= l o g 2 3 − 2 3 l o g 2 3 − 2 3 l o g 2 2 3 =log_23-\frac{2}{3}log_23-\frac{2}{3}log_2{\frac{2}{3}} =log23−32log23−32log232
= l o g 2 3 − 2 3 ( l o g 2 3 + l o g 2 2 3 ) =log_23-\frac{2}{3}(log_23+log_2{\frac{2}{3}}) =log23−32(log23+log232)
= l o g 2 3 − 2 3 l o g 2 2 =log_23-\frac{2}{3}log_22 =log23−32log22
= l o g 2 3 − 2 3 < l o g 2 2 = 1 =log_23-\frac{2}{3}<log_22=1 =log23−32<log22=1
P(A) =1/3，P(B) =2/3 比 P(A) =1/2，P(B) =1/2 确定性大。
熵只与 X 的分布有关，与 X 取值无关
- def calc_shannon_ent(data_set):
- label_count = {}
- for feat_vec in data_set:
- label = feat_vec[0]
- label_count[label] = label_count.get(label, 0) + 1
- shannon_ent = 0.0
- n = len(data_set)
- for label, count in label_count.items():
- prob = float(count) / n
- shannon_ent -= prob * math.log(prob, 2)
- return shannon_ent
多个变量的联合熵
H ( X , Y ) = − ∑ x i ∈ X ∑ y i ∈ Y p ( x i , y i ) l o g 2 p ( x i , y i ) H(X,Y) = -\sum_{x_i \in X}\sum_{y_i \in Y}{p(x_i,y_i)log_2{p(x_i,y_i)}} H(X,Y)=−∑xi∈X∑yi∈Yp(xi,yi)log2p(xi,yi)
条件熵
条件熵类似条件概率，它度量了已知 X 后，剩下 Y 的不确定性。
H ( X ∣ Y ) = − ∑ x i ∈ X ∑ y i ∈ Y p ( x i , y i ) l o g 2 p ( x i ∣ y i ) = ∑ j = 1 n p ( y i ) H ( X ∣ y i ) H(X|Y) = -\sum_{x_i \in X}\sum_{y_i \in Y}{p(x_i,y_i)log_2{p(x_i|y_i)}}=\sum_{j=1}^np(y_i)H(X|y_i) H(X∣Y)=−∑xi∈X∑yi∈Yp(xi,yi)log2p(xi∣yi)=∑j=1np(yi)H(X∣yi)
信息增益
H(X) 度量了 X 的不确定性。
H(X|Y) 度量了，已知 Y 后 X 剩下的不确定性
H(X) - H(X|Y) 什么能度量什么？
韦恩图
- H(X)：左边的椭圆
- H(Y)：左边的椭圆
- I (X ,Y)互信息大概信息增益：两个椭圆交集
- H( X , Y)：两个椭圆并集
- H(X|Y)
- H(Y|X)
G a i n ( X , Y ) = H ( X ) − H ( X ∣ Y ) Gain(X,Y) = H(X) - H(X|Y) Gain(X,Y)=H(X)−H(X∣Y)
∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣ 加权：每个分支数目不一样。
信息增益特点：对可取值数目较多的属性有偏好。
决议树中信息增益等价于训练数据集中类与特性的互信息。
增益率
为了降服信息增益：对可取值数目较多的属性有偏好。使用增益率。
Gain_ratio(D,a) = G a i n ( D , a ) I V ( a ) \frac{Gain(D,a)}{IV(a)} IV(a)Gain(D,a)
I V ( a ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g ∣ D i ∣ ∣ D ∣ IV(a) = -\sum_{i=1}^{n}{\frac{|D_i|}{|D|}log{\frac{|D_i|}{|D|}}} IV(a)=−∑i=1n∣D∣∣Di∣log∣D∣∣Di∣ 模仿信息熵。
增益率特点：对可取值数目较少的属性有偏好。
- def choose_best_feature(self, data_set):
- num_features = len(data_set[0]) - 1
- base_ent = self.calc_shannon_ent(data_set)
- best_info_gain_ratio = 0.0
- best_feature = -1
- for i in range(num_features):
- feat_set = set(example[i] for example in data_set)
- new_ent = 0.0
- split_info = 0.0
- for value in feat_set:
- sub_data_set = self.split_data_set(data_set, i, value)
- prod = len(sub_data_set) / float(len(data_set))
- new_ent += prod * self.calc_shannon_ent(sub_data_set)
- split_info += -prod * math.log2(prod)
- info_gain = base_ent - new_ent
- if info_gain == 0: continue
- info_gain_ratio = info_gain / split_info
- if info_gain_ratio > best_info_gain_ratio:
- best_info_gain_ratio = info_gain_ratio
- best_feature = i
- return best_feature
基尼值
G i n i ( D ) = ∑ k = 1 K p k ∗ （ 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(D) =\sum_{k=1}^K{p_k*（1-p_k)}=1-\sum_{k=1}^Kp_k^2 Gini(D)=∑k=1Kpk∗（1−pk)=1−∑k=1Kpk2
Gini(D) 越小，则数据集 D 的纯度越高。
基尼指数：
G i n i _ i n d e x ( D , a ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ G i n i ( D i ) Gini\_index(D,a) = \sum_{i=1}^n{\frac{|D_i|}{|D|}Gini(D_i)} Gini_index(D,a)=∑i=1n∣D∣∣Di∣Gini(Di)
在属性集合 A 中，选择那个使得划分后基尼指数最小的特性，作为最优化划分特性。
猜测
- def classify(self, input_tree, feat_lables, text_vec):
- first_str = list(input_tree.keys())[0]
- second_dict = input_tree[first_str]
- feat_index = feat_lables.index(first_str)
- for key in second_dict.keys():
- if text_vec[feat_index] == key:
- if type(second_dict[key]).__name__ == "dict":
- class_label = self.classify(second_dict[key], feat_lables, text_vec)
- else:
- class_label = second_dict[key]
- return class_label
ID3 算法的不足
- ID3 没有考虑一连特性：比如长度，密度。大大限制了 ID3 的用途。
- ID3 接纳信息增益大的特性创建决议树的节点。相同条件下，取值多的特性信息增益大（对可取值数目较多的属性有偏好）。
- ID3 算法没有考虑缺失值的环境。
- 没有考虑过拟合的题目。
C4.5
昆兰在 ID4.5 算法对ID3 的不足（一连特性，信息增益容易偏向取值较多的特性，缺失值，过拟合题目）做了改进。
一连特性处理
C4.5 的思绪是将一连特性离散化。
比如有 m 个样本的一连特性 A 有 m 个，
- 从小到大排列一连特性值 [ a 1 , a 2 , . . . , a m ] [a_1,a_2,...,a_m] [a1,a2,...,am] ，
- C 4.5 取相邻两个样本的平均数，一共取得 m - 1划分点，其中第 i 个划分点 T i = a i + ( a i + 1 ) 2 T_i=\frac{a_i+(a_i+1)}{2} Ti=2ai+(ai+1)。
- 对这 m - 1 个点，分别计算：以该点作为二元分类点时的信息增益。选择信息增益最大的点作为一连特性的二元离散分类点。比如取到的信息增益最大点为 a t a_t at，那么小于 a t a_t at 的值的类别为 0，大于 a t a_t at 的值为 类别 1.
留意：与离散特性差别，假如当前节点是一连特性，这个特性后边还是可以到场子节点的产生选择过程
信息增益容易偏向取值较多的特性
引入信息增益比:
I R ( D , A ) = I ( A , D ) H A ( D ) I_R(D,A)=\frac{I(A,D)}{H_A(D)} IR(D,A)=HA(D)I(A,D)
- I ( A , D ) I(A,D) I(A,D)：信息增益
- H A ( D ) H_A(D) HA(D)：特性熵
- D：样本特性输出的集合
- A：样本特性
H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} HA(D)=−∑i=1n∣D∣∣Di∣log2∣D∣∣Di∣
- n：特性 A 的类别数
- D i D_i Di：特性 A 的第 i 个取值对应的样本个数
- |D|：总样本数
特性数越多的特性对应的特性熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特性的题目。
缺失值
要办理缺失值的题目，需要办理两个题目：
一、样本某些特性值缺失的环境下，选择划分的特性。
二、选定了划分特性，对于在该特性上缺失值的样本怎么处理？
过拟合
C4.5 引入正则化系数进行初步的剪枝。
C4.5 算法不足
- 决议树非常容易过拟合，因此需要对决议树进行剪枝。剪枝的算法非常多。C 4.5 的剪枝算法仍有优化空间。思绪主要两种：
- 预剪枝：生成决议树时决定是否剪枝。
- 后剪枝：老师成决议树，再通过交织验证来剪枝。
在 CART 树，讲办理议树的剪枝思绪，主要接纳后剪枝加上交织验选择最符合的决议树。
- C4.5 生成的是多叉树，很多时候，计算机中二叉树模子运行效率高。
- C4.5 只能用于分类，不能应用回归题目。
- C4.5 使用了熵模子，有大量的耗时的对数运算。假如是一连特性另有大量的排序。假如能够简化模子减少运算强度但又不牺牲太多准确性的话，那就更好了。
CART 树
CART 树使用基尼系数替换信息增益比。基尼系数代表了模子的不纯度。
基尼系数越小，则不纯度越低，特性越好。和信息增益(比)是相反的
特性选择
分类题目，假设有 K 个类别，第 k 个类别的概率为 p k p_k pk,基尼系数为： G i n i ( p ) = ∑ k = 1 K ( p k ∗ ( 1 − p k ) ) = 1 − ∑ k = 1 K p k 2 Gini(p)=\sum_{k=1}^K(p_k*(1-p_k))=1-\sum_{k=1}^K{p_k^2} Gini(p)=∑k=1K(pk∗(1−pk))=1−∑k=1Kpk2
假如是二分类： G i n i ( p ) = 2 p ( 1 − p ) Gini(p)=2p(1-p) Gini(p)=2p(1−p)
样本集 D 中有 K 个类别，第 k 个类别的数目为 C k C_k Ck，则基尼系数: G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D) = 1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2 Gini(D)=1−∑k=1K(∣D∣∣Ck∣)2
样本集 D ，假如根据特性 A 的某个值 a ，把 D 分成 D1 好 D2 两部分，则在特性 A 的条件下，D 的基尼系数： G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
各人比力一下基尼系数表示和熵模子的表达式，二次运算比对数运算简单很多。但是基尼系数比熵模子误差大
对于二分类，基尼系数和熵之半的曲线：
从上图可以看出，基尼系数和熵之半的曲线非常接近，因此，基尼系数可以做为熵模子的一个近似替换。
CART分类树算法就是使用的基尼系数来选择决议树的特性。同时，为了进一步简化，CART分类树算法每次仅仅对某个特性的值进行二分，而不是多分，如许 CART 分类树算法创建起来的是二叉树，而不是多叉树。如许一可以进一步简化基尼系数的计算，二可以创建一个更加优雅的二叉树模子。
一连特性和离散特性改进
与 C4.5 思想相同：将一连特性离散化。
C4.5 使用信息增益来选择划分点。
CART 分类树使用基尼系数选择划分点
比如有 m 个样本的一连特性 A 有 m 个，
- 从小到大排列一连特性值 [ a 1 , a 2 , . . . , a m ] [a_1,a_2,...,a_m] [a1,a2,...,am] ，
- C 4.5 取相邻两个样本的平均数，一共取得 m - 1划分点，其中第 i 个划分点 T i = a i + ( a i + 1 ) 2 T_i=\frac{a_i+(a_i+1)}{2} Ti=2ai+(ai+1)。
- 对这 m - 1 个点，分别计算：以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为一连特性的二元离散分类点。比如取到的基尼系数最小点为 a t a_t at，那么小于 a t a_t at 的值的类别为 0，大于 a t a_t at 的值为 类别 1.
CART 分类树对离散值的处理思绪：不停的二分离散特性。
回忆下 ID3 或 C4.5，假如特性$ A\in{A_1,A_2,A_3}$ 被选中创建决议树节点，会在决议树上创建一个三叉的节点，如许导致决议是多叉树。
CART 分类树会将 A 拆成 {A1} 和 {A2 , A3} ， { A2 } 和 {A1 , A2} ,{ A3 } 和 { A1 , A2 } 分组，找基尼系数最小的组合，比如 { A1 } 和 {A2 , A3}，一个节点是 A1对应样本，另一个节点是不即是 A1 的样本（类似 One-Hot-Encoding），后续另有机会处理 {A2} , {A3}
分类树构建
CART 树的剪枝算法单独讲解。
算法输入：训练集D，基尼系数的阈值：min_gini，样本个数阈值：min_count
输出：决议树 T
- if len( D ) < min_count or 没有特性：return T
- if Gini( D ) < min_gini：return T
- 处理一连值和缺失值，同 C4.5
- 计算各个特性的各个特性值对应数据集D的基尼系数，求最小值$ A_k = min([Gini(f_i,f_{other})\quad for \quad f \quad in \quad features])$
- 根据最优特性和最优特性值，将数据数据集划分成两步分D1 和 D2，同时创建左右子节点。
- 对左右子节点调用 1 - 4步，生成决议树。
猜测：
假如样本落到某个叶子节点，二节点有多个训练样本，猜测概率就是叶子节点概率最大的类别。
回归树构建
CART 回归树和 CART 分类树的创建和猜测的主要区别
一连值
分类模子比力符适用基尼系数来度量特性的划分点的优劣。
方差的度量方式比力适合回归模子。
CART 回归树的度量目的：求出使D1 和 D2 各自集合的均方差最小，同时 D1 和 D2 的均方差之和最小。
表达式： m i n ⏟ A , s [ m i n ⏟ c 1 ∑ x i ∈ D 1 ( A , s ) ( y i − c 1 ) 2 + m i n ⏟ c 2 ∑ x i ∈ D 2 ( A , s ) ( y i − c 2 ) 2 ] \underbrace{min}_{A,s}[\underbrace{min}_{c_1} \sum_{x_i \in D_1(A,s){(y_i-c1)^2}+ \underbrace{ min}_{c_2} \sum_{x_i \in D_2(A,s)}{(y_i-c_2)^2}}] A,s min[c1 min∑xi∈D1(A,s)(yi−c1)2+c2 min∑xi∈D2(A,s)(yi−c2)2]
- c 1 c_1 c1 为 D1 数据集的样本输出的均值
- c 2 c_2 c2 为 D2 数据集的样本输出的均值
猜测
接纳最终叶子节点中均值大概中位数作为猜测效果。
CART 树的剪枝
CART 回归树和CART 分类树剪枝策略除了在度量方式上差别，其他完全相同。
CART 分类树：基尼系数
CART 回归树：均方差
决议树很容易过拟合，导致泛化本事差，所以需要剪枝。
CART 树剪枝思想：后剪枝
后剪枝：生成决议树，然后使用交织验证来检验各种剪枝的效果，选择泛化本事最好的剪枝策略。
CART 树剪枝算法两步：
剪枝的损失函数： C a ( T t ) = C ( T t ) + a ∣ T t ∣ C_a(T_t)=C(T_t)+a|T_t| Ca(Tt)=C(Tt)+a∣Tt∣
- a：正则化参数
- C ( T t ) C(T_t) C(Tt) 为训练数据的猜测误差，分类树是用基尼系数度量，回归树是均方差度量.
- ∣ T t ∣ |T_t| ∣Tt∣：子树T的叶子节点的数目。
a 越大，则剪枝剪的越锋利，生成的最优子树相比原生决议树就越偏小。
对于固定的 α，肯定存在使损失函数 C α ( T ) C_α(T) Cα(T)最小的唯一子树。
剪枝思绪
CART 小结
算法支持模子树结构特性选择一连值剪枝缺失值ID3分类多叉树信息增益不支持不支持不支持C4.5分类多叉树信息增益比支持支持支持CART分类，回归二叉树基尼系数，均方差支持支持支持 CART 树的缺点
- 不支持多变量决议树（multi-variate decision tree）。ID3，C4.5，CART 在做特性选择时都是选择最优的一个特性来做决议。但是大多数分类决议不应该由某一个特性决定，而是由一组特性决议。多变量决议树代表是 OC1
- 假如样本发送一点点的改动，就会导致树结构的剧烈改变。通过集成学习里的随机丛林的方法办理。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
