数据仓库与数据挖掘复习资料课件

数据仓库与数据挖掘复习数据仓库数据仓库基本原理、OLAP基本原理数据仓库的模型设计和OLAP建模数据仓库的规划和开发SQL Server 2005与数据仓库的实现数据挖掘数据挖掘 数据挖掘概念数据挖掘概念 数据挖掘基础数据挖掘基础 数据挖掘支柱：数据挖掘支柱：数据、技术、模型数据、技术、模型 数据挖掘的应用数据挖掘的应用概念 对数据仓库所下的定义对数据仓库所下的定义：数据仓库是面向：数据仓库是面向主题的、集成的、稳定的、随时间变化的主题的、集成的、稳定的、随时间变化的数据集合，用以支持管理决策的过程。数据集合，用以支持管理决策的过程。数据挖掘：企业角度数据挖掘：企业角度 指从数据库的大量数据中指从数据库的大量数据中提取提取隐含、目前未知、隐含、目前未知、潜在有用和最终可理解的潜在有用和最终可理解的模式模式（如知识规则、（如知识规则、限制条件和规律等）的非平凡过程。限制条件和规律等）的非平凡过程。概念 数据挖掘：商业角度数据挖掘：商业角度 是一种新的商业信息处理技术，其主要特点是是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转对商业数据库中的大量业务数据进行抽取、转换、分析和其它模型化处理，从中换、分析和其它模型化处理，从中提取提取辅助商辅助商业决策的业决策的关键性数据关键性数据。模式模式 定义：模式是一个用语言定义：模式是一个用语言L表示的表达式表示的表达式E，它，它可用来描述数据集可用来描述数据集F中的数据的特征，中的数据的特征，E所描述所描述的数据是集合的数据是集合F的一个子集的一个子集FE。概念“清洗”就是将错误的、不一致的数据在进入数据仓库之前予以更正或删除，以免影响DSS决策的正确性。元数据：是用来描述数据的数据。它描述和定位数据组件、它们的起源及它们在数据仓库进程中的活动；关于数据和操作的相关描述(输入、计算和输出)。元数据可用文件存在元数据库中。概念 OLAP：粒度就是对数据仓库中数据综合程度的一个度量。它既影响数据仓库中的数据量的多少，也影响数据仓库所能回答询问的种类。DM:粒度的第二种形式是指抽样率，即以一定的抽样率对数据仓库中的数据进行抽样后得到一个样本数据库，数据挖掘将在这个样本数据库上进行。概念 维代表了用户观察数据的特定视角，如时间维、地区维、产品维等。度量度量是数据的实际意义，描述数据“是什么”，即一个数值的测量指标，如人数、单价、销售量等。数据切片、切块、上卷、下钻、转轴数据钻取就是从较高的维度层次下降到较低的维度层次上来观察多维数据。概念：数据挖掘 相关属性相关属性 挖掘过程中要考虑的感兴趣的属性挖掘过程中要考虑的感兴趣的属性 模式模板：模式模板：给定挖掘任务，除说明要挖掘的知识类型，可进一步给定挖掘任务，除说明要挖掘的知识类型，可进一步说明和提供所发现模式匹配的说明和提供所发现模式匹配的元模式、元规则、元查询：元模式、元规则、元查询：可以用于指导发现过程可以用于指导发现过程 概念分层：定义一个概念分层：定义一个映射序列映射序列，将低层概念映射到更，将低层概念映射到更一般的高层概念。一般的高层概念。Schema hierarchy模式分层 Set-grouping hierarchy集合分组分层 Operation-derived hierarchy操作导出的分层 Rule-based hierarchy基于规则的分层概念：数据挖掘 强关联规则（强关联规则（strong association rule）同时满足用户定义的同时满足用户定义的最小最小置信度阈值和置信度阈值和最小最小支持度支持度阈值的关联规则。阈值的关联规则。数据仓库部分 要解决“蜘蛛网”问题，必须将用于事务处理的数据环境和用于数据分析的环境分离。这样，数据处理被分为两大类：操作型处理(事务型处理)操作型处理以传统的数据库为中心进行企业的日常业务处理。分析型处理分析型处理以数据仓库为中心分析数据背后的关联和规律，为企业决策提供可靠有效的依据。数据仓库体系结构数据仓库的数据组织结构不同于一般的数据库系统，需要将从原有的业务数据库中获得的基本数据和综合数据分成一些不同的级别。在数据仓库中，采用分级的方式进行组织。星型结构和雪花型结构 星型结构通过将事实表和维表进行连接，我们就可以得到“星型结构”(Star-Scheme)。p雪花型结构雪花型结构 实际应用需求并不像标准星型结构描述的那么简单，当问题涉及的维度很多时，事实表中的条目数将迅速增长。假定原来的事实表条目数为m，增加一个具有n个条目的维表，通常，事实表的条目数将变成mn条，这样事实表所占用的存储空间将迅速增大。在这种情况下，可以考虑使用“雪花型”的结构。总的来讲，ROLAP在大数据量的存储上有绝对的优势，因此拥有巨型数据量的系统可以选择ROLAP。MOLAP在响应速度、预运算和多维计算方面具有优势，中小型系统可以考虑使用MOLAP。但是ROLAP和MOLAP之间的技术差异不是绝对的。现在MOLAP和ROLAP厂商正在相互借鉴，相互学习对方的技术优势。HOLAP就是对MOLAP和ROLAP的良好折中。数据仓库设计的基本过程：建立企业模型；概念模型设计；逻辑模型设计；物理模型设计以及数据装载接口的设计。收集应用收集应用需求需求 分析应用需求分析应用需求 构建数据库构建数据库 数据仓库建模数据仓库建模 数据获取与集成数据获取与集成 构建数据仓库构建数据仓库 系统实施系统实施 应用编程应用编程 系统测试系统测试 DSS应用编程应用编程 系统测试系统测试 理解理解需求需求DB应用应用B应 用应 用ADBDB 外部外部数据数据DW SDLC方法方法 CLDS方法方法数据仓库的开发方法瀑布式开发 螺旋式开发数据仓库 应用 OLAP DMOLAPDM 在何种数据上进行数据挖掘在何种数据上进行数据挖掘 Relational database 关系数据库关系数据库 Data warehouse 数据仓库数据仓库 Transactional database 事务数据库事务数据库 Advanced database and information repository Object-relational database 对象关系数据库对象关系数据库 Spatial and temporal data 空间和时间数据空间和时间数据 Time-series data 时间系列数据时间系列数据 Stream data 流数据流数据 Multimedia database 多媒体数据库多媒体数据库 Heterogeneous and legacy database 异类和遗留数据库异类和遗留数据库 Text databases&WWW 文本数据库和文本数据库和WWW数据挖掘功能数据挖掘功能 Concept description概念描述:Characterization and discrimination特征化和区分 Generalize归纳,summarize汇总,and contrast data characteristics,e.g.,dry vs.wet regions Association关联(correlation and causality相关性和因果关系)Diaper Beer 0.5%,75%Classification and Prediction 分类和预测 分类：找出描述或区分数据类或概念的模型（或函数），以便能够使用模型预测类标记未知的对象类。E.g.,classify countries based on climate,or classify cars based on gas mileage英里里程 Presentation:decision-tree,classification rule,neural network Predict some unknown or missing numerical values Cluster analysis 聚类分析 Class label类标记 is unknown:Group data to form new classes,e.g.,cluster houses to find distribution patterns Maximizing intra-class类内 similarity&minimizing interclass类间 similarity Outlier analysis孤立点分析 孤立点:与数据的一般行为或模型不一致的数据对象。Noise or exception?噪声或例外 No!useful in fraud detection,rare events analysis Trend and evolution analysis趋势和演变分析 Trend and deviation:regression analysis Sequential pattern mining,periodicity analysis Similarity-based analysis Other pattern-directed or statistical analyses分类 General functionality 一般功能性 Predictive data mining 预测式 Descriptive data mining 描述式 Different views,different classifications Kinds of data to be mined 挖掘的数据类型 Kinds of knowledge to be discovered 发现的知识类型 Kinds of techniques utilized 根据使用的技术 Kinds of applications adapted 根据应用数据挖掘实施控制self 挖掘环境得以成功的要素挖掘环境得以成功的要素 五个要素：五个要素：由一人来专职负责由一人来专职负责建立团队建立团队 团队由各个学科的人员组成团队由各个学科的人员组成 分成技术的和商业的分成技术的和商业的 范围广：企业用户到数据所有者，从统计人员到经理范围广：企业用户到数据所有者，从统计人员到经理 各个事业单位一开始就参与进来各个事业单位一开始就参与进来 数据挖掘的目的，是将结果发布给各事业单位去执行，一开始参与进来，数据挖掘的目的，是将结果发布给各事业单位去执行，一开始参与进来，可以从商业角度推动这项工作。可以从商业角度推动这项工作。信息技术部门一开始也要参与进来信息技术部门一开始也要参与进来 数据挖掘是一项技术，与组织内的其它技术应协调、一致，因为用于挖数据挖掘是一项技术，与组织内的其它技术应协调、一致，因为用于挖掘的数据可能来自任何其它不同的系统。掘的数据可能来自任何其它不同的系统。示范项目可以展现数据挖掘的能力示范项目可以展现数据挖掘的能力 示范项目的成功，推动数据挖掘的开展。示范项目的成功，推动数据挖掘的开展。此项目需要数据挖掘团队精心挑选，并与软件供应商和拥有丰富经验的此项目需要数据挖掘团队精心挑选，并与软件供应商和拥有丰富经验的顾问门亲密合作。顾问门亲密合作。数据挖掘过程数据挖掘过程 数据挖掘的互动循环过程将数据挖掘定位于企业的需求。数据挖掘的互动循环过程将数据挖掘定位于企业的需求。包括下面几个阶段：包括下面几个阶段：Michael J.A.Berry的四阶段过程A.理解业务问题理解业务问题数据挖掘人员广泛听取业内专家意见，确定关键业务问题，明确所需数据。数据挖掘人员广泛听取业内专家意见，确定关键业务问题，明确所需数据。另一方面，业内专家意见需要通过数据验证。另一方面，业内专家意见需要通过数据验证。B.将数据转换成可执行的结果将数据转换成可执行的结果构建模型是一个反复循环的过程，需要知道结果被如何使用。构建模型是一个反复循环的过程，需要知道结果被如何使用。C.结果实施过程结果实施过程挖掘目的是将生成的决策付诸行动。存在不同的表现方式：如有的结果帮助挖掘目的是将生成的决策付诸行动。存在不同的表现方式：如有的结果帮助企业深入了解自己；有的结果只能使用一次；有的需要保存，放进数据仓库企业深入了解自己；有的结果只能使用一次；有的需要保存，放进数据仓库D.评价结果的实施评价结果的实施评测结果将给数据挖掘互动循环系统提出新的问题和新的数据，同时，指出评测结果将给数据挖掘互动循环系统提出新的问题和新的数据，同时，指出数据挖掘的努力方向。数据挖掘的努力方向。数据挖掘过程数据挖掘过程B.将数据转换成可执行的结果将数据转换成可执行的结果明确所需的数据获得数据生成有效数据探索、清洁数据转换数据添加衍生变量创建建模数据集选择建模方法训练模型检查模型的执行效果选择最好的模型数据不太准确得不到数据数据不准确添加新的衍生变量可以改变执行效果新的数据分割或重抽样可以改进模型的效果另一方法或参数可改进效果Data Mining:A KDD ProcessnData miningcore of knowledge discovery processData CleaningData IntegrationDatabasesData WarehouseTask-relevant DataSelectionData MiningPattern EvaluationA5预处理：对数据列的基本处理 对于数据挖掘十分重要的一些特例的分布情况：只有一种值的列 缺乏任何信息内容，忽略。例如：1.null，no，0 2.如建立一个模型预测新泽西州的汽车客户损失率，关于州 名将都是“NJ”，忽略这个字段 几乎只含一种值的列 一般规则：如果某一列中95%99%的值相同，这一列很可能没用 列的值各不相同 无法进行预测 如：客户身份证号码 忽略与目标同义的列 某一列与目标列相关度很高时，可能意味着这一列是目标列的同义列。如：判断是否流失，非空的流失日期 与 已经流失 同义数据预处理的主要任务 Data cleaning数据清洗 Fill in missing values,smooth noisy data,identify or remove outliers,and resolve inconsistencies 填充空缺值，平滑噪声数据，识别或移走孤立点，解决不一致 Data integration 数据集成 Integration of multiple databases,data cubes,or files 集成到多个数据库、数据立方体或文件 Data transformation数据变换 Normalization and aggregation 规范化和聚集 Data reduction 数据规约 Obtains reduced representation in volume but produces the same or similar analytical results 获得数据集的压缩表示，产生同样的或几乎同样的分析结果 Data discretization数据离散化 Part of data reduction but with particular importance,especially for numerical data（减少数据，特别是数值数据。如：概念分层）挖掘方法：概念描述 重点学习方法：1.面向属性的归纳（泛化方法）；概念概念描述描述一般概念描述一般概念描述分类概念描述分类概念描述特征化特征化：面向属性归纳方法。：面向属性归纳方法。比较比较类特征化类特征化(解析特征化解析特征化)：用到面向属性归纳和属性相关分析方法。：用到面向属性归纳和属性相关分析方法。类比较类比较(解析比较解析比较)特征化特征化/类特征化（解析特征化）：类特征化（解析特征化）：t权的量化特征规则。权的量化特征规则。比较比较/类比较（解析比较）：类比较（解析比较）：d权的量化区分规则。权的量化区分规则。量化描述规则量化描述规则Attribute-Oriented Induction通过概化实现一般性概念描述 How it is done?（基本思想）使用关系数据库查询收集任务相关的数据(initial relation)考察任务相关的数据中每个属性的不同值的个数，进行泛化。通过属性删除或属性泛化进行。通过合并相等的广义元组，并累计它们对应的计数值进行聚集。压缩泛化后的数据集合 结果的广义关系可以映射到不同形式。如图表、规则关联规则挖掘 重点：在事务数据库中挖掘单维布尔关联重点：在事务数据库中挖掘单维布尔关联规则规则 mining of single-dimensional Boolean association rules in transactional databases 1.找出所有频繁项集找出所有频繁项集 使用候选项集找频繁项集（使用候选项集找频繁项集（由由Apriori算法实现）算法实现）2.由频繁项集产生强关联规则由频繁项集产生强关联规则单维布尔关联规则挖掘（Association rule mining）过程1 1.使用候选项集找出所有频繁项集，使用候选项集找出所有频繁项集，由由 Apriori算法实现算法实现 Apriori算法算法基本思想：基本思想：使用逐层搜索的迭代方法。使用逐层搜索的迭代方法。k-项集用于搜索项集用于搜索(k+1)-项集。项集。过程：过程：DC1 L1 C2 L2 C3 L3 Ck Lk Cm1 Lm1 如此下去，直到不能找到频繁如此下去，直到不能找到频繁m-项集。项集。其中：其中：Ck：候选：候选k-项集的集合（项集的集合（k1m1），），由由Lk-1产生。产生。Lk：频繁：频繁k-项集的集合（项集的集合（k1m1）,Lk满足最小支持度，即满足最小支持度，即 最小事务支持计数最小事务支持计数。D：待挖掘的事务数据库。：待挖掘的事务数据库。找每个找每个Lk需要扫描整个数据库需要扫描整个数据库D。关键：关键：Lk-1 Ck (连接步、剪枝步连接步、剪枝步)A152Apriori:A Candidate Generation-and-test Approach Apriori性质：性质：Any subset of a frequent itemset must be frequent 任何频繁项集的非空子集都是频繁的。if beer,diaper,nuts is frequent,so is beer,diaper Every transaction having beer,diaper,nuts also contains beer,diaper 即：子集不是频繁的，其超集也不是频繁的。如果A 不是频繁集，则超集 A，B不是频繁集 超集：A，B 包含A How to apply in the Apriori algorithm?A152单维布尔关联规则挖掘（Association rule mining）过程2 2.由频繁项集产生关联规则由频繁项集产生关联规则 规则规则XY在事务集中的在事务集中的置信度置信度（confidence）是指包含）是指包含X和和Y的事务数与包含的事务数与包含X的事务数之比，即的事务数之比，即项集的支持度计数表示项集的支持度计数表示。记为记为confidence(XY)，即，即confidence(XY)=|T:X Y T，T D|/|T:X T，T D|n(X Y)/n(X)根据该式，关联规则可以如下产生：根据该式，关联规则可以如下产生：对于每个频繁项集对于每个频繁项集L，产生，产生L的所有非空子集。的所有非空子集。对于对于L的每个非空子集的每个非空子集s，如果，如果 则输出规则则输出规则“s（L-s）”。其中，。其中，min_conf是最小置信度是最小置信度阈值。阈值。A156support_count(L)support_count(s)min_confThe Apriori AlgorithmAn ExampleDatabase TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E2A153剪枝剪枝剪枝剪枝联接联接联接联接用性质用性质由频繁项集产生关联规则_实例例如：例如：L3：频繁：频繁3-项集的集合。包含项集项集的集合。包含项集L=B,C,E，可以由，可以由L产生那些关联产生那些关联规则？规则？L的非空子集的非空子集s有有B,C,B,E,C,E,B,C,E。输出关联规则结果输出关联规则结果“s（Ls）”如下：如下：如果最小置信度阈值为如果最小置信度阈值为70%，则只有，则只有1、3规则可以输出。因为规则可以输出。因为1、3为为产生的强规则。产生的强规则。ItemsetsupB,C,E2L36%7.663/25%7.663/24%7.663/23%1002/2 2%7.663/21%1002/2confidenceCBEconfidenceEBCconfidenceECBconfidenceBECconfidenceCEBconfidenceECBsupport_count(L)support_count(s)min_confDatabase TDBTidItems10A,C,D20B,C,E30A,B,C,E40B,EClassification vs.Prediction 数据挖掘界广泛接受的观点：分类：用预测法预测类标号（对离散数据的分类）预测：用预测法预测连续值（对数值数据的分类）（如：回归方法）A186 B46ClassificationA Two-Step Process 1.构造模型 Model construction:描述一个预定的数据集或类集。describing a set of predetermined classes 2.使用模型 Model usage:for classifying future or unknown objectsA185Classification Process(2):Use the Model in PredictionClassifierTestingData NAME RANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yesUnseen Data(Jeff,Professor,4)Tenured?A185ID3算法算法 Quinlans ID3是国际上最有影响和最为典型的决策树学习方法。获取信息时，将不肯定的内容转为肯定的内容，因此信息伴随着不肯定性。一般来讲，小概率事件比大概率事件信息量大，如果某事“闻所未闻”或“百年不遇”则肯定比“习以为常”的事更具有信息量。如何度量信息量。根据Shannon于1948年提出的信息论理论。选择信息量较多的属性。B42Classification by decision tree induction 基本思想：利用信息论中的信息增益理论寻找数据集中具有最大信息量的字段，建立决策树的一个节点，再根据字段的不同取值建立树的分支，在每个分支子集中重复建树的下层节点和分支的过程，即可建立决策树。判定树分类算法训练集决策树inputoutputB38Rough Set Approach 粗糙集用于近似地或粗糙地定义等价类 给定类C 的粗糙集的两种情况:下近似：肯定包含在类C中 上近似：不能说不属于类CA210每个矩形代表一个等价类Rough Set Approach 对于从数据库中发现分类规则，其基本思想：将数据库中的属性分为条件和结论属性，对数据库中的元组根据各个属性的不同属性值分成相应的子集，然后基于条件属性划分的子集与结论属性划分的子集间的上下近似关系生成关联规则。E129聚类 基本思想：物以类聚What Is Good Clustering?A good clustering method will produce high quality clusters with类内高度相似类间低度相似Type of data in clustering analysis Interval-scaled variables:区间标度变量 Binary variables二元变量:Nominal标称,ordinal序数,and ratio variables比例标度变量:Variables of mixed types混合类型的变量 相异度计算A226Partitioning Algorithms:Basic Concept Global optimal:exhaustively enumerate all partitions Heuristic methods:k-means and k-medoids algorithms k-means(MacQueen67):Each cluster is represented by the center(means)of the cluster k-medoids or PAM(Partition around medoids)(Kaufman&Rousseeuw87):Each cluster is represented by one of the objects in the clusterA231The K-Means Clustering Method Example012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign