数据挖掘-数据挖掘综述-基础知识和概念总结
数据挖掘-数据挖掘综述-基础知识和概念总结
目录
1.数据挖掘的发展历史
1.1 20世纪60年代及更早
数据挖掘还处于数据收集和数据库创建阶段，此时还只能处理一些非常原始的数据文件。
1.2 20世纪70年代到80年代初期
出现了数据库管理系统，诞生了层次，网状数据库系统，关系数据库系统，可以利用一些工具进行数据的查询和控制。
这个时期的经典算法：
1）广义线性模型：研究响应值的非正态分布以及非线性模型的线性转化。
2）EM算法：从非完全数据集中对参数进行MLE估计。
1.3 20世纪80年代
在高级数据库系统的基础上，出现了数据仓库与OLAP。其中1989 年在美国底特律召开的第 11 届国际人工智能联合会议的专题讨论会上，KDD被提出。KDD的出现标志着数据挖掘变成了计算机的一个十分重要的研究领域。
这个时期的经典算法：
1）支持向量机SVM算法：主要应用于小样本，非线性及高维模式识别，函数拟合。
2）神经网络：机器学习的初步尝试。
3）Bootstrap:在已知数据的基础上，模拟N无穷大时的情况，通过重抽样的方法扩充数据量。
4）ID3算法：经典的分类算法。
1.4 20实际90年代
OLAP与数据仓库技术的突飞猛进使得多次的数据回溯和动态处理变得简单，人们可以用数据来获取知识，数据挖掘进入了数据仓库决策与支持阶段。
这个时期的经典算法：
1）序列模式挖掘： the GSP algorithm
2）项集挖掘：the Apriori algorithm， the AprioriTID algorithm， the FP-Growth algorithm
3）关联规则挖掘： an algorithm for mining all association rules in a transaction database
4）时间序列挖掘 ：an algorithm for converting a time series to a sequence of symbols using the SAX representation of time series.
1.5 20世纪90年代到现在
出现了WEB数据库，随着技术的发展，大数据及分布式更是得到了极大的推广。一些机器学习，深度学习中的复杂算法越来越多的被应用到了数据挖掘中。
这个时期的经典算法类型：
1）Graph Mining
2）High-Utility Pattern Mining
3）Text mining
4）Stream mining
5）Episode Mining
6）Periodic Pattern Mining
2.数据挖掘专业术语列表
|
序号 |
中文 |
英文 |
|
1 |
数据挖掘 |
Data mining |
|
2 |
大数据 |
Big data |
|
3 |
项集挖掘 |
Itemset mining |
|
4 |
序列模式挖掘 |
Sequential Pattern Mining |
|
5 |
时间序列 |
Time series |
|
6 |
深度学习 |
Deep learning |
|
7 |
智能运维 |
AIOPs |
|
8 |
自动化运维 |
Devops |
|
9 |
机器学习 |
Machine learning |
|
10 |
故障预测 |
Failure predict |
|
11 |
异常检测 |
Anomaly detection |
|
12 |
文本挖掘 |
Text mining |
|
13 |
数据仓库 |
Data warehouse |
|
14 |
关联规则挖掘 |
Association Rule Mining |
3 数据挖掘介绍
3.1 数据挖掘概念
3.1.1 数据挖掘定义
数据挖掘（ Data mining）就是对观测到的数据集(经常是很庞大的)进行分析，目的是发现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。即数据挖掘是指从大量数据中提取或“挖掘”知识，也叫做数据中的知识发现。
3.1.2 数据挖掘特点
观察到的数据/大量的数据/发现知识，发现未知的规律。数据挖掘是一门跨学科的技术。统计学、数据库技术、机器学习、模式识别、人工智能、可视化技术等。通过数据挖掘过程所推导出的关系和摘要被称为模型（model）或(模式pattern)，如线形方程、规则、聚类（cluster）、图、树结构以及用时间序列表示的循环模式。模式：是指一系列的时间或特征，它们按照一定的规律发生，因此是可预测的。一旦某个模式被识别了，就可以设计解释和预测模式的规则。
3.1.3 什么样的数据能被挖掘
数据挖掘能被应用于任何对目标应用有意义的数据类型。最基本的形式有：数据库数据、数据仓库数据、交易事务数据，以及一些其他的类型，例如数据流、序列数据、图数据、空间数据、文本数据、多媒体数据等。
3.1.4数据来源
关系数据库；数据仓库：从多个数据源收集的信息存储，存放在一个一致的模式下；事务数据库：事务号及项列表，如超市一个客户所购物品为一个事务；时间数据库：有时间戳；时间序列数据库：存放随时间变化的值的序列，如股票交易数据；
3.1.5 数据仓库
数据仓库是多种数据来源的信息仓库，以统一的模式存放，通常是在一个站点。数据仓库通过一系列的数据清洗、聚合、转换、加载和周期性的更新构建。数据仓库以重要的主题组织，从历史的视角提供信息，常常是概要型的。数据仓库模型是高维数据结构，每一维对应于相应的一个或者一组属性。称为数据立方。通过提供高维数据视角和概要数据，数据仓库为OLAP联机处理提供支持。高维数据挖掘以OLAP的方式在高维空间挖掘。
3.1.6 什么样的模式能被挖掘
数据挖掘任务可以被归类为两种类别：描述性的和预测性的。描述性的挖掘任务是描述目标数据集的数据属性。预测性的挖掘任务是归纳现有数据以用来做预测。
3.1.7 数据描述
数据描述是总结目标类别数据的一般特征。
描述可以通过：（1）通过总结目标类别的一般术语进行数据特征化；（2）把目标类别和一个或一组对比类别做比较的数据区分；（3）同时使用上面2种方法有多种数据描述的方法。可以使用基于统计测量和散点图的简单数据总结。基于数据立方的OLAP操作可以使用在特定维度空间的用户控制的数据摘要。面向属性的归纳技术也可以用来描述数据。
3.1.8 数据区分
数据区分是比较目标类别数据对象和一个或者一组对象的一般特征。
3.1.9 频繁模式
频繁模式，含义是数据中经常发生的模式。包括频繁项集，频繁序列，频繁子结构。频繁项集指的是在交易数据集中经常同时发生的商品。频繁序列，比如顾客先买了笔记本电脑，再买了数码相机，接着买了内存卡，这是一个序列模式。频繁子结构指的是结合项集或者子序列的不同的结构形式（图、树、或者格）。挖掘频繁模式，会发现有趣的数据之间的关联和相关度。
3.1.10 用于预测分析的分类和回归
主要技术如：分类规则、决策树、神经网络等。
分类是找到模型可以描述和区分数据类别或者概念的方法。模型从一系列的训练数据中分析获得，用于预测未知类别的数据标签。
回归是连续值模型，预测缺失的数值型数据而非分类标签。
相关性分析是在分类和回归之前的步骤，我们需要选择那些属性跟分类和回归的过程显著相关。不相关的属性不被包含在考虑之列。
3.1.11聚类分析
聚类分析针对没有标签的数据进行。基于最大化类别内部的相似度，最小化类别之间的相似度的原则来分组。
3.1.12 离群点分析
数据集可能包含不遵守一般行为和模型的数据。这些目标称为离群点。检测离群点可以使用统计检验方法、距离测量、或者基于密度的方法。
3.1.13 有趣的模式
一个模式是有趣的有如下几个条件：1）能很容易被人理解 2）对于新的或者测试数据以一定的确信度也是合理的3）潜在有用的
4）新奇的
一些有关模式是否有趣的客观测量方法如：关联规则挖掘的客观衡量是规则的支持度，表示给定的规则在交易数据库中所占的百分比。另一个是置信度，表示关联规则的确定程度。一般来说，每一个有趣程度的测量方法都有一个用户能控制的阀值。另一种客观的有趣度的衡量包括精确度和覆盖率。主观的有趣度的衡量基于用户对数据的看法。如果模式是没有预料到的或者提供了可以指导用户行为的策略，则认为这些模式是有趣的。
3.1.14 数据挖掘能产生所有有趣的模式吗？
这是数据挖掘的完整性问题。答案是，数据挖掘系统产生所有可能的模式是不现实和不高效的。一个数据挖掘系统能只产生有趣的模式吗？这是数据挖掘的优化问题。只产生有趣的模式是会高度令人满意的。因为对于用户和挖掘系统来说，不需要从生成的模式中鉴别是否有趣，因此是很高效的。但是，虽然这方面研究有进展，但优化问题仍然是一个挑战性的问题。
3.2 数据挖掘的系统结构图
数据挖掘系统结构图
3.3数据挖掘的具体步骤：
1）数据清理（消除噪声和不一致数据）
2）数据集成（不同来源与格式的数据组合到一起）
3）数据选择（挖掘所需的数据）
4）数据变换（数据变换成适合挖掘的形式，如汇总，聚集操作）
5）数据挖掘（方法，建模）
6）模式评估（结果模型）
7）知识表示（可视化）
4.数据挖掘必读经典著作
|
序号 |
书名 |
作者 |
出版年代 |
出版社 |
|
1 |
数据挖掘导论 |
Pang-Ning Tan |
2006年 |
人民邮电出版社 |
|
3 |
数据挖掘概念与技术 |
Jiawwei Han ， Micheline Kamber Jian Pei |
2012年 |
机械工业出版社 |
|
4 |
机器学习 |
周志华 |
2016年 |
清华大学出版社 |
|
5 |
大数据时代的算法 |
刘凡平 |
2017年 |
电子工业出版社 |
|
6 |
统计学方法 |
李航 |
2012年 |
清华大学出版社 |
|
7 |
推荐系统实践 |
项亮 |
2012年 |
人民邮电出版社 |
5 十八大经典数据挖掘算法
【注解】：前10个是数据挖掘十大经典算法
1）C4.5 ：C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法。
2）k-means ：把样本或者实例中N个点划分到k个聚类中，使得每个点都属于离他最近的均值对应的聚类，以之作为聚类的标准。
3）SVM：支持向量机。它是一种监督式学习的方法，它广泛应用于统计分类以及回归分析中。 支持向量机属于一般化线性分类器。
4)Apriori【3】: Apriori算法是进行关联规则挖掘频繁项集的算法。核心步骤包括候选项集的产生和候选项集的剪枝。
5)EM：最大期望算法又称期望最大化算法，在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。
6)PageRank：网页排名是一种由搜索引擎根据网页之间相互的超链接计算的技术。
7)AdaBoost：AdaBoost方法是机器学习中的一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。
8)KNN：K最近邻分类算法，算法的思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。
9)Naive Bayes：贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。
10)CART：分类回归树，属于一种决策树。用于决策分类。
11）HITS算法：HITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念。
12）BIRCH算法：BIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看作数据的多层压缩。
13）GSP算法：GSP算法是序列模式挖掘算法。GSP算法也是Apriori类算法，在算法的过程中也会进行连接和剪枝操作，不过在剪枝判断的时候还加上了一些时间上的约束等条件。
14）PreFixSpan算法：PreFixSpan算法是另一个序列模式挖掘算法，在算法的过程中不会产生候选集，给定初始前缀模式，不断的通过后缀模式中的元素转到前缀模式中，而不断的递归挖掘下去。
15）CBA算法：CBA算法是一种集成挖掘算法，因为他是建立在关联规则挖掘算法之上的，在已有的关联规则理论前提下，做分类判断，只是在算法的开始时对数据做处理，变成类似于事务的形式。
16）RoughSets算法：粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。
17）gSpan算法：gSpan算法属于图挖掘算法领域，主要用于频繁子图的挖掘。
18）FP-Tree算法【4】：这个算法也有被称为FP-growth算法，这个算法克服了Apriori算法的产生过多侯选集的缺点，通过递归的产生频度模式树，然后对树进行挖掘。
6. 数据挖掘之频繁项集挖掘介绍
6.1 频繁项集基础知识介绍
项集：最基本的模式是项集，它是指若干个项的集合。频繁模式是指数据集中频繁出现的项集、序列或子结构。
频繁项集是指支持度大于等于最小支持度(minsup)的集合。其中支持度是指某个集合在所有事务中出现的频率。
置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。频繁项集挖掘有两篇非常经典的论文。一篇是Rakesh Agrawal ; Ramakrishnan Srikant在1994年发表的Fast Algorithms for Mining Association Rules，另外一篇是JIAWEI HAN; JIAN PEI; YIWEN YIN; RUNYING MAO在2004年发表的Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach。
6.2.Apriori 算法介绍
对于Apriori算法，我们使用支持度作为我们判断频繁项集的标准。Apriori算法的目标是找到所有的K项频繁集。
Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。Apriori算法流程：
6.3 fp-tree算法介绍
为了减少I/O次数，FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分，如下图所示：
FP树结构图
第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数，按照次数降序排列。第二部分是FP Tree，它将我们的原始数据集映射到了内存中的一颗FP树。第三部分是节点链表。所有项头表里的1项频繁集都是一个节点链表的头，它依次指向FP树中该1项频繁集出现的位置。
有了项头表和排序后的数据集，我们就可以开始FP树的建立了。开始时FP树没有数据，建立FP树时我们一条条的读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。
我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。
FP Tree算法流程：
1）扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。
2）扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。
3）读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。
4）从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。
5）如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集
7.数据挖掘之序列模式挖掘介绍
序列模式挖掘是数据挖掘中的一个重要研究领域，是指从庞大的事务记录中寻找出具有一定发生顺序的频繁事件序列。目前序列模式挖掘已经广泛应用与DNA序列分许、顾客购物行为分析、网站访问规律分析以及网络行为规律分析等领域。例如大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目，如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有征对性的营销措施。序列模式挖掘比较经典的算法是gsp算法。
gsp算法基本思路：