2014知识发现与数据开采试题及答案

1、1. 什么叫数据挖掘？数据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的并有潜在价值的信息的非平凡过程。数据挖掘是一种决策支持过程。2. 数据挖掘一般有哪些步骤？从数据本身来考虑，数据挖掘通常需要有信息收集、数据集成、数据规约、数据清理、数据变换、数据挖掘实施过程、模式评估和知识表示8个步骤。步骤（1）信息收集：根据确定的数据分析对象，抽象出在数据分析中所需要的特征信息，然后选择合适的信息收集方法，将收集到的信息存入数据库。对于海量数据，选择一个合适的数据存储和管理的数据仓库是至关重要的。步骤（2）数据集成：把不同来源、格式、特点性质的数据在逻辑上或物理上有机地集中，从而为企业提供全面的

2、数据共享。步骤（3）数据规约：如果执行多数的数据挖掘算法，即使是在少量数据上也需要很长的时间，而做商业运营数据挖掘时数据量往往非常大。数据规约技术可以用来得到数据集的规约表示，它小得多，但仍然接近于保持原数据的完整性，并且规约后执行数据挖掘结果与规约前执行结果相同或几乎相同。步骤（4）数据清理：在数据库中的数据有一些是不完整的（有些感兴趣的属性缺少属性值）、含噪声的（包含错误的属性值），并且是不一致的（同样的信息不同的表示方式），因此需要进行数据清理，将完整、正确、一致的数据信息存入数据仓库中。不然，挖掘的结果会差强人意。步骤（5）数据变换：通过平滑聚集、数据概化、规范化等方式将数据转换成适用

3、于数据挖掘的形式。对于有些实数型数据，通过概念分层和数据的离散化来转换数据也是重要的一步。步骤（6）数据挖掘过程：根据数据仓库中的数据信息，选择合适的分析工具，应用统计方法、事例推理、决策树、规则推理、模糊集，甚至神经网络、遗传算法的方法处理信息，得出有用的分析信息。步骤（7）模式评估：从商业角度，由行业专家来验证数据挖掘结果的正确性。步骤（8）知识表示：将数据挖掘所得到的分析信息以可视化的方式呈现给用户，或作为新的知识存放在知识库中，供其他应用程序使用。3. 数据挖掘的功能大致有哪些？（1）自动预测趋势和行为数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题，如今可以迅

4、速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。（2）关联分析数据关联，是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。（3）聚类数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决

5、条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术牞其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。（4）概念描述概念描述，就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。（5）偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如

6、分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。4. 什么叫孤立点（outlier）?在数学上是指坐标满足曲线方程，但并不落在曲线上的点。孤立点也可以指是在数据集合中与大多数数据的特征或不一致的数据。5. 什么叫数据仓库？数据仓库（Data Warehouse）是一个面向主题的（Subject Oriented）、集成的（Integrated）、相对稳定的（Non-Volatile）、反映历史变化（Time Variant）的数据集合，用于支持管理决策(Decision Making Support

7、)。数据仓库是为企业所有级别的决策制定过程提供支持的所有类型数据的战略集合。它是单个数据存储，出于分析性报告和决策支持的目的而创建。 为企业提供需要业务智能来指导业务流程改进和监视时间、成本、质量和控制。6. 为什么数据仓库的数据是非挥发的？因为数据仓库是一个物理上独立的存储结构（存储着转换自操作系统的数据）。数据更新的操作不在数据仓库环境下进行。（1）不需要事务处理，恢复，和并发控制机制（2）在数据访问中只需要两种操作：数据的初始化和访问。7. 什么叫OLTP？什么叫OLAP？它们有何区别？On-Line Transaction Processing联机事务处理系统(OLTP)。也称为面向交

