数据仓库和数据挖掘的OLAP技术概述35733.pptx

《数据仓库和数据挖掘的OLAP技术概述35733.pptx》由会员分享，可在线阅读，更多相关《数据仓库和数据挖掘的OLAP技术概述35733.pptx（76页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据仓库和数据挖掘的OLAP技术数据仓库和数据挖掘的OLAP技术什么是数据仓库？多维数据模型数据仓库的体系结构数据仓库实现数据立方体技术的进一步发展从数据仓库到数据挖掘什么是数据仓库?数据仓库的定义很多，但却很难有一种严格的定义它是一个提供决策支持功能的数据库，它与公司的操作数据库分开维护。为统一的历史数据分析提供坚实的平台，对信息处理提供支持“数据仓库是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策过程.”W.H.Inmon（数据仓库构造方面的领头设计师）建立数据仓库(data warehousing):构造和使用数据仓库的过程。数据仓库关键特征一面向主题围

2、绕一些主题，如顾客、供应商、产品等关注决策者的数据建模与分析，而不是集中于组织机构的日常操作和事务处理。排除对于决策无用的数据，提供特定主题的简明视图。数据仓库关键特征二数据集成一个数据仓库是通过集成多个异种数据源来构造的。关系数据库，一般文件，联机事务处理记录使用数据清理和数据集成技术。确保命名约定、编码结构、属性度量等的一致性。当数据被移到数据仓库时，它们要经过转化。数据仓库关键特征三随时间而变化数据仓库的时间范围比操作数据库系统要长的多。操作数据库系统:主要保存当前数据。数据仓库:从历史的角度提供信息（比如过去 5-10 年）数据仓库中的每一个关键结构都隐式或显式地包含时间元素，而操作数

3、据库中的关键结构可能就不包括时间元素。数据仓库关键特征四数据不易丢失尽管数据仓库中的数据来自于操作数据库，但他们却是在物理上分离保存的。操作数据库的更新操作不会出现在数据仓库环境下。不需要事务处理，恢复，和并发控制等机制只需要两种数据访问:数据的初始转载和数据访问（读操作）数据仓库与异种数据库集成传统的异种数据库集成:在多个异种数据库上建立包装程序（wrappers）和中介程序（mediators）查询驱动方法当从客户端传过来一个查询时，首先使用元数据字典将查询转换成相应异种数据库上的查询；然后，将这些查询映射和发送到局部查询处理器缺点：复杂的信息过虑和集成处理，竞争资源数据仓库:更新驱动将来

4、自多个异种源的信息预先集成，并存储在数据仓库中，供直接查询和分析高性能数据仓库与操作数据库系统操作数据库系统的主要任务是联机事务处理OLTP日常操作:购买，库存，银行，制造，工资，注册，记帐等数据仓库的主要任务是联机分析处理OLAP数据分析和决策OLTP和OLAP的主要区别：用户和系统的面向性:顾客 VS.市场数据内容:当前的、详细的数据 VS.历史的、汇总的数据数据库设计:实体联系模型(ER)和面向应用的数据库设计 VS.星型/雪花模型和面向主题的数据库设计视图:当前的、企业内部的数据 VS.经过演化的、集成的数据访问模式:事务操作 VS.只读查询（但很多是复杂的查询）OLTP系统和OLAP

5、系统的比较特征特征OLTPOLAP任务特点任务特点操作处理信息处理面向面向事务分析用户用户办事员、DBA、数据库专业人员经理、主管、数据分析员功能功能日常操作长期信息分析、决策支持DB设计设计基于E-R，面向应用星型/雪花，面向主体数据数据最新的、详细的历史的、汇总的视图视图详细的、二维关系型汇总的、多维的任务单位任务单位简短的事务复杂的查询访问数据量访问数据量数十个数百万个用户数用户数数千个数百个DB规模规模100M-数GB100GB-数TB优先性优先性高性能、高可用性高灵活性、端点用户自治度量度量事务吞吐量查询吞吐量、响应时间为什么需要一个分离的数据仓库?提高两个系统的性能DBMS是为OL

