【读书笔记-数据挖掘概念与技术】数据立方体技术

基本概念：

基本单元：基本方体的单元
聚集单元：非基本方体的单元
冰山立方体：部分物化的立方体
最小支持度(最小支持度阀值)：部分物化的最小阀值(说白了就是限定了一个范围)

∵冰山立方体仍有大量不感兴趣的单元需要计算

∴引入——闭覆盖——一个单元没有后代或者它的后代的度量值与其不同

法2：只预计算涉及少数维的立方体，这些方体形成的数据立方体的立方体外壳

计算的一般策略：四种优化技术

1. 排序、散列和分组

2. 同时聚集和缓存中间结果

3. 当存在多个子女方体时，由最小的子女聚集

4. 先验剪枝法

—————————————————————————————————————————————————————————————————————————————

数据立方体的计算方法

多路数组聚集

计算以2-D平面为例：

维的大小：A——40；B——400;C——4000

1. 扫描次序为1~64

2. 扫描次序为1，17，33，49，5，21，37，53

特点：

1. 数组可以直接寻址

2. 将表转换成数组，用数据计算立方体，然后再把结果转换成表。（当然这并不意味着慢）

3. 可能仅对具有相对较少维的立方体才有效，因为需要计算的方体个数随维数指数增长

BUC(Bottom-Up Construction)：从顶点方体向下计算稀疏冰山立方体

主要思想

首先计算整个数据立方体的度量值，然后沿着每个维度进行划分，同时检查冰山条件，对不满足条件的分支进行剪枝操作，对满足的在下一个维度进行递归搜索
计算流程：

特点：

1. 采用了分治策略，优点在于能够分担划分开销，减少不必要的计算消耗；

2. 性能容易受到韦德次序以及不平衡数据的影响，应当以维基数的递减顺序进行划分(优化：排序、散列、分组)；

3. 不能利用父子关系共享聚集计算，不像MultiWay；

eg2：

Star-Cubing:使用动态星树结构计算冰山立方体

注：维的基数就是指这个属性的不同取值的个数

最小支持度min_sup(阀值)：相同的取值至少出现多少次

概念

星节点：单个维在属性值p上的聚集不满足冰山条件(可用于剪枝)

主要思想

集成自顶向下和自底向上，结合多路数据聚集的同时聚集和BUC中的Apriori剪枝策略
利用星型树数据结构进行存储，核心是引入共享维。如果共享维的聚集值不满足冰山条件，则共享维向下的所有单元都不满足冰山条件

为快速高维OLAP预计算壳片段

一个问题：

为什么会对数据立方体预计算感兴趣？

因为数据立方体有利于多维数据空间的快速OLAP

尽管冰山立方体可以让我们在更短的时间内得到结果，但是，它并不是最终的解。

so，一个可能得解就是计算一个很薄的立方体外壳

又因为立方体外壳有两个缺点：

不支持高维OLAP
不支持下钻

so，我们只计算它的一部分或片段

外壳片段方法涉及两个算法：一个计算外壳片段立方体；另一个用立方体片段处理查询。外壳片段方法能够处理维度非常高的数据库，并且可以快速联机计算小的局部立方体。它利用信息检索和基于Web的信息系统中很流行的倒排索引结构。

———————————————————————————————————————————————————————————————————————

