大数据算法简介-课件.pptx
- 文档编号:18816926
- 上传时间:2023-12-09
- 格式:PPTX
- 页数:80
- 大小:13.12MB
大数据算法简介-课件.pptx
《大数据算法简介-课件.pptx》由会员分享,可在线阅读,更多相关《大数据算法简介-课件.pptx(80页珍藏版)》请在冰点文库上搜索。
,大数据算法介绍,BIGDATA,CONTENTS,大数据算法,1大数据挖掘算法概述,1.1数据挖掘概念,20世纪80年代末,数据挖掘(DataMining,DM)提出1989年,KDD名词正式开始出现1995年,“数据挖掘”流传,从科学定义分析,数据挖掘是从大量的、有噪声的、不完全的、模糊和随机数据中,提取出隐含在其中的、人们事先不知道的、具有潜在利用价值的信息和知识的过程从技术角度分析,数据挖掘利用一系列相关算法和技术,从大数据中提取出行业或公司所需要的、有实际价值知识的过程。
知识表示形式可以是概念、规律、规则与模式等准确地说,数据挖掘是整个知识发现流程中的一个具体步骤,也是知识发现过程中最重要的核心步骤,1大数据挖掘算法概述,1.2数据挖掘常用算法,1大数据挖掘算法概述,1.2数据挖掘常用算法,数据挖掘方法中的一种重要方法就是分类,在给定数据基础上构建分类函数或分类模型,该函数或模型能够把数据归类为给定类别中的某一种类别,这就是分类的概念,聚类也就是将抽象对象的集合分为相似对象组成的多个类的过程,聚类过程生成的簇称为一组数据对象的集合,关联规则属于数据挖掘算法中的一类重要方法,关联规则就是支持度与信任度分别满足用户给定阈值的规则,时间序列预测法是一种历史引申预测法,也即将时间数列所反映的事件发展过程进行引申外推,预测发展趋势的一种方法,分类,聚类,关联规则,时间序列预测,1大数据挖掘算法概述,1.3数据挖掘算法应用场景,按照数据挖掘的应用场景分类,数据挖掘的应用主要涉及通信、股票、金融、银行、交通、商品零售、生物医学、精确营销、地震预测、工业产品设计等领域,在这些领域众多数据挖掘方法均被广泛采用且衍生出各自独特的算法,1大数据挖掘算法概述,1.3数据挖掘算法应用场景,数据挖掘在电信行业的应用,数据挖掘广泛应用在电信行业,可以帮助企业制定合理的服务与资费标准、防止欺诈、优惠政策,为公司决策者提供可靠的决策依据,为市场营销、客户服务、全网业务、经营决策等提供有效的数据支撑,进一步完善了国内电信公司对省、市电信运营的指导,在业务运营中发挥重要的作用,从而为精细化运营提供技术与数据的基础,数据挖掘在商业银行中的应用,在美国银行业与金融服务领域数据挖掘技术的应用十分广泛,由于金融业务的分析与评估往往需要大数据的支撑,从中可以发现客户的信用评级与潜在客户等有价值的信息,可成功地预测客户的需求,1大数据挖掘算法概述,1.3数据挖掘算法应用场景,数据挖掘在信息安全中的应用,数据挖掘在科学探索中的应用,利用机器学习与数据挖掘等前沿技术与处理方法对入侵检测的数据进行自动分析,提取出尽可能多的隐藏安全信息,从中抽象出与安全有关的数据特征,从而能够发现未知的入侵行为。
数据挖掘技术可以建立一种具备自适应性、自动的、系统与良好扩展性的入侵检测系统,能够解决传统入侵检测系统适应性与扩展性较差的弱点,大幅度提高入侵检测系统效能,近年来,数据挖掘技术开始逐步应用到科学探索研究中。
例如使用概率论模型对蛋白质序列进行多序列联配建模特定数据挖掘技术研究基因数据库搜索技术在被认为是人类征服顽疾的最有前途的攻关课题“DNA序列分析”过程中,由于DNA序列的构成多种多样,数据挖掘技术的应用可以为发现疾病蕴藏的基因排列信息提供新方法,1大数据挖掘算法概述,1.4数据挖掘工具,根据适用的范围,数据挖掘工具分为两类:
专用挖掘工具专用数据挖掘工具针对某个特定领域的问题提供解决方案,在涉及算法的时候充分考虑数据、需求的特殊性通用挖掘工具对任何应用领域,专业的统计研发人员都可以开发特定的数据挖掘工具,1大数据挖掘算法概述,1.4数据挖掘工具,Weka,公开的数据挖掘工作平台,集成大量能承担数据挖掘任务的机器学习算法,包括对数据进行预处理、分类、回归、聚类、关联规则,以及交互式界面上的可视化,SPSS,SPSS采用类似Excel表格的方式输入与管理数据,数据接口较为通用,能方便地从其他数据库中读入数据。
突出的特点是操作界面友好,且输出结果美观,Clementine,Clementine提供出色、广泛的数据挖掘技术,确保用恰当的分析技术来处理相应的商业问题,以应对随时出现的问题,RapidMiner,RapidMiner并不支持分析流程图方式,当包含的运算符比较多时就不容易查看;具有丰富的数据挖掘分析和算法功能,常用于解决各种商业关键问题,CONTENTS,大数据算法,2分类算法,2.1分类算法简介,分类是一种重要的数据分析形式,根据重要数据类的特征向量值及其他约束条件,构造分类函数或分类模型(分类器),目的是根据数据集的特点把未知类别的样本映射到给定类别中数据分类过程主要包括两个步骤,即学习和分类,1.建立模型学习,2.分类,2分类算法,2.1分类算法简介,分类分析在数据挖掘中是一项比较重要的任务,目前在商业上应用最多。
分类的目的是从历史数据记录中自动推导出对给定数据的推广描述,学会一个分类函数或分类模型(也常称作分类器),该模型能把数据库中的数据项映射到给定类别中某一个类中。
为建立模型而被分析的数据元组形成训练数据集,由一组数据库记录或元组构成,每个元组是一个由有关字段(又称属性或特征)值组成的特征向量,此外,每一个训练样本都有一个预先定义的类别标记,由一个被称为类标签的属性确定。
一个具体样本的形式可表示为,其中表示字段值,C表示类别。
分类又称为有监督的学习,2分类算法,2.2贝叶斯决策与分类器,算法思想,贝叶斯学派思想可概括为:
先验概率+数据=后验概率我们在实际问题中需要得到的后验概率,可以通过先验概率和数据一起综合得到。
贝叶斯学派需要假设先验分布的模型,如正态分布,beta分布等。
这个假设一般没有特定依据,因此一直被频率学派认为很荒谬。
虽然难以从严密的数学逻辑里推出贝叶斯学派的逻辑,但是在很多实际应用中,贝叶斯理论很好用,比如:
垃圾邮件分类,文本分类。
2分类算法,2.2贝叶斯决策与分类器,算法流程,2分类算法,2.2.1相关基础数学知识,条件概率,事件A在另外一个事件B已经发生条件下的发生概率,称为在B条件下A的概率。
表示,联合概率,联合概率表示两个事件共同发生的概率。
A与B的联合概率表示为、或者,贝叶斯定理,贝叶斯定理用来描述两个条件概率之间的关系,例如,与根据乘法法则:
2分类算法,2.2.1相关基础数学知识,全概率公式,全概率公式将对复杂事件A的概率求解问题转化为在不同情况下发生的简单事件的概率的求和问题。
设构成一个完备事件组,即它们两两互不相容,其和为全集,且则事件A的概率为:
2分类算法,2.2.2贝叶斯分类实例,2分类算法,2.2.2贝叶斯分类流程-实例(1/2),离散数据案例,判断:
身高“高”,体重“中”,鞋码“中”,对应性别,A代表属性,C代表类别,贝叶斯公式可得,假设Ai相互独立,则P(A1A2A3|Cj)=P(A1|Cj)P(A2|Cj)P(A3|Cj)因此可以求出P(A1A2A3|C1)P(A1A2A3|C2)为男性概率较大,2分类算法,2.2.2贝叶斯分类流程-实例(1/2),连续数据案例,判断:
身高“180”,体重“120”,鞋码“41”,对应性别,A代表属性,C代表类别,贝叶斯公式可得,假设Ai相互独立,则P(A1A2A3|C1)=P(A1|C1)P(A2|C1)P(A3|C1)P(A1A2A3|C2)=P(A1|C2)P(A2|C2)P(A3|C2)因此可以求出P(A1A2A3|C1)=4.9169e-6P(A1A2A3|C1)=2.7244e-9为男性概率更大,2分类算法,2.3ID3、C4.5与C5.0算法,ID3算法,主要针对离散型属性数据,其后又不断的改进,形成C4.5。
C4.5在ID3基础上增加了队连续属性的离散化,C4.5,ID3算法的修订版,采用GainRatio来加以改进方法,选取有最大GainRatio的分割变量作为准则,避免ID3算法过度配适的问题,C5.0,C4.5算法的修订版,适用于处理大数据集,采用Boosting方式提高模型准确率,又称为BoostingTrees,在软件上计算速度比较快,占用的内存资源较少,2分类算法,2.3.1决策树,决策树(DecisionTree)模型,通过对训练样本学习,建立分类规则,依据分类规则,实现对新样本的分类,属于有监督式学习方法,有两类变量目标标量(输入变量)属性变量(输出变量),决策树模型和一般统计分类模型区别-决策树的分类是基于逻辑的,一般统计分类是基于非逻辑的,决策树模型特点决策树擅长处理非数值类型,与神经网络智能处理数值类型比较,免去很多数据预测处理工作每个决策都要求分组之间“差异最大”,各种决策树算法之间主要区别就是对“差异”衡量方式的区别,2分类算法,2.3.1C5.0(1/3)-算法思想,C5.0是经典决策树模型算法之一,可生成多分支决策树,目标变量为分类变量,C5.0可以生成决策树(DecisionTree)或者规则集(rulesets)C5.0模型能根据能带来的最大信息增益(Informationgain)的字段拆分样本第一次拆分确定样本的子集随后再次拆分,通常是根据另一个字段进行拆分,这一过程重复进行直到样本子集不能再被拆分为止最后,重新检验最低层次的拆分,那些对模型没有显著贡献的样本子集被剔除或者修剪,2分类算法,2.3.2C5.0(2/3)-算法原理,2分类算法,2.3.2C5.0(2/3)-算法原理,2分类算法,2.3.3C5.0(3/3)-算法实例,2分类算法,2.4SVM(1/3)-算法思想,支持向量机(SupportVectorMachine)建立在统计学习理论VC维理论和结构风险最小原理基础上,根据有限样本信息在模型复杂性(对特定训练样本的学习精度,Accuracy)和学习能力(无错误地识别任意样本的能力)之间寻求最佳折中,以期获得最好泛化能力。
SVM基本任务。
找到一个能够让两类数据都离超平面很远的超平面,在分开数据的超平面的两边建有两个互相平行的超平面。
分隔超平面使两个平行超平面的距离最大化,平行超平面间的距离或差距越大,分类器的总误差越小,2分类算法,2.4SVM(2/3)-算法流程,2分类算法,2.4.1SVM(3/3)-算法原理,为了定义最佳超平面,我们需要最大化边距的宽度w,2分类算法,2.4.1SVM(3/3)-算法原理,我们发现w和b通过使用二次规划求解以下目标函数,SVM的美妙之处在于,如果数据是线性可分的,那么就有一个唯一的全局最小值。
然而,完全分离可能是不可能的,在这种情况下,SVM找到了最大化边际和最小化误分类的超平面,2分类算法,2.4.1SVM(3/3)-算法原理,SVM试图在最大化边距的同时将松弛变量保持为零。
然而,它并没有最小化误分类的数量,而是最小化了距边缘超平面的距离之和,2分类算法,2.4.1SVM(3/3)-算法原理,分离两组数据的最简单方法是使用直线(一维)、平面(二维)或N维超平面。
然而,在某些情况下,非线性区域可以更有效地分离这些组。
SVM通过使用核函数(非线性)将数据映射到一个不同的空间来处理这个问题,2分类算法,2.5分类算法应用:
在线广告推荐,互联网的出现和普及,带来的网上信息量的大幅增长,出现信息超载问题。
为了解决信息过载的问题,提出了很多解决方案,其中最具有代表性的解决方案是分类目录和搜索引擎,但是随着互联网规模的不断扩大,分类目录和搜索引擎,不能解决用户的需求。
推荐系统就是解决这一矛盾的重要工具,2分类算法,2.5分类算法应用:
在线广告推荐,推荐系统具有用户需求驱动、主动服务和信息个性化程度高等优点,可有效解决信息过载问题,推荐系统是一种智能个性化信息服务系统,可借助用户建模技术对用户的长期信息需求进行描述,并根据用户模型通过一定的智能推荐策略实现有针对性的个性化信息定制,能够依据用户的历史兴趣偏好,主动为用户提供符合其需求和兴趣的信息资源,2分类算法,2.5分类算法应用:
在线广告推荐,推荐系统利用推荐算法将用户和物品联系起来,能够在信息过载的环境中帮助用户发现令他们感兴趣的信息,也能将信息推送给对他们感兴趣的用户,根据已有用户注册信息和购买信息,使用朴素贝叶斯分类预测一个新注册用户购买计算机的可能性,从而向该用户推荐计算机类广告。
训练样本如下表所示,CONTENTS,大数据算法,3聚类算法,3.1聚类算法简介,聚类(clustering)将具体或抽象对象的集合分组成由相似对象组成的为多个类或簇的过程由聚类生成的簇是一组数据对象集合,簇必须同时满足以下两个条件:
每个簇至少包含一个数据对象;每个数据对象必须属于且唯一地属于一个簇聚类分析指用数学的方法来研究与处理给定对象的分类,主要是从数据集中寻找数据间的相似性,并以此对数据进行分类,使得同一个簇中的数据对象尽可能相似,不同簇中的数据对象尽可能相异,从而发现数据中隐含的、有用的信息,聚类过程,3聚类算法,3.2层次聚类算法,指导思想:
是对给定待聚类数据集合进行层次化分解。
此算法又称为数据类算法,此算法根据一定的链接规则将数据以层次架构分裂或聚合,最终形成聚类结果,层次聚类分为自顶而下的分裂聚类和自下而上的聚合聚类,分裂聚类:
初始将所有待聚类项看成同一类,然后找出其中与该类中其他项最不相似的类分裂出去形成两类。
如此反复执行,直到所有项自成一类,聚合聚类:
初始将所有待聚类项都视为独立的一类,通过连接规则,包括单连接、全连接、类间平均连接,以及采用欧氏距离作为相似度计算的算法,将相似度最高的两个类合并成一个类。
如此反复执行,直到所有项并入同一个类,典型代表算法:
BIRCH(BalancedIterativeReducingandClusteringUsingHierarchies),3聚类算法,3.3划分聚类算法,划分法属于硬聚类,指导思想是将给定的数据集初始分裂为K个簇,每个簇至少包含一条数据记录,然后通过反复迭代至每个簇不再改变即得出聚类结果,K-Means算法也称K-平均值算法或K均值算法,是一种得到广泛使用的聚类分析算法,常用聚类距离欧式距离曼哈顿距离,闵可夫斯基距离切比雪夫距离,3聚类算法,3.3.1K-Means(1/2)-算法思想,K-Means算法聚类问题经典算法,对于给定的样本集,按照样本间距离大小,将样本集划分为K个簇。
让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。
3聚类算法,3.3.1K-Means(2/2)-算法实例,3聚类算法,3.4基于密度聚类算法,DBSCANDBSCAN(Density-BasedSpatialClusteringofApplicationwithNoise,具有噪声的基于密度的空间聚类应用)是一种基于高密度连接区域的密度聚类算法,DBSCAN算法流程从任意对象P开始根据阈值和参数通过广度优先搜索提取从P密度可达的所有对象,得到一个聚类若P是核心对象,则可以一次标记相应对象为当前类并以此为基础进行扩展得到一个完整聚类后,再选择一个新对象重复上述过程。
若P是边界对象,则将其标记为噪声并舍弃,DBSCAN算法缺陷聚类的结果与参数关系较大:
阈值过大容易将同一聚类分割;阈值过小容易将不同聚类合并固定的阈值参数对于稀疏程度不同的数据不具适应性:
密度小的区域同一聚类易被分割;密度大的区域不同聚类易被合并,3聚类算法,3.5基于网格聚类算法,网格聚类算法采用一个多分辨率的网格数据结构,即将空间量化为有限数目的单元,这些单元形成了网格结构,所有的聚类操作都在网格上进行,经典算法介绍STING(STatisticalINformationGrid,统计信息网格)针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构高层的每个单元被划分为多个低一层的单元WaveCluster(Clusteringusingwavelettransformation,采用小波变换聚类)先通过在数据空间上加一个多维网格结构来汇总数据,然后采用一种小波变换来变换原特征空间,在变换后的空间中找到密集区域,3聚类算法,3.6基于模型聚类算法,模型聚类算法为每一个聚类假定了一个模型,寻找数据对给定模型的最佳拟合,经典算法介绍统计学方法(EM和COBWEB算法)概念聚类是机器学习中的一种聚类方法,给出一组未标记的数据对象,它产生一个分类模式。
概念聚类除了确定相似对象的分组外,还为每组对象发现了特征描述,即每组对象代表了一个概念或类概念聚类过程主要有两个步骤:
首先,完成聚类;其次,进行特征描述神经网络方法(SOM算法)神经网络方法将每个簇描述成一个模型,模型作为聚类的一个“原型”神经网络聚类的两种方法:
竞争学习方法与自组织特征图映射方法。
3聚类算法,3.8聚类算法应用:
海量视频检索,图像分割图像处理到图像分析的关键步骤,也是一种基本的计算机视觉技术。
图像分割是把图像分成每个区域并提取感兴趣目标的技术和过程。
颜色、灰度、纹理是比较常见和主要的特性,目标可以对应多个区域,也可以对应单个区域,主要与实际应用和目标有关,K-Means聚类算法简捷,具有很强的搜索能力,适合处理数据量大的应用场景,在数据挖掘和图像领域中得到了广泛的应用,CONTENTS,大数据算法,4关联规则算法,4.1关键规则算法简介,关联规则数据挖掘中最活跃的研究方法之一,是指搜索业务系统中的所有细节或事务,找出所有能把一组事件或数据项与另一组事件或数据项联系起来的规则,以获得存在于数据库中的不为人知的或不能确定的信息,它侧重于确定数据中不同领域之间的联系,也是在无指导学习系统中挖掘本地模式的最普通形式,应用市场:
市场货篮分析、交叉销售(CrossingSale)、部分分类(PartialClassification)、金融服务(FinancialService),以及通信、互联网、电子商务,4关联规则算法,4.1关键规则算法简介,关联规则概念一般来说,关联规则挖掘是指从一个大型的数据集(Dataset)发现有趣的关联(Association)或相关关系(Correlation),即从数据集中识别出频繁出现的属性值集(SetsofAttributeValues),也称为频繁项集(FrequentItemsets,频繁集),然后利用这些频繁项集创建描述关联关系的规则的过程,关联规则挖掘问题发现频繁项集发现所有的频繁项集是形成关联规则的基础。
通过用户给定的最小支持度,寻找所有支持度大于或等于Minsupport的频繁项集,生成关联规则通过用户给定的最小可信度,在每个最大频繁项集中,寻找可信度不小于Minconfidence的关联规则,核心问题:
如何迅速高效地发现所有频繁项集?
4关联规则算法,4.2频繁项集的产生及经典算法,格结构(LatticeStructure)常常被用来枚举所有可能的项集,4关联规则算法,4.2频繁项集的产生及经典算法,查找频繁项集经典算法,4关联规则算法,4.2.1Apriori(1/2)-算法思想与流程,算法思想,基于频繁项集性质的先验知识,使用由下至上逐层搜索的迭代方法,即从频繁1项集开始,采用频繁k项集搜索频繁k+1项集,直到不能找到包含更多项的频繁项集为止,算法流程,4关联规则算法,4.2.1Apriori(2/2)-算法实例,4关联规则算法,4.2.2FP-Growth(1/2)-算法思想与流程,算法思想,频繁模式树增长算法(FrequentPatternTreeGrowth)采用分而治之的基本思想,将数据库中的频繁项集压缩到一棵频繁模式树中,同时保持项集之间的关联关系。
然后将这棵压缩后的频繁模式树分成一些条件子树,每个条件子树对应一个频繁项,从而获得频繁项集,最后进行关联规则挖掘,算法流程,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,FP-growth算法需要对原始训练集扫描两遍以构建FP树。
第一次扫描:
过滤掉所有不满足最小支持度的项;对于满足最小支持度的项,按照全局最小支持度排序,第一次扫描,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,第二次扫描:
构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。
事务001,z,x,事务002,z,x,y,t,s,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,第二次扫描:
构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。
事务002,z,x,y,t,s,事务003,z,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,第二次扫描:
构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。
事务003,z,事务004,x,s,r,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,第二次扫描:
构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。
事务004x,s,r,事务005z,x,y,t,r,4关联规则算法,4.2.2FP-Growth(2/2)-算法实例,第二次扫描:
构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。
事务005z,x,y,t,r,事务006z,x,y,t,s,4关联规则算法,4.2.2Apriori与FP-Growth算法对比,4关联规则算法,4.3分类技术,分类技术或称作分类法(Classification)是一种根据输入样本集建立类别模型,并按照类别模型对未知样本类标号进行标记的方法,4关联规则算法,4.3.1决策树,决策树通过一系列规则对数据进行分类的过程,决策树分类步骤构造决策树修剪决策树,4关联规则算法,4.3.1决策树(1/2),构建决策树过程,根据实际需求选择类别标识属性和决策树的决策属性集在决策属性集中选择最有分类标识能力的属性作为决策树的当前决策节点根据当前决策节点属性取值的不同,将训练样本数据集划分为若干子集针对上一步中得到的每一个子集,重复进行以上两个步骤,直到最后的子集符合约束的3个条件根据符合条件不同生成叶子节点,4关联规则算法,4.3.1决策树(2/2),修剪决策树,对决策树进行修剪,除去不必要的分枝,同时也能使决策树得到简化,修剪策略基于代价复杂度的修剪悲观修剪最小描述长度修剪,修剪顺序先剪枝(Pre-pruning)后剪枝(Post-pruning),4关联规则算法,4.3.2k-最近邻(1/3)-算法思想和原理,算法思想,最临近分类基于类比学习,是一种基于实例的学习,它使用具体的训练实例进行预测,而不必维护源自数据的抽象(或模型),算法原理,采用n维数值属性描述训练样本,每个样本代表n维空间的一个点,即所有的训练样本都存放在n维空间中。
若给定一个未知样本,k-最近邻分类法搜索模式空间,计算该测试样本与训练集中其他样本的邻近度,找出最接近未知样本的k个训练样本,这k个训练样本就是未知样本的k个“近邻”,其中的“邻近度”一般采用欧几里得距离定义,4关联规则算法,4.3.2k-最近邻(2/3)-算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 算法 简介 课件