深入浅出决策树

def create_data_set():
    dataset = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['usb', 'exe'] # 第一个代表是否从U盘下载来，第二个代表是否是exe文件后缀，第三个代表是否是病毒文件
    print(dataset, labels)
    return dataset, labels

# 计算数据中的信息熵： H = -∑p(x)log2 p(x)
def calc_shannon_ent(dataset):
    numentries = len(dataset)
    labelcounts = {}    # 创建标签字典
    for featvec in dataset:
        currentlabel = featvec[-1]  # 数据的最后一列是标签作为字典的键值
        if currentlabel not in labelcounts.keys():   # 记录属于该标签数据的次数，后面计算熵使用，
            labelcounts[currentlabel] = 0   # 如果字典里没有这个标签即键值，则创建并赋值为0，如果存在该标签则加1
        labelcounts[currentlabel] += 1
    shannonent = 0.0    # 计算熵值
    for key in labelcounts:
        prob = float(labelcounts[key]) / numentries  # 以每个标签出现的频次为概率计算熵值
        shannonent -= prob * log(prob, 2)
    return shannonent

# 按照给定特征划分数据集
def split_data_set(dataset, axis, value):  # dataset为原始输入数据，axis是原始数据的特征位置，value是数据对应的特征值
    retdataset = []
    for featvec in dataset:  # 迭代dataset中的数据
        if featvec[axis] == value:  # 通过迭代判断每个数据特征位置的数据和给定的特征值是否一致
            reducedfeatvec = featvec[:axis]  # 如果条件成立，那么就把该位置前面的数据保存
            reducedfeatvec.extend(featvec[axis+1:])  # 把该位置后面的数据保存，通过这两句就可以把该特征位置删除
            retdataset.append(reducedfeatvec)  # 把保留下来的数据，存储在新的列表里作为一个元素
            '''下面有例子解释一下上面的三句代码
                trees.split_data_set(mydata, 0, 1)，输入的数据为mydata， 特征位置为0即axis， 数据特征值为1
执行后的数据
原始数据： [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
划分好的数据：  [[1, 'yes'], [1, 'yes'], [0, 'no']]
原始数据是一个列表，这个列表有5个元素，而每个元素又是一个列表，每个元素列表中又有三个元素
                featvec[axis] == value这句代码的意思是featvec从dataset中获得元素后，例如为第一个元素[1, 1, 'yes']，
此时featvec[axis]是指该元素的第零个位置数据即为1，value为给定的特征划分值为1，此时if成立，执行下面的程序
                reducedfeatvec = featvec[:axis]，列表的切片，不会的请查看列表的切片，featvec[:axis]是指把axis位置前面的数据传给reducedfeatvec
，而featvec[axis+1:]是把特征位置后面的数据都保存下来如[1, 'yes']，把保存下来，简单说 这两句意思就是把axis位置删除
把重新组建的数据传给retdata
            '''
    return retdataset
 

# 选择数据集划分方式，主要通过信息增益进行划分
def choose_bestfeature_to_split(dataset):
    num_features = len(dataset[0]) - 1  # 计算每个元素有多少特征
    print(num_features)  # 只计算前两个数值特征
    base_entropy = calc_shannon_ent(dataset)  # 计算基础香浓熵
    best_info_gain = 0.0
    best_feature = -1
    # 下面为计算信息增益做准备工作
    for i in range(num_features):
        feat_list = [example[i] for example in dataset]  # 利用列表推倒，把每个元素数据的特征提取出来，并创建新列表
        print('feat_list', feat_list)  # 打印出来发现是feat_list [1, 1, 1, 0, 0]，即表明把dataset的第0号位置的特征提取出来
        unique_vals = set(feat_list)  # 使用集合元素数据中重复的特征合并
        print('unique_vals', unique_vals)  # 把feat_list [1, 1, 1, 0, 0]重合的合并为unique_vals {0, 1}
        new_entropy = 0.0
        for value in unique_vals:
            subdataset = split_data_set(dataset, i, value)  # 根据特征把同类的数据归类，并计算香浓熵
            prob = len(subdataset)/float(len(dataset))  # 计算概率
            new_entropy += prob * calc_shannon_ent(subdataset)  # 计算条件熵
        info_gain = base_entropy - new_entropy   # 计算信息增益
        if (info_gain > best_info_gain):  # 找出信息增益最大的特征
            best_info_gain = info_gain
            best_feature = i
    return best_feature

