1、什么是数据挖掘？

数据挖掘更正确的命名为“从数据中挖掘知识”，是数据中的知识发现（KDD）的同义词。数据挖掘是从大量数据中挖掘有趣模式和知识的过程，数据源包括数据库、数据仓库、web、其他信息存储库或动态的流入系统的数据。

2、知识发现的过程是什么？

知识发现的过程为：

（1）数据清理（消除噪声和删除不一致的数据）

（2）数据集成（多种数据源可以组合在一起）

（3）数据选择（从数据库中提取与分析任务相关的数据）

（4）数据变换（通过汇总或聚集操作，把数据变换和统一成适合挖掘的形式）

（5）数据挖掘（基本步骤，使用智能方法提取数据模式）

（6）模式评估（根据某种兴趣度度量，识别代表知识的真正有趣的模式）

（7）知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）

3、什么类型的数据可以挖掘？

数据挖掘可以作用于任何类型的数据，数据的最基本形式是数据库数据、数据仓库数据、事务数据。也可以用于数据流、有序/序列数据、图或网络数据、空间数据、文本数据、多媒体数据和万维网。

（1）数据库数据

由一组内部相关的数据和一组管理和存储数据的软件程序组成。关系数据库是表的汇集，每个表被赋予一个唯一的名字，含有一组属性（列或字段），并且通常存放大量元组（记录或行）。每个元组代表一个对象，被唯一的关键字标识，并被一组属性值描述。通常为关系数据库构建语义数据模型，如实体-联系（ER）数据模型。

（2）数据仓库

数据仓库是一个从多个数据源收集的信息存储库，存放在一致的模式下，并且通常驻留在单个站点上。数据存储从历史的角度提供信息，并且通常是汇总的。数据仓库用称作数据立方体的数据结构建模。每个维对应于模式中的一个或一组属性，每个单元存放某种聚集度量值

(3)事务数据

每个记录代表一个事务

4、什么类型的模式可以挖掘？

数据挖掘功能用于指定数据挖掘任务发现的模式，一般而言，这些任务可以分为两类：描述性和预测性。描述性挖掘任务刻画目标数据中数据的一般性质，预测性挖掘任务在当前数据上进行归纳，以便进行预测。

（1）类/概念描述：特征化与区分

数据可以与类或概念相关联。数据特征化是目标类数据的一般特性或特征的汇总。将数据汇总和特征化的方法：基于统计度量和图的简单数据汇总、基于数据立方体的OLAP上卷操作、面向属性的归纳技术。数据特征的输出可以用多种形式提供：饼图、条图、曲线、多位数据立方体、表；数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。

（2）挖掘频繁模式、关联和相关性

频繁模式包括频繁项集（基础）、频繁子序列和频繁子结构。

（3）用于预测分析的分类与回归

     分类预测类别标号，而回归建立连续值函数模型。回归分析是最常用的数值预测统计学方法，相关分析可能需要在分类和回归之前进行，它试图识别与分类和回归过程显著相关的属性。

（4）聚类分析

聚类分析数据对象，而不考虑类标号。

（5）离群点分析

大部分数据挖掘都将离群点作为噪声或异常而丢弃，然而在一些应用中可以做离群点分析或异常挖掘

5、支持度与置信度

支持度表示事物数据库中满足规则的事物所占的百分比，置信度评估所发现的规则的确信程度。

准确率即被一个规则正确分类的数据所占的百分比，覆盖率类似于“支持度”表示规则可以作用的数据所占的百分比。

第2章 认识数据

1、数据对象与数据类型

数据对象又称样本、实例、数据点或对象，数据对象存放在数据库中，则他们为数据元组，即数据库的行对应于数据对象，列对应于属性。

属性：表示数据对象的一个特征（属性、维、特征、变量）

标称属性：一些符号或事物的名称（分类的或枚举的），标称属性可以取整数值，但是不能把它视为数值属性。

二元属性：是一种标称属性，只有两种状态，0或1,0通常表示该属性不出现，1表示出现。二元属性有对称与非对称两种。

序数属性：可能的值之间具有意义的序或秩评定，但是相继值之间的差是未知的。中心趋势可以用它的众数和中位数表示，但不能定义均值。

数值属性：定量的，用整数或实数值表示，数值属性可以是区间标度的或比率标度的。除了中心趋势度量中位数和众数之外，还可以计算均值。比率标度属性是具有固有零点的数值属性。

离散属性与连续属性：离散属性具有有限或无限可数个值，可以用或不用整数表示

2、数据的基本统计描述

