数据挖掘作业

1、给出KDD的定义和处理过程

KDD的定义是：从大量数据中提取出可信的、新颖的、有用的且可以被人理

解的模式的高级处理过程。因此，KDD是一个高级的处理过程，它从数据集中识

别出以模式形式表示的知识。这里的“模式”可以看成知识的雏形，经过验证、

完善后形成知识："高级的处理过程”是指一个多步骤的处理过程，多步骤之间相

互影响反复调整，形成一种螺旋式上升的过程。

KDD的全过程有五个步骤：1、数据选择：确定发现任务的操作对象，即目

标数据，它是根据用户的需要从原始数据库中抽取的一组数据；2、数据预处理：

一般可能包括消除噪声、推到技术却只数据、消除重复记录、完成数据类型转换

等；3、数据转换：其主要目的是消减数据维数或降维，即从初始特征中找出真

正有用的特征以减少数据开采时要考虑的特征或变量个数；4、数据挖掘：这一

阶段包括确定挖掘任务/目的、选择挖掘方法、实施数据挖掘；5、模式解释/评

价：数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无

关的模式，需要剔除；也有可能模式不满足用户的要求，需要退回到整个发现阶

段之前，重新进行KDD过程。

2、阐述数据挖掘产生的背景和意义。

?数据挖掘产生的背景：随着信息科技的进步以及电子化时代的到来，人们

以更快捷、更容易、更廉价的方式获取和存储数据，使得数据及信息量以指数方

式增长。据粗略估计，一个中等规模企业每天要产生100MB以上的商业数据。

而电信、银行、大型零售业每天产生的数据量以TB来计算。人们搜集的数据越

来越多，剧增的数据背后隐藏着许多重要的信息，人们希望对其进行更高层次的

分析，以便更好的利用这些数据。先前的数据库系统可以高效的实现数据的录入、

查询、统计等功能，但无法发现数据中存在的关系与规则，无法根据现有的数据

来预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段。导致了“数据爆

炸但知识贫乏”的现象。于是人们开始提出“要学会选择、提取、抛弃信息”，

并且开始考虑：如何才能不被信息淹没？如何从中及时发现有用的知识、提高信

息利用率？如何从浩瀚如烟海的资料中选择性的搜集他们认为有用的信息？这

给我们带来了另一些头头疼的问题：第一是信息过量，难以消化；第二是信息真

假难以辨别；第三是信息安全难以保证；第四是信息形式不一致，难以统一处理?

面对这一挑战，面对数量很大而有意义的信息很难得到的状况面对大量繁杂

而分散的数据资源，随着计算机数据仓库技术的不断成熟，从数据中发现知识

(Knowledge?Discovery?in?Database)及其核心技术--数据挖掘(Data?Mining)

便应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。

数据挖掘的意义：数据挖掘之所以被称为未来信息处理的骨干技术之一，主

要在于它正以一种全新的概念改变着人类利用数据的方式。在20世纪，数据库

技术取得了重大的成果并且得到了广泛的应用。但是，数据库技术作为一种基本

的信息储存和管理方式,仍然是以联机事务处理为核心应用，缺少对决策、分析、

预测等高级功能的支持机制。众所周知，随着硬盘存储容量及的激增以及磁盘阵

列的普及，数据库容量增长迅速，数据仓库以及Web等新型数据源出现，联机

分析处理、决策支持以及分类、聚类等复杂应用成为必然。面对这样的挑战，数

据挖掘和知识发现技术应运而生，并显现出强大的生命力。数据挖掘和知识发现

使数据处理技术进入了一个更加高级的阶段。它不仅能对过去的数据进行查询，

而且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地作出

决策、预测未来的发展趋势等等。通过数据挖掘，有价值的知识、规则或更高层

次的信息就能够从数据库的相关数据集合中抽取出来，从而使大型数据库作为一

个丰富、可靠的资源为知识的提取服务。

3、给出一种关联规则的算法描述，并举例说明。

Apriori算法描述：Apriori算法由Agrawal等人于1993年提出,是最有影响

