数据挖掘期末复习资料.doc

数据挖掘期末复习资料2009-02-21 20:38:37|分类： 读书笔记 |标签： |字号大中小订阅 题型：填空（20空）、判断（20分）、简答（5个：预处理方法、决策树、朴素贝叶斯过程、其他一些知识内容）、大题（算法：关联分析、分类、决策树、ID3算法、贝叶斯方法、A神经网络、聚类回归占得比较小）概述一、数据挖掘是一个多学科领域，具体涉及到哪些相关学科？数据库及相关领域知识。二、什么是数据挖掘，产生的背景，典型的数据挖掘系统的主要成分？数据挖掘定义：数据挖掘是从存放在数据库，数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。 典型的数据挖掘系统的主要成分：1.数据库，数据仓库或其他信息库；2.数据库或数据仓库服务器：3.知识库；4.数据挖掘引擎；5.模式评估模块；6.图形用户界面。 三、数据挖掘的功能有哪些？数据挖掘功能-可以挖掘什么类型的模式。数据挖掘任务：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性；预测性挖掘任务在当前数据上进行推断。 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。其模式类型介绍如下：（1）、概念/类描述：特征化和区分。用汇总的、简洁的、精确的方式描述每个类和概念，称这种描述为类/概念描述，通过三种方式得到：1）数据特征化 2）数据区分 3）数据特征化和比较。 (2)关联分析：发现规则，这些规则展示属性-值频繁地在给定数据集中一起出现的条件。关联规则的含义为：满足X中条件的数据库元组多半也满足Y中条件。包括多维关联规则和单维关联规则。 (3)分类和预测：分类与预测是两种数据分析形式，它们可用于抽取能够描述重要数据集合或预测未来数据趋势的模型。分类是找出描述并区分数据类或概念的模型或函数，以便能用模型预测类标记未知的对象类。如：可以构造一个分类模型来对银行贷款进行风险评估（安全或危险）；也可建立一个预测模型以利用顾客收入与职业（参数）预测其可能用于购买计算机设备的支出大小。 (4)聚类分析：它考虑的是数据对象，将数据对象根据一定的规则比如，最大化类内的相似性，最小化类间的相似性进行分组或聚类。同类相聚，异类相离 (5)孤立点分析：有些对象与数据的一般行为或模式不一致，称这些数据对象是孤立点。(6)演变分析(时序分析)：描述行为随时间变化的数据对象的规律或趋势，并对其建模，比如，股票的演变规律。 四、数据挖掘的性能问题包括哪3个方面？五、知识发现包括哪些过程？知识发现的过程：1）数据清理（消除噪声或不一致数据）2）数据集成（多种数据源可以组合在一起）3）数据选择（从数据库中检索与分析任务相关的数据）4）数据变换（数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作）5）数据挖掘（基本步骤，使用智能方法提取数据模式）6）模式评估（根据某种兴趣度度量，识别表示知识的真正有趣的模式）7）知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识） 六、数据、信息、知识之间的区别和联系数据：就是能够被计算机处理的任何事物（事实、数字、文本等）数据=事实的记录操作和交易数据：如销售、价格、库存、薪水册等非操作的数据：如工业销售、预测数据、宏观经济数据元数据（Meta data：描述数据自身的数据，如逻辑数据库设计或数据字典定义信息:数据提供的模式、关联、联系等信息。信息是对数据的提炼；信息=数据+意义如：对于零售终端的分析能够获得什么产品在什么时候卖出的信息。知识:从信息中提取出有关历史模式、一般规律、和未来趋势的知识知识是让从定量到定性的过程得以实现的、抽象的、逻辑的东西。知识是需要通过信息使用归纳、演绎得方法得到。知识只有在经过广泛深入地实践检验，被人消化吸收，并成为了个人的信念和判断取向之后才能成为知识，这一点使得知识和信息往往混杂在一起。如：通过分析超市的销售汇总信息，来提供用户购买行为的知识，从而可以知道哪种促销方式是最有效的。数据仓库一、数据仓库是一个 面向主题的、集成的、非易失的、时变的有组织的数据集合。二、OLAP的典型操作有哪些？切片切块、上卷下钻、旋转转轴三、多维数据模型通常采用哪三种模式？星型模式、雪花模式、事实星座四、冰山立方体的相关概念仅计算满足最小支持度阈值的单元，这种部分物化的单元称为冰山立方体。HAVING COUNT(*) = minsup为冰山条件Motivation：v 由于立方体单元在多维空间中的分布常常是稀疏的，因此大量的立方体空间可能被大量具有很低度量值得单元占据。v 仅需物化数据立方体单元的一小部分那些满足阈值的单元v 减轻计算数据立方体中不重要的聚集单元的负担。五、数据仓库和数据库有什么区别和联系？1、数据仓库中的数据时间期限要远远长于操作型系统中的数据时间期限操作型系统含有“当前值”数据，时间期限一般是60-90天；数据仓库从历史的角度提供信息，其中的数据仅仅是一系列某一时刻生成的复杂的快照，时间期限通常是5-10年2、 数据仓库中的键码结构数据仓库中的关键结构，隐式或显式地包含时间元素操作型系统的键码结构可能不包括时间元素3、 反应时间变化的4、数据仓库是非易失的数据仓库总是物理地分别存放数据数据仓库中不进行操作型环境中的数据更新数据仓库不需要事务处理、恢复和并发控制机制数据仓库通常只需要两种数据访问：数据的初始化装入和数据访问4、 相对稳定的数据预处理一、数据预处理包括哪些过程数据清理、数据集成、数据变换和数据规约二、对于每种预处理过程都有哪些方法，处理的思想是怎么样的，比如针对缺失值有哪些方法？针对数据规范化有哪些方法？数据清理中如何处理噪声数据等。数据清理：就是用其例程通过填写空缺的值，平滑噪声数据，识别，删除孤立点，并解决不一致来清理数据。其基本方法为：（1）空缺值1）忽略元组 ，2）人工填写空缺值 3）使用一个全局常量填充空缺值，比如用一个常数（Unknown)来替换所有空缺的值。4）使用属性的平均值填充空缺值 5）使用与给定元组属同类的所有样本的平均值 6）使用最可能的值填充空缺值，可以使用回归，或判定树确定推理获得（2）噪声数据：一个测量变量中的随机错误或偏差。可以用以下方法1）分箱 包括按箱平均值平滑，即就是将属性值根据等深，例如每箱3个进行分箱，然后用这三个值的平均值代替箱中的值。类似有按箱均值平滑，按箱边界平滑；Price的排序后数据 (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* 划分为等频箱:- 箱 1: 4, 8, 9, 15-箱2: 21, 21, 24, 25-箱3: 26, 28, 29, 34* 用箱均值光滑:-箱1: 9, 9, 9, 9 -箱2: 23, 23, 23, 23 -箱3: 29, 29, 29, 29* 用箱边界光滑:- Bin 1: 4, 4, 4, 15- Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 342）回归，让数据适合一个函数（如回归函数）来平滑数据。3）聚类 聚类将相似的值组织成群或类，落在群或类外的值就是孤立点，也就是噪声数据；不一致数据：许多情况下，所记录的数据可能不一致，这是多方面的因素，比如，由于编码或表示不同，在数据集成的时候，就有可能造成不一致。规范化的方法：1）最小最大规范化 ：对原始数据进行变换。假定A的属性最大值和最小值分别是MAX，MIX ，设A 中的任一值是V，则V的值经过规范化后则为：V=（V-MIN）/（MAX-MIX）*（NEW_max-NEW_min)+NEW_min 其中规范化后的区间是NEW_min， NEW_max例如:income的最大，最小值分别为9000，2000，则将它的值映射到0，1时，若income的值6800规范后为： （6800-2000）/（9000-2000）*（1-0）+0=0.6862）z-score规范化（或零均值规范化）：就是属性A的值基于A的平均值和标准差规范。假设A的值V规范后为V，则公式为： V=（V-AVG（A）/A的标准差假设属性income的平均值和方差分别为：5400，1600，则值7360的规范后的值为： （7360-5400）/1600=1。2253）小数定标化：就是科学表示法的形式，将属性的值映射到0，1之间。将小数点的位置规范化，小数点的移动根据属性的最大绝对值。如将A属性的值35规范后为：35/100=0.35属性构造：是由给定的属性构造和添加新的属性，以有利于挖掘。比如，我们根据属性heigh 和 width可以构造 area属性。通过这种组合属性，属性构造可以发现关于数据属性间联系的丢失信息，这对知识发现有用的。数值归约（1）-直方图：数值归约：通过用替代的，较小的数据表示形式来减少数据量。直方图：使用分箱技术近似数据分布，数值归约（2）-聚类数据挖掘的各种算法掌握每种算法的基本思想，优缺点，是否是有监督的挖掘方法等？一、 Apriori算法的基本思想，如何采用Apriori来挖掘频繁模式 需要了解的基础知识：关联规则判断标准1、支持度sup(.)：表示在购物篮分析中同时包含关联规则左右两边物品的交易次数百分比，即支持这个规则的交易的次数百分比。 规则X?Y在交易数据集D中的支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为： support(X?Y)= P（XY）2、置信度confidence(.)：是指购物篮分析中有了左边商品，同时又有右边商品的交易次数百分比，也就是说在所有的购买了左边商品的交易中，同时又购买了右边商品的交易概率。? 连接:用Lk-1自连接得到Ck? 修剪:一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。Apriori 算法：使用候选产生频繁项集例1：假设最小支持度为30%，最小置信度为60%。第一步：产生频繁1-项集（即满足最小支持度要求）；第二步：再次扫描数据库，产生后候选2-项集：第三步：产生频繁3-项集； 第四集：从满足条件的频繁2-项集中构造关联规则：第五步：重复第二步，产生候选3-项集；例2：数据库面向5个事物，min-sup=60%,min-conf=80%.TID购买商品T100M,O,N,K,E,YT200D,O,N,K,E,YT300M,A,K,E T400M,U,C,K,YT500C,O,O,K,I,E（1） 分别用Apriori算法找出所有频繁项集（2） 列举所有与下面的元规则匹配的强关联规则（给出支持度S和置信度C），其中，X代表顾客的变量，item代表项的变量（如“A”，“B”等）对于? xtransaction,buys(X,item1)buys(X,item2)=buys(X,item3) S,C解：（1）、用Apriori算法找出所有频繁项集。原数据库D如下：TIDItemsT100M O N K E YT200D O N K E Y T300M A K E T400M U C K Y T500C O O K I E 扫描D后，得到候选1-项集C1，如下所示： ItemsetMONKEYDAUCISup33 2 54311121从而得到频繁一项集L1：itemsetsupM3O3K5E4Y3再次扫描D后，得到候选2-项集C2：ItemsetM，OM,KM,EM,YO,KO,EO,YK,EK,YE,YSup1322332432根据上面候选2-项集，产生频繁2-项集L2：ItemsetM,KO,KO.EK,EK,YSup33343再次扫描D后，得到候选3-项集C3：ItemsetM,O,KM ,K,EM,K,YO,K,EO,K,YK,E,YO,E,YSup1223222根据上面候选3-项集，产生频繁3-项集L3：ItemsetSupO,K,E3综上所述，得到所有的频繁项集如下所示：频繁1-项集：M;O;K;E;Y.频繁2-项集：M,K;O,K;O,E;K,E;K,Y.频繁3-项集：O,E,K.（2）、从上面得出的频繁3-项集中，构造如下关联规则： buys(X,O)buys(X,E)=buys(X,K) support=3/5=60%,confidence=100% buys(X,O)buys(X,K)=buys(X,E) support=3/5=60%,confidence=100%buys(X,E)buys(X,K)=buys(X,O) support=3/5=60%,confidence=75%得到符合条件的强关联规则，即sup=60%,conf=80%,如下所示：buys(X,O)buys(X,E)=buys(X,K) support=3/5=60%,confidence=100%buys(X,O)buys(X,K)=buys(X,E) support=3/5=60%,confidence=100%二、 决策树算法的基本思想，采用ID3算法进行分类。监督式(supervised learning)的机器学习法-决策树(Decision Tree)非监督式(unsupervised learning)的机器学习法-集群分析法(Cluster Analysis)基础知识：信息论:若一事件有k种结果,对应的机率为Pi。则此事件发生后所得到的信息量I(视为Entropy)为：I=-(p1*log2(p1)+ p2*log2(p2)+ pk*log2(pk)如：设 k=4 p1=0.25,p2=0.25,p3=0.25,p4=0.25 I=-(0.25*log2(0.25)*4)=2信息获利(Information Gain) ：若分类标记(Y)分为(成功、失败)两种，X为预测变量(类别属性;k类)，n为总样本数(n1为总样本数中具成功标记的个数)，经由X变量将样本分类后mi为X=i类中的总样本个数(mi1为X=i类中具成功标记的个数)。根据变量X将n个样本分为m1,m2,mk的信息获利为:Gain(X)=I(n,n1)-E(X),其中I(n,n1)=-(n1/n)log2(n1/n)+(1-n1/n)log2(1-n1/n)E(X)=(m1/n)*I(m1,m11)+(m2/n)*I(m2,m21)+(mk/n)*I(mk,mk1) ID3算法(C4.5,C5.0)的一个例子：I(16,4)=-(4/16)*log2(4/16)+(12/16)*log2(12/16)=0.8113E(年龄)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946 Gain(年龄)=I(16,4)-E(年龄)=0.0167Decision Tree的建立过程（前面是重点，这部分看下就行了）(一)决策树的分割（二）决策树的剪枝(pruning)三、 贝叶斯方法的基本思想，采用朴素贝叶斯方法进行分类朴素贝叶斯分类法：采用监督式的学习方式，分类前必须事先知道分类形态，透过训练样本的训练学习，有效地处理未来欲分类的数据。贝叶斯定理：(i) (i)(i)(i) () n (i)(i) i=1(i)表事前机率(Prior probability)。(i)表事后机率(Posteriori probability)，事件i是一原因，是一结果。Bayes rule是一由已知结果求原因的机率。例：旅客搭乘飞机必须经电子仪器检查是否身上携带金属物品，携带金属仪器会发出声音的机会是97%，但身上无金属物品仪器会发出声音的机会是5%。若已知一般乘客身上带有金属物品的机会是30%，若某旅客经过仪器检查时发出声音，请问他身上有金属物品的机会是多少？解:设A=有金属物，B=仪器会发声则朴素贝叶斯分类法算法：1.计算各属性的条件机率P(C=cj | A1=a1,?,An=an)例一：办信用卡意愿：项目性别年龄学生身分收入办卡1男45否高 会2女3145否高会3女2030是低会4男20是低不会5女2030是中不会6女2030否中会7女3145否高会8男3145是中不会9男3145否中会10女20是低会判断(女性，年龄介于3145之间，不具学生身份，收入中等)者会不会办理信用卡。首先根据训练样本计算各属性相对于不同分类结果的条件机率：P(性别=女|办卡=会)=5/7P(性别=女|办卡=不会)=1/3 P(年龄=3145|办卡=会)=3/7P(年龄=3145|办卡=不会)=1/3 P(学生=否|办卡=会)=5/7P(学生=否|办卡=不会)=0/3P(收入=中|办卡=会)=2/7P(收入=中|办卡=不会)=2/3再应用朴素贝叶斯分类法进行类别预测：P(办卡=会)=7/10 P(女|会)P(31-45|会)P(否|会)P(中|会)=15/3430.044P(办卡=不会)=3/10P(会) P(不会)P(女|不会)P(31-45|不会)P(否|不会)P(中|不会)=0训练样本中对于(女性，年龄介于3145之间，不具学生身份，收入中等)的个人，朴素贝叶斯分类法会将其分类到会办理信用卡的类别。办理的机率是(0.044)/(0.044+0)=1 (正规化分类的结果P(会)/(P(会)+P(不会)。故使用朴素贝叶斯