推荐|Decision Tree（决策树--ID3，C4.5，CART）

决策树基本思想：

所谓三思而后行，步步为营。
这里写图片描述

决策树无处不在，在生活很常见。就让我继续沿用好朋友这个比方吧。比如，我们如何认定一个人是我们的好朋友呢？别回答我：靠感觉啊！我觉得感觉这种东西不就是经过层层神经元，然后大脑产生的一个信号？在一定程度上也是可以抽象出来的，比如神经网络就是模仿了人脑的某些机制。有关神经网络的部分之后总结，先回到主题，让我们理智的，简单的判断一下好朋友的基准，比如TA首先得是个人？得长得好看？得和我们有共同爱好？得乐观向上？得编的一手好程序？对于个人来讲会有不同的选择，也就是对上面这些IF条件进行yes or no的判断，最终可以得到一个判断标准，而这个判断正是我们想要的一棵决策树，然后我们就可以利用这个由老好朋友得出的判断标准去寻找新的好朋友啦。
kNN篇提过它的最大问题就是无法给出数据的内在含义，而决策树在处理多分类问题相较与kNN的优势就是在于数据形式非常便于理解。为什么？它是一种实现分治策略的层次数据结构。它的层次安排使涵盖输入的区域可以快速的确定，例如像我们举的例子，好朋友分类的决策是二元的，那么每次都可以去掉一半的实例，可以轻松的将决策说变成一组易理解的IF-THEN规则。

这里写图片描述

具体的算法，因为决策树的内部由一些决策节点和终端树叶组成，每个决策节点实现一个具有离散输出的测试函数，标记分支。给定一个输入，在每个节点应用一个测试，并根据测试的输出确定一个分支，这一过程从根节点开始，并递归地重复，直至到达一个树叶节点。
那么用哪个条件特征先做if可以使结果最优呢？1970年代，一个叫J Ross Quinlan的人用信息论中的熵（entropy）来度量决策树的决策选择过程得到了很好的效果，这就是决策树最初的高效原型迭代Dichotomiser 3（Iterative Dichotomiser 3，ID3）。熵描述了事物的不确定性，越不确定的事物熵就越高，所以用它来度量可以尽可能的提升划分过程中分支结点的“纯度”（purity）。对于变量X的熵表示为： $H(X)=\sum_{i=1}^n p_i log p_i$
其中n代表X取值，p为概率。考虑到不同分支结点所包含的样本树不同，可以赋予一定的权重W（即某属性a的个数S占整个数据集的比率），算出某属性a的信息增益（Information gain）： $I(X，a)=H（x）-\sum_{i=1}^n WH（S）$
有了度量方法，我们就可以循环计算当前可选的所有属性的信息增益，每次选择最大的那个特征，并枚举该特征的每一个可能值，对每个值都建立一颗子树，然后将该特征从待选特征表里删除，直至信息增益小于某个阈值或者已经没有特征可以用了。

算法实现：（Python）

from math import log
import operator
import copy
def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    return dataSet, labels

def calcShannonEnt(dataSet):#计算熵
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:#为所有可能的分类创造字典
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): #键值是最后一列的数值
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) 
    return shannonEnt
    
def splitDataSet(dataSet, axis, value):#分割数据集。参数为数据集，属性，属性值
    retDataSet = []#为了不修改原来的数据集，新建一个
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis] 
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

#发现出当前特征相同的特征值，就提取出来，这里是把剩下的特征值和结果单独抽取！！！！Append是添加，extend是合并。
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1 #最后一个数据是labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):   
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)     
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain         
            bestFeature = i
    return bestFeature

def majorityCnt(classList):#出现次数最多的，做投票表决
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    labels = copy.copy(labels)#由于传址参数的问题。故增加一行代码
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): #巧用count()，统计分类列表中与第一个结果相同的个数，若该个数等于数组总长度，则说明所有记录归属同一类别，停止划分。
        return classList[0]
    if len(dataSet[0]) == 1: 
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])#这句本来是删除已经划分的属性，但labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改，所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list。解决方法就是增加一个copy。当然了，要import copy模块！！！
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:] #函数参数传递是列表类型时，引用传递。不改变原始数据。
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

#算法：1.类别完全相同就停止划分2.遍历完所有就返回出现次数最多的。
def classify(inputTree,featLabels,testVec):#输入参数为决策树，属性，测试
    firstStr = list(inputTree.keys())[0]#获得属性名称
    secondDict = inputTree[firstStr]#获得该属性下的字典
    featIndex = featLabels.index(firstStr)#反查属性id
    key = testVec[featIndex]#获得测试的值
    valueOfFeat = secondDict[key]#该值对应的子节点
    if isinstance(valueOfFeat, dict): #如果子节点是字典，则继续划分
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel
    
