数据挖掘与数据仓库 知识点总结

1、数据仓库定义：数据仓库是一种新的数据处理体系结构，它与组织机构的操作数据库分别维护，允

许将各种应用系统一起，为统一的历史数据分析提供坚实的平台，对信息处理提供支持。数据仓库是面

向主题的、集成的、相对稳定的、反映历史变化的数据集合，为企业决策支持系统提供所需的集成信息。

设计和构造步骤：1）选取待建模的商务处理；2）选取商务处理的粒变；3）选取用于每•个事实表记录

的维；4）选取事实表中每条记录的变量

系统结构：（1）底层是仓库数据服务器，总是关系数据库系统。（2）中间层是OLAP服务器，有ROLAP

和MOLAP,它将对多维数据的操作映射为标准的关系课作（3）顶层是前端客户端，它包括查询和报表

工具、分析工具和数据挖掘工具

2、数据仓库的多维数据模型：（1）星形模式：在此模型下，数据仓库包括一个大的包含大批数据并且不

含冗余的中心表，一组小的附属表，维表环绕中心事实表显示的射线上。特征：星型模型四周的实体是

维度实体，其作用是限制和过滤用户的查询结果，缩小访问范围。每一个维表都有自己的属性，维表和

事实表通过关键字相关联，【例子:sales数据仓库的星形模式，此模式包含一个中心事实表sales,它包

含四个维time,item,branch和location。

（2）雪花型模式：它是星形模式的变种，其中某些维表是规范化的，于是把数据进一步分解到附加的表

中.特征:雪花模型通过最大限度地减少数据存储量和联合较小的维表来改善查询性能，增加了用户必须

处理的表数量和某些瓷询的复杂性，但同时提高了处理的灵便性，可以回答更多的商业问题，特殊适合

系统的逐步建设要求。【例子同上，只无非把其中的某些维给扩展了.

（3）事实星座形：复杂的应用可能需要多个事实表共享维表，这种模式可看做星形模式的汇集。

特征:事实星座模型能对多个相关的主题建模。例子:有两个事实表sales和shipping,它们可以共享维表

time,item和location„

3、OLAP:即联机分析处理，是在OLTP基础上发展起来的、以数据仓库基础上的、面向高层管理人员

和专.业分析人员、为企业决策支持服务。特点：1。实时性要求不是很高。2。数据量大。3.因为重点在

于决策支持，所以查询普通是动态的，也就是说允许用户随机提出查询要求。

OLAP操作:上卷：通过沿一个维的概念分层向上攀登，或者通过维归约，对数据立方体进行类聚。下钻：

是上卷的逆操作,它由不太详细的数据得到更详细的数据，下钻可以通过沿维的概念分层向下或者引入

附加的维来实现。切片：对给定方体的一个维进行进行选择，导致一个子立方体。切块：通过对两个

或者多个维执行选择，定义子立方体。转轴：是一种可视化操作，它转动数据的视角，提供数据的替代

表示。OLTP:即联机事务处理，是以传统数据库为基础、面向操作人员和低层管理人员、对基本数据

进行查询和增、删、改等的日常事务处理。OLTP的特点有：ao实时性要求高；bo数据量不是很大。

C.交易一般是确定的，是对确定性数据进行存取。d0并发性要求高且严格的要求事务的完整性，安

全性.OLTP和。LAP的区别：1）用户和系统的面向性：OLTP而向顾客.而OLAP而向市场：2）

数据内容：OLTP系统管理当前数据，而OLAP管理历史的数据；3）数据库设计：OLTP系统采用实

体-联系（ER）模型和面向应用的数据库设计，而OLAP系统通常采用星形和雪花模型;4）视图：OLTP系

统主要关注一个企业或者部门内部的当前数据，而OLAP系统主要关注汇总的统一的数据;5）访问模

式QLTP访问主要有短的原子事务组成，而OLAP系统的访问大部份是只读操作，尽管许多可能是复

杂的查询.

7、PageRank算法原理：1）在初始阶段：构建Web图，每一个页面初始设置相同的

PageRank值，通过迭代计算，会得到每一个页面所获得的最终PageRank值。2）在一

轮中更新页面PageRank得分的计算方法：每一个页面将其当前的PageRank值平均分配到

木页面包含的出链上。每一个页面将所有指向木页面的人链所传入的权值求和，即可得到

