新一代数据库要点-db汇总

第1章数据挖掘及其算法概览

数据挖掘的目标是支持利用数据进行合理的决策。数据挖掘可以与数据仓库结合起来帮助实现某些类型的决策。数据库知识发现基本概念数据挖掘目标数据挖掘产生的背景数据库知识发现基本概念第1章数据挖掘及其算法概览VolumeVelocityVariety海量高速多格式多格式海量数据包括多种多样不同格式的数据。从简单的电子邮件、数据日志、信用卡记录到仪器收集的科学研究数据、医疗数据以及丰富的媒体数据（图像、音、视频等）等。半结构和非结构化数据所占的比重日益增加，目前这些不同格式的数据需要采用不同的处理方法。这对传统上以结构化数据为主的数据管理技术带来了新的挑战。

淘宝数据内容：日志型数据、文本数据、关系型数据；涉及的维度多（100个不同行业的商品维度、五级商品类目体系、80000多个品牌）第1章数据挖掘及其算法概览数据库知识发现基本概念数据挖掘产生的背景需要一种新的数据集成逻辑组织模型来描述多格式数据共存的数据管理应用环境。针对目前数据管理方法存在的问题，2005年MichaelJ.Franklin和

AlonHalevy提出了数据空间作为一种新的数据管理方法来解决目前数据管理领域面临的困难。数据空间的目标是为分布异构、多格式的数据源提供一个统一的、便捷的和高效的方法来管理属于主体的所有数据，而不仅仅是某个片段。数据空间概念提出以来，研究者围绕数据空间的组织模型、系统原理、存储索引、搜索查询进行了理论上、应用上的研究，取得了一定的成果，但由于发展时间较短，数据空间研究和应用仍处于起步阶段。多格式第1章数据挖掘及其算法概览数据库知识发现基本概念数据挖掘产生的背景第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程数据源数据源。。数据目标数据预处理后的数据信息知识数据准备数据挖掘结果表达及解释数据集成数据选择预处理数据挖掘表达及解释第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-数据准备数据准备：数据选取、数据预处理和数据转换。数据选取的目标是确定发现任务的操作对象，即目标数据，它是根据用户需求从原始数据库中抽取的一组数据；

数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换（如将连续值数据转换为离散值数据）；

数据转换的主要目标是消减数据维数或降维。即从初始特征中找出真正有用的特征并减少数据挖掘时要考虑的特征或者变量的个数。第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-数据准备数据选取

数据挖掘通常不需要所有的数据。有些数据对象和数据属性对建立模型获得模式是没有影响的，这些数据的加入会大大影响挖掘效率，甚至可能导致数据挖掘结果的偏差。对数据库表的选择，有两种方式，纵向选择-列属性选择；横向选择-元组或记录选择。数据选择是对发现任务和数据本身的内容的理解的基础上。寻找依赖于发现目标的表达数据的有用特征，以减少数据规模，从而在尽可能保持数据原貌的前提下最大限度地精简数据量。通过数据选取使数据的规律性和潜在特征更加明显。数据选取在实际应用中非常重要，但DM领域对其也就并不深入，往往认为数据挖掘时，数据已经准备好了。第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-数据准备数据预处理

也称数据清理或者数据清洗。在数据中消除错误和不一致，并解决对象识别问题的过程。主要包括空值处理、噪声数据处理、及不一致数据处理等。也就是说通过数据预处理去除噪声或无关数据，并处理数据中缺失的数据项或域。例如，关于“高薪”、“低收入”等概念在不同的数据集合中有不同的定义，需要进行统一。需要对数据值进行标准化，例如，人员出身地在不同的集合中表示不同，例如一个集合中为哈市，一个集合中为哈尔滨市。解决异名同义问题，以及同名异义等问题。数据清理是一个困难、繁琐的问题。DM领域对此研究并不多，在数据集成领域研究比较丰富。第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-数据准备数据集成

数据挖掘需要对数据进行集成。将多个数据源中的数据合并存放在统一的数据存储中。数据集成主要涉及三个方面的问题：模式集成：从多个异构的数据库、文件、遗留系统中提取并集成数据，解决语义二义性，统一不同的数据格式，消除冗余，重复等问题。模式集成涉及实体识别。目前该领域研究比较热，但问题多难以形成统一的解决方法。目前研究包括元数据、元知识（Metadata,Metaknowledge）及本体（Ontology）等方法。数据值冲突检测及处理：表示、比例、单位、编码等不同的解决方法。例如，货币单位等冗余：如同一属性多次出现等(结果综合，EntityResolution)。在数据仓库和数据挖掘领域，也许不需要规范化（去规范化）。第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-数据挖掘数据挖掘：确定目标和任务。如数据总结、分类、聚类、关联规则发现或者序列模式发现等。确定任务后，考虑采用何种算法。同样的任务可以采用不同的算法来实现。选择算法的考虑因素包括：不同的数据有不同的特点，因此需要采用与之相关的算法来处理；用户或实际运行系统的要求，有的用户可能希望获得描述性、易于理解的描述性知识，有的用户可能希望获得预测准确度高的预测型知识。数据挖掘仅仅是整个过程的一个部分，数据挖掘质量的好坏有两个影响因素。采用的数据挖掘技术的有效性；用于挖掘数据的质量和数量。数据挖掘过程是一个非平凡的过程，需要不断反馈。可视化在数据挖掘中扮演重要的角色。第1章数据挖掘及其算法概览数据库知识发现基本概念知识发现的过程-结果表达于解释结果解释和评价：数据挖掘阶段发现的模式，经过用户或机器的评价，可能存在冗余或无关的模式，需要将其剔除。模式也可能不满足用户的要求，需要重新进行KDD过程。数据库知识发现基本概念第1章数据挖掘及其算法概览Web数据挖掘WEB数据挖掘内容挖掘结构挖掘使用挖掘分类聚类检索隐链接分析层次链接分析个性化协同过滤从网页内容中抽取有用的信息和知识从表征WEB结构的超链接中寻找有用的知识从记录每位用户点击情况的使用日志中挖掘用户的访问模式数据库知识发现基本概念第1章数据挖掘及其算法概览Web数据挖掘WEB挖掘过程和数据挖掘过程十分相似，区别通常只是数据收集。在传统的数据挖掘中，数据经常是收集并存储在数据仓库中，对Web挖掘来说，数据收集是一项艰巨的任务。尤其是在进行WEB内容挖掘和结构挖掘方面，需要爬取大量的网页。第1章数据挖掘及其算法概览数据挖掘算法概览

