分类算法综述

1、庖”TAWJAN UNIVEBSm OF TECHNO1OOY数据挖掘数据挖掘分类算法综述专业：计算机科学与技术专业学 号：S20100451 姓 名：张靖 指导教师：陈俊杰时 间：2011年08月21日数据挖掘分类算法综述数据挖掘出现于20世纪80年代后期，是数据库研究中最有应用价值的新领 域之一。它最早是以从数据中发现知识 （KDD，Knowledge Discovery in Database） 研究起步，所谓的数据挖掘（Data Mining，简称为DM），就从大量的、不完全的、 有噪声的、模糊的、随机的、实际应用的数据中提取隐含在其中的、人们不知道 的但又有用的信息和知识的过程。分类

2、是一种重要的数据挖掘技术。分类的目的是根据数据集的特点构造一个 分类函数或分类模型（也常常称作分类器）。该模型能把未知类别的样本映射到给 定类别中的一种技术。1. 分类的基本步骤数据分类过程主要包含两个步骤：第一步，建立一个描述已知数据集类别或概念的模型。如图1所示，该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可认为是属于一 个确定的数据类别，其类别值是由一个属性描述 （被称为类别属性）。分类学习方 法所使用的数据集称为训练样本集合，因此分类学习又可以称为有指导学习 （learning by example）。它是在已知训练样本类别情况下，通过学习建立相应模型， 而无指导学习

3、则是在训练样本的类别与类别个数均未知的情况下进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公 式形式。例如，给定一个顾客信用信息数据库，通过学习所获得的分类规则可用 于识别顾客是否是具有良好的信用等级或一般的信用等级。分类规则也可用于对今后未知所属类别的数据进行识别判断，同时也可以帮助用户更好的了解数据库 中的内容。分类规则nameageincomeCredit ratingSandy Jones总0lowfairBill lee总0lowexcellentCourtney fox3140highexcellentSusan lake>40medfairClai

4、re phips> 40medfairAndre beau3140highexcellentIf age= “ 31-40 ” and income=high Then credit_rating=excellent图1数据分类过程中的学习建模第二步，利用所获得的模型进行分类操作。首先对模型分类准确率进行估计， 例如使用保持（holdout）方法。如果一个学习所获模型的准确率经测试被认为是可 以接受的，那么就可以使用这一模型对未来数据行或对象（其类别未知）进行分类。例如，在图2中利用学习获得的分类规则（模型）。对已知测试数据进行模型准确率的评估，以及对未知类别的新数据进行分类预测。nam

