正文对决策树算法举办简要的计算和梳理,并对著名的决定树算法ID3(Iterative
Dichotomiser
迭代二分器)举办落到实处,完结采纳Python语言,一句老梗,“人生苦短,小编用Python”,Python确实能够省比较多言语方面包车型地铁事,进而能够让我们注意于难题和缓慢解决难题的逻辑。

4.1 决策树(Decision Tree)的定义:

(一)认知决策树

遵照分化的多少,作者达成了三个本子的ID3算法,复杂度稳步提高:

是在已知各类地方时有产生概率的基础上,通过整合决策树来求取净现实价值的期望值超过等于零的概率,评价项目危机,决断其大方向的决策深入分析方法,是直观运用可能率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝条,故称决策树。在机器学习中,决策树是一位作品展望模型,他意味着的是指标属性与对象值时期的一种绚烂关系。Entropy

系统的杂乱无章程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一衡量是基于音信学理论中熵的概念。

4.2 划分选取的要义:

4.2.1
音信增益:
是特点采取中的二个最首要目的,它定义为三个表征能够为分类体系带来多少新闻,带来的音讯越来越多,该特征越主要。

图片 1

4.2.2熵:那么哪些权衡贰个特点为分类类别带来的消息有一点点吗:对叁天性子来讲,系统有它和没它时音信量将发生变化,而左右音讯量的差值正是其一特点给系统带来的音信量。所谓新闻量,其实正是熵。音讯熵可以衡量事物的不明确性,这一个东西不明明越大,消息熵也越大

【补充】今日头条上有三个对新闻熵的分解相比好https://www.zhihu.com/question/22178202/answer/49929786一个风浪的音信量正是其一事件发生的票房价值的负对数

【新闻增益熵之间关系】音信增益=熵-条件熵https://www.zhihu.com/question/22104055

【消息增益音讯增益率之间涉及】一些变种决策树的算法对细分的大旨略有分歧,如ID3施用音讯增益,c4.5运用音讯增益比,他们的时期的区分,如下:

https://www.zhihu.com/question/22928442

andy:离散数据运用新闻增益ID3与C4.5的界别并一点都不大。但固然面前碰到连连的数额(如体重、身体高度、年龄、距离等),或然每列数据尚未明显的项目之分(最极端的事例的该列全数数据都无比),在这种景色下,音信增益率缓慢解决了细分行为本人的震慑

4.2.3 基尼指数

Gini是从数据集随机抽多少个样本,不平等的可能率。假若Gini越小,则数据集纯度越高。

4.3 剪枝管理:化解 “过拟合”的要害招数

有关“过拟合”(数据集匹配的太好)和“欠拟合”(数据集相配的倒霉)之间的涉及:http://www.cnblogs.com/nxld/p/6058782.html

分成: 预剪枝和 后剪枝

4.3.1 预剪枝

释疑剪枝前,须要表明如何是泛化

泛化就是,机器学习模型学习到的概念在它地处学习的历程中时模型未有遇上过的范本时候的变现。

好的机器学习模型的模板目的是从难点领域内的教练多少到大肆的多少上泛化质量卓绝。那让大家得以在现在对模型未有见过的数据进行预测。

预剪枝:树还尚无演习成,可是用推断节点,要不要三翻五次划分。这样的操作会进步分类的准度,但是会推动欠拟合的高风险。

4.3.1 后剪枝

后剪枝,是树已经产生了,然后剪枝的政策和预剪枝大约,也是三个个去品尝,在夏瓜的事例中,正是剖断那一个节点是不是替换后,是或不是好瓜如故坏瓜。比较他们剪枝前和剪枝后的精度。从书上的图能够看到,后剪枝分支越来越多,欠拟合的高危机小。但陶冶时间大过多。

4.4 一而再与缺点和失误值

脚下取值的都以离散的。在三回九转的多寡上,要将“三翻五次数学离散化技术”-二分法对连日属性举办管理。

以下那一个诗歌对决策树的二分处精晓释相比好。

http://www.docin.com/p-490493786.html

焦点内容:

图片 2

4.4.1 接二连三值处理:青门绿玉房数据上加多了“密度”和“含糖率”。

【注意】在此以前的数量是离散,如:金棕、浑浊、卷曲、是、否等。但是密度和含糖率,都是接连的数码,如0.456、0.258等。

下一场依据二分法结合新闻增溢来计量新的树。

4.4.2 怎么样数据集有缺点和失误如何是好?

关心2个问题:

1.如何在属性值缺点和失误意况下进展品质选拔?(简来讲之 表头未有怎么做)

比如该节点是基于a属性划分,不过待分类样本a属性缺点和失误,如何是好吧?假诺a属性离散,有1,2二种取值,那么就把该样本分配到八个子节点中去,然而权重由1改为相应离散值个数占样本的比重。然后计算错误率的时候,注意,不是各类样本都以权重为1,存在分数。

2.给定划分的品质,若样本缺点和失误,怎样分割?(一句话来讲表头有了,表头里面包车型大巴数额未有如何是好)

假诺你利用ID3算法,那么选用分类属性时,将要计算有所属性的熵增(新闻增益,Gain)。尽管12个样本,属性是a,b,c。在总括a属性熵时意识,第13个样本的a属性缺点和失误,那么就把第拾个样本去掉,前9个样本组成新的样本集,在新样本集上按通常艺术总结a属性的熵增。然后结果乘0.9(新样本占raw样本的百分比),就是a属性最终的熵。

4.5 多变量决策树

比较于ID3、C4.5、CART这种单变量决策树(分支时只用二个性能),多变量决策树在分层时用的是八脾性格的加权组合,来个直观的图(以下),那么些是单变量决策树学习出来的划分边界,那几个边界都以与坐标轴平行的,多变量决策树的细分边界是倾斜于坐标轴的。

