《数据仓库与数据挖掘教程》ch02数据仓库原理 章节整理_等深分箱法

数据仓库原理

多数据源问题

多数据源

数据仓库和数据挖掘的数据通常来自多种数据库或计算机应用系统或数据文件、web页面

多数据源在集成的问题

• 数据不一致：数据的不一致性主要指数据之间的矛盾性和不相容性。如职务升迁了，但工资数据却没有改变
• 属性差异：性别属性有的取“男”/“女”,长度为2；有的取“1”/“0”，长度为1
• 数据重复：数据源中存在两条或多条完全相同的记录，或者同一个数据冗余地存在于多个数据源中
• 数据不完整：某些属性的值可能是缺失的，甚至是错误的数据
• 噪声数据：噪声是指测量数据时遇到的随机或其它不确定性因素，它导致被测量的数据产生了偏差或错误，称这种含有偏差或错误的数据为噪声数据
• 高维数据：为较全面的描述实体，原始数据通常都使用了较多属性
• 模式不统一：将集成为单一数据集的多个数据源的模式不同
• 数据不平衡：数据集中某一类样本的数量明显少于其它类型样本的数量

数据预处理

• 数据预处理(data preprocessing)：在多数据源集成为统一数据集之前进行的数据清洗、数据变换、数据规约等数据处理过程
• 预处理的目的：消除多数据源集成存在的问题，为数据仓库或数据挖掘提供一个完整、干净、准确、且有针对性的数据集合

数据清洗

• 数据清洗(Data cleaning)
  发现并纠正数据源，即原始数据中存在的问题或错误的过程，包括检查数据一致性，处理无效值、填补缺失值，以及过滤掉那些不符合要求的数据等

  • 属性的处理：对多数据源含义相同的属性进行重命名和统一类型长度，选择设置主键和派生属性等处理
    • 重命名属性：对数据仓库或数据挖掘需要的属性重新赋给它们含义明确，便于理解记忆和使用的属性名称
    • 统一属性：确保多个数据源中对同一实体特征的描述是统一的，包括属性的长度、类型，还有属性的值域
    • 处理主键属性：为建立挖掘结果和原始数据之间的直接对应关系的话，需要保留主键属性
    • 派生新属性：由日期属性派生出年、季、月、周、日等多个时间层次的时间属性
    • 选择相关属性：如果属性X的值可以由另外一个或多个属性值计算出来，称属性X和这些属性是相关的

• 空值的处理
  对原始数据中没有登记或没有输入的属性值——空值，使用某种对其进行补充或删除等预处理

  • 人工填补：优点是能够得到比较真实的数据，但通常人力耗费很大，而且速度较慢
  • 忽略记录：即将有空值的记录删除
  • 忽略属性：删除具有空值的列，即不将其作为数据仓库或数据挖掘对象集的属性
  • 使用默认值：对离散空值用一个固定的常数unknown或者*来填补
  • 使用平均值：对于连续属性空值用所有非空值的平均值来填补
  • 使用预测值：用一定的预测方法，计算得到空值属性最有可能的取值

• 数据噪声处理

  • 数据噪声(Data Noise)
    一种难于解释的数据剧烈变动，它导致一组数据中某些数据与组内其它数据出现了极大的偏差
    • 分箱(binning)：把数据集中所有数据放入不同箱子(区间)的过程称为分箱
  • 分箱技术的步骤
    • 对数据集的数据进行排序
    • 确定箱子个数k、选定数据分箱的方法并对数据集中数据进行分箱
    • 选定处理箱子数据的方法，并对其重新赋值
  • 常用分箱方法
    • 等深分箱、等宽分箱、自定义区间和最小熵分箱法

等深分箱法
把数据集中的数据按照排列顺序分配到k个箱子中(k=1,2,…,k)

• 当k整除n时，令p=n/k，则每个箱子都有p个数据，即
  • 第1个箱子的数据为：a₁，a₂，…，a_p；
  • 第2个箱子的数据为：a_p+1，a_p+2，…，a_2p；
  • …
  • 第k个箱子的数据为：a_n-p+1，a_n-p+2，…，a_n；