使用数据立方体技术处理高级查询(http://blog.csdn.net/mamianskyma/article/details/15494471)

基本数据立方体已经进一步扩充到各种复杂的数据类型和新的应用。如，用于地理数据仓库设计与实现的空间数据立方体，用于多媒体数据多维分析的多媒体立方体；RFID数据立方体处理射频（RFID）的压缩和多维分析，文本立方体和论题立方体是分别为多维文本数据库（包括结构属性和叙事文本属性）中向量空间模型和生成语言模型的应用开发的。

抽样立方体：样本数据上基于OLAP的挖掘

- - 在收集数据时，常常只收集我们想要收集数据的一个子集，结果数据称为样本数据。
  - 如果试图把传统的OLAP工具用于样本数据，则将遇到两个挑战：第一，在多维意义下，样本数据往往过于稀疏。当用户在数据上下钻时，很容易钻到只有很少样本或没有样本的点。基于小样本推断对于总体回答可能产生误导：样本中的单个离群点或微小偏倚都可能显著地扭曲回答。第二，使用样本数据，统计学方法将用来提供可靠性度量（如置信度），指出关于总体，查询回答的质量。而传统的OLAP没有配备这样的工具。
  - 抽样立方体是一种存储样本数据和它们多维聚集的数据立方体结构。它支持样本数据上的OLAP。它计算置信区间，作为多维查询的质量度量。置信区间用于指示估计的可靠性，如样本数据中观众平均年龄为35岁，但35岁是也是总体数据的平均年龄的把握有多大？因此需要某种方法限定我们的估计，指导出误差的一般幅度。置信区间是一个以给定的高概率涵盖真正总体值估计的值域。置信区间总是被一个置信水平限制。例：“在95%时，实际均值变化不会超过+/-两个标准差”，置信水平是95%。置信区间的计算方法见《数据挖掘概念与技术》142页。
  - 如果置信区间很大，则可靠性就成为一个问题。影响置信区间大小的两个因素：样本数据的方差和样本大小。首先，很大的单元方差表明所选单元很差，更好的解可能是在查询单元下钻到更细节的单元时；其次，小样本可能导致大的置信区间。解决小样本问题的最好方法是获取更多数据，立方体中通常有充足的数据，这些数据不能精确地匹配查询单元，然而，可以考虑“邻近”单元中的数据，有两种方法获取这种数据，以增强查询回答的可靠性：1）方体内查询扩展考虑同一方体内的邻近单元；2）方体间查询扩展考虑查询单元的更一般版本（来自父母方体）。
    - 方体内查询扩展：通过包括与查询单元处于同一方体的邻近单元来扩大样本，新样本旨在提高回答的置信度，而不改变查询的语义。1）应该扩展哪些维：与度量值（待预测的值）不相关或弱相关的值。为了精确地度量维与立方体值的相关性，计算维值与它们聚集立方体之间的相关性，通常对数值数据使用皮尔逊相关系数，对标称数据使用X^2相关检验，尽管也可以使用其他度量如协方差。2）选择用于扩展的维后，扩展应该使用这些维中的哪些值：选择语义类似的值，使得改变最终结果的风险最小。
    - 方体间查询扩展：通过考察更一般的单元进行扩展。
- 排序立方体：top-k查询的有效计算
  - 数据立方体不仅有助于多维查询的联机分析处理，而且有助于搜索和数据挖掘。top-k查询（或排序查询）根据用户指定的优选条件，只返回最好的K个结果作为查询的回答，而不是返回大量不加区分的结果。结果按排定的序返回，使得最好结果在顶部。通常，用户指定的优选条件由两部分组成，一个选择条件和一个排序函数。top-k查询在许多应用中很常见，如搜索web数据库、使用近似匹配的k-最近邻搜索、多媒体数据库的相似性查询。
  - OLAP需要脱机预计算，以便多维分析可以联机进行，但是临时设定的排序函数又阻完全物化。一种自然的折中是采用半脱机物化和半联机计算模式。
  - 排序立方体的一般原理是物化选择属性集上的立方体。使用排序维上基于区间的划分使得排序立方体可以有效而灵活地支持用户的临时查询。
数据立方体空间的多维数据分析
- 预测立方体：立方体空间的预测挖掘
  - 多维数据挖掘，发现变化的维组合和变化的粒度的知识，这种挖掘又称为探索式多维数据挖掘或联机分析挖掘。
  - 预测立方体是一种立方体结构，它存储多维数据空间中的预测模型，并以OLAP方式支持预测。预测立方体是多维数据挖掘的一个范例。在数据立方体中，每个单元值都是在该单元中数据子集上计算的聚集值，而预测立方体每个单元值都是通过对建立在该单元数据子集上的预测模型求值计算的，因此代表对该数据子集行为的预测。
- 多特征立方体：多粒度上的复杂聚集
  - 传统的数据立方体是在通常使用的维上，使用简单的度量构建。多特征立方体计算更复杂的查询，其回答依赖于变化粒度层上多个聚集的分组。
  - 多特征立方体使得用户可以灵活地定义复杂的、面向特定任务的立方体，在该立方体上可以进行多维聚集和基于OLAP的挖掘。
  - 多特征立方体的计算依赖于该立方体所使用的聚集函数的类型。聚集函数可以分为分布的、代数的和整体的。
- 基于异常的、发现驱动的立方体空间探查
  - 一个数据立方体可能具有大量方体，且每个方体可能包含大量（聚集）单元。对用户页言，即使只是浏览立方体也成为一种负担。需开发一些工具，帮助用户智能地探查数据立方体巨大的聚集空间。
  - 异常指示符指示数据异常的预计算的度量，在所有的聚集层用来指导用户的数据分析过程。异常是一个数据立方体单元值，基于某种统计模型，它显著地不同于预期值。该模型在单元所属的所有维上考虑度量值的变化和模式。该模型考虑隐藏在数据立方体的所有分组聚集中的异常。