数据挖掘概念复习资料(DOC 10页).doc

1、数据挖掘：是从大量数据中发现有趣（非平凡的、隐含的、先前未知、潜在有用）模式，这些数据可以存放在数据库，数据仓库或其他信息存储中。挖掘流程：(1)学习应用域（2）目标数据创建集（3）数据清洗和预处理（4）数据规约和转换（5）选择数据挖掘函数（总结、分类、回归、关联、分类）（6）选择挖掘算法（7）找寻兴趣度模式（8）模式评估和知识展示（9）使用挖掘的知识概念/类描述：一种数据泛化形式，用汇总的、简洁的和精确的方法描述各个类和概念，通过（1）数据特征化：目标类数据的一般特性或特征的汇总；（2）数据区分：将目标类数据的一般特性与一个或多个可比较类进行比较；（3）数据特征化和比较来得到。关联分析：发现

2、关联规则，这些规则展示属性-值频繁地在给定数据集中一起出现的条件，通常要满足最小支持度阈值和最小置信度阈值。分类：找出能够描述和区分数据类或概念的模型，以便能够使用模型预测类标号未知的对象类，导出的模型是基于训练集的分析。导出模型的算法：决策树、神经网络、贝叶斯、（遗传、粗糙集、模糊集）。预测：建立连续值函数模型，预测空缺的或不知道的数值数据集。孤立点：与数据的一般行为或模型不一致的数据对象。聚类：分析数据对象，而不考虑已知的类标记。训练数据中不提供类标记，对象根据最大化类内的相似性和最小化类间的原则进行聚类或分组，从而产生类标号。第二章数据仓库数据仓库是一个面向主题的、集成的、时变的、非易失

3、的数据集合，支持管理部门的决策过程。从一个或多个数据源收集信息，存放在一个一致的模式下，并且通常驻留在单个站点。数据仓库通过数据清理、变换、继承、装入和定期刷新过程来构造。 面向主题：排除无用数据，提供特定主题的简明视图。集成的：多个异构数据源。时变的：从历史角度提供信息，隐含时间信息。非易失的：和操作数据的分离，只提供初始装入和访问。联机事务处理OLTP：主要任务是执行联机事务和查询处理。联系分析处理OLAP：数据仓库系统在数据分析和决策方面为用户或知识工人提供服务。这种系统可以用不同的格式和组织提供数据。OLAP是一种分析技术，具有汇总、合并和聚集功能，以及从不同的角度观察信息的能力。特征

4、特征面向用户功能DB数据访问OLTP操作处理事务DBA，办事员日常操作基于ER当前最新读/写OLAP信息处理分析知识工人决策支持星型，雪花时间跨度读特征汇总用户操作访问记录优先DB规模度量OLTP原始，详细数千主码索引数十个高性能可用100mb-gb事务OLAP汇总，统一数百大量扫描数百万高灵活100gb-tb查询 多维数据模型:多维数据模型将数据看作数据立方体，允许从多个维度对数据建模和观察。包含维表和事实表。最流行的数据仓库数据模型是多维数据模型，这种模型可以是星形模式（事实表在中间，连接到多个维表）、雪花模式（星型的变种，某些维表规范化，分解到附加维表，以减少冗余）、事实星座模式（多个事

5、实表共享维表）。数据立方体：允许从多维对数据建模和观察。它由维和事实定义。维：关于一个组织想要保存记录的透视图和实体，每个维都有一个表与之相关联，成为维表。事实表：包括事实的名称和度量，以及每个相关维表的码。方体Cuboid：每个数据立方体。基本方体Base Cuboid：存放最底层汇总。顶点方体Apex Cuboid：最高层汇总，all。数据立方体Data Cube：给定维的集合，可以对维的每个可能子集产生一个方体。结果成为方体的格。多维数据立方体：提供数据的多维视图，并允许预计算和快速访问汇总数据。度量：数值函数，通过对给定点的各维-值对聚集数据，计算该点的度量值。概念分层：映射序列，将底