多数情况下，数据挖掘算法可以从五个方面进行考虑。也就是任务、模型、评分函数、搜索方法和数据管理技术。或者称它们是算法组件。关于算法组件例如关联规则的典型数据挖掘算法组件：

1任务：描述变量之间的关联关系；

2结构：用概率表示的“关联规则”模式；

3评分函数：可信度与支持度的阈值；

4搜索方式：系统搜索，带剪枝的广度优先；

5数据管理技术：多重线性扫描。第1章数据挖掘及其算法概览典型数据挖掘算法数据挖掘领域典型算法*ID3,C4.5（决策树）*Thek-meansalgorithm（聚类）Supportvectormachines（支持向量机）*TheApriorialgorithm（关联规则）TheEMalgorithm（迭代优化算法）*PageRank（网页等级/重要性算法）*AdaBoost（迭代分类算法）*kNN:k-nearestneighborclassification（基于事例的学习）NaiveBayes（贝叶斯学习）CART（增量学习算法）第2章数据仓库数据仓库基本概念主要通过以下五点区分开来。

用户和系统的面向性OLTP是面向顾客的,用于事务和查询处理;OLAP是面向市场的,用于数据分析

数据内容

OLTP系统管理当前数据;OLAP系统管理大量历史数据,提供汇总和聚集机制.

数据库设计

OLTP采用实体-联系ER模型和面向应用的数据库设计;

OLAP采用星型或雪花模型和面向主题的数据库设计.

视图

OLTP主要关注一个企业或部门内部的当前数据,不涉及历史数据或不同组织的数据;OLAP则相反.

访问模式

OLTP系统的访问主要由短的原子事务组成.这种系统需要并行和恢复机制;

OLAP系统的访问大部分是只读操作OLTP（on-linetransactionprocessing）与OLAP（On-LineAnalyticalProcessing）区别第2章数据仓库数据仓库基本概念数据仓库定义及特征

数据仓库理论的创始人W.H.Inmon在其《BuildingtheDataWarehouse》一书中，给出了数据仓库的四个基本特征：

面向主题，数据是集成的，数据是不可更新的，数据是随时间不断变化。企业级主题区域级原子数据集成仓库格式直接访问数据集市格式直接访问企业信息化工厂√第3范式否物理维度*是维度数据仓库√维度是*逻辑*维度是独立型数据集市×N/AN/A物理维度*是数据仓库体系结构第2章数据仓库数据仓库体系结构的争论三种体系结构的特征比较数据仓库体系结构第2章数据仓库数据仓库体系结构的争论三种体系结构比较体系结构提倡者其他称谓描述维度设计的角色企业信息化工厂BillInmon原子数据仓库企业数据仓库企业数据仓库是原子数据的一种集成仓库不能被直接访问数据集市为部门使用/分析而重新组织数据维度设计只应用于数据集市维度数据仓库RalphKimball企业数据仓库总线体系结构结构化数据集市虚拟数据集市维度数据仓库是原子数据的一种集成仓库可以被访问包含在维度数据仓库的主题区域，有时称为数据集市数据集市不要求是独立的数据库所有数据按维度组织独立型数据集市无倡导者但很常见数据集市竖井式烟筒型孤岛型主题区域的实现不需要企业环境可以使用维度设计Inmon的企业信息化工厂和Kimball的维度数据仓库都关注企业级应用。他们的目的是支持跨企业或组织机构的分析型需求。这种方法允许在一个主题区域内处理需求，就像跨主题区域处理问题一样。关注企业级应用需要采用一种工程化的方法来处理来自不同组织的数据需求。数据仓库不能仅凭倾听几次需求就能设计出来。设计团队必须研究、分析公共数据元素的不同特征，这些特征由于用户不同而有所差别。比如，用户或产品可能在制造、销售或审计中彼此关联。对于相同的数据元素，在不同的系统中会采用不同的处理方法，数据仓库设计必须以一种统一的视图来适应所有不同的观点。相比之下，独立型数据集市在关注企业级应用方面显示出了不足。其开发只考虑了来自一个小组或部门的需求。由于这种关注的片面性，其开发不会受制于对跨企业公共数据元素的探讨；而仅仅关注特定主题区域的特定系统。由于这两种企业体系结构有相同的范围，因此产生了一个相同的体系结构特点：它们都有一个独立的原子数据的集成仓库。在企业信息化工厂中，这一仓库被称为企业数据仓库。在维度数据仓库中，该仓库被称为维度数据仓库。这种集中存储的集成特性与关注企业级应用是一致的。它汇集了公共实体的多种优势，比如顾客或产品。同样，关注原子化也满足了企业目标。无须按照特定分组或主题区域的需求来收集细节数据。取而代之的是，尽可能有效地收集细节数据以满足所有的分析型需求。数据仓库体系结构第2章数据仓库数据仓库体系结构的争论三种体系结构比较参考StarSchema完全参考手册—数据仓库维度设计权威指南清华大学出版社

对于Inmon体系结构来说，数据集市是为部门使用而建立的一组表格，并且是物理分离的。可以聚集细节数据以适应部门或小组的特殊需要。在这方面，它与独立型数据集市有一些相似之处；然而，企业信息化工厂中的数据集市在企业仓库中获取数据，因此内容与企业信息视图保持一致。而这是独立型数据集市无法保证的。对于Kimball体系结构来说，不要求数据集市与物理数据分开存储。相反，它可以是一种逻辑构件——数据仓库表的子集。单独的数据集市报表可以随时构建。构建完毕后即可从集成仓库中得到报表。数据集市与企业信息视图保持一致，要么是由于它们将这种视图具体化，要么是由于它们从数据集市中获取数据。

