数据挖掘概念复习.docx
《数据挖掘概念复习.docx》由会员分享，可在线阅读，更多相关《数据挖掘概念复习.docx（19页珍藏版）》请在冰点文库上搜索。
数据挖掘概念复习
数据挖掘：
是从大量数据中发现有趣（非平凡的、隐含的、先前未知、潜在有用）模式，这些数据可以存放在数据库，数据仓库或其他信息存储中。
挖掘流程：
（1）学习应用域
（2）目标数据创建集（3）数据清洗和预处理（4）数据规约和转换（5）选择数据挖掘函数（总结、分类、回归、关联、分类）（6）选择挖掘算法（7）找寻兴趣度模式（8）模式评估和知识展示（9）使用挖掘的知识
概念/类描述：
一种数据泛化形式，用汇总的、简洁的和精确的方法描述各个类和概念，通过
（1）数据特征化：
目标类数据的一般特性或特征的汇总；
（2）数据区分：
将目标类数据的一般特性与一个或多个可比较类进行比较；（3）数据特征化和比较来得到。
关联分析：
发现关联规则，这些规则展示属性-值频繁地在给定数据集中一起出现的条件，通常要满足最小支持度阈值和最小置信度阈值。
分类：
找出能够描述和区分数据类或概念的模型，以便能够使用模型预测类标号未知的对象类，导出的模型是基于训练集的分析。
导出模型的算法：
决策树、神经网络、贝叶斯、（遗传、粗糙集、模糊集）。
预测：
建立连续值函数模型，预测空缺的或不知道的数值数据集。
孤立点：
与数据的一般行为或模型不一致的数据对象。
聚类：
分析数据对象，而不考虑已知的类标记。
训练数据中不提供类标记，对象根据最大化类内的相似性和最小化类间的原则进行聚类或分组，从而产生类标号。
第二章数据仓库
数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程。
从一个或多个数据源收集信息，存放在一个一致的模式下，并且通常驻留在单个站点。
数据仓库通过数据清理、变换、继承、装入和定期刷新过程来构造。
面向主题：
排除无用数据，提供特定主题的简明视图。
集成的：
多个异构数据源。
时变的：
从历史角度提供信息，隐含时间信息。
非易失的：
和操作数据的分离，只提供初始装入和访问。
联机事务处理OLTP：
主要任务是执行联机事务和查询处理。
联系分析处理OLAP：
数据仓库系统在数据分析和决策方面为用户或‘知识工人’提供服务。
这种系统可以用不同的格式和组织提供数据。
OLAP是一种分析技术，具有汇总、合并和聚集功能，以及从不同的角度观察信息的能力。
特征
特征
面向
用户
功能
DB
数据
访问
OLTP
操作处理
事务
DBA，办事员
日常操作
基于ER
当前最新
读/写
OLAP
信息处理
分析
知识工人
决策支持
星型，雪花
时间跨度
读
特征
汇总
用户
操作
访问记录
优先
DB规模
度量
OLTP
原始，详细
数千
主码索引
数十个
高性能可用
100mb-gb
事务
OLAP
汇总，统一
数百
大量扫描
数百万
高灵活
100gb-tb
查询
多维数据模型:
多维数据模型将数据看作数据立方体，允许从多个维度对数据建模和观察。
包含维表和事实表。
最流行的数据仓库数据模型是多维数据模型，这种模型可以是星形模式（事实表在中间，连接到多个维表）、雪花模式（星型的变种，某些维表规范化，分解到附加维表，以减少冗余）、事实星座模式（多个事实表共享维表）。
数据立方体：
允许从多维对数据建模和观察。
它由维和事实定义。
维：
关于一个组织想要保存记录的透视图和实体，每个维都有一个表与之相关联，成为维表。
事实表：
包括事实的名称和度量，以及每个相关维表的码。
方体Cuboid：
每个数据立方体。
基本方体BaseCuboid：
存放最底层汇总。
顶点方体ApexCuboid：
最高层汇总，all。
数据立方体DataCube：
给定维的集合，可以对维的每个可能子集产生一个方体。
结果成为方体的格。
多维数据立方体：
提供数据的多维视图，并允许预计算和快速访问汇总数据。
度量：
数值函数，通过对给定点的各维-值对聚集数据，计算该点的度量值。
概念分层：
映射序列，将底层概念映射到更一般的较高层概念。
OLAP操作:
上卷：
上卷操作通过一个维的概念分层向上攀升或者通过维规约，在数据立方体上进行聚集。
下钻：
下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。
切片和切块：
切片对一个维进行选择。
切块对两个以上维进行选择，定义子立方体。
转轴：
可视化操作，转动视角。
钻过：
跨越多个事实表。
钻透：
钻到后端关系表。
数据仓库模型的不同类型：
1、企业仓库：
收集了关于跨部门的整个组织主题的所有信息，跨越整个组织，因此是企业范围的。
2、数据集市：
是企业仓库的一个部门子集，它针对选定的主题，对于特定的用户是有用的，因此是部门范围的，其数据通常是汇总的。
3、虚拟仓库：
虚拟仓库是操作数据库上视图的集合，易于建立，但需要操作数据库服务器具有剩余能力。
数据仓库的三层结构：
1、仓库数据服务器：
使用后端工具（抽取、清晰、转换、装载、刷新）和实用程序由操作数据库和其他外部数据源提取数据，进行数据清理和变换并放入仓库底层
2、OLAP服务器：
直接实现对多维数据的操作,直接为商务用户提供来自数据仓库或数据集市的多维数据。
ROLAP:
多维数据操作映射到标准关系操作。
MOLAP：
多维数据视图映射到数组中.HOLAP:
结合，历史数据ROLAP,频繁访问数据放到MOLAP.
3、前端客户层：
包括查询和报表工具、分析工具或数据挖掘工具。
数据仓库的设计：
1、分析建立企业模型并映射到数据仓库概念模型；
2、逻辑模型的设计
3、物理模型的设计
OLAP建模：
维表设计（维的变化，维表的共享，层次信息和分类信息的位置）、事实表设计（事实表的特性，通用数据和专用数据事实表）
逻辑模型设计：
1、系统数据量估算；
2、数据粒度的选择；
3、数据的分割（到各自的物理单元单独处理）
4、表的合理划分（字段的更新频率和访问频率不一样——稳定性）
5、删除纯操作数据（“收款人”），增加导出字段（“销售总量”）
元数据：
描述数据的数据，定义数据仓库对象的数据。
包括数据仓库的结构、操作元数据（数据血统、流通，监控信息）、用于汇总的算法、从操作环境到数据仓库的映射；关于系统性能的数据、商务元数据。
部分物化：
选择性预计算各种方体子集或子立方体。
冰山立方体：
是一个数据立方体，只存放聚集值大于某个最小支持度阈值的立方体单元。
数据立方体计算中多路数组聚集，多路计算
BUC：
bottom-upcomputation
自底向上构造，一种计算稀疏冰山立方体的算法。
数据立方体允许以多维数据建模和观察，它由维和事实定义。
维是关于一个组织想要记录的透视或实体，事实是数值度量的。
物理模型的设计：
1.确定数据的存储结构（并行RAID）2.索引策略（位图索引、连接索引）
3.数据存储策略与性能优化（多路聚集优化、表的归并、分割表的存放、按列存储、存储分配优化）4.数据装载接口5.并行优化设计
位图索引：
在给定属性的位图索引中，属性的每一个值v都有一个位向量，长度为记录的总数，如果数据表中给定行上该属性的值为v,则在位图索引的对应行上标注该值的位为1，其余为0.，不适用于基数很大的属性。
连接索引：
传统的索引将给定列上的值映射到具有该值的行的列表上，连接索引登记来自关系数据库的两个关系的可连接行，对于维护来自可连接的关系的外码和与之匹配的主码的联系特别有用（事实表——维表）。
N维，且每个维有Li概念封层，可得到的立方体有
多路数组聚集：
是数据立方体的高效计算方式。
使用多维数组作为基本数据结构，自底向上的、共享地计算完全数据立方体。
使用数组直接寻址的典型MOLAP。
方法：
最大维在形成单块的平面上。
最小为在形成单面的平面上，每个平面必须被排序，并按大小递增的顺序被计算。
数据预处理
数据预处理：
不完整的、含噪音的、不一致的
1、数据清洗（缺失值（缺少属性值或某些感兴趣的属性，或仅包含聚集数据）、噪声（错误或存在偏离期望的离群值）、非一致）、
2、数据集成（模式集成（识别实体）、发现冗余（相关分析检测）、数据值冲突检测和处理（不同数据源属性值不同））、
3、数据变换（光滑（去掉噪声）、聚集（数据汇总）、泛化（概念分层，高层替换低层）、规范化（按比例缩放）、属性构造）
4、数据规约（数据立方体聚集、维度规约（属性子集选择）、数值规约、离散化和概念分层产生）、
5、数据离散化（数值数据：
分箱、直方图、聚类、基于熵的离散化、基于直观划分离散化3-4-5规则（区间的最高有效位的取值个数）；
分类数据：
用户或专家在模式级显示说明属性偏序、通过显示数据分组说明分层结构的一部分、说明属性集但不说明偏序（层次高，属性值个数越少）、只说明部分属性集（嵌入数据语义，是语义相关的属性集捆绑在一起））。
噪声：
被测量的变量的随机误差或方差。
噪音数据处理：
分箱（按箱平均值平滑、按箱中值平滑、按箱边界平滑）、回归、聚类。
规范化：
最小-最大规范化；Z-score规范化；小数定标规范化
数据规约技术：
得到数据集的规约显示，小得多，但保持原数据的完整性。
挖掘更有效。
属性子集选择：
检测并删除不相关、弱相关或冗余的属性和维
维规约：
使用编码机制减小数据集的规模,如压缩。
数值规约：
用替代的、较小的数据表示替换或估计数据，如参数模型or非参方法（聚类、抽样、直方图（Equi-depth、equi-width、v-optimal（最小方差）、maxdiff（考虑每对相邻的之间的差，桶的边界具有<桶数-1>的最大对））。
概念分层：
对一个属性递归地进行离散化，产生属性值的分层或多分辨率划分。
属性的原始数据用更高层或离散化的值替换。
离散化：
用少数区间标记替换连续属性的数值，从而减少和简化原来的数据。
特征化和区分：
描述性数据挖掘：
以简洁概要的方式描述概念或数据集，并提供数据的有趣的一般性质。
预测性数据挖掘：
分析数据，建立一个或一组连续值函数模型，预测不知道的数值数据值。
概念描述包括特征化和区分。
特征化：
提供给定数据汇集的简洁汇总。
区分：
提供两个或多个数据集的比较描述。
OLAPVS概念描述：
处理类型、自动化方面比较各自优缺点。
Conceptdescription:
◆canhandlecomplexdatatypesoftheattributesandtheiraggregations
◆amoreautomatedprocess
OLAP:
◆restrictedtoasmallnumberofdimensionandmeasuretypes
◆user-controlledprocess
决策树：
一种类似于流程图的树结构，其中每个结点代表在一个属性值上的测试，每个分支代表测试的一个输出，而树叶代表类或类分布。
数据泛化：
将数据库中的大量任务相关数据从低概念层提升到更高概念层的过程。
数据泛化途径：
1、数据立方体（OLAP途径）2、面向属性的归纳
面向属性的归纳：
1、使用数据库查询收集任务相关的数据；
2、考察相关任务集中的各个属性并进行泛化：
通过属性删除（两种情况）或者属性泛化
3、通过合并相等的广义元组（每个广义元组代表一个规则析取）并累计对应的计数值进行聚集
面向属性归纳方法产生的泛化描述表现形式：
广义关系（表）、交叉表、图、量化特征规则。
属性泛化控制：
属性泛化阈值控制（对所有的属性设置一个泛化阈值，或者对每个属性设置一个阈值。
如果属性的不同值个数大于属性泛化阈值，则应当进行进一步的属性删除或属性泛化）广义关系阈值控制：
为广义关系设置一个阈值。
如果广义关系中不同元组的个数超过该阈值，则当进一步泛化；否则，不再进一步泛化。
特征化VSOLAP:
相同点：
在不同抽象层次数据汇总展示；迭代的上卷、下钻、旋转、切片/块。
不同点：
特征化：
自动产生层次的分配；多个相关维时进行维的相关分析和排序；维和度量的类型可以很复杂
量化规则：
带有量化信息的逻辑规则
解析特征化：
1、收集任务相关数据
2、根据属性分析阈值分析泛化（对目标类和对比类的候选关系）：
属性删除、属性泛化、候选关系
3、属性的相关性分析（信息增益）
4、（去除不/弱相关，对比类的候选关系）形成目标类的初始工作关系
5、在初始工作关系上根据属性泛化阈值使用面向属性的归纳
类对比：
1、通过查询处理收集数据库中的相关数据集，并分别划分成目标类和一个或多个对比类。
2、维相关分析（仅选择高度相关的维进一步分析，属性移除和泛化）
3、同步泛化（目标类泛化到维阈值控制的层，对比类概念泛化到相同层）
4、通过对目标类和对比类使用下钻、上卷和其他OLAP操作调整比较描述的抽象层次。
5、导出比较的表示
量化特征规则（必要）：
T权：
P-135，代表典型性
量化判别规则（充分）：
D权：
p-138，代表和对比类比有多大差别（高D权：
概念主要从目标类导出）
量化描述规则（充分必要）：
关联规则挖掘：
关联规则挖掘：
从操作型数据库、关联数据库或者其他信息库中的项集、对象中，发现频繁模式、关联、相关或者因果结构。
应用:
Basketdataanalysis,cross-marketing,catalogdesign,loss-leaderanalysis,clustering,classification,etc.
例子：
Ruleform:
“BodyHead[support,confidence]”.
buys（x,“diapers”）buys（x,“beers”）[0.5%,60%]
major（x,“CS”）^takes（x,“DB”）grade（x,“A”）[1%,75%]
频繁项集：
频繁地在事务数据集中一起出现的项的集合，满足最小支持度。
支持度：
规则X&YZ的支持度，事务中包括{X、Y、Z}的概率。
置信度：
在X,Y存在的情况下，Z也在事务中的概率。
两步过程：
1、找出所有的频繁项集2、由频繁项集产生强关联规则
Apriori算法：
该算法利用了频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:
第一次扫描得到频繁项集的集合L0，第k趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选k项集的集合Ck，然后再通过扫描数据库确定C中每一候选k项集的支持数，最后在该次扫描结束时求出频繁k项集的集合Lk，算法的终止条件是Ck或Lk为空。
如何通过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、基于散列的技术：
一种基于散列的技术可以用于压缩候选k项集Ck（eg:
在C1中产生L1的过程中，可对每个事务产生所有的2项集，并将它们散列到散列表结构的不同桶中，并增加对应的桶计数，计数低于最小支持桶中的2项集应从2候选项集中删除）
2、事务压缩：
不包含任何K频繁项集的事务不可能产生>K的FI应在后继的扫描中删除
3、划分：
任何频繁项集必须作为局部频繁项集至少出现在一个划分中。
4、抽样：
在样本上降低阈值
5、动态项集计数：
只有子项集都频繁才将其加入候选项集
FP树：
发现频繁项集而不产生候选；
分治策略：
首先将提供频繁项的数据库压缩到一棵FP树上，仍然保留项集相关信息。
然后将压缩后的数据库划分为一组条件数据库，每个关联一个频繁项或模式段，并分别挖掘每个条件数据库。
FP核心：
利用FP树递归地增长频繁模式路径（分治）
FP优点：
去除了不相关的信息；出去节点连接和计数规模比原数据库小；快速；将发现长频繁模式的问题转换成递归地搜索一些较短的模式。
Completeness:
◆neverbreaksalongpatternofanytransaction
◆preservescompleteinformationforfrequentpatternmining
Otheradvantages:
◆reduceirrelevantinformation—infrequentitemsaregone
◆neverbelargerthantheoriginaldatabase（ifnotcountnode-linksandcounts）
◆muchfasterthanApriori
FP性能优于Apriori的原因：
1、没有候选的产生
2、采用紧凑的数据结构
3、消除了对数据库的重复扫描
4、基本的操作既是对FP的构建和计数
提升度（lift）:
，=1表示A、B独立，<1A、B负相关，>1A、B正相关
单维关联规则：
包含单个谓词的关联规则。
buys（X,“milk”）buys（X,“bread”）
多维关联规则：
一个以上属性或谓词之间的关联规则。
维间关联规则：
具有名不重复谓词。
混合关联规则：
某些谓词重复出现。
age（X,”19-25”）occupation（X,“student”）buys（X,“coke”）
多层关联规则：
在多个抽象层上挖掘数据产生的关联规则。
高层：
milk–>bread[20%,60%].底层：
Sweetmilk->wheatbread[6%,50%].
一致支持度（对于所有层使用一致的最小支持度）、递减支持度（在较低层使用递减的最小支持度）、基于分组的支持度（基于项或基于分组的最小支持度）
分层独立策略：
检查所有的节点而不考虑其父节点是否频繁
分类和预测：
分类：
找出描述并区分数据类或概念的模型，以便能够使用模型预测未知对象类的类标记，模型的构建依赖于训练集和分类属性的类标号的使用。
预测：
建立连续值函数模型，预测某些空缺的或不知道的数据值而不是类标记。
从数据分析的角度来看
监督学习（分类）：
提供了每个训练元组的类标号，未知元组通过由训练元组构造的模型来定性类标号的预测
非监督学习（聚类）：
每个训练元组的类标号是未知的，并且要学习的类的个数或集合也可能事先不知道，力求寻找类或聚类的存在。
TypicalApplications
◆creditapproval
◆targetmarketing
◆medicaldiagnosis
◆treatmenteffectivenessanalysis
测试集来评估模型的正确性
决策树：
一种类似于流程图的树结构，其中每个结点代表在一个属性值上的测试，每个分支代表测试的一个输出，而树叶代表类或类分布。
决策树算法：
Basicalgorithm（agreedyalgorithm）自顶向下、递归、分治的贪心策略：
1、Treeisconstructedinatop-downrecursivedivide-and-conquermanner
2、Atstart,allthetrainingexamplesareattheroot
3、Attributesarecategorical（ifcontinuous-valued,theyarediscretizedinadvance）
4、Examplesarepartitionedrecursivelybasedonselectedattributes
5、Testattributesareselectedonthebasisofaheuristicorstatisticalmeasure（e.g.,informationgain）
结束条件：
1、所有的样本都属于同一个类
2、没有剩余的样本可用
3、没有剩余的属性用来划分（投票）
避免过度拟合：
Thegeneratedtreemayoverfitthetrainingdata
◆Toomanybranches,somemayreflectanomaliesduetonoiseoroutliers
◆Resultisinpooraccuracyforunseensamples
前剪枝（在构造过程中，预定义阈值，如果分裂低于阈值，提前停止树的构造。
一旦停止，该节点成为树叶。
）VS后剪枝（构造完成，由完全生长的树剪去子树，用其子树中最频繁的类标记替换。
）：
贝叶斯：
概率学习、增量、概率预测、标准，可以解决不可见样本问题
sampleX，classlabelC寻找使P（C|X）最大的X
朴素假设：
类条件独立P（x1,…,xk|C）=P（x1|C）·…·P（xk|C），当出现新的独立类时可在原基础上直接计算，即增量
神经网络：
一组连接的输入输出单元，每个连接都有一个权重与之相关联，在学习阶段通过调整这些权重能够预测输入元组的正确类标号。
后向传播（图）：
初始化权重——向前传播输入——向后传播误差——调整权值——终止条件
终止：
超过预先指定的周期数；前一周期的权值调整小于预定值/误分的百分比小于预定值。
后向传播算法：
1.将从输入层进过隐藏层到达输出层，得到网络预测值。
2.计算出网络预测与实际已知目标的差值（error）
3.将error从输出层后向传播到隐藏层
4.修改权重和偏值，使得预测网络值和实际目标值的军方误差最小
5.如果满足标准则停止，否则从循环到step1。
后向传播：
通过迭代地处理一组训练样本，将每个样本的网络预测与实际知道的类标号比较，进行学习。
对于每个训练样本，修改权，使得网络预测和实际类之间的均方误差最小，这种修改“后向”进行。
向前传播输入：
计算隐藏层和输出层每个单元的净输入和输出。
向后传播误差：
通过更新权和偏置以反映网络预测的误差，向后传播误差。
急切学习法：
在接收待分类的新元组之前构造分类模型。
懒惰学习法：
给定训练元组时，只是简单存储，并一直等到待检验元组出现才进行泛化，比便根据存储的训练元组的相似性对元组进行分类。
1、K-近邻找到最接近未知元组的K个训练元组
2、基于案例推理
粗糙集：
基于等价类的建立，给定类的粗糙集定义用两个集合近似：
上近似，不能认为不属于C的集合；下近似：
必定属于C的集合。
分类精度高，处理离散属性。
模糊集：
对每个类定义“模糊”的阈值和边界，模糊逻辑0-0.1之间的真值表示一个特定的值是一个给定类成员的隶属程度，而不是用精确的截断，每个类表示一个模糊集。
分类正确性的验证：
划分（独立的训练集和测试集，大规模）；交叉验证（K个子样本集，中等规模，k-1个训练集，1个验证集）
分类和预测的组装方法：
装袋：
对训练集有放回随机抽样产生N个训练子集，导出N个模型，对未知数据，给出对应的N个结果。
每个分类器投出一票，统计得票，将得票最高的类赋予X。
分类-多数表决；预测-均值
提升：
对训练集有放回随即抽样产生N个训练子集，导出N个模
升级会员 