8、易的处理系统，其基本特征是顾客的原始数据可以立即传送到计算中心进行处理，并在很短的时间内给出处理结果。联机分析处理(on一line analytical processing , OLAP).是数据仓库系统最主要的应用，专门设计用于支持复杂的分析操作，侧重对决策人员和高层管理人员的决策支持，可以根据分析人员的要求快速、灵活地进行大数据量的复杂查询处理，并且以一种直观而易懂的形式将查询结果提供给决策人员，以便他们准确掌握企业（公司）的经营状况，了解对象的需求，制定正确的方案。两者的区别如下表：OLTPOLAP用户操作人员,低层管理人员决策人员,高级管理人员功能日常操作处理分析决策DB 设计面向应

9、用面向主题数据当前的, 最新的细节的, 二维的分立的历史的, 聚集的, 多维的集成的, 统一的存取读/写数十条记录读上百万条记录工作单位简单的事务复杂的查询用户数上千个上百万个DB 大小100MB-GB100GB-TB时间要求具有实时性对时间的要求不严格主要应用数据库数据仓库8. 多维数据仓库的事实表的用途是什么？每个数据仓库都包含一个或者多个事实数据表。事实数据表可能包含业务销售数据，如现金登记事务所产生的数据，事实数据表通常包含大量的行。事实数据表的主要特点是包含数字数据（事实），并且这些数字信息可以汇总，以提供有关单位作为历史的数据，每个事实数据表包含一个由多个部分组成的索引，该索引包含

10、作为外键的相关性维度表的主键，而维度表包含事实记录的特性。事实数据表不应该包含描述性的信息，也不应该包含除数字度量字段及使事实与维度表中对应项的相关索引字段之外的任何数据。包含在事实数据表中的“度量值”有两种：一种是可以累计的度量值，另一种是非累计的度量值。最有用的度量值是可累计的度量值，其累计起来的数字是非常有意义的。用户可以通过累计度量值获得汇总信息，例如。可以汇总具体时间段内一组商店的特定商品的销售情况。非累计的度量值也可以用于事实数据表，单汇总结果一般是没有意义的，例如，在一座大厦的不同位置测量温度时，如果将大厦中所有不同位置的温度累加是没有意义的，但是求平均值是有意义的。一般来说，一

11、个事实数据表都要和一个或多个维度表相关联，用户在利用事实数据表创建多维数据集时，可以使用一个或多个维度表。9. 什么叫雪花模式？什么叫事实星座模式？一个雪花模式是一个合乎逻辑的安排表中的多维数据库，这样的实体关系图类似于花的形状。雪花模式是集中代表事实表的连接到多个层面。雪花模式是类似星型模式。然而，在雪花架构，尺寸归到多个相关的表，而星型模式的尺寸非标准化，每个维度表由一个单一的。形状复杂的雪花出现时，雪花模式的详细尺寸，并具有多层次的关系，并有多个子表的父表的效果只会影响维度表而不是事实表。一种常见的数据仓库的概念模型。这种模型往往应用于数据关系比星型模型和雪花模型更复杂的场合。事实星座模

12、型需要多个事实表共享维度表，因而可以视为星形模型的集合，故亦被称为星系模型。10. 雪花模式与星形模式各有哪些有缺点？雪花型结构是一种正规化结构，他取除了数据仓库中的冗余数据。比如有一张销售事实表，然后有一张产品维度表与之相连，然后有一张产品类别维度表与产品维度表连。这种结构就是雪花型结构。雪花型结构取除了数据冗余，所以有些统计就需要做连接才能产生，所以效率不一定有星型架构高。正规化也是一种比较复杂的过程，相应数据库结构设计、数据的ETL、以及后期的维护都要复杂一些。:雪花模式比较复杂，用户不容易理解;浏览内容相对困难;额外的连接将使查询性能下降。 星型架构是一种非正规化的结构，多维数据集中的

