决策树算法,Python机器学习之决策树算法

树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性,推导出树形表示的分类判决

图片 12

一、决策树原理

Day

Outlook

Temperature

Humidity

Wind

PlayTennis

1

Sunny

Hot

High

Weak

No

2

Sunny

Hot

High

Strong

No

3

Overcast

Hot

High

Weak

Yes

4

Rain

Mild

High

Weak

Yes

5

Rain

Cool

Normal

Weak

Yes

6

Rain

Cool

Normal

Strong

No

7

Overcast

Cool

Normal

Strong

Yes

8

Sunny

Mild

High

Weak

No

9

Sunny

Cool

Normal

Weak

Yes

10

Rain

Mild

Normal

Weak

Yes

11

Sunny

Mild

Normal

Strong

Yes

12

Overcast

Mild

High

Strong

Yes

13

Overcast

Hot

Normal

Weak

Yes

14

Rain

Mild

High

Strong

No

决策树是用样本的属性作为结点,用属性的取值作为分支的树结构。
决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树是一种知识表示形式,它是对所有样本数据的高度概括决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别。 

对于上面例子,如何判断是否要去playtennis?

决策树算法ID3的基本思想:

可以采用决策树的方式。

首先找出最有判别力的属性,把样例分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。

决策树是一种以实例为基础的归纳学习算法。从无序列/无规则的数据中,推导出树形表示的分类判决。

J.R.Quinlan的工作主要是引进了信息论中的信息增益,他将其称为信息增益(information
gain),作为属性判别能力的度量,设计了构造决策树的递归算法。

优点:计算量小、显示清晰

举例子比较容易理解:

缺点:容易过拟合(需要修枝)(譬如,使用day做判决,一一对应虽然很准确,但是不能用在其他地方)、对时间顺序的数据,需要过多预处理工作

对于气候分类问题,属性为:
天气(A1) 取值为: 晴,多云,雨
气温(A2)  取值为: 冷 ,适中,热
湿度(A3)  取值为: 高 ,正常
风 (A4)  取值为: 有风, 无风

 

每个样例属于不同的类别,此例仅有两个类别,分别为P,N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。
由ID3算法得出一棵正确分类训练集中每个样例的决策树,见下图。

ID3算法:

图片 1

1、对于实例,计算各个属性的信息增益

决策树叶子为类别名,即P
或者N。其它结点由样例的属性组成,每个属性的不同取值对应一分枝。
若要对一样例分类,从树根开始进行测试,按属性的取值分枝向下进入下层结点,对该结点进行测试,过程一直进行到叶结点,样例被判为属于该叶结点所标记的类别。
现用图来判一个具体例子,
某天早晨气候描述为:
天气:多云
气温:冷
湿度:正常
风: 无风

2、对于信息增益最大的属性P作为根节点,P的各个取值的样本作为子集进行分类

它属于哪类气候呢?————-从图中可判别该样例的类别为P类。 

3、对于子集下,若只含有正例或反例,直接得到判决;否则递归调用算法,再次寻找子节点

ID3就是要从表的训练集构造图这样的决策树。实际上,能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。

 

ID3算法:

图片 2

     1. 对当前例子集合,计算各属性的信息增益;
     2. 选择信息增益最大的属性Ak;
     3. 把在Ak处取值相同的例子归于同一子集,Ak取几个值就得几个子集;
     4.对既含正例又含反例的子集,递归调用建树算法;
     5. 若子集仅含正例或反例,对应分枝标上P或N,返回调用处。

 

一般只要涉及到树的情况,经常会要用到递归。 

熵:表示随机变量的不确定性。

对于气候分类问题进行具体计算有:
1、 信息熵的计算:
图片 3其中S是样例的集合,
P(ui)是类别i出现概率:

条件熵:在一个条件下,随机变量的不确定性。

图片 4

信息增益:熵 – 条件熵,在一个条件下,信息不确定性减少的程度。

|S|表示例子集S的总数,|ui|表示类别ui的例子数。对9个正例和5个反例有:
P(u1)=9/14
P(u2)=5/14
H(S)=(9/14)log(14/9)+(5/14)log(14/5)=0.94bit 

 

2、信息增益的计算:图片 5

用信息增益最大的属性作为结点,是因为最终去不去打球的不确定性,在获得该属性的结果后,不确定性大大降低。

