怎样实现并动用决策树算法?

本文对裁定树算法进行简短的总结暨梳理,并针对性红的核定树算法ID3(Iterative
Dichotomiser
迭代二分器)进行落实,实现以Python语言,一词老梗,“人生苦短,我为此Python”,Python确实能够省多言语方面的从,从而可以让我们注意于问题及化解问题的逻辑。

1
引言 
  于应用程序的设计着,经常索要读取Excel数据还是将Excel数据导入转换到其它数载体被,例如将Excel数据经过应用程序导入SQL
Sever等数据库被以备使用。笔者于开“汽车产业链ASP协同商务平台”中相遇了近乎需求。某汽车整车生产合作社急需以那车辆发车信息公布到汽车产业链平台上去,其数据也中ERP系统生成的Excel数据表,用户率先用该数据表上传至汽车产业链平台,平台以此Excel数据读取导入到平台间的SQL
Sever数据库被,以供其他应用使用。汽车产业链平台的付出以的开发工具为VS.NET,使用的语言是C#,在出的历程被发现采用Microsoft.Jet.OLEDB.4.0读取数据会现出当某一字段外分别包含文本及数字的搅和数据时,某一样类的多寡会起丢失。本文就针对这题材产生的来源于进行了剖析并让出了对应的解决方法。 
2
问题讲述 
  Excel是Microsoft公司的电子表格处理软件,在现世办公室和公司信息化的采取中以十分广阔,正因如此,在先后设计被我们经常要通过访问Excel文件来得到数据,但Excel文件不是专业数据库[1]。 
  ASP.NET也是Microsoft公司之产品,作为.NET
FrameWork框架中之一个最主要组成部分,其要用于Web设计。我们以.NET中做客读取Excel数据时一般用Microsoft.Jet.OLEDB.4.0[2]。现以读取一个Excel文件auto.xls中sheet1工作表为条例,工作表的情节要表1所著。 
  表1 sheet1表明底数据内容 
  现将该表的数目内容读取并展示到到DataGrid中,简化的代码如下: 
  String ConnStr = ” Provider = Microsoft.Jet.OLEDB.4.0;
DataSource=c:/auto.xls;Extended Properties=’Excel 8.0;HDR=YES’;”; 
  OleDbConnection Conn=new OleDbConnection(ConnStr); 
  Conn.Open(); 
  string SQL=”select * from [sheet1$]”; 
  OleDbDataAdapter da=new OleDbDataAdapter(SQL,ConnStr); 
  DataSet ds=new DataSet(); 
  da.Fill(ds); 
  DataGrid1.DataSource=ds; 
  DataGrid1.DataBind(); 
  Conn.Close(); 
  但是运行以上代码的结果连无是盼之,它将展示为表2所出示之始末。可以发现第一单字段被呢“1042”的星星点点独数据项变为空。 
  表2 DataGrid1所显示的数内容 
  有先后设计人员以以上代码OleDbConnection连接字符串中之Extended
Properties一件作了之类改变,Extended Properties=’Excel
8.0;HDR=NO;IMEX=1’,认为可解决是问题。由于在出“汽车产业链协同商务平台”中相见了类似题材,作了大气之测试后意识,添加IMEX=1后无实质上解决是问题。表现也:如果有字段前8长达记下中全部为纯数字来说,那么当该字段随后的记录面临涵盖字母或汉字的项将仍然变为空,但是如果该字段前8修记下着生同一条未也纯数字,将能够得预期想如果的结果。 
   
3
问题浅析 
  产生这种题材之源于与Excel ISAM[3](Indexed Sequential Access
Method,即索引顺序存取方法)驱动程序的限量有关,Excel ISAM
驱动程序通过检查前几乎行吃实际值确定一个 Excel
列的型,然后选取能代表其样本中多数分值的数据类型[4]。也即Excel
ISAM查找某列前几乎尽(默认情况下是8行),把占多的色作为该处理项目。例如如果数字占大半,那么其它富含字母等文件的数额项就见面置空;相反如果文本居多,纯数字之数据项就见面被置空。 
  现具体分析在第1节程序代码Extended
Properties项中的HDR和IMEX所表示的含义。HDR用来安装是否将Excel表中率先推行作为字段名,“YES”代表是,“NO”代表不是不怕为为数量内容;IMEX是故来喻驱动程序使用Excel文件的模式,其值有0、1、2老三栽,分别表示导出、导入、混合模式。当我们安IMEX=1时拿劫持混合数据易为文本,但特这种装置并无牢靠,IMEX=1特保证以某列前8行数据至少有一个凡文件项的上才于作用,它只是把查找前8行数据中数据类型占优选择的一言一行作了略微的改观。例如某列前8行数据均否纯数字,那么它仍然因数字型作为该列的数据类型,随后行里的盈盈文本的数据还是变空。 
  另一个改良之法子是IMEX=1与登记表值TypeGuessRows配合下,TypeGuessRows