6、TP而设计的：存储方式,索引,并发控制,恢复数据仓库是为OLAP而设计：复杂的 OLAP查询,多维视图，汇总不同的功能和不同的数据:历史数据:决策支持需要历史数据，而这些数据在操作数据库中一般不会去维护数据汇总：决策支持需要将来自异种源的数据统一（如聚集和汇总）数据质量:不同的源使用不一致的数据表示、编码和格式，对这些数据进行有效的分析需要将他们转化后进行集成从关系表和电子表格到数据立方体数据仓库和数据仓库技术基于多维数据模型多维数据模型。这个模型把数据看作是数据立方体数据立方体形式。多维数据模型围绕中心主题组织，该主题用事实表事实表表示。事实事实是数值度量的。数据立方体数据立方体允许以多维数

7、据建模和观察。它由维维和事实事实定义。维维是关于一个组织想要记录的视角或观点。每个维都有一个表与之相关联，称为维表维表。事实表事实表包括事实的名称或度量以及每个相关维表的关键字在数据仓库的研究文献中，一个n维的数据的立方体叫做基本方体基本方体。给定一个维的集合，我们可以构造一个方体的格方体的格，每个都在不同的汇总级或不同的数据子集显示数据，方体的格称为数据立方体数据立方体。0维方体存放最高层的汇总，称作顶点方体顶点方体；而存放最底层汇总的方体则称为基本方体基本方体。数据立方体一个方体的格alltimeitemlocationsuppliertime,itemtime,locationtime,

8、supplieritem,locationitem,supplierlocation,suppliertime,item,locationtime,item,suppliertime,location,supplieritem,location,suppliertime,item,location,supplier0-D(apex)cuboid1-D cuboids2-D cuboids3-D cuboids4-D(base)cuboid数据仓库的概念模型最流行的数据仓库概念模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式的形式存在。星型模式（Star schema）:事实

9、表在中心，周围围绕地连接着维表（每维一个），事实表含有大量数据，没有冗余。雪花模式（Snowflake schema）:是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加表中。结果，模式图形成类似于雪花的形状。事实星座（Fact constellations）:多个事实表共享维表,这种模式可以看作星型模式集，因此称为星系模式（galaxy schema），或者事实星座（fact constellation）星型模式实例 time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcitystate_or_pr

10、ovincecountrylocationSales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_salesMeasuresitem_keyitem_namebrandtypesupplier_typeitembranch_keybranch_namebranch_typebranch雪花模式实例time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcity_keylocationSales Fact T

11、able time_key item_key branch_key location_key units_sold dollars_sold avg_salesMeasuresitem_keyitem_namebrandtypesupplier_keyitembranch_keybranch_namebranch_typebranchsupplier_keysupplier_typesuppliercity_keycitystate_or_provincecountrycity事实星座模式实例time_keydayday_of_the_weekmonthquarteryeartimelocat

12、ion_keystreetcityprovince_or_statecountrylocationSales Fact Tabletime_key item_key branch_key location_key units_sold dollars_sold avg_salesMeasuresitem_keyitem_namebrandtypesupplier_typeitembranch_keybranch_namebranch_typebranchShipping Fact Tabletime_key item_key shipper_key from_location to_locat

13、ion dollars_cost units_shippedshipper_keyshipper_namelocation_keyshipper_typeshipper一种数据挖掘查询语言:DMQLDMQL首先包括定义数据仓库和数据集市的语言原语，这包括两种原语定义：一种是立方体定义，一种是维定义立方体定义(事实表)define cube :维定义(维表)define dimension as()特殊案例(共享维表的定义)第一次作为维表定义“cube definition”然后：define dimension as in cube 实例：使用DMQL定义星型模式define cube sal

14、es_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,bran

15、ch_name,branch_type)define dimension location as(location_key,street,city,province_or_state,country)实例：使用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_

16、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)度量的分类一个数据立方体的度量是一个数值函数，该函数可以对数据立方体

17、的每一个点求值。度量可以根据其所用的聚集函数分为三类：分布的(distributive)：将函数用于n个聚集值得到的结果和将函数用于所有数据得到的结果一样。比如：count()，sum()，min()，max()等代数的(algebraic)：函数可以由一个带M个参数的代数函数计算（M为有界整数），而每个参数值都可以有一个分布的聚集函数求得。比如：avg()，min_N()，standard_deviation()整体的(holistic)：描述函数的子聚集所需的存储没有一个常数界。比如：median()，mode()，rank()概念分层：location维的一个概念分层allEuropeN

