数据挖掘试卷分析

一、简答题

1、什么是数据挖掘？数据挖掘有哪些挖掘任务？请进行简要的解释。

答：数据挖掘是一种技术，将传统的数据分析方法与处理大量数据的复杂算法相结合，从大量的、不完全

的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和

知识的过程。简而言之，数据挖掘是从大量数据中挖掘有趣模式和知识的过程。

数据挖掘的任务主要有分类分析、聚类分析、关联分析、序列分析及时间序列。另外，还有孤立点分

析、依赖关系分析、概念描述、偏差检测等。

1、分类分析(ClassificationAnalysis)

分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，并用这种描

述来构造模型，一般用规则或决策树模式表示。分类是有制导的学习，它利用训练数据集通过一定的算法

而求得分类规则。分类可被用于规则描述和预测，常应用于风险管理、广告投放等商业环境。

2、聚类分析(ClusteringAnalysis)

聚类又被称为分隔(segmentatio),聚类分析是把数据按照相似性归纳成若干类别，同一类中的数据

彼此相似，不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据

属性之间的相互关系。聚类分析是无制导的学习，聚类分析与分类分析不同，它不依赖于没有事先确定的

类，也没有已具有类标识的训练集。好的聚类分析算法应该使得所得到的聚簇内的相似性很高，而不同的

聚簇间的相似性很低。

3、关联分析(AssociationAnalysis)

关联规则挖掘是由RakeshApwal等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，

就称为关联.数据关联是数据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和

因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规

则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求.最典型的应用是市场中

购物篮分析。

4、序列分析及时间序列(SequenceAnalysisandTimeSequence)

序列分析及时间序列是指通过序列信息或时间序列搜索出重复发生概率较高的模式。与回归一样，它

也是用己知的数据预测未来的值，但这些数据的区别是变量所处的序列或时间的不同。

2、为什么要数据预处理？简要论述数据预处理步骤和每一步骤的任务

答：原始业务数据来自多个数据库或数据仓库，它们的结构和规则可能是不同的，这将导致原始数据非常

的杂乱、不可用，即使在同一个数据库中，也可能存在重复的和不完整的数据信息，为了使这些数据能够

符合数据挖掘的要求，提高效率和得到清晰的结果，必须进行数据的预处理。为数据挖掘算法提供完整、

干净、准确、有针对性的数据，减少算法的计算量，提高挖掘效率和准确程度。

数据预处理步骤包含数据清理、数据集成、数据规约和数据变换。数据清理的任务是通过填充缺失值、

光滑噪声并识别离群点、组正数据中的不一致.将多个数据源中的数据结合起来存放在一个一致的数据存

储中，有助于减少结果数据集的冗余和不一致，从而提高其后挖掘过程的准确性和速度。数据规约的任务

是指在尽可能保持原始数据完整性的前提下，最大限度地精简数据量(缩小数据的取值范围),这样，在

归约后的数据集上挖掘将更有效，并产生相同(或几乎相同)的分析结果。数据变换的任务是对数据进行变

换和统一，主要有规范化、离散化等策略，达到适用于挖掘的目的.

3、数据仓库相关？什么是OLAP?在数据仓库上经常进行哪些OLAP操作？请进行简要解释。

答：

建立数据仓库(特点见书P83)的目的有3个：

一是为了解次企业次策分析中的系统响应问题，数据仓库能奏供比传统事务数据库更快的大规模次策

分析的响应速度。

二是解决决策分析对数据的特殊需求问题。决策分析需要全面的、正确的集成数据,这是传统事务数

据库不能直接提供的。

三是解决决策分析对数据的特殊操作要求。决策分析是面向专业用户而非一般业务员，需要使月专业

的分析工具，对分析结果还要以商业智能的方式进行表现，这是事务数据库不能提供的。

建立数据仓库的方法：可以使用自顶向下方法、自底向上方法或者二者结合的混合方法建立

构造步骤：一般的，数据仓库的设计过程包含如下步骤：①逃取待建模的商务处理②选取商务处理的

粒度③选取用于每个事实表记录的维④选取事实表中每条记录的度量。

数据仓库与数据库的不同：

