人工智能技术: 机器学习之决策树大作业
以西瓜集 2.0 为建模数据，采用交叉验证方法进行数据训练集和验证集的划分，实现决策树 “预剪枝”算法，要求:尽可能充分利用有限的西瓜集 2.0 数据所提供信息，建立泛化能力强的 决策树模型。（2）提交报告内包含交叉验证部分和决策树建模部分核心程序截图；(3) 对建 模结果要有分析部分。
理论定义
优秀的决策树：
优秀的决策树不仅对数据具有良好的拟合效果，而且对未知的数据具有良好的泛化能力，优秀的决策树具有以下优点：1.深度小；2.叶节点少；3深度小并且叶节点少.
剪枝的目的：处理决策树的过拟合问题。
预剪枝：生成过程中，对每个结点划分前进行估计，若当前结点的划分不能提升 [泛化能力] ，则停止划分，记当前结点为叶结点。
预剪枝的方法：
限定决策树的深度；设定一个阈值；设置某个指标，比较节点划分前后的泛化能力
交叉验证：
如果给定样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分为3部分，分为训练集、验证集和测试集。
简单交叉验证：随机将数据划分为两部分，训练集和测试集。
数据处理
整个西瓜集2.0使用ID3算法生成的决策树：
简单交叉验证：随机将数据划分为两部分，训练集和测试集，各50%。
训练集
测试集
训练集ID3算法生成的决策树：
由两次划分可知：信息增益无法有效划分出第一、第二节点的最优属性，因此重新分组。
重新分组：
训练集
测试集
训练集ID3算法生成的决策树：
进行预剪枝：
这颗树深度从0开始一共4层，现在要将深度限定为2层。
因为浊响->稍蜷中4个瓜3个坏，所以稍蜷定义为坏瓜。
根蒂->硬挺只有一个瓜，且是坏瓜，所以硬挺定义为坏瓜。
预剪枝决策树：
自检验：
正确率88.9%
对测试集检验：
正确率25%
很明显，这个分组依然不理想，将比例调整，训练集70% 和测试集30%。
重新分组：
训练集
测试集
训练集ID3算法生成的决策树：
深度已经是两层的了，没必要再剪枝处理。
自检验：
正确率100%
对测试集检验：
正确率60%
仅9号和14号交换所在集合 的训练集ID3算法决策树：
因为ID3算法生成的决策树深度就已经是两层的了，自检验正确率必为100%。
对测试集检验：
正确率80%
接着又将5号和15号交换：
因为稍凹->浊响中有3个瓜（2好、1坏），所以稍凹->浊响视为好瓜，并预剪枝。
自检验：
正确率91.7%
对测试集检验：
正确率100%
总结
程序截图：代码为ID3算法，资料参考的第二个链接
程序主要实现ID3决策树算法，通过简单交叉验证将数据分为训练集和测试集。
刚开始使用各50% 随机分组，通过预剪枝后，效果非常不理想。具体表现为：1.无法区分分支属性优先级好坏，太多个信息增益相同的属性了；2.泛化能力太差；
之后使用训练集70% ，测试集30%的分组法，随机分组计算ID3决策树，再通过交换训练集和测试集某些属性，提高计算出来的决策树的泛化能力。
交换的具体方法为：
- 找到测试集中预测失败的组号；
- 出现这种问题的主要原因是训练集的“多样性”略低。
以9号和14号交换为例：9号出现判断失误是由于在纹理为稍糊下选择的分支属性有误，在原训练集中只有7号好瓜是稍糊+乌黑，所以ID3算法会认为稍糊+乌黑是好瓜，我们需要交换一个稍糊+乌黑是坏瓜的瓜，让算法重新找一个更好分支属性。在原训练集中稍糊的瓜有：7号、13号、14号。排除7号（因为我们要让稍糊+乌黑是好瓜和坏瓜同时存在）在13和14号中选择交换的对象。如果选择与13号交换，则坏瓜中又只剩下一个敲声为浊响的瓜，这属于是挖东墙补西墙的感觉，而交换14号不会使坏瓜中只有一个单一情况的瓜。最终9号瓜与14号交换，使得测试集检验正确率有效提高20% 。
接着5号和15号交换计算决策树并预剪枝得到最终决策树：
自检验正确率91.7% 测试集检验正确率100%
相较于仅交换9号和14号的决策树：
自检验正确率100% 测试集检验正确率80%
在数据上看确实有提高，泛化能力更强，但是事实上都是仅15号瓜判断失误，只是将15号瓜从测试集转移到训练集。非常神奇的是这两的决策树分支属性天差地别，它两对于现有数据的预测又比较优秀。
资料参考
[1] 机器学习-交叉验证 : python数据集划分_葛琪琪的博客-CSDN博客_python交叉验证划分西瓜集
[2]
https://blog.csdn.net/myec_lipse/article/details/127271973?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167033413516800186581790%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167033413516800186581790&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-127271973-null-null.142^v67^control,201^v4^add_ask,213^v2^t3_esquery_v3&utm_term=%E5%9C%A8%E8%A5%BF%E7%93%9C%E6%95%B0%E6%8D%AE%E9%9B%86%E4%B8%8A%E7%94%A8Python%E5%AE%9E%E7%8E%B0ID3%E5%86%B3%E7%AD%96%E6%A0%91%E7%AE%97%E6%B3%95%E5%AE%8C%E6%95%B4%E4%BB%A3%E7%A0%81&spm=1018.2226.3001.4187