（1）中心趋势度量，度量数据分布的中部或中心位置，包括均值、加权平均、中位数、众数和中列数；均值对极端值比较敏感，为了抵消少数极端值的影响，可以使用截尾均值；对于非对称数据，数据中心最好用中位数；众数是集合中出现最频繁的值，分为单峰、双峰和三峰，对于适度倾斜的单峰数值数据，有经验公式：均值-众数=3*（均值-中位数）；中列数是数据集的最大和最小值的平均值。

（2）数据的散布，最常见度量是极差、四分位数、四分位极差、五数概括和盒图，以及数据的方差和标准差。极差：最大值与最小值之差；分位数：是取自数据分布的每隔一定间隔上的点，把数据划分成基本上大小相等的连贯集合；识别可以的离群点的通常规则是，挑选落在第3个四分位数之上或第1个四分位数之下至少1.5*IQR处的值，IQR为四分位数极差（Q3-Q1）；五数概括由中位数、四分位数Q1和Q3、最小和最大观测值组成；盒图是一种流行的分布的直观表示。

方差和标准差指出数据分布的散布程度。低标准差意味数据观测趋向于非常靠近均值，高标准差表示数据散布在一个大的值域中。

（3）可视化审视数据，包括条图、饼图和线图，还有分位数图、分位数-分位数图、直方图和散点图。分位数图：是一种观察单变量数据分布得简单有效方法，显示给定属性的所有数据。分位数-分位数图（q-q图），可以观察从一个分布到另一个分布是否有漂移。直方图：概括给定属性X的分布的图形方法；散点图：确定两个数值变量之间看上去是否存在联系、模式或趋势的最有效的图形方法之一。

基本数据描述和图形统计显示有助于识别噪声和离群点，对于数据清理特别有用。

3、数据可视化

数据可视化旨在通过图形表示清晰有效地表达数据。

（1）基于像素的可视化技术

像素的颜色反应该维的值，每维创建一个窗口。

（2）几何投影可视化技术

几何投影技术帮助用户发现数据集的投影，二维散点图通过不同颜色或形状表述不同的数据点，三维散点图使用笛卡尔坐标系的三个坐标轴，对于维数超过4的数据集，散点图一般不太有效。平行坐标可以处理更高的维度，绘制n个等距离、相互平行的轴，每维一个。

（3）基于图符的可视化技术

两种流行的图符技术——切尔诺夫脸和人物线条画。切尔诺夫脸：有助于揭示数据中的趋势，脸的要素表示维的值，局限性为在表示多重联系的能力方面，且无法显示具体的数据值，此外面部特征因感知的重要性而异。人物线条画：把数据映射到5段人物线条画中，其中每个画都有四肢和一个躯体。

（4）层次可视化技术

把所有维划分成子集，这些子空间按层次可视化。

    （5）可视化复杂对象和关系

标签云是用户产生的标签的统计量的可视化。标签云的用法有两种，单个术语的标签云可以使用标签的大小表示该标签被不同的用户用于该术语的次数，多个术语上可视化标签统计量时，使用标签的大小表示该标签用于的术语数，即标签的人气。

4、度量数据的相似性和相异性

（1）数据矩阵与相异性矩阵

数据矩阵（对象-属性结构），每行对应于一个对象，每列代表一个属性，也称为二模矩阵

相异性矩阵（对象-对象结构），存放n个对象两两之间的邻近度，只包含一类实体，称为单模矩阵

相似性度量可以表示成相异性度量的函数

（2）标称属性的邻近性度量

标称属性对象之间的相异性可以根据不匹配率来计算   

  M是匹配的数目（i，j取值相同状态的属性数），p是刻画对象的属性总数；

（3）二元属性的邻近性度量

基于非对称的二元属性的相异性称为非对称的二元相异性，非对称的二元属性，两个状态不是同等重要的，若取值为1被认为比取值为0更有意义，负匹配t被认为不重要而忽略，则i，j相异性为

（4）数值属性的相异性

最流行的距离度量是欧几里得距离

曼哈顿距离

欧几里得距离和曼哈顿距离都满足数学性质：

非负性：d（i，j）≥0：距离是一个非负的值

同一性：d（i，j）=0：对象到自身的距离为0

对称性：d（i，j）=d（j，i）：距离是一个对称函数

三角不等式：d（i，j）≤d（i，k）+d（k，j）从对象i到对象j的距离不会大于途径任何其他对象k的距离

闵可夫斯基距离 

（5）序数属性的邻近性度量

第3章 数据预处理

1、为什么要进行数据预处理？ 

数据质量涉及很多因素，包括准确性、完整性、一致性、时效性、可信性和可解释性。不正确、不完整和不一致的数据是现实世界的大型数据库和数据仓库共同特点。数据预处理可以改进数据的质量，有助于提高挖掘过程的准确率和效率。