新的PageRank得分。优点：是一个与查询无关的静态笄法，所有网页的PageRank值通

过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。

缺点：1）人们的杳询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主

题性降低.2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有不少上游链

接，除非它是某个站点的子站点.

5、分类：指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量

及其对应的类。过程:①在已知训练数据集上，根据属性特征，为每一种类别找到•个合理的

描述或者模型，即分类规则;②然后根据规则对新数据进行分类。

分类的方法有哪些，给出弥所了解的评估分类器的方法和特点？

分类方法:用基于归纳的学习算法,k・最近邻分类，人工神经网络法、粗糙集法和遗传算法.用判

定树归纳分类；贝叶斯分类；后向传播分类;基于规则的分类；关联分类，SVM支持向量机

等.

分类和预测的评估方法：预测的准确率、速度、强壮性、可规模性、可解释性.

评估方法：(1)保持方法，给定数据随机地划分成两个独立的集合：训练集和测试集。通常，

三分之二的数据分配到训练集，其余三分之一分配到测试集。使用训练集导出分类法，其准

确率用测试集评估。评估是保守的，因为惟独一部份初始数据用于导出的分类法。

(2)交叉确认：在k-折交叉确认中，初试数据被划分成k个互不相交的子集或者“折”S

1,S2,。.。，Sk,每一个疔的大小大致相等。训练和测试进行k次。在第i次迭代,Si用作测

试集，其余的子集都用于训练分类法.其它方法包括解靴带(bootstrapping)和留一。前者

使用一致的、带放回的选样，选取给定的训练实例；后者是k-折交又确认，这里k为初

始样本数s.普通地，建议使用调整的10•折交叉确认，因为它具有相对低的偏置和方差。

(3)袋装:给定s个样本的集合S,对于迭代t(t=1,2,。。，T),训练集St采用放回

选样，由原始样本集S选取。由于使用放回选样，S的某些样本可能不在St中，而其它

的可能浮现多次.由每一个训练集St学习，得到一个分类法Cto为对一个未知的样本X

分类，每一个分类法Ct返回它的类预测，算作一票。装袋的分类法C*统计得票,并将得

票最高的类赋予Xo通过取得票的平均值，而不是多数，装袋也可以用于连续值的预测。

(4)推进:每一个训练样本赋予一个权。学习得到一系列分类法。学习得到分类法Ct后，更

新权，使得随后的分类法Ct+1”更关注"Ct的分类错误。最终的推进分类法C小组

合每个分类法的表决，这里每一个分类法的表决是其准确率的函数.推进算法也可以扩充

到连续值预测.

应用领域：是数据挖掘领域中研究和应用最为广泛的技术之一,许多分类算法被包含在统计

分析工具的软件包中，作为专门的分类工具来使用。分类问题在商业、银行业、生物学、文

本挖掘、因特网筛选等领域都有广泛应用。例如在因特网筛选中，分类方法可以协助网络工

作人员将正常邮件和垃圾邮件进行分类，从而制定有效的垃圾邮件过滤机制，防止垃圾邮件

干扰人们的正常生活。

8、决策树归纳算法及其优缺点

决策树定义：是用样本的属性作为结点，用属性的取值作为分支的树结构.它是利用信息论原

理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本中信息量最大的

属性。树的中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树

的叶结点是样本的类别值。

归纳算法过程：①创建节点N,若划分D中所有元组属于同一个类C,返回N,并用C标记②若属性表

为空，返回N并以D中多数类标记③从属性表中找到最优属性a,标记节点N④如果a是离散的且允许

多路划分，则从属性表中删除a⑤对属性a在D上的每一个划分Dj,若Dj为空，则加一个树叶到N并

标记D中的多数类，否则递归调用本算法处理Dj,返回的节点加到N⑥返回N

优点：①更高的准确性②可以生成可理解的规则③计算量不是很大④可以处理连续和种类字段⑤可以清

晰显示哪些字段比较重要⑥容易转化成份类规则：只要沿着树根向下向来走到叶子，沿途的分裂条件就

能够惟一的决定一条分类的谓词

缺点：①缺乏伸缩性，由于进行深度优先搜索，所以算法受内存大小限制,难于处理大训练集②为了处

理大数据集的种种算法(离散化、取样)不仅增加了分类算法的额外开消，而且降低了分类的准确性.