• 当k不能整除n时，令p=n/k （向下取整），q=n-k*p，则可让前面q个箱子有
  p+1个数据，后面k-q个箱子有p个数据，即
  • 第1个箱子的数据为：a₁，a₂，…，a_p+1；
  • 第2个箱子的数据为：a_p+2，a_p+3，…，a_2p+2；
  • …
  • 第k个箱子的数据为：a_n-p+1，a_n-p+2，…，a_n；
• 也可让前面k-q个箱放p个数，后面q个箱放p+1个数据

例题：

---

等宽分箱法
把数据集最小值和最大值形成的区间分为k个左闭右开的子区间（最后一个除外）I₁，I₂，…，I_k。如果 a_i属于I_j 就把数据a_i放入第j个箱子
例题：

---

用户自定义区间
当用户明确希望观察某些区间范围内的数据分布时，可以根据实际需要自定义区间，方便地帮助用户达到预期目的

• 数据平滑：对每个箱子中数据进行单独重新赋值
• 三种常见方法：按平均值、按边界值和按中值平滑
  按平均值平滑。对同一个箱子中的数据求平均值，并用这个平均值替代该箱子中的所有数据，其余同理

• 不平衡数据处理
  • 过抽样(oversampling)
    • 在样本集中通过增加少数类的样本来提高少数类样本的数量
    • 最简单的办法是复制少数类样本
    • 这种方法的缺点是引入了额外的训练数据，会延长构建分类器所需要的时间，没有给少数类增加任何新的信息，而且可能会导致过度拟合
  • 欠抽样(undersampling)
    • 该方法通过减少多数类样本的数量来提高少数类样本在样本集中的比例
    • 最简单的方法是通过随机方法，去掉一些多数类样本来减小多数类的规模
    • 这种方法的缺点是会丢失多数类样本的一些重要信息，已有的信息利用得不够充分

数据变换

• 数据聚集
  • 对数据按照管理或挖掘需要进行汇总
  • 比如：如果希望分析客户的经济背景情况对购买能力的影响，只需要关心客户消费的金额，而不需要了解客户购买了什么商品以及商品的数量、价格等信息
• 数据概化
  • 用较高层次的数据代替较低维度层次的数据称为数据的概化(data generalization)，也翻译为数据概括
  • 比如用“时”或“日”的数据来替换“秒” 和“分”的数据
• 数据规范化
  将原始数据按照一定的比例缩放，使之落入一个特定的区间

方法有如下几种：

---

---

数据归约

数据归约(data reduction)(也称为数据约简)：用精简数据表示原始数据的方法，且归约后数据量通常比原始数据小很多，但具有接近甚至等价于原始数据表达的信息

• 维归约(dimensionality reduction)
  减少描述问题的随机变量个数或者数据集的属性个数，后者又称属性约简(attributes reduction)
• 数量归约(numerosity reduction)
  用较少的数据表示形式替换原始数据
• 数据压缩(data compression)
  使用变换方法得到原数据的归约或“压缩”表示，图像压缩技术就是一种典型的数据压缩方法

E-R模型

E-R模型中的基本概念

• 实体(Entity)：客观存在并可相互区别的事物
• 属性(Attribute)：描述实体的每一个特征。姓名、性别
• 关键字(Key)：能唯一地标识实体集中每个实体的属性集合称为关键字或者码
• 联系：实体之间的联系(Relation)，有3种类型
  • 一对一 (1:1)
  • 一对多(1:n)
  • 多对多(m:n)

E-R图的要素

• 实体（集、型)：用矩形表示，矩形框内写明实体名
• 属性：用椭圆形表示，并用无向边将其与相应的实体连接起来
• 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关的实体连接起来，同时在无向边的旁边标上联系的类型
  • 如果一个联系具有属性，则这些属性也要用无向边与该联系连接起来
  • 联系的类型： (1:1)，或(1:n)，或(m:m)
  • 举例：

数据仓库的概念模型

• 概念数据模型(Conceptual Data Model，简称概念模型)：对现实管理决策中各个主题及其特征的数据抽象表示
• 概念模型应具有特点：
  • 能够比较真实地模拟或抽象表示用户的决策主题
  • 表示方法简单直观且易于用户理解
  • 与计算机系统支持的具体数据模型无关
  • 易于向数据仓库的逻辑数据模型转换
• 学术研究的概念模型
  • 数据锥体(Data Cube)模型
  • 维事实模型DFM(Dimensional Fact Model)
  • StarER模型
  • 多维模式CMS (Conceptual Multidimensional Schema)
  • 扩展ER模型
  • DWER模型

