怎么样落到实处并拔取决策树算法?

本文对裁决树算法进行简单的下结论和梳理,并对知名的裁定树算法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.连接值和标称值混合,有缺失数据集

首先个算法参考了《机器学习实战》的大多数代码,第二、三个算法基于后边的完结举办模块的伸张。

决策树简介

核定树算法不用说我们应该都精通,是机器学习的一个显赫算法,由澳大多特Mond有名总括机数学家罗丝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地图