用约束函数在扩展结点处剪去不满足约束的子树； 和用限界函数剪去得不到最优解的子 树。这两类函数统称为剪枝函数。
创新互联公司是专业的谷城网站建设公司，谷城接单;提供成都网站制作、成都做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行谷城网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。 在分支限界法中使用剪枝函数， 可以加速搜索。 该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不比当前最优值更大， 则说明相应的子树中不含问题的最优解，因而可以剪去。
搜索策略
在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处；
计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。
以上内容参考：百度百科-分支限界法
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:
copyFeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, copyFeatureName)
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 = copy.copy(trainData)
testData_tmp = copy.copy(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版权协议，转载请附上原文出处链接及本声明。
原文链接：
include#include#defineMAX100structaddr{charname[30];charstreet[40];charcity[20];charstate[3];unsignedlongintzip;}addr_list[MAX];voidinit_list(void);intmenu_select(void);voidenter(void);intfind_free(void);voiddeleted(void);voidlist(void);intmain(void){charchoice;init_list();/*initializethestructurearray*/for(;;){choice=menu_select();switch(choice){case1:enter();break;case2:deleted();break;case3:list();break;case4:exit(0);}}return0;}/*initializethelist*/voidinit_list(void){registerintt;for(t=0;t4);returnc;}/*Inputaddressintothelist*/voidenter(void){intslot;chars[80];slot=find_free();if(slot==-1)
