决策树的思想比较简单,不复杂,决策树,就是通过一个属性将数据进行划分,而这个属性的选择也就是决策树的关键,用什么样的属性分开的值尽可能属于同一个类别。
属性选择的方法很多,书中主要介绍了:通过信息增益、增益比率、以及基尼指数.
具体伪代码书中给出:
本文采用了ID3算法划分数据集。该算法采用了一个叫信息增益的概念,关于信息论的部分,曾经写过一文http://www.cnblogs.com/fengbing/archive/2011/12/15/2288801.html中有部分阐述。
我的理解就是,信息是什么,怎么度量,也就是信息经过压缩之后还能代表本身的最小值,这个可以根据霍夫曼编码看出。
具体说明:
考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码,假设符号 Fn 在整条信息中重复出现的概率为 Pn,则该符号的熵也即表示该符号所需的位数位为:
En = - log2( Pn )
整条信息的熵也即表示整条信息所需的位数为:E = ∑En
举个例子,对下面这条只出现了 a b c 三个字符的字符串:
aabbaccbaa
字符串长度为 10,字符 a b c 分别出现了 5 3 2 次,则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2,他们的熵分别为:
Ea = -log2(0.5) = 1
Eb = -log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整条信息的熵也即表达整个字符串需要的位数为:
E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
回想一下如果用计算机中常用的 ASCII 编码,表示上面的字符串我们需要整整 80 位,这样我们就用较少的位数表示较频繁出现的符号。
而这个值不能再小了,再小就不能表示这个信息量了。而这个最小的信息量也就是这个信息的度量。
下面就来上代码
1: # -*- coding: utf-8 -*
2: from math import log
3:
4: def calcShannonEnt(dataSet):
5: numEntries = len(dataSet)#得到数据集总数
6: labelCounts = {}
7: for featVec in dataSet:
8: currentLabel = featVec[-1]#-1表示最后一列
9: #这边处理可能不好理解,初始不在字典中先设为0,再加1,以后再字典中就直接加1
10: #我们可能处理是if no in dictionary,设为1,else +1
11: if currentLabel not in labelCounts.keys():
12: labelCounts[currentLabel] = 0
13: labelCounts[currentLabel] +=1
14: shannonEnt = 0.0
15: for key in labelCounts:
16: prob = float(labelCounts[key])/numEntries
17: shannonEnt -= prob*log(prob,2)
18: return shannonEnt
19:
20: def createDataSet():
21: dataSet = [[1, 1, 'yes'],
22: [1, 1, 'yes'],
23: [1, 0, 'no'],
24: [0, 1, 'no'],
25: [0, 1, 'no']]
26: labels = ['no surfacing','flippers']
27: return dataSet, labels
运行
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> myDat
4: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
5: >>> tree.calcShannonEnt(myDat)
6: 0.9709505944546686
这边求得的熵并不高,也就是说信息量不大,下面根据作者一样,我们增加分类,我们会发现熵变大,即信息量变大。
1: >>> myDat[0][-1]='maybe'
2: >>> myDat
3: [[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
4: >>> tree.calcShannonEnt(myDat)
5: 1.3709505944546687
通过信息增益的概念来构造决策树的方法有ID3,C4.5,C5.0还有通过基尼指数的CART算法。
书中没有介绍通过基尼指数的实现,目前也不实现,等书看完了后续对没有实现的算法再进行实现。
我们知道了信息熵,下面我们就开始划分数据集。
1: #axis第几个特征,value特征的值,以这个特征分类
2: def splitDataSet(dataSet,axis,value):
3: retDataSet = []
4: for featVec in dataSet:
5: if featVec[axis] == value:
6: reduceFeatVec = featVec[:axis]#featVec[:axis],axis=0时返回[]
7: reduceFeatVec.extend(featVec[axis+1:])
8: retDataSet.append(reduceFeatVec)
9: return retDataSet
得到的结果
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> tree.splitDataSet(myDat,0,1)
4: [[1, 'yes'], [1, 'yes'], [0, 'no']]
我们这边是以第一个特征值进行分类,下面我们要对所有的特征值进行分类,计算每个分类下的信息熵。
这样信息增益就是分裂前后的两个信息量的差
1: def chooseBestFeatureToSplit(dataSet):
2: numFeatures = len(dataSet[0]) - 1 #最后一个是类别,特征数是每一行数目减去1
3: baseEntropy = calcShannonEnt(dataSet)#计算数据集原始信息熵
4: bestInfoGain = 0.0; bestFeature = -1
5: for i in range(numFeatures):
6: featList = [example[i] for example in dataSet]#example[i]代表第i列的特征值,在for循环获取这一列的所有值
7: uniqueVals = set(featList) #set是一个无序不重复集跟其他语言一样,这样得到i这一列不同的特征值
8: newEntropy = 0.0
9: for value in uniqueVals:#根据不同的特征值分类计算所占百分比
10: subDataSet = splitDataSet(dataSet, i, value)
11: prob = len(subDataSet)/float(len(dataSet))
12: newEntropy += prob * calcShannonEnt(subDataSet)
13: infoGain = baseEntropy - newEntropy #这是信息增益,是两个信息差
14: if (infoGain > bestInfoGain):
15: bestInfoGain = infoGain
16: bestFeature = i
17: return bestFeature
这个例子的第一步就是(3/5)*(-(2/3)*log(2/3)-(1/3)*log(1/3))+(2/5)*(-1*log1)
没有分类的时候直接计算-(2/5)*log(2/5)-(3/5)*log(3/5)
原始信息熵减去分裂之后的信息熵,就是信息增益,信息增益大的就选择这个特征进行分类。
我们打印出信息增益看出
1: num 0 infoGain 0.419973
2: num 1 infoGain 0.170951
所有以0也就是第一列的特征进行划分。
目前我们给出了第一次特征的划分,下面还要进行第二次的划分,甚至更多,决策树是一种树的形式,我们考虑采用的方式是递归处理。
递归处理要有一个结束条件。
1、遍历了所有的属性,或者每个分支下所有的实例都具有相同的分类。
2、可能会遇到最后没有属性可以划分这个样本子集的时候,我们采用投票原则,多的就为这个样本子集的类别标识,强制为叶子节点
具体代码:
1: def majorityCnt(classList):
2: classCount={}
3: for vote in classList:
4: if vote not in classCount.keys():
5: classCount[vote] = 0
6: classCount[vote] += 1
7: #这个sorted跟sort的区别前面提到,这个是重新建了一个数组,sort是在原有的基础上
8: sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
9: return sortedClassCount[0][0]
10:
11: def createTree(dataSet,labels):
12: classList = [example[-1] for example in dataSet]#得到分类这边是yes no
13: if classList.count(classList[0]) == len(classList): #这边说明都是同一个属性了,不好再分了
14: return classList[0]
15: if len(dataSet[0]) == 1:
16: return majorityCnt(classList)
17: bestFeat = chooseBestFeatureToSplit(dataSet)
18: bestFeatLabel = labels[bestFeat]
19: myTree = {bestFeatLabel:{}}
20: del(labels[bestFeat])
21: featValues = [example[bestFeat] for example in dataSet]
22: uniqueVals = set(featValues)
23: for value in uniqueVals:#分类 递归
24: subLabels = labels[:] #:表示全部
25: myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
26: return myTree
结果:
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> myTree = tree.createTree(myDat,labels)
4: >>> myTree
5: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
这边是采用字典的形式表示这个树形结构的,这个json字符串也有点像,不过决策树的优势在于它的图形表示,下面就通过之前用过的Matplotlib画图。
最终得到如下图:
具体画图这边就不叙述了,没有细看。主要通过得到叶子数,得到数的深度。
下面还是一样,给出一个真实的例子,然后对模型进行正确性评估。
也就是知道这个决策树,我们给出一个特征属性,来判断这个的类别是什么
1:
2: def classify(inputTree,featLabels,testVec):
3: firstStr = inputTree.keys()[0]
4: secondDict = inputTree[firstStr]
5: featIndex = featLabels.index(firstStr)
6: key = testVec[featIndex]
7: valueOfFeat = secondDict[key]
8: if isinstance(valueOfFeat, dict): #判断valueOfFeat是不是字典类型,也就是判断是不是还有子集,有在进行递归判断
9: classLabel = classify(valueOfFeat, featLabels, testVec)
10: else: classLabel = valueOfFeat
11: return classLabel
测试:
1: >>> import tree
2: >>> import treePlotter
3: >>> myTree = treePlotter.retrieveTree(0)
4: >>> myData,labels = tree.createDataSet()
5: >>> tree.classify(myTree,labels,[1,0])
6: 'no'
测试模型
另外我们创建好决策树之后就将其保存,这样要使用直接调用就好。
数据持久保存使用pickle模块,进行基本的数据序列和反序列化
1: #pickle模块实现了基本的数据序列和反序列化
2: def storeTree(inputTree,filename):
3: import pickle
4: fw = open(filename,'w')
5: pickle.dump(inputTree,fw)
6: fw.close()
7:
8: def grabTree(filename):
9: import pickle
10: fr = open(filename)
11: return pickle.load(fr)
使用
1: >>> myTree = {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
2: >>> myTree
3: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
4: >>> tree.storeTree(myTree,'classifierStorage.txt')
5: >>> tree.grabTree('classifierStorage.txt')
6: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
7: >>>
最后作者给出了隐形眼镜的测试,我这边也把其代码列出
1: >>> fr = open('lenses.txt')
2: >>> lenses = [inst.strip().split('\t') for inst in fr.readlines()]
3: >>> lensesLabels = ['age','prescript','astigmatic','tearRate']
4: >>> lensesTree = tree.createTree(lenses,lensesLabels)
5: >>> lensesTree
6: {'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft'}}}}}}
7: >>> import treePlotter
8: >>> treePlotter.createPlot(lensesTree)
最后给出图如下:
这样基本的ID3算法就结束了,不过决策树远不止这么多。
决策树是一个很好的思想,因为其直观,效果也好,普通用户使用甚至可以得出几十年专家的水准。但是它也有很多问题,就关这个特征属性的选择问题,就有很多研究。
我们现在使用了信息增益,之后有C4.5算法采用信息增益比,在这本书的第九章有CART算法采用基尼指数,另外还有距离度量、基于统计的等等。
另外由于在真实世界中没有没有完善的数据,这数据有噪声,而我们刚刚的算法没有考虑这些问题。
还有属性之间是有关联的,这样划分出来的结果也会有问题,最终导致划分过细,而且最后的结果不易于理解。
于是有一些方案来解决这些问题。这个在这本书的第九章会给出一定的解决方案,这个ID3算法就到这边。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:机器学习2决策树 - Python技术站