2、数据预处理的主要任务

数据预处理的主要步骤：数据清理、数据集成、数据归约和数据变换。

（1）数据清理通过填写缺失值，光滑噪声数据，识别或删除离群点并解决不一致性来“清理”数据；数据归约得到数据集的简化表示，数据归约策略包括维归约和数值归约。维归约使用数据编码方案，以便得到原始数据的简化或“压缩”，包括数据压缩技术（小波变换和主成分分析）、属性子集选择和属性构造，在数值归约中，使用参数模型（回归和对数线性模型）或非参数模型（直方图、聚类、抽样或数据聚集），用较小的表示取代数据。

缺失值

（2）数据集成：合并来自多个数据存储的数据，存放在一个一致的数据存储中，如存放在数据仓库中。

冗余：一个属性如果能由另一个或另一组属性“导出”，则这个属性可能是冗余的。有些冗余可以被相关分析检测，对于标称数据，我们使用卡方检验，对于数值属性，我们使用相关系数或协方差；

——标称数据的卡方检验：将两个数据元组用相依表显示；

——数值数据的相关系数：相关系数越大，相关性越强，可以作为冗余而被删除；

——数值数据的协方差：

（3）数据归约

数据归约策略包括维归约、数量归约和数据压缩。维归约减少所考虑的随机变量或属性的个数，维归约的方法包括小波变换和主成分分析；数量归约用替代的、较小的数据表示形式替换原数据；数据压缩使用变换，以便得到原数据的归约或“压缩”表示，分为有损和无损。

——小波变换是一种线性信号处理技术，小波变换后的数据可以截短，仅存放一小部分最强的小波系数，就能保留近似的压缩数据，可以用于数据，如数据立方体。

——主成分分析搜索k个最能代表数据的n维正交向量，其中k≤n，原数据投影到一个小得多的空间，导致维归约。基本过程如下：

1) 对输入数据规范化，使得每个属性都落入相同的区间

2)计算k个标准正交向量，作为规范化输入数据的基。这些是单位向量，每一个都垂直于其他向量。这些向量称为主成分。输入数据是主成分的线性组合。

3)对主成分按照“重要性”降序排列，去掉较弱的成分来归约数据。主成分分析能够更好的处理稀疏数据，小波变换更适合高维数据。

——属性子集选择，通过删除不相关或冗余的属性减少数据量，选择的目标是找出最小属性集。

——回归和对数线性模型，可以用来近似给定的数据，在线性回归中，对数据建模，使之拟合到一条直线。

——直方图，属性值划分规则等宽、等频

——聚类，把数据元组看做对象，将对象划分为群或簇，用数据的簇代表替换实际数据。

——抽样，用数据小得多的随机样本表示大型数据集。

——数据立方体聚集

3、数据变换与数据离散化

  数据变换策略包括光滑、属性构造、聚集、规范化、离散化、由标称数据产生概念分层

第4章 数据仓库与联机分析处理

1、什么是数据仓库？

数据仓库是一种数据库，它与单位的操作数据库分别维护。是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理者的决策过程。通常只需要两种数据访问操作：数据的初始化装入和数据访问。我们把建立数据仓库看做构建和使用数据仓库的过程，数据仓库的构建需要数据集成、数据清理和数据统一。

2、操作数据库系统与数据仓库的区别？

联机操作数据库系统的主要任务是执行联机事务和查询处理，这种系统称作联机事务处理系统（OLTP），数据仓库系统可以用不同的格式组织和提供给数据，以便满足不同用户的形形色色的需求，这种系统叫做联机分析处理系统（OLAP）

分离的主要原因是有助于提高两个系统的性能。

1)操作数据库为已知的任务和负载设计，数据仓库的查询通常很复杂，在操作数据库上处理OLAP查询，可能会大大降低操作任务的性能

2)操作数据库支持多事务的并发处理，需要并发控制和恢复机制，OLAP查询只需要对汇总和聚集数据记录进行只读访问，会大大降低OLTP系统的吞吐量

3)两种系统中数据的结构、内容和用法都不相同

4、数据仓库的结构？

数据仓库是一种多层次体系结构，通常采用三层体系结构：

底层是仓库数据库服务器，使用后端工具和实用程序，由操作数据库或其他外部数据源提取数据，放入底层。

中间层是OLAP服务器，典型实现使用关系OLAP模型或使用OLAP模型

顶层是前端客户层，包括查询和报告工具、分析工具或数据挖掘工具。

5、数据仓库模型？

从结构的角度看，数据仓库有三种模型：企业仓库、数据集市和虚拟仓库。

企业仓库：提供企业范围内的数据集成，通常来自一个或多个操作数据库系统或外部信息提供者，并且是多功能的。

