数据挖掘概念与技术第三章数据仓库和OLAP技术课件

11/20/2019 数据挖掘：概念与技术 1 数据挖掘：概念与技术数据挖掘：概念与技术 第三章：数据仓库与 OLAP技术概述 11/20/2019 数据挖掘：概念与技术 1 数据挖掘：概11/20/2019 数据挖掘：概念与技术 2 第三章：数据仓库与OLAP技术概述?什么是数据仓库?多维数据集模型?数据仓库体系结构?数据仓库实现?从数据仓库到数据挖掘 11/20/2019 数据挖掘：概念与技术 2 第三章：数据11/20/2019 数据挖掘：概念与技术 3 什么是数据仓库?多种定义方式，但不严格?从组织机构的操作数据库分离并独立维护的决策支持数据库?支持信息处理，为统一的历史数据分析提供坚实的平台?数据仓库是一个面向主题的、集成的、时变的和非易失的数据集合，支持管理部门的决策过程。W.H.Inmon?建立数据仓库：?构建和使用数据仓库的过程 11/20/2019 数据挖掘：概念与技术 3 什么是数据仓11/20/2019 数据挖掘：概念与技术 4 数据仓库面向主题的?围绕主题组织数据,如顾客、产品、销售等。?关注决策者的数据建模与分析，而不是组织机构的日常操作和事务处理。?提供特定主题的简明视图，排除对于决策支持过程无用的数据。11/20/2019 数据挖掘：概念与技术 4 数据仓库面11/20/2019 数据挖掘：概念与技术 5 数据仓库集成的?由多个异构数据源集成构建?关系数据库,平面文件,联机事务记录?应用数据清理和数据集成技术?确保命名约定，编码结构，属性度量等一致性?将数据迁入数据仓库时需要进行数据转换 11/20/2019 数据挖掘：概念与技术 5 数据仓库11/20/2019 数据挖掘：概念与技术 6 数据仓库时变的?数据仓库中数据的时间范围比业务操作系统中长得多?业务操作数据库：当前数据?数据仓库：提供历史数据信息 (如过去5-10年)?数据仓库中的结构主键：?都隐式或显示包含时间元素?但业务操作数据主键不一定包含时间元素 11/20/2019 数据挖掘：概念与技术 6 数据仓库11/20/2019 数据挖掘：概念与技术 7 数据仓库非易失的?物理存储：与操作环境分离，虽然来自其中。?数据仓库环境中不发生数据更新操作?不需要事务处理，恢复和并发控制机制?只需要两种数据操作：?i数据初始化装入?数据访问 11/20/2019 数据挖掘：概念与技术 7 数据仓库11/20/2019 数据挖掘：概念与技术 8 数据仓库与异构数据库?传统异构数据库集成：查询驱动方法?在异构数据库上建立包装程序和集成程序（中介程序）?提交查询时，使用元数据字典将查询转换为异构站点上的查询。然后将查询映射和发送到局部查询处理器，由不同站点返回的结果集成为全局查询结果集。?复杂的信息过滤和集成处理，与局部数据源的处理竞争资源?数据仓库:更新驱动方法，高性能?将异构源的信息预先集成并存储在数据仓库中，供直接查询和分析?不包含最近的信息?支持复杂多维查询 11/20/2019 数据挖掘：概念与技术 8 数据仓库与异11/20/2019 数据挖掘：概念与技术 9 数据仓库与业务操作数据库?OLTP(on-line transaction processing)，联机事务处理?传统关系数据库管理系统的主要任务?日常操作：购物，库存，制造，银行，工资，注册，记账等。?OLAP(on-line analytical processing)，联机分析处理?数据仓库系统的主要任务?数据分析和决策制定?区别(OLTP vs.OLAP):?用户和系统的面向性：顾客事务和查询（办事员，打工仔）与市场数据分析（知识工人，老板）?数据内容：当前的，细节的 vs.历史的,汇总聚集的?数据库设计：E-R+业务应用 vs.星形、雪花型+主题?视图：当前的,局部的 vs.进化的,集成的?访问模式:更新 vs.只读 但查询复杂 11/20/2019 数据挖掘：概念与技术 9 数据仓库与业11/20/2019 数据挖掘：概念与技术 10 OLTP vs.OLAP 11/20/2019 数据挖掘：概念与技术 10 OLTP 11/20/2019 数据挖掘：概念与技术 11 为什么需要分离数据仓库?提高两个系统的系能?DBMS tuned for OLTP:access methods,indexing,concurrency control,recovery?Warehousetuned for OLAP:complex OLAP queries,multidimensional view,consolidation?不同的功能和不同的数据:?数据不全:Decision support requires historical data which operational DBs do not typically maintain?数据聚合:DS requires consolidation(aggregation,summarization)of data from heterogeneous sources?数据质量:different sources typically use inconsistent data representations,codes and formats which have to be reconciled?Note:越来越多的系统直接在DBMS上进行 11/20/2019 数据挖掘：概念与技术 11 为什么需要11/20/2019 数据挖掘：概念与技术 12 Chapter 3:Data Warehousing and OLAP Technology:An Overview?What is a data warehouse?A multi-dimensional data model?Data warehouse architecture?Data warehouse implementation?From data warehousing to data mining 11/20/2019 数据挖掘：概念与技术 12 Chapt11/20/2019 数据挖掘：概念与技术 13 由表和电子数据表到数据立方体?数据仓库和OLAP工具基于多维数据模型，以数据立方体的方式观察数据?数据立方体,如销售,从多维角度对数据建模和观察?维度表,如 item(item_name,brand,type),or time(day,week,month,quarter,year)?事实表(如 dollars_sold)包含度量值和关联维度表的码?名词：?数据立方体成为方体(cuboid)?存放最底层汇总的方体（n-D）成为基本方体(basic cuboid)?存放最高层汇总的方体（0-D）称为顶点方体(apex cuboid)，用all标记?方体的格成为数据立方体(data cube)11/20/2019 数据挖掘：概念与技术 13 由表和电子11/20/2019 数据挖掘：概念与技术 14 3-D数据立方体 11/20/2019 数据挖掘：概念与技术 14 3-D数据11/20/2019 数据挖掘：概念与技术 15 4-D数据立方体 11/20/2019 数据挖掘：概念与技术 15 4-D数据11/20/2019 数据挖掘：概念与技术 16 数据立方体:方体的格 time,item time,item,location time,item,location,supplier all time item location supplier time,location time,supplier item,location item,supplier location,supplier time,item,supplier time,location,supplier item,location,supplier 0-D(apex)cuboid 1-D cuboids 2-D cuboids 3-D cuboids 4-D(base)cuboid 11/20/2019 数据挖掘：概念与技术 16 数据立方体11/20/2019 数据挖掘：概念与技术 17 数据仓库的概念建模?数据仓库建模：dimensions&measures?星形模型:A fact table in the middle connected to a set of dimension tables?雪花模型:A refinement of star schema where some dimensional hierarchy is normalized into a set of smaller dimension tables,forming a shape similar to snowflake?事实星座型:Multiple fact tables share dimension tables,viewed as a collection of stars,therefore called galaxy schema or fact constellation 11/20/2019 数据挖掘：概念与技术 17 数据仓库的11/20/2019 数据挖掘：概念与技术 18 星形模型例子 time_key day day_of_the_week month quarter year time location_key street city state_or_province country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch 11/20/2019 数据挖掘：概念与技术 18 星形模型例11/20/2019 数据挖掘：概念与技术 19 雪花模型例子 time_key day day_of_the_week month quarter year time location_key street city_key location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_key item branch_key branch_name branch_type branch supplier_key supplier_type supplier city_key city state_or_province country city 11/20/2019 数据挖掘：概念与技术 19 雪花模型例11/20/2019 数据挖掘：概念与技术 20 事实星座型例子 time_key day day_of_the_week month quarter year time location_key street city province_or_state country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch Shipping Fact Table time_key item_key shipper_key from_location to_location dollars_cost units_shipped shipper_key shipper_name location_key shipper_type shipper 11/20/2019 数据挖掘：概念与技术 20 事实星座型11/20/2019 数据挖掘：概念与技术 21 DMQL 中的立方体定义语法?立方体定义(Fact Table)define cube :?维度定义(Dimension Table)define dimension as()?Special Case(Shared Dimension Tables)?First time as“cube definition”?define dimension as in cube 11/20/2019 数据挖掘：概念与技术 21 DMQL 11/20/2019 数据挖掘：概念与技术 22 DMQL定义星形模型 define cube sales_star time,item,branch,location:dollars_sold=sum(sales_in_dollars),avg_sales=avg(sales_in_dollars),units_sold=count(*)define dimension time as(time_key,day,day_of_week,month,quarter,year)define dimension item as(item_key,item_name,brand,type,supplier_type)define dimension branch as(branch_key,branch_name,branch_type)define dimension location as(location_key,street,city,province_or_state,country)11/20/2019 数据挖掘：概念与技术 22 DMQL定11/20/2019 数据挖掘：概念与技术 23 DMQL定义雪花模型 define cube sales_snowflake time,item,branch,location:dollars_sold=sum(sales_in_dollars),avg_sales=avg(sales_in_dollars),units_sold=count(*)define dimension time as(time_key,day,day_of_week,month,quarter,year)define dimension item as(item_key,item_name,brand,type,supplier(supplier_key,supplier_type)define dimension branch as(branch_key,branch_name,branch_type)define dimension location as(location_key,street,city(city_key,province_or_state,country)11/20/2019 数据挖掘：概念与技术 23 DMQL定11/20/2019 数据挖掘：概念与技术 24 DMQL定义事实星座型 define cube sales time,item,branch,location:dollars_sold=sum(sales_in_dollars),avg_sales=avg(sales_in_dollars),units_sold=count(*)define dimension time as(time_key,day,day_of_week,month,quarter,year)define dimension item as(item_key,item_name,brand,type,supplier_type)define dimension branch as(branch_key,branch_name,branch_type)define dimension location as(location_key,street,city,province_or_state,country)define cube shipping time,item,shipper,from_location,to_location:dollar_cost=sum(cost_in_dollars),unit_shipped=count(*)define dimension time as time in cube sales define dimension item as item in cube sales define dimension shipper as(shipper_key,shipper_name,location as location in cube sales,shipper_type)define dimension from_location as location in cube sales define dimension to_location as location in cube sales 11/20/2019 数据挖掘：概念与技术 24 DMQL定11/20/2019 数据挖掘：概念与技术 25 数据立方体的度量:三类?分布式度量:将函数用于n个聚合值得到的结果与将函数用于整个数据集（不划分）得到的结果一样?E.g.,count(),sum(),min(),max()?代数度量:能够用具有M个参数的代数函数计算，而每个参数都可以用一个分布式聚合函数求得?E.g.,avg(),min_N(),standard_deviation()?整体度量:描述它的子聚集所需的存储没有常数界。?E.g.,median(),mode(),rank()11/20/2019 数据挖掘：概念与技术 25 数据立方体11/20/2019 数据挖掘：概念与技术 26 概念分层:维度(location)all Europe North_America Mexico Canada Spain Germany Vancouver M.Wind L.Chan.all region office country Toronto Frankfurt city 11/20/2019 数据挖掘：概念与技术 26 概念分层:11/20/2019 数据挖掘：概念与技术 27 概念分层：数值型数据（price）11/20/2019 数据挖掘：概念与技术 27 概念分层：11/20/2019 数据挖掘：概念与技术 28 数据仓库和分层视图 Specification of hierarchies?Schema hierarchy day month quarter;week year?Set_grouping hierarchy 1.10=minsup?动机?仅一小部分“浮于水面”的立方体单元存储在稀疏立方体中?仅计算感兴趣的单元数据超出某一阈值?避免立方体的爆炸性增长 11/20/2019 数据挖掘：概念与技术 53 冰山立方体11/20/2019 数据挖掘：概念与技术 54 索引OLAP数据：位图索引?某一具体列上的索引；?列中的每一个值都有一个位向量：位操作速度快?如果给定属性上包含n个值，则位图索引中每项需要n个位。?位向量的长度：基本表的记录数?如果基表给定行上该属性值为 v，则位图索引对应行的该值位置1。?不适合集数很大的域，导致位向量很长 11/20/2019 数据挖掘：概念与技术 54 索引OLA11/20/2019 数据挖掘：概念与技术 55 位图索引例子 11/20/2019 数据挖掘：概念与技术 55 位图索引例11/20/2019 数据挖掘：概念与技术 56 索引OLAP数据:连接索引?连接索引：JI(R-id,S-id)where R(R-id,)?S(S-id,)?传统的索引将给定列上的值映射到具有该值的行的列表上?在JI文件中物化关系连接，加快连接速度?在数据仓库中，连接索引维护维的属性值与事实表的对应行的联系?连接索引可以跨越多维，形成符合连接索引 11/20/2019 数据挖掘：概念与技术 56 索引OLA11/20/2019 数据挖掘：概念与技术 57 连接索引例子 11/20/2019 数据挖掘：概念与技术 57 连接索引例11/20/2019 数据挖掘：概念与技术 58 OLAP 查询的有效处理?确定哪些操作应该在可利用的方体上执行?将 drill,roll等操作转化为SQL或OLAP操作?e.g.,dice=selection+projection?确定相关操作 应当使用哪些物化的方体?假设对 brand,province_or_state 处理查询，选择常量“year=2004”,有4个物化方体可用：1)year,item_name,city 2)year,brand,country 3)year,brand,province_or_state 4)item_name,province_or_state where year=2004 应该选择哪一个来处理查询?基于代价的估计。?采用稀疏矩阵和数据压缩技术 11/20/2019 数据挖掘：概念与技术 58 OLAP 11/20/2019 数据挖掘：概念与技术 59 Chapter 3:Data Warehousing and OLAP Technology:An Overview?What is a data warehouse?A multi-dimensional data model?Data warehouse architecture?Data warehouse implementation?From data warehousing to data mining 11/20/2019 数据挖掘：概念与技术 59 Chapt11/20/2019 数据挖掘：概念与技术 60 数据仓库的使用?三种数据仓库应用?信息处理?支持查询、基本的统计分析、使用交叉表、表、图表进行报告?构造低代价的基于Web的访问工具。?分析处理?多维数据分析?支持OLAP操作：slice-dice,drilling,pivoting?数据挖掘?从隐藏的模式中发现知识?支持关联分析，构造分析模型，进行分类和预测，使用可视化工具提供挖掘结果 11/20/2019 数据挖掘：概念与技术 60 数据仓库的11/20/2019 数据挖掘：概念与技术 61 数据仓库的渐进使用?商务管理人员使用数据仓库和数据集市进行数据分析和战略决策?数据仓库使用时间越长，进化的越好?开始，用于产生报告和回答预先定义的查询?渐渐地，用于分析汇总和详细的数据结果以报表和图表提供?稍后，用于战略目的，进行多维分析和复杂的切片和切块操作。?最后，用于知识发现，并使用数据挖掘工具进行战略决策。?数据仓库工具：访问与检索工具，数据库报表工具，数据分析工具和数据挖掘工具 11/20/2019 数据挖掘：概念与技术 61 数据仓库的11/20/2019 数据挖掘：概念与技术 62 从联机分析处理(OLAP)到联机分析挖掘(OLAM)?为什么需要联机分析挖掘？?数据仓库中数据的高质量?DW中包含集成，一致，干净的数据?环绕数据仓库的信息处理基础设施?ODBC,OLEDB,Web访问,服务机制,reporting and OLAP tools?基于OLAP的探测试数据分析?Mining with drilling,dicing,pivoting,etc.?数据挖掘功能的联机选择?Integration and swapping of multiple mining functions,algorithms,and tasks 11/20/2019 数据挖掘：概念与技术 62 从联机分析11/20/2019 数据挖掘：概念与技术 63 联机分析挖掘的体系结构 数据仓库 元数据 MDDB OLAM 引擎 OLAP 引擎 图形用户界面 API 立方体 API 数据库 API 数据清理 数据集成 第三层 OLAP/OLAM 第2层 多维数据库 第1层 数据存储 第4层 用户界面层 过滤&集成 过滤 数据库 挖掘查询 挖掘结果 11/20/2019 数据挖掘：概念与技术 63 联机分析挖11/20/2019 数据挖掘：概念与技术 64 Chapter 3:Data Warehousing and OLAP Technology:An Overview?What is a data warehouse?A multi-dimensional data model?Data warehouse architecture?Data warehouse implementation?From data warehousing to data mining?Summary 11/20/2019 数据挖掘：概念与技术 64 Chapt11/20/2019 数据挖掘：概念与技术 65 总结:数据仓库和OLAP技术?为什么需要数据仓库?数据仓库的多维数据模型?Star schema,snowflake schema,fact constellations?A data cube consists of dimensions&measures?OLAP 操作:drilling,rolling,slicing,dicing and pivoting?数据仓库结构体系?OLAP 服务器:ROLAP,MOLAP,HOLAP?数据立方体的有效计算?Partial vs.full vs.no materialization?Indexing OALP data:Bitmap index and join index?OLAP query processing?从 OLAP 到 OLAM(联机分析挖掘)11/20/2019 数据挖掘：概念与技术 65 总结:数11/20/2019 数据挖掘：概念与技术 66 References(I)?S.Agarwal,R.Agrawal,P.M.Deshpande,A.Gupta,J.F.Naughton,R.Ramakrishnan,and S.Sarawagi.On the computation of multidimensional aggregates.VLDB96?D.Agrawal,A.E.Abbadi,A.Singh,and T.Yurek.Efficient view maintenance in data warehouses.SIGMOD97?R.Agrawal,A.Gupta,and S.Sarawagi.Modeling multidimensional databases.ICDE97?S.Chaudhuri and U.Dayal.An overview of data warehousing and OLAP technology.ACM SIGMOD Record,26:65-74,1997?E.F.Codd,S.B.Codd,and C.T.Salley.Beyond decision support.Computer World,27,July 1993.?J.Gray,et al.Data cube:A relational aggregation operator generalizing group-by,cross-tab and sub-totals.Data Mining and Knowledge Discovery,1:29-54,1997.?A.Gupta and I.S.Mumick.Materialized Views:Techniques,Implementations,and Applications.MIT Press,1999.?J.Han.Towards on-line analytical mining in large databases.ACM SIGMOD Record,27:97-107,1998.?V.Harinarayan,A.Rajaraman,and J.D.Ullman.Implementing data cubes efficiently.SIGMOD96 11/20/2019 数据挖掘：概念与技术 66 Refer11/20/2019 数据挖掘：概念与技术 67 References(II)?C.Imhoff,N.Galemmo,and J.G.Geiger.Mastering Data Warehouse Design:Relational and Dimensional Techniques.John Wiley,2003?W.H.Inmon.Building the Data Warehouse.John Wiley,1996?R.Kimball and M.Ross.The Data Warehouse Toolkit:The Complete Guide to Dimensional Modeling.2ed.John Wiley,2002?P.ONeil and D.Quass.Improved query performance with variant indexes.SIGMOD97?Microsoft.OLEDB for OLAP programmers reference version 1.0.In http:/ and statistical databases:Similarities and differences.PODS00.?S.Sarawagi and M.Stonebraker.Efficient organization of large multidimensional arrays.ICDE94?OLAP council.MDAPI specification version 2.0.In http:/www.olapcouncil.org/research/apily.htm,1998?E.Thomsen.OLAP Solutions:Building Multidimensional Information Systems.John Wiley,1997?P.Valduriez.Join indices.ACM Trans.Database Systems,12:218-246,1987.?J.Widom.Research problems in data warehousing.CIKM95.11/20/2019 数据挖掘：概念与技术 67 Refer