数据挖掘考试重点复习.doc

_1. 了解商务智能的定义与大数据的四个基本特征；答：商务智能是企业利用数据仓库（DW）、数据挖掘（DM）、在线分析处理（OLAP）、决策支持系统（DSS）等现代信息技术对企业生产、经营过程中产生的大量结构化和非结构化数据进行收集、整理、分析，形成知识或情报，以辅助企业做出正确的决策、采取有效的商务行动、优化商务流程、全面提升商务绩效的工具、方法和技术的统称。大数据特征： （4个V）2. 理解商务智能系统的5层结构商务智能系统结构大致分为五层:1 数据源层：也可称作操作型数据层，是整个数据仓库的基础，提供了整个系统最原始的数据2 数据获取层：也可称作数据转换层，主要是把数据源层的数据通过ETCL过程转换到数据仓库中3 数据存取层：该层是按主题进行分析和对相关的数据进行挖掘的数据源，包括每一个按主题进行分类的数据集市或专门用于数据挖掘的数据仓库4 数据分析服务层：该层是数据存储和前端分析工具的桥梁5 前端展现层：用户界面3. 理解操作型与分析型系统分离的必要性以及他们的特征4. 理解维度爆炸给数据挖掘带来的困难数据过高的维度会给计算带来麻烦，在数据挖掘处理时，它会耗费很多的处理时间和内存容量。数据的高维度还使得数据间的关系也不容易察觉，增加了数据的无关属性和噪音点。5. 掌握数据仓库的定义并理解其四个方面的特征数据仓库是决策支持系统和联机分析应用数据源的结构化数据环境。数据仓库研究和解决从数据库中获取信息的问题。（数据仓库是为支持管理决策建立的，面向主题的、集成的、随时间变化的、相对稳定的数据集合。）【滔注：我觉得写括号里的会好一点】四方面特征：1 面向主题：主题是指用户使用数据仓库进行决策时所关心的重点忙面。2 集成性：在数据进入数据仓库之前，要进过统一于综合，将多个异源数据集成在一起。这一步是数据仓库建设中最关键、最复杂的一步。3 时变性：数据仓库随时间变化不断增加新的数据。4 相对稳定性：数据仓库反映的是历史的内容，而不是联机数据，主要供企业决策分析之用。6. 掌握数据挖掘的定义并描述其主要特征【数据挖掘定义】从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。数据挖掘是从大量数据中寻找其规律的技术。【主要步骤】（1）数据准备：从各种数据源中选取和集成用于数据挖掘的数据 ；（2）规律寻找：用某种方法将数据中的规律找出来；（3）规律表示：用尽可能符合用户习惯的方式将找出的规律表示出来。7. 掌握Minkowski距离，并熟练计算l1，l2，l无穷norm【L1norm】当r=1，城市街区（也称曼哈顿、出租车、L1范数）距离；【L2norm】当r=2，欧几里得距离；【Lnorm】当r=，上确界距离，这是对象属性之间的最大距离。8. 理解Hunts算法的基本过程通过将训练记录相继划分成较纯的子集,以递归方式建立决策树。设Dt是与节点t相关联的训练记录集,而Y= y1,y2,yc是类标号,Hunt算法的递归定义如下:(1)如果Dt中所有记录都属于同一个类yt,则t是叶节点,用yt标记。(2)如果Dt中包含属于多个类的记录,则选择一个属性测试条件,将记录划分成较小的子集。对于测试条件的每个输出,创建一个子女节点,并根据测试结果将Dt中的记录分布到子女节点中。然后,对于每个子女节点,递归地调用该算法。9. 掌握吉尼系数、熵的定义，会计算其最大值与最小值，理解信息增益在构造决策树时的意义【基尼系数、熵是度量不纯度的方法】GINI系数和熵都是越小，代表所分的节点属性越纯，最小可取到0，表示这个节点中只有一个类。当一个节点中有n个父节点，而且能分出n个子节点，GINI系数取到最大值，为1-1/n. 熵也取到最大值 log2 n （滔注：那个2是角标，不是log2n ！）【基尼值的性质】：越大越不纯，越小越纯，0最纯，1-1/n最不纯。b.子节点基尼值c.最大值、最小值（最小值表示最纯，最大值表示最不纯）【熵】在信息领域熵被用来衡量一个随机变量出现的期望值。熵是对信息的不确定性的度量。熵越低，意味着传输的信息越少。【熵的性质】：熵是衡量节点一致性的函数。熵大于等于0，当且仅当p1=p2=pn时，熵最大，纯的节点熵是0.【信息增益】当选择熵作为公式的不纯性度量时，熵的差就是所谓的信息增益。信息增益描述了当使用Q进行编码时，再使用P进行编码的差异。通常P代表样本或观察值的分布，也有可能是精确计算的理论分布。Q代表一种理论，模型，描述或者对P的近似。当纯度高达1时（即只有一种数据类型），熵最小，为0；当其中的各类数据均匀分布时，熵最大，为-log2p（j|t）。10. 理解了解最邻近分类的基本思想，邻近分类的前提条件与分类过程【近邻分类法】是基于类比学习，即通过将给定的检验元组与和它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元祖代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，近邻分类法搜索模式空间，找出最接近未知元组的k个训练元组。这k个训练元组是未知元组的k个“最近邻”。一句话概述：点x的k-最近邻分类就是离点x的欧式距离最近的k个点的集合。 三个前提条件：训练集存在内存中；给定距离度量指标；给定K值分类过程：1 计算未知点与其他训练集的距离 2找到K个最邻近的邻近组 3用邻近组的分类标签来决定未知点所在组的标签。11. 了解分类中的过拟合及产生的原因【过度拟合数据】当决策树变大时，测试误差会越来越小，而训练误差会越来越大，测试集产生的决策树与实际会不符。【产生的原因】（1） 噪声导致的过分拟合（2） 决策树的复杂程度超过了需要的程度，会产生过度拟合（3） 训练误差的减小已经对结果没有更多意义但却依然在计算，会产生过度拟合（4） 没有更多的属性来减小样本误差，会产生过度拟合12. 理解关联规则及支持与置信度的定义，并熟练计算支持度与置信度【关联规则】关联规则是形如XY的蕴涵式，其中，X和Y都是事务数据集。关联规则的强度可以用它的支持度和置信度度量。【支持度Support】事务数据库中既包含X又包含Y某个项集的事务占事务总数的比例；【置信度Confidence】在所有包含X的事务中包含Y的事务所占比例。13. 理解Apriori性质及其意义【Apriori】如果一个项集是频繁的，那么它的所有子集都是频繁的。相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。【意义】利用该性质，通过减少搜索空间，来提高频繁项集逐层产生的效率。14. 理解FP-Growth算法克服了Apriori算法的那些不足1. 减少了扫描数据库的次数，只用扫描两次2. 候选项变少，不会产生那么大的候选项集15. 给定一个交易数据库与支持度阈值，能熟练运用Apriori算法与FP-Growth算法挖掘频繁项集【Apriori算法计算频繁项集】【步骤】1、第一次扫描，列出一项集，并计数。 2、去除低于阈值的项集，组合出二项集，扫描计数。 3、重复步骤2，依次组合出N项集，直至项集计数小于阈值，结束。 【注意】Apriori定义：如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。所以在组合项集时一定要注意，新组合出的项集不应包含已经被“淘汰”的项集。 【FP-Growth算法计算频繁项集】步骤一、扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，将频繁项按照支持度的递减排序，生成频繁项集头表。（注意事项：1、降序排列。2、MinSup的存在！）步骤二、第二次扫描投影，按照f,c,a,b,m,p的顺序逐条对应写出剔除非频繁项后的频繁集，（注意：f,c,a,b,m,p的顺序确定后就不在变动，这在下面的步骤中起关键作用）步骤三、并开始构建FP树。按照事务ID号的顺序，将处理好的频繁项集映射创建FP树，并在对应节点计数。步骤四、构建每个对象的条件模式基，建议从频率低的节点开始。（注意：不要忘了f对应的）。步骤五、列出下表，对照MinSup剔除低于阈值的项。步骤六、针对每一项建立条件FP树。下面用m项作例子，如下。步骤七、找出频繁项集。16. 理解关联规则产生时所采取的优化策略（老师说直接距离就可以）比如，L = A,B,C,D:c(ABC D) c(AB CD) c(A BCD)【为什么？分子不变，都是ABCD，分母越来越大】17. 理解K-means算法的内容并讨论该算法之不足【K-means】K均值算法流程1、 随机选择K个对象，每个对象代表一个簇的初始均值或中心2、 对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇。3、 计算每个簇的新均值4、 回到步骤2，循环，直到准则函数收敛。【不足之处】1、 只有当簇均值有定义的情况下，K-means方法才能够使用。2、 用户必须首先给定簇数目3、 不适合发现非凸形状的簇，或者大小差别很大的簇。4、 对噪声和离群点数据敏感。18. 理解凝聚聚类算法的基本过程，并分析算法时间与空间复杂度步骤：1计算距离矩阵 2 让每个数据点成为一个群集 3,循环开始 4， 合并两个距离最近的群集 5， 更新距离矩阵 6，直到只剩下一个群集时间复杂度：N倍 空间复杂度：N倍19. 理解DBSCAN算法将待聚类的点分为哪几类，分解解释之三类：中心点：中心点领域范围内的点的个数临界值（MinPts）边界点：边界点领域范围内的点个数小于临界值，但是它在中心点邻域范围的边界上。噪音点：既不是中心点又不是边界点的点。（噪音点领域范围内的点个数小于临界点。）20. 理解DBSCAN算法的思想及它克服了K-means算法的哪些不足【基于密度的聚类】只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声不敏感。但是，其计算密度短语的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。【DBSCAN】（Density-Based Spatial Clustering of Applications with Noise）具有噪声的基于密度的聚类应用。【算法步骤】1、 通过检查数据集中每个对象的-邻域（可以理解为半径）来寻找聚类2、 如果一个点P的-邻域包含多于MinPts（最少包含点数）个对象，则创建一个P作为核心对象的新簇。3、 反复地寻找从这个核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。4、 当没有新的点可以被添