初识决策树
决策树是一个类似于人们决策过程的树结构，从根节点开始，每个分枝代表一个新的决策事件，会生成两个或多个分枝，每个叶子代表一个最终判定所属的类别。
例如，如下是一个决策树，代表薪水大于30W的男性会买车。
我们可以很容易的写出IF Else来实现决策树的判定。上述的决策树有两个特征区间，性别和年龄，最终的结果有两个类别，买和不买。
信息增益
信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
熵定义为信息的期望值，在明确熵的概念前，首先明确信息的定义，如果待分类的事务可能划分在多个分类中，则符号xi的信息定义为：
假设在样本数据集 D 中，混有 C种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：
图 2. 香农熵的定义
其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。
对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：
图 3. 作用后的信息熵计算公式
其中 k 表示样本 D 被分为 k 个部分。
信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：
图 4. 信息熵差值计算公式
对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。
案例
用户ID 年龄 性别 收入 婚姻状况 是否买房
1 27 男 15W 否 否
2 47 女 30W 是 是
3 32 男 12W 否 否
4 24 男 45W 否 是
5 45 男 30W 是 否
6 56 男 32W 是 是
7 31 男 15W 否 否
8 23 女 30W 是 否
有四个纬度，年龄，性别，收入，婚姻状况，我们先把年龄分为20-30，30-40，40+三个阶段，把收入分为10-20，20-40，40+三个级别。
首先，正对所有数据，一共3人买房，5人没买，条件熵
H(c) = - 3/8 * log2(3/8) - 5/8 * log2(5/8) = 0.288
我们对这四个纬度逐一计算信息增益。
年龄
我们先按照三个年龄阶段将表划分为如下三张：
用户ID 年龄 性别 收入 婚姻状况 是否买房
1 27 男 15W 否 否
4 24 男 45W 否 是
8 23 女 30W 是 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
3 32 男 12W 否 否
7 31 男 15W 否 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
2 47 女 30W 是 是
5 45 男 30W 是 否
6 56 男 32W 是 是
首先，针对20-30年龄区间的，特征条件熵计算如下：
H(c|x11) = - 1/3 * log2(1/3) - 2/3 * log2(2/3) = 0.278（买房的比例乘以其自身对数，加上不买房的比例乘以自身对数）
针对30-40年龄区间的，特征条件熵计算如下：
H(c|x12) = - 0 * log2(0) - 1 * log2(1) = 0
针对40+年龄区间的，特征条件熵计算如下：
H(c|x13) = - 2/3 * log2(2/3) - 1/3 * log2(1/3) = 0.278
综合上面，年龄的条件熵计算如下：
H(c|x1) = 3/8 * 0.278 + 2/8 * 0 + 3/8 * 0.278 = 0.209 （每个区间的比例，乘以各区间的条件熵，再取总和）
那么年龄这个纬度的信息增益就是 0.288 - 0.209 = 0.079
性别
分表如下：
用户ID 年龄 性别 收入 婚姻状况 是否买房
1 27 男 15W 否 否
3 32 男 12W 否 否
4 24 男 45W 否 是
5 45 男 30W 是 否
6 56 男 32W 是 是
7 31 男 15W 否 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
2 47 女 30W 是 是
8 23 女 30W 是 否
针对男性，特征条件熵：
H(c|x21) = - 2/6 * log2(2/6) - 4/6 * log2(4/6) = 0.278
针对女性，特征条件熵：
H(c|x22) = - 1/2 * log2(1/2) - 1/2 * log2(1/2) = 0.301
综合上面，性别的条件熵计算如下：
H(c|x2) = 6/8 * 0.278 + 2/8 * 0.301 = 0.284
那么性别这个纬度的信息增益就是 0.288 - 0.284 = 0.004
收入
分表如下：
用户ID 年龄 性别 收入 婚姻状况 是否买房
1 27 男 15W 否 否
3 32 男 12W 否 否
7 31 男 15W 否 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
2 47 女 30W 是 是
5 45 男 30W 是 否
6 56 男 32W 是 是
8 23 女 30W 是 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
4 24 男 45W 否 是
针对10-20W收入者，特征条件熵：
H(c|x31) = - 0 * log2(0) - 1 * log2(1) = 0
针对20-40W收入者，特征条件熵：
H(c|x32) = - 2/4 * log2(2/4) - 2/4 * log2(2/4) = 0.301
针对40W+收入者，特征条件熵：
H(c|x33) = 0
综合上面，收入的条件熵计算如下：
H(c|x3) = 3/8 * 0 + 4/8 * 0.301 + 1/8 * 0 = 0.151
那么收入这个纬度的信息增益就是 0.288 - 0.151 = 0.137
婚姻状况
分表如下：
用户ID 年龄 性别 收入 婚姻状况 是否买房
1 27 男 15W 否 否
3 32 男 12W 否 否
4 24 男 45W 否 是
7 31 男 15W 否 否
用户ID 年龄 性别 收入 婚姻状况 是否买房
2 47 女 30W 是 是
5 45 男 30W 是 否
6 56 男 32W 是 是
8 23 女 30W 是 否
针对未婚者，特征条件熵：
H(c|x41) = - 3/4 * log2(3/4) - 1/4 * log2(1/4) = 0.245
针对已婚者，特征条件熵：
H(c|x31) = - 2/4 * log2(2/4) - 2/4 * log2(2/4) = 0.301
综合上面，婚姻状态的条件熵计算如下：
H(c|x3) = 4/8 * 0.245+ 4/8 * 0.301 + 1/8 * 0 = 0.274
那么婚姻状态这个纬度的信息增益就是 0.288 - 0.274 = 0.014
OK，我们现在总结下所有四个纬度的信息增益，如下
年龄：0.079
性别：0.004
收入：0.137
婚姻状况：0.014
可以看到，收入这个纬度的信息增益最大，所以我们就按照收入，做为根节点，分枝如下：
收入就是决策树的根节点，可以看到，分枝后，收入在40W+的可以得到结论，是买房，叶子也一并生成；收入在10-20W的也可以得到结论，不买房，叶子也一并生成。对于中间的20到40W的数据，我们将进一步进行决策树的完善，用同样的方式，针对剩余的三个纬度进行计算，此处省略。
这就是决策树的生成，后面针对实际工作中的数据，可能需要有剪枝的操作，针对无意义的枝节。剪枝有预剪枝和后剪枝的方式，目的是精简决策树，减少不必要的匹配计算。
python代码来实现
from math import log
import operator
##计算熵
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
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) #log base 2
return shannonEnt
##划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
##选择最佳数据集
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
uniqueVals = set(featList) #get a set of unique values
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 #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
return bestFeature #returns an integer
更多推荐
【机器学习算法】决策树案例详解
发布评论