18、orth_AmericaMexicoCanadaSpainGermanyVancouverM.WindL.Chan.allregionofficecountryTorontoFrankfurtcity多维数据模型上的OLAP操作上卷(roll-up):汇总数据通过一个维的概念分层向上攀升或者通过维规约下钻(drill-down)：上卷的逆操作由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下或引入新的维来实现切片和切块(slice and dice)投影和选择操作转轴(pivot)立方体的重定位，可视化，或将一个3维立方体转化维一个2维平面序列其他OLAP操作钻过(drill_acro

19、ss)：执行涉及多个事实表的查询钻透(drill_through)：使用关系SQL机制，钻到数据立方体的底层，到后端关系表数据仓库设计：一个商务分析框架数据仓库设计中必须考虑的四种视图自顶向下视图允许我们选择数据仓库所需的相关信息，这些信息能够满足当前和未来商务的需求。数据源视图揭示被操作数据库系统所捕获、存储和管理的信息数据仓库视图有事实表和维表所组成，提供存放在数据仓库内部的信息，包括预先计算的综合与技术，以及关于源、日期和源时间等信息商务查询视图从最终用户的角度透视数据仓库中的数据数据仓库的设计过程（P43）自顶向下法、自底向上法或者两者的混合方法自顶向下法：由总体设计和规划开始（成熟）

20、自底向上法：以实验和原型开始（快速）从软件过程的观点瀑布式方法：在进行下一步前，每一步都进行结构化和系统的分析螺旋式方法：功能渐增的系统的快速产生，相继版本之间间隔很短典型的数据仓库设计过程选取待建模的商务过程选取商务过程的粒度选取用于每个事实表记录的维选取将安放在事实表中的度量三层数据仓库架构DataWarehouseExtractTransformLoadRefreshOLAP服务器AnalysisQueryReportsData miningMonitor&IntegratorMetadata数据源前端工具ServeData MartsOperational DBsothersource

21、s数据仓库服务器OLAP Server三种数据仓库模型（从结构的角度）企业仓库搜集关于跨越整个组织的主题的所有信息，来自一个或多个操作的系统，跨功能的。数据集市企业范围数据的一个子集，对于特定的客户是有用的。其范围限于选定的主题，比如一个商场的数据集市独立的数据集市 VS.非独立的数据集市（数据来自于企业数据仓库）虚拟仓库操作数据库上的一系列视图只有一些可能的汇总视图被物化数据仓库开发自顶向下开发：一种系统的而解决方法，并能最大限度地减少集成问题。但费用高，长时间开发，缺乏灵活性，因为整个组织的共同数据模型达到一致是困难的。自底向上:设计、开发、部署独立的数据集市方法提供了灵活性、低花费，并能

22、快速回报投资。然后，将分散的数据集市集成，形成一个一致的企业数据仓库时，可能导致问题。数据仓库开发一个推荐的方法定义高层数据模型定义高层数据模型数据数据集市集市数据数据集市集市分布式数据分布式数据集市集市多层数据仓库多层数据仓库企业数据仓库企业数据仓库模型提炼模型提炼模型提炼模型提炼OLAP服务器类型关系OLAP服务器(ROLAP)使用关系数据库或扩展的关系数据库存放并管理数据仓库的数据，而用OLAP中间件支持其余部分包括每个DBMS后端优化，聚集导航逻辑的实现，附加的工具和服务较大的可扩展性多维OLAP服务器(MOLAP)基于数组的多维存储引擎（稀疏矩阵技术）能对预计算的汇总数据快速索引混合

23、OLAP服务器(HOLAP)结合上述两种技术，更大的使用灵活性特殊的SQL服务器在星型和雪花模型上支持SQL查询数据仓库的实现难点海量数据快速反应OLAP服务器要在几秒内响应决策支持查询方法高效的数据立方体计算技术高效的存取方法高效的查询处理技术数据立方体的有效计算数据立方体可以被看成是一个方体的格方体的格最底层的方体是基本方体最顶端的方体（顶点）只包含一个单元的值一个n维的数据立方体，每维Li层，可能产生的方体总数是多少？数据立方体的物化（物化（materialization)预先计算所有方体（全物化全物化）:需要海量存储空间，存放预先计算的方体不预先计算任何“非基本”方体（不物化不物化），

