Python与机器学习 C4.5决策树算法

Reply Share

针对ID3算法存在的一些问题，Quinlan将ID3改进为C4.5算法，该算法成功地解决了ID3算法遇到的诸多问题。

信息增益率

C4.5并没有改变ID3的算法逻辑，基本的程序结构仍与ID3相同，但在节点的划分标准做了改进。 C4.5使用信息增益率来替代信息增益进行特征选择，克服了信息增益选择特征时偏向于特征值个数较多的不足。 信息增益率的定义为：

其中Gain(S,A)就是ID3算法中的信息增益，而划分信息SplitInfo(S,A)代表了按照特征A划分样本集S的广度和均匀性。

其中，Si到S是特征A的C个不同值构成的样本子集。

代码实现

C4.5在节点的划分标准上做了改进，代码部分很大程度上没有改动。
(1) 使用信息增益率划分最优节点的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def getBestFeat(self,dataSet):
	Num_Feats=len(dataSet[0][:-1])
	totality=len(dataSet)
	BaseEntropy=self.computeEntropy(dataSet)
	ConditionEntropy=[]    #初始化条件熵
	sliptInfo=[]           #计算增长率
	allFeatVList=[]
	for f in xrange(Num_Feats):
		featList=[example[f] for example in dataSet]
		[splitI,featureValueList]=self.computeSplitInfo(featList)
		allFeatVList.append(splitI)
		resultGain=0.0
		for value in featureValueList:
			subSet=self.splitDataSet(dataSet,f,value)
			appearNum=float(len(subSet))
			subEntropy=self.computeEntropy(subSet)
			resultGain+=(appearNum/totality)*subEntropy
		ConditionEntropy.append(resultGain)   #总条件熵
	infoGainArray=BaseEntropy*ones(Num_Feats)-array(ConditionEntropy)
	infoGainRatio=infoGainArray/array(sliptInfo)   #信息增长率的计算
	bestFeatureIndex=argsort(-infoGainRatio)[0]
	return bestFeatureIndex,allFeatVList[bestFeatureIndex]

(2)计算划分信息（SplitInfo）

1
2
3
4
5
6
7
8
def computeSplitInfo(self,featureVList):
	numEntries=len(featureVList)
	featureVauleSetList=list(set(featureVList))
	valueCounts=[featureVList.count(featVec) for featVec in featureVauleSetList]
	pList=[float(item)/numEntries for item in valueCounts]
	lList=[item*math.log(item,2) for item in pList]
	splitInfo=-sum(lList)
	return splitInfo,featureVauleSetList

(3)决策树函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def builtTree(self,dataSet,labels):
	cateList=[data[-1] for data in dataSet]
	if cateList.count(cateList[0])==len(cateList):
		return cateList[0]
	if len(dataSet[0])==1:
		return self.maxCate(cateList)
	bestFeat,featureValueList=self.getBestFeat(dataSet)
	bestFeatLabel=labels[bestFeat]
	tree={bestFeatLabel:{}}
	del(labels[bestFeat])
	for value in featureValueList:
		subLabels=labels[:]
		splitDataSet=self.splitDataSet(dataSet,bestFeat,value)
		subTree=self.builtTree(splitDataSet,subLabels)
		tree[bestFeatLabel][value]=subTree
	return tree

1