Loading...
墨滴

SuperMP

2021/04/20  阅读:70  主题:默认主题

机器学习 | 决策树:ID3算法

死亡的尽头,没有神。

机器学习 | 决策树:ID3算法

1 决策树

决策树是基于树结构来进行决策的。一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点,叶结点对应于决策结果,其他每个结点则对应于一个属性测试。

来源:西瓜书
来源:西瓜书

2 特征(属性)选择

决策树学习的关键是如何选择最优的划分属性(伪代码的第 8 行),因为特征(属性)选择的好坏直接决定了分类的效果是否理想。一般的,决策树算法以信息增益为准则来选择划分属性

那么,在首次划分时,决策树算法计算所有属性的信息增益,选择信息增益最大的属性作为根节点的特征(属性)。然后,递归地对该属性中的不同属性值构成的样本子集重复上述步骤。

2.1 信息熵

信息熵是度量样本集合纯度最常用的一种指标;信息熵越小,样本集的纯度越高。

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

2.2 信息增益

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

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

属性 a 对样本集 D 进行划分所获得的信息增益为(其中, 为当 a 属性的属性值为 时构成的子集)

信息增益越大,意味着用属性 a 来划分时所获得的“纯度提升”越大(即信息增益越大越好)。

直观地理解,当“熵”一定时,“条件熵”越小(即不确定性越小,意味着越有可能发生),那么“信息增益”越大(不确定性减少的程度大,带来的确定信息增加了)。


3 代码实现

3.1 创建数据集

def createDataSet():
    dataSet = [["青绿""蜷缩""浊响""清晰""凹陷""硬滑""好瓜"],
               ["乌黑""蜷缩""沉闷""清晰""凹陷""硬滑""好瓜"],
               ["乌黑""蜷缩""浊响""清晰""凹陷""硬滑""好瓜"],
               ["青绿""蜷缩""沉闷""清晰""凹陷""硬滑""好瓜"],
               ["浅白""蜷缩""浊响""清晰""凹陷""硬滑""好瓜"],
               ["青绿""稍蜷""浊响""清晰""稍凹""软粘""好瓜"],
               ["乌黑""稍蜷""浊响""稍糊""稍凹""软粘""好瓜"],
               ["乌黑""稍蜷""浊响""清晰""稍凹""硬滑""好瓜"],
               ["乌黑""稍蜷""沉闷""稍糊""稍凹""硬滑""坏瓜"],
               ["青绿""硬挺""清脆""清晰""平坦""软粘""坏瓜"],
               ["浅白""硬挺""清脆""模糊""平坦""硬滑""坏瓜"],
               ["浅白""蜷缩""浊响""模糊""平坦""软粘""坏瓜"],
               ["青绿""稍蜷""浊响""稍糊""凹陷""硬滑""坏瓜"],
               ["浅白""稍蜷""沉闷""稍糊""凹陷""硬滑""坏瓜"],
               ["乌黑""稍蜷""浊响""清晰""稍凹""软粘""坏瓜"],
               ["浅白""蜷缩""浊响""模糊""平坦""硬滑""坏瓜"],
               ["青绿""蜷缩""沉闷""稍糊""稍凹""硬滑""坏瓜"],
               ]
    featureMeans = ["色泽""根蒂""敲声""纹理""脐部""触感"]  # 每一列的属性特征
    return dataSet, featureMeans

3.2 计算信息熵

使用每一类标签的频率代替其概率

def calcShannonEnt(dataSet):
    """
    :param dataSet: 给定的数据集
    :return: 计算给定数据集的信息熵.
    """

    numEntries = len(dataSet)
    labelCounts = {}
    keySet = set()
    for featVec in dataSet:
        currentLabel = featVec[-1]  # 每行的最后一个数据为标签
        if currentLabel not in keySet:
            keySet.add(currentLabel)
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1

        shannonEnt = 0.0  # 信息熵
        for key in labelCounts:
            prob = float(labelCounts[key]) / numEntries  # 属于key类的频率
            shannonEnt -= prob * math.log(prob, 2)
    return shannonEnt

3.3 计算信息增益

计算当前划分样本集下各属性的信息增益,选择信息增益最大的属性作为内部结点。

3.3.1 划分数据集
def splitDataSet(dataSet, i, val):
    """
    选择数据集中满足第i个属性的属性值为val的所有样本, 被选定的样本不包含第i个属性
    :param dataSet: 待划分的数据集
    :param i: 按轴i所在的属性划分
    :param val: 需要选择的属性的值
    :return:
    """

    retDataSet = []
    for featVec in dataSet:
        if featVec[i] == val:
            retDataSet.append(featVec[:i] + featVec[i + 1:])  # 不保留axis处的属性
    return retDataSet
