广工数据挖掘复习要点汇总

1、-第一章 绪论1.数据挖掘要解决的问题：面对高维，复杂，异构的海量数据，如何集中获取有用的信息和知识。2.数据挖掘定义：·技术层面上：数据挖掘就是从大量数据提取有用信息的过程；·商业层面上：数据挖掘就是对大量业务数据进展抽取，转换和分析以及建模处理，从中提取辅助商业决策的关键性数据。3.数据挖掘的特征：先前未知，有效和实用。4.数据挖掘对象：·关系数据库借助集合代数等概念和方法来处理数据库中的数据·数据仓库(数据集合，用于支持管理决策)·事务数据库每个记录代表一个事务·空间数据库·事态数据库和时间序列数据库·流数据

2、·多媒体数据库·文本数据库·万维数据库5. 数据挖掘任务：分类分析按照*种规则，聚类分析具有共性，回归分析，关联分析具有关联规则，离群点检测发现与众不同的数据，演化分析随时间变化的数据对象的趋势，序列模式挖掘分析前后序列模式6.数据挖掘过程：数据清洗，数据集成考虑数据一致性和冗余，数据选择，数据转换，数据挖掘，模式评估，知识表示。例题：1.1 数据挖掘处理的对象有哪些.请从实际生活中举出至少三种。答：数据挖掘处理的对象是*一专业领域中积累的数据，对象既可以来自社会科学,又可以来自自然科学产生的数据,还可以是卫星观测得到的数据。数据形式和构造也各不一样,可以是传统的

3、关系数据库,可以是面向对象的高级数据库系统,也可以是面向特殊应用的数据库,如空间数据库、时序数据库、文本数据库和多媒体数据库等,还可以是Web 数据信息。实际生活的例子：电信行业中利用数据挖掘技术进展客户行为分析，包含客户通话记录、通话时间、所开通的效劳等，据此进展客户群体划分以及客户流失性分析。天文领域中利用决策树等数据挖掘方法对上百万天体数据进展分类与分析，帮助天文学家发现其他未知星体。制造业中应用数据挖掘技术进展零部件故障诊断、资源优化、生产过程分析等。市场业中应用数据挖掘技术进展市场定位、消费者分析、辅助制定市场营销策略等。1.5定义以下数据挖掘功能：关联、分类、聚类、演变分析、离群点

4、检测。使用你熟悉的生活中的数据，给出每种数据挖掘功能的例子。答：关联是指发现样本间或样本不同属性间的关联。例如，一个数据挖掘系统可能发现的关联规则为：major(*, “puting science)owns(*, “personal puter)support=12%, confidence=98% 其中，* 是一个表示学生的变量。该规则指出主修计算机科学并且拥有一台个人计算机的学生所占比例为12%，同时，主修计算机专业的学生有98%拥有个人计算机。分类是构造一系列能描述和区分数据类型或概念的模型(或功能)，分类被用作预测目标数据的类的标签。例如，通过对过去银行客户流失与未流失客户数据的分析

5、，得到一个预测模型，预测新客户是否可能会流失。聚类是将数据划分为相似对象组的过程，使得同一组中对象相似度最大而不同组中对象相似度最小。例如，通过对*大型超市客户购物数据进展聚类，将客户聚类细分为低值客户、高值客户以及普通客户等。数据演变分析描述和模型化随时间变化的对象的规律或趋势，尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、分类、或预测，这种分析的明确特征包括时间序列数据分析、序列或周期模式匹配、和基于相似性的数据分析。离群点检测就是发现与众不同的数据。可用于发现金融领域的欺诈检测。第二章 数据处理根底1.数据及数据类型：数据是数据库存储的根本对象，数据类型：标称属性，序数属性，

