数据挖掘概念与技术.docx
《数据挖掘概念与技术.docx》由会员分享，可在线阅读，更多相关《数据挖掘概念与技术.docx（11页珍藏版）》请在冰点文库上搜索。
数据挖掘概念与技术
数据挖掘概念与技术
数据挖掘概念与技术
一.什么是数据挖掘，数据挖掘的知识体系及应用范围
1.定义：
又称数据中的知识发现，从大量的数据中挖掘有趣模式和知识的过程。
知识发现的过程：
1）.数据清理：
除噪声和删除不一致数据
2）.数据集成：
多种数据源的组合
3）.数据选择：
取和分析与任务相关的数据
4）.数据变换：
数据变换和统一成适合挖掘的形式
5）.数据挖掘：
使用智能方法提取数据格式
6）.模式评估：
识别代表知识的有趣模式
7）.知识表示：
使用可视化和知识表示技术，向用户提供挖掘的知识
2.为什么要进行数据挖掘
未来将是大数据时代，IDC（国际数据公司）研究报告指出2012年全球信息资料量为2.8ZB（2的40次方GB）,而在2020年预计会达到40ZB，平均每人拥有5247GB的数据。
庞大的数据量背后隐藏着巨大的潜在价值，人们手握巨量的数据却没有很好的手段去充分挖掘其中的价值，因此对数据挖掘的研究可以帮助我们将数据转化成知识。
3.数据挖掘的知识体系
二元属性：
只有0、1两种状态
序数属性：
可能的值具有有意义的序，如教师职称
数值属性：
定量的，用实数值表示
2.度量数据的相似性和相异性（即数据的邻近性）
非对称二元属性：
Jaccard属性
数值属性：
欧几里得距离、曼哈顿距离、闵可夫斯基距离、上确界距离
相似性评估：
余弦相似性（用于比较文档）、Tanimoto系数
3.数据预处理
1）.数据清理：
填补缺失值、光滑噪声、识别离群点、纠正数据不一致性，通常是一个两步迭代过程，包括偏差检测盒数据变换
处理缺失值：
有忽略元组、人工填写、全局常量填充、
均值或中位数填充、同类均值或中位数填充、最可能值填充六种方法。
噪声数据处理：
分箱（考察近邻数据值，有箱均值、箱中位数、箱边界光滑方法）
回归、离群点分析
2）.数据集成：
将来自多个数据源的数据整合成一致的数据存储
实体识别问题：
模式集成和对象匹配。
如在一个系统中discount用于订单，而在另一个系统中用于商品，集成不正确导致商品不正确打折
冗余和相关分析：
冗余指一个属性能由另一个或另一组属性导出，则这个属性是冗余的，可用相关分析检测到。
标称数据使用卡方检验，数值属性用相关系数和协方差
3）.数据规约：
简化数据集的表示，包括维规约和数值规约
维规约：
数据压缩技术（如小波变换和主成分分析），属性子集选择，属性构造
数值规约：
参数模型（如回归），非参数模型（聚类、抽样、直方图）
4）.数据变换：
将数据变换成适于挖掘的形式
变换策略包括：
光滑，属性构造，聚集，规范化，离散化，由标称数据产生概念分层。
三.数据仓库与数据立方体技术
1.数据仓库基本概念：
1）.数据仓库定义：
一个面向主题的、集成的、时变的、非易失的数据集合，支持管理者的决策过程。
2）.数据库与数据仓库的区别：
主要区别在于数据库是面向事务操作处理的，而数据仓库是面向分析信息处理的。
数据库的用户为数据库专业人员、处理日常操作，而数据仓库为主管和分析人员，为决策提供支持。
3）.数据仓库体系架构：
底层数据，中间层OLAP服务器，顶层前端工具
4）.数据仓库模型：
企业仓库：
提供企业范围内的数据集成，企业范围的
数据集市：
包含企业范围数据的一个子集，对特定的用户群，咸鱼选定的主题，部门范围的。
虚拟仓库：
操作数据库上视图的集合
2.数据仓库建模
数据立方体：
允许以多维数据建模和观察，由维（属性）和事实（数值）定义
方体：
给定诸维的每个可能的自己产生一个方体，结果形成方体的格，方体的格称作数据立方体。
多维模型：
星形模式：
包括一个大的中心表（事实表）、一组小的附属表（维表），维表围绕中心表
雪花模式：
是星形的表变种，某些维表被规范化费解到附加的表中，用于数据集市
事实星座：
多个事实表分享维表，用于复杂的应用，常用于企业数据仓库
3.典型OLAP操作：
上卷：
沿一个维的概念分层向上攀升或通过维规约进行聚集，如由city上卷到country
下钻：
沿维的概念分层向下或引入附加的维来实现，如由季度数据到更详细的月数据
切片：
在立方体的一个维上进行选择，定义一个子立方体，如选择季度一的数据
切块：
在立方体的两个或多个维上进行选择，定义子立方体，如选择季度为一和商品类型为计算机的数据
转轴：
转动数据视角，或将3D立方变换成2D平面序列
物化：
完全物化（完全立方体）：
计算定义数据立方体的格中所有的方体，需要过多存储空间，导致维灾难部分物化：
选择性计算子立方体
冰山立方体：
一个数据立方体，只存放其聚集值大于某个最小支持度阈值的立方体单元。
立方体外壳：
只预计算涉及少数维的方体，这些方体形成对应的数据立方体。
4.数据立方体的计算方法：
1）.多路数组聚焦：
基本思想：
使用多维数组作为基本数据结构，使用数组直接寻址，其中维值通过位置或对应数组位置的下标访问。
可能产生稀疏数组结构，可以采用chunkID+offset作为单元寻址机制来压缩数组。
优点：
比传统的基于关系记录的计算方法快
缺点：
因为维数增长，计算的方体数指数增长，因此该方法仅对具有较少维的立方体有效；
不能计算冰山立方体，因为该方法从基本方体开始计算，逐步向上泛化，因而不能利用先验剪枝，导致即时单元不满足冰山条件指定的最小支持度，也无法剪掉。
2）. BUC：
基本思想：
以相反的次序观察方体的格，顶点方体在底部，而基本方体在顶部，因而实际上市自底向上的，BUC可以分担数据划分开销，在构造立方体是可以使用先验性质进行剪枝。
优点：
可以计算冰山立方体，可以分担数据划分开销
缺点：
易受维的次序和倾斜数据影响。
理想地，应该先处理最有区分能力的为，维应当以基数递减序处理。
3）.Star-Cubing：
基本思想：
利用自底向上和自顶向下模式的计算模式。
在全局计算次序上，使用自底向上，而它下面有一个基于自顶向下模式的子层，利用共享维的概念。
这种集成允许算法在多个维上聚集，而仍然划分父母分组并剪裁不满足冰山条件的子女分组。
如果共享维上的聚集值不满足冰山条件，则沿共享维向下的所有单元也不满足冰山条件，这样的单元和它们所有的后代都可以剪枝。
优点：
计算完全立方体，速度比BUC快，可以与MultiWay相媲美；计算冰山立方体速度比BUC快。
4）.外壳片段立方体：
冰山立方体的计算和存储开销虽然比完全立方体小，但是仍然很高，一个可能的解决方案是计算一个很薄的立方体外壳，但是这种立方体外壳不支持高维OLAP，它不支持在4维或更多维上的OLAP，并且它甚至不支持沿3个维下钻，因此取代计算立方体外壳可以只计算它的一部分或片段。
外壳片段立方体基本思想：
给定一个高维数据集，把维划分成互不相交的维片段，把每个片段转换成倒排索引表示，构造立方体外壳片段，使用预计算立方体外壳片段，计算所需要的数据立方体的方体单元，这可以通过倒排索引上的集合交操作完成。
四.挖掘频繁模式、关联和相关性
1.基本概念
1）.一个典型例子：
购物篮分析
顾客可能会在一次购物同时购买哪些商品？
分析结果可以用于营销计划和商店布局。
2）.规则兴趣度的度量：
支持度和置信度
支持度：
两种商品同时被购买占事务总数的比例，反映发现该规则的有用性
置信度：
购买一个商品的顾客中同时购买另一个商品的顾客所占比例，反映规则的确定性。
项集：
项的集合，如集合{computer，antivirus_software}是一个2项集
支持度计数：
项集的事务数
频繁项集：
相对支持度满足最小支持度阈值的项集
闭频繁项集：
项集X在数据集D中是闭的，如果不存在真超项集Y使得Y与X在D中具有相同的支持度计数，如果X在D中是闭的和频繁的，则X是数据集的闭频繁项集。
极大频繁项集：
X是频繁的，并且不存在超项集Y使得Y在D中是频繁的。
关联规则的挖掘包含两步：
（1）.找出所有的频繁项集
（2）.由频繁项集产生强关联规则（同时满足最小支持度阈值和最小置信度阈值的规则）
2.频繁项集挖掘方法
可以分为三类：
类Apriori算法，基于频繁模式增长的算法（如FP-growth算法），使用垂直数据格式的算法
1）.Apriori算法（数据挖掘十大经典算法）
频繁项集先验性质：
频繁项集的所有非空子集也一定是频繁的。
基本思想：
使用逐层搜索的迭代方法，其中k项集用于探索（k+1）项集，使用先验性质压缩搜索空间。
如何使用L（k-1）找到L（k）:
通过连接步和剪枝步完成。
连接步通过将L（k-1）与自身连接产生候选k项集集合。
剪枝步从候选k项集确定L（k）。
提高Apriori算法效率：
基于散列的技术：
将事务产生的k项集散列到散列表的不同桶中，并增加相应桶计数，对应桶计数小于支持度阈值不可能是频繁的，可以从候选集中删除。
这一技术可以显著地压缩需要考察的k项集
事务压缩：
不包含任何频繁k项集的事务不可能包含任何频繁（k+1）项集，因此在其后的考虑时，可以加上标记或删除。
划分：
分两个阶段，阶段一把D划分成n个分区，找出每个分区的局部频繁项集，组合所有局部频繁项集形成候选项集；阶段二评估每个候选的实际支持度，找出候选项集中的全局频繁项集。
整个过程只需要两次数据库扫描。
抽样：
基本思想是选取数据库D的随机样本S，然后再S中搜索频繁项集。
这种方法牺牲了一些精度换取了有效性，可能会丢失一些全局频繁项集
动态项集计数：
基本思想是奖数据库划分为用开始点标记的块。
不像Apriori算法仅在每次完整的数据库扫描前确定新的候选，这种变形中，可以再任何开始点添加新的候选集。
该变形需要的数据库扫描笔Apriori算法少。
Apriori算法优缺点
优点：
显著压缩了候选项集的规模，产生很好的性能
缺点：
仍需要产生大量候选项集，需要重复扫描整个数据库
2）.频繁模式增长（FP-growth）
目标：
挖掘全部频繁项集而无需代价昂贵的候选产生过程
基本思想：
采取分治策略，首先将频繁项集的数据库压缩到一棵频繁模式树（FP树），该树仍保留项集的关联信息。
然后把压缩后的数据库划分成一组条件数据库，每个数据库关联一个频繁项或模式段，并分别挖掘每个条件数据库。
随着被考察模式的增长，这种方法显著地压缩被搜索的数据集的大小。
概括起来可分为构造FP树和挖掘FP树两个步骤。
当数据库很大时，构造的FP数可能太大而不能放进主存，可以递归地将数据库划分成投影数据库集合。
FP-growth方法对于挖掘长的频繁模式和短的频繁模式，都是有效的和可伸缩的，并且大约比Apriori算法快一个数量级。
3）.使用垂直数据格式挖掘频繁项集
Apriori算法和FP-growth算法都是使用水平数据格式，即{TID:
itemset}，其中TID为事务标识符，itemset是TID中购买的商品。
垂直数据格式：
{item:
TID}
基本思想：
通过扫描一次数据库，把水平格式的数据转换成垂直格式，根据先验性质，使用频繁k项集来构造候选k+1项集，通过去频繁k项集的TID集的交，计算对应k+1项集的TID集，重复该过程，知道不能找到频繁项集或候选项集。
优点：
利用先验性质，不需要扫描数据库来确定k+1项集的支持度。
缺点：
TID集可能很长，需要大量内存，长集合的交运算还需要大量的计算时间。
3.模式评估
并非所有强关联规则都是有趣的，比如项集计算机游戏和录像可能满足强关联规则，但是它们是负相关的。
提升度：
一种相关性的度量，结果值大于1是正相关，为1表示独立，小于1表示负相关。
相关性度量还有最大置信度和余弦。
五.挖掘频繁模式、关联和相关性
1.高级模式形式：
多层关联、多维关联、量化关联规则、稀有模式、负模式
2.基于约束的挖掘：
模式剪枝约束、数据剪枝约束
模式搜索空间剪枝：
检查候选模式，使用先验性质，剪掉一个模式，如果它的超模式都不可能产生。
数据搜索空间剪枝：
检查数据集，判断特定数据片段是否对其后的可满足模式产生有贡献。
模式剪枝约束分为五类：
反单调的：
如果一个项集不满足规则约束，则它的任何超集不可能满足该约束
单调的：
如果一个项集满足这个规则约束，则它的所有超集也满足。
简洁的：
可以枚举并且仅枚举可以确保该约束的所有集合，该类约束不必迭代检验
可转变的：
不属于以上三类，但该约束在项集一特定次序排列时可能成为单调的或反单调的。
不可转变的：
大部分都属于以上四类。
3.挖掘高维数据和巨型模式：
包括利用垂直数据格式扩充模式增长方法和模式融合方法。
垂直数据格式模式增长：
将具有较少行但具有大量维的数据集变换成具有大量航少量维的数据集。
模式融合：
基本思想：
融合少量较短的频繁模式，形成巨型模式候选。
首先，他以有限的宽度遍历树，只使用有限大小的候选池中的模式作为模式树向下搜索的开始结点，避免了指数搜索空间问题。
它产生巨型模式的近似解，可以找出大部分巨型模式。
步骤：
1.池初始化：
一个短长度（长度不超过3）频繁模式的完全集。
2.迭代的模式融合：
从当前池中随机选取k个种子，对每个种子找出直径为T的球内所有模式，将这些球融合成超模式集。
由于每个超模式的支集随迭代而收缩，因此迭代过程终止。
模式融合合并打魔石的小的子模式，而不是用单个项增量地扩展模式。
4.挖掘压缩或近似模式：
1.基于聚类的压缩：
采用一个好的相似性度量，把相似的对象聚合到一个簇中，代表模式从每个簇中选取，从而提供频繁模式集的一个压缩版本。
模式距离：
闭模式之间的距离度量。
包含模式的支持度信息。
感知冗余的top-k模式：
具有低冗余的k个代表模式的小集合。
一种减少挖掘返回的模式数量的策略。
5.模式挖掘的应用：
1）.作为预处理，用于噪声过滤盒数据清理
2）.发现隐藏在数据中的固有结构和簇
3）.基于模式的分类
4）.高维空间中子空间的有效聚类
5）.对时间空间、序列、图像、视频数据进行分析
6）.序列与结构数据的分析，如图、树、子序列和网络分析
7）.作为基本的索引结构
8）.推荐系统
升级会员 