算法分支(实际情况参见

ID3

选料可以猎取最大音讯增益(information
gain)的特点为数量划分归类,直到全数细分结束而不对树的范畴拓宽任何决定。

等树生成之后,实践后剪枝。

音信增益的暧昧难点是,举个例子有四个数据集含有三个表征是日期只怕ID,则该特征会获得最大的消息增益,但是明显在证实数据中不会获得别的的结果。C45的音信增益比正是缓和这些题材的。

C45

选取能够取得最大音信增益率(information gain
ratio)的特点来划分数据,何况像ID3一律进行后剪枝。

是ID3的一连版本并扩充了IDC的功用,例如特征数值允许三番五次,在分拣的时候举办离散化。

新闻增益率:

“Gain ratio takes number and size of branches into account when choosing
an attribute, and corrects the information gain by taking the intrinsic
information of a split into account (i.e. how much info do we need to
tell which branch an instance belongs to).”

C50

那是风靡的一个本子,是有批准的(proprietary
license)。比之C45,减少了内部存款和储蓄器,使用更加少的准绳集,并且精确率越来越高。

CART

CART(Classification and Regression
Trees)分类回归树,它使用基尼不纯度(Gini Impurity)来决定分开。Gini
Impurity和information gain ratio的领会和界别在那边:

它和C45基本上是类似的算法,首要差距:1)它的叶节点不是实际的分类,而是是叁个函数f(),该函数定义了在该原则下的回归函数。2)CART是二叉树,并非多叉树。

总结表

图片 3

图片 4

xgboost

提起底以下作品对上述内容总括蛮好的 http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

1,决策树分类原理

决策树是通过一雨后冬笋法规对数据开展分拣的进程。它提供一种在怎么样标准下会得到什么样值的类似准绳的措施。决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树。

近些日子的检察注脚决策树也是最平日应用的多寡开采算法,它的定义特别简单。决策树算法之所以那样流行,三个很主要的由来正是使用者基本上不用精晓机器学习算法,也不用深究它是什么样行事的。直观望上去,决策树分类器就疑似判别模块和停止块组成的流程图,终止块象征分类结果(相当于树的卡牌)。剖断模块表示对二个特色取值的判别(该特征有多少个值,决断模块就有几个分支)。

若果不思虑功效等,那么样本全体特征的推断级联起来终会将某贰个样本分到三个类终止块上。实际上,样本全体特征中有局地特征在分拣时起到决定性效用,决策树的构造进度正是找到这一个富有决定性功用的特点,遵照其决定性程度来布局多个倒立的树–决定性功效最大的要命特征作为根节点,然后递归找到各支行下子数据汇总次大的决定性特征,直至子数据集中具有数据都属于同一类。所以,构造决策树的历程本质上就是基于数量特征将数据集分类的递归进度,大家要求缓慢解决的首先个难题正是,当前多少集上哪个特征在细分数据分类时起决定性效用。

为了找到决定性的特色、划分出最佳的结果,我们必须评估数据聚集满含的各样特征,找出分类数据集的最棒特征。实现评估之后,原始数据集就被剪切为多少个数据子集。这几个数据子集会布满在第二个决策点的富有支行上。假若某些分支下的数目属于同一档期的顺序,则则该支行管理完了,称为贰个卡片节点,即显明了分类。要是数据子集内的多少不属于同一类型,则供给重新划分数据子集的进度。怎样分割数据子集的算法和撤销合并原始数据集的格局同样,直到全部具有同样档案的次序的数目均在二个数据子集内(叶子节点)。如下图正是贰个决策树实例(目的是两类–见恐怕错过,每一种样本有年龄、长相、收入、是不是公务员多少个特点):

图片 5

图片 6

1.纯标称值无缺失数据集

2, 决策树的学习进度

一棵决策树的变化进度重要分为以下3个部分:

脾气采用:特征选取是指从磨炼多少中众多的本性中挑选二个表征作为当前节点的分化规范,怎么着挑选特征有着广大不等量化评估标准职业,进而衍生出分歧的仲裁树算法。

表决树生成
依据选用的性状评估规范,从上至下递归地生成子节点,直到数据集不可分则结束决策树截止生长。
树结构来讲,递归纳构是最轻易领会的点子。

剪枝:决策树轻松过拟合,一般来供给剪枝,裁减树结构规模、缓慢解决过拟合。剪枝本事有预剪枝和后剪枝三种。

2.三番五次值和标称值混合且无缺点和失误数据集

3,基于新闻论的二种核定树算法

分割数据集的最大原则是:使冬日的数据变的雷打不动。假诺二个陶冶多少中有十多个特色,那么选择哪个做划分依赖?那就亟须使用量化的办法来判别,量化划分方法有多种,当中一项正是“消息论度量音讯分类”。基于音信论的表决树算法有ID3、CART和C4.5等算法,当中C4.5和CART三种算法从ID3算法中衍生而来。

CART和C4.5协理数据特征为三翻五次布满时的拍卖,首要通过动用二元切分来处理一连型变量,即求二个一定的值-不相同值:特征值大于分歧值就走左子树,或然就走右子树。那些区别值的精选的原则是驱动划分后的子树中的“混乱程度”减少,具体到C4.5和CART算法规有分歧的概念格局。

ID3算法由Ross
Quinlan发明,建立在“奥卡姆剃刀”的底子上:越是Mini的决策树越优于大的决策树(be
simple简单理论)。ID3算法中根据音信论的新闻增益评估和甄选特征,每一遍采取新闻增益最大的特色做判定模块。ID3算法可用以私分标称型数据集,没有剪枝的历程,为了去除过度数据相配的题目,可经过裁剪合併相邻的一点计策也施展不出发生多量新闻增益的卡牌节点(举例设置音讯增益阀值)。使用音信增益的话实际是有多少个毛病,那正是它侧向于具备大批量值的属性–就是说在磨炼集中,有个别属性所取的分裂值的个数更加的多,那么越有望拿它来作为分化属性,而那样做不常候是没风趣的,别的ID3不能够管理接二连三布满的数目特征,于是就有了C4.5算法。CART算法也支撑一连分布的数码特征。

C4.5是ID3的三个革新算法,承继了ID3算法的长处。C4.5算法用消息增益率来选拔属性,克服了用消息增益接纳属性时偏侧选选择值多的本性的阙如在树构造进程中进行剪枝;可以完成对连日属性的离散化管理;能够对不完全部据开展拍卖。C4.5算法发生的分类法规便于精晓、正确率较高;但成效低,因树构造进度中,供给对数码集进行反复的相继扫描和排序。也是因为必得多次数量集扫描,C4.5只适合于能够驻留于内部存款和储蓄器的数量集。