的挖掘布尔关联规则频繁项集的算法，它通过使用递推的方法生成所有频繁项目

集。基本思想是将关联规则挖掘算法的设计分解为两步：⑴找到所有频繁项集，

含有?k?个项的频繁项集称为?k-项集。Apriori使用一种称作逐层搜索的迭代方法,

k-项集用于探索(k+1)-项集。首先，出频繁?1-项集的集合。该集合记作LI。L1用

于找频繁?2-项集的集合L2,而L2用于找L3,如下去，直到不能找到频繁k-项集。

找出每个Lk都需要一次数据库扫描。为提高频繁项集层产生的效率，算法使用

Apriori性质用于压缩搜索空间。⑵使用第一步中找到的频繁项集产生关联规则。

从算法的基本思想可知，Apriori算法的核心和关键在第一步。而第一步的关键是

如何将Apriori性质用于算法，利用Lk?-?1找Lk。这也是一个由连接和剪枝组成

的两步过程：(1)连接步：为找Lk,通过Lk?-1与自己连接产生候选k-项集的集

合。该候选项集的集合记作Cko设II和12是Lk?-?1中的项集。记号li[j]表示li

的第上项(例如，表示II的倒数第3项)。为方便计，假定事务或项集中的

项按字典次序排序。执行连接Lk?-??l?Lk?-??l；其中，Lk?-?1的元素是可连接的，

如果它们前(k-2)项相同；即Lk?-?1的元素II和12是可连接的，如果(11[1]?=?12冏?

A?(ll[2]?=?l2[2])?A?...?A?(ll?[k-2]?=?l2?[k-2])?A?(ll?[k-l]?<?l2?[k-l])o条件

12k1])是简单地保证不产生重复。连接II和12产生的结果项集是

Il[l]?ll[2]...?ll?[k-l]?l2[k-l]o(2)剪枝步：Ck是Lk的超集；即，它的成员可以

是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确

定Ck中每个候选的计数，从而确定Lk(即，根据定义，计数值不小于最小支持

度计数的所有候选是频繁的，从而属于Lk)。然而，Ck可能很大，这样所涉及的

计算量就很大。为压缩Ck,可以用以下办法使用Apriori性质：任何非频繁的(k-1)-

项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-l)-子集不

在Lk?-?1中，则该候选也不可能是频繁的，从而可以由Ck中删除。

Apriori算法举例：如有如下数据

TIDListof

item_ID's

T10011,12,15

T20012,14

T30012,13

T40011,12,14

T50011,13

T60012,13

T70011,13

T80011,12,13,15

T90011,12,13

每一行表示一条交易，共有9行，既9笔交易，左边表示交易ID,右边表

示商品名称。最小支持度是22%,那么每件商品至少要出现9*22%=2次才算频

繁。第一次扫描数据库，使得在每条交易中，按商品名称递增排序。第二次扫描

此时就有规律性了，在频繁项集为K的元素上找频繁项集为K+1的元素的方

法是：在频繁项集为K的项目（每行记录）中，假如共有N行，两两组合，满

足两两中前K-1个元素相同，只后一个元素要求前一条记录的商品名称小于后一

条记录的商品名称，这样是为了避免重复组合，求它们的并集得到长度为K+1

的准频繁项集，那么最多共有Apriori算法种可能的组合，有：

项集

想想如果N很大的话，Apriori算法是一个多么庞大的数字，这时就要用到

Apriori的核心了：如果K+1个元素构成频繁项集，那么它的任意K个元素的子集

也是频繁项集。然后将每组K+1个元素的所有长度为K的子集，有Apriori算法

中组合，在频繁项集为K的项集中匹配，没有找到则删除，用第一条记录｛11,12,13｝

它的长度为2的频繁项集有：Apriori算法分别是：｛11,0,｛II,13｝,｛12,13｝种情况，幸好

这三种情况在频繁项集为2的项集中都找到了。通过这步过滤，得到的依旧是准