6。聚类分析的功能，主要的聚类方法及其特点.

聚类：【不知道数据的分类，甚至连分成几类也不知道】将物理或者抽象对象的集合分成由

类似的对象组成的多个类的过程被称为聚类.由聚类所生成的簇是一组数据对象的集合，

这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。是无指导的学习.

聚类与分类的主要区别：和分类学习相比，聚类的样本没有标记，需要由聚类学习算法来自

动确定.聚类分析是研究如何在没有训练集的条件下把样本划分为若干类.在分类中，对于目

标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属r哪一类标记出来.

主要的聚类方法：1）划分方法:给定n个对象或者数据元组的数据库,划分方法构建数据的

K个划分，每一个划分表示一个簇,k〈=n.构建不同划分，如K均值、K中心点算法等缺点

是需要穷举所有可能划分，合用于中小规模数据库

2）层次方法：对给定数据库对象进行层次分解，如Diana,Agnes、BIRCH、ROCK、

CAMELEON等，缺点在于一旦一个步骤（合并或者分裂）完成，就不能撤销

3）基于密度的方法,，基于连接和密度函数，如DBSCAN和OPTICS

4）基于网格的方法，基于多层粒度函数，如STING、WaveCluster.CLIQUE等，把对象空

间量化为有限个单元，形成网格结构，聚类都在网格上进行。处理速度快，处理时间依

赖于量化空间每一维的单元数目

5）基于模型的方法,为每一个簇假定一个模型，寻觅数据对给定模型的最佳拟合，如EM、

SOM、COBWEB算法等

6）基于频繁模式的聚类:从频繁浮现的维数自己中提取不同的频繁模式。

7）基于约束的聚类：结合用户指定或者面向应用的约束进行聚类。

应用领域：是数据挖掘应用的主要技术之一，它可以作为一个独立的工具来使用，将未知类

标号的数据集划分为多个类别之后，观察每一个类别中数据样本的特点,并且对某些特定的类

别作进一步的分析.此外:聚类分析还可以作为其他数据挖掘技术（例如分类学习、关联规

则挖

掘等）的预处理工作.

4、人工神经网络：是一个函数，主要在于这个函数的自学习过程，在学习过程中，它根据正确结果不

停的校正自己的网络结构。

分类方法：1。依学习策略分类主要有:监督式学习网络为主、无监督式学习网络、混合式学习网络、联

想式学习网络、最适化学习网络2。依网络架构分类主要有：前向式架构、回馈式架构、强化式架构

优点：预测准确性高、对噪声数据的高承受力（训练样本差错时仍可工作）、输出离散值、快速评估目

标缺点：1、需要很长的训练时间2、难以与域知识合作3、可解释性差

BP网络：是一种按误差逆传播算法训练的多层前馈网络，BP网络能学习和存贮大量的输入

-输出模式映射关系，而无需事前揭示描述这种映射关系的数学方程.BP算法由数据流的前向

计算（正向传播）和误差信号的反向传播两个过程构成.

BP神经网络的学习过程：神经网络在外界输入样本的刺激卜.不断改变网络连接的权值，阈

值。以使网络的输出不断地接近期望的输出。学习的本质：对各连接权值、阈值的动态调整。

学习规则：权值、阈值调整规则，即在学习过程中网络中各神经元的连接权变化所依据的一

定的调整规则BP学习算法的步骤：选定学习的数据，p=1P,随机确定初始权矩阵

W（0）；用学习数据计算网络输出；反向修正，直到用完所有学习数据。

BP神经网络算法步骤：1初始化，依据实际问题给出网络连接结构,随机设置所有连接权值。

2提供训练样本，如果输入变量为n个，输出变量为m个，则每一个训练样本形式为（x1,x2,…，

xn：H,2…,tm）o这里T,t2,…,tm是输入为x1,x2,…,xn的期望输出。3计算实际输出，

利用非纯属函数逐级计算各层节点的输入值。4权值调整，用递归方法从输出节点开始返回

到隐层节点。5返回第二步，重复执行,直到达到满意误差。

BP网络的缺点:易陷入局部最小点；收敛速度慢；学习过程容易浮现震荡；

9、提升Adaboost：在提升方法中，权重赋予每一个训练元组。迭代地学习k个分类器序列。

