基于决策树的分类方法研究

数据挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取具有潜在应用价值的知识或模式。模式按其作用可分为两类：描述型模式和预测型模式。分类模式是一种重要的预测型模式。挖掘分类模式的方法有多种，如决策树方法、贝叶斯网络、遗传算法、基于关联的分类方法、粗糙集和k-最临近方法等等。 本文研究如何用决策树方法进行分类模式挖掘。文中详细阐述了几种极具代表性的决策树算法：包括使用信息熵原理分割样本集的ID3算法；可以处理连续属性和属性值空缺样本的C4.5算法；依据GINI系数寻找最佳分割并生成二叉决策树的CART算法；将树剪枝融入到建树过程中的PUBLIC算法；在决策树生成过程中加入人工智能和人为干预的基于人机交互的决策树生成方法；以及突破主存容量限制，具有良好的伸缩性和并行性的SLIQ和SPRINT算法。对这些算法的特点作了详细的分析和比较，指出了它们各自的优势和不足。文中对分布式环境下的决策树分类方法进行了描述，提出了分布式ID3算法。该算法在传统的ID3算法的基础上引进了新的数据结构：属性按类别分布表，使得算法具有可伸缩性和并行性。最后着重介绍了作者独立完成的一个决策树分类器。它使用的核心算法为可伸缩的ID3算法，分类器使用Microsoft Visual C++6.0开发。实验结果表明作者开发的分类器可以有效地生成决策树，建树时间随样本集个数呈线性增长，具有可伸缩性。