13、每一个维度都与事实表相连接，不存在渐变维度，所以数据有一定的冗余，正因为数据的冗余所以很多统计查询不需要做外部的连接所以一般情况下效率比雪花型要高。星型结构不用考虑很多正规化的因素，设计与实现都比较简单。11. 举例说明什么是分布式函数？什么是代数函数？什么是全息函数？分布的(distributive)：将函数用于n个聚集值得到的结果和将函数用于所有数据得到的结果一样。比如：count()，sum()，min()，max()等代数的(algebraic)：函数可以由一个带M个参数的代数函数计算（M为有界整数），而每个参数值都可以有一个分布的聚集函数求得。比如：avg()，min_N()，sta

14、ndard_deviation()整体的(holistic)：描述函数的子聚集所需的存储没有一个常数界。比如：median()，mode()，rank()12、维的概念层次可为数据库的哪些操作提供支撑？上卷(roll-up):汇总数据（1）通过一个维的概念分层向上攀升或者通过维规约（2）当用维归约进行上卷时，一个或多个维由给定的数据立方体删除下钻(drill-down)：上卷的逆操作由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下或引入新的维来实现(为给定数据添加更多细节)切片和切块(slice and dice)切片操作在给定的数据立方体的一个维上进行选择，导致一个子方切块操作通过

15、对两个或多个维进行选择，定义子方转轴(pivot)立方体的重定位，可视化，或将一个3维立方体转化为一个2维平面序列转轴是一种可视化操作，通过转动当前数据的视图来提供一个数据的替代表示钻过(drill_across)：执行涉及多个事实表的查询钻透(drill_through)：使用关系SQL机制，钻到数据立方体的底层，到后端关系表其他OLAP操作可能包括列出表中最高或最低的N项，以及计算移动平均值、增长率、利润、统计函数等等13、什么叫企业级数据仓库？什么叫部门级数据仓库？什么叫虚拟数据仓库？企业仓库：搜集关于跨越整个组织的主题的所有信息数据集市：企业范围数据的一个子集，对于特定的客户是有用的。

