Loading...
墨滴

SuperMP

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

机器学习 | 决策树:C4.5算法之处理连续属性

Can you hear me?

机器学习 | 决策树:C4.5算法之处理连续属性

建议首先阅读文章:机器学习 | 决策树:ID3算法。因为 ID3 决策树算法对属性值种类较多的属性有所偏好,所以 C4.5 决策树算法不直接使用信息增益,而是使用信息增益和增益率来共同选择最优划分属性。

1 增益率

属性熵:在某一属性下,随机变量的不确定性。

增益率的计算公式为:

其中, 称为属性 a 的固有值,表示数据集 D 按属性 a 的 V 个属性值划分所产生的不确定性。一般的,属性的属性值种类越多(V 越大), 越大。

固有值可以看作一种属性熵,固有值越大,说明该属性的的不确定性也越大。一般的,增益率可以随着属性熵(属性的不确定性)的增大而减小该属性的重要性(反之亦然),这也就导致增益率准则对属性值种类较少的属性有所偏好

为了避免上述偏好,C4.5 算法使用一个启发式:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的属性,作为最优划分属性。这也就是上面说的:使用信息增益和增益率来共同选择最优划分属性。

2 根据启发式实现最优划分属性的选择(针对离散数据集)

此处使用《机器学习 | 决策树:ID3算法》中 3.1 节的数据集。