数据集市：包含企业范围数据的一个子集，范围限于选定的主题

虚拟仓库：虚拟仓库是操作数据库上视图的集合

对于开发数据仓库系统，一种推荐的方法是以递增、进化的方式实现数据仓库，首先在一个合理短的时间内定义一个高层次的企业数据模型，在不同的主题和可能的应用之间，提供企业范围的、一致的、集成的数据视图。其次，基于相同的企业数据模型，并行的实现的数据集市和企业数据仓库，再次，通过中心服务器集成不同的数据集市，构造分布数据集市，最后构造一个多层数据仓库

元数据是关于数据的数据，在数据仓库中，元数据是定义仓库对象的数据。包括以下内容：数据仓库结构的描述、操作元数据、用于汇总的算法、由操作环境到数据仓库的映射、关于系统性能的数据、商务元数据。

6、数据仓库建模

数据仓库和OLAP工具基于数据模型，这种模型将数据看做数据立方体形式。

（1）数据立方体：允许以对数据建模和观察，每个维都可以有一个与之相关联的表（维表）,n维数据立方体显示成n-1维立方体的序列。

（2）数据模型的模式：最流行的数据仓库的数据模型是数据模型，可以是星形模式、雪花模式或事实星座模式。

——星形模式，最常见的模型范型是星形模式，数据仓库包括一个大的中心表（事实表），包含大批数据并且不含冗余，一组小的附属表（维表），每维一个。

——雪花模式，是星形模式的变种，雪花模式的维表可能是规范化形式，以便减少冗余，这种表易于维护，并节省存储空间。由于执行查询需要更多的连接操作，雪花结构可能降低浏览的效率，因此不如星形模式流行。

——事实星座，复杂的应用可能需要多个事实表共享维表，这种模式称为星系模式或事实星座。

数据仓库收集了关于整个组织的主题信息，因此是企业范围的，数据仓库多选用星座模式；数据集市是数据仓库的一个部门子集，针对选定的主题，因此是部门范围的，数据集市多采用星形或雪花模式

（3）维：概念分层的作用，概念分层定义一个映射序列，将低层概念集映射到较高层、更一般的概念

（4）度量的分类和计算，立方体度量是一个数值函数，该函数可以对数据立方体空间的每个点求值，度量根据其所用的聚集函数可以分为三类：分布的、代数的和整体的.

     ——分布的，数据划分成n个集合，将函数用于每一个部分，得到n个聚集值，如果函数用于n个聚集值得到的结果和将函数用于整个数据集得到的结果是一样的，则该函数可以用分布方式计算。例如sum（）、count（）。

——代数的，一个聚集函数如果能够用一个具有M个参数的代数函数计算，而每个参数都可以用一个分布聚集函数求得，则它是代数的。例如avg（）=sum（）/count（）

——整体的，一个聚集函数如果描述它的子聚集所需的存储没有一个常数界，则它是整体的。例如median()

（5）典型的OLAP操作，上卷操作通过延一个维的概念分层向上攀升或者通过维归约在数据立方体上进行聚集；下钻是上卷的逆操作；切片和切块，切片操作在给定的立方体的一个维上进行选择，导致一个子立方体；转轴是一种目视操作，转动数据的视角，提供数据的替代表示；其他OLAP操作，钻过执行涉及多个事实表的查询，钻透使用关系SQL机制，钻透到数据立方体的底层，到后端关系表。 

——OLAP系统与统计数据库

（6）查询数据库的星网查询模型

    星网模型由从中心点发出的射线组成，其中每一条射线代表一个维的概念分层。

7、数据仓库的设计与使用

关于数据仓库的设计，必须考虑四种不同的视图：自顶向下视图、数据源视图、数据仓库视图和商务查询视图。

从软件工程的角度看，数据仓库的设计和构造包含以下步骤：规划、需求研究、问题分析、仓库设计、数据集成和测试、部署数据仓库。大型软件系统可以用两种方法开发：瀑布式方法和螺旋式方法。瀑布式方法在进行下一步之前，每一步都进行结构的和系统的分析，螺旋式方法实际功能渐增的系统的快速产生，相继发布之间的间隔很短。

在许多公司，数据仓库用作企业管理的计划——执行——评估“闭环”反馈系统的必要部分。有三类数据仓库应用：信息处理、分析处理和数据挖掘。信息处理支持查询和基本的统计分析，并使用交叉表、表、图表或图进行报告。基于查询，可以发现有用的信息；分析处理支持基本的OLAP操作，包括切片与切块、下钻、上卷和转轴。由用户选定的数据仓库子集，在多粒度上导出汇总的信息。数据挖掘支持知识发现，包括找出隐藏的模式和关联，构造分析模型，进行分类和预测，并使用可视化工具提供挖掘结果。