数据仓库是面向主题的.集成的，不易更改且随时间变化的数据集合.用来支持管理人员的决策.

数据库由一组内部相关的数据和一组管理和存取数据的软件程序组成，是面向操作型的数据库.是组成

数据仓库的源数据.它用表组织数据,采用ER数据模型.它们都为数据挖掘提供了源数据，都是数据的组合

OLAP是联机分析处理的简称,OLAP是一种软件技术，它使分析人员能够迅速、一致、交互地从各

个方面观察信息，以达到深入理解数据的目的.

OLAP的特性：

OLAP是在OLTP的基础上发展起来的，以数据仓库为基础的数据分析处理,是共享多维信息的快速

分析，是被专门设计用于支持复杂的分析操作，侧重对分析人员和高层管理人员的决策支持。

(1)快速性。用户对OLAP的快速反应能力有很高的要求,要求系统能在几秒钟内对用户的多数分

析要求做出反应。

(2)可分析性。OLAP系统应能处理与应用有关的任何逻辑分析和统计分析。尽管系统可以事先编

程，但并不意味着系统定义了所有的应用。

(3)多维性。多维性是OLAP的关键属性。系统能够提供对数据分析的多维视图和分析，包括对层

次维和多重层次维的支持.事实上，多维分析是分析企业数据最有效的方法，是3LAP的灵魂。

(4)信息性。不论数据量有多大，也不管数据存储在何处，OLAP系统应能及时获得信息，并且管

理大容量信息。

(5)共享性。共享性是在大量用户间实现潜在地共享秘密数据所必须的安全需求。

OLAP的操作：

(1)上卷：上卷操作通过沿一个维的概念分层向上攀升或者通过维规约，对数据立方体进行聚集；

(2)下钻：下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。下钻可以通过沿维的概念分层向

下或引入附加的维来实现；

(3)切片和切块：切片操作对给定立方体的一个维进行选择，导致一个子立方体。切块操作通过对两个或

多个维执行选择，定义子立方体；

(4)转轴(旋转)：转轴是一种可视化操作，它转动数据的视角，提供数据的替代表示；

(5)其他OLAP操作：钻过执行涉及多个事实表的杳询；钻透操作使用关系SQL机制，钻透数据立方体

的底层，到后段关系表。

OLTP和OLAP的区别：

用户和系统的面向性：OLTP面向顾客，而OLAP面向市场；

数据内容：OLTP系统管理当前数据，而OLAP管理历史的数据；

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

星形和雪花模型；

视图：OLTP系统主要关注一个企业或部门内部的当前数据，而OLAP系统主要关注汇总的统一的数

据；

访问模式：OLTP访问主要有短的原子事务组成，而OLAP系统的访问大部分是只读操作，尽管许多

可能是复杂的直询.

集中常用数据模型

星形模型：最常见的模型范例是星形模式，其中数据仓库包括（I）一个大的包含大批数据并且不含冗

余的中心表（事实表）；（2）一组小的附属表（维表），每维=\中间是事实表，连接一组维表

雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，而数据进一步分解到附加的维表

中,它的图形类似于雪花的形状

事实星座型：多个事实表共享维表，这种模式可以看作星型模式及，因此称为星系模式或事实星座

4、简述什么是clustersamples，什么是stratifiedsample;,二者有何区别？

答：如果D中的元组被分组，放入M个互不相交的簇，则可以彳嬖I]s个簇的简单随机抽样，这样的抽样称

为簇抽样；如果D被划分为互不相交的部分，称为层，则通过对每一层的简单随机抽样就能得到D的分层

抽样。不同之处：①划分的依据不同；②抽样的方法不同；③适用范围不同.簇抽样需要抽取若T个簇，

而分层抽样则是对每个层抽取一个子样本。分层抽样适用于界质分明的群体，而簇抽样适用于界质不清的

总体。

5、简要论述bagging方法的基本思想，并举例说明

答：Bagging即套袋法，其算法过程如下：

从原始样本集中抽取训辘。每轮从原始样本集中使用有放回抽样的方法抽取n个训练样本（在训练

集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）,共进行k轮抽取，得到k个训