数据仓库体系结构第2章数据仓库数据仓库体系结构的争论三种体系结构比较第2章数据仓库数据仓库体系结构DW中还有一类重要的数据：元数据（metedata）。元数据是“关于数据的数据”（RDBMS中的数据字典就是一种元数据）。数据仓库中的元数据描述了数据的结构、内容、索引、码、数据转换规则、粒度定义等。关于元数据

在数据仓库系统中，元数据可以帮助数据仓库管理员和数据仓库的开发人员非常方便地找到他们所关心的数据。在数据仓库系统中，元数据机制主要支持以下五类系统治理功能：

1描述哪些数据在数据仓库中；

2定义要进入数据仓库中的数据和从数据仓库中产生的数据；

3记录根据业务事件发生而随之进行的数据抽取工作时间安排；

4记录并检测系统数据一致性的要求和执行情况；

5衡量数据质量。第2章数据仓库数据仓库体系结构元数据作用及功能第2章数据仓库数据仓库元数据管理元数据分类技术元数据业务元数据

技术元数据是存储关于数据仓库系统技术细节的数据，是用于开发和治理数据仓库使用的数据。描述和设计如何访问和处理数据，包括查询、汇总、递交等。它主要包括以下信息：

1数据仓库结构的描述，包括仓库模式、视图、维、层次结构和导出数据的定义，以及数据集市的位置和内容；

2业务系统、数据仓库和数据集市的体系结构和模式；

3汇总用的算法，包括度量和维定义算法，数据粒度、主题领域、聚集、汇总、预定义的查询与报告；

4由操作环境到数据仓库环境的映射，包括源数据和它们的内容、数据分割、数据提取、清理、转换规则和数据刷新规则、安全（用户授权和存取控制）。第2章数据仓库技术元数据数据仓库元数据管理技术元数据示例：用户报表和查询访问模式、频率和执行时间；审计控制和负载平衡信息；数据的技术结构；提供给DSS的记录系统；源数据字段标识；从操作型记录系统到DSS的映射与转换；编码/引用表转换；物理和逻辑数据模型；

DSS表名、键和索引；域值；DSS表结构和属性；数据模型和DSS之间的关系；操作型系统的表结构和属性；抽取历史；

DSS表访问模式；DSS归档；工作相关性；程序名和描述；版本维护；安全性；清洗规则等。第2章数据仓库数据仓库元数据管理

业务元数据从业务角度描述了数据仓库中的数据，它提供了介于使用者和实际系统之间的语义层，使得不懂计算机技术的业务人员也能够“读懂”数据仓库中的数据。业务元数据为DSS分析人员提供了访问DSS底层的数据仓库和数据集市中信息的线路图。第2章数据仓库业务元数据数据仓库元数据管理

业务元数据主要包括以下信息：使用者的业务术语所表达的数据模型、对象名和属性名；访问数据的原则和数据的来源；系统所提供的分析方法以及公式和报表的信息；具体包括以下信息：

1企业概念模型：这是业务元数据所应提供的重要的信息，它表示企业数据模型的高层信息、整个企业的业务概念和相互关系。以这个企业模型为基础，不懂数据库技术和SQL语句的业务人员对数据仓库中的数据也能做到心中有数。

2多维数据模型：这是企业概念模型的重要组成部分，它告诉业务分析人员在数据集市当中有哪些维、维的类别、数据立方体以及数据集市中的聚合规则。这里的数据立方体表示某主题领域业务事实表和维表的多维组织形式。

3业务概念模型和物理数据之间的依靠：以上提到的业务元数据只是表示出了数据的业务视图，这些业务视图与实际的数据仓库或数据库、多维数据库中的表、字段、维、层次等之间的对应关系也应该在元数据知识库中有所体现。第2章数据仓库业务元数据数据仓库元数据管理业务数据示例：业务分析员了解的数据结构（与技术用户比较，产品体系对于业务用户的意义有所不同）；

DSS中信息的常见访问例程；主题领域（例如产品、客户、销售等）；表名的业务定义；属性名和业务术语的定义；数据质量的统计信息；

DSS字段映射、转换和概要；下钻、上钻、钻过和钻透的规则；域值；数据负责人；数据位置；

DSS刷新日期等。第2章数据仓库业务元数据数据仓库元数据管理元数据源元数据存储元数据用户ETL工具/处理过程数据建模工具业务人员/文档生产系统应用数据质量工具其他元数据源报表和OLAP工具版本控制/权限管理数据仓库元数据技术元数据业务元数据操作元数据业务用户管理员开发人员第2章数据仓库关于元数据数据仓库元数据管理第2章数据仓库数据仓库元数据管理元数据主要工具常见的元数据位置元数据类型常见工具ETL数据转换规则ArdentDatastage程序任务间的相关性SagentSolutionDSS负载平衡统计及加载统计InformaticPowermartSASInstitute数据谱系（DataLineage）数据建模工具逻辑和物理数据模型OracleDesigner2000技术实体和属性定义PlatnumErwin域值Silverrun报表工具用户访问模式Brio报表执行时间CognosBusinessObjects业务实体、属性、标准定义InformaticAdvantage数据质量工具数据质量统计i.dCentric审核控制TrilliumVality生产商应用程序逻辑和物理数据模型PeopleSoft数据字典SAPSiebolSystems数据仓库的数据模式第2章数据仓库星型模式(StarSchema)事实表(facttable)，存放基本数据，相关主题的数据主体（BCNF）维(dimension)，影响、分析主体数据的因素量(measure)，事实表中的数据属性维表(dimensiontable)，表示维的各种表维是量的取值条件，维用外键表示以事实表为中心，加上若干维表，组成星型数据模式例：产品-商店-销售额CustSalesLocationSalesProdSalesTimeSalesSalestimeid<pk,fk>productid<pk,fk>locationid<pk,fk>customerid<pk,fk>salesrevenueunitssoldProductproductid<pk>makemodelTimetimeid<pk>dateyearquartermonthweekLocationlocationid<pk>regiondistrictstoreCustomercustomerid<pk>categorygroupSalesfactSalesmeasuresTimedimensionAttributesofthe

