机器学习基础(3)

决策树的特点:

1.优点:计算复杂度不高,输出结果易于理解,对中间值的不敏感,可以处理不相关特征数据。

2.缺点:可能会产生过度匹配的问题。

3.适用数据类型:数值型和标称型。

决策树的一般流程:

1.收集数据:任何适用方法

2.准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。

3.分析数据:可以使用任何方法.但完成后,要检查图形是否符合预期。

4.训练算法:构造数的数据结构。

5.测试算法:使用经验树计算错误率。

6.使用算法:帮助理解。

信息增益

首先明白划分数据集的大原则是:将无序的数据变得更加有序。而在划分数据集之前与之后的信息变化称为信息增益。

香农熵(熵)

如果待分类的事务可能划分在多个分类之中,则符号xi的信息定义为:
$$
l(x_i)=-\log_2p(x_i)
$$

$$
其中p(x_i)是选择该分类的概率。
$$

计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：
$$
H=-\sum_{i=1}^{n}{p(x_i)\log_2p(x_i)}
$$

计算给定数据的香农熵：

from math import log
import operator

def calcshannon(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 * log(prob, 2)
    return shannonEnt

输入自己的creatDataSet()函数

def creatDataSet():
    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:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

选择最好的数据集划分方式：

def chooseBestFeatureToSplit(dataSet):
    numfeature = len(dataSet[0]) - 1
    baseEntropy = calcshannon(dataSet)
    bestInFoGain = 0.0
    bestFeature = -1
    for i in range(numfeature):
        #创建唯一的分类标签列表
        featList = [example[i] for example in dataSet]
        vals = set(featList)
        newEntropy = 0.0
        for value in vals:
            #计算每种分类方式的信息熵
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcshannon(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInFoGain):
           #计算最好的信息增益
            bestInFoGain = infoGain
            bestFeature = i
        return bestFeature

递归构建决策树：

def majority(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():classCount[vote] = 0
        classCount[vote] += 1
    sortedcount = sorted(classCount.iteritems(), \
                         key=operator.itemgetter(1), reverse=True)
    return sortedcount[0][0]

创建树的函数代码

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 majority(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