24、在运行时计算昂贵的多维聚集，可能很慢有选择的计算一个所有方体的适当子集（部分物化部分物化）：相应时间和存储空间的折中。确定物化哪些方体考虑工作负荷下的查询、它们的频率和它们的开销等等方体的操作DMQL中的方体定义和计算define cube salesitem,city,year:sum(sales_in_dollars)compute cube sales上述的compute cube子句可以转化为一个类似于SQL的语句SELECT item,city,year,SUM(amount)FROM SALESCUBE BY item,city,year需要计算以下的group by子句(item

25、,city,year)(item,city),(item year),(city,year)(item),(city),(year)()(item)(city)()(year)(city,item)(city,year)(item,year)(city,item,year)方体计算：关系型OLAP的方法（ROLAP）方体计算的有效方法基于ROLAP的方体算法(Agarwal et al96)基于数组的算法基于数组的算法(MOLAP)(Zhao et al97)自底向上的计算方法(Beyer&Ramarkrishnan99)H-cubing技术(Han,Pei,Dong&Wang:SIGMOD0

26、1)基于ROLAP的方法将排序、散列(hashing)和分组操作应用于维的属性，以便对相关元组重新排序和聚类在某些子聚集上分组，作为“部分分组步骤”。可以由以前计算的聚集计算新的聚集，而不必有基本事实表计算方体计算的多路数组聚集方法(1)将数组分成块（chunk,一个可以装入内存的小子方）压缩的稀疏数组寻址：(chunk_id,offset)通过访问立方体单元，计算聚集。可以优化访问单元组的次序，使得每个单元被访问的次数最小化，从而减少内存访问和磁盘I/O的开销。A(month)B29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1

27、b0a2a3C(item)B(city)442856402452362060哪个是多路数组哪个是多路数组聚集的最佳遍历聚集的最佳遍历次序？次序？方体计算的多路数组聚集方法(2)A(month)40B29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C(item)4000442856402452362060B(city)400方体计算的多路数组聚集方法(3)AB29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C44285640245236206

28、0B方体计算的多路数组聚集方法(4)方法：各平面要按他们大小的升序排列进行排序和计算详见书P50 例2.12思想：将最小的平面放在内存中，对最大的平面每次只是取并计算一块这种方法的限制：只有在维数比较小的情况下，效果才比较理想(要计算的立方体随维数指数增长)如果维的数目比较多，可以考虑使用“自底向上的计算”或者时“冰山方体”计算元数据存储在数据仓库中，元数据就是定义数据仓库对象的数据。关于数据的数据。有以下几种：数据仓库结构的描述仓库模式、视图、维、层次结构、导出数据的定义，以及数据集市的位置和内容操作元数据包括数据血统(data lineage)、数据类别(currency of data)

29、，以及监视信息汇总用的算法：包括度量和维定义算法，数据粒度、分割、主题领域、聚集、汇总、预定义的查询和报告由操作环境到数据仓库的映射：数据提取、清理、转换规则、剪裁规则、安全等关于系统性能的数据索引，profiles，数据刷新、更新或复制事件的调度和定时商务元数据商务术语和定义、数据拥有者信息、收费政策等元数据的使用元数据与数据一起，构成了数据仓库中的数据模型，元数据所描述的更多的是这个模型的结构方面的信息。在数据仓库中，元数据的主要用途包括：用作目录，帮助决策支持系统分析者对数据仓库的内容定义作为数据仓库和操作性数据库之间进行数据转换时的映射标准用于指导当前细节数据和稍加综合的数据之间的汇总

30、算法，指导稍加综合的数据和高度综合的数据之间的汇总算法。数据仓库后端工具和使用程序用于加载和刷新它的数据数据提取：从多个外部的异构数据源收集数据数据清理检测数据种的错误并作可能的订正数据变换将数据由历史或主机的格式转化为数据仓库的格式装载排序、汇总、合并、计算视图，检查完整性，并建立索引和分区刷新将数据源的更新传播到数据仓库中数据仓库的应用数据仓库的三种应用信息处理支持查询和基本的统计分析，并使用交叉表、表、图标和图进行报表处理分析处理对数据仓库中的数据进行多维数据分析支持基本的OLAP操作，切块、切片、上卷、下钻、转轴等数据挖掘从隐藏模式中发现知识支持关联分析，构建分析性模型，分类和预测，并