CART算法的齐全部都以Classification And
Regression
Tree,行使的是Gini指数(选Gini指数最小的特征s)作为分歧标准,同临时间它也是包含后剪枝操作。ID3算法和C4.5算法纵然在对陶冶样本集的读书中得以尽恐怕多地开采新闻,但其转移的决策树分支十分大,规模十分的大。为了简化决策树的范畴,提升变换决策树的功用,就应际而生了基于GINI全面来挑选测验属性的决策树算法CART。

3.连连值和标称值混合,有缺点和失误数据集

4,决策树优缺点

决策树适用于数值型和标称型(离散型数据,变量的结果只在有限目的聚焦取值),能够读取数据集合,提取部分列数据中包蕴的平整。在分拣难点中应用决策树模型有为数相当的多的独到之处,决策树计算复杂度不高、便于使用、并且赶快,决策树可管理具有不相干特征的多少、可很轻松地协会出易于明白的条条框框,而平整平常易于解释和明白。决策树模型也可能有局部败笔,譬如拍卖缺点和失误数据时的紧Baba、过度拟合以及忽略数据聚集属性之间的相关性等。

第贰个算法参谋了《机器学习实战》的大多数代码,第二、多个算法基于后面的兑现举行模块的扩大。

(二)ID3算法的数学原理

前边早就涉及C4.5和CART都以由ID3演变而来,这里就先详细阐释ID3算法,奠下基础。

决策树简要介绍

决定树算法不用说大家应该都明白,是机械学习的叁个响当当算法,由澳大利伯维尔联邦(Commonwealth of Australia)闻名Computer地管理学家RoseQuinlan宣布。

决策树是一种监督学习的归类算法,目标是读书出一颗决策树,该树中间节点是数码特征,叶子节点是项目,实际分类时依照树的组织,一步一步依据近期数据特征取值采纳步向哪一颗子树,直到走到叶子节点,叶子节点的项目正是此决策树对此数量的学习结果。下图就是一颗轻易的决策树:

图片 7此决定树用来判定多少个有着纹理,触感,密度的夏瓜是还是不是是“好瓜”。

当有诸有此类贰个西瓜,纹理清晰,密度为0.333,触感硬滑,那么要你判别是或不是是一个“好瓜”,那时如若通过决策树来判别,显著能够一向本着纹理->清晰->密度<=0.382->否,即此瓜不是“好瓜”,一遍决定就这么成功了。正因为决策树决策很有益于,何况正确率也较高,所以时常被用来做分类器,也是“机器学习十大算法”之一C4.5的主导思想。

读书出一颗决策树首要思考八个标题,即 遵照数量集创设当前树应该选取哪一种属性作为树根,即划分标准? 

思索最棒的动静,一开头选用有个别特征,就把数量集划分成功,即在该特征上取某些值的全部是一类。

思索最坏的事态,不断选取特征,划分后的多寡集总是一无可取,就二分拣职责以来,总是有正类有负类,一向到特征全体用完了,划分的数量集合依旧有正有负,那时只可以用投票法,正类多就选正类作为叶子,不然选负类。

由此得出了一般结论:
随着划分的拓宽,大家期待采纳贰个特色,使得子节点蕴涵的范本尽或者属于同一种类,即“纯度”越高越好。

依靠“纯度”的正儿八经分裂,有三种算法:

1.ID3算法(Iterative
Dichotomiser
迭代二分器),也是本文要完成的算法,基于新闻增益即音讯熵来衡量纯度

2.C4.5算法(Classifier
4.5),ID3 的后继算法,也是昆兰提议

3.CART算法(Classification
And Regression Tree),基于基尼指数衡量纯度。

1,ID3算法的音讯论基础

至于决策树的新闻论基础能够参见“决定树1-建立模型进度”

(1)信息熵

消息熵:在可能率论中,新闻熵给了我们一种度量不分明的方法,是用来衡量随机变量不确定的,熵正是消息的期望值。若待分类的东西可能划分在N类中,分别是x1,x2,……,xn,每一样取到的可能率分别是P1,P2,……,Pn,那么X的熵就定义为:

图片 8,从概念中可见:0≤H(X)≤log(n)

当随机变量只取多少个值时,即X的布满为 P(X=1)=p,X(X=0)=1−p,0≤p≤1则熵为:H(X)=−plog2(p)−(1−p)log2(1−p)。

熵值越高,则数据混合的门类越高,其包含的含义是三个变量大概的改造越多(反而跟变量具体的取值未有别的关联,只和值的花色多少以及发生概率有关),它教导的消息量就越大。熵在音信论中是一个拾叁分主要的概念,比比较多机械学习的算法都会动用到那几个定义。

(2)条件熵

要是有随机变量(X,Y),其五只概率布满为:P(X=xi,Y=yi)=pij,i=1,2,⋯,n;j=1,2,⋯,m

条件熵(H(Y∣X))表示在已知随机变量X的规格下率性变量Y的不明确性,其定义为X在加以条件下Y的尺度概率布满的熵对X的数学期望:

    
图片 9
 

(3)消息增益

新闻增益(information
gain)表示得知特征X的新闻后,而使得Y的不明确性减弱的档案的次序。定义为:

     图片 10

ID3算法简要介绍

信息熵是音讯论中的三个入眼概念,也叫“香农熵”,香农先生的史事相比较相当多人都听过,一个人创办了一门理论,牛的那么些。香农理论中二个很要紧的特色正是”熵“,即”信息内容的不分明性“,香农在打开新闻的定量测算的时候,分明地把消息量定义为随机不定性程度的削减。那就标识了他对音讯的领悟:音信是用来裁减随便不定性的东西。也许宣布为香农逆定义:音讯是引人注指标加码。那也验证了决策树以熵作为划分选用的胸怀规范的不利,即大家想更急忙地从数据中收获越多消息,大家就应当异常的快回退不明确性,即减弱”熵“。

音讯熵定义为:

图片 11

D表示数据集,连串总的数量为|Y|,pk表示D中第k类样本所占的比重。依据其定义,Ent的值越小,消息纯度越高。Ent的界定是[0,log|Y|]

上边要接纳某些属性进行分割,要每个思量每一个属性,假使当前设想属性a,a的取值有|V|种,那么大家盼望取a作为划分属性,划分到|V|个子节点后,全部子节点的消息熵之和即划分后的音讯熵能够有极大的削减,减小的最多的非常属性正是大家选用的习性。

分割后的音讯熵定义为:

图片 12 

故而用属性a对样本集D实行私分的音讯增益正是原来的消息熵减去划分后的新闻熵:

图片 13

ID3算法便是如此每回选择几本性能对样本集实行剪切,知道三种处境使这么些进程甘休:

(1)某些子节点样本全部属于一类

(2)属性都用完了,那时候若是实节点样本依然不均等,那么只好少数服从比较多了

图片 14(图片源于互连网)

2,ID3算法推导

(1)分类种类消息熵

设若叁个分拣类别的样本空间(D,Y),D表示样本(有m个特征),Y表示n个类型,或者的取值是C1,C2,…,Cn。每三个品种出现的可能率是P(C1),P(C2),…,P(Cn)。该分类类别的熵为:

图片 15

图片 16

离散遍布中,系列Ci出现的可能率P(Ci),通过该项目出现的次数除去样本总的数量就能够取得。对于连日来分布,常必要分块做离散化管理获得。

(2)条件熵

依附法规熵的概念,分类种类中的条件熵指的是当样本的某一特征X固定期的消息熵。由于该特征X可能的取值会有(x1,x2,……,xn),当总计原则熵而急需把它稳定的时候,各种恐怕都要牢固一下,然后求计算期望。

故此样本特征X取值为xi的概率是Pi,该特征被定位为值xi时的标准信息熵正是H(C|X=xi),那么

H(C|X)正是分类种类中特征X被固定期的尺码熵(X=(x1,x2,……,xn)):

图片 17

比方样本的该特征唯有七个值(x1 =
0,x2=1)对应(出现,不出现),如文本分类中某贰个单词的面世与否。那么对于特征二值的气象,大家用T代表特征,用t代表T出现,图片 18表示该特征出现。那么:

图片 19

与前边条件熵的公式相比一下,P(t)正是T现身的概率,图片 20图片 21正是T不出现的可能率。结合新闻熵的计算公式,可得:

图片 22

图片 23     

 

特征T出现的可能率P(t),只要用出现过T的样本数除以总样本数就能够了;P(Ci|t)表示出现T的时候,体系Ci并发的可能率,只要用出现了T而且属于类型Ci的样本数除以出现了T的样本数就获得了。

(3)新闻增益

依赖音信增益的公式,分类种类中特征X的音信增益正是:Gain(D,
X) = H(C)-H(C|X)

新闻增益是对准三个一个的表征来讲的,正是看一个特征X,系统有它和没它的时候音信量各是稍稍,两个的差值就是其一天性给系统带来的音信增益。每趟接纳特征的进度都以经过测算各种特征值划分数据集后的新闻增益,然后选拔消息增益最高的风味。

对此特征取值为二值的情状,特征T给系统带来的音信增益就足以写成种类原来的熵与确定地点特征T后的标准熵之差:

图片 24

(4)经过上述一轮音信增益总结后会获得三个表征作为决策树的根节点,该特征有几个取值,根节点就能够有多少个支行,每三个拨出都会发出三个新的数据子集Dk,余下的递归进程便是对每一种Dk再另行上述进度,直至子数据集都属于同一类。

在决策树构造进程中恐怕会产出这种景色:全数特征都当做分裂特征用光了,但子集还不是纯净集(集结内的成分不属于同一类型)。在这种情况下,由于未有越来越多信息能够选用了,一般对那一个子集进行“好多裁决”,即采用此子聚集出现次数最多的连串作为此节点连串,然后将此节点作为叶子节点。

ID3算法达成(纯标称值)

若果样本全是标称值即离散值的话,会比较简单。

代码:

图片 25图片 26

from math import log
from operator import itemgetter
def createDataSet():            #创建数据集
    dataSet = [[1,1,'yes'],
               [1,1,'yes'],
               [1,0,'no'],
               [0,1,'no'],
               [0,1,'no']]
    featname = ['no surfacing', 'flippers']
    return dataSet,featname
def filetoDataSet(filename):
    fr = open(filename,'r')
    all_lines = fr.readlines()
    featname = all_lines[0].strip().split(',')[1:-1]
    print(featname)
    dataSet = []
    for line in all_lines[1:]:
        line = line.strip()
        lis = line.split(',')[1:]
        dataSet.append(lis)
    fr.close()
    return dataSet,featname
def calcEnt(dataSet):           #计算香农熵
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label] += 1
    Ent = 0.0
    for key in labelCounts.keys():
        p_i = float(labelCounts[key]/numEntries)
        Ent -= p_i * log(p_i,2)
    return Ent
def splitDataSet(dataSet, axis, value):   #划分数据集,找出第axis个属性为value的数据
    returnSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet
def chooseBestFeat(dataSet):
    numFeat = len(dataSet[0])-1
    Entropy = calcEnt(dataSet)
    DataSetlen = float(len(dataSet))
    bestGain = 0.0
    bestFeat = -1
    for i in range(numFeat):
        allvalue = [featVec[i] for featVec in dataSet]
        specvalue = set(allvalue)
        nowEntropy = 0.0
        for v in specvalue:
            Dv = splitDataSet(dataSet,i,v)
            p = len(Dv)/DataSetlen
            nowEntropy += p * calcEnt(Dv)
        if Entropy - nowEntropy > bestGain:
            bestGain = Entropy - nowEntropy
            bestFeat = i
    return bestFeat
def Vote(classList):
    classdic = {}
    for vote in classList:
        if vote not in classdic.keys():
            classdic[vote] = 0
        classdic[vote] += 1
    sortedclassDic = sorted(classdic.items(),key=itemgetter(1),reverse=True)
    return sortedclassDic[0][0]
def createDecisionTree(dataSet,featnames):
    featname = featnames[:]              ################
    classlist = [featvec[-1] for featvec in dataSet]  #此节点的分类情况
    if classlist.count(classlist[0]) == len(classlist):  #全部属于一类
        return classlist[0]
    if len(dataSet[0]) == 1:         #分完了,没有属性了
        return Vote(classlist)       #少数服从多数
    # 选择一个最优特征进行划分
    bestFeat = chooseBestFeat(dataSet)
    bestFeatname = featname[bestFeat]
    del(featname[bestFeat])     #防止下标不准
    DecisionTree = {bestFeatname:{}}
    # 创建分支,先找出所有属性值,即分支数
    allvalue = [vec[bestFeat] for vec in dataSet]
    specvalue = sorted(list(set(allvalue)))  #使有一定顺序
    for v in specvalue:
        copyfeatname = featname[:]
        DecisionTree[bestFeatname][v] = createDecisionTree(splitDataSet(dataSet,bestFeat,v),copyfeatname)
    return DecisionTree