timedimension数据仓库的数据模式第2章数据仓库星型模式

位于星形中心的实体是指标实体，是用户最关心的基本实体和查询活动的中心，为数据仓库的查询活动提供定量数据。每个指标实体代表一系列相关事实，完成一项指定的功能。位于星形图星角上的实体是维度实体，其作用是限制用户的查询结果，将数据过滤使得从指标实体查询返回较少的行，从而缩小访问范围。每个维表有自己的属性，维表和事实表通过关键字相关联。星形模式虽然是一个关系模型，但是它不是一个规范化的模型。在星形模式中，维度表被故意地非规范化了，这是星形模式与OLTP系统中的关系模式的基本区别。使用星形模式主要原因:提高查询的效率。采用星形模式设计的数据仓库的优点是由于数据的组织已经过预处理，主要数据都在庞大的事实表中,所以只要扫描事实表就可以进行查询，而不必把多个庞大的表联接起来，查询访问效率较高。同时由于维表一般都很小,甚至可以放在高速缓存中,与事实表作连接时其速度较快;便于用户理解。对于非计算机专业的用户而言，星形模式比较直观，通过分析星形模式，很容易组合出各种查询。数据仓库的数据模式第2章数据仓库星型模式数据仓库的数据模式第2章数据仓库雪花模式(SnowflakeSchema)维一般是由若干层次组成把维按其层次结构表示成若干个表规范化、节省存储空间但需多做连接操作定单号销售员号客户号产品号日期标识地区名称数量总价定单号定货日期客户号客户名称客户地址销售员号姓名城市产品号产品名称单价日期标识日月年地区名称省事实表雪花模式产品号公司代码公司代码公司名称地址雪花模式(SnowflakeSchema)数据仓库的数据模式第2章数据仓库

雪花模式是对星形模式维表的进一步层次化，将某些维表扩展成事实表，这样既可以应付不同级别用户的查询，又可以将源数据通过层次间的联系向上综合，最大限度地减少数据存储量，因而提高了查询功能。数据仓库的数据模式第2章数据仓库星模式与雪花模式的区别数据仓库的数据模式第2章数据仓库维度表与事实表维度表维度提供了环境信息，如果没有环境信息，报表将显得毫无意义。成功的维度设计要点在于适当地使用键，维度列集合包含丰富的细节信息，摒弃节省存储空间的主张。

星型模式中，每个维度表都分配有一个代理键。这个键并不是从操作型系统中获得的。代理键仅仅是为数据仓库和数据集市创建的。代理键通常表现为整数，在星型模式加载时的获取、转换、加载(ETL)过程中产生并被管理。键值不包含内在的含义，因此对数据仓库使用者来说并无特殊的意义。维度表的每一行都包含一个唯一的代理键与之对应。与代理键不同，多数维度表中都包含一个或多个自然键。自然键通常来源于源系统。它们不能唯一地区分数据仓库中的行，但能够区分来自源系统中对应的实体。数据仓库的数据模式第2章数据仓库维度表与事实表SurrogateKeyNaturalKeySKU产品统一编号的简称，在大型企业中每种产品均对应有唯一的SKU号维度表数据仓库的数据模式第2章数据仓库维度表与事实表SurrogateKey的作用

（1）维度表的每一行都包含一个唯一的代理键与之对应。起到了类似数据库表中主键的作用。（2）将代理键作为唯一标识符的使用方法允许数据仓库对源系统发生的变化做出响应，这种方式适应了分析型系统的需求。由于维度表不依赖于自然键来区分行的唯一性，因此维度表能够维护历史信息，即使源系统不能也无所谓。维度表假设订单输入系统包含一个customer_id为404777的记录，该记录包含客户的地址信息。在客户地址发生改变时，由于源系统重写了客户地址，因此无法跟踪地址变迁的历史信息。如果在维度表中使用同样的customer_id作为区分行的唯一标识符，那么在维度表中仅能存储一条customer_id为404777的记录，因此采用该方式的维度表也不能跟踪客户地址变迁的历史信息。通过使用代理键，我们就可以在系统中为customer_id为404777的客户保存两条甚至多条记录，因此可以维护客户地址变迁的历史信息。这一历史信息可能是有用的。数据仓库的数据模式第2章数据仓库维度表与事实表SurrogateKey的作用维度表数据仓库的数据模式第2章数据仓库维度表与事实表维度表维度为事实提供了环境。没有环境，事实就无法理解。例如类似“订单为40000美元”这样的说明没有什么意义。它表达的是没有任何实际意义的事实(订单总额)。该订单是有关一个产品还是多个产品的？是一天的订单情况还是一年的订单情况？为正确理解“40000美元”的含义，显然需要更多的信息。“2009年1月有关电子产品的订单为40000美元”，通过增加维度环境——电子产品类、一个月、某年，使得事实具有实际意义。维度以及维度值在多个方面增强了事实的含义：用于过滤查询或报表。

用于控制聚集事实的范围。

用于确定信息的顺序或排序。

与事实一起构成提供报表的环境。

用于定义主从结构、分组、分类汇总、汇总等。通过这些应用，维度揭示了事实的价值。在查询中可以使用维度的不同组合方式回答各种问题。维度涉及的属性越广，对事实表开展分析工作的方式就越多。数据仓库的数据模式第2章数据仓库维度表与事实表维度表的作用在操作型系统中，经常采用的方法是将数据元素尽可能分解为构成其内容的多个组件。采用这种方法，可以将不同的组件按照需要加以合并。例如，客户姓名可以分解并以first_name、middle_initial、last_name的方式存储。在需要时可以将这些属性加以组合形成全名。