myDat,labels=createDataSet()
myTree=createTree(myDat,labels)
print(classify(myTree,labels,[1,0]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

可是ID3算法也有很多的问题：

想用朋友的年龄值做特征怎么办？不能处理连续特征。
对于连续值怎么计算信息熵？将连续的特征离散化就可以了。取相邻两样本值的平均数，共取n-1个划分点，对于这n-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

某些类型的人多势众怎么办？结果容易偏向取值多的。
换一种度量方法。选用新的属性选择标准–信息增益和特征熵的比值。

无法知道某些朋友在某些特征的取值怎么办？缺失值处理。
宁缺毋滥。先将他们划入所有分支。或者提前对缺失值进行处理。

太贴近老好朋友的决策树，无法判断新好朋友？过拟合问题。
剪枝。一般有预剪枝（prepruning）或后剪枝（postpruning），预剪枝是在生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点；后剪枝是先生成决策树后自底向上对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提高，则将该子树替换成叶结点。

其实以上四大点都是C4.5算法对ID3的改进，C4.5还提供了决策树与等价规则集的转换功能，便于人更好的理解。
这里写图片描述

虽然C4.5已经改进不少的问题，但是它还是有诸如选择偏向，不能用于回归，多叉树效率不高等的问题，所以分类和回归树算法（Classification and regression tree，CART）又进行了优化。正如它的名字，分类回归树， CART既能做回归，也能做分类。 分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。（文末有一个树回归的代码，可视化看出来会比较奇怪，但实际上回归树只是将原先的输出类别A、B、C，变成了输出一个预测数值）。

CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。 $\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]$ c1为D1数据集的样本输出均值，c2为D2数据集的样本输出均值。对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。
所以如果是分类树，将选择能够最小化分裂后节点GINI值的分裂属性；如果是回归树，选择能够最小化两个节点样本方差–均方误差（均方误差越小即代表分类的数值很相近，效果就越好）的分裂属性。在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。

这里写图片描述

CART在回归树用均方差，分类树采用基尼指数。
######基尼系数原本是经济学里的一个概念。基尼系数是1943年美国经济学家阿尔伯特·赫希曼根据劳伦茨曲线所定义的判断收入分配公平程度的指标。基尼系数是比例数值，在0和1之间，是国际上用来综合考察居民内部收入分配差异状况的一个重要分析指标。其具体含义是指，在全部居民收入中，用于进行不平均分配的那部分收入所占的比例。基尼系数最大为“1”，最小等于“0”。前者表示居民之间的收入分配绝对不平均，即100%的收入被一个单位的人全部占有了；而后者则表示居民之间的收入分配绝对平均，即人与人之间收入完全平等，没有任何差异。但这两种情况只是在理论上的绝对化形式，在实际生活中一般不会出现。因此，基尼系数的实际数值只能介于0～1之间，基尼系数越小收入分配越平均，基尼系数越大收入分配越不平均。国际上通常把0.4作为贫富差距的警戒线，大于这一数值容易出现社会动荡。
基尼值定义为： $\sum\limits_{n=1}^{n}p_n(1-p_n) = 1- \sum\limits_{n=1}^{n}p_n^2$
同样的可以得到基尼指数： $\frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$
那么对于通过计算Gini指数便可以指导建树了。
在这里插入图片描述
除此CART还固定了只建二叉树，每一次分裂会产生两个子节点，加快了建树的速度。另外通过上图可以看到叶子节点会有相应的“分数”，在做预测时可以算出每一类的“分数”来做评判的特点可以使整个进程更快，具体如何计算本篇不记录。而这个快的特点在它的变体XGBoost体现的尤为突出，也使得这一技术基本上横扫了大多数的数据挖掘任务！

几个特征之间有联系？多值偏向问题。
处理多值偏向的改进算法，还有些有基于特征间关联度的，基于统计估计的，还有一种基于灰色关联度（GDA）的改进算法，其基本思想是根据数列的几何关系或曲线的相似程度来判别因素间的关联程度。
Med Gen算法，它是基于C4.5的改进，它在选择特征之后到建立相应的决策树的过程中间增加了对数据集的预处理。具体第一步是面向特征规约的方法实现对数据集的水平压缩，第二步进行属性相关分析，根据分析结果从数据中去除分类属性依赖较小的数据，实现读数据集的垂直压缩。
卡方自动交互检测法(chi-squared automatic interaction detector,CHAID)，是一种基于调整后的显着性检验（邦费罗尼检验）决策树技术。最早由Kass于1980年提出，其核心思想是：根据给定的反应变量和解释变量对样本进行最优分割，按照卡方检验的显著性进行多元列联表的自动判断分组。利用卡方自动交互检测法可以快速，有效地挖掘出主要的影响因素，它不仅可以处理非线性和高度相关的数据，而且可以将缺失值考虑在内，能克服传统的参数检验方法在这些方面的限制,结果的解释也简单明了。
SLIQ算法（Su-pervised Learning In Quest），是一个高速可扩展的算法，采用特殊的数据结构，将输入的数据分解成多个属性表，在它的运行中，每次只需要保留一个属性表，从而达到了处理海量数据的目的。

进一步探究过拟合问题。
构建决策树过程是一个不断递归直到最后的过程，而这样做的结果是树深度变深，叶节点过多，从而造成过拟合，预测结果会很差，特别是在训练的数据中一般掺杂噪音的情况下。除了采用剪枝来解决外，还可以用k-fold cross validation来计算使分类误差最小化时提前停止，或者不纯度下降差阈值来限制，提前停止建树。比如scikit-learn就设定了叶结点数的阈值，设定限制树的深度等，详见下面的应用举例。
造成树深度太大的另一个可能的原因是由于每次都选用最好的特征进行分类，但还是可能存在一些特征对分类很有用，尽管不是像最好的特征那样有用，所以采用一次性对多个特征进行分类的多变量决策树就出现了，代表OC1算法，它先贪心地寻找每个属性的最优权值，在局部优化的基础上再对分类的边界进行随机的扰动以试图找到更好的边界。还可以使用MBDT度量数据相似性。
这里写图片描述
(线性多变量决策树，节点可安放任意超平面。)

老好朋友某些性格无明显偏向？正反比例问题。
比如说恰好这些朋友中是否喜欢机器学习的人数是一半一半的比例，那么结果误差会比较大。可以看出决策树是很依赖数据集中的正反比例，如果正反比例相同，原先的方法可能就不那么适用了。改进的方法有比如IBLE算法，它利用信道容量的概念作为度量方法，所以它不依赖于正反比例，而是依赖于正，反的特征取值的选择量。各特征的的正例标准值由译码函数决定。判断正例，反例的阈值是由实例中权值的变化规律来确定的。

一旦有新好朋友的加入，标准大变化？容易被干扰的决策树。
正如你不可能一直之和那几个朋友交往一样，数据不一定是不变的，随着新数据的产生，决策树可能会剧烈动荡。而且在实际运动决策树算法时，为了小数量的新数据再重新生成一棵庞大的决策树在效率上是不可取的，所以科学家们提出了增量学习（incremental），即在接收到新样本后可对已学得的模型进行调整，而不用重新开始学习，主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构，代表算法有ID4，ITI，ID5R等，增量学习可有效的降低每次接收到新样本后的训练时间的开销，只不过在多步增量学习后的模型会与基于全部数据训练而得的模型有较大的差别。
不过虽然决策树是很容易被干扰，但是这个特性非常适合集成学习（ensemble learning）。它俩的组合使准确率得到了很大的提升。除了和集成学习结合，还可以引入线性分类器的最小二乘法，也就是在决策树的叶结点上嵌入神经网络。比如RLSE（递归最小二乘估计器），在新数据和新参数适应过程中递归得到最小二乘估计器，最后再用随机森林的方法。

树为什么不需要归一化
因为数值放缩不影响分类点的位置，总归都是排序。而且树模型是不能梯度下降的，因为它寻找最优点是阶跃式，此处不可导，也没有求导的必要，所以不需要归一化。

但为什么在Adaboost，AVM，LR的树形要归一化呢？
因为对于线性模型，特征值差别很大的时候，等高线是椭圆形，而归一化后会变成原型，方便迭代。

DT应用：
sklearn DecisionTreeClassifier参数说明：
DecisionTreeClassifier(class_weight=None，criterion=‘gini，max_depth=None,max_features=None，max_leaf_nodes=None，min_impurity_split=1e-07，min_samples_leaf=1，min_samples_split=2，min_weight_fraction_leaf=0.0，presort=False,，random_state=None，splitter=‘best’)

class_weight=None：类别权重。
criterion=‘gini："gini"代表基尼系数，"entropy"代表信息增益。默认gini，即CART算法。
max_depth=None：最大深度。
max_features=None："None"表所有，"log2"log2N个；"sqrt"，"auto"最多N特征。整数即整数，小数即分数。
max_leaf_nodes=None：最大叶结点。
min_impurity_split=1e-07：最小不纯度。
min_samples_leaf=1：最小叶子结点数。
min_samples_split=2：最小划分样本数。
min_weight_fraction_leaf=0.0：叶子节点最小权重和，若小于则全部被剪。
presort=False：是否排序预处理。
random_state=None：随机状态。
splitter='best'："best"每次都找出最优的特征，"random"是随机的寻找局部最优特征。
1
2
3
4
5
6
7
8
9
10
11
12

继续使用Iris数据集。在全部使用DecisionTreeClassifier函数默认参数时：
这里写图片描述

正如我们分析的那样，过拟合很严重，但现在只要稍稍设置一个属性情况就会好很多。

from sklearn import datasets
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
import numpy as np
from sklearn import tree#导入分类器
from pylab import *
mpl.rcParams['font.sans-serif'] = ['SimHei'] 
mpl.rcParams['axes.unicode_minus'] = False 

iris=datasets.load_iris()
x=iris.data[:,:2]
y=iris.target

x_min,x_max=x[:,0].min()-0.5,x[:,0].max()+0.5
y_min,y_max=x[:,1].min()-0.5,x[:,1].max()+0.5

cmap_light=ListedColormap(['#AAAAFF','#AAFFAA','#FFAAAA'])
h=0.02
xx,yy=np.meshgrid(np.arange(x_min,x_max,h),np.arange(y_min,y_max,h))

DTC = tree.DecisionTreeClassifier(max_depth=3)#设置最大深度为3
DTC = DTC.fit(x, y)
z=DTC.predict(np.c_[xx.ravel(),yy.ravel()])
z=z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx,yy,z,cmap=cmap_light)