8、OLAP和数据挖掘相同吗？

OLAP是数据汇总/聚集工具，帮助简化数据分析；数据挖掘自动发现隐藏在大量数据中的隐含模式和有趣知识。OLAP工具的目标是简化和支持交互数据分析；数据挖掘工具的目标是尽可能自动处理，尽管允许用户指导这一过程。数据挖掘包含数据描述和数据建模，OLAP的功能基本上是用户指导的汇总和比较。数据挖掘不限于分析存放在数据仓库中的数据，可以分析比数据仓库提供的汇总数据粒度更细的数据。也可以分析事务的、空间的、文本的和多媒体数据。

9、数据库OLAM

数据挖掘特别重要：数据仓库中数据的高质量，环绕数据仓库的信息处理基础设施、基于OLAP的数据探索、数据挖掘功能的联机选择

10、数据仓库的实现

数据仓库系统要支持高校的数据立方体计算技术、存取方法和查询处理技术。

（1）数据立方体的有效计算

数据分析的核心是有效计算许集合上的聚集，这些聚集称为分组，每个分组用一个方体表示，分组的集合形成定义数据立方体的方体的格。

——compute cube操作与维灾难

Compute cube操作在操作指定的维的所有子集上计算聚集。数据立方体是方体的格；

对于不同的查询，联机分析处理可能需要访问不同的方体。因此，提前计算所有的或者至少一部分方体是个好主意。预计算的主要挑战是，如果数据立方体中素有的方体都预先计算，所需的存储空间可能爆炸，特别是当立方体包含许时。这个问题成为维灾难。如果每个维没有概念分层，n维数据立方体有2n个方体;

——部分物化：方体的选择计算

给定基本方体，方体的物化有三种选择：不物化、完全物化、部分物化。不物化即不预先计算任何“非基本”方体，这导致回答查询时实时计算昂贵的聚集，速度非常慢；完全物化即预先计算所有方体，需要海量存储空间；部分物化即有选择的计算整个可能的方体集中一个适当的子集，部分物化是存储空间和响应时间两者之间的折中。冰山立方体是一个数据立方体，只存放聚集值大于某个最小支持度阈值的立方体单元，外壳立方体涉及预计算数据立方体的只有少量维的方体。

（2）索引OLAP数据

——位图索引，允许在数据立方体中快速搜索，如果给定的属性域包含n个值，则位图索引中每项需要n个位，如果数据表给定航上该属性值为v，则在位图索引的对应行，该值的位为1，该行的其他位均为0

——连接索引，登记来自关系数据库的两个关系的可连接行，连接索引可以跨越，形成复合连接索引。

（3）OLAP查询的有效处理

物化方体和构造OLAP索引结构的目的是加快数据立方体查询处理的速度，查询处理应首先确定哪些操作应当在可利用的方体上执行，然后确定相关操作应当使用哪些物化的方体。

（4）OLAP服务器结构：ROLAP/MOLAP/HOLAP的比较

——关系OLAP（ROLAP）服务器，一种中间服务器，使用关系的或扩充关系的DBMS存储并管理数据仓库数据，OLAP中间件支持其余部分

——OLAP（MOLAP）服务器，通过基于数组的存储引擎，支持数据的视图。多数都采用两级存储表示来处理稠密和稀疏数据集：识别较稠密的子立方体并作为数组结构存储，而稀疏子立方体使用压缩技术，提高存储利用率

——混合OLAP（HOLAP）服务器，结合ROLAP和MOLAP技术、

——特殊的SQL服务器，提供高级查询语言和查询处理，在只读环境下，在星形和雪花形模式下支持SQL查询。

（5）数据泛化：面向属性的归纳

数据泛化通过把相对底层的值用较高层概念替换来汇总数据，或通过减少维数，在涉及较少维数的概念空间汇总数据。概念描述，概念通常指数据的汇集，概念描述产生数据的特征和比较描述，当被描述的概念涉及对象类时，有时也称概念描述为类描述。

——数据特征的面向属性的归纳，数据立方体方法基本上是基于数据的物化视图，通常在数据仓库中预先计算，面向属性的归纳基本上是面向查询的、基于泛化的、联机的数据分析处理技术。面向属性归纳的基本思想是：首先使用数据库查询收集任务相关的数据，然后通过考察任务相关数据中每个属性的不同值的个数进行泛化。

属性删除基于如下规则：如果出示工作关系的某个属性有大量不同的值，但是在该属性上并没有泛化操作符，或者它的较高层概念用其他属性表示，则应当将该属性从工作关系中删除

