首页 > 分享 > 决策树挑出好西瓜（基于ID3、C4.6、CART实现）

决策树挑出好西瓜（基于ID3、C4.6、CART实现）

花匠小妙招
2024-12-17 09:11

文章目录一、决策树介绍利用信息增益选择最优划分属性二、实现针对西瓜数据集的ID3算法代码，并输出可视化结果。1、西瓜数据集2. 代码实现（1）建立决策树（2）绘制决策树三、C4.5方法建立决策树四、使用CART算法五、总结六、参考链接

一、决策树介绍

决策树是一种基于树结构来进行决策的分类算法，我们希望从给定的训练数据集学得一个模型（即决策树），用该模型对新样本分类。决策树可以非常直观展现分类的过程和结果，一旦模型构建成功，对新样本的分类效率也相当高。

最经典的决策树算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以处理离散属性样本的分类，C4.5和CART算法则可以处理更加复杂的分类问题。

利用信息增益选择最优划分属性

样本有多个属性，该先选哪个样本来划分数据集呢？原则是随着划分不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一分类，即“纯度”越来越高。先来学习一下“信息熵”和“信息增益”。
信息熵（information entropy）
样本集合D中第k类样本所占的比例（k=1,2,…,|Y|），|Y|为样本分类的个数，则D的信息熵为：
在这里插入图片描述

Ent(D)的值越小，则D的纯度越高。直观理解一下：假设样本集合有2个分类，每类样本的比例为1/2，Ent(D)=1；只有一个分类，Ent（D）= 0，显然后者比前者的纯度高。

信息增益（information gain）

使用属性a对样本集D进行划分所获得的“信息增益”的计算方法是，用样本集的总信息熵减去属性a的每个分支的信息熵与权重（该分支的样本数除以总样本数）的乘积，通常，信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。因此，优先选择信息增益最大的属性来划分。设属性a有V个可能的取值，则属性a的信息增益为：
在这里插入图片描述

增益率（gain ratio）
基于信息增益的最优属性划分原则——信息增益准则
，对可取值数据较多的属性有所偏好。C 4.5 C4.5C4.5算法使用增益率代替信息增益来选择最优划分属性，增益率定义为：
在这里插入图片描述
其中

称为属性 a aa 的固有值。属性 a aa 的可能取值数目越多（即V VV越大），则 I V ( a ) IV(a)IV(a) 的值通常会越大。这在一定程度上消除了对可取值数据较多的属性的偏好。
事实上，增益率准则对可取值数目较少的属性有所偏好，C 4.5 C4.5C4.5 算法并不是直接使用增益率准则，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数（Gini index）
C A R T CARTCART 决策树算法使用基尼指数（Gini index）来选择划分属性。数据集 D DD 的纯度可用基尼值来度量：
在这里插入图片描述

G i n i ( D ) Gini(D)Gini(D) 反应了从数据集 D DD 中随机抽取两个样本，其类别标记不一致的概率。由此，G i n i ( D ) Gini(D)Gini(D) 越小，纯度越高。
属性 a aa 的基尼指数定义为：
在这里插入图片描述
在候选属性集合 A AA 中，选择那个使得划分后基尼指数最小的属性作为最优化分属性。即

二、实现针对西瓜数据集的ID3算法代码，并输出可视化结果。

1、西瓜数据集

在这里插入图片描述

青绿蜷缩浊响清晰凹陷硬滑是
乌黑蜷缩沉闷清晰凹陷硬滑是
乌黑蜷缩浊响清晰凹陷硬滑是
青绿蜷缩沉闷清晰凹陷硬滑是
浅白蜷缩浊响清晰凹陷硬滑是
青绿稍蜷浊响清晰稍凹软粘是
乌黑稍蜷浊响稍糊稍凹软粘是
乌黑稍蜷浊响清晰稍凹硬滑是
乌黑稍蜷沉闷稍糊稍凹硬滑否
青绿硬挺清脆清晰平坦软粘否
浅白硬挺清脆模糊平坦硬滑否
浅白蜷缩浊响模糊平坦软粘否
青绿稍蜷浊响稍糊凹陷硬滑否
浅白稍蜷沉闷稍糊凹陷硬滑否
乌黑稍蜷浊响清晰稍凹软粘否
浅白蜷缩浊响模糊平坦硬滑否
青绿蜷缩沉闷稍糊稍凹硬滑否

2. 代码实现

（1）建立决策树

计算信息熵函数

#计算信息熵 def calcInformationEntropy(dataSet): #dataSet最后一列是类别，前面是特征 dict = {} m = len(dataSet) for i in range(m): #.get()函数：如果没有这个key，就返回默认值；如果有这个key，就返回这个key的value dict[dataSet[i][-1]] = dict.get(dataSet[i][-1], 0) + 1; ent = 0 for key in dict.keys(): p = float(dict[key]) / m ent = ent - (p * np.math.log(p, 2)) return ent 1234567891011121314'

划分数据集函数