6、区间属性，比率属性。2. 数据集分为三类：记录数据，基于图形的数据和有序的数据集。补充：数据统计特征：均值，中位数，中列数数据集中最大和最小值的平均值，众数出现频率最高的值，截断均值指定010间的百分位数p，丢弃高端的和低端的p/2%的数据，然后按照计算均值那样计算3. 数据挖掘的效果直承受到数据源的影响。4.数据清理的目的：试图填充缺失数据，去除噪声并识别离群点，纠正数据中的不一致值。5. 缺失值的处理方法：分析时忽略元组，分析时忽略属性列，估计缺失值人工填写缺失数据，估计缺失值自动填充缺失数据。6.噪声平滑方法：分箱，聚类。7. 数据聚合的目的：将两个或多个数据源中的数据，存放在一个一致的

7、数据存储设备中。8.数据变换的容：数据泛化把学科分为理学和工学，忽略细节，规化，特征构造集中数据特征构造新的特征，减少特征维数，数据离散化出现了熵计算。9.数据归约：·维度归约和特征变换：维度归约可以删除不相关的特征并降低噪声，降低维度灾难风险，降低数据挖掘的时间复杂度和空间复杂度，特征变幻可以反响出数据的不同视角的不同特征。·抽样：长期用于数据的事先调查和最终的数据分析，在数据挖掘中，抽样是选择数据子集进展分析的常用方法。1） 无放回的简单随机抽样方法2） 有放回的简单随机抽样方法3） 分层抽样方法·特征选择：从一组特征的集合中选取最具有代表性的特征子集，使其保

8、存原有数据的大局部特征，正确区分数据集中的每个数据对象。根据特征选择过程与后续数据挖掘任务的关联可分为三种方法：过滤，封装和嵌入。根据是否用到类信息的指导，分为监视式，无监视式和半监视式特征选择·特征子集选择的搜索策略：逐步向前选择从空集开场，逐步添加，逐步向后删除从整个属性集开场，逐个删除，向前选择和向后删除相结合,决策树归约。特征搜索过程中不可缺少的环节就是逐步评估。*数据预处理方法：数据清理，数据集成，数据变换，数据归约，数据离散化例题：2.5 假定用于分析的数据包含属性age，数据元组中age 的值如下(按递增序)：13,15,16,16,19,20,20,21,22,22,

9、25,25,25,25,30,33,33,33,35,35,35,35,36,40,45,46,52,70。(a) 使用按箱平均值平滑对以上数据进展平滑，箱的深度为3。解释你的步骤。评论对于给定的数据，该技术的效果。 (b) 对于数据平滑，还有哪些其它方法. 答：(a)数据元组中age 的值如下(按递增序)：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,33,35,35,35,35,36,40,45,46,52,70，且箱的深度为3，划分为(等频)箱：箱1：13,15,16箱2：16,19,20箱3：20,21,22箱4：22,25,25

10、箱5：25,25,30箱6：33,33,33箱7：35,35,35箱8：35,36,40箱9：45,46,52箱10：70用箱均值光滑：箱1：15,15,15箱2：18,18,18箱3：21,21,21箱4：24,24,24箱5：27,27,37箱6：33,33,33箱7：35,35,35箱8：37,37,37箱9：48,48,48箱10：70；(b)对于数据平滑，其它方法有：(1)回归：可以用一个函数(如回归函数)拟合数据来光滑数据；(2)聚类：可以通过聚类检测离群点，将类似的值组织成群或簇。直观地，落在簇集合之外的值视为离群点。2.6 使用习题2.5 给出的age数据，答复以下问题： (a

11、) 使用min-ma*规化，将age 值35 转换到0.0，1.0区间。 (b) 使用z-score 规化转换age 值35，其中，age 的标准偏差为12.94 年。 (c) 使用小数定标规化转换age 值35。 (d) 指出对于给定的数据，你愿意使用哪种方法。述你的理由。 答：(a)最大值为70，最小值为13，则可将35规化为：；(b)均值为30，标准差为12.94，则可将35规化为：；(c)使用小数定标规化可将35规化为：；2.17 给定两个向量对象，分别表示为p1(22，1，42，10)，p2(20，0，36，8)： (a) 计算两个对象之间的欧几里得距离(b) 计算两个对象之间的曼哈