属性泛化基于以下规则：如果初始工作关系的某个属性有大量不同的值，并且该属性上存在泛化操作符的集合，则应当选择一个泛化操作符，并将它用于该属性。

属性泛化控制有两种技术：属性泛化阈值控制：对所有的属性设置一个泛化阈值或对每个属性设置一个阈值，如果属性不同值个数大于该属性泛化阈值，则进行进一步的属性删除或属性泛化；广义关系阈值控制：为广义关系设置一个阈值，如果广义关系中不同元组的个数超过该阈值，则进一步泛化。这两种技术可以顺序使用，首先使用属性泛化阈值控制技术泛化每个属性，然后使用关系阈值控制进一步压缩广义关系。

第5章 数据立方体

1、数据立方体计算：基本概念

（1）立方体物化

基本方体的单元是基本单元，非基本方体的单元是聚集单元。聚集单元在一个或多个维上聚集，其中每个聚集维用单元记号中的*指示。假设有一个n维数据立方体，令a=（a1，a2，....，an，measures）是一个单元，取自构成数据立方体的一个方体。如果{a1，a2，....，an}中恰有m（m≤n）个值不是*，则我们说a是m维单元，如果m=n，则a是基本单元；否则是聚集单元。

完全预计算的立方体为完全立方体，部分物化的立方体为冰山立方体。一种计算冰山立方体的朴素方法是，首先计算完全立方体，然后剪去不满足冰山条件的单元。另一种有效的方法是直接计算冰山立方体，而不计算完全立方体。引入冰山立方体将减轻计算数据立方体中不重要聚集单元的负担。

（2）数据立方体计算的一般策略

1　排序、散列和分组，在立方体计算中，对共享一组相同维值的元组进行聚集，需要利用排序、散列和分组对数据进行访问和分组，以便有利于聚集的计算

2　同时聚集和缓存中间结果，从先前计算的较低层聚集而不是从基本事实表计算较高层聚集，从缓存的中间计算结果同时聚集可以减少开销很大的磁盘IO操作

3　当存在多个子女方体时，由最小的子女聚集。当存在多个子女方体时，由先前的最小子女方体计算父母方体更有效。

4　可以使用先验剪枝方法有效的计算冰山立方体。对于数据立方体，先验性质表述如下：如果给定的单元不满足最小支持度，则该单元的后代也都不满足最小支持度。通常的冰山条件是单元必须满足最小支持度阈值，如最小计数或总和。

2、数据立方体的计算方法

  （1）完全立方体计算的多路数组聚集

多路数组聚集方法使用数组作为基本的数据结构，计算完全数据立方体。

第6章 挖掘频繁模式、关联和相关性：基本概念和方法

频繁模式是频繁的出现在数据集中的模式，如果一个子结构频繁出现，则称它为（频繁的）结构模式。对于挖掘数据之间的关联、相关性和许多其他有趣的联系，发现这种频繁模式起着至关重要的作用。此外，它对数据分类、聚类和其他数据挖掘任务也有帮助。

1、基本概念

（1）规则的支持度和置信度是规则兴趣度的两种度量，分别反映所发现规则的有用性和确定性。在典型情况下，关联规则被认为是有趣的，如果它满足最小支持度阈值和最小置信度阈值。

支持度

置信度

同时满足最小支持度阈值和最小置信度阈值的规则称为强规则，用0%~100%之间的值表示。

项的集合称为项集，包含k个项的项集称为k项集。项集的出现频度是包含项集的事物数，简称为项集的频度、支持度计数或计数。

如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集的集合通常记为LK。

可以看出规则的置信度可以从A和A∪B的支持度计数推出，因此挖掘关联规则可以归结为挖掘频繁项集。

（2）一般而言，关联规则的挖掘是一个两步的过程

1、找出所有的频繁项集：根据定义，这些项集的每一个频繁出现的次数至少与预定义的最小支持计数min_sup一样

2、由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。

如果一个项集是频繁的，则它的每个子集也是频繁的，一个长项集将包含组合个数较短的频繁子项集。

项集X在数据集D中是闭的，如果不存在真超项集Y使得Y与X在D中具有相同的支持度计数，项集X是D中的闭频繁项集，如果X在D中是闭的和频繁的，项集X是D中的极大频繁项集或极大项集。

2、频繁项集挖掘方法

挖掘最简单形式的频繁模式方法，Apriori算法是一种发现频繁项集的基本算法。

（1）通过候选产生发现频繁项集

Apriori算法是布尔关联规则挖掘频繁项集的原创性算法，算法使用频繁项集性质的先验知识，使用一种称为逐层搜索的迭代方法，其中k项集用于探索k+1项集。

首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1。

然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集

