决策树

一、问题描述

使用决策树预测患者需要佩戴的眼镜类型，根据数据集lenses.data，分为训练集和测试集，使用ID3算法，信息增益作为属性选择度量，自顶向下的分治方式构造决策树，从有类标号的训练元组中学习决策树，再用决策树对测试集分类，计算准确率和误分类率，评估分类器的性能。

二、主要设备（软件）

Ubuntu,python2.7

三、 决策树算法

数据分区：最开始为训练元组和他们相应类标号的完全集

属性列表：描述元组属性的列表

选择最优属性方法：指定选择属性的启发式过程，用来选择可以按类最好地区分给定元组的属性：

树从单节点开始，若不满足三个终止条件则调用选择最优属性方法确定分裂准则，通过确定把数据集中的元组划分为个体类的“最好”方法，告诉我们在单节点上对哪个属性测试，使得每个分枝上的输出尽可能纯。对分裂准则每个输出都生长一个分枝，对每个分枝上的分区，递归构造决策树。

终止条件：

结束条件一：分区的所有元组都属于同一个类

结束条件二：没有剩余属性可以用来划分元组，只有类标签列，多数表决

结束条件三：给定的分枝没有元组，即分区为空时，用D中的多数类创建树叶

算法缺点：容易造成过度匹配：过拟合（overfitting）过于针对训练数据，熵值与真实情况比降低，泛化能力太弱

四、实验过程

（1）收集数据：提供的文件lenses.data 数据标签为：

lenses_labels = ['age', 'prescript', 'astigmatic', 'tear_rate']

（2）准备数据：

去掉文件中的行号，解析用空格分隔的数据行，将用readlines()读到的元组去掉空格，分割后改为int形式添加到列表中，取前15个为训练集，后8个为测试集。

（3）训练算法：分为两个py文件

#以下为trees.py
# coding:utf-8
from math import log
import operator
# 属性选择度量采用信息增益，计算信息熵
def calculate_info(data_set):
    num = len(data_set)  # 数据集中实例总数
    label_count = {}
    for feat_vec in data_set:  # 对于每个数据集中的元组，为类标号属性在类标号计数字典label_count中计数
        current_label = feat_vec[-1]
        if current_label in label_count.keys():
            label_count[current_label] += 1
        else:
            label_count[current_label] = 1
    info_D = 0.0
    for key in label_count.keys():  # 对每个类计算信息熵，即信息的期望值，求和。信息熵：H（x)=∑-p(xi)×logP(xi) i=1,2,3,...n
        prob = float(label_count[key]) / num
        info_D -= prob * log(prob, 2)
    return info_D


# 按照给定的属性划分数据集
# data 需要划分的数据，双重列表[[],[==],……,[]]
# attri 划分的属性
# value 属性的值
def splitData(data_set, attri, value):
    result = []
    for feature_vec in data_set:  # 对每个数据集中的元组找到符合给定属性的值的，抽取出来并去掉属性值添加到列表result[]
        if feature_vec[attri] == value:
            reduce_feat = feature_vec[:attri]
            reduce_feat.extend(feature_vec[attri + 1:])
            result.append(reduce_feat)
    return result


# 选择可以按类最好地区分给定元组的属性
def Attribute_selection(data_set):
    num_attribute = len(data_set[0]) - 1  # 每个元组中除类之外的属性的个数
    base_entropy = calculate_info(data_set)  # 未考虑属性前的信息熵
    best_info_gain = 0.0
    best_attribute = -1
    for i in range(num_attribute):  # 计算每个属性的信息增益Gain
        attribute_list = [item[i] for item in data_set]  # 将每个元组中的一列属性值放入列表中使用集合去重，得到这种属性的值
        unique_attribute = set(attribute_list)
        new_entropy = 0.0
        for value in unique_attribute:  # 对第i属性中每一种值划分数据集并计算信息熵，求和
            sub_data = splitData(data_set, i, value)
            prob = len(sub_data) / float(len(data_set))  # infoA(D)=∑(Dj/D)*info(Dj) A中分区的概率乘以它的信息熵
            new_entropy += prob * calculate_info(sub_data)
        info_gain = base_entropy - new_entropy  # 信息增益：原始信息熵-考虑属性i后的信息熵
        if info_gain > best_info_gain or info_gain == best_info_gain:  # 搜索最大信息增益
            best_info_gain = info_gain
            best_attribute = i
    return best_attribute


# 多数表决，当attribut_list为空，标记为数据集中的多数类
def majorityCnt(class_list):
    class_count = {}
    for vote in class_list:  # 存储class_list每个类标签出现的频率
        if vote not in class_count.keys():
            class_count[vote] = 0
        class_count[vote] += 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)  # 根据第一个域的值对字典迭代排序
    return sorted_class_count[0][0]  # 返回出现最多的分类