16、其范围限于选定的主题，比如一个商场的数据集市虚拟仓库：操作数据库上的一系列视图，只有一些可能的汇总视图被物化(先计算出来，小部分)。14、数据立方体的计算有哪些优化策略？基于ROLAP的方体计算(Agarwal et al96)基于数组的算法(MOLAP)(Zhao et al97)自底向上的计算方法(Beyer&Ramarkrishnan99)H-cubing技术(Han,pei,dong&wang:SIGMOD0115、什么叫数据清洗？数据清理：填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性。16、什么叫OLAM？与OLAP有什么区别？联机分析挖掘OLAM(on一line an

17、alytical mining )是OLAP与数据挖掘相结合的产物。它融合和OLAP和数据挖掘两者的优点，即体现了OLAP的对用户请求的快速响应，交互式操作和多维分析，又体现了数据挖掘分析数据的深入和分析过程的自动化。与OLAP相比由于融合了数据挖掘技术，因此在数据分析时更加深入，并可实现分析过程的自动化。17、挖掘前为什么要进行数据预处理？1 不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据2 含噪声的：包含错误或者“孤立点”3 不一致的：在编码或者命名上存在差异4 没有高质量的数据，就没有高质量的挖掘结果5 高质量的决策必须依赖高质量的数据6 数据仓库需要对高质量的数据进行一致地集成

18、18、如何处理丢失的非类别特征的数据？1忽略元组：当类标号缺少时通常这么做（假定挖掘任务涉及分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。2 人工填写空缺值：工作量大，可行性低3 使用一个全局变量填充空缺值：比如使用unknown或-4 使用属性的平均值填充空缺值5 使用与给定元组属同一类的所有样本的平均值6 使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法19、如何处理噪声数据？分箱(binning):（1）首先排序数据，并将他们分到等深的箱中（2）然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等聚类：监测并且去除孤立点计算机和人

19、工检查结合：计算机检测可疑数据，然后对它们进行人工判断回归：通过让数据适应回归函数来平滑数据20、什么叫数据的模式集成？模式集成：（1）整合不同数据源中的元数据（2）实体识别问题：匹配来自不同数据源的现实世界的实体。21、数据转换（data transformation）通常采用哪些方法完成?平滑：去除数据中的噪声（分箱、聚类、回归）聚集：汇总，数据立方体的构建数据概化：沿概念分层向上概化规范化：将数据按比例缩放，使之落入一个小的特定区间（1）最小最大规范化（2）z-score规范化（3）小数定标规范化属性构造：通过现有属性构造新的属性，并添加到属性集中；以增加对高维数据的结构的理解和精确度2

20、2、为什么要进行特征选择？1 获取某些特征所需的计算量可能很大，因此倾向于选择较小的特征集2 特征间的相关性，比如特征A完全依赖于特征B，如果我们已经将特征B选入特征集，那么特征A是否还有必要选入特征集？我认为是不必的。3 特征集越大，分类器就越复杂，其后果就是推广能力（generalization capability）下降。选择较小的特征集会降低复杂度，可能会提高系统的推广能力。Less is More !23、主成分（PCA）分析的作用是什么？经过 PCA 分析，一个多变量的复杂问题被简化为低维空间的简单问题。可以利用这种简化方法进行作图，形象地表示和分析复杂问题24、有放回的采样与不放

21、回的采样的统计学区别是什么？有放回采样下一次采样结果不受上一次采样结果的影响（即连续两次采样的结果相互独立），而无放回采样下一次采样的结果受到上一次采样结果的影响（即连续两次采样的结果不独立）。25、数据离散化的目的是什么？通过将属性域划分为区间，减少给定连续属性值的个数。区间的标号可以代替实际的数据值。26、数据离散化有哪些方法？分箱（binning）：分箱技术递归的用于结果划分，可以产生概念分层。直方图分析（histogram）：直方图分析方法递归的应用于每一部分，可以自动产生多级概念分层。聚类分析：将数据划分成簇，每个簇形成同一个概念层上的一个节点，每个簇可再分成多个子簇，形成子节点。基

22、于熵的离散化通过自然划分分段27、概念描述与预测性挖掘的区别？描述性挖掘：以简洁概要的方式描述数据，并提供数据的有趣的一般性质。预测性数据挖掘：通过分析数据建立一个或一组模型，并试图预测新数据集的行为28、什么叫属性相关性分析？通过识别不相关或者是弱相关的属性，将它们排除在概念描述过程之外，从而确定哪些属性应当包含在类特征化和类比较中。29、属性相关性分析有哪些度量方法？可采用的度量包括：信息增益、Gini索引、不确定性和相关系数。（涉及机器学习、统计、模糊和粗糙集理论等方面的相关知识）。30、什么叫d-weight?什么叫t-weight?量化区分规则使用d-weight作为兴趣度度量qa概

23、化元组Cj目标类qa的d-weight是初始目标类工作关系中被qa覆盖的元组数与初始目标类和对比类工作关系中被qa覆盖的总元组数的比使用t_weight表示主概化关系中每个元组的典型性31、什么叫关联规则？给定：项的集合：I=i1,i2,.,in任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c32、什么叫频繁模式？如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集33、什么叫最大频繁模式？什么叫闭包频繁模式？挖掘

24、最大的频繁模式（该模式的任何真超模式都是非频繁的）挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c）34、什么叫支持度？什么叫可信度？支持度s是指事务集D中包含的百分比：置信度c是指D中包含A的事务同时也包含B的百分比35、为什么FP-growth算法非常快？12. Apriori准则是什么？Apriori定律1)：如果一个集合是频繁项集，则它的所有子集都是频繁项集。举例：假设一个集合A,B是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集A,B出现次数必定大于等于min_support，即它的子集都是频繁