3.3.2 选择信息增益最大的属性作为划分属性
def chooseBestFeatureTosplit(dataSet):
    """
    计算当前样本集下每一个属性的信息增益,选择信息增益最大的属性作为划分属性
    :param dataSet: 当前样本集
    :return: 信息增益最大的属性索引及信息增益值
    """

    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet) # 信息熵
    bestInfoGain = 0.0
    bestFeatureIdx = -1
    for i in range(numFeatures):
        uniqueVals = set([example[i] for example in dataSet])  # 第i个属性的所有属性值
        newEntropy = 0.0
        for val in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, val)
            prob = len(subDataSet) * 1.0 / (len(dataSet)) # 频率
            newEntropy += prob * calcShannonEnt(subDataSet) # 条件熵
        infoGain = baseEntropy - newEntropy # 信息增益
        if infoGain > bestInfoGain: # 是否更新属性
            bestInfoGain = infoGain
            bestFeatureIdx = i
    return bestFeatureIdx, bestInfoGain

3.4 决策树算法(ID3算法)

def treeGenerate(dataSet, featureMeans):
    classList = [ex[-1for ex in dataSet]
    # 所有样本的标签完全相同
    if classList.count(classList[0]) == len(classList): return classList[0]
    # 使用完了所有属性, 仍然不能将数据集划分为仅包含唯一类别的分组, 返回值:多数表决
    if len(dataSet[0]) == 1return majorityCnt(classList)

    bestFeatureIdx, _ = chooseBestFeatureTosplit(dataSet) # 【核心代码】
    bestFeatureMean = featureMeans[bestFeatureIdx]  # 索引bestFeatureIdx的含义
    myTree = {bestFeatureMean: {}}
    del (featureMeans[bestFeatureIdx])
    featVals = [ex[bestFeatureIdx] for ex in dataSet]  # 得到当前最好划分特征下的所有属性值
    uniqueVals = set(featVals)
    
    for val in uniqueVals:
        newfeatureMeans = featureMeans[:]  # 列表复制
        newDataSet = splitDataSet(dataSet, bestFeatureIdx, val)
        myTree[bestFeatureMean][val] = createTree(newDataSet, newfeatureMeans)
    return myTree

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        # sortedClassCount = sorted(classCount.items(), key=lambda x: x[1], reverse=True)
    return sortedClassCount[0][0]

3.5 测试决策树算法

程序比较测试数据与决策树上的数值,递归地执行该过程(如果是内部结点),直到进入叶结点,该测试数据的类别即为该叶结点所属的类别。

def classify(inputTree, featureMeans, testVec):
    curNodeStr = list(inputTree.keys())[0]
    curNodeDict = inputTree[curNodeStr]
    featIndex = featureMeans.index(curNodeStr)

    for featVal in curNodeDict.keys():  # 当前内部结点curNodeStr的每一个属性值featVal
        if testVec[featIndex] == featVal:
            if type(curNodeDict[featVal]).__name__ == 'dict':  # 是内部结点, 继续递归
                classLabel = classify(curNodeDict[featVal], featureMeans, testVec)
            else:  # 是叶结点
                classLabel = curNodeDict[featVal]
    return classLabel

3.6 生成的决策树

整体决策树生成和样本测试过程。

myDat, featureMeans = createDataSet()
myTree = treeGenerate(myDat, featureMeans)
print(myTree)
classLabel = classify(myTree, ["色泽""根蒂""敲声""纹理""脐部""触感"], ["乌黑""稍蜷""沉闷""清晰""平坦""软粘"])
print(classLabel) # 预测类别: 坏瓜

{'纹理': {'清晰': {'根蒂': {'稍蜷': {'色泽': {'乌黑': {'触感': {'硬滑': '好瓜', '软粘': '坏瓜'}}, '青绿': '好瓜'}}, '蜷缩': '好瓜', '硬挺': '坏瓜'}}, '稍糊': {'触感': {'硬滑': '坏瓜', '软粘': '好瓜'}}, '模糊': '坏瓜'}}


4 总结

ID3 算法以信息增益准则来划分属性,而信息增益准则对可取属性值种类较多的属性有所偏好

因为,若一个属性 X 可取的属性值有 20 种,而另一个属性 Y 可取的属性值有 3 种,ID3 算法按属性 X 的属性值划分出的样本子集的信息熵 会更小(更纯),从而使得信息增益越大,更可能将 X 作为最优划分属性。

想象一下,对于某一个属性的属性值划分的越细(划分为 100 种和 3 种),是不是划分的越多,相同属性值下的样本越可能属于同一类标签(越纯)。

ID3算法的缺点:

  1. 无法对具有连续属性的样本集进行决策;
  2. 对缺失值没有进行考虑;
  3. 没有考虑过拟合问题;
  4. 对属性值种类较多的属性有所偏好。

参考资料:周志华《机器学习》,李锐《机器学习实战(中文版)》。

SuperMP

2021/04/20  阅读:70  主题:默认主题

作者介绍

SuperMP