数据仓库与知识发现2024 期末复习

发表于 2024-12-30 更新于 2025-01-05 分类于数据仓库与知识发现阅读次数： Waline：本文字数： 9.1k 阅读时长 ≈ 17 分钟

复习建议

开卷考试，建议携带材料：
- 数据仓库白皮书（数据仓库与数据挖掘） + 黑皮书（数据挖掘：概念与技术），可能会考一些往年没有的题，这个时候翻书就很有用了；
- 往年卷题型解答（最好是你自己写的过程）；
- 对数表、分数表、信息熵计算表；
题型与往年题相同，数据会变，因此推荐面向往年题复习。
- 一道数据仓库 + 一道关联 + 一道数据预处理与分类 + 一道聚类；
- 复习时建议动笔计算，只有动手了才更好理解如何计算；
- 一定要使用题目要求的算法；

数据仓库及其实现技术

题型1 数据仓库的作用和地位

问：简述数据仓库在知识发现过程中的作用和地位。（2012、2013）

答：

作用：数据仓库是一个面向主题的（subject-oriented）、集成的（integrated）、时变的（time-variant）、非易失的（nonvolatile）数据集合，通常用于辅助决策支持。数据仓库通过数据清理、数据变化、继承和定期刷新等办法，从一个或多个数据源收集数据，存放在一个一致的模式下。数据仓库能够提供大量的、按照实际要求集成的不同主题的数据，通过OLAP引擎对其进行数据挖掘，发现知识。

地位：数据仓库是知识发现过程中不可或缺的一环，它是进行数据挖掘的必要基础。数据仓库能提供非冗余的有效数据，这些数据都是面向主题的，因此能够大大提高知识发现的能力和效率。没有数据仓库，知识发现就没有数据源。

题型2 B树

问：为何B树等在数据库中广泛使用的索引技术无法被直接引入数据仓库？（2012、2013）

答：

B树要求属性必须具有许多不同的值，比如iteamID、customID等；
B树要求查询应具有更简单的条件和更少的结果；
创建B树的空间和时间复杂度很大；

题型3 BITMAP索引

问：试采用BITMAP索引方式对图中的维度表进行索引。（2012、2013、2014、2015）

答：

题型4 Join Index索引

问：试采用 Join Index 对图中的事实表和维表进行索引。（2014、2015）

答：

将维表连线到事实表即可，如下：

题型5 数据立方体

问：数据立方体是什么？什么是数据立方体的多层和多维度？（2019）

答：

数据立方体是什么？

数据立方体（Data Cube）是一种用于表示和处理多维数据的数据结构。在数据库和数据仓库系统中，它是一个常用的概念，特别是在在线分析处理（OLAP）和多维数据分析中。数据立方体使得用户可以从多个维度（如时间、地区、产品类型等）分析数据，支持复杂的数据查询和汇总操作。
以下是数据立方体的几个关键特点：

多维视图：数据立方体提供多维的视图，使用户能够从不同的角度和维度分析数据。
聚合操作：它支持聚合操作，如求和、平均、最大值和最小值等，以便对数据进行汇总分析。
切片和切块操作：用户可以进行切片（Slice）和切块（Dice）操作，以便查看数据的特定部分。切片是指在某个维度上进行数据的筛选，而切块是指在多个维度上同时进行筛选。
数据钻取：数据立方体允许用户在不同层级上钻取数据，比如从年度数据钻取到季度或月度数据。
灵活性和可扩展性：数据立方体设计灵活，可以根据需要进行扩展，以包含更多维度或数据。

在实际应用中，数据立方体能够帮助企业和组织快速获取关键的业务洞察，支持决策制定过程。通过数据立方体，用户可以轻松地执行复杂的数据查询，无需进行复杂的数据库编程。

数据立方体是一种多维数据模型，主要有星形模式、雪花模式和事实星座模式。

星形模式它是最常见的模式，它包括一个大的中心表（事实表），包含了大批数据但是不冗余；一组小的附属表（维表），每维一个。如下所示，从item、time、branch、location四个维度去观察数据，中心表是Sales Fact Table，包含了四个维表的标识符（由系统产生）和三个度量。每一维使用一个表表示，表中的属性可能会形成一个层次或格。

雪花模式它是星模式的变种，将其中某些表规范化，把数据进一步的分解到附加的表中，形状类似雪花。