练集。（k个训练集之间是相互独立的）

每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法

或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均

值作为最后的结果.（所有模型的重要性相同）

6、监督、无监督、半监督、强化学习

答：SupervisedLearning的数据是有特征（feature）和标签（label）的。机器可以寻找到标签和特征之间的联系，

当面对只有特征而没有标签自缴据时，可以判断出标签。

与SupervisedLearning（监督学习）相对的是UnsupervisedLearning（无监督学习）。Supervised的数

据只有特征（feature）,没有标签（label）。这种问题在机器学习领域中就被称作聚类（Clustering）.在只有

特征没有标签的训练数据集中，通过数据之间的内在联系和相似性将他们分成若干类。

处在监督学习和无监督学习之间的是半监督学习。Semi-SupervisedLearning中使用的数据，有一部分

是标记过的，而大部分是没有标记的。因此和监督学习相比，半监督学习的成本较低，但是又能达到较高

的准确度。

强化学习也是使用未标记的数据，但是可以通过某种方法知道你是离正确答案越来越近还是越来越远

（即奖惩函数）o可以把奖惩函数想象成正确答案的一个延迟的、稀疏的形式。在监督学习中，能直接得

到每个输入的对应的输出。强化学习中，训练一段时间后，你才能得到一个延迟的反馈，并且只有一点提

示说明你是离答案越来越远还是越来越近。

二、画出一列数据的盒图

极差是最大值与最小值之差，四分位数是三个数据点，把数据分布划分成4个相等的部分（QLQ2、

Q3）,四分位数极差（IQR）则是Q3-QI的值。识SU可以的离群点的通常规则是，挑选落在第三个四分位

数之上或第Y四分位数之下至少1.5XIQR处的值.

分布的五数概括由中位数、四分位数Q1和Q3、最小和最大观测值组成，按照次序写出.而盒图就是

典型的直观表示，盒的端点T殳在四分位数上，使得盒的长度是四分位数极差IQR,中位数用盒内的线标

记，盒外两条线（称作胡须）延伸到最小和最大观测值。

方差和标准差是数据散布度量，指出散布程度，低标准差意味着靠近均值。

基本统计的图形显示包括分位数图、分位数-分位数图、直方图、散点图。

三、使用min-max与z-score方法实现归一化

最小最大规范化对原始数据进行线性变换，假设minA和maxA是属性的最小值和最大值，则公式为：

011n

也=-~~~1—（new_maxx-new_min4）+new_min4A的值vi映射到

max八-min八

[new_min,new_max]区间中。

z分数规范化，属性A拔的值基于A的均值和标准差规范化，由下式计算：

M.=小

四、数据库中包含9个事务，设最小支持度阈值min_sup=30%,请使用apnori算法或者

FP-GROWTH算法或者垂直数据格式方法找出所有的频繁项集。

Apriori算法的基本操作步骤P160

&Apriori使用一种称作逐层搜索的迭代方法，K项集用于泰索K+1项集.

&该方法是基于候选的策略，解氐候选数

tApriori剪枝原则：若任何项集是非频繁的，则其超集必然是非频繁的（不用产生和测试超舆）

令k=i

6产生长度为1的频繁项集

&循环，直到无新的频繁项集产生

p从长度为k的频繁项集产生长度为k+1的候诜频繁项集

?连接步:项集的各项排序，前k-1个项相同

P若候选频繁子集包含长度为k的m濒繁子集，则剪枝

P剪枝步：利用支持度属性原则

P扫描数据库，计算每个候选频繁集的支持度

P删除m濒繁项，保留频繁项

该算法的基本思想是:首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样.

然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产

生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则

的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所

有频集，使用了递归的方法。

apriori算法基本过程，不足之处：Apriori算法的缺点：⑴由频繁k-l项集进行自连接生成的候选频繁

k项集数量巨大。⑵在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。

五、根据直观划分离散化

3-4-5规则可以用来将数值数据分割成相对一致、看上去自然的区间。一般，该规则根据最高有效位

的取值范围，递归逐层地将给定的数据区域划分为3、4或5个相对等宽的区间。我们将用一个例子解释这

个规则的用法。规则如下：

