<学习笔记> 决策树

2017-11-12

决策树所做的工作：
读取数据集合，获取其中蕴含的知识信息，使用不熟悉的数据集合，并从中提取出一系列的规则，然后机器学习算法最终将使用这些机器
从数据集中创造规则。
优点：
计算复杂度不高，输出结果便于理解，对中间值的缺失不敏感，可以处理不相关的特征数据。
缺点：
可能会产生过度匹配的问题。
构造决策树的方法：
首先我们要搞清楚哪个特征在划分数据分类时起到了决定性的作用。
为了找到决定性的特征，得到最优的结果，我们要对每一个特征值进行评估，完成这样的测试之后，原始的数据集就依据上面的特征划分为几个数据集。
这些数据集分布在我们的第一个决策点的各个分支上，接下来，我们还要检查，在同一个分支上是否都是同一个类型，如果子集中的数据集已经是同一
类型，我们就达到目的了，相反，我们要依照上面的方法，重复划分的过程，直到每个分支上的数据的类型不能再分。
信息增益
我们划分数据集的大原则：将无序的数据变得更加有序。
我们要了解一些信息论的术语了。
熵：信息的期望值。
信息：如果待分类的事务可能划分在多个分类之中，则x的信息定义为：

1	l(x)=-logp(x)

其中p(x)为选择某个分类的概率。
那么我们的熵就可以定义为：

1	H=-∑p(x)logp(x)

也就是每个x的信息与选取这个信息的概率的乘积，然后将所有总体上所取的期望值。
我们来计算香农熵：

def cshannon(dataset):
    num=len(dataset)  #将数据集总数记录；
    labelcounts={}  #创建一个字典保存每种类型的数据出现的次数；
    for featvec in dataset:
        currentlabel=featvec[-1]  #取最后一列作为label
        if currentlabel not in labelcounts.keys():   #如果字典中不存在当前加入的label
            labelcounts[currentlabel]=1
        labelcounts[currentlabel]+=1  #添加进去
    shannon=0.0
    for key in labelcounts:   #利用公式计算熵值
        prob=float(labelcounts[key])/num
        shannon-=prob*log(prob,2)
    return shannon

通过测试，我们很容易发现，熵越高，我们混合的数据也就越多。
划分数据集
我们需要对每个特征划分的数据集计算一次香农熵，然后判断哪个特征划分数据集是最好的划分方式。

def splitdata(dataset,axis,value):
    rtndataset=[]
    for featvec in dataset:
        if featvec[axis]==value:
            reducedfeatvec=featvec[:axis]
            reducedfeatvec.extends(featvec[axis+1:])
            rtndataset.append(reducedfeatvec)
    return rtndataset

向我们的方法中传入三个参数：数据集，特征，特征的返回值
我们遍历数据集中的每一列向量，发现符合我们要求的值，我们就把它加入我们要得到的集合当中。

def choosebestfeaturetosplit(dataset):
    numfeatures=len(dataset[0])-1;#获得数据集的长度；其实是一个由各种属性组成的矩阵；
    baseentropy=cshannon(dataset)#调用计算香农熵的函数计算
    bestinfogain=0.0#初始化划分最好的香农熵和最好的参考特征；
    bestfeature=-1
    for i in range(numfeatures):#遍历所有特征值；
        featlist=[example[i] for example in dataset]
        uniquevals=set(featlist)
        newentropy=0.0
        for value in uniquevals:
            subdataset=splitdata(dataset,i,value)
            prob=len(subdataset)/float(len(dataset))
            newentropy+=prob*cshannon(subdataset)
        infogain=baseentropy-newentropy
        if(infogain>bestinfogain):#更新；
            bestinfogain=infogain
            bestfeature=i
    return bestfeature

在这个函数调用的数据要符合以下条件：
1.数据必须要是由列表元素组成的的列表
2.所有的列表元素都要具有相同的数据长度
3.数据的最后一列或者每个实例的最后一个元素是当前实例的label
如果数据集处理了所有的属性，但是类标签仍然不是唯一的，这时候，我们要继续进行”分叉”,去思考如何定义该叶子节点，
这种情况，我们就会采取多数表决的方法来决定分类。

def majoritycnt(classlist):
    classcount={}
    for vote in classlist:
        if vote not in classcount.keys():
            classcount[vote]=0
        classcount[vote]+=1
    #统计每种分类的数目，表决器
    sortedclasscount=sorted(classcount,key=operator.itemgetter(1),reverse=True)
    return sortedclasscount[0][0]#排序返回出现次数最多的

最后就是利用递归法建一棵树了：

def createtree(dataset,labels):
    classlist=[example[-1] for example in dataset]#创建包含所有类标签的一个list
    if classlist.count(classlist[0])==len(classlist):#递归边界一：所有的类标签都相同；
        return classlist[0]
    if len(dataset[0])==1:#递归边界二：使用了所有特征进行划分，选取出现次数最多的返回；
        return majoritycnt(classlist)
    bestfeat=choosebestfeaturetosplit(dataset)#选取最优特征；
    bestfeatlabel=labels[bestfeat]
    mytree={bestfeatlabel:{}}
    del(labels[bestfeat])#删除引用；
    featvalues=[example[bestfeat] for example in dataset]
    uniquevals=set(featvalues)#得到列表中的所有属性值；
    for value in uniquevals:
        sublabels=labels[:]#复制类标签，防止改变原始列表的内容；
        mytree[bestfeatlabel][value]=createtree(splitdata(dataset,bestfeat,value),sublabels)
    return mytree

ps:感谢<机器学习实战>一书的讲解！