12、顿距离 (c) 计算两个对象之间的闵可夫斯基距离，用*=3(d) 计算两个对象之间的切比雪夫距离答：(a) 计算两个对象之间的欧几里得距离(b) 计算两个对象之间的曼哈顿距离(c) 计算两个对象之间的闵可夫斯基距离，其中参数r=3(d)切比雪夫距离：=62.8以下是一个商场所销售商品的价格清单(按递增顺序排列，括号中的数表示前面数字出现次数)1(2)、5(5)、8(2)、10(4)、12、14(3)、15(5)、18(8)、20(7)、21(4)、25(5)、28、30(3)。请分别用等宽的方法和等高的方法对上面的数据集进展划分。答：(1)等宽方法：划分为3个数据集，每个数据集的宽度为价格10

13、。价格在110之间出现次数为13；价格在1120之间出现的次数为24；价格在2130之间出现的次数为13。(2)等高方法：划分为2个数据集，每个数据集的高度为出现的次数4。出现次数14之间的价格为1、8、10、12、14、21、28、30，共8个数据；出现次数58之间的价格为5、15、18、20、25，共5个数据。2.9 讨论数据聚合需要考虑的问题。 答：数据聚合需要考虑的问题有：(1)模式识别：这主要是实体识别问题；(2)冗余：一个属性是冗余的，即它能由另一个表导出，如果属性或维的命名不一致，也可能导致冗余，可以用相关分析来检测；(3)数据值冲突的检测与处理：有些属性因表示比例或编码不同，会

14、导致属性不同。第三章 分类与回归1.分类：分类是数据挖掘中的主要手段，其任务是对数据集进展学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，把类标号未知的样本映射到*个预先给定的类标号中。2.分类模型学习方法：基于决策树的分类方法，贝叶斯分类方法，k-最近邻分类方法，神经网络方法。3.决策树的概念与构建：决策树是一种树形构造，包括决策节点，分支节点和页节点三个局部。·决策节点：代表*个测试，通常对应带分类对象的*个属性。该属性上的不同测试结果对应一个分支。·叶节点：每个叶节点对应一个类标号，表示一种可能的分类结果。·决策树的构建：1） 属性的选择很重

15、要，一般要最大限度地增大样本集纯度2） 获得大小适合的决策树3） 使用ID3等经典算法构建决策树4.分类模型的评价：分类过程一般分为两步：第一步是利用分类算法对训练集进展学习，建立分类模型；第二步是用分类模型对标号未知的测试数据进展分类。5.分类模型性能评价指标：1分类准确率：指模型正确地预测新的或先前未知的数据的类标号的能力。影响分类准确率的因素：训练数据集，记录的数目，属性的数目，属性中的信息，测试数据集记录的分布情况2计算复杂度：决定着算法执行的速率和占用的资源，依赖于具体的实现细节和软、硬件环境。3可解释性：分类结果只有可解释性好，容易理解，才能更好地用于决策支持。4可伸缩性。5稳定性

16、：指不会随着数据的变化而发生剧烈变化。6强壮性：指数据集含有噪声和空缺值的情况下，分类器正确分类数据的能力。6.分类模型的误差：1训练误差和泛化误差。7.评估分类模型的性能的方法：1保持方法：以无放回抽样方式把数据集分为两个相互独立的子集，训练集2/3和测试集1/3；2随机子抽样：保持方法的屡次迭代；3k-折穿插验证。例题：3.1 考虑表3-23所示二元分类问题的数据集。表3-23 习题3.4数据集AB类标号TF+TT+TT+TF-TT+FF-FF-FF-TT-TF-(1) 计算按照属性A和B划分时的信息增益。决策树归纳算法将会选择那个属性.(2) 计算按照属性A和B划分时Gini系数。决策树