如果一个区间在最高有效位包含3,6,7或9个不同的值，则将该区间划分成3个区间（对于3,6和9,

划分成3个等宽的区间；而对于7,按2-3-2分组，划分成3个区间）。

如果它在最高有效位包含2,4或8个不同的值，则将区间划分成4个等宽的区间.

如果它在最高有效位包含I.5或10个不同的值，则将区间划分成5个等宽的区间。该规则可以递归

地用于每个区间，为给定的数值属性创建概念分层。

概念分层的产生

使用数据离散化技术，通过把值映射到区间或概念标号变换数值数据，这种方法可以用来自动的产生

数据的概念分层，概念分层允许在多个粒度层拾掘。对于标称数据，概念分层可以基于模式定义以及每个

属性的不同值个数产生。

六、决策树（ID3算法）

决策树是一种类似流程图的树结构，其中，每个内部结点（非树叶结点）表示在一个属性上的测试，

每个分枝代表该测试的一个输出，而每个树叶结点（终端结点）存放一个类标号.树的最顶层结点是根结

点。内部结点用矩形表示，外部结点用椭圆表示。

“如何使用决策树分类？”给定一个类标号未知的元组x,在决策树上测试该元组的属性值。跟踪一

条由根到叶结点的路径，该叶结点就存放着该元组的类预测（即通过决策树对新样本属性值的测试，从树

的根结点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶结点，该叶结点表示的类别就是

新样本的类别）。

判定树归纳算法的基本策略：树以代衣单个训练样本的节点开始。如果样本都在同•个类，则该节点

成为树叶，并用该类标记。否则，算法使用成为信息增益的基于嫡的度量作为启发信息，选择能够最好的

将样本分类的属性。对测试属性每个已知的值，创建一个分枝，并据此划分样本。算法使用同样的过程，

递归地形成每个划分上的样本判定树。一旦一个属性出现在一个节点上，就不必考虑该节点的任何后代上。

递归划分步骤仅当下列条件之一成立时停止：

（a）绐定节点的所有样本属于同一类；

（b）没有剩余属性可以用来进一步划分样本，在此情况下，使用多数表决所得的类编号将节点转亿为树

叶；

（c）如果某个分枝没有样本，则以其划分前的训练样本的多数类创建一个树叶。

分析决策树算法的优缺点：1）决策树归纳是一种构建分类模型的非参数方法，决策树分类器的构造

不需要任何领域知识或参数设置，它的学习和分类步骤简单快速，可以处理高维数据：2）找到最佳的决策

树是NP完全问题，可以采用一种贪心的、自顶向下的递归划分策略建立抉策树：3）构建决策树技术不需

要昂贵的计算代价；4）决策树算法对于噪声的干扰具有相当好的鲁棒性，采用避免过分拟合的方法之后尤

其如此：5）冗余属性不会对决策树的准确率造成不利的影响：6：用树的形式表示直观，易于理解：但7）

当决策树很小时，训练和检验误差都很大，称为模型拟合不足：当规模变得太大时，即使训练误差还在继

续降低，但是检验误差开始增大，称为模型过分拟合。

Info（D）=pJog2（pJ

/=1

Gain（A）=Info（£＞）-Info（£）/）

画出最后决策树结束

七、K・means聚类

表3-1主要聚类算法分类

类别包括的主要算法

K-MEANS算法（K-平均）、K-MI-D0IDS算法（K-中心点）、CLARANS弟法（基

划分（分裂）方法

丁•选择的算法）

BIRCH算法（平衡迭代规约和三类3CIKE算法（代表点聚类）、

层次方法

CHAMELEON算法（动态模型）

DBSC/W算法（基「•高密度连接区域）、DENCLUE算法（密度分布函数）、

基」•密度的方法

OPTICS算法（对象排序识别）

STING算法（统计信息网络）、CLI0U,:算法（聚类高维空间）、

基于网格的方法

WAVE-CLUSTER算法（小波变换）

基I•模型的方法统计学方法、神经网络方法

（K-means）根据簇中心，选择离这个簇最近的距离的点，计算簇中的均值作为下一个簇中心点，继

续计算直到前后不在改变.

