都说万事开头难，可一旦开头，就是全新的状态，就有可能收获自己未曾预料到的成果。记录是为了更好的监督、理解和推进，学习过程中用到的数据集和代码都将上传到github
机器学习系列博客：（1） 机器学习之K-近邻算法
1. 什么是决策树
用阐述性的语言来说，决策树通过对给出的学习样本进行学习，自行产生出一个树结构，每个叶节点都对应一簇数据，这一簇数据导向的结果是相同的；之后，将该树结构抽离出来，对所需要进行分类并预测结果的数据进行分类，并预测其结果。
（1）决策树在本质上就是一组嵌套的if-else判断规则，看下图：
a. 首先根据判断是不是www.A.email发来的邮件判断是否为垃圾邮件
b. 再根据是否含涨工资信息来判断是不是要立马查看或下班再看
（2）决策树能做什么
有了上图的决策树后，下次再收到邮件，就可以将邮件交给这棵决策树，立马知道该如何对邮件进行处理
2. 温习几个重要概念
在创建决策树之前，先来温习下面的几个重要的概念
（1）自信息
对于自信息的理解是学习决策树的基础之基础，下面的内容务必理解！
以下内容摘抄自https://blog.csdn.net/xuejianbest/article/details/80391191，感谢博主的分享，很直接明了的解释了信息公式：
有时候我们会说“信息量好大”，但是究竟怎么比较信息量的大小呢？我们需要量化信息量的值。
举个例子，你扔一个骰子，我不知道点数，你知道并告诉我。
你说"点数不大于6"，这句话的信息量应该等于0，因为我猜都猜的到，点数不大于6的概率是1，这句话没有带给我任何信息；
你说 "点数不大于5"，这句话的信息量应该大于0，但是并不大，因为我猜能差不多猜的到，点数不大于5的概率是5/6 ，这句话带给我的信息较少；
你说 "点数为3"，这句话的信息量应该大于0，而且应比上面那句话信息量大，因为"点数为3"包含了"点数不大于5"的信息在里面，点数为3的概率是1/6，这句话带给我的信息较多。
所以我们可以做出总结：信息量的值和事件发生的概率有关系，概念越小信息量越大，我们考虑用概率的相反数来量化信息量，但是根据直觉，信息量不应该为负数，所以我们考虑用概率的倒数来量化信息量，设事件A发生的概念为p，则事件A发生了带给我们的信息量为1/p
考虑来考虑去，信息量还应该有一个性质，就是可加性
再举个例子：
情况一： 你扔了第一个骰子，告诉我"点数是3"；
你扔了第二个骰子，告诉我"点数是1"。
那你两次告诉我的总信息量应该是第一次告诉我的信息量加第二次告诉我的信息量的和。
情况二： 你扔了第一个骰子，什么都没说；
你扔了第二个骰子，告诉我第一次点数是3，第二次点数是1。
根据直觉，这句话的信息量应该和情况一中两句话的信息量的和一样。
根据我们上面信息量的量化公式算一下：
"点数是3"的概率为1/6，信息量为6，"点数是1"的概率为1/6 ，信息量为6，两句话信息量的和为12
第一次"点数是3"，第二次"点数是1"的概率为(1/6)*(1/6)=1/36，信息量为36
算出来的信息量并不相等！所以我们要修正我们信息量的量化公式，我们用函数I来修正原来信息量等于概率的倒数的量化公式：设事件A发生的概率为p，则事件A发生了带给我们的信息量为I(1/p)。
两次独立事件A，B发生的概率分别为p1和p2，A和B同时发生概率为p1*p2，如上面所讨论，信息量的性质要求：
看出来没，函数I的运算规则正好和对数的运算规则相同：
所以我们的函数可以用对数函数，最终我们给出信息量的量化公式：设事件A发生的概率为p，则事件A发生了带给我们的信息量为logb(1/p)，式中的b是对数的底，b的取值决定信息量的单位，如b取2信息量的单位是bit，b取自然常数e信息量的单位是nat，容易计算1 nat=log2e≈1.443 bit1 nat=log2e≈1.443 bit
（2）期望
概率论中描述一个随机事件中的随机变量的平均值的大小可以用数学期望这个概念，数学期望的定义是实验中可能的结果的概率乘以其结果的总和
举个简单的例子：
小时候玩的自动吐硬币的赌博机，硬币Y遵从以下概率分布，吐0个币的概率为0.7，吐10个币的概率为0.29，吐20个币的概率为0.01，那么Y的期望值为：
E[Y] = 0*0.7 + 10 * 0.29 + 20 * 0.01
（3）熵
熵很难理解，拿书本上的一句话说，它们自从诞生的那一天起，就注定令世人十分费解。但是只要记住熵定义为信息的期望值，理解信息和期望后，使用熵也就不费解了
（4）信息增量
Gain(S,Sv) = H(S)- (|Sv|/|S|)H(Sv)
信息增益 = 经验熵 - 条件熵
用通俗的话理解就是，当加入了一个判断条件之后，我需要判定一个结论所需要的信息熵相比之前就有所减少了，这减少的量就是信息增益
3. 决策树构造实现
3.1 需求
比如在海洋中有5种生物，我们根据（不浮出水面是否可以生存，是否有脚蹼（鱼尾中间的薄膜））两个分类特征来判断该生物是否属于鱼类来构建决策树
看下表：
| 浮出水面是否可以生存 | 是否有脚蹼 | 属于鱼类 | |
| 1 | 否 | 是 | 是 |
| 2 | 否 | 是 | 是 |
| 3 | 否 | 否 | 否 |
| 4 | 是 | 是 | 否 |
| 5 | 是 | 是 | 否 |
3.2 构思
（1）伪代码的创建
前面说决策树在本质上就是一组嵌套的if-else判断规则树，那么我有个疑惑：面对这么多规则，我该先选哪个规则作为第一规则，再选哪个作为第二规则呢？规则选择次序不同，对决策树的构造会有什么影响？
这两个问题就涉及到了自信息的概念，一个规则给我们提供的信息量究竟有多大，信息量越大我们肯定能最快的得到想要的答案，从而决策树的高度也会最大程度的小
由此，我们首先需要判断数据集上的哪个规则在划分数据分类时起决定性作用，然后再对数据集进行划分，创建分支的伪代码如下：
if so return 类标签 else 寻找到分类数据种的最好特征 划分数据集 创建分支节点 for 每个划分的子集 递归 return 分支节点
（2）找到数据集中的决定性特征
我们可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择
比如，先计算浮出水面是否可以生存的信息增量gain(A)，再计算是否有脚蹼的信息增量gain(B)，比较gain(A)和gain(B)，哪个大就以哪个作为决定性特征
3.3 实现
（1）计算数据集熵
熵为自信息的期望，参照上面的定义
def calc_entropy(dataset): """ 计算熵，dataset为list """ rows = len(dataset) label_count = {} entropy = 0 for i in range(rows): label = dataset[i][-1] label_count[label] = label_count.get(label,0) + 1 for key,val in label_count.items(): p = val / rows l = log(p,2) * (-1) entropy += p*l return entropy
（2）选取最佳特征
根据最大信息增量，选取最佳特征，遍历每个特征，计算其熵，然后与其原始数据集熵的差值来决定最大信息增量，最大信息增量时对应的特征极为最佳特征
def split_dataset_by_feature_value(dataset, feature_index, value): """ 根据给定特征及其对应的特征值拆分数据集 dataset：原始数据集 feature_index：特征索引，也就是dataset的列索引 value：feature_index对应的特征值 """ new_dataset = [] for row in dataset: if row[feature_index] == value: row_list = row[:feature_index] row_list.extend(row[feature_index+1:]) new_dataset.append(row_list) return new_dataset def choose_best_feature(dataset): """ 根据信息增量，选择最佳分类特征 """ base_entropy = calc_entropy(dataset) feature_num = len(dataset[0]) - 1 #特征个数 max_info_gain = 0 #信息增量 best_feature = -1 #最佳特征 for feature_index in range(feature_num): feature_value_list = [row[feature_index] for row in dataset] #特征值列表 feature_value_set = set(feature_value_list) #特征值集合，确保没有重复值 new_entropy_sum = 0 #根据特征分类后的熵和 info_gain = 0 for value in feature_value_set: sub_dataset = split_dataset_by_feature_value(dataset, feature_index, value) #根据特定特征及其特征值得到子数据集 prob = len(sub_dataset) / len(dataset) new_entropy = calc_entropy(sub_dataset) new_entropy_sum += prob * new_entropy info_gain = base_entropy - new_entropy_sum #计算信息增量 if info_gain > max_info_gain: max_info_gain = info_gain best_feature = feature_index return best_feature
（3）构建决策树
参照上面的伪代码
def max_count(classlist): """ 返回出现次数最多的类别 """ dic = {} for i in classlist: dic[classlist[i]] = dic.get(classlist[i],0)+1 sorted_list = sorted(dic.items(), key=lambda x: x[1], reserver=True) print('sorted_list:',sorted_list) return sorted_list[0][0] def create_policy_tree(dataset,lables): """ 构建决策树 """ classlist = [example[-1] for example in dataset] if classlist.count(classlist[0]) == len(classlist): #类别完全相同停止继续分类 return classlist[0] if len(dataset[0]) == 1: #遍历完所有特征时返回出现次数最多的类别 return max_count(classlist) best_feature = choose_best_feature(dataset) best_feature_lable = lables[best_feature] tree = {best_feature_lable:{}} del lables[best_feature] feature_value_list = [row[best_feature] for row in dataset] #特征值列表 feature_value_set = set(feature_value_list) #特征值集合，确保没有重复值 for value in feature_value_set: sub_dataset = split_dataset_by_feature_value(dataset, best_feature, value) #根据特定特征及其特征值得到子数据集 tree[best_feature_lable][value] = create_policy_tree(sub_dataset,lables) return tree
注意：递归的条件就是不停的选择最佳特征并拆分数据集，递归基线条件有两个：a. 类别完全相同停止继续分类;b. 遍历完所有特征时返回出现次数最多的类别
（4）测试
if __name__ == '__main__': dataset = [[0,1,1],[0,1,1],[0,0,0],[1,1,0],[1,1,0]] lables = ['no surfacing','flippers'] print("policy tree:",create_policy_tree(dataset,lables))
输出：
用matplotlib显示如下：
4. 总结
决策树分类器就像带有终止块的流程图，终止块表示分类结果。开始处理数据时，首先需要测量集合数据的不一致性，也就是熵，然后寻找最优方案划分数据集，直到数据集中的所有数据属于同一分类。
k~近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征的数据
缺点：可能会产生过度匹配问题