# 创建决策树
# data_set 数据集，每条记录的最后一项为该实例的类别
# labels 为了增加结果的可解释性，设定标签
def createTree(data_set, labels):
    class_list = [example[-1] for example in data_set]  #获取数据集中的最后一列的类标签，存入classList列表
    # 结束条件一：分区的所有元组都属于同一个类
    if class_list.count(class_list[0]) == len(class_list):  # 在calsslist中和list[0]相同的值的个数和list中值的总数是否一致，即list中是否全为list[0]
        return class_list[0]
    # 结束条件二：没有剩余属性可以用来划分元组，只有类标签列，多数表决
    if len(data_set[0]) == 1:
        return majorityCnt(class_list)
    best_attribute = Attribute_selection(data_set)  # 选择最好的属性
    best_label = labels[best_attribute]  # 将对应标签添加到树
    my_tree = {best_label: {}}
    sub_lables = labels[:]  # 复制类标签
    del (sub_lables[best_attribute])  # 删除分裂属性
    feature_values = [example[best_attribute] for example in data_set] #将最好的属性所在列用集合取唯一值
    unique_values = set(feature_values)
    for value in unique_values:     # 对属性的每个取值作为分枝递归建立决策树
        my_tree[best_label][value] = createTree(splitData(data_set, best_attribute, value), sub_lables)
    return my_tree


# 使用决策树进行分类
# 参数说明：决策树， 标签， 待分类数据
def classify(input_tree, feature_labels, test_vec):
    first_str = input_tree.keys()[0]  # 3.x firstStr=list(inputTree.keys())[0] 找到树的根节点
    second_dict = input_tree[first_str]  # 从树中得到分支
    feature_index = feature_labels.index(first_str)
    for key in second_dict.keys():  # #测试节点是否为字典类型
        if test_vec[feature_index] == key:
            if type(second_dict[key]).__name__ == 'dict':
                classLabel = classify(second_dict[key], feature_labels, test_vec)
            # 达到叶子节点，返回递归调用，得到分类 ，如果是叶子节点，则返回节点取值
            else:
                classLabel = second_dict[key]
    return classLabel

#以下为tree_test.py
# coding:utf-8
# 读取数据并处理数据
import trees
import imp

imp.reload(trees)
fr = open('/home/wangyuhang/数据挖掘/决策树/lenses.data')
lenses = []  # 训练集
for lines in fr.readlines():
    line = lines.strip().split('  ')
    intline = [int(item) for item in line]
    lenses.append(intline)
D_set=lenses[18:24]   # 取后6个作为测试集
lenses = lenses[:18]  # 取前18个作为训练集
print '训练集:\n', lenses
lenses_labels = ['age', 'prescript', 'astigmatic', 'tear_rate']
lenses_tree = trees.createTree(lenses, lenses_labels)
print '决策树：\n', lenses_tree
# 测试分类
print '测试集：\n', D_set
# 测试分类器
def test_tree(D_set):
    trueclass = 0
    for row in range(5):
        if trees.classify(lenses_tree, lenses_labels,
                          [D_set[row][0], D_set[row][1], D_set[row][2], D_set[row][3]]) == D_set[row][4]:
            trueclass += 1
        print D_set[row], trees.classify(lenses_tree, lenses_labels,
                                         [D_set[row][0], D_set[row][1], D_set[row][2], lenses[row][3]])
    correct_rate = trueclass / 5.0  # 分类的正确率
    return correct_rate


print '正确率为：\n', test_tree(D_set)
print '错误率为：\n', 1 - test_tree(D_set)

五、实验结果

六、问题分析
问题1：读取数据出错，每次都执行了多数表决
原因：分割数据时由于分隔符无法读取，不能使用split('\t')
解决方法：改为使用line=lines.strip().split(' ')

问题2：决策树嵌套很少，无叶子节点
原因：选择最优分裂属性函数中计算属性的信息熵出错
解决方法：infoA(D)=∑(Dj/D)*info(Dj) A中分区的概率乘以它的信息熵
代码修改为：
prob = len(sub_data) / float(len(data_set))
new_entropy += prob * calculate_info(sub_data)

问题3：在测试中使用决策树分类时报错 ValueError: 'tear_rate' is not in list
原因：在构建决策树时将原始标签删除
解决方法1：先复制当前特征标签列表，防止改变原始列表的内容,在之后递归时使用复制的标签列表
解决方法2：调用分类函数时使用另一个类标签列表label2

问题4：分类时报错：local variable 'classLabel' referenced before assignment
原因1：找了多种方法都没有用，后来发现是数据集的问题，使用readlines()读入是字符串，分割后还是字符串，必须转换成整型，原因？？？
解决方法：使用列表生成式intline=[int(item) for item in line]将每个属性转换为Int
原因2：在分数据时又遇上这个错误，发现原来将 bestFeature 初始化为 -1 ，当给定的数据集只包含有1个特征时 infoGain == bestInfoGain，导致 bestFeature 不会被更新，直接返回 -1；在调用函数createTree中，bestFeat == -1 时 会将dataSet 最后1列，即样本的分类作为属性的值返回：
解决方法：在只有最后1个特征时，直接返回 0，而不是默认的 -1

七：分类器评估

准确率：

Accuracy=（TP+TN）/ALL = 0.8

错误率：

Error_rate=1-accuracy(M)=0.2

若对 no contact lenses类感兴趣

精度：

precision=正确分类的正元组/预测出的正元组=0.75

召回率：

Recall=TP/P=正确分类的正元组/实际正元组=1