划分方法：K均值、k中心点计算、区别、优缺点

K-均值和法的输入、输出及聚类过程（流程）。

输入：簇的数目k和包含n个对象的数据集。

输出：k个簇，使平方误差准则最小。

步骤：

i.任意选择k个对象作为初始的强中心：

ii.计算其它对象与这k个中心的距离，然后把每个对象归入离它“最近”的簇：

iii.计算各簇中对象的平均值，然后重新选择簇中心（离平均值“最近”的对象值）：

iv.重复笫2笫3步直到簇中心不再变化为止.

K-中心点算法的输入、输出及聚类过程（流程）。

输入：结果簇的数目匕包含n个对象的数据集

输出：k个簇，使得所有对象与其最近中心点的相异度总和最小。

流程：

i.随机选择k个对象作为初始中心点：

ii.计算其它对象与这k个中心的距离，然后把每个对象归入离它"最近"的簇：

iii.随机地选择一个非中心点对象Orandom,并计算用Orandom代替Oj的总代价S：

iv.如果S<0,则用Orandom代替Oj,形成新的k个中心点集合；

V.重复迭代第3、4步，直到中心点不变为止。

区别：K均值用每类的平均值作为聚类中心，K中心点是选用对象作为聚类中心。

优缺点：k-medoids聚类算法比k-means聚类算法在处理异常数据和噪声数据方面更为鲁棒，因为与

聚类均值相比，一个聚类中心的代表对象要较少受到异常数据或极端数据的影响。但是前者的处理时间要

比后者更大。两个算法都需要用户事先指定所需聚类个数匕

八、层次聚类

先找出两个最接近的簇，然后合并他们形成一个簇，其他簇与这个簇的距离取到这个簇中点的最大的

距离，最后聚成一个类.

层次方法

层次聚类方法将数据对蒙组成层次结构或簇的“树”°自底句上的凝聚层次聚类和自顶向上的分裂层

次聚类。通常，使用一种称作树状图的树形结构来表示层次聚类的过程，它展示对象是如何一步一步被分

组聚集（在凝聚方法中）或话（在分裂方法中）。

无论是凝聚方法还是分裂方法，•个核心问题是度量两个簇之间的距离。最大距离、最小距离、均值

距离、平均距离。P300.

缺点:一旦一个步骤（合并或分裂）完成，它就不能被撤消，因此而不能更正错误的决定。

代表算法有：BIRCH算法（利用层次方法的平衡迭代归约和聚类）、CURE算法（利用代表点聚类）、

Chameleon算法

九、朴素贝叶斯

p（XIG）=巾p（xkIq）=产区IG）P（X21£）.•.P（41G）

«=i

被预测的类标号是使p（X|Ci）P（G）最大的类Ci

十、其他

神经网络及其特点

神经网络是一组连接的输入,，输出单元，其中每个连接都与一个权重相关联.在学习阶段，通过调整这

些权重，使得它能够预测输入元组的正确类标号来学习。

神经网络的缺点：I）需要很长的训练时间，因而更适合具有足够长的训练时间的应用；2）它需要大

量的参数，如网络拓扑或“结构"，通常这些主要靠经验确定；3）神经网络也常常因其可解释性差而受到

批评，例如，人们很难解释网洛中学习的权重和“隐藏单元”的符号含义；4）神经网络权值学习使月的梯

度下降方法经常会收敛到局吾陂小值。

神经网络的优点：1）对于噪声数据的承受能力高，以及它对未经训练的数据的模式分类能力；2）神

经网络可以处理冗余特征，对训练数据中的噪声非常敏感；3）不像大部分的决策树算法，它非常适合连续

值的输入和输出；4）神经网络算法是固有并行的，可以使用并行技术来加快计算过程。

SVM支持向量机

SVM：靠核函数将数据从低维映射到高维，变得可分。

支持向量机是一种对线性和非线性数据进行分类的方法.它使用一种非线性映射，把原训练数据映射

到较高的维上。在新的维上，它搜索最佳分离超平面（即将一个弟的元组与其它类分离的“决策边界"）O

使用到足够高维上的、合适的非线性映射，两个类的数据总可以被超平面分开。SVM使用支持向量："基

