数据挖掘作业.docx

11、 给出 KDD 的定义和处理过程KDD 的定义是：从大量数据中提取出可信的、新颖的、有用的且可以被人理解的模式的高级处理过程因此，KDD 是一个高级的处理过程，它从数据集中识别出以模式形式表示的知识这里的“模式”可以看成知识的雏形，经过验证、完善后形成知识：“高级的处理过程” 是指一个多步骤的处理过程，多步骤之间相互影响反复调整，形成一种螺旋式上升的过程KDD 的全过程有五个步骤：1、数据选择：确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数据；2、数据预处理：一般可能包括消除噪声、推到技术却只数据、消除重复记录、完成数据类型转换等；3、数据转换：其主要目的是消减数据维数或降维，即从初始特征中找出真正有用的特征以减少数据开采时要考虑的特征或变量个数；4 、数据挖掘：这一阶段包括确定挖掘任务/目的、选择挖掘方法、实施数据挖掘；5、模式解释/ 评价：数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无关的模式，需要剔除；也有可能模式不满足用户的要求，需要退回到整个发现阶段之前，重新进行 KDD 过程2、 阐述数据挖掘产生的背景和意义数据挖掘产生的背景：随着信息科技的进步以及电子化时代的到来，人们以更快捷、更容易、更廉价的方式获取和存储数据，使得数据及信息量以指数方式增长。

据粗略估计，一个中等规模企业每天要产生 100MB 以上的商业数据而电信、银行、大型零售业每天产生的数据量以 TB 来计算人们搜集的数据越来越多，剧增的数据背后隐藏着许多重要的信息，人们希望对其进行更高层次的分析，以便更好的利用这些数据先前的数据库系统可以高效的实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系与规则，无法根据现有的数据来预测未来的发展趋势缺乏挖掘数据背后隐藏的知识的手段导致了“数据爆炸但知识贫乏”的现象于是人们开始提出“要学会选择、提取、抛弃信息” ，并且开始考虑：如何才能不被信息淹没？如何从中及时发现有用的知识、提高信息利用率？如何从浩瀚如烟海的资料中选择性的搜集他们认为有用的信息？这给我们带来了另一些头头2疼的问题：第一是信息过量，难以消化；第二是信息真假难以辨别；第三是信息安全难以保证；第四是信息形式不一致，难以统一处理 面对这一挑战，面对数量很大而有意义的信息很难得到的状况面对大量繁杂而分散的数据资源，随着计算机数据仓库技术的不断成熟，从数据中发现知识（Knowledge Discovery in Database）及其核心技术 ——数据挖掘（Data Mining）便应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。

数据挖掘的意义：数据挖掘之所以被称为未来信息处理的骨干技术之一，主要在于它正以一种全新的概念改变着人类利用数据的方式在 20 世纪，数据库技术取得了重大的成果并且得到了广泛的应用但是，数据库技术作为一种基本的信息储存和管理方式，仍然是以联机事务处理为核心应用，缺少对决策、分析、预测等高级功能的支持机制众所周知，随着硬盘存储容量及的激增以及磁盘阵列的普及，数据库容量增长迅速，数据仓库以及Web 等新型数据源出现，联机分析处理、决策支持以及分类、聚类等复杂应用成为必然面对这样的挑战，数据挖掘和知识发现技术应运而生，并显现出强大的生命力数据挖掘和知识发现使数据处理技术进入了一个更加高级的阶段它不仅能对过去的数据进行查询，而且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地作出决策、预测未来的发展趋势等等通过数据挖掘，有价值的知识、规则或更高层次的信息就能够从数据库的相关数据集合中抽取出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务3、 给出一种关联规则的算法描述，并举例说明Apriori 算法描述： Apriori 算法由 Agrawal 等人于 1993 年提出，是最有影响的挖掘布尔关联规则频繁项集的算法，它通过使用递推的方法生成所有频繁项目集。