31、用可视化工具呈现挖掘的结果三种应用间的差别（P62）从联机分析处理到联机分析挖掘为什么要联机分析挖掘（P63）数据仓库中有高质量的数据数据仓库中存放着整合的、一致的、清理过的数据围绕数据仓库的信息处理结构存取、集成、合并多个异种数据库的转换，ODBC/OLEDB连接,Web访问和访问工具等基于OLAP的探测式数据分析使用上卷、下钻、切片、转轴等技术进行数据挖掘数据挖掘功能的联机选择多种数据挖掘功能、算法和任务的整合联机分析挖掘的体系结构数据仓库数据仓库元数据元数据多维数多维数据库据库OLAM引擎引擎OLAP引擎引擎用户图形界面用户图形界面 API数据方体数据方体 API数据库数据库 API数据

32、清理数据清理数据集成数据集成Layer3OLAP/OLAMLayer2多维数据库多维数据库Layer1数据存储数据存储Layer4用户界面用户界面数据的过滤、集成数据的过滤、集成过滤过滤数据库数据库基于约束的基于约束的数据挖掘数据挖掘挖掘结果挖掘结果数据预处理主要内容为什么要预处理数据？数据清理数据集成和变换数据归约为什么要预处理数据？现实世界的数据是“肮脏的”不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据含噪声的：包含错误或者“孤立点”不一致的：在编码或者命名上存在差异没有高质量的数据，就没有高质量的挖掘结果高质量的决策必须依赖高质量的数据数据仓库需要对高质量的数据进行一致地集成数据

33、质量的多维度量一个广为认可的多维度量观点：精确度完整度一致性合乎时机可信度附加价值可访问性跟数据本身的含义相关的内在的、上下文的、表象的数据预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要数据预处理的形式空缺值数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因

34、为误解而没有被输入的数据在输入时，有些数据应为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上如何处理空缺值忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样公式或判定树这样的基于推断的方法的基于推断的方法噪声数据噪声：一个测量变量中的随机错误或偏差引起不正

35、确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其它需要数据清理的数据问题重复记录不完整的数据不一致的数据如何处理噪声数据 分箱(binning):首先排序数据，并将他们分到等深的箱中然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等聚类：监测并且去除孤立点计算机和人工检查结合计算机检测可疑数据，然后对它们进行人工判断回归通过让数据适应回归函数来平滑数据数据平滑的分箱方法price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱

36、1：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34聚类回归xyy=x+1X1Y1Y1数据集成数据集成：将多个数据源中的数据整合到一个一致的存储中模式集成：整合不同数据源中的元数据实体识别问题：匹配来自不同数据源的现实世界的实体，比如：A.cust-id=B.customer_no检测并解决数据值的冲突对现实世界中的同一实体，来自不同数据源的属性值可能是不同的可能的原因：不同的数据表示，不同的度量等等处理数据集成中的冗余数据集成多个数据库时，经常会出现冗余数据同一属性在不同的数据库中会有不同的字段名一个属性可以由

37、另外一个表导出，如“年薪”有些冗余可以被相关分析检测到仔细将多个数据源中的数据集成起来，能够减少或避免结果数据中的冗余与不一致性，从而可以提高挖掘的速度和质量。数据变换平滑：去除数据中的噪声聚集：汇总，数据立方体的构建数据概化：沿概念分层向上汇总规范化：将数据按比例缩放，使之落入一个小的特定区间最小最大规范化z-score规范化小数定标规范化属性构造通过现有属性构造新的属性，并添加到属性集中。数据变换规范化最小最大规范化z-score规范化小数定标规范化其中，j是使 Max(|)1的最小整数数据归约策略数据仓库中往往存有海量数据，在其上进行复杂的数据分析与挖掘需要很长的时间数据归约数据归约可以

38、用来得到数据集的归约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果数据归约策略数据立方体聚集维归约数据压缩数值归约离散化和概念分层产生用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。数据立方体聚集最底层的方体对应于基本方体基本方体对应于感兴趣的实体在数据立方体中存在着不同级别的汇总数据立方体可以看成方体的格每个较高层次的抽象将进一步减少结果数据数据立方体提供了对预计算的汇总数据的快速访问使用与给定任务相关的最小方体在可能的情况下，对于汇总数据的查询应当使用数据立方体维归约通过删除不相干的属性或维减少数据量属性子集选择找出最小属性集，使得数据类的概率分布尽可能的接