#划分数据集 #dataSet:数据集 #axis: 要划分的列下标 #value: 要划分的列的值 def splitDataSet(dataSet, axis, value): splitedDataSet = [] for data in dataSet: if(data[axis] == value): reduceFeatureVec = data[: axis] reduceFeatureVec.extend(data[axis + 1 :]) splitedDataSet.append(reduceFeatureVec) return splitedDataSet 12345678910111213'

计算信息增益函数

#计算信息增益,然后选择最优的特征进行划分数据集 #信息增益的计算公式：西瓜书P75 def chooseBestFeatureToSplit(dataSet): #计算整个集合的熵 EntD = calcInformationEntropy(dataSet) mD = len(dataSet) #行 featureNumber = len(dataSet[0][:]) - 1 #列 maxGain = -1000 bestFeatureIndex = -1 for i in range(featureNumber): #featureSet = set(dataSet[:][i]) #错误写法：dataSet[:][i]仍然是获取行 featureCol = [x[i] for x in dataSet] #取列表某列的方法！！ featureSet = set(featureCol) splitedDataSet = [] for av in featureSet: retDataSet = splitDataSet(dataSet, i, av) splitedDataSet.append(retDataSet) gain = EntD for ds in splitedDataSet: mDv = len(ds) gain = gain - (float(mDv) / mD) * calcInformationEntropy(ds) if(bestFeatureIndex == -1): maxGain = gain bestFeatureIndex = i elif(maxGain < gain): maxGain = gain bestFeatureIndex = i return bestFeatureIndex #当所有的特征划分完了之后，如果仍然有叶子节点中的数据不是同一个类别， # 则把类别最多的作为这个叶子节点的标签 def majorityCnt(classList): dict = {} for label in classList: dict[label] = dict.get(label, 0) + 1 sortedDict = sorted(dict, dict.items(), key = operator.itemgetter(1), reversed = True) return sortedDict[0][0]

123456789101112131415161718192021222324252627282930313233343536373839'

递归构建决策树

#递归构建决策树 def createTree(dataSet, labels): classList = [x[-1] for x in dataSet] # if(len(set(classList)) == 1): # return classList[0] if(classList.count(classList[0]) == len(classList)): return classList[0] elif(len(dataSet[0]) == 1): #所有的属性全部划分完毕 return majorityCnt(classList) else: bestFeatureIndex = chooseBestFeatureToSplit(dataSet) bestFeatureLabel = labels[bestFeatureIndex] myTree = {bestFeatureLabel: {}} del(labels[bestFeatureIndex]) #使用完该属性之后，要删除 featureList = [x[bestFeatureIndex] for x in dataSet] featureSet = set(featureList) for feature in featureSet: subLabels = labels[:] #拷贝一份，防止label在递归的时候被修改（list是传引用调用） tmpDataSet = splitDataSet(dataSet, bestFeatureIndex, feature) #划分数据集 myTree[bestFeatureLabel][feature] = createTree(tmpDataSet, subLabels) return myTree

12345678910111213141516171819202122'

读取数据

#读取西瓜数据集2.0 def readWatermelonDataSet(): ifile = open("西瓜数据集.txt") featureName = ifile.readline() #表头 labels = (featureName.split(' ')[0]).split(',') lines = ifile.readlines() dataSet = [] for line in lines: tmp = line.split('n')[0] tmp = tmp.split(',') dataSet.append(tmp) return dataSet, labels 1234567891011121314'

输出

melonDataSet, melonLabels = readWatermelonDataSet() print(melonLabels) melonBestFeature = chooseBestFeatureToSplit(melonDataSet) tree = createTree(melonDataSet, melonLabels) print(tree) 123456

[‘色泽’, ‘根蒂’, ‘敲声’, ‘纹理’, ‘脐部’, ‘触感’, ‘好瓜’]
{‘纹理’: {‘稍糊’: {‘触感’: {‘软粘’: ‘是’, ‘硬滑’: ‘否’}}, ‘模糊’: ‘否’, ‘清晰’: {‘根蒂’: {‘蜷缩’: ‘是’, ‘稍蜷’: {‘色泽’: {‘乌黑’: {‘触感’: {‘软粘’: ‘否’, ‘硬滑’: ‘是’}}, ‘青绿’: ‘是’}}, ‘硬挺’: ‘否’}}}}

（2）绘制决策树