值决定了ISAM
驱动程序从前面几乎条数采样确定数据类型,默认为“8”。可以经过修改“HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Jet\4.0\Engines\Excel”下之拖欠注册表值来改变采样行数。但是这种改进要么不曾从达缓解问题,即使我们将IMEX设为“1”,
TypeGuessRows设得重新杀,例如1000,假要数据表有1001尽,某列前1000行都呢纯数字,该列的第1001推行而是一个文书,ISAM驱动之这种机制还是给这排的数码化空。 
   
4
解决办法 
  从上述之解析中可以得知,当某列数据中含混合类型时,在.NET中采用Microsoft.Jet.OLEDB.4.0来读取Excel文件造成数丢失是不可避免的,要解决这个题材不得不考虑以任何数据读取方法。 
  在.NET中读取Excel文件之另外一栽艺术是归用传统COM组件,这种办法在群术文章要舆论中还生涉嫌,本文不发赘述。需要指出的凡,使用COM组件来读取Excel文件数量的频率比逊色,在发释放的当儿发生或撞不可预知的荒唐,特别开Web应用的顺序应该慎重使用。 

据悉不同之多少,我实现了三个本子的ID3算法,复杂度逐步提升:

本文提出另外一栽采取读取CSV纯文本格式解决这个题材的方。 
  (1)在读取Excel的.xls类型的文本数据之前,先将该转移为.csv格式,在Excel中直接另存也这种格式就足以达成转换的目的。CSV文件又称作逗号分隔的文件,是千篇一律种纯文本文件,它坐“,”分隔数据列,本文表1的数额表用CSV格式存储后就此纯文本编辑器打开的表现形式如表3所出示。 
  表3 采用CSV格式保存的表1数据 
  需要指出的是,CSV文件呢可以用Ole
DB或ODBC的法子读取,但是若利用这些措施读博该数量而见面回到丢失数据的套路上,ISAM机制同会发挥作用。 
  (2)采用一般的读取文本文件之措施打开文件,读取第一履行,用“,”作为分隔符获得各字段名,在DataTable中开创对应之每字段,字段的类可以统一创造成为“String”。 
   
本文原文 
  (3)逐行读取数据行,
用“,”作为分隔符获得某行各列的数目并填写入DataTable相应的字段中。 
  实现之简化代码如下: 
  String line; 
  String [] split = null; 
  DataTable table=new DataTable(“auto”); 
  DataRow row=null; 
  StreamReader sr=new