这些组件具备分析的价值，当然应该包含在维度设计中。与操作型模式不同，维度模式还应该包含这些组件的各种组合。例如，如果在报表中存在大量的按照全名或last_middle_first格式分类信息的情况，那么应该将这些组合独立地以列的方式体现在维度表中。如下图数据仓库的数据模式第2章数据仓库维度表与事实表维度表的应用数据仓库的数据模式第2章数据仓库维度表与事实表维度表的应用客户维度展示了如何将客户姓名的三个组成部分，例如

JohnP.Smith，构建为客户维度表中的5个属性。由于每一个属性在维度设计时都可以获取，因此可以很容易地使用它们来组织数据、排序报表、设置数据顺序等。另外，由于它们在查询中是不可计算的，因此对数据库管理员来说，可以为这些列增加索引以改善查询性能数据仓库的数据模式第2章数据仓库维度表与事实表维度表—缓慢变化维-变化类型1

Type1Change

当一个维度值的源发生变化，并且不需要在星型模式中保留变化历史时，通常采用类型1来响应变化情况。仅仅使用变化的值重写维度即可。该技术通常应用于源数据元素是为了更正错误而发生更改的情况。通过重写星型模式中对应的维度值，变化类型1删除了数据元素的历史信息。星型模式不会保留该列曾经包含不同值的线索。一般来说，该方法可以达到预期的效果，但也可能会导致混乱。如果存在与变化前关联的事实，就说明历史环境发生了改变。数据仓库的数据模式第2章数据仓库维度表与事实表维度表—缓慢变化维

Type1Change数据仓库的数据模式第2章数据仓库维度表与事实表维度表—缓慢变化维Type2Change多数操作型系统的变化采用变化类型2处理。变化类型2保存了变化的历史事实。描述变化前的事件的事实与过去的值关联，描述变化后的事件的事实将与新值关联。当源系统发生变化时，可以采用的第2种方法是在维度表中插入新的行。先前存在的记录不会发生任何改变。变化类型2将保存与以往值关联的事实环境，并允许新的事实与新值关联。数据仓库的数据模式第2章数据仓库维度表与事实表维度表—缓慢变化维Type2Change客户SueJohnson地址改变的问题提供了应用变化类型2的实例。随着时间的推移，客户Sue由先前居住在亚利桑那州，改变为目前居住在加利福尼亚州。她居住在亚利桑那州时提交过一些订单，居住在加利福尼亚州时提交了另外一些订单。若采用变化类型1处理客户Sue地址变化的情况，会产生一些负面效果，即重新声明了Sue地址变化前提交订单的环境。这些订单将与她目前居住的加利福尼亚州关联，即使这些订单是Sue在亚利桑那州提交的。数据仓库的数据模式第2章数据仓库维度表与事实表维度表—缓慢变化维小结（1）数据仓库针对数据源发生的变化而进行响应，这样的过程称

为缓慢变化维（2）缓慢变化类型1在响应数据源变化时，重写维度属性。维度表

不能反映历史情况。已经存在事实的历史环境被改变了。（3）数据值发生改变时，缓慢变化类型2创建了一个新版本的维度

行。尽管不能与时间关联，但维度表维护了版本历史，历史

事实的环境得到保存。数据仓库的数据模式第2章数据仓库维度表与事实表事实表事实表是度量业务过程的引擎。事实表存储用来描述过程的详细度量。事实采用外键为每个度量提供维度环境。作为过程度量的核心，事实表应包含与其描述的过程有关的所有事实，当然也包含从其他方面获得的一些事实。

事实以特定的细节层次存储，但可以通过上卷产生各种级别的维度。

由于事实具有可加性，因此这样的聚集是可能的。某些度量不具备可加性，但通常可以分解成具有可加性的组件数据仓库的数据模式第2章数据仓库维度表与事实表事实表该星型模式的事实表包含下列事实：quantity_ordered(订货数量)

order_dollars(订单总额)

cost_dollars(开销总额)

margin_dollars(利润总额)利润总额可以通过从订单总额减去开销总额获得当然放不放在事实表中与应用和设计者的风格有关。1.切片和切块(SliceandDice)在多维数据结构中,按二维进行切片,按三维进行切块,可得到所需要的数据。如在“城市、产品、时间”三维立方体中进行切块和切片,可得到各城市、各产品的销售情况。2.钻取(Drill)

钻取包含向下钻取(Drill-down)和向上钻取(Drill-up)/上卷(Roll-up)操作，钻取的深度与维所划分的层次相对应。