#使用Matlotlib绘制决策树 import matplotlib.pyplot as plt #设置文本框和箭头格式 decisionNode = dict(boxstyle = "sawtooth", fc = "0.8") leafNode = dict(boxstyle = "round4", fc = "0.8") arrow_args = dict(arrowstyle = "<-") plt.rcParams['font.sans-serif'] = ['SimHei'] plt.rcParams['font.family'] = 'sans-serif' #画节点 def plotNode(nodeTxt, centerPt, parentPt, nodeType): 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): leafNumber = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if(type(secondDict[key]).__name__ == 'dict'): leafNumber = leafNumber + getNumLeafs(secondDict[key]) else: leafNumber += 1 return leafNumber #获取决策树的高度（递归） def getTreeDepth(myTree): maxDepth = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): #test to see if the nodes are dictonaires, if not they are leaf nodes if type(secondDict[key]).__name__=='dict': thisDepth = 1 + getTreeDepth(secondDict[key]) else: thisDepth = 1 if thisDepth > maxDepth: maxDepth = thisDepth return maxDepth #在父子节点添加信息 def plotMidText(cntrPt, parentPt, txtString): xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0] yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1] createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30) #画树 def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on numLeafs = getNumLeafs(myTree) #this determines the x width of this tree depth = getTreeDepth(myTree) firstStr = list(myTree.keys())[0] #the text label for this node should be this 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] plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': plotTree(secondDict[key],cntrPt,str(key)) #recursion else: #it's a leaf node print the leaf node plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode) plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key)) plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD #画布初始化 def createPlot(inTree): fig = plt.figure(1, facecolor='white') fig.clf() axprops = dict(xticks=[], yticks=[]) createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #no ticks #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses plotTree.totalW = float(getNumLeafs(inTree)) plotTree.totalD = float(getTreeDepth(inTree)) plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0; plotTree(inTree, (0.5,1.0), '') plt.show()

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980'

输出结果：
在这里插入图片描述

三、C4.5方法建立决策树

相关数据：
在这里插入图片描述

编号色泽根蒂敲声纹理脐部触感好瓜
1 青绿蜷缩浊响清晰凹陷硬滑是
2 乌黑蜷缩沉闷清晰凹陷硬滑是
3 乌黑蜷缩浊响清晰凹陷硬滑是
4 青绿蜷缩沉闷清晰凹陷硬滑是
5 浅白蜷缩浊响清晰凹陷硬滑是
6 青绿稍蜷浊响清晰稍凹软粘是
7 乌黑稍蜷浊响稍糊稍凹软粘是
8 乌黑稍蜷浊响清晰稍凹硬滑是
9 乌黑稍蜷沉闷稍糊稍凹硬滑否
10 青绿硬挺清脆清晰平坦软粘否
11 浅白硬挺清脆模糊平坦硬滑否
12 浅白蜷缩浊响模糊平坦软粘否
13 青绿稍蜷浊响稍糊凹陷硬滑否
14 浅白稍蜷沉闷稍糊凹陷硬滑否
15 乌黑稍蜷浊响清晰稍凹软粘否
16 浅白蜷缩浊响模糊平坦硬滑否
17 青绿蜷缩沉闷稍糊稍凹硬滑否

导入相关库

#导入相关库 import pandas as pd import graphviz from sklearn.model_selection import train_test_split from sklearn import tree 123456

导入数据

f = open('water.csv','r') data = pd.read_csv(f) x = data[["色泽","根蒂","敲声","纹理","脐部","触感"]].copy() y = data['好瓜'].copy() print(data) 1234567

将特征值数值化

#将特征值数值化 x = x.copy() for i in ["色泽","根蒂","敲声","纹理","脐部","触感"]: for j in range(len(x)): if(x[i][j] == "青绿" or x[i][j] == "蜷缩" or data[i][j] == "浊响" or x[i][j] == "清晰" or x[i][j] == "凹陷" or x[i][j] == "硬滑"): x[i][j] = 1 elif(x[i][j] == "乌黑" or x[i][j] == "稍蜷" or data[i][j] == "沉闷" or x[i][j] == "稍糊" or x[i][j] == "稍凹" or x[i][j] == "软粘"): x[i][j] = 2 else: x[i][j] = 3 y = y.copy() for i in range(len(y)): if(y[i] == "是"): y[i] = int(1) else: y[i] = int(-1)

1234567891011121314151617181920

将数据转换为DataFrame数据类型

#需要将数据x，y转化好格式，数据框dataframe，否则格式报错 x = pd.DataFrame(x).astype(int) y = pd.DataFrame(y).astype(int) print(x) print(y) 123456

在这里插入图片描述
将80%数据用于训练，20%数据用于测试

x_train, x_test, y_train, y_test = train_test_split(x,y,test_size=0.2) print(x_train) 123

在这里插入图片描述
建立模型并训练

sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False) 12345678910111213

可视化决策树

feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"] dot_data = tree.export_graphviz(clf ,feature_names= feature_name ,class_names=["好瓜","坏瓜"] ,filled=True ,rounded=True ,out_file =None ) graph = graphviz.Source(dot_data) graph 1234567891011

在这里插入图片描述

四、使用CART算法

只需要将DecisionTreeClassifier函数的参数criterion的值改为gini：

clf = tree.DecisionTreeClassifier(criterion="gini") #实例化 clf = clf.fit(x_train, y_train) score = clf.score(x_test, y_test) print(score) 12345

画决策树：

# 加上Graphviz2.38绝对路径 import os os.environ["PATH"] += os.pathsep + 'D:/workspace/wrater' feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"] dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","坏瓜"],filled=True,rounded=True,out_file =None) graph = graphviz.Source(dot_data) graph 123456789

在这里插入图片描述