6、层概念映射到更一般的较高层概念。OLAP操作:上卷：上卷操作通过一个维的概念分层向上攀升或者通过维规约，在数据立方体上进行聚集。下钻：下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。切片和切块：切片对一个维进行选择。切块对两个以上维进行选择，定义子立方体。转轴：可视化操作，转动视角。钻过：跨越多个事实表。钻透：钻到后端关系表。数据仓库模型的不同类型：1、企业仓库：收集了关于跨部门的整个组织主题的所有信息，跨越整个组织，因此是企业范围的。2、数据集市：是企业仓库的一个部门子集，它针对选定的主题，对于特定的用户是有用的，因此是部门范围的，其数据通常是汇总的。3、虚拟仓库：虚拟仓库是操作数据库

7、上视图的集合，易于建立，但需要操作数据库服务器具有剩余能力。数据仓库的三层结构：1、仓库数据服务器：使用后端工具（抽取、清晰、转换、装载、刷新）和实用程序由操作数据库和其他外部数据源提取数据，进行数据清理和变换并放入仓库底层2、OLAP服务器：直接实现对多维数据的操作,直接为商务用户提供来自数据仓库或数据集市的多维数据。ROLAP:多维数据操作映射到标准关系操作。MOLAP：多维数据视图映射到数组中.HOLAP:结合，历史数据ROLAP,频繁访问数据放到MOLAP.3、前端客户层：包括查询和报表工具、分析工具或数据挖掘工具。数据仓库的设计：1、分析建立企业模型并映射到数据仓库概念模型；2、逻辑

8、模型的设计3、物理模型的设计OLAP建模：维表设计（维的变化，维表的共享，层次信息和分类信息的位置）、事实表设计（事实表的特性，通用数据和专用数据事实表）逻辑模型设计：1、 系统数据量估算；2、 数据粒度的选择；3、 数据的分割（到各自的物理单元单独处理）4、 表的合理划分（字段的更新频率和访问频率不一样稳定性）5、 删除纯操作数据（“收款人”），增加导出字段（“销售总量”）元数据：描述数据的数据，定义数据仓库对象的数据。包括数据仓库的结构、操作元数据（数据血统、流通，监控信息）、用于汇总的算法、从操作环境到数据仓库的映射；关于系统性能的数据、商务元数据。部分物化：选择性预计算各种方体子集或子

9、立方体。冰山立方体：是一个数据立方体，只存放聚集值大于某个最小支持度阈值的立方体单元。数据立方体计算中多路数组聚集，多路计算BUC：bottom-up computation 自底向上构造，一种计算稀疏冰山立方体的算法。数据立方体允许以多维数据建模和观察，它由维和事实定义。维是关于一个组织想要记录的透视或实体，事实是数值度量的。物理模型的设计：1.确定数据的存储结构（并行RAID）2.索引策略（位图索引、连接索引）3.数据存储策略与性能优化（多路聚集优化、表的归并、分割表的存放、按列存储、存储分配优化）4.数据装载接口5.并行优化设计位图索引：在给定属性的位图索引中，属性的每一个值v都有一个位

10、向量，长度为记录的总数，如果数据表中给定行上该属性的值为v, 则在位图索引的对应行上标注该值的位为1，其余为0.，不适用于基数很大的属性。连接索引：传统的索引将给定列上的值映射到具有该值的行的列表上，连接索引登记来自关系数据库的两个关系的可连接行，对于维护来自可连接的关系的外码和与之匹配的主码的联系特别有用（事实表维表）。N维，且每个维有Li概念封层，可得到的立方体有多路数组聚集：是数据立方体的高效计算方式。使用多维数组作为基本数据结构，自底向上的、共享地计算完全数据立方体。使用数组直接寻址的典型MOLAP。方法：最大维在形成单块的平面上。最小为在形成单面的平面上，每个平面必须被排序，并按大小

