数据仓库与数据挖掘

#期末考试 #数据仓库

01 知识发现总览

数据挖掘：从大型数据库的数据中提取有趣的（非琐碎的、隐含、以前未知的和潜在有用的）信息或模式，也是知识发现过程的核心。
KDD 过程的步骤：
- 学习应用领域：相关知识和应用目标。
- 创建目标数据集：数据选择。
- 数据清洗和预处理。
- 数据还原和转换：寻找特征、降维。
- 选择数据挖掘功能：总结、分类、回归、关联和聚类。
- 选择挖掘算法。
- 数据挖掘：搜索感兴趣的模式。
- 模式评估和知识展示：可视化、转换、去除多余模式。
- 使用发现的知识。
数据挖掘功能：关联、分类和预测、聚类分析、离群点分析、趋势和演变分析、其它以模式为导向的分析或统计分析。
有趣的衡量标准：容易被人类理解，在新的或测试数据上有一定程度的有效性，有潜在的用处，验证了用户想要确认的假设。
- 客观：基于统计和模式，如支持度、置信度。
- 主观：基于用户对数据的信念，如意外性、新颖性、可操作性。
- 完备性：找到所有有趣的模式。
- 优化性：只搜索有趣的模式。
  - 首先概括所有模式，然后过滤掉不感兴趣的模式。
  - 挖掘查询优化。
OLAP 挖掘：数据挖掘和数据仓库的整合。
OLAM 架构：底层数据存储、中间层MDDB（服务器上的多维数据库）、顶层OLAP/OLAM、最后是用户界面。
数据挖掘主要问题
- 挖掘方法和用户互动。
- 性能和可扩展性。
- 与数据类型的多样性有关的问题。
- 与应用和社会影响有关的问题：知识发现的应用、融合、完整性、安全隐私。

02 数据仓库

集成多个数据源，应用了数据清理和数据集成技术。
时间范围明显长于操作性数据库的时间范围，显式或隐式包含时间元素。
数据操作更新不会发生在数据仓库环境中，不需要事务处理、恢复和并发控制机制。
OLTP（在线事务处理），传统dbms的主要任务。
OLAP(在线分析处理)，数据仓库系统的主要任务，数据分析和决策。
独立数据仓库：适用DBMS和仓库的高性能，数据完整、整合和质量。
数据仓库建模：
- 星形模式：中间事实数据表连接到一组维度表。
- 雪花模式：星形模式的细化，一些维度规范化到一组较小的维度表，形成雪花形状。
- 实况星座：多个事实数据表共享维度表。
典型 OLAP 操作：
- 上钻：汇总数据，爬上层结构或缩小维度。
- 下钻：反向汇总，更高摘要到较低的汇总或详细数据，或引入新的维度。
- 切片和骰子：投影和选择。
- 枢轴（旋转）：重新定位多维数据集、可视化、3D 重新定向为一系列 2D 平面。
- 钻过（drill across）：跨越多个事实数据表。
- 钻透（drill through）：通过多维数据集底层到其后端关系表（SQL）。
维表通过记录因素的属性描述事件中包含的诸多因素。
维表的本质是多维分析空间在某个角度上的投影。
维层次信息放入信息表：计算方便但是事实表会非常庞大。
维层次信息放入各自维表中，减少了事实表的大小，但OLAP性能比上一种方式差。
维分类在事实表体现：OLAP性能好但事实表的字段数和记录数增加。
因此应当尽量减小一条记录的长度，才能避免事实表过大而难于管理，数据的粒度是影响事实表大小的关键因素。
数据量较小使用单一数据粒度，直接存储细节数据，定期数据综合。
数据量大采用双重粒度，对于细节数据只保存近期数据在数据仓库中，周期到达时将距离较远的数据导出。
数据分割：数据量过大时，检索速度很慢。将数据分散到各自物理单元里以便能够独立处理，以提高数据处理的效率。
表划分：字段数目很大的表直接存储，会导致：
- 各字段更新频率不一，放一张表中会造成数据追加工作的浪费。
- 各字段访问频率不一，放一张表影响访问效率。
- 按数据稳定性划分，或按业务规则划分。
元数据：仓库元数据、操作型元数据（数据沿袭【迁移数据的历史记录和转换路径】、数据的流通性【活动的、存档的或清除的】、监视信息【仓库使用统计、错误报告、审计跟踪】）、摘要算法、从操作环境到数据仓库的映射、业务数据（业务术语和定义、数据归属权和收费政策）。
记录系统是操作型元数据一部分，指明关系表的各个字段来源于业务数据库何处。
一般的数据库数据量相对较小，除非业务要求必须保证数据的安全性和可恢复性，否则可以不采用并行存储结构。数据仓库由于数据的巨量存储，必须采用并行存储结构，例如 RAID。
为何B树等在数据库中广泛使用的索引技术无法被直接引入数据仓库？【重要】
- B树索引要求属性必须具有许多不同的值，如项目ID、客户ID等，但是数据仓库里经常有如性别这样的二值字段。
- B树索引要求查询具有更简单的条件和更少的结果，但是数据仓库的查询经常要求返回一个较大的集合。
- 创建B树的空间复杂性和时间复杂度是巨大的，这对数据仓库来说不划算。
位图索引：适合只有几个固定值的列，如性别、婚姻状况、行政区等等，而身份证号（取值范围很广没有重复，B-tree索引较为合适）这种类型（高基数）不适合用位图索引。
联接索引：在数据仓库中，联接索引将星型架构的维度值与事实表中的行相关联。连接索引可以跨越多个维度。
数据存储策略：表合并、增加冗余、划分表。
数据立方体：高性能计算。顶层长方体只包含一个 cell。
多路数据聚合：将数组划分为块（一个适合内存的小的子立方体）。压缩稀疏数组寻址：（chunk_id，offset）。通过按最小化访问每个单元的次数的顺序访问多维数据集单元，以“多路”方式计算聚合，并降低内存访问和存储成本。维度从小到大升序排列计算。
该方法的局限性：仅对少量维数计算良好，如果有大量的维度，可以探索冰山立方体的计算方法。
数据仓库后端工具：数据抽取、数据清洗、数据转换、数据装载、刷新。
假设驱动：用户探索，巨大搜索空间。
发现驱动：预先计算指示异常的度量，指导用户在所有维度上的聚合分析，背景色表示。
三种数据仓库应用：
- 信息处理：支持使用交叉表、表格、图表和图形进行查询、基本统计分析和报告。
- 分析处理：数据仓库数据的多维分析；支持基本的OLAP操作，切片，钻取，旋转。
- 数据挖掘：基于隐藏模式的知识发现；支持关联、构建分析模型、执行分类和预测，以及使用可视化工具呈现挖掘结果。

