机器学习课上决策树小demo决策树+随机森林+预剪枝

from math import log2 #计算熵 def calcShannonEnt(dataSet): numEntires = len(dataSet) #返回数据集的行数 labelCounts = {} #保存每个标签(Label)出现次数的字典 for featVec in dataSet: #对每组特征向量进行统计 currentLabel = featVec[-1] #提取标签(Label)信息 if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去 labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 #Label计数 shannonEnt = 0.0 #经验熵(香农熵) for key in labelCounts: #计算香农熵 prob = float(labelCounts[key]) / numEntires #选择该标签(Label)的概率 shannonEnt -= prob * log2(prob) #利用公式计算 return shannonEnt #返回经验熵(香农熵) def splitDataSet(dataSet, i, value): retDataSet = [] #创建返回的数据集列表 for featVec in dataSet: #遍历数据集 if featVec[i] == value: reducedFeatVec = featVec[:i] #去掉axis特征 reducedFeatVec.extend(featVec[i+1:]) #将符合条件的添加到返回的数据集 retDataSet.append(reducedFeatVec) return retDataSet def major(dataSet): featList = [example[-1] for example in dataSet] data_num = {} for i in featList: data_num[i] = data_num.get(i, 0) + 1 data_num=sorted(data_num, key=None, reverse=True) return data_num[0] def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 # 特征数量 baseEntropy = calcShannonEnt(dataSet) # 计算数据集的香农熵 bestInfoGain = 0.0 # 信息增益 bestFeature = -1 # 最优特征的索引值 for i in range(numFeatures): # 遍历所有特征 #获取第i个特征 featList = [example[i] for example in dataSet] uniqueVals = set(featList) #创建set集合{},元素不可重复 newEntropy = 0.0 #经验条件熵 for value in uniqueVals: # 计算信息增益 subDataSet = splitDataSet(dataSet, i, value) #subDataSet划分后的子集 prob = len(subDataSet) / float(len(dataSet)) # 计算子集的概率 newEntropy += prob * calcShannonEnt(subDataSet) # 根据公式计算经验条件熵 infoGain = baseEntropy - newEntropy # 该类别的信息增益 if (infoGain > bestInfoGain): # 计算信息增益 bestInfoGain = infoGain # 更新信息增益，找到最大的信息增益 bestFeature = i # 记录信息增益最大的特征的索引值 return bestFeature # 返回信息增益最大的特征的索引值 # 建立表 def createTree(dataSet, labels, featLabels): classList = [example[-1] for example in dataSet] # 取分类标签 jilu=set(classList) if len(jilu) == 1: # 如果类别完全相同则停止继续划分 return classList[0] if len(dataSet)<4: #预剪枝，如果样本个数少于4个，则停止划分，将主要的类别作为返回结果 return major(dataSet) bestFeat = chooseBestFeatureToSplit(dataSet) # 选择最优特征 bestFeatLabel = labels[bestFeat] # 最优特征的标签 featLabels.append(bestFeatLabel) myTree = {bestFeatLabel: {}} # 根据最优特征的标签生成树 # del(labels[bestFeat]) #删除已经使用特征标签 featValues = [example[bestFeat] for example in dataSet] # 得到训练集中所有最优特征的属性值 uniqueVals = set(featValues) # 去掉重复的属性值 for value in uniqueVals: # 遍历特征，创建决策树。 del_bestFeat = bestFeat del_labels = labels[bestFeat] del (labels[bestFeat]) myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels) labels.insert(del_bestFeat, del_labels) return myTree def predict(mytree,testVec): classLabel='坏' firstStr = next(iter(mytree)) #获取决策树结点 secondDict = mytree[firstStr] # 下一个字典 featIndex=-1 if firstStr== '色泽': featIndex = 0 elif firstStr== '根蒂': featIndex = 1 elif firstStr== '敲声': featIndex = 2 elif firstStr== '纹理': featIndex =3 elif firstStr =='脐部': featIndex =4 elif firstStr =='触感': featIndex =5 for key in secondDict.keys(): if testVec[featIndex] == key: if type(secondDict[key]).__name__ == 'dict': classLabel = predict(secondDict[key], testVec) else: classLabel = secondDict[key] return classLabel