11、递增的顺序被计算。数据预处理数据预处理：不完整的、含噪音的、不一致的1、数据清洗（缺失值（缺少属性值或某些感兴趣的属性，或仅包含聚集数据）、噪声（错误或存在偏离期望的离群值）、非一致）、2、数据集成（模式集成（识别实体）、发现冗余（相关分析检测）、数据值冲突检测和处理（不同数据源属性值不同）、3、数据变换（光滑（去掉噪声）、聚集（数据汇总）、泛化（概念分层，高层替换低层）、规范化（按比例缩放）、属性构造）4、数据规约（数据立方体聚集、维度规约(属性子集选择)、数值规约、离散化和概念分层产生）、5、数据离散化（数值数据：分箱、直方图、聚类、基于熵的离散化、基于直观划分离散化3-4-5规则（区间的

12、最高有效位的取值个数）；分类数据：用户或专家在模式级显示说明属性偏序、通过显示数据分组说明分层结构的一部分、说明属性集但不说明偏序（层次高，属性值个数越少）、只说明部分属性集（嵌入数据语义，是语义相关的属性集捆绑在一起）。噪声：被测量的变量的随机误差或方差。噪音数据处理：分箱（按箱平均值平滑、按箱中值平滑、按箱边界平滑）、回归、聚类。规范化：最小-最大规范化；Z-score规范化；小数定标规范化数据规约技术：得到数据集的规约显示，小得多，但保持原数据的完整性。挖掘更有效。属性子集选择：检测并删除不相关、弱相关或冗余的属性和维维规约：使用编码机制减小数据集的规模,如压缩。数值规约：用替代的、较小

13、的数据表示替换或估计数据，如参数模型or非参方法（聚类、抽样、直方图（Equi-depth、equi-width、v-optimal（最小方差）、maxdiff（考虑每对相邻的之间的差，桶的边界具有的最大对）。概念分层：对一个属性递归地进行离散化，产生属性值的分层或多分辨率划分。属性的原始数据用更高层或离散化的值替换。离散化：用少数区间标记替换连续属性的数值，从而减少和简化原来的数据。特征化和区分：描述性数据挖掘：以简洁概要的方式描述概念或数据集，并提供数据的有趣的一般性质。预测性数据挖掘：分析数据，建立一个或一组连续值函数模型，预测不知道的数值数据值。概念描述包括特征化和区分。特征化：提供给

14、定数据汇集的简洁汇总。区分：提供两个或多个数据集的比较描述。OLAP VS 概念描述：处理类型、自动化方面比较各自优缺点。 Concept description: u can handle complex data types of the attributes and their aggregationsu a more automated process OLAP: u restricted to a small number of dimension and measure typesu user-controlled process决策树：一种类似于流程图的树结构，其中每个结点代表在

15、一个属性值上的测试，每个分支代表测试的一个输出，而树叶代表类或类分布。数据泛化：将数据库中的大量任务相关数据从低概念层提升到更高概念层的过程。数据泛化途径：1、数据立方体（OLAP途径）2、面向属性的归纳面向属性的归纳：1、使用数据库查询收集任务相关的数据；2、考察相关任务集中的各个属性并进行泛化：通过属性删除（两种情况）或者属性泛化3、通过合并相等的广义元组（每个广义元组代表一个规则析取）并累计对应的计数值进行聚集面向属性归纳方法产生的泛化描述表现形式：广义关系（表）、交叉表、图、量化特征规则。属性泛化控制：属性泛化阈值控制（对所有的属性设置一个泛化阈值，或者对每个属性设置一个阈值。如果属性

16、的不同值个数大于属性泛化阈值，则应当进行进一步的属性删除或属性泛化）广义关系阈值控制：为广义关系设置一个阈值。如果广义关系中不同元组的个数超过该阈值，则当进一步泛化；否则，不再进一步泛化。特征化 VS OLAP: 相同点：在不同抽象层次数据汇总展示；迭代的上卷、下钻、旋转、切片/块。不同点：特征化：自动产生层次的分配；多个相关维时进行维的相关分析和排序；维和度量的类型可以很复杂量化规则：带有量化信息的逻辑规则解析特征化：1、收集任务相关数据2、根据属性分析阈值分析泛化（对目标类和对比类的候选关系）：属性删除、属性泛化、候选关系3、属性的相关性分析（信息增益）4、（去除不/弱相关，对比类的候选关