if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\西瓜2.0.txt"
    DataSet,featname = filetoDataSet(filename)
    #print(DataSet)
    #print(featname)
    Tree = createDecisionTree(DataSet,featname)
    print(Tree)

View Code

解释一下多少个函数:

filetoDataSet(filename)
 将文件中的数据整理成数据集

calcEnt(dataSet)    
总计香农熵

splitDataSet(dataSet, axis, value)    
划分数据集,采用出第axis个属性的取值为value的具备数据集,即D^v,并去掉第axis个脾气,因为无需了

chooseBestFeat(dataSet)    
 依据音讯增益,选取二个最好的天性

Vote(classList)      
 假设属性用完,连串仍分歧样,投票决定

createDecisionTree(dataSet,featnames)    
递归创设决策树


用青门绿玉房数据集2.0对算法举办测量试验,西瓜数据集见 夏瓜数据集2.0,输出如下:

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

为了能够显示决策树的优越性即决定方便,这里依据matplotlib模块编写可视化函数treePlot,对转移的决策树进行可视化,可视化结果如下:

图片 27

 

出于数量太少,未有设置测量试验数据以评释其正确度,不过本人后边会依靠乳房纤维瘤的例子进行正确度的测量检验的,上面踏向下局地:

(三)C4.5算法

有三番五次值的情事

有一而再值的事态如 水瓜数据集3.0 

叁本性能有很三种取值,大家必定无法每一种取值都做八个分支,这时候供给对连续属性进行离散化,有两种艺术供采纳,当中二种是:

1.对每一项别的数据集的连天值取平均值,再取各个的平均值的平均值作为划分点,将一连属性化为两类成为离散属性

2.C4.5运用的二分法,排序离散属性,取每八个的当心作为划分点的候选点,计算以每一个划分点划分数据集的音讯增益,取最大的可怜划分点将三番五次属性化为两类成为离散属性,用该属性进行私分的音信增益正是刚刚总结的最大消息增益。公式如下:

图片 28

此间运用第三种,并在攻读前对延续属性实行离散化。扩张拍卖的代码如下:

def splitDataSet_for_dec(dataSet, axis, value, small):
    returnSet = []
    for featVec in dataSet:
        if (small and featVec[axis] <= value) or ((not small) and featVec[axis] > value):
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet
def DataSetPredo(filename,decreteindex):
    dataSet,featname = filetoDataSet(filename)
    Entropy = calcEnt(dataSet)
    DataSetlen = len(dataSet)
    for index in decreteindex:     #对每一个是连续值的属性下标
        for i in range(DataSetlen):
            dataSet[i][index] = float(dataSet[i][index])
        allvalue = [vec[index] for vec in dataSet]
        sortedallvalue = sorted(allvalue)
        T = []
        for i in range(len(allvalue)-1):        #划分点集合
            T.append(float(sortedallvalue[i]+sortedallvalue[i+1])/2.0)
        bestGain = 0.0
        bestpt = -1.0
        for pt in T:          #对每个划分点
            nowent = 0.0
            for small in range(2):   #化为正类负类
                Dt = splitDataSet_for_dec(dataSet, index, pt, small)
                p = len(Dt) / float(DataSetlen)
                nowent += p * calcEnt(Dt)
            if Entropy - nowent > bestGain:
                bestGain = Entropy-nowent
                bestpt = pt
        featname[index] = str(featname[index]+"<="+"%.3f"%bestpt)
        for i in range(DataSetlen):
            dataSet[i][index] = "是" if dataSet[i][index] <= bestpt else "否"
    return dataSet,featname

珍视是预管理函数DataSetPredo,对数据集提前离散化,然后再张开课习,学习代码类似。输出的决策树如下:

图片 29

1,新闻增益比选取最棒风味

以音信增益进行分类核定期,存在偏向于取值相当多的特点的标题。于是为了缓和那些难题大家有付出了依照消息增益比的分类核定办法,也便是C4.5。C4.5与ID3都以行使贪心算法举办求解,差异的是分类核定的依据不一样。

所以,C4.5算法在组织与递归上与ID3一模一样,差距就在于选用决断特征时选取新闻增益比最大的。

信息增益比率度量是用ID3算法中的的增益测量Gain(D,X)和瓦解新闻度量SplitInformation(D,X)来一起定义的。区别音讯衡量SplitInformation(D,X)就相当于特征X(取值为x1,x2,……,xn,各自的概率为P1,P2,…,Pn,Pk不畏样本空间中特征X取值为xk的数量除上该样本空间总的数量)的熵。

SplitInformation(D,X) = -P1
log2(P1)-P2
log2(P)-,…,-Pn
log2(Pn)

GainRatio(D,X) =
Gain(D,X)/SplitInformation(D,X)

在ID3中用音讯增益选拔属性时偏侧于选用分枝比较多的属性值,即取值多的性子,在C4.第55中学由于除以SplitInformation(D,X)=H(X),能够削弱这种成效。

有缺点和失误值的事态

数码有缺点和失误值是常见的情景,大家欠好间接丢掉那一个多少,因为如此会损失大量数据,不划算,然则缺点和失误值我们也无从剖断它的取值。怎么办吧,办法依旧有的。

虚构四个难题: 

1.有缺点和失误值时怎么进展剪切选取

2.已选取划分属性,有缺点和失误值的样本划不分开,怎么样分割?

问题1:有缺点和失误值时怎么进展分割选用**

着力思维是开展最优待军属和烈属性选用时,先只怀念无缺点和失误值样本,然后再乘以相应比例,获得在一切样本集上的大约情形。连带思索到第贰个难题的话,怀念给每二个样本三个权重,此时各个样本不再总是被看做二个单身样本,那样方便第叁个问题的消除:即若样本在属性a上的值缺点和失误,那么将其当做是全数值都取,只可是取每种值的权重不雷同,每一个值的权重仿效该值在无缺点和失误值样本中的比例,轻便地说,比如在无缺点和失误值样本集中,属性a取去五个值1和2,而且取1的权重和占总体权重和百分之二十五,而取2的权重和占2/3,那么依照该属性对样本集实行私分时,碰到该属性上有缺点和失误值的样书,那么大家以为该样本取值2的大概更加大,于是将该样本的权重乘以2/3归到取值为2的样书集中继续开展分割构造决策树,而乘51%划到取值为1的样本聚焦继续协会。不知底自家说掌握未有。