其中A是属性,Value(A)是属性A取值的集合,v是A的某一属性值,Sv是S中A的值为v的样例集合,|
Sv |为Sv中所含样例数。

也就是说,该属性对于打球的选择很重要。

以属性A1为例,根据信息增益的计算公式,属性A1的信息增益为

 

图片 6

 

S=[9+,5-] //原样例集中共有14个样例,9个正例,5个反例
S晴=[2+,3-]//属性A1取值晴的样例共5个,2正,3反
S多云=[4+,0-] //属性A1取值多云的样例共4个,4正,0反
S雨=[3+,2-] //属性A1取值晴的样例共5个,3正,2反
故 

对于解决上述问题,

图片 7

首先,计算系统熵,PlayTennis

3、结果为

P(No) = 5/14

图片 8

P(Yes) = 9/14

属性A1的信息增益最大,所以被选为根结点。

Entropy(S) = -(9/14)*log(9/14)-(5/14)*log(5/14) = 0.94

4、建决策树的根和叶子

 

ID3算法将选择信息增益最大的属性天气作为树根,在14个例子中对天气的3个取值进行分枝,3
个分枝对应3 个子集,分别是:

然后,计算各个属性的熵。

图片 9

譬如:Wind

其中S2中的例子全属于P类,因此对应分枝标记为P,其余两个子集既含有正例又含有反例,将递归调用建树算法。

其中,Wind中取值为weak的记录有8条,其中,playtennis的正例6个,负例2个;取值为strong的记录有6条,正例为3个,负例为3个。

5、递归建树

Entrogy(weak) = -(6/8)*log(6/8)-(2/8)*log(2/8) = 0.811

分别对S1和S3子集递归调用ID3算法,在每个子集中对各属性求信息增益.
(1)对S1,湿度属性信息增益最大,以它为该分枝的根结点,再向下分枝。湿度取高的例子全为N类,该分枝标记N。取值正常的例子全为P类,该分枝标记P。
(2)对S3,风属性信息增益最大,则以它为该分枝根结点。再向下分枝,风取有风时全为N类,该分枝标记N。取无风时全为P类,该分枝标记P。

Entrogy(strong) = -(3/6)*log(3/6)-(3/6)*log(3/6) = 1.0

二、PYTHON实现决策树算法分类

对应的信息增益为:

本代码为machine learning in action 第三章例子,亲测无误。
 1、计算给定数据shangnon数据的函数:

Gain(Wind) = Entropy(S) – (8/14)* Entrogy(weak)-(6/14)*
Entrogy(strong) = 0.048

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. 创建数据的函数

同理,Gain(Humidity = 0.151;Gain(Outlook = 0.247;Gain(Temperature =
0.029

def createDataSet(): 
 dataSet = [[1,1,'yes'], 
    [1,1, 'yes'], 
    [1,0,'no'], 
    [0,1,'no'], 
    [0,1,'no']] 
 labels = ['no surfacing','flippers'] 
 return dataSet, labels 

 

3.划分数据集,按照给定的特征划分数据集

此时,可以得到跟节点为:Outlook

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.选择最好的数据集划分方式

Outlook分为三个集合:

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 

Sunny:{1,2,8,9,11},正例:2、反例:3

5.递归创建树

Overcast:{3,7,12,13},正例:4、反例:0

用于找出出现次数最多的分类名称的函数

Rain:{4,5,6,10,14},正例:3、反例:2

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] 

至此,可以得到:

用于创建树的函数代码

Sunny:

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 

Day

Outlook

Temperature

Humidity

Wind

PlayTennis

1

Sunny

Hot

High

Weak

No

2

Sunny

Hot

High

Strong

No

8

Sunny

Mild

High

Weak

No

9

Sunny

Cool

Normal

Weak

Yes

11

Sunny

Mild

Normal

Strong

Yes

然后是在python 名利提示符号输入如下命令:

 

myDat, labels = trees.createDataSet() 
myTree = trees.createTree(myDat,labels) 
print myTree 

Entropy(S) = -(3/5)*log(3/5)-(2/5)*log(2/5) = 0.971

结果是:
{‘no surfacing’: {0: ‘no’, 1: {‘flippers’:
{0: ‘no’, 1: ‘yes’}}}}

对于Wind,weak时,正例为1,反例为2;Strong时,正例为1,反例为1.

6.实用决策树进行分类的函数

Entrogy(weak) = -(1/3)*log(1/3)-(2/3)*log(2/3) = 0.918

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], featLabels, testVec) 
   else: classLabel = secondDict[key] 
 return classLabel 