17、归纳算法将会选择那个属性.答：按照属性A和B划分时，数据集可分为如下两种情况：A=TA=F+40-33B=TB=F+31-15划分前样本集的信息熵为 E=-0.4log220.6=0.9710按照属性A划分样本集分别得到的两个子集(A取值T和A取值F)的信息熵分别为:按照属性A划分样本集得到的信息增益为：按照属性B划分样本集分别得到的两个子集(B取值T和B取值F)的信息熵分别为:按照属性B划分样本集得到的信息增益为：因此，决策树归纳算法将会选择属性A。(2) 划分前的Gini值为G=1-0.42-0.62=0.48按照属性A划分时Gini指标:Gini增益按照属性B划分时Gini指标:Gini

18、增益因此，决策树归纳算法将会选择属性B。3.2 考虑表3-24数据集，请完成以下问题：表3-24 习题3.7数据集记录号ABC类1000+2001-3011-4011-5001+6101+7101-8101-9111+10101+(1) 估计条件概率，。(2) 根据(1)中的条件概率，使用朴素贝叶斯方法预测测试样本(A=0，B=1，C=0)的类标号；(3) 使用Laplace估计方法，其中p=1/2，l=4，估计条件概率，。(4) 同(2)，使用(3)中的条件概率(5) 比较估计概率的两种方法，哪一种更好，为什么.答：(1)=3/5=1/5=2/5=2/5=1(2) 假设P(A=0,B=1,C

19、=0)=K则K属于两个类的概率为：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0|+)×P(+)/K(贝叶斯算法)=P(A=0|+)P(B|+)P(C=0|+)×P(+)/K=0.4×0.2×0.2×0.5/K=0.008/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=0|-)×P(-)/K=P(A=0|-)P(B|-)P(C=0|-)×P(-)/K=0.4×0.2×0×0.5/K=0/K则得到，此样本的类标号是+。(3)P(A|+)=(3+2)/(5+4)=5/9P

20、(A|-)=(2+2)/(5+4)=4/9P(B|+)=(1+2)/(5+4)=1/3P(B|-)=(2+2)/(5+4)=4/9P(C|-)=(0+2)/(5+4)=2/9(4) 假设P(A=0,B=1,C=0)=K则K属于两个类的概率为：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(+)/K=P(A=0|+)P(B|+)P(C=0|+)×P(+)/K=(4/9) ×(1/3) ×(1/3) ×0.5/K=0.0247/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(-)/K=P(A=0|

21、-)P(B|-)P(C=0|-)×P(-)/K=(5/9) ×(4/9) ×(2/9) ×0.5/K=0.0274/K则得到，此样本的类标号是-。(5)当条件概率为0的时候，条件概率的预测用Laplace估计方法比较好，因为我们不想整个条件概率计算结果为0.第四章 聚类分析1.聚类：聚类就是将数据集划分为由假设干相似对象组成的多个组或簇的过程，使得同一组中的对象的相似度最大化，不同组中的相似度最小化。或者说聚类是由彼此相似的一组对象构成的集合。分类：分类是数据挖掘中的主要手段，其任务是对数据集进展学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类

22、标号，把类标号未知的样本映射到*个预先给定的类标号中。记：聚类和分类的区别2.典型的聚类分析任务包括的步骤：1模式表示聚类算法的根底，2适合于数据领域的模式相似性定义(是聚类分析最根本的问题)，3聚类或者划分算法聚类分析的核心，4数据摘要如有必要，5输出结果的评估，有效性的评估如有必要3. 数据挖掘对聚类的典型要求：1可伸缩性，2处理不同类型属性的能力3发现任意形状的聚类4用于决定输入参数的领域知识最小化5处理噪声数据的能力6对输入记录的顺序不敏感7高维度8基于约束的聚类9可解释性和可用性。4.典型聚类方法：1划分方法每个划分表示一个聚类2层次方法将数据对象组成一个聚类树3基于密度的方法绝大多