17、系）形成目标类的初始工作关系5、在初始工作关系上根据属性泛化阈值使用面向属性的归纳类对比：1、通过查询处理收集数据库中的相关数据集，并分别划分成目标类和一个或多个对比类。2、维相关分析（仅选择高度相关的维进一步分析，属性移除和泛化）3、同步泛化（目标类泛化到维阈值控制的层，对比类概念泛化到相同层）4、通过对目标类和对比类使用下钻、上卷和其他OLAP操作调整比较描述的抽象层次。5、导出比较的表示量化特征规则（必要）：T权：P-135，代表典型性量化判别规则（充分）：D权：p-138，代表和对比类比有多大差别（高D权：概念主要从目标类导出）量化描述规则(充分必要)：关联规则挖掘：关联规则挖掘：从操

18、作型数据库、关联数据库或者其他信息库中的项集、对象中，发现频繁模式、关联、相关或者因果结构。应用:Basket data analysis, cross-marketing, catalog design, loss-leader analysis, clustering, classification, etc.例子：Rule form: “Body Head support, confidence”.buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%

19、频繁项集：频繁地在事务数据集中一起出现的项的集合，满足最小支持度。支持度：规则X & Y Z的支持度，事务中包括X、Y、Z的概率。置信度：在X,Y存在的情况下，Z也在事务中的概率。两步过程：1、找出所有的频繁项集2、由频繁项集产生强关联规则Apriori 算法：该算法利用了频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:第一次扫描得到频繁项集的集合L0 ，第k趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选k项集的集合Ck，然后再通过扫描数据库确定C中每一候选k项集的支持数，最后在该次扫描结束时求出频繁k项集的集合Lk，算法的终止条件是Ck或Lk为空。如何通过

20、Lk-1找到Lk。使用候选产生发现频繁项集（1）连接步： Ck根据Lk-1与自身连接生成（2）剪枝步（子集测试）Ck是Lk的超集，扫描数据库，确定Ck中的每个候选的计数，剪去小于最小支持度的项集。Apriori 性质：频繁项集的所有非空子集也必须是频繁Apriori 核心：用k 项集生成k+1 项集；使用数据库扫描和模式匹配收集候选项集计数Apriori 瓶颈：候选项集计算量大尤其是1频繁项集自交叉生成2候选项集时；数据库多次扫描，每次抽取都要扫描由Apriori 产生频繁项集产生关联规则：由频繁项集直接产生强关联规则s-(l-s),s为l的非空子集提高Apriori 算法的效率：1、基于散列

21、的技术：一种基于散列的技术可以用于压缩候选k 项集Ck（eg:在C1中产生L1的过程中，可对每个事务产生所有的2项集，并将它们散列到散列表结构的不同桶中，并增加对应的桶计数，计数低于最小支持桶中的2项集应从2候选项集中删除）2、事务压缩：不包含任何K频繁项集的事务不可能产生K的FI应在后继的扫描中删除3、划分：任何频繁项集必须作为局部频繁项集至少出现在一个划分中。4、抽样：在样本上降低阈值5、动态项集计数：只有子项集都频繁才将其加入候选项集FP树：发现频繁项集而不产生候选；分治策略：首先将提供频繁项的数据库压缩到一棵FP树上，仍然保留项集相关信息。然后将压缩后的数据库划分为一组条件数据库，每个

22、关联一个频繁项或模式段，并分别挖掘每个条件数据库。FP核心：利用FP树递归地增长频繁模式路径（分治）FP优点：去除了不相关的信息；出去节点连接和计数规模比原数据库小；快速；将发现长频繁模式的问题转换成递归地搜索一些较短的模式。 Completeness:u never breaks a long pattern of any transactionu preserves complete information for frequent pattern mining Other advantages:u reduce irrelevant informationinfrequent items

23、 are goneu never be larger than the original database (if not count node-links and counts)u much faster than AprioriFP性能优于Apriori的原因：1、 没有候选的产生2、 采用紧凑的数据结构3、 消除了对数据库的重复扫描4、 基本的操作既是对FP的构建和计数提升度（lift）: ，=1表示A、B独立，1A、B正相关单维关联规则：包含单个谓词的关联规则。buys(X, “milk”) buys(X, “bread”)多维关联规则：一个以上属性或谓词之间的关联规则。维间关联规则：