学习得到分类器Mj之后，更新权重，使得其后的分类器Mj+J更关注"Mj误分类的训练元组。

最终提升的分类器M*组合每一个个体分类器，其中每一个分类器投票的权重是其准确率的函

数。过程：给定数据集D,包含d个类标记的元组（X1,y1）,（X2,y2）,……,（Xd,yd）,

其中,yi是元组Xi的类标号.Adaboost对每一个训练元组赋予相等的权重1/d。在第i轮中:从

D中元组抽样，形成大小为d的训练集每一个元组被选中的机会由它的权重决定。从

训练兀组Di导出分类模型使用R作为检验集计算的误差。调整训练兀组D的权重：

如果元组不

正确地分类，则它的权重增加.如果元组正确分类，则它的权重减少。元组的权重反应对它

们分类的艰难程度——权重越高，越可能错误地分类。分类器使用这些权重产生下•轮的训

练样本。如果分类器Mi的性能太差，误差率超过0。5.则丢弃它。

AdaBoost算法的优点:一是训练的错误率上界，随着迭代次数的增加，会逐渐下降：二是

adaboost算法即使训练次数不少，也不会浮现过拟合的问题.

10、DBSCAN算法的特点和算法描述

DBSCAN原理：（具有噪声的基于密度的聚类应用），这种方法将簇卸任是数据空间中被低密

度区域分割开的稠密数据对象区域。它将簇定义为密度相连的点的最大集合。可在具有噪声

的空间数据库中发现任意开关的聚类。基于密度的簇是基于密度可达性的密度相连的点的最

大集合.

算法描述：（1）任选一未处理过的点p为种子点；（2）如果p为核心对象，则查找点p直接

密度可达的点，将其中未标记的点标记簇标号，并且将未处理的其它核心点加入种子列表；

否则，转到（1）；（3）将种子列表的点挨次执行操作（2）直到列表为空，一个簇形成；（4）重

复（1）-（3）,直到没有点可以加到任何一个簇中，聚类完成，剩余的点为噪声点。

优点：1如果用户定义的参数设置的恰当，该算法可以有效地找出任意形状的簇.同时，

DBSCAN能够识别出噪声点。2DBSCAN对于数据库口的样本的顺序不敏感。但是，对于

处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。

缺点：1聚类质量对参数非常敏感；2需要较大的内存和输入输出支持。3使用全局密度参

数，不能处理多密度数据集。

4、支持向量机（SVM）思想：使用一种非线性映射，将原训练集映射到较高的维，在新的维

上，它搜索最佳分离超平面，使用一个适合的对足够高维的非线性映射,两类数据总可以被超

平面分开.优点：（1）对复杂的非线性决策边界的建模能力是高度准确的（2）不太容易过分

拟合⑶提供了学习模型的紧凑表示。（4）可以用来预测和分类。缺点:训练时间长。特点：

SVM是一种有坚实理论基础的小样本学习方法；SVM最终决策函数只由少数的支持向量

所确定，计算复杂度和支持向量的数目有关。算法具有较好的“鲁棒”性.SVM可以有效处

理非线性分类和回归问题；SVM可以确定所建模型的推广能力的上界；核函数的选取和参

数优化仍需要解决

5、EM:（定义）EM（期望最大化）算法是一种流行的迭代求精算法，可以用来求得参数的估计值，它可看

作是k均值算法的一种扩展，基于簇的均值把对象指派到最相似的簇中。EM不是把每一个对象指派到

特定的簇，而是根据一个代表隶属概率的权重将每一个对象指派到簇。（步骤）（1）期望步：对每簇计

算对■象x的簇隶属概率⑵最大化步：利用前面得到的概率估计重新估计模型参数（优点）简单和稳定,

收敛快（缺点）达不到局部最优

4、关联规则：定义：最初由R。Agrawal等人提出，用来发现超级市场中用户购买的商品之间的隐含

关联关系，并用规则的形式表示出来，称为关联规则。应用：关联规则除了可以发现超市购物中隐含的

关联关系之外，还可以应用于其他不少领域。关联规则的应用还包括文本挖掘、商品广告邮寄分析、网

络故障分析等。分类：（1）基于规则中涉及到的数据的维数，关联规则可以分为单维的利多维的。（2）

基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则.（3）基于规则中处理的变量的类

型不同，关联规则可以分为布尔型和数值型。