因为｛11,12,14｝只出现了1次，小于最小支持度2,删除。就这个例子而言,

它的最大频繁项集只有3,就是｛II,12,13｝和｛II,12,15｝。

4、给出一种聚类算法描述，并举例说明。

k-means算法是一种属于划分方法的聚类算法，通常采用欧氏距离作为2

个样本相似程度的评价指标，其基本思想是：随机选取数据集中的k个点作为

初始聚类中心，根据数据集中的各个样本到k个中心的距离将其归到距离最小

的类中，然后计算所有归到各个类中的样本的平均值，更新每个类中心，直到平

方误差准则函数稳定在最小值。

算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有K?个初始聚类中

心。？?2.将样本集中的样本按照最小距离原则分配到最邻近聚类???3.使用每个聚

类中的样本均值作为新的聚类中心。？4.重复步骤2.3步直到聚类中心不再变化。

k-means算法举例：数据对象集合S见下表，作为一个聚类分析的二维样本,

要求的簇的数量k=2o

OXy

102

200

31.50

45（）

552

⑴选择q（o,2）,。2（0,0）为初始的簇中心，即M=Q=（O,2），%=Q=（o,o）

（2）对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。

对R：d（M，Q）=J（0-L5）2+（2-Op=2.5”（此。3）=［（0-1.5）2+（0-=L5

显然d（%，q）"（M，q）,故将。3分配给G

对于。4：J（）=^/（0-5）2+（2-0）2=729^（^2，）=7（0_5）2+（0-0）2=5

因为4Mz,QjwaMOj，所以将。4分配给c2_______________

对于Q：d（M，Q）=，（。-5）2+（2-2）2=54（也，。5）=10-5）2+（0-2）2=扬

因为d（M，q）wd（"2，Q）,所以将。5分配给G

更新，得到新簇G=｛q,Q｝和。2=｛。2，。3，。4｝

计算平方误差准则，单个方差为

2

（3）计算新的簇的中心。M,=（（0+5）/2,（2+2）/2）=（2.5,2）

重复（2）和（3）,得到。分配给G；0?分配给C2,。3分配给C2,0“分配给

C2,分配给3。更新，得到新簇。|=｛牝。,｝和。2=｛02，°3，04｝。

中心为M=（252）,M2=（2.17,0）0

单个方差分别为

总钿刖误续国（2一2）［+［（2.5—5『+（2一2月=12.5

由上可以看出，第一次迭代后，总体平均误差值52.25~25.65,显着减小。

由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。

5、给出一种分类的算法描述，并举例说明。

决策树算法是数据挖掘领域的核心分类算法之一,其中ID3算法是最为经典

的决策树算法。ID3算法理论清晰、使用简单、学习能力较强，且构造的决策树

平均深度较小,分类速度较快,特别适合处理大规模的学习问题，目前已得到广泛

应用。

在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节

点时所应采用的合适属性。这样就可以选择具有最高信息增益（端减少的程度最

大）的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类

所需要的信息最小，也就是说，利用该属性进行当前（节点所含）样本集合划分，

将会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用

这样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策

树最为简单。

F

®E=F1XF2X…XFn是n维有穷向量空间，其中,是有穷离散符号集,

,―一VVV,V.p

E中的兀素e=<1,2,…，">叫做例子,其中JG,j=l,2,…，n。设

PE和NE是E的F两个例子集，分别叫正例集和反例集。

假设向量空间E中的正例集PE和反例集NE的大小分别为p和n,ID3基于

下列两个假设：（1）在向量空间E上的一棵正确决策树，对任意例子的分类概率

同E中的正、反例的概率一致；（2）一棵决策树能对一例子做出正确类别判断所

需的信息量为：

log2-^--log2—

I（p,n）=〃+〃P+〃P+n

如果以属性A作为决策树的根，A具有v个值（匕，…，匕），它将E分为

v个子集（耳，纥），假设中含有Pi个正例和4个反例,子集耳的信息

焙为I（Pi,〃，），以属性A为根分类后的信息端为：

