决策树-ID3算法

决策树

分类决策树模型是一 种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。 决策树学习常用的算法有ID3,C4.5,CART。

特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。

信息增益

在信息论与概率统计中，熵(entropy)表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：
$ P(X=x{i}) = p{i}, i=1,2, \cdot \cdot \cdot, n $ 则随机变量X的熵定义为
$ H(X)=-\sum{i=1}^{n}p{i} \log p_{i} $ ,通常式中的对数以2为底或以e为底。
熵越大，随机变量的不确定性就越大。 (信息增益：定义) 特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
$ g(D,A)= H(D)-H(D|A) $
熵H(Y)与条件熵H(Y|X)之差称为互信息。

 from scipy.stats import entropy
 from collections import Counter
 # 计算熵
 def calcEnt(dataSet):
    num = len(dataSet)
    labelCount = {}
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCount:
            labelCount[label] = 0
        labelCount[label] += 1
    Ent = 0.0
    for k in labelCount:
        prob = float(labelCount[k])/num
        Ent -= prob * log(prob, 2)
    return Ent


def calcEnt2(dataSet):
    dataSet = np.array(dataSet)
    num = len(dataSet)
    labelCount = Counter(dataSet[:,-1]) #使用Counter简化代码

    prod = [float(labelCount[k])/num for k in labelCount]
    Ent = entropy(prod, base=2)        # scipy中提供计算熵的函数

    return Ent


# 对数据集进行切割
def splitData(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 chooseBestFeature(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 特征的数量
    hd = calcEnt2(dataSet)
    bestInfoGain, bestFeature = 0.0, -1

    for i in range(numFeatures):
        featList = [elt[i] for elt in dataSet] #获取特征列表
        uniqueVals = set(featList)     #对特征值进行去重
        newEntropy = 0.0
        for v in uniqueVals:
            # 切割数据计算熵
            subDataSet = splitData(dataSet, i, v)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcEnt2(subDataSet)
        infoGain = hd - newEntropy   # 计算信息增益
        print(infoGain)
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature


# 返回出现次数最多的那项
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount:
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


# 使用字典构造决策树
def createTree(dataSet, labels):
    classList = [elt[-1] for elt in dataSet] #获取分类
    # 如果只有一分类，则只有一个根节点
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 当数据为一维时，返回出现次数最多的项
    if len(dataSet[0]) == 1:
        print('dataSet', dataSet)
        return majorityCnt(classList)
    bestFeat = chooseBestFeature(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel: {}}
    del(labels[bestFeat])
    featValues = [elt[bestFeat] for elt in dataSet]
    uniqueVals = set(featValues)
    print('labels=', labels)

    for v in uniqueVals:
        subLabels = labels[:]
        print('subLabels',subLabels)
        # 使用递归法构建决策树
        myTree[bestFeatLabel][v] = createTree(splitData(dataSet, bestFeat, v), subLabels)
    return myTree


# 使用构建的决策树进行分类
def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    print('featIndex', featIndex)
    print('secondDict', secondDict)
    for k in secondDict:
        if testVec[featIndex] == k:
            if isinstance(secondDict[k], dict):
                classLabel = classify(secondDict[k], featLabels, testVec)
            else:
                classLabel = secondDict[k]
    return classLabel

---

Ref：
1.机器学习实战
2.统计学习方法—李航