事实星座

允许多个事实表共享维表，可以看作是星形模式的汇集。如下所示，Sales和Shipping两个事实表共享了time、item、location三个维表。

在数据仓库中多用事实星座模式，因为它能对多个相关的主题建模；而在数据集市流行用星形或雪花模式。

什么是数据立方体的多层和多维度？

数据立方体的“多层”和“多维度”是两个关键的概念，它们在多维数据分析中起着重要的作用：
多维度（Multidimensionality）

定义：在数据立方体中，多维度是指数据可以沿着多个不同的维度进行组织和分析。每个维度代表数据的一个特定方面或分类。
例子：常见的维度包括时间（例如年、月、日）、地理位置（如国家、城市）、产品类别等。例如，一个零售业务的数据立方体可能包含时间、产品类别和地区三个维度。
作用：多维度使得用户能够从不同角度查看和分析数据，以便更全面地理解业务情况和趋势。

多层（Multilevel）

定义：在数据立方体中，多层指的是每个维度内部的层次结构。一个维度可以被分解成不同的层次，每个层次提供不同粒度的数据视图。
例子：以时间维度为例，时间可以被分解为年、季、月、日等层次。用户可以选择查看年度总结数据，也可以深入到月度或日度数据进行更详细的分析。
作用：多层结构允许用户在不同的粒度级别上进行数据分析，从而进行更深入的数据挖掘和洞察。

在实际应用中，数据立方体的多维度和多层特性使其成为一个强大的工具，用于支持复杂的数据分析和决策制定过程。用户可以通过在不同维度和层次上进行分析，获得更深入、更全面的业务洞察。

题型6 表合并、表冗余、表分割

问：数据仓库数据存储据设计中，表合并、表冗余、表分割三者的原理。（2019）

在数据仓库存储设计中，表合并、表冗余和表分割是三个关键的概念，它们各自基于不同的原理，旨在优化数据存储、查询性能和数据整合。下面我将详细解释每一个概念：
表合并（Table Merging）

原理：表合并是将多个相关的表合并为一个更大的表的过程。这通常发生在维度表与事实表之间，或者是当多个维度表具有高度相关性时。例如，在一个销售数据仓库中，可以将产品信息、供应商信息和价格信息合并为一个大表。
目的：主要目的是为了简化查询，通过减少需要进行连接操作的表的数量来提高查询效率。这对于需要频繁访问多个表的数据分析尤为重要。
优点：减少了查询时的表连接操作，简化了查询逻辑，提高了查询效率。
缺点：可能导致数据冗余和存储空间的增加。

表冗余（Table Redundancy）

原理：表冗余是指在一个或多个表中故意存储重复数据的做法。在数据仓库中，这通常意味着某些数据在多个地方被复制和存储。
目的：主要是为了优化查询性能，尤其是在分布式系统中，通过本地化数据来减少查询时的网络延迟。
优点：提高了数据检索的速度，减少了复杂的表连接和数据聚合操作。
缺点：增加了存储需求，可能导致数据一致性维护的复杂性增加。

表分割（Table Partitioning）

原理：表分割是将一个大表分割成多个更小的、管理起来更容易的部分。这可以是水平分割（根据行），也可以是垂直分割（根据列）。
目的：旨在提高大数据集的管理效率和查询性能。分割后，查询可以仅针对相关的数据分区进行，而不是整个表。
优点：提高了大型表的管理效率，优化了查询性能，降低了维护成本。
缺点：如果分割策略设计不当，可能会导致数据分布不均匀，影响查询性能。

综上所述，这三种策略在数据仓库设计中都扮演着重要角色。选择哪种策略取决于特定的数据特征、查询需求和系统架构。正确地应用这些策略可以显著提高数据仓库的性能和效率。

关联

题型1 Apriori算法求频繁集

问：针对图中的交易事务数据，采用Apriori算法求取频率项集，假设最小支持度为>=30%。（2012）

答：

支持度计算公式：support(X) = count(X∈T) / |D|

Apriori算法求解过程如下：

首先产生 1-候选集C1，然后在C1上去除支持度小于sup_min的项集，形成 1-频繁集L1：

然后将L1中的各项集组合连接，产生 2-候选集C2，并且再次在C2上筛除支持度小于sup_min的项集，形成 2-频繁集L2：

