最小二乘回归树生成算法
- 在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上地输出值，构建二叉决策树
输入：训练数据集D
输出：回归树f ( x )
步骤：
（1）遍历变量j 对固定的切分变量j 扫描切分点s ，得到满足下面式子的( j , s )
（2）用选定的( j , s ) 划分区域并决定相应的输出值
3）对两个子区域调用(1)(2)步骤， 直至满足停止条件
4）将输入空间划分为M 个区域R 1 , R 2 , … , R M 生成决策树：
CART分类树的生成
- 分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点
- 概率分布的基尼指数定义
如果样本集合D 根据特征A 是否取某一可能值a 被分割成D 1 和D 2 两部分，则在特征A的条件下，集合D 的基尼指数定义为
输入：训练数据集D DD，停止计算的条件
输出：CART决策树
根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树：
设结点地训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A ，对其可能取得每个值a，根据样本点对A = a 的测试为“是”或“否”将D 分成D 1 和D 2 两部分，计算A = a 时的基尼指数
在所有可能的特征A 以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依照最优特征和最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
对两个子结点递归地调用1、2，直至满足停止条件
生成CART决策树
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于指定阈值，或者没有更多特征
例5.1
根据书上的例题5.1，用决策树实现
def create_data(): datasets = [['青年', '否', '否', '一般', '否'], ['青年', '否', '否', '好', '否'], ['青年', '是', '否', '好', '是'], ['青年', '是', '是', '一般', '是'], ['青年', '否', '否', '一般', '否'], ['中年', '否', '否', '一般', '否'], ['中年', '否', '否', '好', '否'], ['中年', '是', '是', '好', '是'], ['中年', '否', '是', '非常好', '是'], ['中年', '否', '是', '非常好', '是'], ['老年', '否', '是', '非常好', '是'], ['老年', '否', '是', '好', '是'], ['老年', '是', '否', '好', '是'], ['老年', '是', '否', '非常好', '是'], ['老年', '否', '否', '一般', '否'], ] labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别'] # 返回数据集和每个维度的名称 return datasets, labels datasets, labels = create_data() train_data = pd.DataFrame(datasets, columns=labels)
# 经验熵 def entropy(datasets): data_length = len(datasets) label_count = {} for i in range(data_length): label = datasets[i][-1] if label not in label_count: label_count[label] = 0 label_count[label]+=1 ent = -sum([( p/data_length) * log(p/data_length,2) for p in label_count.values()]) return ent # 经验条件熵 def condition_entropy(datasets,axis = 0): data_length = len(datasets) feature_sets = {} for i in range(data_length): feature = datasets[i][axis] if feature not in feature_sets: feature_sets[feature] = [] feature_sets[feature].append(datasets[i]) condi_ent = sum([ (len(p) / data_length)*entropy(p) for p in feature_sets.values()]) #print(feature_sets) return condi_ent # 信息增益 def info_gain(ent,condi_entropy): return ent - condi_entropy def info_gain_train(data_sets): count = len(datasets[0]) - 1 ent = entropy(datasets) best_feature = [] for c in range(count): c_info_gain = info_gain(ent,condition_entropy(datasets,axis=c)) best_feature.append((c,c_info_gain)) print("特征（{}）的信息增益为： {:.3f}".format(labels[c],c_info_gain)) best = max(best_feature, key=lambda x:x[-1]) print( '特征({})的信息增益最大，选择为根节点特征'.format(labels[best[0]])) info_gain_train(datasets)
特征(年龄) - info_gain - 0.083 特征(有工作) - info_gain - 0.324 特征(有自己的房子) - info_gain - 0.420 特征(信贷情况) - info_gain - 0.363 特征(有自己的房子)的信息增益最大，选择为根节点特征
例5.3
利用ID3算法生成决策树
# 定义节点类 二叉树 class Node: def __init__(self,root=True,label=None,feature_name = None, feature = None): self.root = root self.label = label self.feature_name = feature_name self.feature = feature self.tree = {} self.result = {'label:':self.label,'feature':self.feature,'tree':self.tree} def __repr__(self): return '{}'.format(self.result) def add_node(self,val,node): self.tree[val] = node def predict(self,features): if self.root is True: return self.label return self.tree[features[self.feature]].predict(features)
class DTree: def __init__(self,epsilon=0.1): self.epsilon = epsilon self._tree = {} # 经验熵 @staticmethod #静态方法可以不实例化调用 def entropy(datasets): data_length = len(datasets) label_count = {} for i in range(data_length): label = datasets[i][-1] if label not in label_count: label_count[label] = 0 label_count[label] += 1 ent = -sum([(p / data_length) * log(p / data_length, 2) for p in label_count.values()]) return ent # 经验条件熵 def condition_entropy(self,datasets,axis = 0): data_length = len(datasets) feature_sets = {} for i in range(data_length): feature = datasets[i][axis] if feature not in feature_sets: feature_sets[feature] = [] feature_sets[feature].append(datasets[i]) condi_ent = sum([ (len(p) / data_length)*self.entropy(p) for p in feature_sets.values()]) return condi_ent # 信息增益 @staticmethod def info_gain(ent,condi_entropy): return ent - condi_entropy def info_gain_train(self, datasets): count = len(datasets[0]) - 1 ent = self.entropy(datasets) best_feature = [] for c in range(count): c_info_gain = self.info_gain(ent,self.condition_entropy(datasets,axis=c)) best_feature.append((c,c_info_gain)) print("特征（{}）的信息增益为： {:.3f}".format(labels[c],c_info_gain)) best = max(best_feature, key=lambda x:x[-1]) return best def train(self,train_data): _,y_train,features = train_data.iloc[:,:-1],train_data.iloc[:,-1],train_data.columns[:-1] # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T if len(y_train.value_counts()) == 1: return Node(root=True, label = y_train.iloc[0]) # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T if len(features) == 0: return Node(root= True, label=y_train.value_counts().sort_values(ascending=False).index[0]) # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征 max_feature, max_info_gain = self.info_gain_train(np.array(train_data)) max_feature_name = labels[max_feature] # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T if max_info_gain < self.epsilon: return Node(root=True,label= y_train.value_counts().sort_values(ascending=False).index[0]) # 5,构建Ag子集 node_tree = Node(root = False,feature_name= max_feature_name, feature= max_feature) feature_list = train_data[max_feature_name].value_counts().index for f in feature_list: sub_train_df = train_data.loc[train_data[max_feature_name] == f].drop([max_feature_name],axis=1) # 6, 递归生成树 sub_tree = self.train(sub_train_df) node_tree.add_node(f, sub_tree) return node_tree def fit(self,train_data): self._tree = self.train(train_data) return self._tree def predict(self,X_test): return self._tree.predict(X_test)
datasets, labels = create_data() data_df = pd.DataFrame(datasets, columns=labels) dt = DTree() tree = dt.fit(data_df) print(tree) print(dt.predict(['老年', '否', '否', '一般']))
{'label:': None, 'feature': 2, 'tree': {'否': {'label:': None, 'feature': 1, 'tree': {'否': {'label:': '否', 'feature': None, 'tree': {}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}} '否'
scikit-learn 实现
当然，我们也可以直接用sklearn来实现决策树
# scikit-learn 实现 from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split def create_data(): iris = load_iris() df = pd.DataFrame(iris.data, columns=iris.feature_names) df['label'] = iris.target df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label'] data = np.array(df.iloc[:100, [0, 1, -1]]) # print(data) return data[:,:4], data[:,-1] X, y = create_data() X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3) from sklearn.tree import DecisionTreeClassifier clf = DecisionTreeClassifier() clf.fit(X_train, y_train) print(clf.fit(X_train, y_train)) print(clf.score(X_test, y_test))
第5章决策树-习题
习题5.1
根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。
解答：
表5.1 贷款申请样本数据表
from sklearn.tree import DecisionTreeClassifier from sklearn import preprocessing import numpy as np import pandas as pd from sklearn import tree import graphviz features = ["年龄", "有工作", "有自己的房子", "信贷情况"] X_train = pd.DataFrame([ ["青年", "否", "否", "一般"], ["青年", "否", "否", "好"], ["青年", "是", "否", "好"], ["青年", "是", "是", "一般"], ["青年", "否", "否", "一般"], ["中年", "否", "否", "一般"], ["中年", "否", "否", "好"], ["中年", "是", "是", "好"], ["中年", "否", "是", "非常好"], ["中年", "否", "是", "非常好"], ["老年", "否", "是", "非常好"], ["老年", "否", "是", "好"], ["老年", "是", "否", "好"], ["老年", "是", "否", "非常好"], ["老年", "否", "否", "一般"] ]) y_train = pd.DataFrame(["否", "否", "是", "是", "否", "否", "否", "是", "是", "是", "是", "是", "是", "是", "否"]) # 数据预处理 le_x = preprocessing.LabelEncoder() le_x.fit(np.unique(X_train)) X_train = X_train.apply(le_x.transform) le_y = preprocessing.LabelEncoder() le_y.fit(np.unique(y_train)) y_train = y_train.apply(le_y.transform) # 调用sklearn.DT建立训练模型 model_tree = DecisionTreeClassifier() model_tree.fit(X_train, y_train) # 可视化 dot_data = tree.export_graphviz(model_tree, out_file=None, feature_names=features, class_names=[str(k) for k in np.unique(y_train)], filled=True, rounded=True, special_characters=True) graph = graphviz.Source(dot_data) graph
习题5.2
已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。
表5.2 训练数据表
解答：
决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
import numpy as np class LeastSqRTree: def __init__(self, train_X, y, epsilon): # 训练集特征值 self.x = train_X # 类别 self.y = y # 特征总数 self.feature_count = train_X.shape[1] # 损失阈值 self.epsilon = epsilon # 回归树 self.tree = None def _fit(self, x, y, feature_count, epsilon): # 选择最优切分点变量j与切分点s (j, s, minval, c1, c2) = self._divide(x, y, feature_count) # 初始化树 tree = {"feature": j, "value": x[s, j], "left": None, "right": None} if minval < self.epsilon or len(y[np.where(x[:, j] <= x[s, j])]) <= 1: tree["left"] = c1 else: tree["left"] = self._fit(x[np.where(x[:, j] <= x[s, j])], y[np.where(x[:, j] <= x[s, j])], self.feature_count, self.epsilon) if minval < self.epsilon or len(y[np.where(x[:, j] > s)]) <= 1: tree["right"] = c2 else: tree["right"] = self._fit(x[np.where(x[:, j] > x[s, j])], y[np.where(x[:, j] > x[s, j])], self.feature_count, self.epsilon) return tree def fit(self): self.tree = self._fit(self.x, self.y, self.feature_count, self.epsilon) @staticmethod def _divide(x, y, feature_count): # 初始化损失误差 cost = np.zeros((feature_count, len(x))) # 公式5.21 for i in range(feature_count): for k in range(len(x)): # k行i列的特征值 value = x[k, i] y1 = y[np.where(x[:, i] <= value)] c1 = np.mean(y1) y2 = y[np.where(x[:, i] > value)] c2 = np.mean(y2) y1[:] = y1[:] - c1 y2[:] = y2[:] - c2 cost[i, k] = np.sum(y1 * y1) + np.sum(y2 * y2) # 选取最优损失误差点 cost_index = np.where(cost == np.min(cost)) # 选取第几个特征值 j = cost_index[0][0] # 选取特征值的切分点 s = cost_index[1][0] # 求两个区域的均值c1,c2 c1 = np.mean(y[np.where(x[:, j] <= x[s, j])]) c2 = np.mean(y[np.where(x[:, j] > x[s, j])]) return j, s, cost[cost_index], c1, c2
train_X = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]).T y = np.array([4.50, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00]) model_tree = LeastSqRTree(train_X, y, .2) model_tree.fit() model_tree.tree
{'feature': 0, 'value': 5, 'left': {'feature': 0, 'value': 3, 'left': 4.72, 'right': 5.57}, 'right': {'feature': 0, 'value': 7, 'left': {'feature': 0, 'value': 6, 'left': 7.05, 'right': 7.9}, 'right': {'feature': 0, 'value': 8, 'left': 8.23, 'right': 8.85}}}
根据上面程序的输出，可得到用平方误差损失准则生成一个二叉回归树：
习题5.3
证明 CART 剪枝算法中，当α 确定时，存在唯一的最小子树T α 使损失函数C α ( T ) 最小。
解答：
**第1步：**内部节点是否剪枝只与以该节点为根节点的子树有关。
剪枝过程：
计算子树的损失函数：
其中，
是叶结点个数，k是类别个数。
有剪枝前子树T 0 剪枝后子树T 1 满足C α ( T 1 ) ⩽ C α ( T 0 ) 则进行剪枝。
**第2步（反证法）：**假设当α \alphaα确定时，存在两颗子树T 1 , T 2 都使得损失函数C α 最小。
第1种情况：假设被剪枝的子树在同一边，易知其中一个子树会由另一个子树剪枝而得到，故不可能存在两个最优子树，原结论得证。
第2种情况：假设被剪枝的子树不在同一边，易知被剪枝掉的子树都可以使损失函数C α最小，故两颗子树都可以继续剪枝，故不可能存在两个最优子树，原结论得证。
习题5.4
证明 CART 剪枝算法中求出的子树序列{ T 0 , T 1 , ⋯ , T n } \{T_0,T_1,\cdots,T_n\}{T
0
,T
1
,⋯,T
n
}分别是区间α ∈ [ α i , α i + 1 ) \alpha \in [\alpha_i,\alpha_{i+1})α∈[α
i
,α
i+1
)的最优子树T α T_{\alpha}T
α
，这里i = 0 , 1 , ⋯ , n , 0 = α 0 < α 1 < ⋯ , α n < + ∞ i=0,1,\cdots,n,0=\alpha_0 < \alpha_1 < \cdots, \alpha_n < +\inftyi=0,1,⋯,n,0=α
0
<α
1
<⋯,α
n
<+∞。
解答：
原结论可以表述为：将α \alphaα从小增大，0 = α 0 < α 1 < ⋯ < α n < + ∞ ，在每个区间[ α i , α i + 1 ) 中，子树T i 是这个区间里最优的。
**第1步：**易证，当α = 0 时，整棵树T 0是最优的，当α → + ∞时，根结点组成的单结点树（即T n）是最优的。
第2步：
由于每次剪枝剪的都是某个内部结点的子结点，也就是将某个内部结点的所有子结点回退到这个内部结点里，并将这个内部结点作为叶子结点。因此在计算整体的损失函数时，这个内部结点以外的值都没变，只有这个内部结点的局部损失函数改变了，因此本来需要计算全局的损失函数，但现在只需要计算内部结点剪枝前和剪枝后的损失函数。
从整体树T 0 开始剪枝，对T 0 的任意内部结点t
剪枝前的状态：有∣ T t ∣
个叶子结点，预测误差是C ( T t )
剪枝后的状态：只有本身一个叶子结点，预测误差是C ( t )
因此剪枝前的以t tt结点为根结点的子树的损失函数是
剪枝后的损失函数是
易得，一定存在一个α \alphaα使得C α ( T t ) = C α ( t )这个值为
可知，找到α 即找到了子结点t ，即完成了剪枝，得到最优子树T 1
根据书中第73页，采用以下公式计算剪枝后整体损失函数减少的程度：
在T 0 中剪去g ( t ) 最小的T t，将得到的子树作为T 1 ，同时将最小的g ( t ) 设为α 1，T 1 为区间[ α 1 , α 2 )的最优子树。依次类推，子树T i T_iT 是区间[ α i , α i + 1 ) 里最优的，原结论得证。
