决策树
一、问题描述
使用决策树预测患者需要佩戴的眼镜类型，根据数据集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