25、项集。Apriori定律2)：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。举例：假设集合A不是频繁项集，即A出现的次数小于min_support，则它的任何超集如A,B出现的次数必定小于min_support，因此其超集必定也不是频繁项集。13. 冰山查询与Ariori准则有什么关系？14. 关联规则的提升是用来度量什么指标的？15. 一个约束是单调的需要满足什么条件？16. 分类与预测有何区别？分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测未知或空缺值17. 分类与聚类有何区别？简单地说，分类(

26、Categorization or Classification)就是按照某种标准给对象贴标签(label)，再根据标签来区分归类。简单地说，聚类是指事先没有“标签”而通过某种成团分析找出事物之间存在聚集性原因的过程。区别是，分类是事先定义好类别 ，类别数不变 。分类器需要由人工标注的分类训练语料训练得到，属于有指导学习范畴。聚类则没有事先预定的类别，类别数不确定。 聚类不需要人工标注和预先训练分类器，类别在聚类过程中自动生成 。分类适合类别或分类体系已经确定的场合，比如按照国图分类法分类图书；聚类则适合不存在分类体系、类别数不确定的场合，一般作为某些应用的前端，比如多文档文摘、搜索引擎结果后

27、聚类(元搜索)等。 分类的目的是学会一个分类函数或分类模型(也常常称作分类器 ),该模型能把数据库中的数据项映射到给定类别中的某一个类中。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：(v1,v2,.,vn; c)；其中vi表示字段值，c表示类别。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。 聚类(clustering)是指根据“物以类聚”原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一

28、个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系，挖掘的知识用以属性名为变量的数学方程来表示。聚类技术正在蓬勃发展，涉及范围包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等领域，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。常见的聚类算法包括：K-均值聚类算法、K-中心点聚类算法、CLARANS、 BIRCH、CLIQUE、DBSCAN等。18. 什么叫有监督学习？

29、利用一组已知类别的样本调整分类器的参数，使其达到所要求性能的过程，也称为监督训练或有教师学习。监督学习中在给予计算机学习样本的同时，还告诉计算各个样本所属的类别。若所给的学习样本不带有类别信息,就是无监督学习数据立方体计算的Pipesort算法PipeSort算法是基于代价和排序的流水线型算法，它主要结合了“最小父母”、“缓存结果”和“批处理”三种优化方法。该算法可以保证在计算每一个立方格图的子图时排序的代价最小，但并不能保证对于整个立方格图的排序代价最小。因此，对于一个实际的数据立方，PipeSort算法往往生成一个代价很高的立方格图划分方案。字符串编辑距离算法字符串编辑距离：是一种字符串之

30、间相似度计算的方法。给定两个字符串S、T，将S转换成T所需要的删除、插入、替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。举个例子：S=”eeba” T=”abac”我们可以按照这样的步骤转变：（1）将S中的第一个e变成a；（2）删除S中的第二个e；（3）在S中最后添加一个c；那么S到T编辑路径就等于3。当然，这种变换并不是唯一的，但如果3是所有变换中最小值的话。那么我们就可以说S和T的编辑距离等于3了。熵、信息增益和卡方测试计算方法单符号离散信源熵定义：对于给定离散概率空间表示的信源所定义的随机变量I的数学期望为信源的信息熵，单位为比特/符号信息增益计算：

31、关联规则算法典型的算法Aprior算法Aprior算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库1中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则。其中，挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分表中的每一行代表一次购买清单（注意你购买十盒牛奶也只计一次，即只记录某个商品的出现与否）。数据记录的所有项的集合称为总项集，上表中的总项集S=牛奶,面包,尿布,啤酒,鸡蛋,可乐。关联规则就是有关联的规则，形式是这样定义的：两个不相交的非空集合X、Y，如果有X-Y，就说X-Y是一条关联规则。举个例子，在上面的

32、表中，我们发现购买啤酒就一定会购买尿布，啤酒-尿布就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述，支持度的定义：support(X-Y) = |X并Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如：support(啤酒-尿布) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%。自信度的定义：confidence(X-Y) = |X并Y|/|X| = 集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数 。例如：confidence(啤酒-尿布) = 啤酒和尿布同时出现的次数/啤酒出现的次数=