24、具有名不重复谓词。混合关联规则：某些谓词重复出现。age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)多层关联规则：在多个抽象层上挖掘数据产生的关联规则。高层：milk bread 20%, 60%.底层：Sweet milk- wheat bread 6%, 50%.一致支持度(对于所有层使用一致的最小支持度)、递减支持度（在较低层使用递减的最小支持度）、基于分组的支持度（基于项或基于分组的最小支持度）分层独立策略：检查所有的节点而不考虑其父节点是否频繁分类和预测：分类：找出描述并区分数据类或概念的模型，以便能够使用模型预测未知对象类的类

25、标记，模型的构建依赖于训练集和分类属性的类标号的使用。预测：建立连续值函数模型，预测某些空缺的或不知道的数据值而不是类标记。从数据分析的角度来看监督学习（分类）：提供了每个训练元组的类标号，未知元组通过由训练元组构造的模型来定性类标号的预测非监督学习（聚类）：每个训练元组的类标号是未知的，并且要学习的类的个数或集合也可能事先不知道，力求寻找类或聚类的存在。 Typical Applicationsu credit approvalu target marketingu medical diagnosisu treatment effectiveness analysis测试集来评估模型的正确性

26、决策树：一种类似于流程图的树结构，其中每个结点代表在一个属性值上的测试，每个分支代表测试的一个输出，而树叶代表类或类分布。决策树算法：Basic algorithm (a greedy algorithm)自顶向下、递归、分治的贪心策略：1、Tree is constructed in a top-down recursive divide-and-conquer manner2、At start, all the training examples are at the root3、Attributes are categorical (if continuous-valued, they

27、are discretized in advance)4、Examples are partitioned recursively based on selected attributes5、Test attributes are selected on the basis of a heuristic or statistical measure (e.g., information gain)结束条件：1、 所有的样本都属于同一个类2、 没有剩余的样本可用3、 没有剩余的属性用来划分（投票）避免过度拟合： The generated tree may overfit the trainin

28、g data u Too many branches, some may reflect anomalies due to noise or outliersu Result is in poor accuracy for unseen samples前剪枝（在构造过程中，预定义阈值，如果分裂低于阈值，提前停止树的构造。一旦停止，该节点成为树叶。） VS 后剪枝（构造完成，由完全生长的树剪去子树，用其子树中最频繁的类标记替换。）：贝叶斯：概率学习、增量、概率预测、标准，可以解决不可见样本问题sample X ，class label C 寻找使 P(C|X)最大的X朴素假设：类条件独立P(x1

29、,xk|C) = P(x1|C)P(xk|C)，当出现新的独立类时可在原基础上直接计算，即增量神经网络：一组连接的输入输出单元，每个连接都有一个权重与之相关联，在学习阶段通过调整这些权重能够预测输入元组的正确类标号。后向传播(图)：初始化权重向前传播输入向后传播误差调整权值终止条件终止：超过预先指定的周期数；前一周期的权值调整小于预定值/误分的百分比小于预定值。后向传播算法：1. 将从输入层进过隐藏层到达输出层，得到网络预测值。2. 计算出网络预测与实际已知目标的差值（error）3. 将error从输出层后向传播到隐藏层4. 修改权重和偏值，使得预测网络值和实际目标值的军方误差最小5. 如果

30、满足标准则停止，否则从循环到step1。后向传播：通过迭代地处理一组训练样本，将每个样本的网络预测与实际知道的类标号比较，进行学习。对于每个训练样本，修改权，使得网络预测和实际类之间的均方误差最小，这种修改“后向”进行。向前传播输入：计算隐藏层和输出层每个单元的净输入和输出。向后传播误差：通过更新权和偏置以反映网络预测的误差，向后传播误差。急切学习法：在接收待分类的新元组之前构造分类模型。懒惰学习法：给定训练元组时，只是简单存储，并一直等到待检验元组出现才进行泛化，比便根据存储的训练元组的相似性对元组进行分类。1、K-近邻 找到最接近未知元组的K个训练元组2、基于案例推理粗糙集：基于等价类的建