但还没有学术界和工程应用领域普遍接受的DW概念模型

多维数据模型

定义1：称A (维度₁,维度₂,…,维度_n ；变量₁,…,变量_k) 是一个名称为A的n维数组，也称A为n维超立方体(Hypercube)或多维数据模型(多维模型)

---

例如：某市公安局拟建立警务数据仓库，需要从入住时间、旅客来源和宾馆辖区三个不同的角度，统计分析来该市城区登记入住宾馆的人次，其多维数据模型为：
Hotel(入住时间，旅客来源，宾馆辖区；入住人次)

多维数据模型通常用于描述决策分析的一个主题框架

• 变量
  • 决策分析的度量指标，一个描述数据实际意义的名称
  • 它描述数据“是什么”,即已经发生过的事实（Fact）
  • 变量的取值为连续型实数，如企业“销售收入”,“管理成本”,旅客入住宾馆的 “入住人次”,“人均天数”等
• 维度
  • 决策分析人员观察数据(度量指标、事实)的一个特定角度称为维度，也简称维
  • 例如，时间、地理就是两个不同的维度
• 维的层次
  • 决策分析人员在某个维度上观察数据（度量指标）时需要的细节程度称为维的层次，也称作维的级别
• 维成员
  • 维成员就是一个维度在某个维层次上的一个具体取值
• 多维数据集
  • 多维数组的每个维度都指定了确定的维成员、且每个变量对应于每个维成员都赋予了具体的数值，就称一个多维数据集
• 数据单元(单元格)
  • 多维数据集指定维成员后对应变量值的一个存储空间。因此，每个单元格描述了一个确定的事实
• 多维数据集的两种结构
  • 超立方体结构(Hypercube)：描述一个决策主题的三维或更多维数组，且每个维彼此垂直，数据空间的各个单元格都取定了相同层次的维成员
  • 多立方体(Multicube) 结构：用若干个较小的超立方体结构表示一个大的超立方体结构

维度与粒度

• 数据的粒度是指数据仓库的数据单元中所保存数据的综合程度。数据的综合程度越高，其粒度就越粗。反之，数据的综合程度越低，其粒度也就越细
• 多维数据集数据的粒度与维的层次是两个联系密切，而且内涵一致的概念，即维的层次刻画了数据的粒度，维的层次越低，数据的粒度就越小，反之，维的层次越高，数据的粒度就越大
• 数据粒度设计深刻地影响存放在数据仓库中数据占用存储空间的大小和所能回答的查询类型。数据粒度小，即维的层次低可以回答许多细节的查询需求，但占用过多的存储空间。

数据仓库的逻辑模型

• 逻辑数据模型(Logical Data Model)是用户从数据仓库管理系统中所看到的、具体的DWMS所支持的数据模型
• 商品化的数据仓库管理系统(DWMS)产品中，主要有两大类可供用户选择
  • 基于关系模型的数据仓库管理系统(Relational DWMS, RDWMS)，如SQL Server、Oracle、DB2等
  • 基于多维模型的数据仓库管理系统，称为多维数据库管理系统(Multi-Dimensional DataBase Management System，NMDDBMS)，也称纯多维数据库管理系统

多维模型

若用纯多维数据库管理系统作为DW的管理平台，则多维数据模型既是数据仓库的概念模型，又是数据仓库的逻辑模型，而多维数据集都存储在多维数据库中

