SVG("./res/uml/Model__tree_0.svg")

"""
Explanation: 决策树在 sklearn 中的实现简介
0. 预前
本文简单分析 scikit-learn/scikit-learn 中决策树涉及的代码模块关系。
分析的代码版本信息是：
```shell
~/W/s/sklearn ❯❯❯ git log -n 1                                                                                                                                                         study/analyses_decision_tree
commit d161bfaa1a42da75f4940464f7f1c524ef53484f
Author: John B Nelson &#106;&#110;&#101;&#108;&#115;&#111;&#49;&#49;&#64;&#103;&#109;&#117;&#46;&#101;&#100;&#117;
Date:   Thu May 26 18:36:37 2016 -0400
Add missing double quote (#6831)

```
本文假设读者已经了解决策树的其本概念，阅读 sklearn - Decision Trees 有助于快速了解。 
1. 总纲
决策树的代码位于 scikit-learn/sklearn/tree 目录下，各文件大意说明如下：
tree
+-- __init__.py
+-- setup.py            
+-- tree.py             主文件
+-- export.py           导出树模型
+-- _tree.*             组建树的类
+-- _splitter.*         分割方法
+-- _criterion.*        不纯度评价
+-- _utils.*            辅助数据结构：栈和最小堆 
+-- tests/
    +-- __init__.py
    +-- test_tree.py
    +-- test_export.py
类之间的大致关系如下：
End of explanation
"""


SVG("./res/uml/Model___criterion_1.svg")

"""
Explanation: Tree.py 下定义了 BaseDecisionTree 基类，实现了完整的分类和回归功能，衍生出的子类主要用于封装初始化参数。两种子类的区别在于：DecisionTree* 类会遍历特征和值，从而找到最佳分割点，而 ExtraTree* 类会随机抽取特征和值，来寻找分割点。
下面是基类的训练方法 fit 流程：

检查参数。
设置评价函数。
创建分割方法：根据数据是否稀疏阵，生成相应类。
创建树：根据叶子数决定用深度优先还是评价优先。
调用树的构建方法：生成决策树。

代码如下，细节已经折叠：
python
  72 class BaseDecisionTree(six.with_metaclass(ABCMeta, BaseEstimator,
  73                                           _LearntSelectorMixin)):
  74     """Base class for decision trees.
  75 #+--  3 lines: Warning: This class should not be used directly.-------------------
  78     """
  79
  80     @abstractmethod
  81     def __init__(self,
  82 #+-- 30 lines: criterion,---------------------------------------------------------
 112
 113     def fit(self, X, y, sample_weight=None, check_input=True,
 114             X_idx_sorted=None):
 115         """Build a decision tree from the training set (X, y).
 116 #+-- 34 lines: Parameters---------------------------------------------------------
 150         """
 151
 152 #+--180 lines: random_state = check_random_state(self.random_state)---------------
 332
 333         # Build tree
 334         criterion = self.criterion
 335 #+--  6 lines: if not isinstance(criterion, Criterion):---------------------------
 341
 342         SPLITTERS = SPARSE_SPLITTERS if issparse(X) else DENSE_SPLITTERS
 343 #+--  9 lines: splitter = self.splitter-------------------------------------------
 352
 353         self.tree_ = Tree(self.n_features_, self.n_classes_, self.n_outputs_)
 354
 355         # Use BestFirst if max_leaf_nodes given; use DepthFirst otherwise
 356         if max_leaf_nodes &lt; 0:
 357             builder = DepthFirstTreeBuilder(splitter, min_samples_split,
 358                                             min_samples_leaf,
 359                                             min_weight_leaf,
 360                                             max_depth)
 361         else:
 362             builder = BestFirstTreeBuilder(splitter, min_samples_split,
 363                                            min_samples_leaf,
 364                                            min_weight_leaf,
 365                                            max_depth,
 366                                            max_leaf_nodes)
 367
 368         builder.build(self.tree_, X, y, sample_weight, X_idx_sorted)
 369
 370 #+--  3 lines: if self.n_outputs_ == 1:-------------------------------------------
 373
 374         return self
预测方法 predict 代码非常简单，调用 tree_.predict() 方法取得预测值：如果是分类问题，输出预测值最大的类；如果是回归问题，直接输出。
Python
 398     def predict(self, X, check_input=True):
 399         """Predict class or regression value for X.
 400 +-- 20 lines: For a classification model, the predicted class for each sample in X
 420         """
 421
 422         X = self._validate_X_predict(X, check_input)
 423         proba = self.tree_.predict(X)
 424         n_samples = X.shape[0]
 425
 426         # Classification
 427         if isinstance(self, ClassifierMixin):
 428             if self.n_outputs_ == 1:
 429                 return self.classes_.take(np.argmax(proba, axis=1), axis=0)        
 430
 431 +---  9 lines: else:--------------------------------------------------------------
 440
 441         # Regression
 442         else:
 443             if self.n_outputs_ == 1:
 444                 return proba[:, 0]
 445 +---  3 lines: else:--------------------------------------------------------------
sklearn 的决策树是 CART(Classification and Regression Trees) 算法，分类问题会转换成预测概率的回归问题，所以两类问题的处理方法是相同的，主要区别在评价函数。
2 模块简介
2.0 评价函数
_criterion.* 是评价函数相关的文件，用 Cython 实现，.pxd 和 .pyx 文件分别对等 C 语言中的 .h 和 .c 文件。
下面是类的关系图：
End of explanation
"""


SVG("./res/uml/Model___splitter_2.svg")

"""
Explanation: 对于分类问题，sklearn 提供了 Gini 和 Entropy 两种评价函数；
默认会用 Gini 。

Decision Trees: “Gini” vs. “Entropy” criteria


对于回归问题，则提供了 MSE（均方差）和 FriedmanMSE。

默认会用 MSE 。
FriedmanMSE 用于 gradient boosting。

在实际使用中，我们应该都测试下同的评价函数。
2.1 分割方法
_splitter.* 是分割方法相关的文件。
下面是类的关系图：
End of explanation
"""


SVG("./res/uml/Model___tree_3.svg")

"""
Explanation: Splitter 基类依数据储存方式（实阵或稀疏阵）衍生为 BaseDenseSplitte 和 BaseSparseSplitter。在这之下根据阈值的寻优方法再细分两类：Best*Splitter 会遍历特征的可能值，而 Random*Splitter 则是随机抽取。
2.2 树的组建方法
_tree.* 是树组建方法相关的文件。
下面是类的关系图：
End of explanation
"""