03 数据预处理

数据处理的主要任务：
- 数据清理：填写缺失值（可能需要推断-贝叶斯/决策树）、平滑嘈杂数据（分箱、聚类、人机交互和回归）、识别删除异常值、解决不一致问题。
- 数据集成：集成多个数据库、多维数据集或文件。
- 数据转换：归一化和聚合。
- 数据减少：减少尺寸（聚合、启发式方法、决策树归纳）/数据压缩，从而体积减小，但产生相同或类似的分析结果。
- 数据离散化：数据减少的一部分，但特别重要，尤其是对于数字数据。
  - 等宽（距离）分区：最简单，但异常值可能主导，倾斜的数据难以处理好。
  - 等深（频率）分区：良好的数据伸缩性，但难以管理分类属性。
  - 基于熵的离散化。
  - 3-4-5 规则：最高有效位为基准，不同项为3、6、7、9 分三堆，2、4、8 分四堆，1、5、10 分五堆。
  - 具有最不同值的属性放置在层次结构的最低级别。

04 特征化与区分

数据泛化：将数据库中大量与任务相关的数据从较低概念级别抽象为较高概念级别。
- OLAP方法、面向属性的归纳方法。
特征化：数据立方体方法（不使用面向属性的归纳）。限制：仅处理简单非数字数据的维度和简单聚合数值的度量。缺乏智能分析，不能判断应该使用哪些维度，概括应该达到什么水平。
面向属性的归纳基本算法：
- InitialRel：查询任务相关数据，导出初始关系。
- PreGen：基于每个属性不同值，确定每个属性的泛化计划：移除或泛化的高度。
- PrimeGen：基于 PreGen，对正确的级别进行泛化，累积计数。
- Presentation：用户交互，通过钻操作调整级别，旋转，映射到规则、交叉标签和可视化演示。
表征和 OLAP
- 相同：在多个抽象层次呈现数据摘要，交互式钻孔、旋转、切片和切块。
- 差异：自动按所需级别分配，存在多个相关维度时的维度相关性分析和排序，复杂的维度和度量。
相关性度量确定一组数据中属性的分类能力：信息增益（ID3）、回报率（C4.5）、基尼系数、 $χ^{2}$ 列联表统计信息、不确定系数。
ID3算法【重要】
- 基于已知类别标签的训练对象构建决策树对测试对象进行分类。
- 基于信息增益度量的等级属性。
- 最小高度：对对象进行分类的最少测试次数。
熵和信息增益：
挖掘类比较：比较两个或更多的类。
- 相关数据集划分为目标类和对比类。
- 将两个类推广到相同高级描述的元组。
- 为每个元组提供其描述和两个度量：支持——单个类内的分布，比较——类间分布。
- 突出显示具有强判别特征的元组。
相关分析：找到最能区分不同类别的属性（特征）。
数据收集，相关属性分析，同步泛化（由用户指定的维度阈值控制、主要目标和对比类关系/长方体）
五个数字总结分布：最小值、四分之一值、中位数、四分之三值、最大值。
箱型图：箱上下是 Q3 和 Q1，也就是说高度是 IQR，箱外两条线是最大最小值，中位数在箱中间以一条线标记。
分位数：升序排列数据，有百分之多少的数据低于或等于该值。
Quantile-Quantile 图：理论值和实际值，和 y=x 比较看是否吻合，还可以看两组数据是否来自同一分布。
洛伦斯曲线（Loess Curve）：考虑两个参数，一个是平滑参数，另一个是回归拟合多项式的次数。
面向属性归纳 vs 范例学习
- 基本假设差异：
  - 范例学习中的正负样本：正样本用于概括，负样本用于专门化。
  - 数据挖掘的正样本：基于泛化，向下钻取将泛化回溯到先前状态。
