Using chemical analysis determine the origin of wines 赵启杰 SC11011063
摘要
采用较简单的决策树归纳算法根据红酒的成分对其进行分类，划分度量采用的是Gini 指标，所有数据都看做是连续属性，进行二元划分，最后得到的是一棵二叉决策树。

最后采用二折交叉验证的方式，进行评估，得到的分类准确度在85%左右。

为了简单，没有考虑噪声的干扰，没有考虑模型的过分拟合问题，没有考虑泛化误差。

相关工作
算法的实现参考《数据挖掘导论》算法4.1的决策树归纳算法的框架。

TreeGrowth(E,F)
if Stopping_cond(E,F)=true then
leaf=creatNode()
bel=Classify(E)
return leaf
else
root=creatNode()
root.test_cond=find_best_split(E, F)
令V={v|v是root.test_cond的一个可能的输出}
for 每个v in V do
E v ={e|root.test_cond(e)=v 并且e in E}
child=TreeGrowth(E v, F)
将child 作为root的派生节点添加到树中，并将边(root-->child)标记为v end for
end if
ruturn root
其中E是训练记录集，F是属性集。

涉及到的主要类：
Tuple：数据集的一条记录，这里把记录的所有属性都当成浮点型数据处理。

TupleTable：整个数据集。

其中iClassNum代表总共的类数，iTableLen代表记录数，iTupleSize代表记录的属性数，rgStrClasses保存所有的类，rgStrAttribute保存所有的属性，rgTuples保存所有的记录。

DecisionNode：决策树中的一个节点。

TestCond：决策树非叶子节点中保存的测试条件。

涉及到的主要方法：
TupleTable ：：InitTableFromFile
从数据文件获取数据，初始化数据集。

数据文件格式需要做适当修改。

TupleTable ：：TupleIndexs
从数据集导出一个数据集的索引，即一个由Tuple 指针组成的数组，该数组中的每一个元素指向TupleTable 中的一个Tuple 。

可以通过比较Tuple 的值对索引中的指针进行排序。

Stopping_cond
通过检查是否所有的记录都属于同一个类，或者都具有相同的属性值，决定是否终止决策树的增长，或者检查记录数是否小于某一个最小阈值（_BOUNDARY_RECORD_）。

通过调整阈值可以在一定范围内改变分类器的准确率。

CreateNode
为决策树建立新节点，决策树的节点或者是一个测试条件，即一个testcond 对象，或者是一个类标号。

Find_best_split
确定应当选择哪个属性作为划分训练记录的测试条件。

使用的不纯性度量是Gini 指标。

首先对索引按第j 个属性进行排序，如果索引中第i 个记录和第i+1个记录不是同一个类，则将第i 个记录和第i+1个记录的属性j 的中间值作为划分点，计算Gini 指标。

循环计算所有可能的Gini 指标，找出其中的最小值，保存属性名和属性值，作为当前最优测试条件。

GetGini
获取某个训练数据子集的Gini 指标。

∑-=-=1
02)]|([1)(c i t i p t Gini
其中p(i|t)表示节点t 中属于类i 的记录所占比例。

Classify
为节点确定类标号，对于节点t ，统计分配到该节点的所有记录中类i 的记录数0<i<iClassNum ，则节点的类标号为max{i}。

Sort_record
对记录子集的索引按照某个属性从小到大进行排序，为了简单，使用了冒泡。

TreeGrowth
递归创建决策树。

创建决策时之前需要对作为输入的数据集文件做适当修改：
属性个数n
属性名1
.
.
.
属性名n
类个数m
类名1
.
.
.类名m
记录数k
类名，属性1，...，属性n
.
.
.
类名，属性1，...，属性n
由于分类器的性能评估并不是实验的主要内容，因此这里只是简单的做了一下二折交叉验证，将数据集随机分成两个子集，其中一个作为训练集，另一个作为检验集，然后互换集合再做一次，最后得到的准确率在85%左右。

优劣分析：
1〉决策树归纳是一种构建分类模型的非参数方法。

换言之，它不要求任何先验假设，不假定类和其他属性服从一定的概率分布（如Logistic回归）；
2〉找到最优决策树是NP完全问题，许多决策树算法都采取启发式方法指导对假设空间的搜索，如采用贪心的、自顶向下的递归划分策略建立决策树；
3〉不需要昂贵的计算代价，即使训练集非常大，也可以快速建立模型。

此外，决策树一旦建立，未知样本分类也非常快，最坏情况下的时间复杂度为O(w)，其中w是树的最大深度；
4〉决策树相对容易解释，特别是小型决策树；在很多简单的数据集上，决策树的准确率也可以与其他分类算法想媲美；
5〉决策树算法对于噪声的干扰具有相当好的鲁棒性，采用避免过分拟合的方法之后尤其如此；
6〉冗余属性不会对决策树的准确率造成不利影响。

如果一个属性在数据集中与另一个属性是强相关的，则该属性是冗余的。

在两个冗余属性中，如果已经选择其中一个作为用于划分的属性，则另一个属性将被忽略；另一方面，如果数据集中含有很多与目标变量不相关的属性，则某些属性可能在树的构造过程中偶然被选中，导致决策树过于庞大。

在预处理阶段，特征选择技术能够帮助找出并删除不相关属性，以帮助提高决策树的准确率；
7〉数据碎片（data fragmentation）问题。

由于大多数的决策树算法采用自顶向下的递归划分方法。

因此沿着树向下，记录会越来越少，在叶子结点记录数量可能太少，以致对于叶子结点代表的类的判决不具有统计显著性。

解决这一问题的方法是当样本数小于某个特定阀值时停止分裂；
8〉由于大多数决策树算法采用分治划分策略，因此属性空间的不同部分可能使用相同的测试条件，从而导致子树在决策书中重复出现多次，这使得决策树过于复杂，并且可能更
难于解释；
9〉决策树是学习离散值函数的典型代表，然而，它不能很好的推广到某些特定的布尔问题。

如对于奇偶函数来说，当奇数/偶数个布尔属性为真时其值为0/1，对这样的函数准确建模需要一棵具有2的d次方个节点的满决策树（d为布尔属性的个数）。

10〉对于测试条件只涉及一个属性的决策树，可以将决策树的成长过程看成划分属性空间为不相交的区域的过程，直到每个区域都只包含同一记录，两个不同类的相邻区域之间的边界称作决策边界（Decision Boundary）。

由于测试属性只涉及单个属性，因此决策边界是平行于坐标轴的直线，这就限制了决策树对连续属性之间复杂关系建模的表达能力。

斜决策树（Oblique Decision Tree）是克服以上局限的方法之一，它允许测试条件涉及多个属性（如x+y<1），当然，这一技术在赋予决策树更强表达能力的同时，为给定结点找出最佳的测试条件的计算复杂度也是昂贵的。

另一种将属性空间划分为非矩形区域的方法是构造归纳（Constructive Induction），即创建复合属性用于代表已有属性的算术/逻辑组合，该方法不需要昂贵的计算花费；
11〉研究表明大部分不纯性度量方法的结果是指一致的，因此不纯性度量方法的选择对决策树算法的性能影响很小。

树剪枝对最终决策树的影响往往比不纯性度量的选择影响更大；
12)决策树归纳最终可能并不能获得一个最优的分类器，但是至少可以获得一个次优的分类器。

参考文献：
Pang-Ning Tan, Michael Steinbach, Vipin Kumar. 数据挖掘导论（完整版）[M].范明, 范宏建等译. 人民邮电出版社. 2011.。