决策树挑好西瓜
目录
- 一、决策树
- 二、决策树之ID3生成算法
- （1）理论
- （2）代码实现
- 三、决策树之Sklearn库实现ID3、C4.5、CART
- （1）ID3
- （2）C4.5
- （3）CART
- 四、总结
- 五、参考资料
一、决策树
决策树（decision tree）是一种基本的分类与回归方法。一般情况下，回归方法可以转换为分类方。
决策树主要算法有：ID3、C4.5、CART。以及进化后的C4.5算法C5.0、分类有极大提升的Tsallis等算法。这些算法的区别就在于选择最优特征的方式。但C5.0的核心原理与C4.5是相同的，它对于C4.5的改进在于计算速率，尤其是对于大数据，C4.5的速度非常慢，而C5.0对大数据运算效率极高。但C5.0一直是商用算法，之前一直未开源，但官方提供了可将C5.0构建的分类器嵌入到自己组织中的C源码。
二、决策树之ID3生成算法
（1）理论
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)
1.经验熵
2.经验条件熵
看不懂公式没关系，待会有例子直接秒懂！建议看了例子再回来回味下公式的含义哦。
3.信息增益
info_gain(D,A) = H (X) - H (D | A)
简单来说就是我如果把A特征作为本次的根节点，那么熵则变化多少。
（2）代码实现
1.导入包并读取数据
import numpy as np
import pandas as pd
import math
import collectionsdef import_data():data = pd.read_csv('D:\下载软件\watermalon.txt')data.head(10)data=np.array(data).tolist()# 特征值列表labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']# 特征对应的所有可能的情况labels_full = {}for i in range(len(labels)):labelList = [example[i] for example in data]uniqueLabel = set(labelList)labels_full[labels[i]] = uniqueLabelreturn data,labels,labels_full
data,labels,labels_full=import_data()
data
2.计算给定数据集的信息熵
def splitDataSet(dataSet, axis, value):"""按照给定的特征值，将数据集划分:param dataSet: 数据集:param axis: 给定特征值的坐标:param value: 给定特征值满足的条件，只有给定特征值等于这个value的时候才会返回:return:"""# 创建一个新的列表，防止对原来的列表进行修改retDataSet = []# 遍历整个数据集for featVec in dataSet:# 如果给定特征值等于想要的特征值if featVec[axis] == value:# 将该特征值前面的内容保存起来reducedFeatVec = featVec[:axis]# 将该特征值后面的内容保存起来，所以将给定特征值给去掉了reducedFeatVec.extend(featVec[axis + 1:])# 添加到返回列表中retDataSet.append(reducedFeatVec)return retDataSet3.选择最好的数据集划分特征，根据信息增益值来计算
def chooseBestFeatureToSplit(dataSet, labels):"""选择最好的数据集划分特征，根据信息增益值来计算:param dataSet::return:"""# 得到数据的特征值总数numFeatures = len(dataSet[0]) - 1# 计算出基础信息熵baseEntropy = calcShannonEnt(dataSet)# 基础信息增益为0.0bestInfoGain = 0.0# 最好的特征值bestFeature = -1# 对每个特征值进行求信息熵for i in range(numFeatures):# 得到数据集中所有的当前特征值列表featList = [example[i] for example in dataSet]# 将当前特征唯一化，也就是说当前特征值中共有多少种uniqueVals = set(featList)# 新的熵，代表当前特征值的熵newEntropy = 0.0# 遍历现在有的特征的可能性for value in uniqueVals:# 在全部数据集的当前特征位置上，找到该特征值等于当前值的集合subDataSet = splitDataSet(dataSet=dataSet, axis=i, value=value)# 计算出权重prob = len(subDataSet) / float(len(dataSet))# 计算出当前特征值的熵newEntropy += prob * calcShannonEnt(subDataSet)# 计算出“信息增益”infoGain = baseEntropy - newEntropy#print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain)+"i等于"+str(i))#如果当前的信息增益比原来的大if infoGain > bestInfoGain:# 最好的信息增益bestInfoGain = infoGain# 新的最好的用来划分的特征值bestFeature = i#print('信息增益最大的特征为：' + labels[bestFeature])return bestFeature4.判断数据集的各个属性集是否完全一致
def judgeEqualLabels(dataSet):"""判断数据集的各个属性集是否完全一致:param dataSet::return:"""# 计算出样本集中共有多少个属性，最后一个为类别feature_leng = len(dataSet[0]) - 1# 计算出共有多少个数据data_leng = len(dataSet)# 标记每个属性中第一个属性值是什么first_feature = ''# 各个属性集是否完全一致is_equal = True# 遍历全部属性for i in range(feature_leng):# 得到第一个样本的第i个属性first_feature = dataSet[0][i]# 与样本集中所有的数据进行对比，看看在该属性上是否都一致for _ in range(1, data_leng):# 如果发现不相等的，则直接返回Falseif first_feature != dataSet[_][i]:return Falsereturn is_equal5.创建决策树
def createTree(dataSet, labels):"""创建决策树:param dataSet: 数据集:param labels: 特征标签:return:"""# 拿到所有数据集的分类标签classList = [example[-1] for example in dataSet]# 统计第一个标签出现的次数，与总标签个数比较，如果相等则说明当前列表中全部都是一种标签，此时停止划分if classList.count(classList[0]) == len(classList):return classList[0]# 计算第一行有多少个数据，如果只有一个的话说明所有的特征属性都遍历完了，剩下的一个就是类别标签，或者所有的样本在全部属性上都一致if len(dataSet[0]) == 1 or judgeEqualLabels(dataSet):# 返回剩下标签中出现次数较多的那个return majorityCnt(classList)# 选择最好的划分特征，得到该特征的下标bestFeat = chooseBestFeatureToSplit(dataSet=dataSet, labels=labels)print(bestFeat)# 得到最好特征的名称bestFeatLabel = labels[bestFeat]print(bestFeatLabel)# 使用一个字典来存储树结构，分叉处为划分的特征名称myTree = {bestFeatLabel: {}}# 将本次划分的特征值从列表中删除掉del(labels[bestFeat])# 得到当前特征标签的所有可能值featValues = [example[bestFeat] for example in dataSet]# 唯一化，去掉重复的特征值uniqueVals = set(featValues)# 遍历所有的特征值for value in uniqueVals:# 得到剩下的特征标签subLabels = labels[:]subTree = createTree(splitDataSet(dataSet=dataSet, axis=bestFeat, value=value), subLabels)# 递归调用，将数据集中该特征等于当前特征值的所有数据划分到当前节点下，递归调用时需要先将当前的特征去除掉myTree[bestFeatLabel][value] = subTreereturn myTree6.输出
mytree=createTree(data,labels)
print(mytree)
7.绘画可视化决策树
import matplotlib.pylab as plt
import matplotlib# 能够显示中文
matplotlib.rcParams['font.sans-serif'] = ['SimHei']
matplotlib.rcParams['font.serif'] = ['SimHei']# 分叉节点，也就是决策节点
decisionNode = dict(boxstyle="sawtooth", fc="0.8")# 叶子节点
leafNode = dict(boxstyle="round4", fc="0.8")# 箭头样式
arrow_args = dict(arrowstyle="<-")def plotNode(nodeTxt, centerPt, parentPt, nodeType):"""绘制一个节点:param nodeTxt: 描述该节点的文本信息:param centerPt: 文本的坐标:param parentPt: 点的坐标，这里也是指父节点的坐标:param nodeType: 节点类型,分为叶子节点和决策节点:return:"""createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',xytext=centerPt, textcoords='axes fraction',va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)def getNumLeafs(myTree):"""获取叶节点的数目:param myTree::return:"""# 统计叶子节点的总数numLeafs = 0# 得到当前第一个key，也就是根节点firstStr = list(myTree.keys())[0]# 得到第一个key对应的内容secondDict = myTree[firstStr]# 递归遍历叶子节点for key in secondDict.keys():# 如果key对应的是一个字典，就递归调用if type(secondDict[key]).__name__ == 'dict':numLeafs += getNumLeafs(secondDict[key])# 不是的话，说明此时是一个叶子节点else:numLeafs += 1return numLeafsdef getTreeDepth(myTree):"""得到数的深度层数:param myTree::return:"""# 用来保存最大层数maxDepth = 0# 得到根节点firstStr = list(myTree.keys())[0]# 得到key对应的内容secondDic = myTree[firstStr]# 遍历所有子节点for key in secondDic.keys():# 如果该节点是字典，就递归调用if type(secondDic[key]).__name__ == 'dict':# 子节点的深度加1thisDepth = 1 + getTreeDepth(secondDic[key])# 说明此时是叶子节点else:thisDepth = 1# 替换最大层数if thisDepth > maxDepth:maxDepth = thisDepthreturn maxDepthdef plotMidText(cntrPt, parentPt, txtString):"""计算出父节点和子节点的中间位置，填充信息:param cntrPt: 子节点坐标:param parentPt: 父节点坐标:param txtString: 填充的文本信息:return:"""# 计算x轴的中间位置xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]# 计算y轴的中间位置yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]# 进行绘制createPlot.ax1.text(xMid, yMid, txtString)def plotTree(myTree, parentPt, nodeTxt):"""绘制出树的所有节点，递归绘制:param myTree: 树:param parentPt: 父节点的坐标:param nodeTxt: 节点的文本信息:return:"""# 计算叶子节点数numLeafs = getNumLeafs(myTree=myTree)# 计算树的深度depth = getTreeDepth(myTree=myTree)# 得到根节点的信息内容firstStr = list(myTree.keys())[0]# 计算出当前根节点在所有子节点的中间坐标,也就是当前x轴的偏移量加上计算出来的根节点的中心位置作为x轴（比如说第一次：初始的x偏移量为：-1/2W,计算出来的根节点中心位置为：(1+W)/2W，相加得到：1/2），当前y轴偏移量作为y轴cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)# 绘制该节点与父节点的联系plotMidText(cntrPt, parentPt, nodeTxt)# 绘制该节点plotNode(firstStr, cntrPt, parentPt, decisionNode)# 得到当前根节点对应的子树secondDict = myTree[firstStr]# 计算出新的y轴偏移量，向下移动1/D，也就是下一层的绘制y轴plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD# 循环遍历所有的keyfor key in secondDict.keys():# 如果当前的key是字典的话，代表还有子树，则递归遍历if isinstance(secondDict[key], dict):plotTree(secondDict[key], cntrPt, str(key))else:# 计算新的x轴偏移量，也就是下个叶子绘制的x轴坐标向右移动了1/WplotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW# 打开注释可以观察叶子节点的坐标变化# print((plotTree.xOff, plotTree.yOff), secondDict[key])# 绘制叶子节点plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)# 绘制叶子节点和父节点的中间连线内容plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))# 返回递归之前，需要将y轴的偏移量增加，向上移动1/D，也就是返回去绘制上一层的y轴plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalDdef createPlot(inTree):"""需要绘制的决策树:param inTree: 决策树字典:return:"""# 创建一个图像fig = plt.figure(1, facecolor='white')fig.clf()axprops = dict(xticks=[], yticks=[])createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)# 计算出决策树的总宽度plotTree.totalW = float(getNumLeafs(inTree))# 计算出决策树的总深度plotTree.totalD = float(getTreeDepth(inTree))# 初始的x轴偏移量，也就是-1/2W，每次向右移动1/W，也就是第一个叶子节点绘制的x坐标为：1/2W，第二个：3/2W，第三个：5/2W，最后一个：(W-1)/2WplotTree.xOff = -0.5/plotTree.totalW# 初始的y轴偏移量，每次向下或者向上移动1/DplotTree.yOff = 1.0# 调用函数进行绘制节点图像plotTree(inTree, (0.5, 1.0), '')# 绘制plt.show()if __name__ == '__main__':createPlot(mytree)得到图形：
三、决策树之Sklearn库实现ID3、C4.5、CART
（1）ID3
1.导入包,输出数据
# 导入包
import pandas as pd
from sklearn import tree
import graphviz
df = pd.read_csv('D:\下载软件\watermalon.txt')
df.head(10)
2.将特征值全部转化为数字，并绘图
df['色泽']=df['色泽'].map({'浅白':1,'青绿':2,'乌黑':3})
df['根蒂']=df['根蒂'].map({'稍蜷':1,'蜷缩':2,'硬挺':3})
df['敲声']=df['敲声'].map({'清脆':1,'浊响':2,'沉闷':3})
df['纹理']=df['纹理'].map({'清晰':1,'稍糊':2,'模糊':3})
df['脐部']=df['脐部'].map({'平坦':1,'稍凹':2,'凹陷':3})
df['触感'] = np.where(df['触感']=="硬滑",1,2)
df['好瓜'] = np.where(df['好瓜']=="是",1,0)
x_train=df[['色泽','根蒂','敲声','纹理','脐部','触感']]
y_train=df['好瓜']
print(df)
id3=tree.DecisionTreeClassifier(criterion='entropy')
id3=id3.fit(x_train,y_train)
print(id3)id3=tree.DecisionTreeClassifier(criterion='entropy')
id3=id3.fit(x_train,y_train)
labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
dot_data = tree.export_graphviz(id3
,feature_names=labels
,class_names=["好瓜","坏瓜"]
,filled=True
,rounded=True
)
graph = graphviz.Source(dot_data)
graph
（2）C4.5
1.前面和ID3差不多，就需要改一个把得到信息增益的那步再增加一步，得到信息增益率
## 实现C4.5算法
def chooseBestFeatureToSplit_4(dataSet, labels):"""选择最好的数据集划分特征，根据信息增益值来计算:param dataSet::return:"""# 得到数据的特征值总数numFeatures = len(dataSet[0]) - 1# 计算出基础信息熵baseEntropy = calcShannonEnt(dataSet)# 基础信息增益为0.0bestInfoGain = 0.0# 最好的特征值bestFeature = -1# 对每个特征值进行求信息熵for i in range(numFeatures):# 得到数据集中所有的当前特征值列表featList = [example[i] for example in dataSet]# 将当前特征唯一化，也就是说当前特征值中共有多少种uniqueVals = set(featList)# 新的熵，代表当前特征值的熵newEntropy = 0.0# 遍历现在有的特征的可能性for value in uniqueVals:# 在全部数据集的当前特征位置上，找到该特征值等于当前值的集合subDataSet = splitDataSet(dataSet=dataSet, axis=i, value=value)# 计算出权重prob = len(subDataSet) / float(len(dataSet))# 计算出当前特征值的熵newEntropy += prob * calcShannonEnt(subDataSet)# 计算出“信息增益”infoGain = baseEntropy - newEntropyinfoGain = infoGain/newEntropy#print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain)+"i等于"+str(i))#如果当前的信息增益比原来的大if infoGain > bestInfoGain:# 最好的信息增益bestInfoGain = infoGain# 新的最好的用来划分的特征值bestFeature = i#print('信息增益最大的特征为：' + labels[bestFeature])return bestFeature2.结果
（3）CART
1.加包并输出数据
import pandas as pd
from sklearn import tree
import graphviz
df = pd.read_csv('D:\下载软件\watermalon.txt')
df.head(10)2.将特征值化为数字，训练得到树，并且可视化
df['色泽']=df['色泽'].map({'浅白':1,'青绿':2,'乌黑':3})
df['根蒂']=df['根蒂'].map({'稍蜷':1,'蜷缩':2,'硬挺':3})
df['敲声']=df['敲声'].map({'清脆':1,'浊响':2,'沉闷':3})
df['纹理']=df['纹理'].map({'清晰':1,'稍糊':2,'模糊':3})
df['脐部']=df['脐部'].map({'平坦':1,'稍凹':2,'凹陷':3})
df['触感'] = np.where(df['触感']=="硬滑",1,2)
df['好瓜'] = np.where(df['好瓜']=="是",1,0)
x_train=df[['色泽','根蒂','敲声','纹理','脐部','触感']]
y_train=df['好瓜']print(df)
gini=tree.DecisionTreeClassifier(criterion='entropy')
gini=id3.fit(x_train,y_train)
print(gini)# 构建模型并训练
gini=tree.DecisionTreeClassifier()
gini=gini.fit(x_train,y_train)
#实现决策树的可视化
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
gini_data = tree.export_graphviz(gini
,feature_names=labels
,class_names=["好瓜","坏瓜"]
,filled=True
,rounded=True
)
gini_graph = graphviz.Source(gini_data)
gini_graph
结果：
四、总结
决策树作为经典分类算法，具有计算复杂度低、结果直观、分类效率高等优点，ID3决策树利用信息增益来选择最优划分属性，它可以处理标称型数据，无法处理连续和缺失值。C4.5算法，它可以处理连续值和缺失值，而且增加了剪枝过程来应对过拟合现象。CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。
五、参考资料
决策树ID3详解（西瓜案例）
机器学习笔记（4）——ID3决策树算法及其Python实现
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！