23、数划分方法都是基于对象之间的距离大小进展聚类4基于模型的方法试图将给定数据与*个数学模型搭成最正确拟合5基于图的聚类算法利用图的许多重要性质和特性5.k-means算法，层次聚类算法的优缺点：1k-means算法：优点：算法描述容易，实现简单快速；缺乏：·簇的个数要预先给定，·对初始值的依赖极大·不适合大量数据的处理·对噪声点和离群点很敏感·很难检测到“自然的簇。2层次聚类算法：BIRCH算法：优点：利用聚类特征树概括了聚类的有用信息，节省存空间；具有对象数目呈线性关系，可伸缩性和较好的聚类质量。缺乏：·每个节点只能包含有限数目的条目

24、，工作效率受簇的形状的影响大。CURE算法：优点：对孤立点的处理能力强；·适用于大规模数据处理，伸缩性好，没有牺牲聚类质量；缺点：算法在处理大量数据时必须基于抽样，划分等技术。ROCK算法：优点：分类恰当，可采用随机抽样处理数据；缺点：最坏的情况下时间复杂度级数大。基于密度的聚类算法：可识别具有任意形状不同大小的簇，自动确定簇的数目，分离簇和环境噪声，一次扫描即可完成聚类，使用空间索引时间复杂度为O(NlbN)例题：1.假设描述学生的信息包含属性：性别，籍贯，年龄。有两条记录p、q及两个簇C1、C2的信息如下，分别求出记录和簇彼此之间的距离。k-means算法的拓展p=男，18 q=

25、女，20C1=男：25，女：5；：20，：6，：4；19C2=男：3，女：12；：12，：1，：2；24解：按定义4-3，取*=1，得到的各距离如下：d(p，q)=1+1+20-18=4d(p，C1)=1-25/30+1-20/30+19-18=1.5d(p，C2)=1-3/15+1-0/15+24-18=7.8d(q，C1)=1-5/30+1-6/30+20-19=79/30d(q，C2)=1-12/15+1-1/15+24-20=77/15d(C1，C2)=1-25*3+5*12/30*15+1-6*1/30*15+24-19=1003/1504.1 什么是聚类.简单描述如下的聚类方法：划

26、分方法，层次方法，基于密度的方法，基于模型的方法。为每类方法给出例子。答：聚类是将数据划分为相似对象组的过程，使得同一组中对象相似度最大而不同组中对象相似度最小。主要有以下几种类型方法：(1)划分方法给定一个有N个元组或者记录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足以下条件：第一，每一个分组至少包含一条记录；第二，每一条记录属于且仅属于一个分组(注意：这个要求在*些模糊聚类算法中可以放宽)；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录

27、越近越好，而不同分组中的记录越远越好。使用这个根本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。(2)层次方法这种方法对给定的数据集进展层次似的分解，直到*种条件满足为止。具体又可分为“自底向上和“自顶向下两种方案。例如在“自底向上方案中，初始时每一个数据记录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者*个条件满足为止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。(3)基于密度的方法基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离，而是基于密度的。这样就能抑制基于

28、距离的算法只能发现“类圆形的聚类的缺点。这个方法的指导思想就是：只要一个区域中的点的密度大过*个阈值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。(4)基于模型的方法基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在假定就是：目标数据集是由一系列的概率分布所决定的。基于模型的方法主要有两类：统计学方法和神经网络方法(SOM)。4.10 下表中列出了4个点的两个最近邻。使用SNN相似度定义，计算每对点之间的SNN相似度。点第一个近邻第二个近邻1

29、43234342431答：SNN即共享最近邻个数为其相似度。点1和点2的SNN相似度：0没有共享最近邻点1和点3的SNN相似度：1共享点4这个最近邻点1和点4的SNN相似度：1共享点3这个最近邻点2和点3的SNN相似度：1共享点4这个最近邻点2和点4的SNN相似度：1共享点3这个最近邻点3和点4的SNN相似度：0没有共享最近邻第五章 关联分析1.FP-tree基于FP-growth算法2.Apriori算法的例子(最小支持度计数阈值=2)3.概述：在关联分析中，包含0个或多个项的集合称为项集，一个包含k个数据项的项集就称为k-项集。假设一个项集的支持度大于或等于*个阈值，则称为频繁项集。*：1

