分类算法.doc

分类算法摘要: 分类算法是数据挖掘中的最重要的技术之一。通过对当前提出的最新的具有代表性的分类算法进行分析和比较,总结每类算法的各方面特性,从而便于研究者对已有的算法进行改进,提出具有更好性能的新的分类算法,同时方便使用者在应用时对算法的选择和使用。关键词: 分类算法决策树基于规则贝叶斯人工神经网络支持向量机分类是挖掘数据的一个重要技术,是数据挖掘中最有应用价值的技术之一,其应用遍及社会各个领域。分类任务就是通过学****得到一个目标函数( 通常也称作分类模型, 即分类器), 把每个属性集映射到一个预先定义的类标号。分类和回归都可以用于预测。和回归方法不同的是,分类的类标号是离散属性,而预测建模的回归的目标属性是连续的。构造分类器的过程一般分为训练和测试两个阶段。在构造模型之前,要求将数据集随机地分为训练数据集和测试数据集。在训练阶段, 分析训练数据集的属性, 为每个属性产生一个对相应数据集的属性描述或模型。在测试阶段,利用属性描述或模型对测试数据集进行分类, 测试其分类准确度。一般来说,测试阶段的代价远远低于训练阶段。为了提高分类的准确性、有效性和可伸缩性,在进行分类之前,通常要对数据进行预处理,包括: (1) 数据清理。其目的是消除或减少数据噪声,处理空缺值。(2) 相关性分析。由于数据集中的许多属性可能与分类任务不相关, 若包含这些属性将减慢和可能误导学****过程。相关性分析的目的就是删除这些不相关或冗余的属性。(3) 数据变换。数据可以概化到较高层概念。比如, 连续值属性“收入”的数值可以概化为离散值:低,中,高。又比如, 标称值属性“市”可概化到高层概念“省”。此外, 数据也可以规范化,, 规范化将给定属性的值按比例缩放,落入较小的区间,比如[0,1] 等。分类模型的构造方法有决策树类、基于规则类、最近邻类、贝叶斯类、人工神经网络类等。 1 决策树分类算法 决策树基本概念决策树是一种由结点和有向边组成的层次结构,树中包含三种结点;根结点、内部结点和叶结点( 终结点)。它采用自顶向下的递归方式, 在根结点使用属性将训练数据集区分开, 在内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,树的每个叶结点都赋予一个类标号,即在叶结点得到结论。决策树是实例的分类器。从根到叶结点的一条路径就对应着一条规则,整个决策树就对应着一组析取表达式规则。可将实例分到多个分类(≥ 2) 并以析取范式(DNF) 形式重写为规则。这种具有预测功能的系统叫决策树分类器。 常用的决策树算法决策树分类算法从提出以来,出现了很多算法,比较常用的有: 1986 年 Quinlan 提出了著名的 ID3 算法。 ID3 算法体现了决策树分类的优点: 算法的理论清晰, 方法简单, 学****能力较强。其缺点是: 只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变, 并且在测试属性选择时,它倾向于选择取值较多的属性。在 ID3 算法的基础上, 1993 年 Quinlan 又自己提出了改进算法— C4. 5 算法。为了适应处理大规模数据集的需要, 后来又提出了若干改进的算法, 其中 SLIQ(su-pervised learning in quest) 和 SPRINT (scalable parallelizable induction