挖掘步骤：I）找出交易数据库中所有大于或者等于用户指定的最小支持度的频繁项集；（2）利用频繁

项集生成所需要的关联规则，根据用户设定的最小可信度进行取舍，产生强关联规。

3、朴素贝叶斯分类：定义：贝叶斯分类法是统计学分类方法，可以预测类成员关系的可能性。朴素贝

叶斯分类法假定一个属性值对给定类的影响独立于其他属性值.它表示属性子集间的依赖

主要思想：设为一个类别未知的数据样本，H为某个假设，若数据样本X属于一个特定的类别C,分类

问题就是决定P（IIIX）,即在获得数据样本X时假设成立的概率。

优点：（1）理论上，贝叶斯分类具有最小的错误率（2）可以用来为不直接使用贝叶斯定理的其他分类

法提供理论判定（3）有着坚实的数学基础，以及稳定的分类效率（4）模型所需估计的参数很少，对缺

失数据不太敏感，算法也比较简单（5）网格结构一旦确定下来后，添加新变量容易（5）适合处理不完

整的数据（6）对过分拟合问题鲁棒。

缺点：（1）实际上，由于对其使用的假定的不正确性，以及缺乏可用的概率，此分类法并不具有最小的错

误率（2）有可能遇到零概率值，需要修正（3）构造网格费时、费力

为什么朴素：朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值。该假定称作类条件

独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”

2、简述数值数据根据直观划分离散化的3-4-5规则

（1）如果一个区间在最高有效位包括3,6,7或者9个不同的值，则将该区间划分为3个

区间（对于3,6和9,划分为3个等宽的区间；对于7,按2-3-2划分为3个区间）。

（2）如果最高位包含2,4,8个不同值，则将区间划分为4个等宽区间。

（3）如果最高位包含1,5或者10个不同的值，则将区间划分为5个等宽的区间。

最高分层普通在第5个百分位到第95个百分位上进行。

2、急切学习法是在接收待分类的新元组（如检验元组）之前,利用训练集，构造泛化模型，

即分类器。学习后的模型已经就绪，并急于对先前未见过的元组进行分类。常见的急切学习

法主要有支持向量机，决策树归纳，贝叶斯分类，基于规则的分类等.

3、惰性学习法是当给定一组训练元组时，简单地存储它，仅当给出检验元组时，才利用存储

的训练元组的相似性对该元组进行分类，不像急切学习法，惰性学习法在提供训练元组时只

做少量工作，而在进行分类或者预测时才做更多的工作。常见的惰性学习法有K最近邻和基

于案例的推理分类法。

急切学习法和情性学习法的优缺点，急切学习法训练分类器时需耗费大量时间，但对检验

元组进行分类或者预测时速度较快，且占用空间少；惰性学习法不需要建立模型，但是在对检

验元组进行分类或者预测时，需要将所有训练元组与检验元组进行运算，计算开消可能相

当大，耗费大量时间。

1、后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每一个连接

都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标

号来学习。优点：预测精度总的来说较高、茁壮性好,训练样本中包含错误时也可正常工

作、输出可能是离散值、连续值或者是离散或者量化属性的向量值、对目标进行分类较快

缺点：训练（学习）时间长、蕴涵在学习的权中的符号含义很难理解、很难根专业领域知识

相整合

34、KNN定义：即K最近邻分类法，它是基于类比学习,即通过给定的检验元组与和他相似

的训练元组进行比较来学习.

优点1）算法简单直观，易于实现；（2）不需要产生额外的数据来描述规则，并且可以存在噪

音；（3）可以较好地避免样本数量的不平衡问题：（4）减少了类别特征选择不当对分类结果

造成的不利影响,可以最大程度地减少分类过程中的误差项（5）适合增量学习

缺点：1）分类速度慢（2）样本库容量依赖性较强（3）必须指定K值，K值选择不当则分

类精度不能保证。k值的设定,k太小，分类结果易受噪声点影响,k值太大，近邻中又可能包

含太多的其它类别的点（G计算开消大（5）需要有效的存储技术和并行硬件的支撑.

1、数据预处理过程：数据清理:旨在消除或者减少数据噪音和处理遗漏值的数据预处理。相关性分析：

数据中许多属性可能与分类和预测任务不相关。数据变换：数据可以泛化到较高层概念。