公式如下:

图片 30

其中,D~表示数据集D在属性a上无缺点和失误值的范本,依照它来判别a属性的三六九等,rho(即‘lou’)表示属性a的无缺点和失误值样本占全部样本的比重,p~_k表示无缺点和失误值样本中第k类所占的比例,r~_v表示无缺点和失误值样本在属性a上取值为v的样书所占的比重。

在划分样本时,假设有缺点和失误值,则将样本划分到全部子节点,在属性a取值v的子节点上的权重为r~_v
* 原本的权重。

更详细的解读参谋《机器学习》P86-87。

基于权重法修改后的ID3算法完成如下:

图片 31图片 32

from math import log
from operator import itemgetter

def filetoDataSet(filename):
    fr = open(filename,'r')
    all_lines = fr.readlines()
    featname = all_lines[0].strip().split(',')[1:-1]
    dataSet = []
    for line in all_lines[1:]:
        line = line.strip()
        lis = line.split(',')[1:]
        if lis[-1] == '2':
            lis[-1] = '良'
        else:
            lis[-1] = '恶'
        dataSet.append(lis)
    fr.close()
    return dataSet,featname

def calcEnt(dataSet, weight):           #计算权重香农熵
    labelCounts = {}
    i = 0
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label] += weight[i]
        i += 1
    Ent = 0.0
    for key in labelCounts.keys():
        p_i = float(labelCounts[key]/sum(weight))
        Ent -= p_i * log(p_i,2)
    return Ent

def splitDataSet(dataSet, weight, axis, value, countmissvalue):   #划分数据集,找出第axis个属性为value的数据
    returnSet = []
    returnweight = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?' and (not countmissvalue):
            continue
        if countmissvalue and featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        if featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i])
        i += 1
    return returnSet,returnweight

def splitDataSet_for_dec(dataSet, axis, value, small, countmissvalue):
    returnSet = []
    for featVec in dataSet:
        if featVec[axis] == '?' and (not countmissvalue):
            continue
        if countmissvalue and featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        if (small and featVec[axis] <= value) or ((not small) and featVec[axis] > value):
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
    return returnSet

def DataSetPredo(filename,decreteindex):     #首先运行,权重不变为1
    dataSet,featname = filetoDataSet(filename)
    DataSetlen = len(dataSet)
    Entropy = calcEnt(dataSet,[1 for i in range(DataSetlen)])
    for index in decreteindex:     #对每一个是连续值的属性下标
        UnmissDatalen = 0
        for i in range(DataSetlen):      #字符串转浮点数
            if dataSet[i][index] != '?':
                UnmissDatalen += 1
                dataSet[i][index] = int(dataSet[i][index])
        allvalue = [vec[index] for vec in dataSet if vec[index] != '?']
        sortedallvalue = sorted(allvalue)
        T = []
        for i in range(len(allvalue)-1):        #划分点集合
            T.append(int(sortedallvalue[i]+sortedallvalue[i+1])/2.0)
        bestGain = 0.0
        bestpt = -1.0
        for pt in T:          #对每个划分点
            nowent = 0.0
            for small in range(2):   #化为正类(1)负类(0)
                Dt = splitDataSet_for_dec(dataSet, index, pt, small, False)
                p = len(Dt) / float(UnmissDatalen)
                nowent += p * calcEnt(Dt,[1.0 for i in range(len(Dt))])
            if Entropy - nowent > bestGain:
                bestGain = Entropy-nowent
                bestpt = pt
        featname[index] = str(featname[index]+"<="+"%d"%bestpt)
        for i in range(DataSetlen):
            if dataSet[i][index] != '?':
                dataSet[i][index] = "是" if dataSet[i][index] <= bestpt else "否"
    return dataSet,featname

def getUnmissDataSet(dataSet, weight, axis):
    returnSet = []
    returnweight = []
    tag = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?':
            tag.append(i)
        else:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
        i += 1
    for i in range(len(weight)):
        if i not in tag:
            returnweight.append(weight[i])
    return returnSet,returnweight

def printlis(lis):
    for li in lis:
        print(li)

def chooseBestFeat(dataSet,weight,featname):
    numFeat = len(dataSet[0])-1
    DataSetWeight = sum(weight)
    bestGain = 0.0
    bestFeat = -1
    for i in range(numFeat):
        UnmissDataSet,Unmissweight = getUnmissDataSet(dataSet, weight, i)   #无缺失值数据集及其权重
        Entropy = calcEnt(UnmissDataSet,Unmissweight)      #Ent(D~)
        allvalue = [featVec[i] for featVec in dataSet if featVec[i] != '?']
        UnmissSumWeight = sum(Unmissweight)
        lou = UnmissSumWeight / DataSetWeight        #lou
        specvalue = set(allvalue)
        nowEntropy = 0.0
        for v in specvalue:      #该属性的几种取值
            Dv,weightVec_v = splitDataSet(dataSet,Unmissweight,i,v,False)   #返回 此属性为v的所有样本 以及 每个样本的权重
            p = sum(weightVec_v) / UnmissSumWeight          #r~_v = D~_v / D~
            nowEntropy += p * calcEnt(Dv,weightVec_v)
        if lou*(Entropy - nowEntropy) > bestGain:
            bestGain = Entropy - nowEntropy
            bestFeat = i
    return bestFeat

def Vote(classList,weight):
    classdic = {}
    i = 0
    for vote in classList:
        if vote not in classdic.keys():
            classdic[vote] = 0
        classdic[vote] += weight[i]
        i += 1
    sortedclassDic = sorted(classdic.items(),key=itemgetter(1),reverse=True)
    return sortedclassDic[0][0]

def splitDataSet_adjustWeight(dataSet,weight,axis,value,r_v):
    returnSet = []
    returnweight = []
    i = 0
    for featVec in dataSet:
        if featVec[axis] == '?':
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i] * r_v)
        elif featVec[axis] == value:
            retVec = featVec[:axis]
            retVec.extend(featVec[axis+1:])
            returnSet.append(retVec)
            returnweight.append(weight[i])
        i += 1
    return returnSet,returnweight