然后将L2中的各项集组合连接，注意：只有最后一个项目不同的两个项集才可以进行连接，例如{a,b}和{a,d}可以连接，但{a,b}和{b,c}不可以连接；并且还要判断产生的项集的子集是否都在L2中，即频繁集的子集必须是频繁集，例如{b,c}和{b,e}连接成{b,c,e}后，由于{c,e}不在L2中，因此要筛除。

连接后产生 3-候选集C3，并且再次在C3上筛除支持度小于sup_min的项集，形成 3-频繁集L3：

然后重复上述步骤，继续将L3的各项集组合连接，发现C4为空。

题型2 FP增长算法求频繁集

问：针对图中（见题型1）的交易事务数据，采用FP增长算法求取频率项集，假设最小支持度为>=30%。（2013、2014、2015）

答：

FP增长算法求解过程如下：

首先扫描交易记录集D，计算每个项目的计数值，选出支持度计数大于3的项，降序排列，放在列表L中：

然后将交易记录集D中的项目按照L中的顺序表示，如下：

开始构建FP树，先创建一个标记为null的根节点，然后依次扫描交易记录集D的每个交易，建立对应的路径（如果路径不存在），并将路径上各节点的计数+1（一个更简便的方法是，先将树画出来，然后检查每个节点所对应的路径在D中出现了几次）。

e5653bbbf8d43248cc17e66dcbcb448a

然后对列表L 从下往上遍历项目：

对于项目C：有{dbec:1}、{dbc:1}、{deac:1}、{dc:1}、{bac:1}五条路径，搜索这些路径，可以得到包含项目C的频繁集为：{c} 5、{dc} 4、{bc} 3；

对于项目A：有{dbea:2}、{dea:2}、{ba:1}三条路径，可以得到包含项目A的频繁集为：{a} 5 、{da} 4、{ea} 4、{ba} 3、{dea} 4；

对于项目E，有{dbe:4}、{de:2}两条路径，可以得到包含项目E的频繁集为：{e} 6、{de} 6、{be} 4、{bde} 4；

对于项目B，有{db:6}、{b:1}两条路径，可以得到包含项目B的频繁集为：{b} 7、{db} 6;

对于项目D，有{d:9}一条路径，可以得到包含项目D的频繁集为{d} 9。

题型3 构造关联规则