33、3/3=100%;confidence(尿布-啤酒) = 啤酒和尿布同时出现的次数/尿布出现的次数 = 3/4 = 75%。这里定义的支持度和自信度都是相对的支持度和自信度，不是绝对支持度，绝对支持度abs_support = 数据记录数N*support。支持度和自信度越高，说明规则越强，关联规则挖掘就是挖掘出满足一定强度的规则。关联规则挖掘的定义：给定一个交易数据集T，找出其中所有支持度support = min_support、自信度confidence = min_confidence的关联规则。有一个简单而粗鲁的方法可以找出所需要的规则，那就是穷举项集的所有组合，并测试每个组合是否满

34、足条件，一个元素个数为n的项集的组合个数为2n-1(除去空集)，所需要的时间复杂度明显为O(2N)，对于普通的超市，其商品的项集数也在1万以上，用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。仔细想一下，我们会发现对于啤酒-尿布，尿布-啤酒这两个规则的支持度实际上只需要计算尿布，啤酒的支持度，即它们交集的支持度。于是我们把关联规则挖掘分两步进行：1）生成频繁项集这一阶段找出所有满足最小支持度的项集，找出的这些项集称为频繁项集。2）生成规则在上一步产生的频繁项集的基础上生成满足最小自信度的规则，产生的规则称为强规则。关联规则挖掘所

35、花费的时间主要是在生成频繁项集上，因为找出的频繁项集往往不会很多，利用频繁项集生成规则也就不会花太多的时间，而生成频繁项集需要测试很多的备选项集，如果不加优化，所需的时间是O(2N)。三、Apriori定律为了减少频繁项集的生成时间，我们应该尽早的消除一些完全不可能是频繁项集的集合，Apriori的两条定律就是干这事的。Apriori定律1)：如果一个集合是频繁项集，则它的所有子集都是频繁项集。举例：假设一个集合A,B是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集A,B出现次数必定大于等于min_support，即它的子集都是频繁项集。Apri

36、ori定律2)：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。举例：假设集合A不是频繁项集，即A出现的次数小于min_support，则它的任何超集如A,B出现的次数必定小于min_support，因此其超集必定也不是频繁项集。利用这两条定律，我们抛掉很多的候选项集，Apriori算法就是利用这两个定理来实现快速挖掘频繁项集的。四、Apriori算法Apriori是由a priori合并而来的，它的意思是后面的是在前面的基础上推出来的，即先验推导，怎么个先验法，其实就是二级频繁项集是在一级频繁项集的基础上产生的，三级频繁项集是在二级频繁项集的基础上产生的，以此类推。Apriori算法

37、属于候选消除算法，是一个生成候选集、消除不满足条件的候选集、并不断循环直到不再产生候选集的过程。上面的图演示了Apriori算法的过程，注意看由二级频繁项集生成三级候选项集时，没有牛奶,面包,啤酒，那是因为面包,啤酒不是二级频繁项集，这里利用了Apriori定理。最后生成三级频繁项集后，没有更高一级的候选项集，因此整个算法结束，牛奶,面包,尿布是最大频繁子集。FP-growth算法/abcjennifer/article/details/Apriori算法的一个主要瓶颈在于，为了获得较长的频繁模式，需要生成大量的候选短频繁模式。FP-Growth算法是针对

38、这个瓶颈提出来的全新的一种算法模式。算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D；最小支持度阈值min_sup。输出：频繁模式的完全集。1 按以下步骤构造FP-树：(a) 扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。(b) 创建FP-树的根结点，以“null”标记它。对于D 中每个事务Trans，执行：选择 Trans 中的频繁项，并按L 中的次序排序。设排序后的频繁项表为p | P，其中，p 是第一个元素，而P 是剩余元素的表。调用insert_tree(p | P, T)。该过程执行情况如下。如果T 有子女N 使得N.item-name = p.item-name，则N 的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name 的结点。如果P 非空，递归地调用insert_tree(P, N)。2 FP-树的挖掘通过调用FP_growth(FP_tree, null)实现。该过程实现如下：procedure FP_growth(Tree,