AI机器学习-决策树-python实现C4.5算法

C4.5算法是在ID3算法上的一种改进，它与ID3算法最大的区别就是特征选择上有所不同，一个是基于信息增益比，一个是基于信息增益。

之所以这样做是因为信息增益倾向于选择取值比较多的特征(特征越多，条件熵(特征划分后的类别变量的熵)越小，信息增益就越大)，详细区别可查看之前的文章。

下面我们举例来说明一下，还是以上节的例子，我们加一列，叫名字：

名字,长相,有没有钱,见不见

张三,帅, 有钱, 见

李四,帅, 有钱, 见

王五,帅, 没钱, 不见

赵六,不帅, 有钱, 不见

马七,不帅, 有钱, 不见

按ID3算法，重新运行程序，可以得出下面的决策树结构：

可以发现，名字这个属性的信息增益很大，但是并没有什么实际的意义。这种情况下我们可以用C4.5算法，通过信息增益率来进行条件选择。

根据C4.5算法的定义，某属性的信息增益率等于此属性的信息增益/此属性的信息熵

gainRate(A)=

只需要修改一下条件选择函数，即可实现，新建一个方法chooseBestFeatureToSplit2，内容如下：

#通过递归调用创建决策树,method是指的算法，默认为ID3

defcreateTree(dataSet, labels, method='ID3'):

#获取数据集结果列的数据组成列表

resultList = [example[-1]forexampleindataSet]

ifresultList.count(resultList[0]) == len(resultList): # 列表中的结果集的值相同则直接返回结果值

returnresultList[0]

iflen(dataSet[0]) == 1: #遍历完所有的特征时，仍然不能将数据集划分成仅包含唯一类别的分组 dataSet

returnmajorityCnt(resultList) #由于无法简单的返回唯一的类标签，这里就返回出现次数最多的类别作为返回值

bestFeatColumnIndex=-1

ifmethod =="ID3":

bestFeatColumnIndex = chooseBestFeatureToSplit(dataSet) #ID3算法获取最佳分支属性列索引

ifmethod =="C4.5":

bestFeatColumnIndex = chooseBestFeatureToSplit2(dataSet) # C4.5算法获取最佳分支属性列索引

ifbestFeatColumnIndex == -1: #如果没找出最好的结果，选第一列

bestFeatColumnIndex = 0

bestFeatLabel = labels[bestFeatColumnIndex] #获取最佳分支属性列名称

myTree = }

del(labels[bestFeatColumnIndex]) #把已分配的列名称删除,因为递归调用createTree的时候splitDataSet方法会把当前列去除

featValues = [example[bestFeatColumnIndex]forexampleindataSet] #取出最佳分支列整列的数据组成一个列表

uniqueVals = set(featValues) #把列数据去重，得到此属性的所有可能的不重复取值

forbestFeatColumnUniqueValinuniqueVals:

subLabels = labels[:] # 为了不改变原始列表的内容复制了一下

#递归调用构建决策树

treeResult = createTree(splitDataSet(dataSet,bestFeatColumnIndex, bestFeatColumnUniqueVal), subLabels, method)

myTree[bestFeatLabel][bestFeatColumnUniqueVal] = treeResult

returnmyTree

然后在修改调用方法

myTree = createTree(data, label,"C4.5") 运行后的结果如下图，虽然看上去还是不怎么准确，不过相对来说靠谱了不少。（注，预想应该是长相->是不是有钱，因为是不是有钱这个的增益率和名字的增益率相同，在算法中如果增益率相同，默认取第一个）

关注微信公众号“挨踢学霸”，获取更多技术文章