基本思想是将关联规则挖掘算法的设计分解为两步：(1)找到所有频繁项集，含有 k 个项的频繁项集称为 k-项集 Apriori 使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集首先，出频繁 1-项集的集合该集合记作 L1L1 用于找频繁 2-项集的集合 L2，而 L2 用于找 L3，如下去，直到不能找到频繁 k-项集找出每个 Lk 都需要一次数据库扫描为提高频3繁项集层产生的效率，算法使用 Apriori 性质用于压缩搜索空间2)使用第一步中找到的频繁项集产生关联规则从算法的基本思想可知，Apriori 算法的核心和关键在第一步而第一步的关键是如何将 Apriori 性质用于算法，利用 Lk - 1 找 Lk这也是一个由连接和剪枝组成的两步过程：（1）连接步：为找 Lk，通过 Lk -1 与自己连接产生候选 k-项集的集合该候选项集的集合记作 Ck设 l1 和 l2 是 Lk - 1 中的项集记号 li[j]表示 li 的第 j 项（例如，l1[k-2]表示 l1 的倒数第 3 项） 为方便计，假定事务或项集中的项按字典次序排序执行连接 Lk - 1 Lk - 1；其中，Lk - 1 的元素是可连接的，如果它们前(k-2)项相同；即 Lk - 1 的元素 l1 和 l2 是可连接的，如果 (l1[1] = l2[1])∧ (l1[2] = l2[2]) ∧ ... ∧ (l1 [k-2] = l2 [k-2]) ∧ (l1 [k-1] 叫做例子, 其中 ∈ , j = 1 ,2 , 1V2 jV…, n。

设 PE 和 NE 是 E 的 F 两个例子集,分别叫正例集和反例集假设向量空间 E 中的正例集 PE 和反例集 NE 的大小分别为 p 和 n ,ID3基于下列两个假设: (1)在向量空间 E 上的一棵正确决策树,对任意例子的分类概率同 E 中的正、反例的概率一致;(2)一棵决策树能对一例子做出正确类别判断所需的信息量为:I（p,n）=log2lpnnp如果以属性 A 作为决策树的根, A 具有 v 个值( , ,…, ) ,它将 E1V2n分为 v 个子集( , ,…, ) ,假设 中含有 Pi 个正例和 个反例,子集1E2viEi的信息熵为 I(Pi, ) ,以属性 A 为根分类后的信息熵为：i in1()(viipAI因此,以 A 为根的信息增益是 Gain (A) = I (p,n) - E(A) ID3 选择使 Gain (A) 最大(即 E(A) 最小)的属性 作为根结点对 的不同的取值对应的 E 的 v 个子集 递归调用上述过程,生成 的子结点, …，iE12,BVBID3 的基本原理是基于两类分类问题,但很容易扩展到多类设样本集S 共有 C 类样本 ,每类样本数为 pi ,( i = 1 ,2 ,3 , …c) 。

若以属性 A 作为决策树的根, A 具有 V 个值 , ,…, ,它将 E 分成 V 个子集[ ,12nV1E,…, ] ,假设 中含有 j 类样本的个数为 ,j = 1,2,…,c 那么,子集2EviEijp的信息量是 I( )j i91()*log||cijvijiPIEE以 A 为根分类的信息熵为: 1|()*()viiiI选择属性 使 E( A) 最小,信息增益也将增大理想的决策树分成 3 种: (1)叶节点数最小, (2)叶节点深度最小; (3)叶节点数量最少且叶子结点深度最小决策树的好坏,不仅影响分类的效率,而且还影响分类的准确率人们为了寻求较优的解,不得不寻求各种启发式的方法有的采用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的则扩充决策树,形成决策图如今普遍采用的是优化算法,基本思想:首先用 ID3 选择属性 F1,建立树T1,左、右子树的属性分别为 F2,F3,再以 F2,F3 为根,重建树 T2，T3;较T1,T2,T3 的结点个数,选择结点最少的树对于选择定树的儿子结点采用同样的方法递归建树尽管作者用一个实验证明能建立理想的决策树,但算法有较大的弱点:时间开销太大,因为每选择一个新的属性,算法都需要建立 3 棵决策树,从中选优。

ID3 算法举例：性格 父母教育程度 性别 类别内向外向外向内向外向内向外向外向外向内向内向内向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差此例假定要按某校学生学习成绩好坏这个概念对一个集合进行分类,该集合中用来描述学生的属性有性格、父母教育程度和性别性格的取值为外10向、内向父母教育程度取值为良好、中等和差性别的取值为男生、女生例子集中共有 12 名学生,如表所示在类别一栏,将正例即“学习成绩好”的学生用“好”标出,反例即“学生成绩差”的学生用“差”标出这些例子一开始全部包含在根结点中,为了找出当前的最佳划分属性,先须根据信息论中的公式计算训练实例集 Es 的熵值则根节点的熵值为:= 166()log2log211Entropys下面分别计算例子集中各个属性的信息赢取值对属性“性格”来说,分外向和内向两个分支当 v =“外向”时,有 4 名“外向”小学生是“学习成绩好”的,有 2 名“外向”小学生是“学习成绩差”的因此,42()loglog0.918366sEntropy性 格 ,外 向当 v =“内向”时,有 2 名“内向”小学生是“学习成绩好 ”的,有 4 名“内向”小学生是“学习成绩差”的。

因此, 42()loglog0.9183664sntropy性 格 ,内 向所以根据“性格”属性来进行例子集分类的信息赢取值为:Gain(Es)=Entropy(Es)-Entropy(Esv)=-(*.+.)=0.8172同理,对“父母教育程度”来说:Gain(Es, 父母教育程度)=0.4591 ;对“性别”来说:Gain( Es,性别) = 0 因为 Gain ( Es ,性别) < Gain ( Es ,性格) < Gain ( Es , 父母教育程度) 可以看出以“父母教育程度”这个属性进行例子集分类的信息赢取值最大,于是“父母教育程度”就被选为用于划分的属性,得到如下图所示的决策树父母教育程度良差中内向 ， 良 ， 女生 ： 好外向 ， 良 ， 男生 ： 好内向 ， 良 ， 男生 ： 好外向 ， 良 ， 女生 ： 好内向 ， 中 ， 女生 ： 差外向 ， 中 ， 男生 ： 好内向 ， 中 ， 男生 ： 差外向 ， 中 ， 女生 ： 差内向 ， 差 ， 女生 ： 差外向 ， 差 ， 女生 ： 好内向 ， 差 ， 男生 ： 差外向 ， 差 ， 男生 ： 差11现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差”的小学生的“学习成绩好坏”,因此必须对“中”和“差”两个分支的实例组成的例子集(共 8 个例子) 重复上述计算过程。

这里简化计算过程,算出:Gain(Es,性格)=0.3113 和 Gain(Es,性别) =0.2045因为 Gain ( Es ,性别) < Gain ( Es ,性格) ,所以用属性 “性格”作第二步划分,于是得到如下图所示的决策树父母教育程度良差中内向 ， 良 ， 女生 ： 好外向 ， 良 ， 男生 ： 好内向 ， 良 ， 男生 ： 好外向 ， 良 ， 女生 ： 好内向 ， 中 ， 女生 ： 差内向 ， 中 ， 男生 ： 差内向 ， 差 ， 女生 ： 差内向 ， 差 ， 男生 ： 差性格内向外向外向 ， 中 ， 男生 ： 好外向 ， 中 ， 女生 ： 差性格内向外向外向 ， 差 ， 女生 ： 好外向 ， 差 ， 男生 ： 差现在只有“父母教育程度”为“中”和“差”的“外向”小学生还没有明确类别,它们要用属性“性别”来进一步划分最终得到的决策树如下图所示。