决策树的一般思路分析（机器学习实战）

快来打我* 2022-05-24 11:47 177阅读 0赞

'''决策树：  
在构造决策树时最重要的是确定划分数据时，哪个特征起决定性作用  
为了确定起决定性作用的特征，必须先计算信息的增益，获得信息增益  
最高的特征就是最好的选择  
  
  
集合信息的度量方式称为熵————信息的期望  
信息的定义：若待分类事物存在多个划分，则符号xi的信息定义为  
l(xi)=log2 (p(xi)), 其中p(xi)是选择该类的概率  
熵是信息的期望：H= -∑ p(xi)\*log2 (p(xi))，从1到n求和 n为分类的数目'''  
  
  
  
  
from math import log  
from numpy import \*  
  
  
def calculate\_entropy(data\_set):  \#计算熵  
    num\_entries=len(data\_set)  
    laber\_counst=\{\}  
    for feature\_vector in data\_set:  
        current\_laber=feature\_vector\[-1\]  
        if current\_laber not in laber\_counts.key():  
            laber\_counts\[current\_laber\]=0  
        laber\_counts\[currnt\_laber\]=1  
    entrop=0.0  
    for key in laber\_counts:  
        prob=float(laber\_counts\[key\])/num\_entries  
        entrop-=prob\*log(prob,2)  
    return entrop  
  
  
\# 划分数据集  
\#split\_dataset的输入参数(数据集，划分数据的特征，满足划分的特征的值)  
\#输出时 元数据集上减去（列数减少—除去了特征的那一列，元素减少—挑出是满足value的那些元素）满足划分特征后的剩余集  
def split\_dataset(dataset, axis, value):  
    ret\_dataset=\[\]  
    for feauret\_vector in dateset:  
        if feature\_vector\[axis\]==vlaue:  
            reduce\_feature\_vector=feature\_vector\[:axis\]  
            reduce\_feature\_vector.exdend(feature\_vector\[axis+1:\])  
            ret\_dataset.append(reduce\_feature\_vector)  
    return ret\_dataset  
  
  
\#选择最好的数据划分方式  
\#返回的是最好的划分特征，依据每个特征的熵（信息的增益）计算出  
def choose\_best\_feature\_to\_split(dataset):  
    num\_feature=len(dataset\[0\])-1  \#dataset的最后一列是标签  
    base\_entropy=calculat\_entrop(dataset)  
    best\_info\_gain, best\_feature=0.0, -1  
    for i in range(num\_feature):  
        feature\_list=\[example\[i\] for example in dataset\]  
        unique\_vals=set(feature\_list)  
        new\_entropy=0.0  
        for value in unique\_vals:  
            subdataset=split\_dataset(dataset,i,value)  \#待划分数据集，划分特征，返回的特征值  
            prob=len(subdataset)/float(len(dataset))  
            new\_entropy+=prob\*calculate\_entropy(subdataset)  
            info\_gain=base\_entropy-new\_entropy  
            if infogain>dest\_info\_gain:  
                best\_info\_gain=info\_gain  
                best\_feature=i  
    return best\_feature  
  
  
def majority\_cnt(class\_list):  \#返回的是频数最高的类别的名称  
    class\_count=\{\}  
    for vote in class\_list:  
        if vote not in calss\_count.key():  
            class\_count\[vote\]=0  
        else:  
            class\_count\[vote\]=1  
    sorted\_calss\_count=sorted(class\_count.items(),key=operator.itemgetter(1),reverse=True)  
    return sorted\_class\_count\[0\]\[0\]  
  
  
def creat\_tree(dataset,laber):  \#构造决策树，采用的是字典数据结构  
    class\_list=\[example\[-1\] for example in dataset\]  
    if class\_list.count(class\_list\[0\])==len(class\_list):  
        return class\_list\[0\]  
    if len(dataset)==1:  
        return majority\_cunt(class\_list)  
    best\_feature=choose\_best\_feature\_to\_split(dataset)  
    best\_feature\_laber=laber\[best\_feature\]  
    my\_tree=\{best\_feature\_laber:\{\}\}  
    del(laber\[best\_feature\])  
    feature\_value=\[example\[best\_feature\] for example in dataset\]  
    unique\_values=set(feature\_value)  
    for vlaue in unique\_values:  
        sublabers=laber\[:\]  
        my\_tree\[best\_feature\_laber\]\[value\]=craet\_tree(split\_dataset(dataset,best\_feature,value),sublabers)  
    return my\_tree