缺点：每找出一个Lk 需要一次数据库扫描，为了提高频繁项集逐层产生的效率，使用先验性质压缩搜索空间。

先验性质：频繁项集的所有非空子集也一定是频繁的。如果一个集合不能通过测试，则它的所有超集也都不能通过测试。   

如何使用LK-1找出LK？

1、连接步：为找出LK，通过将LK-1与自身连接产生候选k项集的集合。该候选项集的集合记为CK

2、剪枝步：CK是LK的超集。扫描数据库，确定CK中每个候选的计数，从而确定LK

（2）由频繁项集产生关联规则

一旦由数据库D中的事务找出频繁项集，就可以直接由它们产生强关联规则。

根据上式，关联规则可以产生如下：

对于每个频繁项集L，产生L的所有非空子集

对于L的每个非空子集s，如果则输出规则，其中min_conf是最小置信度阈值。

（3）提高Apriori算法的效率

提高算法的效率需要一些变形。其中一些变形如下：

——基于散列的技术，一种基于散列的技术可以用于压缩候选k项集的集合CK

——事务压缩，不包含任何频繁k项集的事务不可能包含任何频繁k+1项集。因此，这种事务在其后的考虑时，可以加上标记或删除，因为产生j项集的数据库扫描不再需要他们

——划分，使用划分技术，只需要扫描两次数据库就可以挖掘频繁项集。首先，算法把D中的事务划分成n个非重叠的分区，如果D中事务的最小相对支持度阈值为min_sup，则每个分区的最小支持度计数为min_sup×该分区中的事务数，对每个分区，找出所有的局部频繁项集。然后，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。

    ——抽样，抽样方法的基本思想是，选取给定数据库D的随机样本S，然后在S而不是D中搜索频繁项集。牺牲精度换取有效性，可能丢失一些全局频繁项集。为降低这种可能性，使用比最小支持度低的支持度阈值来找出S的局部频繁项集。

——动态项集计数，将数据库划分为用开始点标记的块。可以在任何开始点添加新的候选项集

（4）挖掘频繁项集的模式增长方法

频繁模式增长（FP-growth）：首先，将代表频繁项集的数据库压缩到一颗频繁模式树，概述仍保留项集的相关信息。然后，把这种压缩后的数据库划分成一组条件数据库，每个数据库关联一个频繁项或模式段，并分别挖掘每个条件数据库。

（5）使用垂直数据格式挖掘频繁项集

Apriori算法和FP-growth算法都从TID项集格式({TID:itemset})的事务集中挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品，这种数据格式称为水平数据格式。或者，数据也可以用项-TID集格式{item：TID_set}表示，其中item是项的名称，TID_set是包含item的事务的标识符的集合，这种格式称为垂直数据格式。

（6）挖掘闭模式和极大模式

从闭频繁项集的集合可以很容易的推出频繁项集的集合和它们的支持度。挖掘闭频繁项集的一种朴素方法是，首先挖掘频繁项集的完全集，然后删除这样的频繁项集，它们是某个频繁项集的真子集，并且具有相同支持度。 一种推荐的方法是在挖掘过程中直接搜索闭频繁项集，在挖掘过程中，一旦识别闭项集就尽快对搜索空间进行剪枝。剪枝包括以下几个策略：

项合并，如果包含频繁项集X的每个事物都包含项集Y，但不包含Y的任何真超集，则X∪Y形成一个闭频繁项集，并且不必再搜索包含X但不包含Y的任何项集。

子项集剪枝：如果频繁项集X是一个已经发现的闭频繁项集Y的真子集，并且support_count(X)=support_count(Y),则X和X在集合枚举树中的后代都不可能是闭频繁项集，因此可以剪枝。

项跳过：在深度优先挖掘闭项集时，每一层都有一个与头表和投影数据库相关联的前缀项集X。如果一个局部频繁项P在不同层的多个头表中都具有相同的支持度，则可以将P从较高层头表中剪裁掉。

3、模式评估方法

提升度是一种简单的相关性度量，项集A的出现于项集B的出现，如果P(A∪B)=P(A)P(B)；否则，作为事件，项集A和B是依赖的和相关的。A和B出现之间的提升度可以通过公式计算

如果计算出的值小于1，则为负相关，意味着一个出现可能导致另一个不出现；如果计算出的值大于1，则A和B是正相关，意味着一个出现另一个也会出现；如果计算出的值等于1，则A和B是的，它们之间没有相关性。

X2相关分析

全置信度

最大置信度

余弦度量

零事务是不包含任何考察项集的事务

第7章 高级模式挖掘

1.挖掘模式

大部分研究都主要关注模式挖掘的三个方面：所挖掘的模式类型、挖掘方法和应用。基于模式的多样性，模式挖掘可以使用如下标准进行分类：