def createDecisionTree(dataSet,weight,featnames):
    featname = featnames[:]              ################
    classlist = [featvec[-1] for featvec in dataSet]  #此节点的分类情况
    if classlist.count(classlist[0]) == len(classlist):  #全部属于一类
        return classlist[0]
    if len(dataSet[0]) == 1:         #分完了,没有属性了
        return Vote(classlist,weight)       #少数服从多数
    # 选择一个最优特征进行划分
    bestFeat = chooseBestFeat(dataSet,weight,featname)
    bestFeatname = featname[bestFeat]
    del(featname[bestFeat])     #防止下标不准
    DecisionTree = {bestFeatname:{}}
    # 创建分支,先找出所有属性值,即分支数
    allvalue = [vec[bestFeat] for vec in dataSet if vec[bestFeat] != '?']
    specvalue = sorted(list(set(allvalue)))  #使有一定顺序
    UnmissDataSet,Unmissweight = getUnmissDataSet(dataSet, weight, bestFeat)   #无缺失值数据集及其权重
    UnmissSumWeight = sum(Unmissweight)      # D~
    for v in specvalue:
        copyfeatname = featname[:]
        Dv,weightVec_v = splitDataSet(dataSet,Unmissweight,bestFeat,v,False)   #返回 此属性为v的所有样本 以及 每个样本的权重
        r_v = sum(weightVec_v) / UnmissSumWeight          #r~_v = D~_v / D~
        sondataSet,sonweight = splitDataSet_adjustWeight(dataSet,weight,bestFeat,v,r_v)
        DecisionTree[bestFeatname][v] = createDecisionTree(sondataSet,sonweight,copyfeatname)
    return DecisionTree

if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\breastcancer.txt"
    DataSet,featname = DataSetPredo(filename,[0,1,2,3,4,5,6,7,8])
    Tree = createDecisionTree(DataSet,[1.0 for i in range(len(DataSet))],featname)
    print(Tree)

View Code

有缺点和失误值的意况如 水瓜数据集2.0阿尔法

试验结果:

图片 33

2,管理三番五次数值型特征

C4.5不只能够处理离散型属性,也得以管理三番两次性属性。在挑选某节点上的分枝属性时,对于离散型描述属性,C4.5的管理办法与ID3平等。对于一而再布满的性状,其拍卖格局是:

先把三翻五次属性转变为离散属性再进行拍卖。尽管本质上品质的取值是三番四回的,但对此有数的采集样品数据它是离散的,假如有N条样本,那么大家有N-1种离散化的章程:<=vj的分到左子树,>vj的分到右子树。总计那N-1种景况下最大的音信增益率。别的,对于连日来属性先进行排序(升序),独有在决定属性(即分类爆发了转变)产生改换的地方才要求切开,那能够明显减少运算量。经求证,在调整连续特征的分界点时接纳增益那个指标(因为若使用增益率,splittedinfo影响差别点音讯衡量正确性,若某分界点恰好将连接特征分成数目相等的两部分时其幸免功能最大),而接纳属性的时候才使用增益率这些目的能选取出最好分类特征。

在C4.5中,对连日属性的拍卖如下:

1.      对特色的取值举办升序排序

2.      七个特点取值之间的大旨作为恐怕的不同点,将数据集分成两有的,计算每一个大概的分裂点的音讯增益(InforGain)。优化算法便是只总计分类属性产生更换的这几个特征取值。

3.      选用校订后消息增益(InforGain)最大的不同点作为该特征的极品分歧点

4.      总结最好差距点的新闻增益率(Gain
Ratio)作为特色的Gain
Ratio。注意,此处需对顶尖区别点的消息增益进行考订:减去log2(N-1)/|D|(N是三番五次特征的取值个数,D是教练多少数目,此核查的缘由在于:当离散属性和连接属性并存时,C4.5算法偏侧于选用总是特征做最棒树分化点)

兑现再三再四特征数据集划分的Python程序为:

Source Code:▼Copy

  1. def binSplitDataSet(dataSet, feature, value):
      
  2.     mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]
      
  3.     mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]
      
  4.     return mat0,mat1  

其间dataset为numpy matrix,
feature为dataset连续特征在dataset全部特征中的index,value即为feature周围两值的均值。

在乳房棘球蚴病数据集上的测量检验与表现

有了算法,大家自然想做断定的测量检验看一看算法的变现。这里小编选取了威斯康辛女人奶腺癌的多寡。

数量总共有9列,每一列分别表示,以逗号分割

1 Sample
code number (病人ID)
2 Clump
Thickness 肿块厚度
3
Uniformity of Cell Size 细胞大小的均匀性
4
Uniformity of Cell Shape 细胞形状的均匀性
5
Marginal Adhesion 边缘粘
6 Single
Epithelial Cell Size 单上皮细胞的轻重缓急
7 Bare
Nuclei 裸核
8 Bland
Chromatin 乏味染色体
9 Normal
Nucleoli 正常核
10
Mitoses 有丝分歧
11 Class:
2 for benign, 4 formalignant(恶性或良性分类)

[from
Toby]

合计700条左右的数量,选择末了80条作为测验集,前边作为训练集,实行学习。

运用分类器的代码如下:

import treesID3 as id3
import treePlot as tpl
import pickle

def classify(Tree, featnames, X):
    classLabel = "未知"
    root = list(Tree.keys())[0]
    firstGen = Tree[root]
    featindex = featnames.index(root)  #根节点的属性下标
    for key in firstGen.keys():   #根属性的取值,取哪个就走往哪颗子树
        if X[featindex] == key:
            if type(firstGen[key]) == type({}):
                classLabel = classify(firstGen[key],featnames,X)
            else:
                classLabel = firstGen[key]
    return classLabel

def StoreTree(Tree,filename):
    fw = open(filename,'wb')
    pickle.dump(Tree,fw)
    fw.close()

def ReadTree(filename):
    fr = open(filename,'rb')
    return pickle.load(fr)

