从数据挖掘到深度学习

从数据挖掘到深度学习——大数据建模分析的算法和应用概述刘豫2016-3-25提纲概述大数据建模分析算法和应用数据挖掘算法简介深度学习算法简介大数据分析工具关于网管大数据分析的思考实现基础：数据库、数据仓库、分布式存储、并行计算、流式计算、GPU加速……大数据建模分析的理论和方法2020/5/6如果数据是21世纪最宝贵的财富，大数据分析就是当今最伟大的炼金术，可以从前所未有的大规模数据中发现前所未知的知识，实现不可限量的价值。大数据分析依赖的理论和方法主要包括传统的统计学、机器学习、数据挖掘，以及近10年来逐渐发展成熟的深度学习。统计学机器学习数据挖掘深度学习提供特征和模型重要的发展分支提供数据分析技术基础实现对海量数据的明确可预期的分析能力算法可解析，物理意义清晰实现对海量数据的超越预期的分析能力算法多为启发式的，难以分析和理解人工学习特征人工学习规律人工学习特征自动学习规律自动学习特征自动学习规律关于特征、规律和学习2020/5/6大数据建模分析的本质是通过构建数学模型，从数据中学习特征和规律，收获有用的知识。特征：决定数据对象所蕴含的知识的关键属性规律：将特征的表达为目标知识的一种模式，及其参数学习：从样本数据集计算得到规律的过程原始数据特征规律训练数据测试数据学习目标函数标签数据标签数据测试验证输出参数优化目标建模流程验证流程可选流程贝叶斯决策树神经网络SVMKNNK-Means……最小二乘极大似然梯度下降BP算法EM算法……大数据建模分析的基本流程关于学习2020/5/6学习能力是大数据分析建模的关键技术之一。根据反馈的不同，学习技术可以分为监督学习（Supervisedlearning）、非监督学习（Unsupervisedlearning）、半监督学习（Semi-supervisedlearning）和强化学习（Reinforcementlearning）四大类。•使用有标签数据进行学习•典型场景：分类、回归监督学习（Supervisedlearning）•使用无标签数据进行学习•典型场景：聚类非监督学习（Unsupervisedlearning）•使用数据的一部分是有标签的，另一部分没有标签，无标签数据的数量有标签数据数量•典型场景：海量数据分类半监督学习（Semi-supervisedlearning）•使用无标签但有反馈的数据进行学习•典型场景：策略推理强化学习（Reinforcementlearning）半监督（Semi-supervised)学习案例步骤一:用带有标识的图片训练分类器步骤二:对没有标识的数据进行分类，并按照信任度从大到小进行排序步骤三:将信任度最高的图片自动加入标识项步骤四:重新训练分类器并重复步骤二~步骤四图片分类案例：从图库中识别出“日蚀”图片。当图库巨大时，人工标注耗时耗力。提纲概述大数据建模分析算法和应用数据挖掘算法简介深度学习算法简介大数据分析工具关于网管大数据分析的思考数据挖掘的概念和历史1960s1970sand80s1990s2000s--•DataCollection•DatabaseCreation•RelationalDataModel•RDBMS•DataMining•DataWarehouse•MultimediaDatabase•WebDatabase•Streamdatamanagementandmining•Webtechnology(XML,dataintegration)SAS研究所（1997）：“在大量相关数据基础之上进行数据探索和建立相关模型的先进方法”Bhavani（1999）：“使用模式识别技术、统计和数学技术，在大量的数据中发现有意义的新关系、模式和趋势的过程”Handetal（2000）：“数据挖掘就是在大型数据库中寻找有意义、有价值信息的过程”JiaweiHan(韩家炜)（2000）：从海量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中、人们事先不知道的、但又潜在有用的信息和知识的过程--《数据挖掘:概念与技术》数据挖掘定义的发展数据挖掘（DataMining）一词是在1989年8月召开的第十一届国际联合人工智能学术会议（JCAI’89）上正式形成的，其根源可追溯到经典统计学、人工智能、机器学习三个学科，关系型数据库、互联网的广泛应用两次推动了数据挖掘技术的发展。9主要的数据挖掘算法广义型知识•反映同类事物共同性质的知识特征型知识•反映事物各方面的特征知识差异型知识•反映不同事物之间属性差别的知识关联型知识•反映事物之间依赖或关联的知识预测型知识•根据历史和当前数据推测未来数据偏离型知识•揭示事物偏离常规的异常现象分类•按照分析对象的属性、特征，建立不同的组类来描述事物聚类•识别出内在的规则，按照这些规则把对象分成若干类关联规则•关联是某种事物发生时其他事物会发生的这样一种联系时序预测•把握分析对象发展的规律，对未来的趋势做出预见异常检测•对分析对象的少数极端的特例的描述，揭示内在的原因随着数据挖掘应用多年来不断的扩展和深化，产生积累了大量的数据挖掘算法。根据应用场景及目标的不同，可以将数据挖掘算法分为如下几类。分类算法单一的分类方法主要包括：决策树、贝叶斯、神经网络、K-近邻、支持向量机分类等集成学习算法：组合单一分类方法如Bagging和Boosting等分类算法需要对训练数据集进行标识、即事先确定好类别，属于监督学习分类算法的应用场景：解决各种模式识别问题图库软件的图片分类新闻网站的话题分类银行贷款客户的风险分类医院对患者病因的分类分类的目的是根据数据集的特点构造一个分类器，把未知类别的样本映射到给定类别中的某一个。分类算法：贝叶斯贝叶斯贝叶斯（Bayes）分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯（NaiveBayes）算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别由于贝叶斯定理的成立本身需要一个很强的条件独立性假设，而此假设在实际情况中经常是不成立的，其分类准确性就会下降为此，出现了许多降低独立性假设的贝叶斯分类算法，如TAN（TreeAugmentedNaiveBayes)算法，可以考虑属性间的关联性P(A|B)=P(B|A)*P(A)/P(B)贝叶斯公式：分类应用：P(类别|样本)=P(样本|类别)*P(类别)=ΠP（样本各属性|类别）*P(类别)分类算法：KNNk-近邻(kNN，k-NearestNeighbors)k-近邻算法是一种基于实例的分类方法该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数分类算法：SVM支持向量机支持向量机（SVM，SupportVectorMachine）是Vapnik根据统计学习理论提出的一种新的学习方法SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题SVM一般只能用在二类问题，对于多类问题效果不好示例一示例二分类算法：决策树决策树决策树是用于分类的主要技术，是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则构造决策树的目的是找出属性和类别间的关系，用来预测将来未知类别的记录的类别它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处决策树模型的缺点：处理缺失数据时的困难过度拟合问题忽略数据集中属性之间的相关性聚类算法划分法(partitioningmethods)给定一个有N个元组或者纪录的数据集，划分法将构造K个分组，每一个分组就代表一个聚类，KN对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好同一分组中的记录越近越好，而不同分组中的纪录越远越好使用划分法思想的算法有：K-MEANS、K-MEDOIDS、CLARANS密度法(density-basedmethods)密度法它不是基于各种各样的距离的，而是基于密度的克服基于距离的算法只能发现“类圆形”的聚类的缺点指导思想只要一个点所属区域的密度大过某个阈值，就把它加到与之相近的聚类中去代表算法有：DBSCAN、OPTICS、DENCLUE等层次法(hierarchicalmethods)将数据转换为树形结构，实现不同层次上的聚类模型法（model-basedmethods）对于每个类假定一个分布模型，试图找到每个类最好的模型混合高斯模型GMM聚类算法的任务是将相似的事物分成一类，不依赖于事先确定好的组别，属于无监督学习。聚类算法根据设计思想的不同主要有如下几种。聚类算法：K-Means和K-MedoidsK-Meansk-Means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。k-Means算法流程：首先从n个数据对象任意选择k个对象作为初始聚类中心而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）不断重复这一过程直到标准测度函数开始收敛为止一般都采用均方差作为标准测度函数K-Means的缺点：产生类的大小相差不会很大，对于脏数据很敏感K-MEDOIDS对K-Means改进：选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类在K-means中，中心点取为当前cluster中所有数据点的平均值在K-medoids算法中，从当前cluster中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点聚类算法：高斯混合模型GMMGMM将k个高斯模型混合在一起，每个点出现的概率是几个高斯混合的结果假设有K个高斯分布，每个高斯对数据点的影响因子为πk，数据点为x，高斯参数为thetaEM（expectationmaximization）算法对产生样本数据的最大似然实现各个高斯模型估计GMM可以给出每个数据属于各个类型的概率，可以对non-spherical数据进行聚类缺点是计算量大，不保证全局最优聚类算法：DBSCANDBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)几个定义：Ε领域：给定对象半径为Ε内的区域称为该对象的Ε领域；核心对象：如果给定对象Ε领域内的样本点数大于等于MinPts，则称该对象为核心对象；直接密度可达：对于样本集合D，如果样本点q在p的Ε领域内，并且p为核心对象，那么对象q从对象p直接密度可达。密度可达：对于样本集合D，给定一串样本点