基本模式：频繁模式是满足最小支持度阈值的模式。如果不存在与P具有相同支持度的超模式P’，模式P是一个闭模式。如果不存在P的频繁超模式，模式P是一个极大模式。

基于模式所涉及的抽象层：模式或关联规则可能具有处于高、低或多个抽象层的项，则挖掘的规则集由多层关联规则组成，反之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。

基于规则或模式所涉及的维数：如果关联规则或模式中的项或属性只涉及一个维，则它是单维关联规则/模式。如果规则/模式涉及两个或多个维，则它是多为关联规则

基于规则或模式中所处理的值类型：如果规则考虑的关联是项是否出现，则为布尔关联规则；如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则。

基于挖掘选择性模式的约束或标准：被发现的模式或规则可以是基于约束的、近似的、压缩的、近似匹配的。

根据数据类型和所涉及的应用分类：

基于所挖掘的数据类型和特征，在这种情况下，频繁模式的挖掘本质上是频繁项集挖掘，也可以挖掘结构模式，即结构数据集中的频繁子结构。

基于应用领域的特定语义：多样性的应用数据导致大量不同的模式挖掘方法

基于数据分析的使用方法：频繁模式挖掘充当中间步骤，作为分类的特征提取步骤使用为基于模式的分类，基于模式的聚类显示了在聚类高维数据方面的优势

2、多层、空间中的模式挖掘

（1）挖掘多层关联规则

    关注在多个抽象层以足够的灵活性挖掘模式并易于在不同的抽象空间转换的方法。

在多个抽象层的数据上挖掘产生的关联规则为多层关联规则。对于所有层使用一致的最小支持度称为一致支持度，即在每个抽象层上挖掘时，使用相同的最小支持度阈值。缺点是较低抽象层的项不大可能像较高抽象层的项那样频繁出现。如果最小支持度阈值设置太高，则可能错失在较低抽象层中出现的有意义的关联。如果阈值设置太低，则可能会产生出现在较高抽象层的无趣的关联。

在较低层使用递减的最小支持度：抽象层越低，对应的阈值越小

使用基于项或基于分组的最小支持度，为了从具有不同支持度阈值的组中挖掘混合项模式，通常在挖掘中取所有组的最低支持度阈值。这将避免过滤掉有价值的模式。每组的最小支持度阈值要保持一致。缺点：可能产生一些多个抽象层上的冗余规则

（2）挖掘关联规则

涉及两个或多个维或谓词的关联规则称为关联规则。具有不重复谓词的关联规则称为维间关联规则。包含某些谓词多次出现的规则称为混合维关联规则。

数据库属性可能是标称的或量化的。标称属性的值是“事物的名称”。量化属性是数值的，并在值之间具有一个隐序。根据量化属性的处理，挖掘关联规则的技术可以分为两种基本方法

一种是，使用预先定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行。离散化的数值属性具有区间标号，可以像标称属性一样处理。我们称这种方法为使用量化属性的静态离散化挖掘关联规则。

第二种是根据数据分布将量化属性离散化或聚类到“箱”。这些箱可能在挖掘的过程中进一步组合。离散化的过程是动态的，这种方法挖掘的关联规则称为（动态）量化关联规则

（3）挖掘量化关联规则

——量化关联规则的基于数据立方体挖掘

——挖掘基于聚类的量化关联规则

——使用统计学理论发现异常行为

（4）挖掘稀有模式和负模式

非频繁（稀有）模式是支持度低于用户指定的最小支持度阈值的模式。可以定义负模式的方法有多种，我们考虑其中三种：

1　如果项集X和Y都是频繁的，但很少一起出现（sup（X∪Y）2　如果X和Y是强负相关的，则

但是度量不一定是零不变的。

3　假设项集X和Y都是频繁的，如果,其中是负模式阈值，则X∪Y是负相关模式。

3、基于约束的频繁模式挖掘

约束包括：知识类型约束（关联、相关、分类或聚类）、数据约束（数据集）、维/层约束（数据维、抽象层、概念分层）、兴趣度约束（支持度、置信度和相关性）、规则约束（规则形式或条件）。

对于模式空间剪枝，有三类有助于基于约束搜索空间剪枝：反单调性、单调性和简洁性。对于数据空间剪枝，有数据的简洁性和数据的反单调性两种。

（1）关联规则的元规则制导挖掘

元规则使得用户可以说明他们感兴趣的规则的语法形式，规则的形式可以作为约束，帮助提高挖掘过程的性能。元规则可以根据分析者的经验、期望或对数据的直觉，或者根据数据库模式自动产生。

（2）基于约束的模式产生：模式空间剪枝和数据空间剪枝。下载本文