# 创建决策树
def create_tree(dataset, labels):
    classlist = [example[-1] for example in dataset]
    # 该句代码的意思是，把元素数据的分类信息提取出来，此时classlist = ['yes', 'yes', 'no', 'no', 'no']
    if classlist.count(classlist[0]) == len(classlist):
        return classlist[0]
    '''
    # 第一个递归停止条件，如果classlist中的信息都为同一类，则说明分类已经是纯净的了，无须再划分，返回类别就好
    # 如classlist = ['no', 'no', 'no'],此时classlist[0]出现三次，而列表长度也为3，等式成立执行if语句，即返回类别’no‘
    '''
    if len(dataset[0]) == 1:  # 使用完了所有的特征，但还是无法将数据划分为唯一类别的分组，因此就挑选出现次数最多的类别进行分类
        return max(classlist,key=classlist.count)
    '''
    # 第二个递归停止条件是根据特征判断，因为每次根据特征划分时，后面就会删除该特征，如果遍历完所有特征以后发现classlist还是不纯净，
    # 那么就通过出现的次数划分。如刚开始dataset[0] = [1, 1, 'yes']，有两个特征，一个分类标签，当每根据一个特征进行分类结束时就会
    # 删除该特征，最后只剩下dataset[0] = ['yes'],无法再根据特征进行分类，此时，根据分类列表中把该元素划分到出现类别最多的次数的
    # 分类中，如classlist = ['no', 'yes', 'yes','yes'],此时‘no’出现一次，‘yes’出现三次，因此把该类分为‘yes’，其中通过函数
    # majority_cnt（）进行统计。
    '''
 
    bestfeat = choose_bestfeature_to_split(dataset)  # 使用信息增益返回最好的划分特征的列表位置信息
    # 分类的标准是通过ID3算法即信息增益进行划分，返回的是使信息增益增加最大的特征
    bestfeatlabel = labels[bestfeat]
    # 提出该最优特征 第一次特征为'U盘'
    mytree = {bestfeatlabel: {}}
    # 以当前使信息增益最大的特征创建以字典形式迭代的迭代器,此时为mytree = {U盘: {}}
    del (labels[bestfeat])
    # 删除该使用的特征
    featvalues = [example[bestfeat] for example in dataset]
    # 遍历所有元素的最优特征位置对应的特征值featvalues = [1, 1, 1, 0, 0]
    unique_vals = set(featvalues)
    # 转换成集合形式，即去除重复的特征值，集合的互异性可以使相同特征值合并,此时unique_vals = [1,0]
    for value in unique_vals:
        sublabels = labels[:]
        # 复制一份 标签列表
        mytree[bestfeatlabel][value] = create_tree(split_data_set(dataset, bestfeat, value), sublabels)
    return mytree

def classify(inputtree, featlabels, testvec):
    firststr = list(inputtree.keys())[0]
    second_dict = inputtree[firststr]
    feat_index = featlabels.index(firststr)
    for key in second_dict.keys():
        if testvec[feat_index] == key:
            if type(second_dict[key]) == dict:
                classlabel = classify(second_dict[key], featlabels, testvec)
            else:
                classlabel = second_dict[key]
    return classlabel

data_set, labels = create_data_set()
decision_tree = create_tree(data_set, labels)
print "决策树：", decision_tree

print classify(decision_tree, labels, [1, 0])
print classify(decision_tree, labels, [1, 1])
print classify(decision_tree, labels, [0, 0])

output:
决策树： {'usb': {0: 'no', 1: {'exe': {0: 'no', 1: 'yes'}}}}
no
yes
no