网站前台代码,济南网站推广效果,成都地铁建设分公司网站,网页设计代码中相对定位在生活中我们经常会用到决策树算法#xff0c;最简单的就是二叉树了#xff1b;相信大家也会又同样的困扰#xff0c;手机经常收到各种短信#xff0c;其中不乏很多垃圾短信、此时只要设置这类短信为垃圾短信手机就会自动进行屏蔽、减少被骚扰的次数#xff0c;同时正常短… 在生活中我们经常会用到决策树算法最简单的就是二叉树了相信大家也会又同样的困扰手机经常收到各种短信其中不乏很多垃圾短信、此时只要设置这类短信为垃圾短信手机就会自动进行屏蔽、减少被骚扰的次数同时正常短信又不会被阻拦。类似这种就是决策树的工作原理决策树的一个重要任务是为了理解数据中所含的信息可以使用决策树不熟悉的数据集合并从中体取一系列规则这些机器根据数据集创建规则的过程就是机器学习的过程。决策树优缺点优点计算复杂度不高输出结果易于理解、即对模型的输出结果的可解释性要高对中间值的缺失不敏感可以处理不相关数据缺点可能会产生过拟合现象决策树的构建输入数据集输出构建好的决策树(训练集)def 创建决策树 if(数据集中所有样本分类一致) 创建携带类标签的叶子节点else 寻找划分数据集最好的特征 根据最好特征划分数据集 for每个划分的数据集 创建决策子树(递归完成)决策树的关键在于当前数据集上选择哪个特征属性作为划分的条件(能够将本来无序的数据集最大程度的划分为有序的子集)度量最佳分类属性特征的“最佳性”可用非纯度进行衡量如果一个数据集只有一种分类结果则该数据集一致性好、能够提供的信息也最少只有一种情况如果数据集有很多分类则该数据集的一致性不好能够提供的信息也较多至少确定不只一种。组织杂乱数据的一种方法就是使用信息论度量信息在划分数据前后信息发生的变化称为信息增益、这里描述集合信息的度量方式称为香农熵或者简称熵。(该名字来源于克劳德.香农、二十实际最聪明的人之一)。熵定义为信息的期望值为了计算熵、我们需要计算所有类别的可能值所包含的信息期望。熵计算公式明确决策树分类选择特征的依据后先梳理下决策树的流程都有哪些1、收集数据一切可以使用的方法、只要不违法2、准备数据树构造算法只适用于标准型数据因此数据值必须离散化3、分析数据可以使用任何方法数据构建完成后需看下是否达到了我们的预期4、训练算法构建树的数据结构5、测试算法使用构建好的树计算正确率越高当然越好(也可能过拟合、不能过份高了)6、使用算法。为了后面更好的理解决策树利用如下数据我们先套用下公式直观的计算一下什么是信息熵、什么是信息增益以及如何选择一个特征作为当前数据的划分条件以便后面更好的撸代码。经典的样例数据Day天气温度湿度风决定1晴热高弱N2晴热高强N3阴热高弱Y4雨中高弱Y5雨凉正常弱Y6雨凉正常强N7阴凉正常强Y8晴中高弱N9晴凉正常弱Y10雨中正常弱Y11晴中正常强Y12阴中高强Y13阴热正常弱Y14雨中高强N根据信息熵的公式此数据比较简单、我们可以手工计算一下各个特征的信息增益从而知道ID3算法具体选择哪个特征作为分类的依据和算法的一个计算过程。先列一下公式、参照公式带入计算减小手工计算误差计算数据集(D)的经验熵一个特征(A)对数据集(D)的经验条件熵那么相对特征(A)此时的信息增益计算公式为以上4个特征中天气(晴、阴雨)/温度(热、适中、凉)/湿度(高、正常)/风(强弱)推算过程中我们选择湿度或风、这两个特征值分布均只含两个值计算过程的时候相对要简单一点。第一步计算该数据集的经验熵该数据集共有14条数据9条决定为Y、5条决定为N则p(Y)9/14、p(N)5/14。此时代入公式第二步选择风这个特征计算该特征相对数据集的经验熵从数据可以看出风共有两个值强和弱。其中为强风的数据分布如下、共有6条数据其中决定为Y和N的分别是3条此时p(Y)3/6、p(N)3/6。Day天气温度湿度风决定2晴热高强N6雨凉正常强N7阴凉正常强Y11晴中正常强Y12阴中高强Y14雨中高强N代入公式其中为若风的数据分布如下、共有8条数据其中决定为Y有6条、N有2条此时p(Y)6/8、p(N)2/8。Day天气温度湿度风决定1晴热高弱N3阴热高弱Y4雨中高弱Y5雨凉正常弱Y8晴中高弱N9晴凉正常弱Y10雨中正常弱Y13阴热正常弱Y代入公式风这个特征的经验熵计算就完成了强风和弱风在整个数据集中的占比分别为p(强)6/14、p(弱)8/14代入公式则风这个特征的条件熵为风这个特征的信息增益为以此类推从中可以看出天气的新增增益为0.246、高于其他三个特征的增益这也是为什么天气作为第一个分类依据的特征、在树的根节点上。参照《机器学习实践》构建一颗决策树、python代码如下from math import logimport operatordef calcShannonEnt(dataSet): # 计算数据的熵(entropy) numEntries len(dataSet) # 数据条数 labelCounts {} for featVec in dataSet: currentLabel featVec[-1] # 每行数据的最后一个字(类别) if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] 0 labelCounts[currentLabel] 1 # 统计有多少个类以及每个类的数量 shannonEnt 0 for key in labelCounts: prob float(labelCounts[key]) / numEntries # 计算单个类的熵值 shannonEnt - prob * log(prob, 2) # 累加每个类的熵值 return shannonEntdef createDataSet1(): # 创造示例数据 dataSet [[黑, 是, 男], [白, 否, 男], [黑, 是, 男], [白, 否, 女], [黑, 是, 女], [黑, 否, 女], [白, 否, 女], [白, 否, 女]] labels [a, b] return dataSet, labels#待划分的数据集、划分数据集的特征、需要返回的特征值def splitDataSet(dataSet, axis,value): # 按某个特征分类后的数据例如value 长axis为头发axis 0 retDataSet [] # retDataSet返回的是数据中所有头发为长的记录 for featVec in dataSet: if featVec[axis] value: # 每次会将这个feature删除掉 reducedFeatVec featVec[:axis] reducedFeatVec.extend(featVec[axis 1:]) retDataSet.append(reducedFeatVec) return retDataSetdef chooseBestFeatureToSplit(dataSet): # 选择最优的分类特征 numFeatures len(dataSet[0]) - 1 baseEntropy calcShannonEnt(dataSet) # 原始的熵 bestInfoGain 0 bestFeature -1 # (1)遍历每个特征 for i in range(numFeatures): featList [example[i] for example in dataSet] uniqueVals set(featList) newEntropy 0 # (2)对单个特征中每个唯一值都进行子树的切分然后计算这个的信息增益然后累加每个分裂条件的信息增益为newEntropy for value in uniqueVals: subDataSet splitDataSet(dataSet, i, value) prob len(subDataSet) / float(len(dataSet)) newEntropy prob * calcShannonEnt(subDataSet) # 按特征分类后的熵 infoGain baseEntropy - newEntropy # 原始熵与按特征分类后的熵的差值 if (infoGain bestInfoGain): # 若按某特征划分后熵值减少的最大则次特征为最优分类特征 bestInfoGain infoGain bestFeature i return bestFeaturedef majorityCnt(classList): #按分类后类别数量排序比如最后分类为2男1女则判定为男 classCount {} for vote in classList: if vote not in classCount.keys(): classCount[vote] 0 classCount[vote] 1 sortedClassCount sorted(classCount.items(), keyoperator.itemgetter(1), reverseTrue) return sortedClassCount[0][0]# 决策树核心逻辑递归深度优先遍历创建子树def createTree(dataSet, labels): #print(dataSet) classList [example[-1] for example in dataSet] # 类别男或女 if classList.count(classList[0]) len(classList): return classList[0] if len(dataSet[0]) 1: # 当只剩最优一个feature时因为每次分裂会删除一个特征 return majorityCnt(classList) # (1) 选择最优分裂特征 bestFeat chooseBestFeatureToSplit(dataSet) #选择最优特征 bestFeatLabel labels[bestFeat] myTree {bestFeatLabel: {}} #分类结果以字典形式保存 del (labels[bestFeat]) featValues [example[bestFeat] for example in dataSet] uniqueVals set(featValues) # (2) 遍历分裂特征的每个唯一值分裂产生子树 for value in uniqueVals: # 将每个label都往子树传递labels一直可能会被选用 subLabels labels[:] # 对基于best feature这个feature内每个唯一值切分为不同的子树然后返回子树的结果。每个子树切分能多个分支 # 递归调用每层的切分为每个特征的唯一值 # (3) 对最佳分裂特征的每个值分别创建子树 myTree[bestFeatLabel][value] createTree( splitDataSet(dataSet, bestFeat, value), subLabels) return myTreeif __name__ __main__: dataSet, labels createDataSet1() # 创造示列数据 print(createTree(dataSet, labels)) # 输出决策树模型结果为了更直观展示决策树及各节点的信息熵用sklearn工具基于鸢尾花数据集展示一颗完整的决策树结构。from sklearn.datasets import load_irisfrom sklearn import treeimport osimport pydot # need installprint(os.getcwd())clf tree.DecisionTreeClassifier(criterionentropy, max_featureslog2,max_depth 10) #giniiris load_iris()clf clf.fit(iris.data, iris.target)tree.export_graphviz(clf, out_filetree.dot)(graph, ) pydot.graph_from_dot_file(tree.dot)graph.write_png(tree.png)对应的决策树结构如下ID3是基于信息增益作为分类依据的监督学习算法它有一个明显的缺点是该算法会倾向选择有较多属性值的特征作为分类依据鉴于ID3算法缺点后面又衍生出来C4.5和CART算法、具体后面再详细介绍和分享总结。
