数据挖掘的算法课件.ppt

《数据挖掘的算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章数据挖掘的算法本章要点：数据挖掘方法相应的挖掘算法第7章数据挖掘的算法7．1分类规则挖掘7．2预测分析与趋势分析规则7．3数据挖掘的关联算法7．4聚类分析7．5神经网络算法7．1分类规则挖掘7．1．1分类过程与方法7．1．2决策树分类(1)ID3算法(2)C4.5算法(3)SLIQ算法(4)SPRINT算法7．1．3贝叶斯分类(1)朴素贝叶斯算法(2)TAN算法7．1．1分类过程与方法分类是一种重要的数据挖掘技术。分类的目的是根据数据集的特点构造一个分类函数或分类模型，该模型能把未知类别的样

2、本映射到给定类别中的某一个。分类和回归都可以用于预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的输出是连续或有序值。构造模型的过程一般分为训练和测试两个阶段。在构造模型之前，要求将数据集随机地分为训练数据集和测试数据集。7．1．1分类过程与方法在训练阶段，使用训练数据集，通过分析由属性描述的数据库元组来构造模型，假定每个元组属于一个预定义的类，由一个称作类标号属性的属性来确定。训练数据集中的单个元组也称作训练样本，一个具体样本的形式可为：（u1,u2,……un;c）；其中ui表示属性值

3、，c表示类别。由于提供了每个训练样本的类标号，该阶段也称为有指导的学习，通常，模型用分类规则、判定树或数学公式的形式提供。在测试阶段，使用测试数据集来评估模型的分类准确率，如果认为模型的准确率可以接受，就可以用该模型对其它数据元组进行分类。一般来说，测试阶段的代价远远低于训练阶段。7．1．2决策树分类决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结

4、点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizableinductionofdecisiontrees)是比较有代表性的两个算法。ID3算法(1)ID

5、3算法ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（informationgain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。ID3算法某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较

6、它们的大小，获得具有最大信息增益的属性。设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci(i=1,…,m)。设Si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出：其中pi=Si/s是任意样本属于Ci的概率。注意，对数函数以2为底，其原因是信息用二进制编码。设属性A具有v个不同值{a1,a2,……,av}。可以用属性A将S划分为v个子集{S1,S2,……,Sv}，其中Sj中的样本在属性A上具有相同的值aj（j=1,2,……,v）。设Sij是子集Sj中类Ci

7、的样本数。由A划分成子集的熵或信息期望由下式给出：其中Pij=Sij/Sj是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是ID3算法ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。ID3算法的算法流程如下：创建节点N；Ifsamples都在同一个类Cthen返回N作为叶节点，以类C为标记；Ifattribute_list为空then返回N作为叶节点，标记为samples中最普通的类

8、；选择attribute_list中具有最高信息增益的属性test_attribute；标记节点N为test_attribute；Foreachtest_attribute中的已知值ai由节点N长出一个条件为test_attribute=ai的分枝；设si是samples中test_attribute=ai的样本集合；Ifsi为空then加上一个树叶，标记为samples中最普通的类；Else加上一个由Generate_decision_tree(si,attribute_list