问：基于上述频繁项集（见题型1 2），构造关联规则，要求最小置信度>=50%。(2012、2013、2014、2015）

关联规则置信度计算公式：confidence(X=>Y) = support(X∪Y) / support(X)

答：

我们可以从频繁项集中产生关联规则，并且这些规则都会自动地满足最小支持度。

由频繁集{a,d,e}得到关联规则：

{a,d}=>{e}, confidence = support(a,d,e) / support(a,d) = 4/4 = 1

{a,e}=>{d}, confidence = 4/4 = 1

{d,e}=>{a}, confidence = 4/6 ≈ 0.67

{a}=>{d,e}, confidence = 4/5 = 0.8

{d}=>{a,e}, confidence = 4/9 ≈ 0.44 舍弃

{e}=>{a,d}, confidence = 4/6 ≈ 0.67

由频繁集{b,d,e}得到关联规则：

{b,d}=>{e}, confidence = 4/6 ≈ 0.67

{b,e}=>{d}, confidence = 4/4 = 1

{d,e}=>{b}, confidence = 4/6 ≈ 0.67

{b}=>{d,e}, confidence = 4/7 ≈ 0.57

{d}=>{b,e}, confidence = 4/9 ≈ 0.44 舍弃

{e}=>{b,d}, confidence = 4/6 ≈ 0.67

由频繁集{a,b}得到关联规则：

{a}=>{b}, confidence = 3/5 = 0.6

{b}=>{a}, confidence = 3/7 舍弃

由频繁集{a,d}得到关联规则：

{a}=>{d}, confidence = 4/5 = 0.8

{d}=>{a}, confidence = 4/9 舍弃

由频繁集{a,e}得到关联规则：

{a}=>{e}, confidence = 4/5 = 0.8

{e}=>{a}, confidence = 4/6 ≈ 0.67

由频繁集{b,c}得到关联规则：

{b}=>{c}, confidence = 3/7 舍弃

{c}=>{b}, confidence = 3/5 = 0.6

由频繁集{b,d}得到关联规则：

{b}=>{d}, confidence = 6/7

{d}=>{b}, confidence = 6/9

由频繁集{b,e}得到关联规则：

{b}=>{e}, confidence = 4/7

{e}=>{b}, confidence = 4/6

由频繁集{c,d}得到关联规则：

{c}=>{d}, confidence = 4/5

{d}=>{c}, confidence = 4/9 舍弃

由频繁集{d,e}得到关联规则：

{d}=>{e}, confidence = 6/9

{e}=>{d}, confidence = 6/6

最后得到的关联规则有：

{a,d}=>{e}、{a,e}=>{d}、{d,e}=>{a}、{a}=>{d,e}、{e}=>{b,d}、{b,d}=>{e}、{b,e}=>{d}、{d,e}=>{b}、{b}=>{d,e}、{e}=>{b,d}、{a}=>{b}、{a}=>{d}、{a}=>{e}、{e}=>{a}、{c}=>{b}、{b}=>{d}、{d}=>{b}、{b}=>{e}、{e}=>{b}、{c}=>{d}、{d}=>{c}、{d}=>{e}、{e}=>{d}。

数据预处理与分类

题型1 信息增益进行属性筛选

问：给定图中的目标集（DOG）和对比集（CAT），使用信息增益计算各个属性与当前概念描述任务之间的相关性。并采用T=0.1作为阈值，对属性进行筛选。（2014、2015）

首先推荐阅读文章什么是信息增益-CSDN博客，理解信息熵、信息增益等知识。

省流：

信息熵 = -ΣPi*log2(Pi)，表示信息的不确定性，特点：

当所有事件的概率相等时，熵最大，即最不确定。

当一个事件的概率为 1，其他事件的概率为 0 时，熵为 0，即完全确定。

信息增益（Information Gain）表示由于引入某一特征或条件而使得系统的不确定性减少的程度，它是信息熵的减少量。

答：

注：在计算时建议对照信息熵计算表辅助计算。

题型2 等宽分桶、等深分桶、3-4-5分桶

问：针对图中的训练数据集进行离散化处理。要求采用等宽分桶的方式将age和incoming属性离散到3个区间。（2012、2013、2014、2015等宽分桶，2017、2018等深分桶，2020 3-4-5分桶）

等宽分桶（Equal-width binning）：

在等宽分桶中，数据的范围被分割成宽度相等的区间。
每个区间的宽度由数据的最大值和最小值决定。
这种方法的优点是实现简单，但缺点是可能不会很好地处理数据中的异常值或非均匀分布。
假设我们有一组年龄数据：20,22,25,30,32,35,38,40,45,50。
- 我们想要将这些数据分成4个等宽的区间。
- 数据的范围是20到50，因此每个区间的宽度为 (50−20)/4=7.5(50−20)/4=7.5。
- 因此，分桶后的区间为：20−27.5, 27.5−35, 35−42.5, 42.5−50。

等深分桶（Equal-frequency binning）：

等深分桶将数据分割成包含大致相同数量数据点的区间。
这意味着每个桶的宽度可能会不同，但每个桶中的数据点数量相似。
这种方法对于处理有偏分布的数据较为有效，但可能会导致区间的界限不够明确。
使用同样的数据：20,22,25,30,32,35,38,40,45,50。
- 假设我们想要分成3个包含大致相同数量的数据点的区间。
- 每个区间将包含大约3或4个数据点。
- 因此，分桶后的区间可能是：20,22,25,30, 32,35,38, 40,45,50。

3-4-5原则分桶：

这是一种更加定性的分桶方法，通常用于商业和市场分析。
它基于这样一个观察：人类倾向于更好地记住和理解3到5个类别。
在应用这个原则时，数据被分割成3到5个区间，以使结果更容易被人理解和记忆。
这种方法更多地依赖于业务理解和目标，而不是严格的数学规则。
假设我们有一家公司的销售额数据，我们需要将这些数据分为容易理解的几个区间。
- 数据范围很广，从几千到几百万不等。
- 应用3-4-5原则，我们可能会选择分成4个区间：小型销售（数千至数万），中型销售（数万至十万），大型销售（十万至百万），超大型销售（超过百万）。