机器学习算法之决策树！ID3以及C4.5两种算法区别与联系

>>>> 公众号：数字学吧专注：大数据VS机器学习VS数据挖掘算法vs人工智能vs区块链

熟悉决策树算法的人都知道ID3以及C4.5两种算法，当然也非常清楚信息增益以及信息增益率两个概念。

信息增益：节点M的信息熵E1与其全部子节点信息熵之和E2的差。

信息增益率：节点信息增益与节点分裂信息度量的比值。

信息增益是ID3算法的基础，信息增益率是C4.5算法的基础。同时，C4.5是ID3算法的改进版，改进了某些情况下，决策树构建过程中过拟合的问题。

首先说一下信息增益：

在网上，我们可以轻松找到信息增益的计算公式，乍一看，公式极为简单，只是两个熵减一下，但实际上，当我们去代码实现时，却可能会遇到，究竟该如何计算Entropy(S)跟Gain(S,A)的问题。

S是样本集合这句话描述的并不清晰，对于初学决策树模型的人来说，把S说成所有位于节点M的样本的集合，或许更为恰当。

之所以这么说，是因为下图

同样是刮风的属性，但是，样本的数量却发生的变化，这在决策树的构建过程中是经常遇到的现象。

属性会重复出现？有些人或许会感到不解，但是看weka使用J48跑测试样例的结果，大家或许就能明了了。

在一条从上往下的路径中，petalwidth属性出现了两次呢。

许多刚刚学习决策树的人很难理解为什么计算一个节点的时候需要用到样本（误以为是整个样本）集合，其实这里的样本集合指的是，当前在某个节点N上的样本集合SN；

使用数学话的形式表述信息增益前，定义几个常用的变量，使用变量表示节点A上的样本集合，使用表示在节点A的全部样本中属于类别Ci的样本数量，使用NAm表示在节点A选择属性m的样本数量，用表示选择属性m的样本中，属于类别Ci的样本数量。

这样我们可以表示出节点A的熵为，注意，这里直接使用了概率公式替换了前面公式中的p;

节点A的属性有M个，所以Gain(S,A)即可表述成如下形式

有了信息增益的实际表达式之后，我们再根据信息增益率的描述写出信息增益率的表达式：

信息增益比率实际在信息增益的基础上，又将其除以一个值，这个值一般被成为分裂信息量，是将属性可选值m作为划分，计算节点上样本总的信息熵。

大家可以在网上找到如下公式：

必须说，直接去写S很容易误导人，所以我将公式重写了一下，如下：

然后，我们将之前定义的变量代入到公式中，可以得到GainRatio(SA,A)的最终表达式：

即：

大家一定要注意，计算节点熵和计算节点分类信息量的时候，样本的划分标准一个是类别，一个是节点的可选属性！！

连续值处理

C4.5算法采用二分法对连续属性进行处理，假设当前样本集合在某个连续属性上有n个取值，首先对这n个属性值排序，然后取每两个相邻值的平均值作为划分值来考察。

与离散属性不同，若当前结点划分属性为连续属性，那么该属性还可以作为后代结点的划分属性。

缺失值处理

现实中常常遇到不完整样本，也就是样本在某些属性的取值缺失，此时需要解决两个问题：

1.如何在属性值缺失的情况下进行属性选择

2.给定划分属性，如何对缺失该属性的样本进行划分

解决这两个问题的方法是给每一个样本一个权值，计算信息增益的时候只选用没有缺失值的样本，选择完属性后，让每一个缺失该属性值的样本以不同的概率进入到每个子节点中，也就是将进入这些子节点的该样本的权值置为不同的值。

最后的公式可能有点复杂，但是如果一点一点拼凑起来的话，其实很简单，以此勉励。

Python实现

下面是用python实现ID3的代码，没有新定义结点的数据结构，而是使用了内置的dict类型表示非叶结点结点，对于叶子节点用一个字符串（类标签）。对于每一个非叶结点，只有一个键值为当前结点的划分属性，然后是属性值对应的叶子节点。