30、产生频繁项集：发现满足最小支持度阈值的所有项集，即频繁项集。 2产生规则：从上一步发现的频繁项集中提取大于置信度阈值的规则，即强规则。5.1 列举关联规则在不同领域中应用的实例。答：在医学领域：发现*些病症与*种疾病之间的关联，为医生进展疾病诊断和治疗提供线索； 在商业领域：发现商品间的联系，为商场进展商品促销及摆放货架提供辅助决策信息； 在地球科学领域：提醒海洋、陆地和大气过程之间的关系。5.2 给出如下几种类型的关联规则的例子，并说明它们是否是有价值的。(a)高支持度和高置信度的规则；(b)高支持度和低置信度的规则；(c)低支持度和低置信度的规则；(d)低支持度和高置信度的规则。5.3 数

31、据集如表5-14所示：表5-14 习题5.3数据集Customer IDTransaction IDItems Bought11223344550001002400120031001500220029004000330038a, d, ea, b, c, ea, b, d, ea, c, d, eb, c, eb, d, ec, da, b, ca, d, ea, b, e(a) 把每一个事务作为一个购物篮，计算项集e, b, d和b, d, e的支持度。(b) 利用(a)中结果计算关联规则b, de 和 eb, d的置信度。置信度是一个对称的度量吗.(c) 把每一个用户购置的所有商品作为一个

32、购物篮，计算项集e, b, d和b, d, e的支持度。(d) 利用(b)中结果计算关联规则b, de 和 eb, d的置信度。置信度是一个对称的度量吗.答：(a) s(e) = 8/10 =0.8 ; s(b,d) = 2/10 = 0.2 ; s(b,d,e) = 2/10 = 0.2. (b) c(b,d->e) = s(b,d,e)/s(b,d) = 0.2/0.2 = 1;c(e->b,d) =s(b,d,e)/s(e) = 0.2/0.8 = 0.25.由于c(b,d->e)c(e->b,d)，所以置信度不是一个对称的度量。 (c)如果把每一个用户购置所有的

33、所有商品作为一个购物篮，则 s(e) = 4/5 =0.8 ; s(b,d) = 5/5 = 1 ; s(b,d,e) = 4/5 = 0.8.(d) 利用c中结果计算关联规则b, de 和 eb, d的置信度,则 c(b,d->e) = 0.8/1 = 0.8 c(e->b,d) = 0.8/0.8 = 1置信度不是一个对称的度量5.6 考虑如下的频繁3-项集：1, 2, 3，1, 2, 4，1, 2, 5，1, 3, 4，1, 3, 5，2, 3, 4，2, 3, 5，3, 4, 5。(a)根据Apriori算法的候选项集生成方法，写出利用频繁3-项集生成的所有候选4-项集。(

34、b)写出经过剪枝后的所有候选4-项集答：(a)利用频繁3-项集生成的所有候选4-项集： 1,2,3,4 1,2,3,5 1,2,4,5 1,3,4,5 2,3,4,5 (b)经过剪枝后的所有候选4-项集： 1,2,3,4 1,2,3,55.7 一个数据库有5个事务，如表5-15所示。设min_sup=60%，min_conf = 80%。表5-15 习题5.7数据集事务ID购置的商品T100T200T300T400T500M, O, N, K, E, YD, O, N, K, E, YM, A, K, EM, U, C, K, YC, O, O, K, I ,E(a) 分别用Apriori算法和FP-growth算法找出所有频繁项集。比较两种挖掘方法的效率。(b) 比较穷举法和Apriori算法生成的候选项集的数量。(c) 利用(1)所找出的频繁项集，生成所有的强关联规则和对应的支持度和置信度。答：(1) 频繁1-项集：M,O,K,E,Y 频繁2-项集：M,K， O,K， O,E，K,Y，K,E 频繁3-项集：O,K,E (2)穷举法：M=2k-1=211-1=2047 Apriori算法：23(3) O,K>E，支持度0.6，置信度1 O,E>k，支持度0