本”训练元组）和边缘（由西寺向量定义）发现该超平面（最佳超平面，最大边缘超平面，离最近的训练

元组具有最大距离的超平面）。

数据线性可分的情况：最大边缘超平面，支持向量，边缘

数据非线性可分的情况：I）用非线性映射（核函数：h次多项式核函数，高斯径向基函数核函数，S

型核函数）把原输入数据变换到较高维空间；2）一旦将数据变换到较高维空间，就在信的空间搜索分离超

平面，在新空间找到的最大边缘超平面对应于原空间中的非线性分离超平面。

理解SVM的核心：1）非线性映射是SVM方法的理论基础，SVM利用内积核函数代替向高维空间的

非线性映射；2）寻找特征空间划分的最优超平面是SVM的目标，最大化分类边际的思想是SVM方法的

核03）支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。

SVM优点：1）SVM是种有坚实理论基础的新颖的小样本学习方法，大大简化了通常的分类和回归

等问题；2）SVM的最终决策函数只由少数的支持向量所确定.计算的复杂性取决于支持向量的数目，而不

是样本空间的维数，这在某种意义上避免了,,维数灾难"；3）少数支持向量决定了最终结果，这不但可以帮助

我们抓住关键样本、“剔除”大量冗余样本，而且注定了该方法不但篝法简单,而且具有较好的“鲁棒”性。

SVM不足：1）SVM算法对大规模训练样本难以实施。由于SVM是借助二次规划来求解支持向量，

而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费

大量的机器内存和运算时间；2）用SVM解决多分类问题存在困难。

贝叶斯网络分类：

贝叶斯分类是统计学分类方法。它们可以预测类隶属关系的概率，如一个给定的元组属于一个特定类

的概率。贝叶斯分类基于贝叶斯定理。

朴素贝叶斯分类：例8.4

K最邻近分类特点：

（1）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对

于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。（2）当样本不平衡时，如一

个类的样本容量很大,而其磔样本容量很小时，有可能导致当输入一个新样本时,该样本的K个邻居中

大容量类的样本占多数。数量影响运行结果。（可以采用权值的方法来改进）。（3）该方法的另一个不足之处

是计算量较大。（4）准确率受噪声影响。

何为pagcrank算法，列举典型应用

PageRank算法是Google排名运算法则（排名公式）的一个非常重要的组成部分，其是用于衡量一个

网站好坏的标准，PageRank能够对网页的重要性做出客观评价。

PageRank并不计算直接链接的数量，而是将从网页A指向网页B的链接解释为由网页A对网页B所

投的一票。这样,PageRank会根据网页B所收到的投票数量来评估该网页的重要性。此外，PageRank还

会评估每个投票网页的重要性，因为某些重要网页的投票被认为具有较高的价值，这样，它所链接的网页

就断得较高的价值。这就是PageRank的核心思想主要用在google搜索引擎上，之后也被用于像论文检

索这样的领域。

十一、相关例题

例6.1让我们看一个Apnon的具体例子。该例期于图6.2的AllElectronics的事务数据库。数

据件中有9个事务,即|口=9.Apnon假定事务中的项按字典次序存放。我们使用图63解释Apnon

算法发现。中的频繁项集，

AlIF.lM,trnnic^数据库

TIDListofitemID's

T100I1I2.I5

T20012.14

T30012,13

T400II.12.14

T50011.13

T60012,13

T700ILB

T800I1.I2.I3.I5

T900II.12.13

图6.2AllElectromcs某分店的事务数据

1.在算法的第一诙迭代，每个项都是候选1-项集的集合G的成员。算法简单地扫描所有的事务，

对将个项的出现次数讦数.

2.假定最小事务支持计数为2（即，加忆卯=279=22%）。可以确定须繁1-项集的集合办。它由

且右易小&林肉的灰漆1-珀依州能一

3.为发现频繁2-项集的集合Z2,算法使用乙乙产生候选2频集的集合Q叱C2由1)个2-

2

项集组成。

4.下步，扫描Z＞中事务，计算Q中每个候选项集的支持计数，如图6.3的第二行的中间表所示。

