⑴ 求CART演算法matlab實現
function D = CART(train_features, train_targets, params, region)
% Classify using classification and regression trees
% Inputs:
% features - Train features
% targets - Train targets
% params - [Impurity type, Percentage of incorrectly assigned samples at a node]
% Impurity can be: Entropy, Variance (or Gini), or Missclassification
% region - Decision region vector: [-x x -y y number_of_points]
%
% Outputs
% D - Decision sufrace
[Ni, M] = size(train_features);
%Get parameters
[split_type, inc_node] = process_params(params);
%For the decision region
N = region(5);
mx = ones(N,1) * linspace (region(1),region(2),N);
my = linspace (region(3),region(4),N)' * ones(1,N);
flatxy = [mx(:), my(:)]';
%Preprocessing
[f, t, UW, m] = PCA(train_features, train_targets, Ni, region);
train_features = UW * (train_features - m*ones(1,M));;
flatxy = UW * (flatxy - m*ones(1,N^2));;
%Build the tree recursively
disp('Building tree')
tree = make_tree(train_features, train_targets, M, split_type, inc_node, region);
%Make the decision region according to the tree
disp('Building decision surface using the tree')
targets = use_tree(flatxy, 1:N^2, tree);
D = reshape(targets,N,N);
%END
function targets = use_tree(features, indices, tree)
%Classify recursively using a tree
if isnumeric(tree.Raction)
%Reached an end node
targets = zeros(1,size(features,2));
targets(indices) = tree.Raction(1);
else
%Reached a branching, so:
%Find who goes where
in_right = indices(find(eval_r(tree.Raction)));
in_left = indices(find(eval_r(tree.Laction)));
Ltargets = use_tree(features, in_left, tree.left);
Rtargets = use_tree(features, in_right, tree.right);
targets = Ltargets + Rtargets;
end
%END use_tree
function tree = make_tree(features, targets, Dlength, split_type, inc_node, region)
%Build a tree recursively
if (length(unique(targets)) == 1),
%There is only one type of targets, and this generates a warning, so deal with it separately
tree.right = [];
tree.left = [];
tree.Raction = targets(1);
tree.Laction = targets(1);
break
end
[Ni, M] = size(features);
Nt = unique(targets);
N = hist(targets, Nt);
if ((sum(N < Dlength*inc_node) == length(Nt) - 1) | (M == 1)),
%No further splitting is neccessary
tree.right = [];
tree.left = [];
if (length(Nt) ~= 1),
MLlabel = find(N == max(N));
else
MLlabel = 1;
end
tree.Raction = Nt(MLlabel);
tree.Laction = Nt(MLlabel);
else
%Split the node according to the splitting criterion
deltaI = zeros(1,Ni);
split_point = zeros(1,Ni);
op = optimset('Display', 'off');
for i = 1:Ni,
split_point(i) = fminbnd('CARTfunctions', region(i*2-1), region(i*2), op, features, targets, i, split_type);
I(i) = feval_r('CARTfunctions', split_point(i), features, targets, i, split_type);
end
[m, dim] = min(I);
loc = split_point(dim);
%So, the split is to be on dimention 'dim' at location 'loc'
indices = 1:M;
tree.Raction= ['features(' num2str(dim) ',indices) > ' num2str(loc)];
tree.Laction= ['features(' num2str(dim) ',indices) <= ' num2str(loc)];
in_right = find(eval_r(tree.Raction));
in_left = find(eval_r(tree.Laction));
if isempty(in_right) | isempty(in_left)
%No possible split found
tree.right = [];
tree.left = [];
if (length(Nt) ~= 1),
MLlabel = find(N == max(N));
else
MLlabel = 1;
end
tree.Raction = Nt(MLlabel);
tree.Laction = Nt(MLlabel);
else
%...It's possible to build new nodes
tree.right = make_tree(features(:,in_right), targets(in_right), Dlength, split_type, inc_node, region);
tree.left = make_tree(features(:,in_left), targets(in_left), Dlength, split_type, inc_node, region);
end
end
⑵ 決策樹演算法 CART和C4.5決策樹有什麼區別各用於什麼領域
1、C4.5演算法是在ID3演算法的基礎上採用信息增益率的方法選擇測試屬性。CART演算法採用一種二分遞歸分割的技術，與基於信息熵的演算法不同，CART演算法對每次樣本集的劃分計算GINI系數，GINI系數，GINI系數越小則劃分越合理。
2、決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
3、決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。
⑶ 決策樹是什麼東東
小白自學路上的備忘記錄。。。
參考：
決策樹(分類樹、回歸樹)
決策樹 :這個博客的圖真好看，通俗易懂。哈哈
決策樹詳解
決策樹（Decision Tree）是一種有監督學習演算法，常用於分類和回歸。本文僅討論分類問題。
決策樹模型是運用於分類以及回歸的一種樹結構。決策樹由節點和有向邊組成，一般一棵決策樹包含一個根節點、若干內部節點和若干葉節點。決策樹的決策過程需要從決策樹的根節點開始，待測數據與決策樹中的特徵節點進行比較，並按照比較結果選擇選擇下一比較分支，直到葉子節點作為最終的決策結果。
簡而言之，決策樹是一個利用樹的模型進行決策的多分類模型
為了找到最優的劃分特徵，我們需要先了解一些資訊理論的知識：
純度 ：
你可以把決策樹的構造過程理解成為尋找純凈劃分的過程。數學上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標變數的分歧最小
信息熵 ：表示信息的不確定度
在資訊理論中，隨機離散事件出現的概率存在著不確定性。為了衡量這種信息的不確定性，信息學之父香農引入了信息熵的概念.
當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高 。
信息熵越大，純度越低。當集合中的所有樣本均勻混合時，信息熵最大，純度最低
經典的 「不純度」的指標有三種，分別是信息增益（ID3 演算法）、信息增益率（C4.5 演算法）以及基尼指數（Cart 演算法）
信息增益 ：
信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。
信息增益率
信息增益率 = 信息增益 / 屬性熵
基尼指數
基尼指數（基尼不純度）：表示在樣本集合中一個隨機選中的樣本被分錯的概率。
即 基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率
基尼系數的性質與信息熵一樣：度量隨機變數的不確定度的大小；
G 越大，數據的不確定性越高；
G 越小，數據的不確定性越低；
G = 0，數據集中的所有樣本都是同一類別
詳細參考： 機器學習——基尼指數
ID3 演算法是建立在奧卡姆剃刀（用較少的東西，同樣可以做好事情）的基礎上：越是小型的決策樹越優於大的決策樹
ID3演算法的核心是在決策樹各個節點上根據信息增益來選擇進行劃分的特徵，然後遞歸地構建決策樹。演算法採用自頂向下的貪婪搜索遍歷可能的決策樹空間。
具體方法 ：
ID3的局限 ：
C4.5與ID3相似，但大的特點是克服了 ID3 對特徵數目的偏重這一缺點，引入信息增益率來作為分類標准。
C4.5的實現基於ID3的改進 ：
信息增益率對可取值較少的特徵有所偏好（分母越小，整體越大），因此 C4.5 並不是直接用增益率最大的特徵進行劃分，而是使用一個 啟發式方法 ：先從候選劃分特徵中找到信息增益高於平均值的特徵，再從中選擇增益率最高的。
C4.5的局限 ：
ID3 和 C4.5 生成的決策樹分支、規模都比較大，CART 演算法的二分法可以簡化決策樹的規模，提高生成決策樹的效率。
CART(),分類回歸樹演算法，既可用於分類也可用於回歸，在這一部分我們先主要將其分類樹的生成。區別於ID3和C4.5,CART假設決策樹是二叉樹，內部節點特徵的取值為「是」和「否」，左分支為取值為「是」的分支，右分支為取值為」否「的分支。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間(即特徵空間)劃分為有限個單元。
CART的分類樹用基尼指數來選擇最優特徵的最優劃分點，具體過程如下
剪枝就是給決策樹瘦身，這一步想實現的目標就是，不需要太多的判斷，同樣可以得到不錯的結果。之所以這么做，是為了防止「過擬合」（Overfitting）現象的發生。
過擬合：指的是模型的訓練結果「太好了」，以至於在實際應用的過程中，會存在「死板」的情況，導致分類錯誤。
欠擬合：指的是模型的訓練結果不理想.
剪枝的方法 ：
參考： 【機器學習】決策樹（上）——ID3、C4.5、CART（非常詳細）
更多模型不斷更新中。。。。
⑷ 用python實現紅酒數據集的ID3,C4.5和CART演算法
ID3演算法介紹
ID3演算法全稱為迭代二叉樹3代演算法（Iterative Dichotomiser 3）
該演算法要先進行特徵選擇，再生成決策樹，其中特徵選擇是基於「信息增益」最大的原則進行的。
但由於決策樹完全基於訓練集生成的，有可能對訓練集過於「依賴」，即產生過擬合現象。因此在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般採用後剪枝。
信息熵、條件熵和信息增益
信息熵：來自於香農定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。
設x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1
,x
2
,x
3
,...x
n
為信息集合X的n個取值，則x i x_ix
i
的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i
,i=1,2,3,...,n
信息集合X的信息熵為：
H ( X ) = − ∑ i = 1 n p i log p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n
p
i
logp
i
條件熵：指已知某個隨機變數的情況下，信息集合的信息熵。
設信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1
,y
2
,y
3
,...y
m
組成的隨機變數集合Y，則隨機變數（X，Y）的聯合概率分布為
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij
條件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m
p(y
j
)H(X∣y
j
)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j
)=−
j=1
∑
m
p(y
j
)
i=1
∑
n
p(x
i
∣y
j
)logp(x
i
∣y
j
)
和貝葉斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i
y
j
)=p(x
i
∣y
j
)p(y
j
)
可以化簡條件熵的計算公式為:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m
i=1
∑
n
p(x
i
,y
j
)log
p(x
i
,y
j
)
p(x
i
)
信息增益：信息熵-條件熵，用於衡量在知道已知隨機變數後，信息不確定性減小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)
python代碼實現
import numpy as np
import math
def calShannonEnt(dataSet):
""" 計算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy
def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特徵列label等於value，並且過濾掉改特徵列的數據集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)
def chooseFeature(dataSet):
""" 通過計算信息增益選擇最合適的特徵"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0
for v in uniqueValues: #計算條件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #計算信息增益
if infoGain >= bestInfoGain: #選擇最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex
def creatDecisionTree(dataSet, featNames):
""" 通過訓練集生成決策樹 """
featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變數會指向舊變數的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一個類別
return classList[0]
if dataSet.shape[1] == 1: #當所有特徵屬性都利用完仍然無法判斷樣本屬於哪一類，此時歸為該數據集中數量最多的那一類
return max(set(classList), key=classList.count)
bestFeatureIndex = chooseFeature(dataSet) #選擇特徵
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已選特徵列
decisionTree = {bestFeatureName: {}}
featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特徵列所包含的類別， 通過遞歸生成決策樹
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree
def classify(decisionTree, featnames, featList):
""" 使用訓練所得的決策樹進行分類 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子節點仍是樹，則遞歸查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
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
下面用鳶尾花數據集對該演算法進行測試。由於ID3演算法只能用於標稱型數據，因此用在對連續型的數值數據上時，還需要對數據進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特徵所有連續性數值的中值作為分界點，小於中值的標記為1，大於中值的標記為0。訓練1000次，統計准確率均值。
from sklearn import datasets
from sklearn.model_selection import train_test_split
iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]
scoreL = []
for i in range(1000): #對該過程進行10000次
trainData, testData = train_test_split(data) #區分測試集和訓練集
featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #對訓練集每個特徵，以中值為分界點進行離散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
輸出結果為：score: 0.7335，即准確率有73%。每次訓練和預測的准確率分布如下：
數據離散化
然而，在上例中對特徵值離散化的劃分點實際上過於「野蠻」，此處介紹一種通過信息增益最大的標准來對數據進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數據集的不確定性。
具體步驟如下：
對每個特徵所包含的數值型特徵值排序
對相鄰兩個特徵值取均值，這些均值就是待選的劃分點
用每一個待選點把該特徵的特徵值劃分成兩類，小於該特徵點置為1， 大於該特徵點置為0，計算此時的條件熵，並計算出信息增益
選擇信息使信息增益最大的劃分點進行特徵離散化
實現代碼如下：
def filterRawData(dataSet, colIndex, value, tag):
""" 用於把每個特徵的連續值按照區分點分成兩類，加入tag參數，可用於標記篩選的是哪一部分數據"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)
def dataDiscretization(dataSet, featName):
""" 對數據每個特徵的數值型特徵值進行離散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
for featIndex in range(featureNum): #對於每一個特徵
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []
for i in range(len(uniqueValues) - 1): # 求出相鄰兩個值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #對於每個劃分點
subEntropy = 0.0 #計算該劃分點的信息熵
for tag in range(2): #分別劃分為兩類
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)
## 計算信息增益
infoGain = entropy - subEntropy
## 選擇最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
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
重新對數據進行離散化，並重復該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數據進行分類，分別統計平均准確率。運行代碼如下:
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #對該過程進行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #區分測試集和訓練集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據信息增益離散化
for i in range(testData.shape[1]-1): #根據測試集的區分點離散化訓練集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))
print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
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
兩者准確率分別為：
score: 0.7037894736842105
score-sk: 0.7044736842105263
准確率分布如下：
兩者的結果非常一樣。
（但是。。為什麼根據信息熵離散化得到的准確率比直接用均值離散化的准確率還要低啊？？哇的哭出聲。。）
最後一次決策樹圖形如下：
決策樹剪枝
由於決策樹是完全依照訓練集生成的，有可能會有過擬合現象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a
(T)=
t=1
∑
T
N
t
H
t
(T)+α∣T∣
其中，H t ( T ) H_t(T)H
t
(T)表示葉子節點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T
N
t
H
t
(T)是決策樹的經驗損失函數當隨著T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。
對於決策樹損失函數的理解，如何理解決策樹的損失函數? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路理解一下
C4.5演算法
ID3演算法通過信息增益來進行特徵選擇會有一個比較明顯的缺點：即在選擇的過程中該演算法會優先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3演算法無法解決當每個特徵屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。
C4.5演算法ID3演算法的改進，它不是依據信息增益進行特徵選擇，而是依據信息增益率，它添加了特徵分裂信息作為懲罰項。定義分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n
∣X∣
∣X
i
∣
log
∣X∣
∣X
i
∣
則信息增益率為：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)
關於ID3和C4.5演算法
在學習分類回歸決策樹演算法時，看了不少的資料和博客。關於這兩個演算法，ID3演算法是最早的分類演算法，這個演算法剛出生的時候其實帶有很多缺陷：
無法處理連續性特徵數據
特徵選取會傾向於分類較多的特徵
沒有解決過擬合的問題
沒有解決缺失值的問題
即該演算法出生時是沒有帶有連續特徵離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3演算法不少的缺陷：
通過信息最大增益的標准離散化連續的特徵數據
在選擇特徵是標准從「最大信息增益」改為「最大信息增益率」
通過加入正則項系數對決策樹進行剪枝
對缺失值的處理體現在兩個方面：特徵選擇和生成決策樹。初始條件下對每個樣本的權重置為1。
特徵選擇：在選取最優特徵時，計算出每個特徵的信息增益後，需要乘以一個**「非缺失值樣本權重占總樣本權重的比例」**作為系數來對比每個特徵信息增益的大小
生成決策樹：在生成決策樹時，對於缺失的樣本我們按照一定比例把它歸屬到每個特徵值中，比例為該特徵每一個特徵值占非缺失數據的比重
關於C4.5和CART回歸樹
作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：
C4.5的熵運算中涉及了對數運算，在數據量大的時候效率非常低。
C4.5的剪枝過於簡單
C4.5隻能用於分類運算不能用於回歸
當特徵有多個特徵值是C4.5生成多叉樹會使樹的深度加深
————————————————
版權聲明：本文為CSDN博主「Sarah Huang」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_44794704/article/details/89406612
⑸ 決策樹演算法原理
決策樹是通過一系列規則對數據進行分類的過程。它提供一種在什麼條件下會得到什麼值的類似規則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變數做決策樹，回歸樹對連續變數做決策樹。
如果不考慮效率等，那麼樣本所有特徵的判斷級聯起來終會將某一個樣本分到一個類終止塊上。實際上，樣本所有特徵中有一些特徵在分類時起到決定性作用，決策樹的構造過程就是找到這些具有決定性作用的特徵，根據其決定性程度來構造一個倒立的樹--決定性作用最大的那個特徵作為根節點，然後遞歸找到各分支下子數據集中次大的決定性特徵，直至子數據集中所有數據都屬於同一類。所以，構造決策樹的過程本質上就是根據數據特徵將數據集分類的遞歸過程，我們需要解決的第一個問題就是，當前數據集上哪個特徵在劃分數據分類時起決定性作用。
一棵決策樹的生成過程主要分為以下3個部分:
特徵選擇：特徵選擇是指從訓練數據中眾多的特徵中選擇一個特徵作為當前節點的分裂標准，如何選擇特徵有著很多不同量化評估標准標准，從而衍生出不同的決策樹演算法。
決策樹生成： 根據選擇的特徵評估標准，從上至下遞歸地生成子節點，直到數據集不可分則停止決策樹停止生長。 樹結構來說，遞歸結構是最容易理解的方式。
剪枝：決策樹容易過擬合，一般來需要剪枝，縮小樹結構規模、緩解過擬合。剪枝技術有預剪枝和後剪枝兩種。
劃分數據集的最大原則是：使無序的數據變的有序。如果一個訓練數據中有20個特徵，那麼選取哪個做劃分依據？這就必須採用量化的方法來判斷，量化劃分方法有多重，其中一項就是「資訊理論度量信息分類」。基於資訊理論的決策樹演算法有ID3、CART和C4.5等演算法，其中C4.5和CART兩種演算法從ID3演算法中衍生而來。
CART和C4.5支持數據特徵為連續分布時的處理，主要通過使用二元切分來處理連續型變數，即求一個特定的值-分裂值：特徵值大於分裂值就走左子樹，或者就走右子樹。這個分裂值的選取的原則是使得劃分後的子樹中的「混亂程度」降低，具體到C4.5和CART演算法則有不同的定義方式。
ID3演算法由Ross Quinlan發明，建立在「奧卡姆剃刀」的基礎上：越是小型的決策樹越優於大的決策樹（be simple簡單理論）。ID3演算法中根據資訊理論的信息增益評估和選擇特徵，每次選擇信息增益最大的特徵做判斷模塊。ID3演算法可用於劃分標稱型數據集，沒有剪枝的過程，為了去除過度數據匹配的問題，可通過裁剪合並相鄰的無法產生大量信息增益的葉子節點（例如設置信息增益閥值）。使用信息增益的話其實是有一個缺點，那就是它偏向於具有大量值的屬性--就是說在訓練集中，某個屬性所取的不同值的個數越多，那麼越有可能拿它來作為分裂屬性，而這樣做有時候是沒有意義的，另外ID3不能處理連續分布的數據特徵，於是就有了C4.5演算法。CART演算法也支持連續分布的數據特徵。
C4.5是ID3的一個改進演算法，繼承了ID3演算法的優點。C4.5演算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整數據進行處理。C4.5演算法產生的分類規則易於理解、准確率較高；但效率低，因樹構造過程中，需要對數據集進行多次的順序掃描和排序。也是因為必須多次數據集掃描，C4.5隻適合於能夠駐留於內存的數據集。
CART演算法的全稱是Classification And Regression Tree，採用的是Gini指數（選Gini指數最小的特徵s）作為分裂標准,同時它也是包含後剪枝操作。ID3演算法和C4.5演算法雖然在對訓練樣本集的學習中可以盡可能多地挖掘信息，但其生成的決策樹分支較大，規模較大。為了簡化決策樹的規模，提高生成決策樹的效率，就出現了根據GINI系數來選擇測試屬性的決策樹演算法CART。
決策樹演算法的優點：
（1）便於理解和解釋，樹的結構可以可視化出來
（2）基本不需要預處理，不需要提前歸一化，處理缺失值
（3）使用決策樹預測的代價是O(log2m)，m為樣本數
（4）能夠處理數值型數據和分類數據
（5）可以處理多維度輸出的分類問題
（6）可以通過數值統計測試來驗證該模型，這使解釋驗證該模型的可靠性成為可能
（7）即使該模型假設的結果與真實模型所提供的數據有些違反，其表現依舊良好
決策樹演算法的缺點:
（1）決策樹模型容易產生一個過於復雜的模型,這樣的模型對數據的泛化性能會很差。這就是所謂的過擬合.一些策略像剪枝、設置葉節點所需的最小樣本數或設置數的最大深度是避免出現該問題最為有效地方法。
（2）決策樹可能是不穩定的，因為數據中的微小變化可能會導致完全不同的樹生成。這個問題可以通過決策樹的集成來得到緩解。
（3）在多方面性能最優和簡單化概念的要求下，學習一棵最優決策樹通常是一個NP難問題。因此，實際的決策樹學習演算法是基於啟發式演算法，例如在每個節點進行局部最優決策的貪心演算法。這樣的演算法不能保證返回全局最優決策樹。這個問題可以通過集成學習來訓練多棵決策樹來緩解,這多棵決策樹一般通過對特徵和樣本有放回的隨機采樣來生成。
（4）有些概念很難被決策樹學習到,因為決策樹很難清楚的表述這些概念。例如XOR，奇偶或者復用器的問題。
（5）如果某些類在問題中佔主導地位會使得創建的決策樹有偏差。因此，我們建議在擬合前先對數據集進行平衡。
（1）當數據的特徵維度很高而數據量又很少的時候，這樣的數據在構建決策樹的時候往往會過擬合。所以我們要控制樣本數量和特徵的之間正確的比率；
（2）在構建決策樹之前，可以考慮預先執行降維技術（如PCA，ICA或特徵選擇），以使我們生成的樹更有可能找到具有辨別力的特徵；
（3）在訓練一棵樹的時候，可以先設置max_depth=3來將樹可視化出來，以便我們找到樹是怎樣擬合我們數據的感覺，然後在增加我們樹的深度；
（4）樹每增加一層，填充所需的樣本數量是原來的2倍，比如我們設置了最小葉節點的樣本數量，當我們的樹層數增加一層的時候，所需的樣本數量就會翻倍，所以我們要控制好樹的最大深度，防止過擬合；
（5）使用min_samples_split（節點可以切分時擁有的最小樣本數） 和 min_samples_leaf（最小葉節點數）來控制葉節點的樣本數量。這兩個值設置的很小通常意味著我們的樹過擬合了，而設置的很大意味著我們樹預測的精度又會降低。通常設置min_samples_leaf=5；
（6）當樹的類比不平衡的時候，在訓練之前一定要先平很數據集，防止一些類別大的類主宰了決策樹。可以通過采樣的方法將各個類別的樣本數量到大致相等，或者最好是將每個類的樣本權重之和(sample_weight)規范化為相同的值。另請注意，基於權重的預剪枝標准（如min_weight_fraction_leaf）將比不知道樣本權重的標准（如min_samples_leaf）更少偏向主導類別。
（7）如果樣本是帶權重的，使用基於權重的預剪枝標准將更簡單的去優化樹結構，如mn_weight_fraction_leaf，這確保了葉節點至少包含了樣本權值總體總和的一小部分；
（8）在sklearn中所有決策樹使用的數據都是np.float32類型的內部數組。如果訓練數據不是這種格式，則將復制數據集，這樣會浪費計算機資源。
（9）如果輸入矩陣X非常稀疏，建議在調用fit函數和稀疏csr_matrix之前轉換為稀疏csc_matrix，然後再調用predict。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。
⑹ 決策樹之CART演算法
一、基本概念
1.cart使用基尼系數作為劃分標准。基尼系數越小，則不純度越低，區分的越徹底。
2.假設有k個類別，第k個類別的概率為 ,則基尼系數表達式為：
Gini(p)= (1- )=1-
3.對於樣本D，如果根據特徵A 的值把樣本分為D1,D2兩部分，則在特徵A條件下，D的基尼系數
Gini(D,A)= Gini(D1)+ Gini(D2)
4.CART建立起來的是二叉樹，如果特徵A有A1,A2，A3三個類別，CART會考慮把A分成{A1},{A2 ,A3}兩組，或者是其他兩種情況。由於這次A並沒有完全分開，所以下次還有機會在子節點把A2,A3分開.
5.對於連續值的切分.假如有1 2 3 4 5 那麼cart會有4個切分點 [1.5 2.5 3.5 4.5]
二.實例推導樹的建立過程
1.假設我有以下源數據
序號 天氣 周末 促銷 銷量
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 好 否 否 低
該數據集有三個特徵 天氣 周末 促銷
2.為了簡化建立樹的過程,我將忽略基尼系數與樣本個數閥值
2.1 首先計算各個特徵值對數據集的基尼系數,公式見---- 基本概念.3
Gini(D|天氣)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706
Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063
Gini(D|促銷)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131
周末的基尼系數最小，這也符合我們的一般認識
2.2 第一個分列特徵選擇周末。此時數據集按照是否周末分成兩個。
Gini(周末|天氣)=0.2679
Gini(周末|促銷)=0.2714
Gini(非周末|天氣)=0.3505
Gini(非周末|促銷)=0.3875
此時，周末應該以天氣作為劃分，非周末也是以天氣作為劃分，下面放個圖
三、CART樹對於連續特徵的處理
假如特徵A為連續型變數，則把特徵A按照從小到大進行排序，取相鄰兩點的平均值為切分點，計算基尼系數。則基尼系數最小的點為切分點，大於切分點的為一類，小於切分點的為另一類。舉例：特徵A的值為 1，2，3，4，5，6 目標變數是高、低、高、低、高、低。則1.5處的基尼系數為 (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4 2.5處的基尼系數為 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5處的基尼系數為 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.5處的基尼系數為 (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5 5.5處的基尼系數為 (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4 結論： 1.5和5.5處的基尼系數最小，可以把1分為一類，2-6分為另一類。或者6分為一類，1-5另一類。
四、關於回歸樹
1.回歸樹和分類樹的區別在於輸出值類型不同。分類樹輸出的是離散值，回歸樹輸出的是連續值。
2.和分類樹使用基尼系數不同，回歸樹使用和均方差來度量最佳分隔點。假設有1 2 3 4 5 6 六個數。假設3.5處把數據分開最合適，那麼(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割點中取得最小值。2，5為各自數據段的平均值。
3.回歸樹採用最後葉子的平均值或者中值作為輸出結果
⑺ R語言-17決策樹
是一個預測模型，分為回歸決策樹和分類決策樹，根據已知樣本訓練出一個樹模型，從而根據該模型對新樣本因變數進行預測，得到預測值或預測的分類
從根節點到葉節點的一條路徑就對應著一條規則．整棵決策樹就對應著一組表達式規則。葉節點就代表該規則下得到的預測值。如下圖決策樹模型則是根據房產、結婚、月收入三個屬性得到是否可以償還貸款的規則。
核心是如何從眾多屬性中挑選出具有代表性的屬性作為決策樹的分支節點。
最基本的有三種度量方法來選擇屬性
1. 信息增益（ID3演算法）
信息熵
一個信源發送出什麼符號是不確定的，衡量它可以根據其出現的概率來度量。概率大，出現機會多，不確定性小；反之不確定性就大。不確定性函數f是概率P的 減函數 。兩個獨立符號所產生的不確定性應等於各自不確定性之和，即f(P1,P2)=f(P1)+f(P2)，這稱為可加性。同時滿足這兩個條件的函數f是對數函數，即
在信源中，考慮的不是某一單個符號發生的不確定性，而是要考慮這個信源所有可能發生情況的平均不確定性。因此，信息熵被定義為
決策樹分類過程
2、增益率（C4.5演算法）
由於信息增益的缺點是：傾向於選擇具有大量值的屬性，因為具有大量值的屬性每個屬性對應數據量少，傾向於具有較高的信息純度。因此增益率使用【信息增益/以該屬性代替的系統熵（類似於前面第一步將play換為該屬性計算的系統熵】這個比率，試圖克服這種缺點。
g(D,A)代表D數據集A屬性的信息增益，
3. 基尼指數（CART演算法）
基尼指數：
表示在樣本集合中一個隨機選中的樣本被分錯的概率。越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高。
假設集合中有K個類別，則：
說明:
1. pk表示選中的樣本屬於k類別的概率，則這個樣本被分錯的概率是(1-pk)
2. 樣本集合中有K個類別，一個隨機選中的樣本可以屬於這k個類別中的任意一個，因而對類別就加和
3. 當為二分類是，Gini(P) = 2p(1-p)
基尼指數是將屬性A做二元劃分，所以得到的是二叉樹。當為離散屬性時，則會將離散屬性的類別兩兩組合，計算基尼指數。
舉個例子：
如上面的特徵Temperature，此特徵有三個特徵取值： 「Hot」，「Mild」， 「Cool」，
當使用「學歷」這個特徵對樣本集合D進行劃分時，劃分值分別有三個，因而有三種劃分的可能集合，劃分後的子集如下：
對於上述的每一種劃分，都可以計算出基於 劃分特徵= 某個特徵值 將樣本集合D劃分為兩個子集的純度：
決策數分類過程
先剪枝 ：提前停止樹的構建對樹剪枝，構造樹時，利用信息增益、統計顯著性等，當一個節點的劃分導致低於上述度量的預定義閾值時，則停止進一步劃分。但閾值的確定比較困難。
後剪枝 ：更為常用，先得到完全生長的樹，再自底向上，用最下面的節點的樹葉代替該節點
CART使用代價復雜度剪枝演算法 ：計算每個節點剪枝後與剪枝前的代價復雜度，如果剪去該節點，代價復雜度較小（復雜度是樹的結點與樹的錯誤率也就是誤分類比率的函數），則剪去。
C4.5採用悲觀剪枝 ：類似代價復雜度，但CART是利用剪枝集評估代價復雜度，C4.5是採用訓練集加上一個懲罰評估錯誤率
決策樹的可伸縮性
ID3C4.5CART都是為較小的數據集設計，都限制訓練元祖停留再內存中，為了解決可伸縮性，提出了其它演算法如
RainForest(雨林）：對每個屬性維護一個AVC集，描述該結點的訓練元組，所以只要將AVC集放在內存即可
BOAT自助樂觀演算法：利用統計學，創造給定訓練數據的較小樣本，每個樣本構造一個樹，導致多顆樹，再利用它們構造1顆新樹。優點是可以增量的更新，當插入或刪除數據，只需決策樹更新，而不用重新構造。
決策樹的可視化挖掘
PBC系統可允許用戶指定多個分裂點，導致多個分支，傳統決策樹演算法數值屬性都是二元劃分。並且可以實現交互地構建樹。
rpart是採用cart演算法，連續型「anova」;離散型「class」;
2）進行剪枝的函數：prune()
3）計算MAE評估回歸樹模型誤差，這里將樣本劃分成了訓練集和測試集，testdata為測試集
rt.mae為根據訓練集得到的決策樹模型對測試集因變數預測的結果與測試集因變數實際值得到平均絕對誤差
⑻ 決策樹演算法 CART和C4.5決策樹有什麼區別各用於什麼領域
1、C4.5演算法是在ID3演算法的基礎上採用信息增益率的方法選擇測試屬性。CART演算法採用一種二分遞歸分割的技術，與基於信息熵的演算法不同，CART演算法對每次樣本集的劃分計算GINI系數，GINI系數，GINI系數越小則劃分越合理。
2、決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
3、決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。
⑼ 決策樹原理及演算法比較
決策樹是什麼？
和線性回歸一樣是一種模型，內部節點和葉節點。實現分類，內部節點和葉節點通過有向線（分類規 則）連接起來
決策樹的目標是什麼？
決策樹通過對數據復雜度的計算，建立特徵分類標准，確定最佳分類特徵。
表現為「熵」（entropy）和信息增益（information gain），基於決策樹思想的三種演算法：ID3，C4.5,CART演算法，三種演算法的信息衡量的指標也不同.
熵來表示信息的復雜度，熵越大，信息也就越復雜，公式如下：
那些演算法能夠實現決策樹？
在決策樹構建過程中，什麼是比較重要的。特徵選擇（按照熵變計算），演算法產生最重要的部分，
決策樹中葉節點的分類比較純，
節點順序的排列規則：
熵變：
數據的預處理：
改進思路一般有兩個1，換演算法；2，調參數
做好數據的預處理：
1，做好特徵選擇；
2，做好數據離散化、異常值處理、缺失填充
分類器：
在決策樹中，從根到達任意一個葉節點的之間最長路徑的長度，表示對應的演算法排序中最壞情況下的比較次數。這樣一個比較演算法排序中的最壞情況的比較次數就與其決策樹的高度相同，同時如果決策樹中每種排列以可達葉子的形式出現，那麼關於其決策樹高度的下界也就是關於比較排序演算法運行時間的下界，
ID3演算法存在的缺點：
1，ID3演算法在選擇根節點和內部節點分支屬性時，採用信息增益作為評價標准。信息增益的缺點是傾向於選擇取值較多的屬性
2，當數據為連續性變數的時候，ID3演算法就不是一個合理的演算法的模型了
C4.5信息增益比率，
1，在信息增益的基礎上除以split-info，是將信息增益改為信息增益比，以解決取值較多的屬性的問題，另外它還可以處理連續型屬性，其判別標準是θ，
2，C4.5演算法利用增益/熵值，克服了樹生長的過程中，總是『貪婪』選擇變數分類多的進行分類
3，處理來內需型變數，C4.5的分類樹的分支就是兩條
衡量指標：
（1）信息增益
基於ID3演算法的信息增益對於判定連續型變數的時候病不是最優選擇，C4.5演算法用了信息增益率這個概念。
分類信息類的定義如下：
這個值表示將訓練數據集D劃分成對應屬性A測試的V個輸出v個劃分產生的信息，信息增益率定義為：
選擇最大信息增益率的屬性作為分裂屬性
Gini指標，CART
表明樣本的「純凈度」。Gini系數避免了信息增益產生的問題，
過擬合問題，非常好的泛化能力，有很好的推廣能力
Gini系數的計算：
在分類問題中，假設有k個類，樣本點屬於第k類的概率為Pk，則概率分布的gini指數的定義為：
如果樣本集合D根據某個特徵A被分割為D1，D2兩個部分，那麼在特徵A的提哦啊見下，集合D的gini指數的定義為：
Gini指數代表特徵A不同分組下的數據集D的不確定性，gini指數越大，樣本集合的不確定性也就越大，這一點和熵的概念相類似
決策樹原理介紹：
第三步：對於每個屬性執行劃分：
（1）該屬性為離散型變數
記樣本中的變數分為m中
窮舉m種取值分為兩類的劃分
對上述所有劃分計算GINI系數
（2）該屬性為連續型變數
將數據集中從小到大劃分
按順序逐一將兩個相臨值的均值作為分割點
對上述所有劃分計算GINI系數
學歷的劃分使得順序的劃分有個保證，化為連續型變數處理。
決策樹的生成演算法分為兩個步驟：
預剪枝和後剪枝 CCP（cost and complexity）演算法：在樹變小和變大的的情況有個判斷標准。誤差率增益值：α值為誤差的變化
決策樹的終止條件：
1，某一個節點的分支所覆蓋的樣本都是同一類的時候
2，某一個分支覆蓋的樣本的個數如果小於一個閾值，那麼也可以產生葉子節點，從而終止Tree-Growth
確定葉子結點的類：
1，第一種方式，葉子結點覆蓋的樣本都屬於同一類
2， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類