if __name__ == '__main__':
    filename = "D:\\MLinAction\\Data\\breastcancer.txt"
    dataSet,featnames = id3.DataSetPredo(filename,[0,1,2,3,4,5,6,7,8])
    Tree = id3.createDecisionTree(dataSet[:620],[1.0 for i in range(len(dataSet))],featnames)
    tpl.createPlot(Tree)
    storetree = "D:\\MLinAction\\Data\\decTree.dect"
    StoreTree(Tree,storetree)
    #Tree = ReadTree(storetree)
    i = 1
    cnt = 0
    for lis in dataSet[620:]:
        judge = classify(Tree,featnames,lis[:-1])
        shouldbe = lis[-1]
        if judge == shouldbe:
            cnt += 1
        print("Test %d was classified %s, it's class is %s %s" %(i,judge,shouldbe,"=====" if judge==shouldbe else ""))
        i += 1
    print("The Tree's Accuracy is %.3f" % (cnt / float(i)))

磨练出的决策树如下:

图片 34

最后的准确率能够见到:

图片 35

准确率约为96%左右,算是不差的分类器了。

小编的宫颈糜烂数据见:

从这之后,决策树算法ID3的兑现得了,上边思虑基于基尼指数和音讯增益率举办私分采用,以及思量完成剪枝进程,因为我们得以看到上面训练出的决策树还设有着众多冗余分支,是因为完结进程中,由于数据量太大,每一种分支都不完全纯净,所以会创立往下的分支,可是分支投票的结果又是同样的,况且数据量再大,特征数再多的话,决策树会相当的大极度复杂,所以剪枝一般是必做的一步。剪枝分为先剪枝和后剪枝,借使细说的话能够写非常多了。

此文亦可知:这里
参谋资料:《机器学习》《机器学习实战》通过本次实战也开采了这两本书中的一些不当之处。

lz初学机器学习不久,如有错漏之处请多满含提出依旧各位有啥样主张或意见应接批评去报告小编:)

3,叶子裁剪

深入分析归类回归树的递归建树过程,简单窥见它实质上存在着贰个数量过度拟合难点。在决策树构造时,由于磨炼多少中的噪音或孤立点,好多分枝反映的是练习多少中的分外,使用那样的判断树对品种未知的多寡开展分拣,分类的正确性不高。因而试图检验和削减那样的道岔,检测和削减这一个分支的经过被称之为树剪枝。树剪枝方法用于拍卖过于适应数据难题。常常,这种格局应用计算度量,减去最不可相信的分支,那将造成非常的慢的归类,升高树独立于磨练多少精确分类的力量。

决策树常用的剪枝常用的差十分少方法有二种:预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。预剪枝是依附局地尺码及早的休息树增加,如树的深度到达客商所要的吃水、节点中样本个数少于顾客内定个数、不纯度指标下跌的最大幅度面低于客户内定的增长幅度等。预剪枝的主干难点是何等先行钦点树的最大深度,假使设置的最大深度不适合,那么将会促成过度限制树的生长,使决策树的表明式法规趋于一般,不能够更加好地对新数据集举办分拣和预测。除了事先限定决策树的最大深度之外,还恐怕有其他三个方法来贯彻预剪枝操作,那正是运用核准工夫对眼下结点对应的范本集合举行检查,假设该样本集合的样本数量已低于事先钦命的蝇头允许值,那么为止该结点的承继生长,并将该结点变为叶子结点,不然能够三番七次扩充该结点。

后剪枝则是通过在完全生长的树上剪去分枝完成的,通过删除节点的道岔来剪去树节点,能够利用的后剪枝方法有二种,比方:代价复杂性剪枝、最小引用误差剪枝、悲观相对误差剪枝等等。后剪枝操作是二个边修剪边防检核准的进度,一般法规规范是:在决策树的无休止剪枝操作进度中,将原样本集合或新数据集协作为测量检验数据,核算决策树对测量试验数据的预测精度,并总括出相应的错误率,借使剪掉某些子树后的决策树对测验数据的展望精度或别的推断不下滑,那么剪掉该子树。

有关后剪枝的切切实实理论能够参谋“数量发现十大卓越算法–CART:
分类与回归树”剪枝部分。

(三)Python达成ID3、C4.5算法决策树

Python中无需组织新的数据类型来囤积决策树,使用字典dict就可以方便的仓库储存节点新闻,永恒存款和储蓄则足以经过pickle也许JSON将决策树字典写入文件中,本包选取JSON。包中trees模块定义了一个decisionTree对象,同不平时间扶助ID3和C4.5二种算法(C4.5算法三番两次特征的拍卖和后剪枝未有兑现),该指标中的属性如函数__init__中所示:

Source
Code:▼Copy

  1. class decisionTree(object):   
  2.     def __init__(self,dsDict_ID3 = None,dsDict_C45 = None, features = None, **args):
      
  3.         ”’currently support ID3 and C4.5, the default type is C4.5, CART TBD 
  4.            
     
  5.         ”’  
  6.         obj_list = inspect.stack()[1][-2]   
  7.         self.__name__ = obj_list[0].split(‘=’)[0].strip()
      
  8.         self.dsDict_ID3 = dsDict_ID3   
  9.         self.dsDict_C45 = dsDict_C45   
  10.         #self.classLabel = classLabel  
  11.         self.features = features  

decisionTree对象的train函数的输入数据为模本列表和样本特征列表,个中样本列表各类成分的最后一项表示该因素的归类,格式如下所示:

  1. dataSet = [[1,1,’yes’],   
  2.                [1,1,’yes’],   
  3.                [1,0,’no’],   
  4.                [0,1,’no’],   
  5.                [0,1,’no’]   
  6.               ]   
  7. labels = [‘no surfacing’, ‘flippers’]  

除此以外,通过Python的Matplotlib的注明功用则足以绘制树形图,方便彰显。decisionTree对象提供了treePlot方法,通过模块treePlotter中的函数实现。

testDS模块则应用决策树决定伤者是或不是能够佩戴隐形老花镜,须要惦记的个性因素归纳四个–‘age’,
‘prescript’, ‘astigmatic’,
‘tearRate’。下图正是运用decisionTree对象生成的决策树。

仲裁树算工学习包下载地址:

Machine learning DecisionTree

(四)决策树应用

决策树技艺在数据化运行中的首要用途展现在:作为分类、预测难题的卓绝辅助手艺,它在客户划分、行为预测、准则梳理等地点抱有大范围的使用前景。

参考

C4.5管理一而再属性

C4.5决策树

从决策树学习聊起贝叶斯分类算法、EM、HMM

决策树2-ID3,C4.5,CART

正文作者Adan,来源于:机械学习优异算法详解及Python实现–决策树(Decision
Tree)。转发请阐明出处。

相关文章