5.确定频繁2-项集的集合它由具有最小支持度的U中的候选2-」成.

Ci

C2C2

项集项集支持度计数

由L1产生{11,12}UU2)4

候出：2{【1,13}{11,13}4

{11,14}{I1J4}1

(11,151UU5}2

{12,13}{I2J3}4

{12,14}{I2J4}2

{【2,15}{12,15}2

{13,14}(1344}0

{13,15}(卬5}1

(14,15)114.1510

C3

由L2声生迹D,对每候选支持度计数项集

项集支持度计数小支持度计数支持度计数

.候选C3个候选计数

(11,12,13}{I1AI3}(I1J2J3)2

01,12,15}UU2J5}2

图6.3候选项集和领繁项集的产生，最小支持计数为2

1.连接：C3=L2L2=｛｛11.12).｛11.13).｛I1.15).｛12.13｝.｛12.14).｛12.15))

2.使用Apnon性质剪枝：物繁项第的所有子集必须是频繁的。存在候选项集，其

子便不是频繁的叫？

・｛111213｝的2-项子集是(ILI2｝,｛11.13｝和｛12.13｝。｛H.I2.I3｝的所有2-项子集都

是L2的元素.因此,保留｛11,12,13｝在C3中.

・｛1112.15｝的2.项子集是｛HJ2｝,｛11,15｝和｛1215｝。｛ILI2.I5｝的所有2.项子集都

是L2的元素。因此，保留｛H.I2J5｝在C3中。

•｛H.I3.I5｝的2-项子集是｛H.I3｝,｛11.15｝和｛13.15｝・｛1315｝不是L2的元素,因而

不是频繁的。这样，由C3中删除｛11,13,15｝。

•｛I2J3.I4｝的2-项子集是(12.13｝,｛12,14｝和｛13,14｝°｛1314｝不是L2的元素，因而

不是频繁的.这样，由C3中删除｛1213.14｝.

•｛12,13,15｝的2-项子集是｛12,13｝,｛12,15｝和｛13,15｝。｛1315｝不是L?的兀素,因而

不是频繁的.这样.由。3中删除｛I2.BI5｝.

•{I2.I4J5}的2-项子集是{I2J4},{12.15}和{14.15}.{14.15}不是L?的元素，因而

不是频繁的。这样，由C3中删除{I2.BI5}。

3.这样，剪枝后C3={{HJ2.B}.{n.I2J5}}・

图6.4使用Apnori性质，由L?产生候选3.项集C3

6.候选3-项集的集合Cs的产生详细地列在图6.4中。首先，令Q=Z；L2=({I1J2J3}.(I1J2I5}.

{11,13,15},{12,13,14),{12.13,15),{I2.I4.I5)}_根据Apnori性质,频繁项集的所有子集必须是频警

的，我们可以确定后4个候选不可能是频繁的.因此，我们把它们由C?删除，这样，在此后扫

描。确定4时就不必再求它们的计数值.注意，Apnon算法使用逐层搜索技术，给定小项集，

我们只需要检查它们的伽1)-子集是否频繁.

7.扫描。中事务，以确定它由具有最小支持度的C,中的候选3-项集组成(图6.3)。

8.算法使用〃打产生候选4•项集的集合G。尽管连接产生结果{{11.12.13.15}},这个项集被剪

去，因为它的子集{HI3I5}不是频繁的.这样，G=0,因此算法终止，找出了所有的频繁项集，

例7.4使用朴素贝叶斯分类预测类标号：给定与例7.2判定树归纳相同的训练数据，我们希

望使用朴素贝叶斯分类预测一个未知样本的类标号.训练数据在表7.1中,数据样本用属性age,

income,student和credijrating描述。类标号属性具有两个不同值(即，{yes,

no})♦设C对应于类buys_coaputer-''yes",而C对应于类buys_c。曜uter-"no".我们希望

分类的未知样本为：

X=(age="<=30'\income="mediunf.student=Mves"aeditrating="fair'').

我们需要最大化RXIC)RG),2=1,2.每个类的先验概率RG)可以根据训练样本计算：

P(buys_coaputer=yes)-9/14=0.613