plt.title('基于Iris数据集的决策树分类')
plt.scatter(x[:,0],x[:,1],c=y)
plt.xlim(xx.min(),xx.max())
plt.ylim(yy.min(),yy.max())
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

这里写图片描述

决策树回归
DecisionTreeRegressor参数：
DecisionTreeRegressor(criterion=‘mse’, max_depth=None, max_features=None，max_leaf_nodes=None, min_impurity_split=1e-07,min_samples_leaf=1, min_samples_split=2,min_weight_fraction_leaf=0.0, presort=False, random_state=None, splitter=‘best’)

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)

X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)

plt.figure()
plt.scatter(X, y, s=20, edgecolor="black",
            c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue",
         label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这里写图片描述

使用Weka做分类决策
Weka(Waikato Environment for Knowledge Analysis)基于JAVA环境下开源的机器学习软件，很方便使用。预处理，分类，回归、聚类、关联规则，可视化都能做。下面简单的用一下J48分一下类。

这里写图片描述

打开Exprorer，导入天气的数据。

这里写图片描述

从这个数据可以看到play由四个方面决定。下面选择J48（也可以选用别的，J48是类似C4.5的基于JAVA的变体）进行应用分类操作就行了，当然了在这一步之前进行一些数据预处理也是可以的，也在Exprorer上面，选用不同的过滤器，加噪音测试性能都很方面，在这就不多说了，可以动手尝试一下。

这里写图片描述

很方便结果就出来了。当然还可以调整一下上面提到过的剪枝等优化的方法。

这里写图片描述

可视化最后的决策树。

这里写图片描述

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-dracula">

class="toc">

一、摘要及版本选择说明

1.1 摘要

作为一名对 AI 和生成式模型感兴趣的开发者或学习者，了解如何在小规模环境中部署这些模型是有趣且有益的。在个人笔记本上部署 DeepSeek-R1 是一种具有挑战性的但非常有价值的实践。它不仅可以帮助你快速实现文本生成和问答功能，还能通过不断解决遇到的问题，提升你的技术能力和对 AI 模型的理解。尽管过程中可能会遇到资源不足、配置复杂等问题，但通过仔细规划和持续学习，最终可以成功完成部署并享受到模型带来的便利。本文将介绍下载安装Ollama的方法，并且根据个人电脑的配置选择合适的DeepSeek版本进行安装部署测试，然后通过安装部署Open-WebUI交互页面来增强使用大模型的体验的整个过程。

1.2 版本选择

DeepSeek R1对硬件资源比较友好，对不同硬件配置有良好的适应性，能根据用户计算机硬件配置选择合适的模型版本。入门级设备拥有4GB 存和核显就能运行1.5B（Billion，十亿，大模型参数的数量）版本；进阶设备8GB内存搭配4GB显存就能驾驭7B版本；高性能设备则可选择32B版本。而且，DeepSeek R1支持低配置电脑，即使是没有独立显卡的低配置电脑，只要有足够的空余硬盘空间，如部署最大的6710亿参数的大模型需要至少1TB的空余空间，也能完成部署。
本人电脑配置支持DeepSeek-R1:8b，因此选择部署DeepSeek-R1:8b大模型。