5、eageincomeCredit ratingSandy Jones<0lowfairBill lee<0lowexcellentCourtney fox3140highexcellentSusan lake>40medfairClaire phips> 40medfairAndre beau3140highexcellent新数据| John Henri p041 high图2数据分类过程中的分类测试分类的具体规则可描述如下：给定一组训练数据的集合T(Training set)，由一 条条的数据库记录(Record)组成的，T的每一条记录包含若干条属性(Attribu

6、te)组 成一个特征向量，用矢量 X =(x1,x2,.,xn)表示，其中xi ( i < n)对应各非类别 属性，可以有不同的值域，当一属性的值域为连续域时，该属性为连续属性 (Numerical Attribute)，否则为离散属性 (Discrete Attribute)，用c表示类别属性 c=(g,C2,cQ，即数据集有k个不同的类别，那么，T就隐含了一个从矢量X到 类别属性的映射函数H : f (X) > c o分类的目的就是分析输入数据，通过在训练 集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型，采用该种方法(模型)将隐含函数表示出来。构造分类模型的过程

7、一般分为训练和测试两 个阶段，在构造模型之前，要求将数据集随机地分为训练数据集和测试数据集。 在训练阶段，使用训练数据集通过分析有属性描述的数据库元组来构造模型。在测试阶段，使用测试数据集，来评估模型的分类准确率，如果认为模型的准确率 可以接受，就可以用该模型对其它数据元组进分类，一般来说，测试阶段的代价远远低于训练阶段。2. 分类数据的预处理为了提高分类的准确性、有效性和可伸缩性，在进行分类之前通常要对数据 进行预处理，包括以下几方面：(1) 数据清理大多数数据预处理是数据清理的一种形式， 其目的是消除或减少数据噪声和 处理缺失数据的信息。噪声代表属性值中的随机错误。在所有大的数据集中噪声

8、以各种形式和排列方式出现，对噪声数据通常关心的问题如下： 发现重复记录。 查找错误的属性值。在分类数据中寻找错误是大型数据集所面临的一个 问题。一些数据挖掘工具提供了频率值或分类属性的预测能力值的汇 总，可以认为预测能力值接近于 0的属性值可能是错误的。 数据平滑。数据平滑是一个数据清理和数据转换的过程。一些数据平滑 技术努力减少数值属性值的维数。一些分类器，如神经网络，有在分类 过程中用函数完成数据平滑的功能。当数据平滑在分类过程中完成时， 则称为是内部数据平滑。外部数据平滑是在分类以前进行的，舍入和计 算平均值是两种简单的外部数据平滑技术。 当我们想使用不支持数值数 据的分类器，并想保留数

9、值属性值的原始信息时，用平均值平滑就很合 适。在这种情况下，所有的数值属性值被相应的中值所替代。在处理缺失数据时， 因为在训练阶段和分类过程本身， 缺失数据值会导致一 些问题，训练数据中的缺失值会产生不准确的结果， 所以必须进行处理。 分类方 法必须能够处理一个要被分类的元组中的缺失数据， 有许多种处理缺失数据的方 法。 忽略缺失数据。一些数据挖掘算法，包括神经网络和贝叶斯分类器采用 了这种方法。 丢弃含有缺失值的记录。 当记录只有一小部分缺失数据并且我们可以确 定缺失值表示信息丢失时，应用这种方法非常合适。 对于实值数据，用中值代替缺失值。在大多数情况下这是处理数值属性 的一种理想的方法。

10、对缺失数据给定一个假设的值， 这可能需要使用某种方法预测这个值是 什么。 用其它相似样本中的属性值代替某个样本缺失的属性值。（2）相关性分析由于数据集中的许多属性可能与分类任务不相关， 若包含这些属性将减慢和 可能误导学习过程。相关性分析的目的就是删除这些不相关或冗余的属性。（3）数据变换数据可以概化到较高层概念。比如，连续值属性“收入”的数值可以概化为 离散值：低、中、高。此外数据也可以规范化，规范化将给定属性的值按比例缩 放落入较小的区间，比如 0，1等。3. 分类算法数据挖掘有多种经典分类算法， 这些算法基于不同的分类思想， 例如基于距 离的KNN算法、基于归纳的决策树算法、基于统计的贝

11、叶斯算法等等，本文主 要介绍以下几种经典分类算法。3.1 决策树分类在求解分类问题的方法中决策树学习是应用最广的归纳推理算法之一。 它是 一种逼近离散函数值的方法， 分类精度高， 操作简单， 并且对嗓声数据有很好的 健壮性，因而成为实用的并且比较流行的数据挖掘算法。 它的最大优点是， 在学 习过程中不需要使用者了解很多背景知识， 只要训练样本集能够用 “属性值” 的 方式表达出来就能使用决策树学习算法分类。 决策树是最为经典的决策树学习系 统，它采用自顶向下不回溯策略，能保证找到一个简单的树。（1）基本思想 决策树方法是挖掘分类规则的有效方法，通常包括两个部分： 树的生成开始时所有的数据都在根

12、节点， 然后根据设定的标准选择测试属性， 用不 同的测试属性递归进行数据分割。 树的修剪就是除去一些可能是噪音或异常的数据。基于信息熵的ID3算法、C4. 5算法都能有效地生成决策树， 建决策树的关键在于建立分支时对记录字段 不同取值的选择。 选择不同的字段值使划分出来的记录子集不同， 影响决 策树生长的快慢及决策树的结构，从而可寻找到规则信息的优劣。可见，决策树算法的技术难点就是选择一个好的分支取值。 利用好的取值产 生分支可加快决策树的生长， 更重要是产生好结构的决策树， 并可得到较好的规 则信息。相反，若根据一个差的取值产生分支，不但减慢决策树的生长速度，而 且使产生的决策树分支过细、结

13、构差，从而难以发现有用的规则信息。随着训练样本集中样本个数的不断增多 （即样本集规模不断扩大 ），训练样本 集在主存中换进换出就耗费了大量的时间， 严重影响了算法效率。 因此使算法能 有效处理大规模的训练样本集已成为决策树算法研究的一个重要问题， 也是目前 国内对决策树算法研究的热点。（2）实现过程输入：训练数据samples由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。 创建结点 N ； / 根结点 IF samples都在同一个类C THEN返回N作为叶结点，以类 C标记； IF attribute_list为空THEN返回N作为叶结点，标记为 sampl

14、es中最普 通的类； 选择 attribute_list 中具有最高信息增益的属性 test_attribute； 标记结点 N 为 test_attribute； /选取具有最高信息增益的属性作为根结点 FOR each test_attribute 中的已知值ai 由结点 N 长出一个条件为test_attribute=ai 分支； 设 si 是 samples 中 test_attribute =ai 的样本的集合； /一个划分 IF s为空THEN加上一个树叶，标记为samples中最普通的类； ELSE 加上一个由 Generate_decision_trees（i， attribu

15、te_list-test_attribute） 返回的结点；3.2 基于距离的分类1）算法思想基于距离的分类算法的思路比较简单直观。 假定数据库中的每个元组为数值向量，每个类用一个典型数值向量来表示， 则能通过分配每个元组到它最相似的 类来实现分类。给定一个数据库 D=ti, t2,，tn和一组类C=Cl,，Cm。假定每个 元组包括一些数值型的属性值：ti= til , ti2,，tik，每个类也包含数值性属性 值：Cj=Cj1, Cj2,，Cjk，则分类问题是要分配每个 ti到满足如下条件的类 Cj：sim(ti, Cj)>=sim(ti, Ci)，寸Ci C, Ci屯，(2-1)其中

16、，sim(ti, Cj)表示相似性。在实际的计算中，往往用距离来表征，距离越近，相似性越大，距离越大， 相似性越小。为了计算相似性，需要首先得到表示每个类的向量。计算方法有多种，例如代表每个类的向量可以通过计算每个类的中心来表示。另外，在模式识别中，一个预先定义的图像用于代表每个类，分类就是把待分类的样例与预先定义的图象 进行比较。(2)实现过程输入：每个类的中心C1,，Cm；待分类的元组t。输出：输出类别c。 dist=%； 距离初始化 FOR i:=1 to m DO IF dis(ci, t)<dist THEN BEGIN cj i; dist jdist(i, t)； END.

17、3.3 规则归纳规则归纳是采用规则的形式来建立分类器，规则，是指通过学习数据，归纳 总结出的该领域数据所遵守的规律。 和其余分类方法相比，分类器采用规则形式 表达具有易理解性。通常，采用规则表示的分类器构造方法有很多种，可以采用 规则归纳技术直接生成规则，也可以利用决策树方法先生成决策树， 然后把决策 树转换为规则，还可以使用粗糙集方法或者遗传算法中的分类器技术生成规则 等。(1)规则归纳的策略规则归纳有四种策略：减法、加法，先加后减、先减后加。 减法策略：以具体例子为出发点，对例子进行推广或泛化，推广即减除 条件(属性值)或减除合取项(为了方便，我们不考虑增加析取项的推 广),使推广后的例子

18、或规则不覆盖任何反例。 加法策略：起始假设规则的条件部分为空(永真规则)，如果该规则覆盖了反例，贝U不停地向规则增加条件或合取项，直到该规则不再覆盖反 例。 先加后减策略：由于属性间存在相关性，因此可能某个条件的加入会导致前面加入的条件没什么作用，因此需要减除前面的条件。 先减后加策略：道理同先加后减，也是为了处理属性间的相关性。（2）规则归纳算法典型的规则归纳算法有 AQ、CN2和FOIL等。以AQ为例简要说明，AQ 算法在归纳过程中使用的是“种子”和“星”的概念，种子即是一个正例，星是 覆盖种子而同时排除所有反例的概念描述或规则。 AQ 获取星的方法是通过在星 中增加析取或者去掉合取项，使其包含新的正例，然后又在该星中增加合取项， 使其包含新的正例， 然后又在该星中增加合取项使其排除所包含的反例。 上面的 过程反复进行，直到所有的正例都被覆盖。除了上述