Python机器学习之决策树算法
|
一、决策树原理 决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。 决策树算法ID3的基本思想： 首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。 J.R.Quinlan的工作主要是引进了信息论中的信息增益，他将其称为信息增益（information gain），作为属性判别能力的度量，设计了构造决策树的递归算法。 举例子比较容易理解： 对于气候分类问题，属性为: 每个样例属于不同的类别，此例仅有两个类别，分别为P，N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。
决策树叶子为类别名，即P 或者N。其它结点由样例的属性组成，每个属性的不同取值对应一分枝。 它属于哪类气候呢?-------------从图中可判别该样例的类别为P类。 ID3就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。 ID3算法： 1. 对当前例子集合，计算各属性的信息增益； 一般只要涉及到树的情况，经常会要用到递归。 对于气候分类问题进行具体计算有：
|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有： 2、信息增益的计算:
其中A是属性，Value(A)是属性A取值的集合，v是A的某一属性值，Sv是S中A的值为v的样例集合，| Sv |为Sv中所含样例数。 以属性A1为例，根据信息增益的计算公式，属性A1的信息增益为
S=[9+,5-] //原样例集中共有14个样例，9个正例，5个反例
3、结果为
属性A1的信息增益最大，所以被选为根结点。 4、建决策树的根和叶子 ID3算法将选择信息增益最大的属性天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:
其中S2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。 5、递归建树 分别对S1和S3子集递归调用ID3算法，在每个子集中对各属性求信息增益. 二、PYTHON实现决策树算法分类 本代码为machine learning in action 第三章例子，亲测无误。
def calcShannonEnt(dataSet):
#calculate the shannon value
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #create the dictionary for all of the data
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) #get the log value
return shannonEnt
2. 创建数据的函数 def createDataSet(): dataSet = [[1,1,'yes'],[1,'no'],[0,'no']] labels = ['no surfacing','flippers'] return dataSet,labels 3.划分数据集，按照给定的特征划分数据集 def splitDataSet(dataSet,axis,value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: #abstract the fature reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet 4.选择最好的数据集划分方式 def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0])-1 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 5.递归创建树 用于找出出现次数最多的分类名称的函数
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
用于创建树的函数代码
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
# the type is the same,so stop classify
if classList.count(classList[0]) == len(classList):
return classList[0]
# traversal all the features and choose the most frequent feature
if (len(dataSet[0]) == 1):
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
#get the list which attain the whole properties
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
然后是在python 名利提示符号输入如下命令： myDat,labels = trees.createDataSet() myTree = trees.createTree(myDat,labels) print myTree 结果是： 6.实用决策树进行分类的函数
def classify(inputTree,featLabels,testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key],testVec)
else: classLabel = secondDict[key]
return classLabel
在Python命令提示符，输入： 得到结果： 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程小技巧。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