StreamReader(“c:/auto.csv”,System.Text.Encoding.Default); 
  //创建及数据源对应之数量列 
  line = sr.ReadLine(); 
  split=line.Split(‘,’); 
  foreach(String colname in split){ 
  table.Columns.Add(colname,System.Type.GetType(“System.String”));

  //将数据填充数据表 
  int j=0; 
  while((line=sr.ReadLine())!=null){ 
   j=0; 
   row = table.NewRow(); 
   split=line.Split(‘,’); 
   foreach(String colname in split){ 
   row[j]=colname; 
   j++;} 
   table.Rows.Add(row);} 
   sr.Close(); 
  //显示数据 
  dataGrid1.DataSource=table.DefaultView; 
  dataGrid1.DataBind(); 
   
5
结语 
  在应用程序的计划中,需要访问Excel数据的场面颇广泛,本文为当.NET中对访含有混合类型数据的Excel表格拟采取的计进行探讨。当然,如果非在混合类型的多寡运用Microsoft.Jet.OLEDB为于理想方案。对于不是使用.NET开发之情,本论文的剖析及所提供的办法会参考。

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

OLEDB 连接EXCEL的连年字符串 IMEX的题材

       今天遇上一个题材亟待想EXCEL表中形容多少,折腾了长期才察觉凡是IMEX惹得祸,所以记录下提醒自己,也可望大家不要来同的摩擦。 

碰到问题:使用语句 “insert into [Sheet1$] (大类) values (‘test’)”
无法插入 。 

原因:Provider=Microsoft.Jet.OLEDB.4.0;Data
Source=’2008-08.xls’; Extended Properties=’Excel 8.0;HDR=Yes;IMEX=1′ 

釜底抽薪方法:
去丢IMEX=1 

补充: 
       向EXCEL插入数据时 数据类型是由前8行数据遭到数据类型占优选择
例如:分数一排列前前8行为空值 插入5为字符串格式,如果前8行为数字格式
插入5呢数字格式关于IMEX的资料: 

       IMEX是因此来报告驱动程序使用Excel文件之模式,其值有0、1、2叔种植,分别代表导出、导入、混合模式。当我们装IMEX=1时用强制混合数据易为文本,但无非这种装置并无保险,IMEX=1一味包于某列前8行数据至少有一个是文本项的时才自作用,它只是把查找前8行数据被数据类型占优选择的表现作了稍稍的更改。例如某列前8行数据都呢纯数字,那么它们依旧以数字型作为该列的数据类型,随后行里的盈盈文本的数据还是变空。 

  另一个改良的法门是IMEX=1与注册表值TypeGuessRows配合以,TypeGuessRows
值决定了ISAM
驱动程序从眼前几长达数采样确定数据类型,默认为“8”。可以经过改“HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft
\Jet\4.0\Engines\Excel”下之该注册表值来转采样行数。但是这种改进要么不曾从上化解问题,即使我们将IMEX设为“1”,
TypeGuessRows设得又不行,例如1000,假要数据表有1001尽,某列前1000行都否纯数字,该列的第1001推行以是一个文件,ISAM驱动之这种机制还是受这排的数目化空。

2.连续值与标称值混合且无短缺失数据集

3.老是值与标称值混合,有缺乏失数据集

第一独算法参考了《机器上实战》的大部代码,第二、三只算法基于前的贯彻进行模块的加。

仲裁树简介

决定树算法不用说大家该都亮,是机械上的一个响当当算法,由澳大利亚举世瞩目计算机科学家Rose
Quinlan发表。

决策树是均等种监督上的归类算法,目的是上学产生同颗决策树,该树中间节点是数码特征,叶子节点是项目,实际分类时根据树的组织,一步一步冲目前多少特征取值选择进入哪一样粒子树,直到走至叶子节点,叶子节点的型就是是其一决定树对是数的念结果。下图虽是同粒简单的裁定树:

图片 1以此决定树用来判断一个兼有纹理,触感,密度的西瓜是否是“好瓜”。

当起这么一个西瓜,纹理清晰,密度为0.333,触感硬滑,那么要而认清是否是一个“好瓜”,这时要由此决策树来判断,显然好一直本着纹理->清晰->密度<=0.382->否,即是瓜不是“好瓜”,一潮裁决就这样好了。正以决策树决策很便利,并且准确率为比较高,所以时吃用来做分类器,也是“机器上十特别算法”之一C4.5的着力思想。

习产生同样粒决策树要考虑一个问题,即 根据数量集构建当前培训应该选哪种特性作为树根,即分标准? 

考虑最好的景,一开始选有特征,就管数据集划分成,即以拖欠特征上取某个值的备是一律近乎。

考虑最要命之景象,不断选择特征,划分后底数据集总是乱,就第二分拣任务以来,总是有正类有负类,一直顶特征全部据此完了,划分的多少集合还是有刚发负,这时只能用投票法,正接近多便挑正类作为叶子,否则选负类。

用得出了相似结论:
随着划分的开展,我们想选择一个特色,使得子节点包含的范本尽可能属于同一档次,即“纯度”越强逾好。

基于“纯度”的规范不同,有三种算法:

1.ID3算法(Iterative
Dichotomiser
迭代二分器),也是本文要落实的算法,基于信息增益即信息熵来度量纯度

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

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

ID3算法简介

信熵是信息论中的一个关键概念,也叫“香农熵”,香农先生的史事相比多口都任了,一个丁创造了扳平派理论,牛的坏。香农理论被一个挺重点的性状就是是”熵“,即”信息内容的不确定性“,香农在开展信息的定量测算的当儿,明确地将信息量定义为擅自不定性程度之减。这就算标明了外本着信息的知道:信息是为此来压缩随意不定性的东西。或者发表为香农逆定义:信息是妇孺皆知的充实。这也印证了决定树为熵作为划分选择的胸怀标准的是,即我们怀念再迅速地自数中获得更多信息,我们尽管应很快回落不确定性,即减少”熵“。

信熵定义为:

图片 2

D表示数据集,类别总数也|Y|,pk代表D中第k类样本所占的百分比。根据该定义,Ent的价值更聊,信息纯度越强。Ent的限制是[0,log|Y|]

下要选择有属性进行划分,要依次考虑每个属性,假设当前设想属性a,a的取值有|V|种,那么我们希望取a作为划分属性,划分到|V|个子节点后,所有子节点的信熵之与就分后底音讯熵能够发生很死之缩减,减小的不过多之杀属性就是我们挑选的习性。

分后的消息熵定义为:

图片 3 

从而用属性a对样本集D进行剪切的信息增益就是原的音熵减去划分后底音讯熵:

图片 4

ID3算法就是这般每次挑一个属性对样本集进行私分,知道少种植情景而这进程停止:

(1)某个子节点样本全部属同一近乎

(2)属性都为此完了,这时候若果实节点样本或未平等,那么只能少数从多数了

图片 5(图片来源网络)

ID3算法实现(纯标称值)

设样本全部凡标称值即距离散值的讲话,会比较简单。

代码:

图片 6图片 7

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,对转移的仲裁树进行可视化,可视化结果如下:

图片 8

 

鉴于数量最少,没有装测试数据因说明其准确度,但是本人后面会根据乳腺癌的事例进行准确度的测试的,下面进入下局部:

发连续值的情况

产生连续值的情形只要 西瓜数据集3.0 

一个性能有充分多种取值,我们定不能够每个取值都召开一个支,这时候需要针对连属性进行离散化,有几种方法供选择,其中有数种植是:

1.针对各国一样近似别的数据集的连接值取平均值,再取各类的平均值的平均值作为划分点,将接连属性化为少好像成为离散属性

2.C4.5利用的次分叉效仿,排序离散属性,取诸半个之中段作为划分点的候选点,计算以每个划分点划分数据集的信增益,取最好可怜之那个划分点将接连属性化为零星近乎成为离散属性,用该属性进行分的信息增益就是刚计算的最好要命信增益。公式如下:

图片 9

这边以第二栽,并于习前对连日属性进行离散化。增加处理的代码如下:

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,对数据集提前离散化,然后再度拓展学习,学习代码类似。输出的决定树如下:

图片 10

生欠失值的景象

数量产生少失值是大的情状,我们不好直接丢弃这些数量,因为这么会损失大量数目,不经济,但是缺失失值我们吧束手无策判断其的取值。怎么收拾吧,办法要有。

设想个别个问题: 

1.发生少失值时怎样进行分选择

2.早已摘分属性,有缺乏失值的样本划不分,如何分割?

问题1:有欠失值时怎样进行私分选择**

骨干考虑是拓展最优属性选择时,先就考虑无短缺失值样本,然后重新乘以相应比例,得到在全样本集上之大概情况。连带考虑到第二只问题吧,考虑为各国一个样书一个权重,此时每个样本不再总是被看做一个单独样本,这样便于第二独问题之解决:即如果样本在属性a上之值缺失,那么以其当做是所有值都得到,只不过取每个值的权重不同等,每个值的权重参考该值在无缺失值样本中之比重,简单地游说,比如当无缺失值样本集中,属性a取去两个值1和2,并且取得1之权重和占用尽权重和1/3,而收获2的权重和占2/3,那么根据该属性对样本集进行剪切时,遇到该属性上有缺乏失值的范本,那么我们以为该样本取值2的可能还可怜,于是以欠样本的权重乘以2/3由到取值为2的样本集中继续进行分构造决策树,而随着1/3扛及取值为1的样本集中继续组织。不知情我说知道没有。

公式如下:

图片 11

其中,D~表示数据集D在属于性a上无缺失失值的范本,根据其来判定a属性的好坏,rho(即‘lou’)表示属性a的无缺失值样本占所有样本的比重,p~_k表示无缺失失值样本被第k近似所占据的比重,r~_v表示无论是缺失失值样本在属于性a上取值为v的范本所占据的百分比。

在划分样本时,如果产生欠失值,则拿样本划分到所有子节点,在属性a取值v的子节点上的权重为r~_v
* 原来的权重。

再也详实的解读参考《机器上》P86-87。

依据权重法修改后的ID3算法实现如下:

图片 12图片 13

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.0alpha

试验结果:

图片 14

于乳腺癌数据集上的测试和见

出了算法,我们当然想做肯定的测试看一样拘禁算法的表现。这里我选了威斯康辛女性乳腺癌的数量。

数总共发生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)))

训练有之决定树如下:

图片 15

说到底的正确率可以观看:

图片 16

正确率约为96%横,算是不异之分类器了。

自身之乳腺癌数据表现:http://7xt9qk.com2.z0.glb.clouddn.com/breastcancer.txt

迄今为止,决策树算法ID3的贯彻得了,下面考虑因基尼指数和信息增益率进行分割选择,以及考虑实现剪枝过程,因为咱们可见见地方训练有底仲裁树还在正在广大冗余分支,是以实现过程遭到,由于数据量太好,每个分支都非全纯净,所以会见创造为下之分层,但是分支投票的结果以是同等的,而且数据量再特别,特征数还多吧,决策树会非常充分非常复杂,所以剪枝一般是肯定做的如出一辙步。剪枝分为先剪枝和后剪枝,如果细说的言语可形容深多了。

此文亦可见:这里
参考资料:《机器上》《机器上实战》通过此次实战也意识了立点儿本书中之局部谬误的处在。

lz初学机器上不久,如产生错漏的处在请求多包涵指出要各位有啊想法还是意见欢迎评论去报告我:)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图