因此，以A为根的信息增益是Gain(A)=I(p,n)-E(A)„ID3选择使

Gain(A)最大(即E(A)最小)的属性4作为根结点。对4的不同的取值对应的

E的v个子集4递归调用上述过程，生成4的子结点，4，员，…，必。

ID3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集S共

有C类样本，每类样本数为pi,(i=1,2,3,…c)。若以属性A作为决策

树的根，A具有V个值匕，…，匕，它将E分成V个子集［&,

假设片中含有j类样本的个数为P",j=1,2,…,c那么，子集号的信息量是

E

K*)o

以A为根分类的信息蜡为：

选择属性4使£(A)最小,信息增益也将增大。

理想的决策树分成3种：(1)叶节点数最小，(2)叶节点深度最小；(3)叶节

点数量最少且叶子结点深度最小。决策树的好坏，不仅影响分类的效率,而且还影

响分类的准确率。人们为了寻求较优的解，不得不寻求各种启发式的方法。有的

采用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的则

扩充决策树,形成决策图。

如今普遍采用的是优化算法,基本思想:首先用ID3选择属性F1,建立树T1,

左、右子树的属性分别为F2,F3,再以F2,F3为根,重建树T2,T3;较T1,T2,T3

的结点个数,选择结点最少的树。对于选择定树的儿子结点采用同样的方法递归

建树。尽管作者用一个实验证明能建立理想的决策树，但算法有较大的弱点:时间

开销太大,因为每选择一个新的属性,算法都需要建立3棵决策树,从中选优。

ID3算法举例：

性格父母教育程度性别类别

内向良女生好

外向良男生好

外向中女生差

内向差女生差

外向中男生好

内向良男生好

外向差女生好

外向差男生差

外向良女生好

内向中女生差

内向中男牛差

内向差男生差

此例假定要按某校学生学习成绩好坏这个概念对一个集合进行分类,该集合

中用来描述学生的属性有性格、父母教育程度和性别。性格的取值为外向、内向。

父母教育程度取值为良好、中等和差。性别的取值为男生、女生。例子集中共有

12名学生，如表所示。在类别一栏，将正例即“学习成绩好”的学生用“好”标

出，反例即“学生成绩差”的学生用"差”标出。

这些例子一开始全部包含在根结点中，为了找出当前的最佳划分属性,先须

根据信息论中的公式计算训练实例集Es的燧值。则根节点的蜡值为：

Entropy{Es)=-/log2—^―-提log2—^―

126+6126+6=1

下面分别计算例子集中各个属性的信息赢取值。对属性“性格”来说，分外

向和内向两个分支。当丫="外向”时，有4名“外向”小学生是“学习成绩好”

的，有2名“外向”小学生是“学习成绩差”的。因此，

当v="内向”时，有2名“内向”小学生是“学习成绩好”的，有4名“内

向”小学生是“学习成绩差”的。因此，

所以根据“性格”属性来进行例子集分类的信息赢取值为：

1-(-*0.9183+4*0.9183)=0.0817

Gain(Es)=Entropy(Es)-Entropy(Esv)=22

同理，对“父母教育程度”来说:Gain(Es,父母教育程度)=0.4591;

对“性别”来说:Gain(Es,性别)=0。

因为Gain（Es，性别）＜Gain（Es,性格）＜Gain（Es,父母教育程

度）可以看出以“父母教育程度”这个属性进行例子集分类的信息赢取值最大,

于是“父母教育程度”就被选为用于划分的属性,得到如下图所示的决策树。

现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差”

的小学生的“学习成绩好坏”，因此必须对“中”和“差”两个分支的实例组成

的例子集（共8个例子）重复上述计算过程。这里简化计算过程,算出:Gain（Es,

性格）=0.3113和Gain（Es,性别）=0.2045。

因为Gain（Es，性别）＜Gain（Es，性格），所以用属性“性格”作第二

步划分，于是得到如下图所示的决策树。

父母教育程度

差

一

向良

女

内

向良

男

外