本文在我的知乎上同步更新：sklearn中的决策树（分类） – 知乎
Sklearn库有很多机器学习模型，不同的模型有着不同的特点，针对不同的问题，选取对应的模型，可以很好地解决问题。树模型作为经典的机器学习模型，可以做分类以及回归，分类模型中有DecisionTreeClassifier与ExtraTreeClassifier；回归模型中有DecisionTreeRegressor与ExtraTreeRegressor。
目前网上大多数对于决策树等模型的讲解，原理与代码总是割裂的。本文试图在理解原理的基础上，结合Python中sklearn库的相关代码，互为补充理解。有一些原理上的原则，在实际运用中并非如此，比如大多数博客会以离散指标作为讲解Gini指数判断纯度的依据，但其实sklearn的决策树代码只会把所有特征视为连续变量，并对其离散化处理；还有对于后剪枝算法CCP，很多博客只是罗列概念，没有给出模型中参数ccp_alpha的具体含义，以及
到底怎么算……
本文试图弥补原理与代码之间的GAP，并作为我自学的笔记，供诸君参考，算是抛砖引玉，如有不正之处或者侵权，还望及时指出。
1 决策树（分类）基本概念
顾名思义，决策树就是一棵树，一棵决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶子结点的路径对应了一个判定测试序列。
对于离散的分类任务，决策树最后生成的树叶是根据算法构建出的最优类别，如果没有限定决策树的最大高度等参数，树叶内的数据一般会是纯的，即一片树叶内只有一种类别，但是经过剪枝（后面会讲）操作后，叶节点的数据可能会不纯。
2 分类问题决策树生成原理
2.1 “纯度”判断
决策树学习的关键在于如何选择最优的划分属性，所谓的最优划分属性，对于分类而言，就是尽量使划分的样本属于同一类别，即”纯度”最高的属性。
那么，如何定义数据的”纯度”就成了问题的关键，现在的主流算法是CART算法，sklearn中DecisionTreeClassifier就是用的CART算法，其判别纯度的指标是entropy熵与Gini指数。
熵的公式为：
其中
表示有种类别，是取第种类的概率，实际计算直接用第i种类别所占的比例代替，熵越大，表示此时的混乱程度越大，数据越不纯。
如果利用某一种指标
将原数据 分为两类与 之后，在这个分类下，定义此时的 条件熵为
接着定义 信息增益：
基尼指数的公式为：
同样
表示有种类别， 是 取第种类的概率，直观上说，基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，所以基尼指数也是越大表示越混乱。
同样地，利用某一种指标
将原数据 分为两类与 之后，在这个分类下，定义此时的基尼指数为
相比于熵的对数运算，基尼指数只涉及平方与加法运算，所以在大数据量问题上，基尼指数有更快的运行速度。
2.2 CART算法思路
CART算法生成的决策树是二叉树，每一步只对某一个指标做出划分。如果特征是离散的取值，那么就对每个特征的每个不同的取值作为二叉树的判定标准，大于或者小于等于该值分成两类，并计算以该点分类后，新节点的信息增益(information entropy)或者基尼指数，以两个子节点的样本数占比进行加权计算；如果特征是连续的取值，那么以每两个相邻的特征取值的算术平均离散化。
具体来说，如果某一个特征
有 个连续的属性，那么对应的取值从小到大排列为 ， 以 为其n-1个划分点，将特征 离散化。
2.2.1 算法伪代码
设需要分类的数据为
，定义数据集内数据量为，属性集，算法的伪代码如下：
① 设定纯度判断阈值
与样本数量阈值 等防止树过深的参数
② 若
或 或没有特征，则停止，返回当前树，否则转③
③根据所有特征的值进行二分类，选出基尼指数最小或信息增益最大的那个特征的值作为分类依据，得到的两个子数据集
并返回②
2.2.2 计算实例
假设有如下数据集，住房一栏中1表示拥有住房，0表示没有住房；婚姻一栏中，0表示单身，1表示已婚，2表示离异；年收入一栏中单位为1000元；拖欠贷款一栏0表示不拖欠，1表示拖欠。
拖欠贷款数据集 住房婚姻年收入拖欠贷款1012500110000 0 7001112000295101600122200008510175000901
现在我们想构造一个决策树来拟合上述数据，根据前三列的特征数据，训练出一个决策树模型判断某个家庭会不会拖欠银行贷款。在sklearn的决策树CART算法中，其实没有所谓离散变量的特征，它将所有的特征均视为连续特征，根据上述提到的连续特征离散化的方式进行分类。
所以，对于住房来说，其分类的标准是以0.5为界限；对于婚姻来说，其分类标准是以0.5与1.5为界限；对于年收入来说，{65,72.5,80,87.5,92.5,97.5,110,122.5,172.5}是其分类指标集。现在依次计算以上述指标为二分类标准对应的基尼指数，如下表所示：
Gini指数 标准基尼指数住房0.50.343婚姻0.50.367婚姻1.50.400年收入650.400年收入72.50.375年收入800.343年收入87.50.417年收入92.50.400年收入97.50.300年收入1100.343年收入122.50.375年收入172.50.400
对于基尼指数具体的计算过程，举一个为例，如果以住房0.5为界限，那么会有如下状态表：
有房无房拖欠03不拖欠34
假设有住房的数据集为
，没住房的数据集为 ，则有， ，且有：
则有：
从上表可以看出，基尼指数最小的是以年收入97.5k为界限的分裂，那么对得到的两个子数据集
与 做同样地计算，最后可以得到完整的决策树。
2.2.3 决策树的剪枝处理
对于决策树的剪枝处理是为了应对决策树容易出现过拟合现象的应对办法。由于在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，会把训练集自身的一些特点当做所有一般性质而导致过拟合，所以可以通过主动去掉一些分支来降低过拟合的风险。
决策树的剪枝方法主要分为两类，”预剪枝”与”后剪枝”，概念如下：
预剪枝(pre-pruning)：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
后剪枝(post-pruning)：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。
对于这两种剪枝方法，各有优劣，其中后剪枝比预剪枝会保留更多的节点，不容易出现”欠拟合”问题；但是因为是先生成树，再对树进行剪枝，因此，时间开销比预剪枝大。
常用的是，先构建一棵决策树，然后根据特征重要性，筛选出重要的特征，再构建新的决策树。
对于预剪枝，在代码中我们可以用设定最大深度max_depth，叶节点最小样本数量min_samples_leaf等方式做到。
对于后剪枝，已经有一些比较成熟的算法，REP(Reduced-Error Pruning)、PEP(Pesimistic-Error Pruning)以及CCP(cost complexity pruning)是比较常见的，sklearn库中所运用的后剪枝算法就是CCP算法，ccp_alpha就是与之相关的参数。
下面重点说一下CCP算法即代价复杂性剪枝法。CCP算法为子树
定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数 。
其中代价指的是在剪枝过程中因子树T_t被叶节点替代而增加的错分样本;
复杂度表示剪枝后子树
减少的叶结点数; 则表示剪枝后树的复杂度降低程度与代价间的关系，定义为：
①
为节点 的错误代价，有公式：
②
为节点 的错分样本率：，其中 为 节点被错误划分的样本数量，为 节点总样本数
③
表示节点中样本占全部样本的比例： ，其中 为总样本数
④
为节点 的子树错误代价，有公式： ， 其中 为子树所有叶节点集
⑤
为子树 中的叶节点数
CCP算法步骤：
①按照上述公式从下往上计算每一个非叶节点的
值，每次都减掉 值最小的子树，从而得到一个集合 ，其中 表示之前算法得到的完整的树， 表示之前算法得到的树根。
②在集合
中选出泛化能力最强的树作为最终的模型。
但是在实际的代码中，我们一般会设定一个参数ccp_alpha，然后再对生成的决策树中非叶节点计算其
，选出其中最小的而且要小于预设定的ccp_alpha，这个非叶节点才会被剪枝为叶节点。所以最后比较的决策树集合是包含于 的。
2.3 决策树的Python代码
from sklearn import tree
import numpy as np
from io import StringIO
import pydotplus
X = np.array([[1, 0, 125],[0, 1, 100],[0, 0, 70],[1, 1, 120],
[0, 2, 95],[0, 1, 60],[1, 2, 220],[0, 0, 85],
[0, 1, 75],[0, 0, 90]])
y = np.array([[0], [0], [0], [0], [1],
[0], [0], [1], [0], [1]])
tree_model = tree.DecisionTreeClassifier(criterion='gini',
max_depth=None,
min_samples_leaf=1,
ccp_alpha=0.0)
tree_model.fit(X, y)
dot_data = StringIO()
feature_names = ['House', 'Marriage', 'Annual salary']
target_names = ['No default', 'Default']
tree.export_graphviz(tree_model,
out_file=dot_data,
feature_names=feature_names,
class_names=target_names,
filled=True,
rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("default.pdf")
针对前述问题，我们可以编写如上代码验证，并通过sklearn.tree中内置的可视化工具将决策树可视化呈现出来得到如下的决策树：
决策树
在这个决策树中，每个节点的第一行是分裂该节点所用的标准的名字以及数量指标；第二行表示判断纯度的指标；第三行是该节点所含样本数量；第四行表示不同的类别分别有多少样本数；第五行是该节点被标记的类别，以样本数量最多的那个类别为该节点的类别。
以这个决策树为例，我们可以来计算一下CCP算法中的
值，选择节点序号为1即图中白色框节点为计算对象，有：
同理，可以算出根节点对应的
。如果ccp_alpha设定的值超过0.30，那么经过后剪枝之后，这个决策树就只有一个节点了，初始设定如果在0.15到0.30之间，由于后剪枝是从下到上裁剪，所以不会直接剪枝到只剩一个根节点。
2.3.1 Python代码解析
①首先从sklearn中导入模组tree；导入numpy生成我们所需要的数据；从io库中导入StringIO模组，这个StringIO是用来将字符串读入内存的模组；导入pydotplus用来将导入内存的字符串转化为图像。
②然后利用numpy的array数组写入我们需要的数据，X是一个103的矩阵，表示特征；y是101的列向量，表示是否违约的类别。
③接着实例化类tree.DecisionTreeClassifier()为tree_model，其中有四个初始化参数最为重要，一是判断纯度的标准criterion，可以取’gini’或者’entropy’；二是设定树的最大深度max_depth，默认值为None，即没有限制，如果设定为某个整数k，则某个分支的深度达到k之后就不再分裂；三是每个叶节点样本数的最小值min_samples_leaf，默认为1；四是后剪枝算法中的参数ccp_alpha，默认值为0，即不进行后剪枝。实例化完之后利用tree_model.fit(X, y)就可以将模型训练好了。另外还有一些参数也可以用来调节、剪枝决策树，大家可以自行查阅。
④后面的工作是用来可视化我们得到的决策树，首先创建一个内存空间名为dot_data；然后指定我们生成的决策树中特征变量X对应的指标名字以及类的名字，利用tree模组中自带的tree.export_graphviz()函数将模型中的数据传入内存dot_data中，后面三个参数是用来修改最后树的形状的，可以自行设定；最后通过pydotplus画出树，并存到文件”default.pdf”中。
2.3.2 决策树的其他数量指标
根据我们上面代码得到的模型tree_model，我们可以接着输入以下代码查看一些数量指标：
x = np.array([[0,1,100]])
print(tree_model.predict(x))
print(tree_model.predict_proba(x))
print(tree_model.apply(x))
由于我们这个决策树模型最终得到的就是如果年收入在(80,97.5]区间内则会拖欠，其他情形均不拖欠(不用理会这个模型的合理性)，那么对应的结果分别是：
[0]
[[1. 0.]]
[4]
第一行表示[0,1,100]这个新数据根据拟合出来的模型会被分类为不拖欠；第二行表示一个概率向量，x取不拖欠的概率是1，拖欠的概率是0；第三行表示x最终被分在哪个节点内，代码中的决策树节点序号排序规则是从上到下，从左到右，根节点序号为0.
假如另有一批新数据X_test与y_test，那么利用如下代码可以查看原模型的拟合程度，即可查看这个训练出来的模型在新数据集下的泛化能力，函数所返回的是模型的可决系数
：
print(tree_model.score(X_test,y_test))
参考：
①相关概念参考周志华《机器学习》
②CCP算法参考决策树-剪枝算法（二） – DreamFaquir – 博客园
③计算例子参考决策树算法–CART分类树算法 – 知乎
Original: https://blog.csdn.net/qq_33761152/article/details/123976591
Author: 登高望远，倚树听泉
Title: sklearn中的决策树（分类）
相关阅读
Title: 人脸检测-人脸对齐-人脸识别原理及方法
目录
要想做人脸识别，首先需要检测出人脸子图和关键点，然后根据关键点对人脸进行对齐，然后对对齐后的人脸提取人脸特征并进行特征值比对，下面简单介绍下三个过程中的原理。
1.人脸检测
人脸检测就没什么说的了，就是检测出图像中的人脸和关键点，比如我们用yolov5-face做检测得到如下图片，
也可以使用 blazeface得到如下结果
当然也可以使用其他方法，比如mtcnn、SCRFD、RetinaFace。但是这些方法的目的都是得到人脸子图和关键点。
2 人脸对齐
要做人脸对齐就需要用到人脸特征点，人脸特征点, 又称为人脸关键点 (face landmark), 是人脸上具有明确语义的坐标点, 如鼻尖, 嘴角, 眼角等. 人脸对齐具体做法是: 利用最小二乘法求解当前人脸图像的关键点与预定义的标准人脸关键点 (通常是由统计得到的) 之间的空间变换矩阵 (一般是相似变换矩阵), 再在人脸图像上进行该空间变换矩阵对应的变换. 人脸对齐后的图像是标准尺寸的, 而且减小了人脸姿态, 尺度和偏移 (想想看, 相似变换矩阵中包含了旋转, 尺度和平移参数) 对人脸识别的影响。
其实人脸对齐可以简单的理解为就是为了把比如歪着的人脸、尺度不正常的人脸、在图像中位置偏移的人脸，都矫正成比较标准的人脸。
2.1 人脸对齐参考代码1
根据人脸关键点做人脸对齐face alignment—-C++实现_陈 洪 伟的博客-CSDN博客
2.2 人脸对齐参考代码2
可以使用opencv实现人脸对齐，可以参考
基于Landmark的人脸对齐以及裁剪方法 – horsetail – 博客园
2.3 人脸对齐参考代码3
人脸对齐的代码在SeetaFace2/FaceRecognizer/seeta/FaceRecognizerPrivate.cpp文件中是有的，可以借鉴，从下图中的mean_shape可以看到前面两个点的y坐标一样说明是两个眼睛，后面两个点的y坐标一样是嘴巴的两个点，中间第三个点是鼻子，这就是标准的人脸关键点。
具体github网址为：https://github.com/seetafaceengine/SeetaFace2
3 人脸识别
3.1 特征提取方法1—-分类网络
前面经过了人脸检测及人脸对齐，我们得到了对齐后的人脸子图，这时候我们一般使用一个分类网络提取人脸特征，一般使用分类层的前面一层的feature map作为人脸特征，例如我们可以使用Resnet50网络训练一个128类别的人脸分类网络，然后实际使用时候我们把倒数第二层的128个输出值作为特征向量。
3.2 特征提取方法2—-facenet
前面的特征提取方法是训练一个分类模型，然后取倒数第二层作为人脸特征值，这样的方法不够直接和效率低下。不够直接是指希望学习的指定层的特征可以很好的泛化到未知人脸上；效率低是指一般学习的特征维度很高（大于1000维），有的方法对提取的特征进行PCA降维处理，但这只是一个线性变换，可以通过一个网络层很简单的实现出来。
FaceNet是直接利用triplet loss训练模型输出128维的特征向量，triplets是由来自于一人的两张人脸图像和来自于另一个人的第三张图像组成，训练的目的是来自于同一人的人脸对之间的欧式距离要远小于来自于不同人的人脸对之间的欧氏距离。
相关资料介绍参考：
https://github.com/davidsandberg/facenet
https://github.com/timesler/facenet-pytorch
【人脸识别】FaceNet详解_姚路遥遥的博客-CSDN博客_facenet
facenet-pytorch库的简单使用 – 木易123 – 博客园
3.3 人脸比对
前面我们提取了人脸特征，加下来我们要做人脸比对，人脸比对就是把提取到的特征向量和底库中的特征向量进行比对，可以通过余弦距离或欧氏距离的方法求解相似度，得到比对得分，并和阈值进行比较，其中如果是小底库的嵌入式设备，底库可以使用sqlite数据库自己封装一个增删改查以及比对接口。
相关资料参考：
C++求欧氏距离_陈 洪 伟的博客-CSDN博客_c++ 欧式距离
特征值比对代码/计算相似度代码_陈 洪 伟的博客-CSDN博客_代码相似度对比
常用的相似度计算方法—-欧式距离、曼哈顿距离、马氏距离、余弦、汉明距离、切比雪夫距离、闵可夫斯基距离、马氏距离_陈 洪 伟的博客-CSDN博客
Python操作sqlite3数据库–增删改查，利用sqlite3实现轻量级图像搜索底库_陈 洪 伟的博客-CSDN博客
4 实际比对效果
生成的简单的测试底库如下所示(马赛克的为真实人名)，
实际测试结果如下图所示，刘德华的比对时，底库中的top4是正确的，
部分代码未开源，
后期会对该算法进行持续优化。
Original: https://blog.csdn.net/u013171226/article/details/123627357
Author: 陈 洪 伟
Title: 人脸检测-人脸对齐-人脸识别原理及方法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/223809/
转载文章受原作者版权保护。转载请注明原作者出处！