3.数据仓库的特点和操作数据库和数据仓库的区别：

数据仓库的特点：（1）面向主题的:数据仓库环绕一些主题，如顾客、供应商、产品和销售

组织。数据仓库关注决策者的数据建模与分析，而不是构造组织机构的口常操作和事务处理.

因此，数据仓库排除对于决策无用的数据，提供特定主题的简明视图。（2）集成的:通常，构

造数据仓库是将多个异种数据源，如关系数据库、普通文件和联机事务处理记录，集成在一

起。使用数据清理和数据集成技术，确保命名约定、编码结构、属性度量的一致性。（3）

时变的：数据存储从历史的角度（例如，过去5-10年）提供信息。数据仓库中的关键结构，

除式或者显式地包含时间元索。（4）非易失的：数据仓库总是物埋地分离存放数据；这些

数据源于操作环境下的应用数据.由于这种分离，数据仓库不需要事务处理、恢复和并行

控制机制。通常，它只需要两种数据访问:数据的初始化装入和数据访问。

操作数据库和数据仓库的区别：

,,（1）用户和系统的面向性：OLTP是面向顾客的，月于办事员、客户、和信息技术专业

人员的事务和资询处理。OLAP是面向市场的，用于知识工人（包括经理、主管、和分析

人员）的数据分析。（2）数据内容：OLTP系统管理当前数据.通常，这种数据太琐碎，难

以方便地用「决策。OLAP系统管理大量历史数据，提供汇总和会萃机制，并在不同的粒

度级别上存储和管理信息。这些特点使得数据容易用于见多识广的决策.（3）数据库设计：

通常，OLTP系统采用实体一联系（ER）模型和面向应用的数据库设计.而OLAP系统通常

采用星形或者雪花模型（222小节讨论）和面向主题的数据库设计.（4）视图：OLTP系统主

要关注一个企业或者部门内部的当前数据,而不涉及历史数据或者不同组织的数据。相比

之下，由于组织的变化，OLAP系统往往跨越数据库模式的多个版本。OLAP系统也处

理来自不同组织的信息，由多个数据存储集成的信息.由于数据量巨大，OLAP数据也存

放在多个存储介质上。（5）访问模式：OLTP系统的访问主要由短的、原子事务组成。这

种系统需要并行控制和恢复机制。然而，对OLAP系统的访问大部份是只读操作（由于

大部份数据仓库存放历史数据，而不是当前数据），尽管许多可能是复杂的查询。

1、概念分层及作用，举例说明。

一个概念分层定义一个映射序列，将低层概念到更普通的高层概念。概念分层也可以通

过将给定维或者属性的值离散化或者分组来定义，产生集合分组分层。可以在值组间定义全

序或者偏序.例子如图关干维price的集合分组概念分层。其中，区间（$X.,。SY］表示

由$X（不包括）到$丫（包括）。概念分层可以由系统用户、领域专家、知识工程师人工地提

供，也可以根据数据分有的统计分析自动地产生.对于一个给定的属性或者维，根据不同的

用户视图，可能有多个概念分层。例如，用户可能愿意用inepensive,moderately_priced和

expensive来组织price,

6。ID3算法基本思想和算法描述,04.5算法增加了那些功能？

基本思想：首先找出最有判别力的因素，然后把数据分成多个子集，每一个子集又选择最有

判别力的因素进一步划分，向来进行到所有子集仅包含同一类型的数据为止。最后得到一

棵决策树，可以用它来对新的样例进行分类.

算法描述：①从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；②用“建树算

法”对当前窗口形成一棵决策树；③对训练集（窗口除外）中例子用所得决策树进行类别判定，

找出错判的例子；④若存在错判的例子，把它们插入窗口，重复步骤②，否则结束。

优点：1、理论清晰，算法简单/艮有实用价值的示例学习算法。2、计算时间是例子个数、特

征属性个数、节点个数之积的线性函数，总预测准确率较令人满意

缺点：（1）ID3算法在诜择根结点和各内部结点中的分枝属性时，使用信息增益作为评价标

准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这种属性可能不会提供太

多有价值的信息（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树

C4.5是机器学习算法中的另一个分类决策树算法，基于ID3算法进行改进后的一种重要算

法，相比于ID3算法，改进有如下几个要点：

（1）用信息增益率来选择属性.ID3选择属性用的是子树的信息增益，这里可