注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

阿当的博客

世界是个游乐场

 
 
 

日志

 
 

机器学习笔记(2)—— 决策树ID3算法  

2017-09-06 10:01:37|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
决策树算法属于监督学习,用于分类。决策树的构造算法常见的有ID3、C4.5和CART三种算法。这里我们先讲ID3算法。

创建分支的伪代码函数createBranch()如下所示:

检测数据集中的每个子项是否属于同一分类:
if so 
return 类标签
else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch并增加返回结果到分支节点中
return 分支节点


如何划分数据集以帮助数据尽快由混乱变为规则呢?这里有一个重要的概念,就是熵。正确划分数据的方式,就是划分后,熵值最低。

下面是熵值计算的python代码:

from math import log

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


下面是划分数据集的python代码:


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


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):
    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

我们可以简单写几个代码来测试一下他们的运作是否良好:

/*创建数据*/
myDat,labels = createDataSet()    
/*计算数据的熵值*/
calcShannonEnt(myDat)
/*摘取相应的数据子集*/
splitDataSet(myDat,0,1)
/*选择最好的数据集划分方式*/
chooseBestFeatureToSplit(myDat)

在决策树做分类决策时,有可能会遇到一个极端情况 —— 数据集已经处理了所有属性,但是类标签依然不是唯一的。在这种情况下,我们通常会采用多数表决的方法决定叶子节点的分类。

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]


好,下面我们结合前面的函数,做一个创建树的python实现:

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:{}}
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        del(subLabels[bestFeat])
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree


树的返回结果,是一个字典。比如说:

myDat,labels = createDataSet()
myTree = createTree(myDat,labels)
myTree 是
 {
'no surfacing': {
0:'no',
1:{
'flippers':{
0:'no',
1:'yes'
}
}
}
}


树构造完了,接下来,我们怎么使用决策树算法来实现分类功能呢?

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

我们使用一下试试:
myDat,labels = createDataSet()
myTree = createTree(myDat,labels)
classify(myTree,labels,[1,0])     // 'no'
classify(myTree,labels,[1,1])     // 'yes'

最后,决策树较之K近邻算法有一个优点,就是决策树一旦构建出来之后,每次调用classify不需要即时再去和训练样本进行重新训练,可以保存下来,下次直接使用。一个最简单的保存方式,就是使用pickle模块。

def storeTree(inputTree,filename):
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()


def grabTree(filename):
    fr = open(filename)
    return pickle.load(fr)


决策树算法的优点是:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。缺点是:可能会产生过度匹配问题。
  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017