P(buys_computer-no)-5/14=0.357

为计算RXIG),i=l,2o我们计算下面的条件概率：

P(age="<30"1buys_computer-"yes")2/9

0.222

P(age="<30"/buys_coaputer="no")3/5-

0.600

P(income="medium"buys_couputer-4/9

"yes")0.444

P(income="aediua"/buys_cosputer=2/5—

no/0.400

P(student="yes"/buys_coaputer=6/9—

“yes”)0.667

P(student="yes"/buys_couputer=1/5—

"no")0.200

P(credit_rating-"fair"6/9—

buys_compuTer-"yes")0.667

Picredit_rating="fair"2/5二

buys_coaputer="no")0.400

使用以上概率,我们得到:

P(X/buys_coaputer="yes")=0.222x0.444x0.667x0.667=0.044

P(X/buys_coiBputfr="no")=0.600x0.400x0.200x0.400=0.019

P(X/buys_coiaputer="yes")P(buys_coaputer-"yes")=0.014x0.613=0.028

P(Xbuys_coaputer-"no")P(buys_coaputer="no")=0.019x0.357=0.007

因此，对于样本.X，朴素贝叶斯分类预测buys_compureryes"cJ

朴素贝叶斯分类，或的单贝叶斯分类的工作过程如下：

1.每个数据样本用一个A堆特征向量X={X]/2,…，/}表示，描述由属性4,送，…,4对样本的A

个度量.

2.假定有屈个类G«2,…,C,。给定一个未知的数据样本1(即，没有类标号)，分类法将预测1

属于具有最高后验"率(条件1下)的类.即，朴素贝叶好分类将未知的样本分配给类G,当

且仅当：

P(C,|AT)>P(C;|T)1<j<mj^i.

这样，我们最大化P(CJX)。其p(aIX)最大的类C称为最大后验假定。根据贝叶斯定理

((7.5)式),

尸(X|C)P(C)

(7.6)

3.由于尸对于所有类为常数，只需要RXIG)RG)最大即可。如果类的先验概率未知，则通

常假定这些类是等概率的：即，P(C])・P(C2)—.・P(，)・并据此对只尸(c,ix)最大化。否则,

我们最大化RXIGWq)。注意，类的先验概率可以用尸(Cj)=sjs计算；其中，&是类c中

的训练样本数.而S是训练样本总数.

4.给定具有许多属性的数据集，计算RXG)的开销可能非常大。为降低计算RXIG)的开销，

可以做类条件独立的朴素假定.给定样本的类标号，假定属性侑条件地相互独立。即，在属性

间，不存在依赖关系。这样，

p⑶c,)・np(x*iG)

k=\

(7.7)

概率IC),久gC),...,P(xM|C,.)可以由训练样本估值，其中，

(a)如果4是分类属性，则尸(4|Cj)=s*/»：其中5〃是在属性4上具有值％的类a的训练

样本数，而S是C中的训练样本数。

(b)如果是连续值属性,则通常假定该属性服从高斯分布。因而，

_(A生J

P(x*lG)=g®,〃c,，%)=WJe3

(7.8)

其中，给定类G的训练样本属性4的值，g(xh〃j。。)处属性儿的高斯密度函数，

而4C分别为平均值和标准差。

5.为对未知样本I分类，对每个类C，计算RX|G)P(Cj)・样本¥被指派到类C，当且仅当:

NXd)>P(X\Cj)P(Cj)l<j<m尸上

换言之，X被指派到其P(X|G)RG)最大的类以

例7.2判定树归纳，表7.1给出了取自AllElectronics顾客数据库数据元组训练集。（该数

据取自［Qui86］）。类标号属性加产Lea卬有两个不同值（电｛yes,AO｝）,因此有两个不同

的类5=2）・设类G对应于居$,而类G对应于〃。。类有9个样本，类〃。有5个样本.为计

算每个属性的信息增益，我们首先使用（7.1）式，计算对给定样本分类所需的期望信息：

9955

1(力,与)=1(9,5)=log、leg,—=0.940

14141414

表7.1AllElectronics顾客数据库训练数据元组

Rageincostcredit.Class：

ID