39、近使用所有属性的原分布减少出现在发现模式上的属性的数目，使得模式更易于理解启发式的（探索性的）方法逐步向前选择逐步向后删除向前选择和向后删除相结合判定归纳树探索性选择方法d个属性有2d d个可能的子集逐步向前选择由空属性集开始，选择原属性集中最好的属性，并将其添加入该集合，重复该步骤。逐步向后删除由整个属性集开始，每一步都删除掉尚在属性集中的最坏属性向前选择和向后删除相结合每一步选择一个最好属性，并删除一个最坏属性可以使用一个临界值来判定上述三种方法的结束条件判定归纳树数据压缩有损压缩 VS.无损压缩字符串压缩有广泛的理论基础和精妙的算法通常是无损压缩在解压缩前对字符串的操作非常有限音频/视频

40、压缩通常是有损压缩，压缩精度可以递进选择有时可以在不解压整体数据的情况下，重构某个片断两种有损数据压缩的方法：小波变换和主要成分分析数值归约通过选择替代的、较小的数据表示形式来减少数据量有参方法：使用一个参数模型估计数据，最后只要存储参数即可。线性回归方法：Y=+X多元回归：线性回归的扩充对数线性模型：近似离散的多维数据概率分布无参方法：直方图聚类选样直方图一种流行的数据归约技术将某属性的数据划分为不相交的子集，或桶，桶中放置该值的出现频率桶和属性值的划分规则等宽等深V-最优MaxDiff聚类将数据集划分为聚类，然后通过聚类来表示数据集如果数据可以组成各种不同的聚类，则该技术非常有效，反之如果

41、数据界线模糊，则方法无效数据可以分层聚类，并被存储在多层索引树中聚类的定义和算法都有很多选择选样允许用数据的较小随机样本（子集）表示大的数据集对数据集D的样本选择：简单随机选择n个样本，不回放：由D的N个元组中抽取n个样本简单随机选择n个样本，回放：过程同上，只是元组被抽取后，将被回放，可能再次被抽取聚类选样：D中元组被分入M个互不相交的聚类中，可在其中的m个聚类上进行简单随机选择（m400?，01000的整数将在比较1000次后得出结果，但是如果先将这1000个值划分为10个区间：0-100,100-200900-1000，则只要比较10次就可以得出结果）离散化的数值用于进一步分析离散化和概

42、念分层离散化通过将属性域划分为区间，减少给定连续属性值的个数。区间的标号可以代替实际的数据值。概念分层通过使用高层的概念（比如：青年、中年、老年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据概念分层后，数据的细节丢失了，但是概化后的数据更有意义，更容易解释，而且所需的存储空间更少。有效的减少I/O支出数据数值的离散化和概念分层生成分箱（binning）分箱技术递归的用于结果划分，可以产生概念分层。分箱、递归的：比如将10,000个值，每个箱子中放10个，则可以将其规约为1000个值；如果要求将这10,000个值规约为10个概念，则只要将上述分箱方法递归的使用3次就可以了。直方图分析（

43、histogram）直方图分析方法递归的应用于每一部分，可以自动产生多级概念分层。聚类分析将数据划分成簇，每个簇形成同一个概念层上的一个节点，每个簇可再分成多个子簇，形成子节点。基于熵的离散化通过自然划分分段通过自然划分分段将数值区域划分为相对一致的、易于阅读的、看上去更直观或自然的区间。自然划分的3-4-5规则：如果一个区间最高有效位上包含3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；如果一个区间最高有效位上包含2，4，或8个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位上包含1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区

44、间对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%比如年收入最低的可能时5，000，最高的可能是50万，如果之间进行区间划分，就会将顶层划分为5个分段（每10万1个），但是95以上的人他们的收入都是集中在【10,000100,000】的范围，也就是说都集中在第一段，这样的分段就会引起结果的扭曲分类数据的概念分层生成分类数据是指无序的离散数据，它有有限个值（可能很多个）。分类数据的概念分层生成方法：由用户或专家在模式级显式的说明属性的部分序。通过显示数据分组说明分层结构的一部分。说明属性集，但不说明它们的偏序，然后系统根据算法自动产生属性的序，构造有意义的概念分层。对只说明部分属性集的情况，则可根据数据库模式中的数据语义定义对属性的捆绑信息，来恢复相关的属性。属性集的规格根据在给定属性集中，每个属性所包含的不同值的个数，可以自动的生成概念分成；不同值个数最多的属性将被放在概念分层的最底层。越底层的属性集将有越多的不同值跟它相对应，而越高层的属性值将有越少的不同值跟它相对应。因为底层属性的值要通过汇总才可以生成高层属性的值，而汇总就意味着不同值个数的减少。countryprovincecitystreet5个不同值65 个不同值3567 个不同值674,339 个不同值