- 泛化方法差异：
  - 机器学习在元组基础上的推广。
  - 数据挖掘在属性基础上的推广。

05 关联规则挖掘

定义：在事务数据库、关系数据库和其他信息库中的项目或对象集之间寻找频繁的模式、关联、相关性或因果结构。
Apriori 定则：频繁项集的任何子集必须是频繁的。
最小支持度阈值：只有在数据集中出现次数超过这个阈值的项集才被认为是频繁的。
Apriori 算法【重要】：输入：数据集合D，支持度阈值α；输出：最大的频繁k项集。
- 1. 扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。
- 1. 挖掘频繁k项集：
  - 扫描数据计算候选频繁k项集的支持度。
  - 去除候选频繁k项集中支持度低于阈值的数据集，得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。
  - 基于频繁k项集，连接生成候选频繁k+1项集。
- 1. 令k=k+1，转入步骤2。
- 连接步骤： $L_{k - 1}$ 和自身连接得到 $C_{k}$ 。
- 剪枝步骤：任何（k-1)项集不是频繁的，那么也不可能是k项频繁集的子集。
- 提升效率：
  - 基于哈希的项集计数：对应哈希桶计数低于阈值的k项集不是频繁的。
  - 事务减少：不包含任何频繁k项集的事务在后续扫描中无用。
  - 分区：任何在DB中可能频繁出现的项集必须至少在DB的一个分区中频繁出现。
  - 采样：对给定数据子集挖掘，降低支持阈值和确定完备性的方法。
  - 动态项集计数：新的候选项集只有在仅当它们的所有子集被估计为频繁时，才被添加。
- DHP：Apriori 变体，减少待扫描事务量，并削减初始候选集生成中每个事务的项数，尤其是频繁的2项集。（低于支持阈值的hash桶内项集直接丢弃）。
- Apriori 算法瓶颈：候选集生成，巨大扫描成本。
- Frequent-Pattern tree（FP-tree）：高度压缩，避免高昂的数据库扫描。
  - 首先建立项头表，剔除低于支持阈值的项，然后对每项数据按频率降序排列。
  - 然后分别以每个节点为叶子节点的FP子树进行挖掘。
  - 这里D的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。
  - 没有候选生成，没有候选测试，使用紧凑的数据结构，消除重复的数据库扫描，基本操作是计数和FP树构建。
支持阈值递减：
- 逐层独立: 完全的宽度(广度)搜索, 没有频繁项集的背景知识用于剪枝。
- 层交叉单项过滤: 一个第i层的项被考察, 当且仅当它在第(i-1)层的父节点是频繁的。
- 层交叉k项集过滤: 一个第i层的k项集被考察, 当且仅当它在第(i-1)层的对应父节点k-项集是频繁的。
- 单项可控水平交叉过滤。
支持度和置信度都存在不足：
A和B事件独立，结果小于1则负向相关，否则则正向相关。

06 分类挖掘

监督学习：分类；无监督学习：聚类。
决策树：贪婪算法。
信息增益：假设所有属性都是可以分类的，选择最高信息增益的属性。
- ID3算法：
贝叶斯：记得拉普拉斯平滑处理，分子都加1，分母加n。
后向传播。
线性回归：

07 聚类分析

数据标准化：
距离计算：
分割方法：K-Means 聚类。
- 1. 随机选择k个对象作为当前分区的簇的质心。质心是聚类的中心（中点）。
- 1. 将每个对象分配给具有最近种子点的集群。
- 1. 计算每个聚类的新质心。
- 1. 返回步骤2，当没有新任务时停止。
层次聚类：使用距离矩阵作为聚类标准。该方法不需要簇数k作为输入，但需要一个终止条件。
密度聚类：DBSCAN 算法。