例如：

一棵典型的数的根节点是这个样子的：

{‘a’: }}}

其中a，b为属性名，0，1为属性值，yes，no为类别名

fromnumpyimport*frommathimportlogimportoperator# ID3算法defcreateDataSet():dataSet = [[1,1,'yes'], [1,,'no'], [,1,'no'], [,,'no']] feature = ['a','b'] featureValues = [[,1], [,1]]returndataSet, feature, featureValues# 计算熵defcalEnt(dataSet):num = len(dataSet) labelCount = {}fordataindataSet: label = data[-1]iflabelnotinlabelCount: labelCount[label] =labelCount[label] +=1ent =forlabelinlabelCount: p = float(labelCount[label])/num ent -= p * log(p,2)returnent# 划分数据集defsplitByVal(dataSet, axis, val):retDataSet = []fordataindataSet:ifdata[axis] == val: newData = data[:axis] newData.extend(data[axis+1:]) retDataSet.append(newData)returnretDataSet# 选择划分方式defchooseBestFeature(dataSet):numFeatures = len(dataSet[]) -1numVector = len(dataSet) baseEnt = calEnt(dataSet) bestInfoGain =bestFeature = -1foriinrange(numFeatures): featureList = [data[i]fordataindataSet] featureList = set(featureList) currentEnt =forfeatureinfeatureList: tmpDataSet = splitByVal(dataSet, i, feature) tmpLen = len(tmpDataSet) tmpEnt = calEnt(tmpDataSet) currentEnt += tmpEnt * tmpLen / numVector currentInfoGain = baseEnt - currentEntif(currentInfoGain > bestInfoGain): bestFeature = i bestInfoGain = currentInfoGainreturnbestFeature# 找出多数类别deffindMajoritiyClass(dataSet):classCount = {}fordataindataSet: currentClass = data[-1]ifcurrentClassnotinclassCount.keys(): classCount[currentClass] =else: classCount[currentClass] +=1sortedClassCount = sorted(classCount.items(), key=lambdad : d[1], reverse=True)returnsortedClassCount[][]# 建树操作defcreateTreeNode(dataSet, labels, featureValues):classList = [example[-1]forexampleindataSet] majorityClass = findMajoritiyClass(dataSet)# 如果类别相同，将当前节点标记为这个类别ifclassList.count(classList[]) == len(classList):returnclassList[]# 如果当前属性集为空或者样本在属性集中的取值相同# 采用多数表决的方法将当前节点标记为数量最多的类别iflen(dataSet[]) ==1ordataSet.count(dataSet[]) == len(dataSet):returnmajorityClass# 其他情况bestFeature = chooseBestFeature(dataSet) bestFeatureLabel = labels[bestFeature]del(labels[bestFeature]) node = }forvalinfeatureValues[bestFeature]: subLabels = labels[:] subFeatureValues = featureValues[:bestFeature] subFeatureValues.extend(featureValues[bestFeature+1:]) subDataSet = splitByVal(dataSet, bestFeature, val)#如果子集为空，那么输出父节点多数类的标签iflen(subDataSet) ==: node[bestFeatureLabel][val] = majorityClasselse: node[bestFeatureLabel][val] = createTreeNode(subDataSet, subLabels, subFeatureValues) labels.insert(bestFeature, bestFeatureLabel)returnnodedefclassify(node, featureLabels, featureValues, inx):whiletype(node)isdict: firstFeature = list(node.keys())[] featureIndex = featureLabels.index(firstFeature) featureValue = inx[featureIndex] node = node[firstFeature][featureValue]returnnode#自己构造数据集 ，属性集，属性的取值集合dataSet, labels, featureValues = createDataSet()#构造决策树root = createTreeNode(dataSet, labels, featureValues)print(root)#分类，最后一个是要预测的向量classOfX = classify(root, labels, featureValues, [1,1])print(classOfX)print(root)

数字学吧：致力于搭建一个普及最新资讯的交流平台，技术精华的学习平台