Entrogy(strong) = -(1/2)*log(1/2)-(1/2)*log(1/2) = 1

在Python命令提示符,输入:
trees.classify(myTree,labels,[1,0]) 

 

得到结果:
‘no’
Congratulation. Oh yeah. You did it.!!!

Gain(Wind) = Entropy(S) – 3/5* Entrogy(weak)-2/5* Entrogy(strong) =
0.0202

 

同理,Gain(Humidity) = 0.971;Gain(Temperature) = 0.571

 

 

此时,可以画出部分决策树:

 

 

图片 10

 

其中,python代码:

import math
#香农公式计算信息熵
def calcShannonEnt(dataset):
    numEntries = len(dataset)
    labelCounts = {}
    for featVec in dataset:
        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*math.log(prob, 2)
    return shannonEnt

def CreateDataSet():
    dataset = [['sunny', 'hot','high','weak', 'no' ],
               ['sunny', 'hot','high','strong', 'no' ],
               ['overcast', 'hot','high','weak', 'yes' ],
               ['rain', 'mild','high','weak', 'yes' ],
               ['rain', 'cool','normal','weak', 'yes' ],
                ['rain', 'cool','normal','strong', 'no' ],
                ['overcast', 'cool','normal','strong', 'yes' ],
                ['sunny', 'mild','high','weak', 'no' ],
                ['sunny', 'cool','normal','weak', 'yes' ],
                ['rain', 'mild','normal','weak', 'yes' ],
                ['sunny', 'mild','normal','strong', 'yes' ],
                ['overcast', 'mild','high','strong', 'yes' ],
                ['overcast', 'hot','normal','weak', 'yes' ],
                ['rain', 'mild','high','strong', 'no' ],
               ]
    labels = ['outlook', 'temperature', 'humidity', 'wind']
    return dataset, labels
#选取属性axis的值value的样本表
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)

    return retDataSet
#选取信息增益最大的属性作为节点
def chooseBestFeatureToSplit(dataSet):
    numberFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numberFeatures):
        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
#对于属性已经用完,仍然没有分类的情况,采用投票表决的方法 
def majorityCnt(classList):
    classCount ={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote] += 1
    return max(classCount)


def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    #类别相同停止划分
    if classList.count(classList[0])==len(classList):
        return classList[0]
    #属性用完,投票表决
    if len(dataSet[0])==1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    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



myDat,labels = CreateDataSet()
tree = createTree(myDat,labels)
print tree

  

 在计算决策树的时候,sklearn库提供了决策树的计算方法(tree),但是,这个库提供的是:

scikit-learn uses an optimised version of the CART algorithm.

对于本文中使用的ID3算法是不支持的。

 然而

该库支持ID3算法。

按照官网说明,注意安装时的依赖库的版本,该升级的升级,该安装的安装即可。‘

from id3 import Id3Estimator
from id3 import export_graphviz

X = [['sunny',    'hot',   'high',   'weak'],
     ['sunny',    'hot',   'high',   'strong'], 
     ['overcast', 'hot',   'high',   'weak'], 
     ['rain',     'mild',  'high',   'weak'], 
     ['rain',     'cool',  'normal', 'weak'], 
     ['rain',     'cool',  'normal', 'strong'], 
     ['overcast', 'cool',  'normal', 'strong'], 
     ['sunny',    'mild',  'high',   'weak'], 
     ['sunny',    'cool',  'normal', 'weak'], 
     ['rain',     'mild',  'normal', 'weak'], 
     ['sunny',    'mild',  'normal', 'strong'], 
     ['overcast', 'mild',  'high',   'strong'], 
     ['overcast', 'hot',   'normal', 'weak'], 
     ['rain',     'mild',  'high',   'strong'], 
]
Y = ['no','no','yes','yes','yes','no','yes','no','yes','yes','yes','yes','yes','no']
f = ['outlook','temperature','humidity','wind']
estimator = Id3Estimator()
estimator.fit(X, Y,check_input=True)
export_graphviz(estimator.tree_, 'tree.dot', f)

  然后通过GraphViz工具生成PDF

dot -Tpdf tree.dot -o tree.pdf

  结果:

图片 11

 

当然,你也可以进行预测判断:

print estimator.predict([['rain',     'mild',  'high',   'strong']])

  图片 12