def chooseBestFeatureTosplit_C4dot5(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestGainRatio = 0.0
    bestFeatureIdx = -1
    infoGainList = []
    gainRatioList = []
    for i in range(numFeatures):
        uniqueVals = set([example[i] for example in dataSet])  # 第i个特征的所有属性值
        newEntropy = 0.0
        intrinsicValue = 0.0
        for val in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, val)
            prob = len(subDataSet) * 1.0 / (len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
            intrinsicValue -= prob * math.log(prob, 2)
        infoGain = baseEntropy - newEntropy
        gainRatio = infoGain / intrinsicValue
        infoGainList.append(infoGain)
        gainRatioList.append(gainRatio)
    avgInfoGain = sum(infoGainList) / len(infoGainList)
    
    for i in range(numFeatures):
        if infoGainList[i] > avgInfoGain and gainRatioList[i] > bestGainRatio: # 启发式
            bestGainRatio = gainRatioList[i]
            bestFeatureIdx = i
    return bestFeatureIdx, bestGainRatio

生成的决策树:

根据启发式生成的决策树
根据启发式生成的决策树
仅根据增益率生成的决策树
仅根据增益率生成的决策树

3 数据集中的连续值处理

各类数据集中并非只有离散化属性,也经常遇到连续属性,如何在决策树学习中使用连续属性?那就是:连续属性离散化:采用二分法将连续属性值一分为二。

对于属性 a 的 n 个不同的属性值(标量),将其升序排序得 ,C4.5 算法将相邻属性值的中位数 作为候选的划分点 ,可以得到包含 个划分点的候选划分点集合

那么,对于属性 a 的最终划分点 如何确定?

答:每次从集合 中选择一个候选划分点 ,这样属性 a 的属性值将会分裂(二分)为两类离散化属性值(根据是否 获得两类离散属性值: / ),由此可以计算每个划分点 下的信息增益 / 增益率,根据信息增益 / 增益率的大小选择最优划分点,作为结点的最优划分属性,即

3.1 根据划分点将数据集一分为二

给出具有离散属性的数据集:

def createDataSet():
    dataSet2 = [["青绿""蜷缩""浊响""清晰""凹陷""硬滑"0.6970.460"好瓜"],
                ["乌黑""蜷缩""沉闷""清晰""凹陷""硬滑"0.7740.376"好瓜"],
                ["乌黑""蜷缩""浊响""清晰""凹陷""硬滑"0.6340.264"好瓜"],
                ["青绿""蜷缩""沉闷""清晰""凹陷""硬滑"0.6080.318"好瓜"],
                ["浅白""蜷缩""浊响""清晰""凹陷""硬滑"0.5560.215"好瓜"],
                ["青绿""稍蜷""浊响""清晰""稍凹""软粘"0.4030.237"好瓜"],
                ["乌黑""稍蜷""浊响""稍糊""稍凹""软粘"0.4810.149"好瓜"],
                ["乌黑""稍蜷""浊响""清晰""稍凹""硬滑"0.4370.211"好瓜"],
                ["乌黑""稍蜷""沉闷""稍糊""稍凹""硬滑"0.6660.091"坏瓜"],
                ["青绿""硬挺""清脆""清晰""平坦""软粘"0.2430.267"坏瓜"],
                ["浅白""硬挺""清脆""模糊""平坦""硬滑"0.2450.057"坏瓜"],
                ["浅白""蜷缩""浊响""模糊""平坦""软粘"0.3430.099"坏瓜"],
                ["青绿""稍蜷""浊响""稍糊""凹陷""硬滑"0.6390.161"坏瓜"],
                ["浅白""稍蜷""沉闷""稍糊""凹陷""硬滑"0.6570.198"坏瓜"],
                ["乌黑""稍蜷""浊响""清晰""稍凹""软粘"0.3600.370"坏瓜"],
                ["浅白""蜷缩""浊响""模糊""平坦""硬滑"0.5930.042"坏瓜"],
                ["青绿""蜷缩""沉闷""稍糊""稍凹""硬滑"0.7190.103"坏瓜"],
                ]
    featMeans2 = ["色泽""根蒂""敲声""纹理""脐部""触感""密度""含糖率"]
    isContinuous2 = [00000011# 0 离散, 1 连续
    return dataSet2, featMeans2, isContinuous2

根据划分点的大小划分数据集:

def splitDataSet_Continuous(dataSet, i, val):
    retDataSetLess, retDataSetBig = [], [] # 小于等于 / 大于划分点的数据集
    for featVec in dataSet:
        # 连续属性要保留axis处的属性
        retDataSetLess.append(featVec) if featVec[i] <= val else retDataSetBig.append(featVec)
    return retDataSetLess, retDataSetBig

注意:与离散属性不同,若当前结点划分属性为连续属性,该属性还可以作为其后代结点的划分属性(即可以重复使用)。

3.2 根据信息增益选择最优划分属性(离散属性+连续属性)

def chooseBestFeatureTosplit_Continuous(dataSet, isContinuous):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeatIdx = -1
    globalBestDivideVal = None  # 全局最优划分值(若最优划分为离散属性,那么无该值)
    for i in range(numFeatures):
        newEntropy = 0.0
        localBestDivideVal = None  # 局部(当前属性)最优划分值(若最优划分为离散属性,那么无该值)
        uniqueVals = set([ex[i] for ex in dataSet])
        if isContinuous[i] == 0:  # 离散属性
            for val in uniqueVals:
                subDataSet = splitDataSet(dataSet, i, val)
                prob = len(subDataSet) * 1.0 / (len(dataSet))
                newEntropy += prob * calcShannonEnt(subDataSet)
        else:  # 连续属性
            sortedUniqueVals = sorted(list(uniqueVals))
            minEntropy = float('inf')
            for j in range(1, len(sortedUniqueVals)):  # 依次判断每个划分点的条件熵, 最小者具有最大信息增益
                dividePointVal = (sortedUniqueVals[j - 1] + sortedUniqueVals[j]) / 2
                subDataSetLess, subDataSetBig = splitDataSet_Continuous(dataSet, i, dividePointVal)
                prob = len(subDataSetLess) * 1.0 / (len(dataSet))
                entropy = prob * calcShannonEnt(subDataSetLess) + (1 - prob) * calcShannonEnt(subDataSetBig)  # 条件熵
                if entropy < minEntropy:
                    minEntropy = entropy
                    localBestDivideVal = dividePointVal
            newEntropy = minEntropy

        infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeatIdx = i
            globalBestDivideVal = localBestDivideVal  # 当离散属性满足if时, 连续属性的划分值将被重置
    return bestFeatIdx, bestInfoGain, globalBestDivideVal

3.3 递归地构建决策树(离散属性+连续属性)

def treeGenerate(dataSet, featMeans, isContinuous):
    classList = [ex[-1for ex in dataSet]
    # 所有样本的标签完全相同
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 使用完了所有特征, 仍然不能将数据集划分为仅包含唯一类别的分组
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeatIdx, _, bestDivideVal = chooseBestFeatureTosplit_Continuous(dataSet, isContinuous)
    if isContinuous[bestFeatIdx] == 0:  # 处理离散属性
        bestFeatMean = featMeans[bestFeatIdx]
        myTree = {bestFeatMean: {}}
        copyFeatureMeans = featMeans[:]
        copyIsContinuous = isContinuous[:]
        # 注意: 离散属性若被选择则不能继续使用, 而连续属性可以继续使用
        del (copyFeatureMeans[bestFeatIdx])
        del (copyIsContinuous[bestFeatIdx])
        uniqueVals = set([ex[bestFeatIdx] for ex in dataSet])
        for val in uniqueVals:
            subDataSet = splitDataSet(dataSet, bestFeatIdx, val)
            myTree[bestFeatMean][val] = treeGenerate(subDataSet, copyFeatureMeans[:], copyIsContinuous[:])
    else:  # 处理连续属性
        bestFeatMean = featMeans[bestFeatIdx] + '≤' + str(round(bestDivideVal, 4))
        myTree = {bestFeatMean: {}}
        subDataSetLess, subDataSetBig = splitDataSet_Continuous(dataSet, bestFeatIdx, bestDivideVal)
        # 递归每一类“离散”属性
        myTree[bestFeatMean]["是"] = treeGenerate(subDataSetLess, featMeans[:], isContinuous[:])
        myTree[bestFeatMean]["否"] = treeGenerate(subDataSetBig, featMeans[:], isContinuous[:])
    return myTree

3.4 测试决策树算法(离散属性+连续属性)

细节之处在于定位属性结点在属性列表中的索引时,离散属性可以直接使用属性结点的字符定位,而连续属性需要通过'≤'分割字符串,通过前一部分定位索引。

def classify_Continuous(inputTree, featMeans, testVec):
    curNodeStr = list(inputTree.keys())[0]
    isCon = True if curNodeStr.find('≤') > -1 else False  # 根据结点的名称判断是否是连续属性
    splitCurNodeStr = curNodeStr.split('≤')[0]

    curNodeDict = inputTree[curNodeStr]
    featIdx = featMeans.index(splitCurNodeStr)  # 根据属性名定位所在位置
    classLabel = None
    for featVal in curNodeDict.keys():  # 当前内部结点curNodeStr的每一个属性值featVal
        if not isCon:  # 离散属性
            if testVec[featIdx] == featVal:
                if type(curNodeDict[featVal]).__name__ == 'dict':  # 是内部结点
                    classLabel = classify_Continuous(curNodeDict[featVal], featMeans, testVec)
                else:  # 是叶结点
                    classLabel = curNodeDict[featVal]
        else:  # 连续属性
            divideVal = float(curNodeStr.split('≤')[1])
            featVal = '是' if testVec[featIdx] <= int(divideVal) else '否'
            if type(curNodeDict[featVal]).__name__ == 'dict':  # 是内部结点
                classLabel = classify_Continuous(curNodeDict[featVal], featMeans, testVec)
            else:  # 是叶结点
                classLabel = curNodeDict[featVal]
    return classLabel

3.5 生成的决策树

myDat, featMeans, isContinuous = createDataSet()
myTree = treeGenerate(myDat, featMeans, isContinuous)
print(myTree)
classLabel = classify_Continuous(myTree, ["色泽""根蒂""敲声""纹理""脐部""触感""密度""含糖率"],
                                 ['浅白''蜷缩''浊响''清晰''凹陷''硬滑'0.5850.112])
print(classLabel) # 好瓜

生成的决策树:{'纹理': {'清晰': {'密度≤0.3815': {'是': '坏瓜', '否': '好瓜'}}, '稍糊': {'触感': {'软粘': '好瓜', '硬滑': '坏瓜'}}, '模糊': '坏瓜'}}

具有连续属性的决策树
具有连续属性的决策树

4 总结

  1. C4.5 决策树算法通过一个启发式解决 ID3 算法对属性值种类较多的属性有所偏好的问题;
  2. C4.5 决策树算法通过二分法将连续属性离散化,解决了 ID3 算法无法对具有连续属性的样本集进行决策的问题;
  3. C4.5 决策树算法还可以处理具有缺失值的样本集(后续学习)。

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

参考资料

[1]

赵赵赵颖: https://blog.csdn.net/leaf_zizi

SuperMP

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

作者介绍

SuperMP