决策树的著名算法CART，它解决了ID3算法的2个不足，既能用于分类问题，又能用于回归问题

　　CART算法的主体结构和ID3算法基本是相同的，只是在以下几点有所改变：

　　选择划分特征时，ID3使用信息熵量化数据集的混乱程度;CART使用基尼指数和均方误差量化数据集的混乱程度。

　　选定某切分特征时，ID3算法使用该特征所有的取值进行切分，例如一个特征有k个取值，数据集则被切分成K份，创建k个子树;CART算法使用某一阈值进行二元切分，即在特征值的取值范围区间内选择一个阈值t，将数据集切分成两份，然后用一个子集(大于t)构造左子树，使用另一个数据子集(小于t)构造右子树，因此CART算法创建的就是二叉树。

　　对于以用于创建内部节点的特征，在后续运算中(创建子树中的节点时)，ID3算法不会再次使用它作为内部节点;CART算法可能会再次使用它创建其他内部节点

　　CART分类树：

　　CART分类树的构造算法为递归算法，流程如下：

　　1.如果当前数据集D中样本数量小于“最小切分数”，或D的基尼指数小于“基尼指数阈值”：

　　创建叶节点，节点的值为数据集D中出现最多的类标记

　　2. 否则

　　创建内部节点

　　使用每一个布尔值特征将数据集切分成D1，D2，并计算切分后基尼指数降低的值，从而找到最佳切分特征

　　使用由最佳切分特征切分得到的D1，D2，递归调用CART分类树构造算法，创建左右子树

　　将当前内部节点作为两颗子树的父节点

　　基尼指数：

　　假设数据集D中有K个分类，其样本总数为|D|，每个分类放入样本个数分别为|D1|,|D2|,...|Dk|，则一个样本属于第i类的概率为：

　　数据集D的基尼指数定义如下：

　　类似条件熵，也可以定义在特征A条件下D的基尼指数。CART算法总会动态的吧所有特征都转换为布尔值特征，因此数据集D总可以根据某一布尔特征A切分成D1和D2两个子集，在特征A条件下D的基尼指数定义如下：

　　CAR分类树构造算法在选择切分特征时，只需计算每一个特征条件下的基尼指数，然后选择其中使得基尼指数最小的特征。 郑州哪里做人流好 http://www.kdrlyy.com/

　　代码如下：

　　import numpy as np

　　from sklearn.preprocessing import LabelEncoder

　　from sklearn.model_selection import train_test_split

　　from sklearn.metrics import accuracy_score

　　class CartClassificationTree:

　　class Node:

　　'''树节点类'''

　　def __init__(self):

　　self.value = None

　　# 内部叶节点属性

　　self.feature_index = None

　　self.feature_value = None

　　self.left = None

　　self.right = None

　　def __str__(self):

　　if self.left:

　　s = '内部节点