正文对决策树算法实行简要的总括和梳理，并对名牌的核定树算法ID三(Iterative
Dichotomiser
迭代二分器)进行落到实处，实现利用Python语言，一句老梗，“人生苦短，笔者用Python”，Python确实能够省很多言语方面包车型客车事，从而可以让大家注意于难题和消除难点的逻辑。
4.1 决策树(Decision Tree）的定义：
依照差异的多少，小编完结了三个版本的ID三算法，复杂度稳步升级：
是在已知各样状态时有产生可能率的基础上，通过结合决策树来求取净现值的期望值超出等于零的票房价值，评价项目危机，判断其可行性的决策分析方法，是直观运用可能率分析的1种图解法。由于那种决策分支画成图形很像一棵树的枝条，故称决策树。在机器学习中，决策树是一个预测模型，他表示的是指标属性与对象值时期的一种炫耀关系。Entropy
系统的紊乱程度，使用算法ID3,C4.5和C五.0生成树算法使用熵。这1衡量是基于音讯学理论中熵的定义。
四.二 划分选用的要义：
四.贰.一消息增益：是特色选用中的二个首要指标，它定义为三特本性能够为分类连串带来多少消息，带来的新闻越来越多，该特征越主要。
4.2.2熵：那么如何度量二个特色为分类连串带来的音信有点吧：对二个风味而言，系统有它和没它时音信量将发生变化，而上下新闻量的差值就是那个特点给系统带来的新闻量。所谓消息量，其实便是熵。新闻熵可以衡量事物的不分明性，那个东西不肯定越大，消息熵也越大。
【补充】和讯上有一个对新闻熵的解说相比好https://www.zhihu.com/question/22178202/answer/49929786三个事件的消息量便是那几个事件发生的概率的负对数。
【音信增益熵之间关系】新闻增益=熵-条件熵https://www.zhihu.com/question/22104055
【音讯增益新闻增益率之间涉及】①些变种决策树的算法对私分的大旨略有不相同，如ID三施用音信增益，c四.五运用音信增益比，他们的时期的区分，如下：
https://www.zhihu.com/question/22928442
andy：离散数据利用新闻增益ID叁与C4.五的分别并十分小。但1旦面对连连的多寡（如体重、身高、年龄、距离等），或许每列数据尚未显明的品类之分（最极端的事例的该列全体数据都无比），在那种情况下，新闻增益率减轻了细分行为本人的影响
4.贰.三 基尼指数
Gini是从数据集随机抽多少个样本，不等同的票房价值。假设Gini越小，则数据集纯度越高。
4.三 剪枝处理：化解 “过拟合”的显要手段
有关“过拟合”（数据集匹配的太好）和“欠拟合”（数据集匹配的不得了）之间的涉嫌：http://www.cnblogs.com/nxld/p/6058782.html
分为： 预剪枝和 后剪枝
4.3.1 预剪枝
表明剪枝前，需求表明什么是泛化
泛化便是，机器学习模型学习到的概念在它地处学习的长河中时模型未有遭逢过的样书时候的显现。
好的机械学习模型的沙盘指标是从难题领域内的教练多少到自由的数额上泛化品质卓越。那让大家能够在今后对模型未有见过的多寡开始展览展望。
预剪枝：树还向来不磨炼成，不过用判断节点，要不要持续划分。那样的操作会进步分类的准度，不过会推动欠拟合的风险。
4.3.1 后剪枝
后剪枝，是树已经形成了，然后剪枝的策略和预剪枝大约，也是三个个去品味，在西瓜的例子中，就是判断那么些节点是或不是替换后，是还是不是好瓜依旧坏瓜。比较他们剪枝前和剪枝后的精度。从书上的图可以看出，后剪枝分支越多，欠拟合的风险小。但磨炼时间大过多。
四.4 接二连三与缺点和失误值
近期取值的都是离散的。在一而再的多少上，要将“连续数学离散化技术”-二分法对连年属性举办拍卖。
以下那些散文对决策树的二分处精晓释比较好。
http://www.docin.com/p-490493786.html
主题内容：
四.四.一 一而再值处理：西瓜数据上添加了“密度”和“含糖率”。
【注意】在此以前的多少是离散，如：羊毛白、浑浊、卷曲、是、否等。然而密度和含糖率，都以连接的数据，如0.45陆、0.258等。
然后依照二分法结合新闻增溢来总计新的树。
4.四.二 如何数据集有缺点和失误怎么做？
关心2个问题：
壹.怎么在属性值缺点和失误情况下实行质量采纳？（简单的讲 表头未有如何是好）
例如该节点是依照a属性划分，可是待分类样本a属性缺点和失误，如何是好呢？假若a属性离散，有1,二三种取值，那么就把该样本分配到多少个子节点中去，不过权重由一改为相应离散值个数占样本的比重。然后总计错误率的时候，注意，不是每一种样本都是权重为一，存在分数。
贰.给定划分的性质，若样本缺点和失误，怎么样分割？（简而言之表头有了，表头里面包车型地铁数目尚未咋办）
万一你使用ID3算法，那么选拔分类属性时，就要总括有所属性的熵增(音信增益，Gain)。假如11个样本，属性是a,b,c。在总计a属性熵时意识，第七个样本的a属性缺点和失误，那么就把第10个样本去掉，前柒个样本组成新的样本集，在新样本集上按常规格局总结a属性的熵增。然后结果乘0.玖（新样本占raw样本的百分比），便是a属性最后的熵。
四.5 多变量决策树
对照于ID三、C四.五、CACR-VT那种单变量决策树（分支时只用一本性情），多变量决策树在分层时用的是陆特性子的加权组合，来个直观的图（以下），这些是单变量决策树学习出来的撤销合并边界，那一个边界都以与坐标轴平行的，多变量决策树的划分边界是倾斜于坐标轴的。
算法分支（详情参见http://scikit-learn.org/stable/modules/tree.html）
ID3
选拔能够得到最大新闻增益（information
gain）的特色为数量划分归类，直到一切瓜分甘休而不对树的局面实行任何决定。
等树生成之后，执行后剪枝。
音讯增益的地下难题是，比如有多个数目集含有1个特点是日期可能ID，则该特征会赢得最大的音讯增益，可是明显在印证数据中不会获取别的的结果。C四伍的新闻增益比正是缓解那么些问题的。
C45
慎选能够获得最大音信增益率（information gain
ratio）的本性来划分数据，并且像ID三一致举办后剪枝。
是ID三的一而再版本并扩展了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）。比之C四伍，减弱了内部存款和储蓄器，使用更加少的规则集，并且准确率越来越高。
CART
CAKugaT（Classification and Regression
Trees）分类回归树，它选取基尼不纯度（Gini Impurity）来控制分开。Gini
Impurity和information gain ratio的知道和区分在那里：
它和C45基本上是左近的算法，首要差别：一）它的叶节点不是切实的归类，而是是3个函数f()，该函数定义了在该规范下的回归函数。二）CA奥迪Q伍T是2叉树，而不是多叉树。
总结表
xgboost
最终以下文章对上述内容总括挺好的 http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html
1.纯标称值无缺点和失误数据集
二.老是值和标称值混合且无缺点和失误数据集
三.连接值和标称值混合，有缺点和失误数据集
先是个算法参考了《机器学习实战》的多数代码，第二、多个算法基于前边的兑现实行模块的加码。
决策树简介
核定树算法不用说大家应该都知情，是机械学习的三个盛名算法，由澳大伊Lisa白港（Australia）知名计算机化学家RoseQuinlan发布。
决策树是一种监督学习的归类算法，目标是上学出1颗决策树，该树中间节点是数额特征，叶子节点是项目，实际分类时依据树的组织，一步一步依照当下数据特征取值选取进入哪一颗子树，直到走到叶子节点，叶子节点的系列就是此决策树对此数据的上学结果。下图正是1颗不难的决策树：
此决定树用来判定一个独具纹理，触感，密度的西瓜是或不是是“好瓜”。
当有那样多个西瓜，纹理清晰，密度为0.333，触感硬滑，那么要你判定是还是不是是3个“好瓜”，那时借使因此决策树来判断，鲜明可以直接本着纹理->清晰->密度<=0.3八2->否，即此瓜不是“好瓜”，三次决定就那样形成了。正因为决策树决策很便宜，并且准确率也较高，所以平时被用来做分类器，也是“机器学习10大算法”之1C四.伍的基本思维。
读书出一颗决策树主要考虑3个题材，即 依据数量集营造当前树应该采取哪一类属性作为树根，即划分标准？
设想最佳的情形，1开端选取有个别特征，就把多少集划分成功，即在该特征上取有些值的全是壹类。
设想最坏的情景，不断选用特征，划分后的数码集总是非常倒霉，就二分类职务的话，总是有正类有负类，一直到特征全体用完了，划分的多寡集合依旧有正有负，那时只能用投票法，正类多就选正类作为叶子，不然选负类。
于是得出了貌似结论：
随着划分的进行，我们期望选用三本性格，使得子节点包括的样本尽可能属于同壹品种，即“纯度”越高越好。
根据“纯度”的规范各异，有三种算法：
壹.ID三算法(Iterative
Dichotomiser
迭代二分器)，也是本文要兑现的算法，基于消息增益即音讯熵来衡量纯度
二.C4.5算法(Classifier
四.5)，ID三 的后继算法，也是昆兰提议
3.CA卡宴T算法(Classification
And Regression Tree)，基于基尼指数衡量纯度。
ID3算法简介
音信熵是音信论中的三个重点概念，也叫“香农熵”，香农先生的史事相比较很两人都听过，1人成立了1门理论，牛的那些。香农理论中二个很重点的特色便是”熵“，即”音信内容的不明确性“，香农在拓展音讯的定量测算的时候，明显地把音讯量定义为私自不定性程度的缩减。那就表明了她对音信的敞亮：新闻是用来压缩自由不定性的事物。也许发布为香农逆定义：音信是举世著名的充实。那也印证了决策树以熵作为划分选用的胸襟标准的不易，即咱们想更加高速地从数额中拿走越来越多新闻，我们就应有非常快降低不分明性，即缩减”熵“。
音信熵定义为：
D表示数据集，种类总数为|Y|，pk表示D中第k类样本所占的比例。遵照其定义，Ent的值越小，消息纯度越高。Ent的限量是[0,log|Y|]
下边要选择有个别属性实行分割，要每一个思量每种属性，假若当前设想属性a，a的取值有|V|种，那么我们意在取a作为划分属性，划分到|V|个子节点后，全体子节点的新闻熵之和即划分后的新闻熵能够有相当大的压缩，减小的最多的10分属性正是我们选用的质量。
分开后的新闻熵定义为：
于是用属性a对样本集D举行划分的信息增益正是本来的新闻熵减去划分后的消息熵：
ID3算法正是那样每便选拔多个性格对样本集进行分割，知道二种状态使那个进度结束：
（一）某些子节点样本全体属于一类
（二）属性都用完了，那时候假若实节点样本依然差别，那么只好少数遵从多数了
（图片来自互联网）
ID三算法达成(纯标称值)
比方样本全体是标称值即离散值的话，会相比简单。
代码：
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个属性，因为不供给了
choose贝斯特Feat(dataSet)
依照音讯增益，选拔八个最佳的质量
Vote(classList)
即便属性用完，连串仍不一样，投票决定
createDecisionTree(dataSet,featnames)
递归创建决策树
用西瓜数据集贰.0对算法进行测试，西瓜数据集见 西瓜数据集二.0，输出如下：
['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
{'纹理': {'清晰': {'根蒂': {'蜷缩': '是', '硬挺': '否', '稍蜷': {'色泽': {'青绿': '是', '乌黑': {'触感': {'硬滑': '是', '软粘': '否'}}}}}}, '稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}, '模糊': '否'}}
为了可以反映决策树的优越性即决定方便，那里依照matplotlib模块编写可视化函数treePlot，对转移的决策树进行可视化，可视化结果如下：
鉴于数量太少，未有安装测试数据以表达其准确度，不过本身背后会基于乳腺囊性增生病的例证进行准确度的测试的，上边进入下有些：
有一连值的情况
有连续值的情况如 西瓜数据集三.0
几天品质有很八种取值，大家自然无法每一种取值都做1个分段，那时候供给对连日属性实行离散化，有三种艺术供选取，个中三种是：
一.对每壹类别的数据集的连接值取平均值，再取各种的平均值的平均值作为划分点，将接二连三属性化为两类成为离散属性
二.C四.伍莱用的二分法，排序离散属性，取每四个的正中作为划分点的候选点，总计以每种划分点划分数据集的新闻增益，取最大的不得了划分点将接连属性化为两类成为离散属性，用该属性进行分割的新闻增益正是刚刚计算的最大音讯增益。公式如下：
此处运用第三种，并在念书前对连接属性进行离散化。扩展拍卖的代码如下：
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，对数据集提前离散化，然后再实行学习，学习代码类似。输出的决策树如下：
有缺失值的情景
数量有缺点和失误值是常见的情况，我们倒霉直接丢掉这个数据，因为那样会损失大批量数目，不划算，但是缺点和失误值大家也无能为力看清它的取值。如何是好呢，办法依旧有的。
设想多个难题：
一.有缺点和失误值时怎么样实行划分选用
二.已选取划分属性，有缺点和失误值的样本划不分开，如何划分？
问题1：有缺点和失误值时怎么样进行私分选择**
骨干思索是展开最优待军属和烈士家属性选用时，先只思量无缺点和失误值样本，然后再乘以相应比例，拿到在任何样本集上的大致景况。连带思索到第三个难点来说，思量给每一个样书四个权重，此时各样样本不再总是被作为3个单身样本，那样有利于第三个难点的消除：即若样本在属性a上的值缺点和失误，那么将其看做是全数值都取，只可是取每个值的权重不平等，各种值的权重参考该值在无缺失值样本中的比例，简单地说，比如在无缺失值样本集中，属性a取去八个值一和二，并且取壹的权重和占全体权重和1/三，而取2的权重和占2/3，那么依据该属性对样本集进行剪切时，蒙受该属性上有缺点和失误值的样书，那么我们认为该样本取值二的大概越来越大，于是将该样本的权重乘以2/三归到取值为二的样书集中继续拓展剪切构造决策树，而乘1/3划到取值为壹的样本集中继续协会。不明了自家说精晓没有。
公式如下：
其中，D~表示数据集D在属性a上无缺点和失误值的范本，依照它来判定a属性的上下，rho(即‘lou’)表示属性a的无缺失值样本占全部样本的比重，p~_k表示无缺点和失误值样本中第k类所占的比例，r~_v表示无缺点和失误值样本在属性a上取值为v的范本所占的百分比。
在细分样本时，假若有缺点和失误值，则将样本划分到全体子节点，在属性a取值v的子节点上的权重为r~_v
* 原来的权重。
更详实的解读参考《机器学习》P8陆-87。
根据权重法修改后的ID三算法完成如下：
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
有缺点和失误值的景况如 西瓜数据集二.0阿尔法
试行结果：
在乳腺炎数据集上的测试与表现
有了算法，大家自然想做一定的测试看1看算法的显现。那里自身选拔了威斯康辛女性附件炎的多少。
数码总共有玖列，每一列分别表示，以逗号分割
1 Sample
code number （病人ID）
二 Clump
Thickness 肿块厚度
3Uniformity of Cell Size 细胞大小的均匀性
4Uniformity of Cell Shape 细胞形状的均匀性
5
Marginal Adhesion 边缘粘
陆 Single
Epithelial Cell Size 单上皮细胞的分寸
7 Bare
Nuclei 裸核
八 Bland
Chromatin 乏味染色体
9 Normal
Nucleoli 正常核
10Mitoses 有丝差别
1一 Class:
二 for benign, 四 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)))
练习出的决策树如下：
最后的正确率可以看来：
正确率约为9六%左右，算是不差的分类器了。
自家的输卵管炎数据见：http://7xt9qk.com2.z0.glb.clouddn.com/breastcancer.txt
迄今，决策树算法ID3的兑现得了，下边记挂基于基尼指数和音信增益率进行私分选用，以及思索达成剪枝进度，因为大家得以看来上边演练出的决策树还留存着不少冗余分支，是因为达成进程中，由于数据量太大，每一种分支都不完全纯净，所以会成立往下的分支，不过分支投票的结果又是1模一样的，而且数据量再大，特征数再多的话，决策树会非常大格外复杂，所以剪枝一般是必做的一步。剪枝分为先剪枝和后剪枝，就算细说的话能够写很多了。
此文亦可知：这里
参考资料：《机器学习》《机器学习实战》通过这一次实战也发觉了那两本书中的1些荒谬之处。
lz初学机器学习不久，如有错漏之处请多原谅建议依然各位有如何想法或意见欢迎评论去报告本身：）