3.旋转(Rotate)/转轴(Pivot)通过旋转可以得到不同视角的数据。第2章数据仓库多维分析第2章数据仓库多维分析OLAP的分析方法(一)切片(slicing)、切块(dicing)按时间维向上钻取60按时间维向下钻取OLAP的分析方法(二)钻取(drill-down)第2章数据仓库多维分析OLAP的分析方法(三)旋转第2章数据仓库多维分析第2章数据仓库多维分析多维分析方法总结切片是在一部分维上选定值后，关心数据在剩余维上的数据度量。钻取是改变维的层次，变换分析的粒度；Rollup是在某一维上将低层次的细节数据概括到高层次的汇总数据；Drilldown则相反，它从汇总数据深入到细节数据进行观察。旋转式改变维的方向，即在表格中重新安排维的位置（如行列互换）。第2章数据仓库高性能物理数据仓库设计非规格化数据非规格化数据仓库的两个主要优势：1能够提高多个数量级的查询响应时间；因为大型的，长时间的表格扫描或复杂的连接可以被简单地查找预先计算出来的结果所取代；2将使系统资源被更加有效地利用；能够大量减少为获得某个特定查询的结果而需要处理的工作量。非规格化数据仓库一般方法：预聚集、列复制、预连接第2章数据仓库高性能物理数据仓库设计非规格化数据非规格化数据的三种技巧1预聚集将一个聚集函数（例如求和求平均）的结果存储以被后用的方法称为预聚集；该方法在数据库中也经常使用，因为这些聚集函数的计算往往需要扫描大量的记录，将他们计算一次后就存储在数据库中以便后续使用是非常实际的方法。例如在税务系统中经常将每月税收总计和平均存储在特定的表中。在数据仓库中，一般将详细数据进行汇总。第2章数据仓库高性能物理数据仓库设计非规格化数据非规格化数据的三种技巧2列复制当用户经常进行连接操作时，为了较少连接的代价，将经常连接的两个或者多个表合并。第2章数据仓库高性能物理数据仓库设计非规格化数据非规格化数据的三种技巧3预连接是列复制的极端情况。列复制只是将某个表的一列或者几列复制到一个表中。预连接时将某个表中的所有列复制到一个表中。就是说用指定的连接键来连接两个（多个）表格，并将连接结果存储在一个表中。表扫描的代价显然要比表连接的代价小。第2章数据仓库高性能物理数据仓库设计非规格化数据非规格化数据的三种技巧非规格化的代价：增加了磁盘容量；非规格化本身需要大量的计算和合并代价；增加了数据仓库的刷新代价。对于那些查询需要非规格化需要在实际应用用加以验证和改进，也就是说与应用环境有关。第2章数据仓库高性能物理数据仓库设计类型划分无共享型共享内存型共享磁盘型共享内存共享磁盘磁盘磁盘磁盘内存内存内存CPUCPUCPU磁盘磁盘磁盘内存内存内存网络网络网络CPUCPUCPUCPUCPUCPUSN：SharedNothingSM：SharedMemorySD：SharedDiskSM：处理器之间的通信通过共享内存，数据处理算法比较简单。最大的问题是难以扩展SD：消除了SM的问题，将所有处理器连接到磁盘上，磁盘成为可扩展性的障碍。SN：消除了SM、SD存在的问题，可扩展性最好，网络成为主要瓶颈。瓶颈SM内存SD磁盘SN网络类型第2章数据仓库高性能物理数据仓库设计并行数据处理第4章关联规则关联规则挖掘简介

关联规则（AssociationRule）是数据中所蕴含的一类重要规律，对关联规则进行挖掘是数据挖掘中的一项根本性任务，甚至可以说是数据库和数据挖掘领域中所发明的并被广泛研究的最为重要的模型。第4章关联规则关联规则挖掘简介

关联规则（AssociationRule）反映一个事物与其他事物之间的相互依存性和关联性。是对一个事物和其它事物的相互依存和关联关系的描述。若两个或多个变量的取值存在某种规律，称为关联。关联规则是寻找在同一个事件中出现的不同项的相关性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。

关联规则是数据挖掘中用于表示局部模式的最流行方法之一。关联分析的目的是挖掘隐藏在数据间的相互关系，自动探测以前未发现的蕴藏着的模式模式是一种局部概念，它反映的是数据某一方面的信息。而模型则是对数据的全面描述。第4章关联规则关联规则挖掘简介

典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。（关联规则应用最适合的应用案例）货篮数据的特点：数据量巨大，数据稀疏。(行为百万级，列至少是千级别的，行表示一次购买事件，列表示商店的商品)

对一个描述超市的数据集合来说，模式可能是“十分之一”的顾客购买了酒和牛奶。第4章关联规则关联规则挖掘简介Basket-idA1A2A3A4A5….….T110000T211110T310101T400100T501110T611100T710110T801101T910010T1001101…….

购物篮数据中，行表示顾客购买行为，列表示商店的商品。若顾客购买了某种商品，则表中表示为1，反之为0第4章关联规则关联规则挖掘简介关联规则

关联规则是对数据库中某些特定事件一起发生的概率的简单陈述；首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出；在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构。频繁模式是指数据库中频繁出现的项集。SIGMOD：SpecialInterestGrouponManagementofData第4章关联规则关联规则挖掘简介研究关联规则的目标：发现数据中的规律超市中的什么产品经常会被一起购买；-啤酒与尿布在购买了PC机后，顾客下一步一般购买什么产品；如何自动对WEB文档分类；用户上了CCTV网站后，一般将会去那些其他网站；用户购买了“XXX”书后，一般还会购买什么书;某一类纳税人在当月未纳税，则其下个月也不纳税的可能性第4章关联规则关联规则挖掘简介关联规则特别适用于稀疏的数据集合。如购物篮等。为简单起见，设所有变量都是二值的，则关联规则具有以下的形式：如果A=1，且B=1,则C=1的概率为p。其中，A、B、C是二值变量。且

p=p(C=1|A=1,B=1)，

即给定A=1，B=1时C=1的条件概率。P有时被称为规则的精度或可信度。p(C=1，A=1，B=1)称为支持度。寻找规则结构的典型目标就是寻找满足以下约束的所有规则：可信度p大于某个阈值pa，支持度大于某个阈值ps。例如寻找支持度大于0.05,可信度大于0.8的所有规则。第4章关联规则关联规则挖掘简介关于规则(Rule)表示

规则是人工智能领域研究的知识表示方法中最古老，最经典的一种表示方法。应用非常广泛。具有易于解释的优点。规则是由左侧的命题（前提或者条件）和右侧的结论组成。规则的含义是如果左侧为真，则右侧也为真。规则的左侧一般可以是合取式（conjunction）。规则具有固有的离散性，也就是说，规则左右侧均为布尔陈述。因此规则特别适合于离散型和范畴型变量建模。概率（Probabilistic）规则将此定义修改为：如果左侧为真，则右侧为真的概率是p。概率p实际上就是给定左侧后，右侧为真的条件概率。第4章关联规则关联规则挖掘简介如何从数据中发现模式？

若给定了表示模式的某种方式及这种表示方式下的所有可能模式。最原始的方法就是依次试验每种模式，并观察它是否在数据中发生。若模式的数量较小，此方法是可以接受的。但一般都不行，例如前述超市的例子。假定有5000种商品（以0,1表示是否购买）则可能的模式个数是25000个。（实际上是25000-1）若各个模式之间毫无关系。只好采用原始的方式。实际上，模式都存在大量的结构，可以使用这些模式结构引导搜索。通常各个模式之间都存在泛化关系。第4章关联规则关联规则挖掘简介关于泛化如果只要模式α出现在数据中，模式β也一定出现在数据中，则称模式β就是模式α的泛化。例如模式“至少有10%的顾客购买了香烟”是模式“至少有10%的顾客购买了香烟和啤酒”的泛化。使用模式中的泛化关系可以得到一种简单的算法来寻找出现在数据中的所有特定类型的模式。第4章关联规则关联规则挖掘简介关于频繁项集对于从变量A1,….,Ap观察到的0,1集合关联规则的形式如下：

