机器学习与知识发现实验—酒分类

《机器学习与知识发现实验—酒分类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Usingchemicalanalysisdeterminetheoriginofwines赵启杰SC11011063摘要采用较简单的决策树归纳算法根据红酒的成分对其进行分类，划分度量采用的是Gini指标，所有数据都看做是连续属性，进行二元划分，最后得到的是一棵二叉决策树。最后采用二折交叉验证的方式，进行评估，得到的分类准确度在85%左右。为了简单，没有考虑噪声的干扰，没有考虑模型的过分拟合问题，没有考虑泛化误差。相关工作算法的实现参考《数据挖掘导论》算法4.1的决策树归纳算法的框架。TreeGr

2、owth(E,F)ifStopping_cond(E,F)=truethenleaf=creatNode()leaf.label=Classify(E)returnleafelseroot=creatNode()root.test_cond=find_best_split(E,F)令V={v

3、v是root.test_cond的一个可能的输出}for每个vinVdoEv={e

4、root.test_cond(e)=v并且einE}child=TreeGrowth(Ev,F)将child作为root的派

5、生节点添加到树中，并将边(root-->child)标记为vendforendifruturnroot其中E是训练记录集，F是属性集。涉及到的主要类：Tuple：数据集的一条记录，这里把记录的所有属性都当成浮点型数据处理。TupleTable：整个数据集。其中iClassNum代表总共的类数，iTableLen代表记录数，iTupleSize代表记录的属性数，rgStrClasses保存所有的类，rgStrAttribute保存所有的属性，rgTuples保存所有的记录。DecisionNode：

6、决策树中的一个节点。TestCond：决策树非叶子节点中保存的测试条件。涉及到的主要方法：TupleTable：：InitTableFromFile从数据文件获取数据，初始化数据集。数据文件格式需要做适当修改。TupleTable：：TupleIndexs从数据集导出一个数据集的索引，即一个由Tuple指针组成的数组，该数组中的每一个元素指向TupleTable中的一个Tuple。可以通过比较Tuple的值对索引中的指针进行排序。Stopping_cond通过检查是否所有的记录都属于同一个类，或者

7、都具有相同的属性值，决定是否终止决策树的增长，或者检查记录数是否小于某一个最小阈值（_BOUNDARY_RECORD_）。通过调整阈值可以在一定范围内改变分类器的准确率。CreateNode为决策树建立新节点，决策树的节点或者是一个测试条件，即一个testcond对象，或者是一个类标号。Find_best_split确定应当选择哪个属性作为划分训练记录的测试条件。使用的不纯性度量是Gini指标。首先对索引按第j个属性进行排序，如果索引中第i个记录和第i+1个记录不是同一个类，则将第i个记录和第i+

8、1个记录的属性j的中间值作为划分点，计算Gini指标。循环计算所有可能的Gini指标，找出其中的最小值，保存属性名和属性值，作为当前最优测试条件。GetGini获取某个训练数据子集的Gini指标。其中p(i

9、t)表示节点t中属于类i的记录所占比例。Classify为节点确定类标号，对于节点t，统计分配到该节点的所有记录中类i的记录数0

10、递归创建决策树。创建决策时之前需要对作为输入的数据集文件做适当修改：属性个数n属性名1...属性名n类个数m类名1...类名m记录数k类名，属性1，...，属性n...类名，属性1，...，属性n由于分类器的性能评估并不是实验的主要内容，因此这里只是简单的做了一下二折交叉验证，将数据集随机分成两个子集，其中一个作为训练集，另一个作为检验集，然后互换集合再做一次，最后得到的准确率在85%左右。优劣分析：1〉决策树归纳是一种构建分类模型的非参数方法。换言之，它不要求任何先验假设，不假定类和其他属性服从

11、一定的概率分布（如Logistic回归）；2〉找到最优决策树是NP完全问题，许多决策树算法都采取启发式方法指导对假设空间的搜索，如采用贪心的、自顶向下的递归划分策略建立决策树；3〉不需要昂贵的计算代价，即使训练集非常大，也可以快速建立模型。此外，决策树一旦建立，未知样本分类也非常快，最坏情况下的时间复杂度为O(w)，其中w是树的最大深度；4〉决策树相对容易解释，特别是小型决策树；在很多简单的数据集上，决策树的准确率也可以与其他分类算法想媲美；5〉决策树算法对于噪声的干扰具有相当好的