31、立，给定类的粗糙集定义用两个集合近似：上近似，不能认为不属于C的集合；下近似：必定属于C的集合。分类精度高，处理离散属性。模糊集：对每个类定义“模糊”的阈值和边界，模糊逻辑0-0.1之间的真值表示一个特定的值是一个给定类成员的隶属程度，而不是用精确的截断，每个类表示一个模糊集。分类正确性的验证：划分（独立的训练集和测试集，大规模）；交叉验证（K个子样本集，中等规模，k-1个训练集，1个验证集）分类和预测的组装方法：装袋：对训练集有放回随机抽样产生N个训练子集，导出N个模型，对未知数据，给出对应的N个结果。每个分类器投出一票，统计得票，将得票最高的类赋予X。分类-多数表决；预测-均值提升：对训练

32、集有放回随即抽样产生N个训练子集，导出N个模型。每个训练元组都赋予一个权重。对每个训练元组从1-N模型迭代地进行，重整每个元组的权重；使得在下一轮更关注上一轮误分的元组，并计算每个模型的投票权重。分类返回具有最大权重的类聚类挖掘：聚类：要划分的类是未知的，将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。General Applications： Pattern Recognition Spatial Data Analysis Image Processing Economic Science (especially market researc

33、h) WWWu Document classificationu Cluster Weblog data to discover groups of similar access patterns划分方法：K-均值：以K为输入参数，将对象分为K个簇，是簇内，簇外1、随机选择K个对象作为K个簇的中心2、选择离K最近的点形成簇3、根据簇中的点计算新的均值，这个均值可以看做簇的中心OR质心4、以新的中心更新簇，从步骤2开始重复直到簇不再变化优点：相对可伸缩，有效率；往往终止局部最优解；缺点：需要用户给出K；对分类属性的数据均值无定义；对噪声和离群点敏感；不适合凹形；Applicable only w

34、hen mean is defined, then what about categorical data?K-中心点算法：簇的中心必须落在某个实在的点上，对噪声不敏感。确定N个对象的K各划分，随机选择k个初始代替代表对象代表，其余的每个对象聚类到与其最相似的代表对象所在的簇。然后反复地试图选择簇的更好的代表对象（用代价函数计算聚类的质量，代表对象被误差更小的对象）。层次方法：凝聚的（开始每个对象形成单独的组，然后逐次合并相近的对象或组，直到所有组合并成一个或满足终止条件）；分裂的（开始所有对象置于一个簇，每次迭代分裂成更小的簇，知道每个对象在一个簇中或满足终止条件）；优点：在运行中可随时停止

35、，不要K参数；缺点：不可回溯基于密度的方法：只要邻域中的密度（数据点的数目）大于每个阈值，就继续聚类。优点：1、发现任意形状的簇；2、处理噪声；3、一次扫描；4、需要密度参数作为终止条件；DBSCAN：（具有噪声的基于密度的聚类应用）密度可达和密度相连 (这个可能要考)1、 邻域2、 核心对象（对象的eps邻域至少包含minpts的对象，成为核心对象）3、 直接密度可达：p从q直接密度可达：如果q为核心对象且p在q的eps邻域4、 密度可达：如果对象链Pi+1是从Pi关于E和MINPTS直接密度可达的，p1=q,pn=p,则对象p从q关于E和MINPTS密度可达的。5、 密度相连：p,q都是从

36、o关于E和MINPTS密度可达的，则p到q是关于密度相连的。基于密度的簇是基于密度可达性的最大密度相连对象的集合，不包含在簇中的认为是噪声（MINPTS的限制不可能成为核心对象）。离群点：与数据的一般行为或模型不一致。 Problemu Find top n outlier points Applications:u Credit card fraud detectionu Telecom fraud detectionu Customer segmentationu Medical analysis1、 基于统计分布：例如正态分布的3以外的区域2、 基于距离：阈值1：D; 阈值2：水平eg:95%到其他点的距离有大于95%的大于D，则认为是离群点3、基于偏差：它通过检查一组对象的主要特征来识别离群点，背离这种对象的被认为是离群点。10