((Ai1=1)∧(Ai2=1)∧…..∧(Aik=1))=〉Aik+1=1

可以简化为

(Ai1

∧Ai2

∧…..∧Aik=1)

像(Ai1=1)∧(Ai2=1)∧…..∧(Aik=1)这样的模式被称为项集（itemset）第4章关联规则关联规则挖掘简介关于属性值-属性值离散化若数据集的属性都是布尔值，则此数据集中挖掘的关联规则都是布尔关联规则。其它属性可以进行转换。可以将非布尔值数据转换为布尔数据值。TIDAgeSalary1353200243460035637004242100………第4章关联规则关联规则挖掘简介关于属性值-属性值离散化

上图中，挖掘某一个具体的年龄和一个具体的收入间的关联关系，由于属性取值的多样性，通常很难满足最小支持度和最小可信度阈值指标。并且一般来说，发现类似Age(41)=>Salary(4320)之类的表达显然没有多大意义。更多的情况是希望发现年龄段与收入范围间的关系。因此，可以将数量属性值划分为若干区间，按照区间的划分将一个数量属性分解为若干个布尔属性。例如将年龄按照[20，30），[30，40），…

收入按区间[2000，3000），[3000，4000），…..进行划分。第4章关联规则IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。

给定一组事务；产生所有的关联规则；满足最小支持度和最小可信度。关联规则的基本模型及算法

设I={i1,i2,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。第4章关联规则关联规则的基本模型及算法第4章关联规则关联规则的基本模型及算法

关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support(X)，规则的信任度为

support(XY)／support(X)。这是一个条件概率P(Y|X)。也就是：support(XY)=P(XY)confidence(XY)=P(Y|X)第4章关联规则关联规则的基本模型及算法关联规则的挖掘一般分为两个步骤。（1）找出所有支持度大于等于最小支持度阈值的频繁项集。（2）由频繁项集生成满足可信度阈值的关联规则。第一步工作相当费时，第二步相对容易得多。所以关联规则算法的性能主要由第一步决定。第4章关联规则关联规则的基本模型及算法Basket-idA1A2A3A4A5….….T110000T211110T310101T400100T501110T611100T710110T801101T910010T1001101…….第4章关联规则关联规则的基本模型及算法关联规则的典型数据挖掘算法组件：

1任务：描述变量之间的关联关系；

2结构：用概率表示的“关联规则”模式；

3评分函数：可信度与支持度的阈值；

4搜索方式：系统搜索，带剪枝的广度优先；

5数据管理技术：多重线性扫描。第4章关联规则关联规则的基本模型及算法关于评分函数关联规则的评分函数是简单的二择一函数。有两个阈值：可信度Pa，支持度Ps。

Ps是规则支持度的下限。当我们想要至少覆盖10%时，Ps=.1Pa是规则可信度的下限。当我们想要精度不低于90%，Pa=.9

若一个模式满足上述两个条件，则得分为1，否则为0。因此，算法的目标就是寻找得分为1的规则。

所有关联规则的数量非常巨大，前面提到5000种商品共有25000种模式。但可用评分函数的优势，可以将平均运行时间将到一个可以接受的范围。第4章关联规则关联规则的基本模型及算法关于评分函数注意若P(A=1)≤Ps，且P(B=1)≤Ps中任何一个成立。则

P(A=1,B=1)≤Ps。

因此，可以首先找概率大于Ps的所有单个事件（线性扫描一次）。若事件（或一组事件）大于Ps，则称其为频繁项集（频繁1项集）。然后，对这些频繁事件所有可能对作为容量为2的候选频繁集合。

第4章关联规则关联规则的基本模型及算法关于评分函数：更一般的情况下。当从容量为K-1的频繁项集生成容量为K的频繁项集时，可以剪除任何容量为K的集合。只要它包含的K-1项的子集，且该子集在K-1级是不频繁的。例如，若有容量为2的频繁项集（A=1，B=1）及（B=1,C=1）。将其组合为容量为3的频繁项集（A=1，B=1，C=1）若存在（A=1，B=1）是不频繁的，则（A=1，B=1，C=1）是不频繁的，因此可以将其剪除。第4章关联规则关联规则的基本模型及算法关于评分函数注意这种剪除可在不直接搜索数据的情况下进行，因此提高了计算速度。确定了修剪后的容量为K的频繁项集后，对数据库再执行一次线性扫描以确定那些集合是频繁的。然后将确定后的容量为K的频繁项集进行组合，以生成所有可能的含有K+1个事件的频繁集合，然后再修剪，再扫描一次数据，直到无法产生新的频繁集。第4章关联规则关联规则的基本模型及算法频繁项集的挖掘问题可以用图形形式表示。所有项集能构成的组合用图所示的集合枚举树（Set-enumerationTree）表示。集合枚举树是一颗排序树。树中每个节点表示一种项集组合。树根是空集。以下依次为1项集，2项集，3项集，….频繁项集的数据挖掘问题实际上是从集合枚举树中找一条分割线使分割线上的项集是频繁的，分割线下的项集是非频繁的。为找出此分割线，需要以一定的策略遍历该树。第4章关联规则关联规则的基本模型及算法{}abcdeabacadaebcbdbecdcedeabcabdabeacdaceadebcdbcebdecdeabcdabceabdeacdebcdeabcde第4章关联规则关联规则的基本模型及算法支持度和可信度

查找所有的规则X&YZ具有最小支持度和可信度支持度,

s,一次交易中包含{X、Y、Z}的可能性可信度,

c,

包含{X、Y}的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户第4章关联规则关联规则的基本模型及算法Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,F第4章关联规则关联规则的基本模型及算法ForruleA

C:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%第4章关联规则关联规则的基本模型及算法Apriori算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.思想:Apriori使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集. 首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描..第4章关联规则关联规则的基本模型及算法Apriori算法频繁项集

为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系LkCk

。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。第4章关联规则关联规则的基本模型及算法Apriori算法关联规则的性质性质1：频繁项集的子集必为频繁项集。

性质2：非频繁项集的超集一定是非频繁的。

Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。

第4章关联规则关联规则的基本模型及算法Apriori算法关联规则的性质Apriori算法是反单调的即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。第4章关联规则关联规则的基本模型及算法{}abcdeabacadaebcbdbecdcedeabcabdabeacdaceadebcdbcebdecdeabcdabceabdeacdebcdeabcde若{c,d,e}是频繁的，则其子集{c,d}、{c,e}、{d,e}{c}、{d}、{e}一定是频繁的反之，如果一个集合是非频繁的，则其超集必然也是非频繁的第4章关联规则关联规则的基本模型及算法为什么需要支持度和可信度？支持度是一种重要的度量，因为支持度低的规则可能只是偶然出现。从商务角度看，低支持度的规则多半也是不令人感兴趣的，因为对顾客很少同时购买的商品进行促销没有意义。另一方面，可信度度量通过规则进行推理的可靠性。对于给定的规则X-〉Y，可信度越高，Y在包含X的事务中出现的可能性就越大。可信度也提供了Y在给定X下的条件概率的估计回顾Apriori算法L1C2L2C3L3候选键产生1、连接步2、剪枝步2项集建立3项集建立频繁项集产生计算步骤问题：处理庞大的候选集合问题：重复扫描数据表检查候选模式第4章关联规则关联规则的基本模型及算法第4章关联规则关联规则的基本模型及算法Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈:候选集生成巨大的候选集:扫描数据库次数：如果最长的模式是n的话，则需要n

次数据库扫描Apriori算法的瓶颈Apriore算法小结，两个问题：

1、复杂的候选建立过程消耗了大量的时间、空间和内容；

2、对数据库的多遍扫描；第4章关联规则关联规则研究趋势Apriori算法的几个注意点：Apriori算法理论上是指数级别的算法。设I中项目的数目为m，则整个

项集集合空间的规模将达到O（2m）。然而，该算法充分利用了数据的

稀疏性和较高的最小支持度值来保证算法的可行性和高效性。在购物

篮数据分析中，数据的稀疏性（Sparseness）表现在“尽管商场会出售

数量巨大的各种商品，但每位顾客一次仅会购买很少的一部分。”由于该算法不需要将数据集一次性装入内存中，所以它可以应用于规模

巨大的数据集合上。算法仅需要对数据集合扫描K次，其中K是最大项

集的大小。在实际应用中，K往往很小。一旦给定了一个事务集T，一个最小支持度值和一个最小置信度值，则T

中频繁项目集集合就被唯一确定了。任何算法都应该找出同一个频繁项

目集，这一特性在其他很多算法中都不成立。比如分类和聚类。第4章关联规则关联规则研究趋势目前主要的研究集中在改进关联规则算法的效率：1）减少对数据库扫描的遍数；2）抽样指导方法；3）并行化4）对结构模型增加额外的约束第4章关联规则关联规则研究趋势减少对数据库扫描的遍数FP树是继Apriori之后关联规则挖掘的一个里程碑。频繁项集的建立仅经过两遍数据库扫描，并且不产生候选建立过程。FP树是一种扩展的前缀树结构，存储关键的和频繁模式的数量。节点中的树仅仅包含频繁1项集。FP树的优点表现在三个方面：

FP树是一种对原始数据库数据的压缩表达，仅有频繁项可以加入到树中；其他不相关的数据被剪枝；该算法仅仅扫描数据库两遍。

FP树采用分治方法减少了后续的条件FP树的数量。第4章关联规则关联规则研究趋势抽样指导方法抽样方法一般包括两个步骤：1、获取数据库的抽样并获得抽样的关联规则；2、将上述结果在数据库中验证。Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FTransaction-idItemsbought10A,B,C11C,E,G……20A,C30A,D40B,E,F…..….规则集Validation第4章关联规则关联规则研究趋势并行化

利用并行系统可以利用其高速和高存储特点。FDM算法是Apriori算法的并行化实现（采用SN结构）。从研究上看，在此方面可以有所作为。第4章关联规则关联规则研究趋势关联规则挖掘的约束

多数发现频繁模式的数据挖掘技术针对数据集合。一般，其目标是发现频繁出现在数据集中（超过用户定义的域值）的所有模式。但用户往往想要通过增加额外的约束限制被发现的模式，例如对模式结构的约束。数据挖掘系统应该运用这些约束加速数据挖掘的过程。应用到约束驱动的模式发现主要分以下几类：

1、后处理技术。在挖掘过程完成后，将不满足用户约束要求的模式过滤掉；

2、模式过滤技术。将约束集成到数据挖掘过程中，只建立满足用户约束的模式；

3、数据集合过滤。将不满足用户约束的数据集合过滤掉。

第4章关联规则FP-TREE用Frequent-Patterntree(FP-tree)结构压缩数据库,-高度浓缩，同时对频繁集的挖掘又完备的-避免代价较高的数据库扫描开发一种高效的基于FP-tree的频繁集挖掘算法-采用分而治之的方法学：分解数据挖掘任务为小任务-避免生成关联规则:只使用部分数据库!关联规则研究趋势第4章关联规则FP-TREEFP树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树种的一条路径来构造。由于不同的事务可能有若干个相同的项，因此它们的路径可能部分重叠。路径相互重叠越多，使用FP树结构获得的压缩效果越好。关联规则研究趋势第4章关联规则关联规则研究趋势利用FP-TREE方法实现频繁项集挖掘（示例）TIDITEMSBought100a,b,c,d,e,f,g,h200