• 多维数据库
  多维数据库(Multi-Dimesional DataBase，简称是长期存储在计算机内的、可共享的多维数据集合
  MDDB将所有数据都以n维数组的形式存储

• 多维数据库管理系统
  多维数据库管理系统是位于用户与操作系统之间的一层数据管理软件，负责对多维数据库进行统一管理和控制，并为用户和应用程序提供访问多维数据库的方法等

• 纯多维数据库管理系统Caché
  Caché是美国Intersystems公司推出的一款纯多维数据库管理系统，是一种面向对象的多维数据库管理系统，并支持SQL的访问方式
  在美国和欧洲的HIS系统(Hospital Information System)中，使用Caché多维数据库管理系统所占的比例是最大的，被医疗界公认为首选数据库
  哈尔滨医科大学第一临床医学院2007年实施了基于Caché的HIS系统
  特点：

  • 速度快
  • 使用简单
  • 接口容易
  • 对象型编辑
  • 真正C/S的3层结构
  • 灵活性，可不经修改便能在多种操作系统平台上运行
  • 支持WEB开发
  • 价格便宜

• 多维数据库存储
  多维数据集用超立方体结构(Hypercube)，或多立方体结构(Multicube)表示，因此，采用纯多维数据库管理系统(MDDBMS)来存储和管理多维数据集是一种理想的方法

• 多维数据库存储的优点
  多维数据库存储多维数据集，其数据显示直观、计算处理效率高，特别便于汇总

• 多维数据库存储的缺点

  • 增加维度操作麻烦：超立方体(3维)建立前必须确定各个维度及其层次关系。但建立后若要增加一个新的维度，就要重建立新的超立方体(4维)
  • 维度增多引起灾难：超立方体随着维度的增多，其数据量呈指数增长，有可能导致数据文件超过操作系统文件空间上限
  • 实时细节数据缺乏：超立方体存储的都是前期抽取的汇总级别数据，缺乏事实细节数据

星形模型

• 若用户选择RDWMS产品，多维数据集就必须按照关系模式组织数据，存放在基本表中
• 星形模型由一个事实表和多个维度表的连接表示多维数据模型，其中矩形表示事实表，凹圆角矩形表示维度表，并用直线表示其间的主键-外键联系
• 星形模型是多维数据模型在关系数据库中的组织和存储结构描述，即它是多维数据模型的关系模型表示方法。因此，星形模型是多维数据模型的一种逻辑模型

1. 事实表
   事实表是星型模型结构的核心，它至少应包含两个部分，一是多维数据模型的事实（变量），也就是度量指标值，另一个是由主键和若干外键
   事实表可以通过外键与维度表的主键连接，帮助用户理解度量指标值的实际意义，还可以按照维度表中维度层次进行各种统计和分析

2. 维度表
   维度表就是存放多维数据模型维度信息的基本表，它也包括两个部分，一个是主键，并作为外键存放在事实表中。另一个是维度名称和维层次等细节信息，它为事实表中的每个事实提供了详细的描述信息

---

例如：

• 星形模型的优势
  • 星形模型围绕一个确定的主题， 体现了数据仓库对数据结构和组织的要求
  • 星形模型表达直观，易于理解且设计相对容易
  • 星形模型维度表包含了用户经常查询和分析的属性，优化了对数据库的浏览，在维度表和事实表之间没有任何“迷宫 ”，使查询的过程变得简单而直接
  • 星形模型为OLAP提供了良好的工作条件，使OLAP能通过星形连接和星形索引，显著提高查询性能
  • 设计相对较为简单，因为不用考虑关系模式规范化化问题
• 星形模型的不足
  • 维度表通常是非规范化的，造成很大的数据冗余
  • 由于星形模型中各个维度表主键的组合构成事实表的主键，导致维度的变化非常复杂、费时
  • 维度属性的复杂形成的大维度问题，比如长文本字段占用存储空间，维度数据不易更新和维护，大维度表填充数据难度增大
  • 处理维的层次关系比较困难，特别当维的属性复杂时
  • 无法表达“多对多”的联系

雪花模型

雪花模型是星形模型按照关系数据库规范化理论对维度表进行分解的结果。其目的是消除数据冗余，同时增加更多对事实进行细节描述的信息，提高查询分析的灵活性。但其查询效率通常比星型模型表示的多维数据集要低一些

• 雪花模型优势
  • 减少了一定数据冗余量，节约了许多存储空间
  • 处理复杂维度和更新维度更加容易
  • 表示“多对多”的联系方便
  • 查询分析更具灵活性
• 雪花模型的不足
  • 事实表与维度表、详细类别表联系比较复杂，用户不易理解
  • 浏览查询多维数据内容相对困难
  • 额外的详细类别连接操作导致查询性能下降

数据仓库的物理模型

物理数据模型(Physical Data Model)，是描述数据在存储介质上组织结构的数据模型，它不但与具体的DBMS有关，而且还与操作系统和硬件有关，是机器世界物理层次的数据模型

位图索引模型

• 重要实用：在数据仓库的存储结构中，位图索引是一项非常重要且实用的索引模型
• 索引条件：对于那种只取少量几个离散值的属性列(属性取值种类在1%以下)来说，位图索引就是用一个二进制串，代替基本表中某一列的取值
• 索引效果：使我们在不触及数据记录的情况下，直接通过位图索索引而快速地获得查询结果
• 位图索引总结
  • 由于位图索引为二进制串，占用空间少且仅仅涉及位的逻辑运算，在内存中可实现快速运算，并提高查询效率
  • 位图索引用于类别统计也非常高效，比如，在户籍登记表中要统计已婚人员数量，只需要统计“已婚”位图索引中1的个数即可，而不需要读取登记表的每一条记录来逐一判断累加
  • 位图索引的适用条件：属性取值种类占总记录数的1%以下就比较适合创建位图索引

广义索引模型

• 广义索引:决策分析人员最关心而且经常需要查询的、关于数据仓库的一些统计数据
• 索引目的：提高数据的查询速度
• 创建方法：从操作型数据环境抽取数据并向数据仓库中装载的同时，可以根据用户的需要建立各种广义索引，而每一次向数据仓库追加数据时，就重新生成或更新这些广义索引的内容。这样就无需为建“广义索引”而重新去扫描数据仓库
• 创建条件：对于一些经常性的统计数据查询，如果预先建立了“广义索引”，就可直接通过直接查询广义索引来代替对事实表的查询，其查询速度显然要比直接查询事实表要快很多

连接索引模型

• 连接索引：事实表和维度表中满足连接条件的元组主键形成的索引项，并保留在数据仓库系统之中
• 索引使用：每当需要将事实表和维度表进行连接运算时，就直接利用连接索引项的指针进行连接运算
  • 设有关系R(Rid,A,B,C,D)和S(Sid,W,X,Y,Z)，有1000条记录，其中Rid和Sid分别是主键
  • 它们的全连接为RS(Rid,Sid,A,B,C,D,W,X,Y,Z) 有10个属性，100万条记录的大表
  • 它们的连接接索引由两个主键属性形成的索引项(Rid，Sid)构成，虽然也有100万条记录，但显然比全连接结果要小得多

RAID存储结构

• 数据仓库这种大数据的存储问题，可以选用RAID(Redundant Array of Inexpensive Disk)技术支持的廉价冗余磁盘阵列
• 虽然RAID磁盘阵列包含多块磁盘，甚至几百块磁盘，但是在操作系统下是作为一个独立的大型存储设备进行管理的
• RAID技术分为RAID0、1、2、3、4、5，6，7等几个不同的等级标准，RAID0又可以配合后面几种进行更多的功能组合，形成RAID10、30、50等工作方式。这些等级标准分别为用户提供了速度、价格、容量和安全性不相同的磁盘阵列的多种选择
  • RAID0，又称为磁盘条带化(Striping)工作方式
  • RAID1，又称为镜像(Mirroring)工作方式
  • RAID10(或者叫RAID0+1) 也可以简单的理解成两个分别由多个磁盘组成的RAID0阵列再进行镜像
  • 由于RAID2是一种比较特殊的专用RAID模式，与现有的磁盘驱动器不兼容，因实现成本比较高，目前还没有实际应用
  • RAID3 是在RAID 2 基础上发展而来的，采用并行传输及校验工作方式(Parallel transfer with parity)。主要的变化是用相对简单的异或逻辑运算(XOR， eXclusive OR)校验代替了相对复杂的汉明码校验，从而大幅降低了成本
  • RAID4采用带奇偶的条块化工作方式，它是RAID0和RAID3工作方式的结合，也称为具有共享校验硬盘的独立数据硬盘 (Independent Data disks with shared Parity disk)，I/O传输率比RAID3高，但磁盘空间利用率比RAID0低
  • RAID 5是目前应用最广泛的RAID技术。各块独立硬盘进行条带化分割，相同的条带区进行奇偶校验(异或运算)，校验数据平均分布在每块硬盘上。以n块硬盘构建的RAID 5阵列可以有n-1块硬盘的容量，存储空间利用率非常高
  • RAID6允许两块硬盘同时故障的情况发生
  • RAID7称为最优的异步高I/O速率和高数据传输率磁盘(Optimized Asynchrony for High I/O Rates as well as High Data Transfer Rates)，可以理解为一个独立的存储计算机，它自己的操作系统，有自己的处理器，有自己的总线，而不是通过简单的插卡就可以实现的