大数据挖掘与算法课件.pptx

1、 大数据挖掘与算法第三章数据挖掘算法3.1数据挖掘概述3.2分类3.3聚类3.4关联规则3.5预测规模习题3.6数据挖掘算法综合应用of3923.1数据挖掘概述第三章 数据挖掘算法20世纪80年代末，数据挖掘（Data Mining，DM）提出。1989年，KDD 这个名词正式开始出现。1995年，“数据挖掘” 流传。从科学定义分析，数据挖掘是从大量的、有噪声的、不完全的、模糊和随机的数据中，提取出隐含在其中的、人们事先不知道的、具有潜在利用价值的信息和知识的过程。从技术角度分析，数据挖掘就是利用一系列的相关算法和技术，从大数据中提取出行业或公司所需要的、有实际应用价值的知识的过程。知识表示形

2、式可以是概念、规律、规则与模式等。准确地说，数据挖掘是整个知识发现流程中的一个具体步骤，也是知识发现过程中最重要的核心步骤。特征处理大数据的能力更强，且无须太专业的统计背景就可以使用数据挖掘工具数据挖掘的最终目的是方便企业终端用户使用，而并非给统计学家检测用的从使用与需求的角度上看，数据挖掘工具更符合企业界的需求of3933.1.1 数据挖掘概念3.1数据挖掘概述第三章 数据挖掘算法使用广义角度分类聚类估值预测关联规则数理基础角度机器学习方法统计方法神经网络方法决策树基于范例学习规则归纳遗传算法回归分析 时间序列分析 关联分析聚类分析粗糙集探索性分析支持向量机最近邻分析模糊集前向神经网络自组织

3、神经网络多层神经网络深度学习感知机可视化of3943.1.2 数据挖掘常用算法3.1数据挖掘概述第三章 数据挖掘算法1分类数据挖掘方法中的一种重要方法就是分类，在给定数据基础上构建分类函数或分类模型，该函数或模型能够把数据归类为给定类别中的某一种类别，这就是分类的概念。2聚类3关联规则4时间序列预测聚类也就是将抽象对象的集合分为相似对象组成的多个类的过程，聚类过程生成的簇称为一组数据对象的集合。关联规则属于数据挖掘算法中的一类重要方法，关联规则就是支持度与信任度分别满足用户给定阈值的规则。时间序列预测法是一种历史引申预测法，也即将时间数列所反映的事件发展过程进行引申外推，预测发展趋势的一种方法

4、。of3953.1.2 数据挖掘常用算法3.1数据挖掘概述第三章 数据挖掘算法按照数据挖掘的应用场景分类，数据挖掘的应用主要涉及通信、股票、金融、银行、交通、商品零售、生物医学、精确营销、地震预测、工业产品设计等领域，在这些领域众多数据挖掘方法均被广泛采用且衍生出各自独特的算法。1数据挖掘在电信行业的应用2数据挖掘在商业银行中的应用数据挖掘广泛应用在电信行业，可以帮助企业制定合理的服务与资费标准、防止欺诈、优惠政策，为公司决策者提供可靠的决策依据，为市场营销、客户服务、全网业务、经营决策等提供有效的数据支撑，进一步完善了国内电信公司对省、市电信运营的指导，在业务运营中发挥重要的作用，从而为精细

5、化运营提供技术与数据的基础。在美国银行业与金融服务领域数据挖掘技术的应用十分广泛，由于金融业务的分析与评估往往需要大数据的支撑，从中可以发现客户的信用评级与潜在客户等有价值的信息，可成功地预测客户的需求。of3963.1.3 数据挖掘应用场景3.1数据挖掘概述第三章 数据挖掘算法3数据挖掘在信息安全中的应用4数据挖掘在科学探索中的应用利用机器学习与数据挖掘等前沿技术与处理方法对入侵检测的数据进行自动分析，提取出尽可能多的隐藏安全信息，从中抽象出与安全有关的数据特征，从而能够发现未知的入侵行为。数据挖掘技术可以建立一种具备自适应性、自动的、系统与良好扩展性的入侵检测系统，能够解决传统入侵检测系统

6、适应性与扩展性较差的弱点，大幅度提高入侵检测系统的检测与响应的效能。近年来，数据挖掘技术已经开始逐步应用到科学探索研究中。例如，在生物学领域数据挖掘主要应用在分子生物学与基因工程的研究。 使用概率论模型对蛋白质序列进行多序列联配建模； 特定数据挖掘技术研究基因数据库搜索技术； 在被认为是人类征服顽疾的最有前途的攻关课题“DNA序列分析”过程中，由于DNA序列的构 成多种多样，数据挖掘技术的应用可以为发现疾病蕴藏的基因排列信息提供新方法。of3973.1.3 数据挖掘应用场景3.1数据挖掘概述第三章 数据挖掘算法根据适用的范围，数据挖掘工具分为两类：专用挖掘工具和通用挖掘工具。专用数据挖掘工具针

7、对某个特定领域的问题提供解决方案，在涉及算法的时候充分考虑数据、需求的特殊性。对任何应用领域，专业的统计研发人员都可以开发特定的数据挖掘工具。Weka软件SPSS软件Clementine软件RapidMiner软件其他数据挖掘软件SPSS采用类似Excel表格的方式输入与管理数据，数据接口较为通用，能方便地从其他数据库中读入数据。突出的特点是操作界面友好，且输出结果美观。Clementine提供出色、广泛的数据挖掘技术，确保用恰当的分析技术来处理相应的商业问题，得到最优的结果以应对随时出现的问题。RapidMiner并不支持分析流程图方式，当包含的运算符比较多时就不容易查看；具有丰富的数据挖掘

8、分析和算法功能，常用于解决各种商业关键问题。公开的数据挖掘工作平台，集成大量能承担数据挖掘任务的机器学习算法，包括对数据进行预处理、分类、回归、聚类、关联规则，以及交互式界面上的可视化。流行的数据挖掘软件还包括Orange、Knime、Keel与Tanagra等of3983.1.4 数据挖掘工具3.2分类3.1数据挖掘概述第三章数据挖掘算法3.3聚类3.4关联规则3.5预测规模习题3.6数据挖掘算法综合应用of3993.2 分类分类是一种重要的数据分析形式，根据重要数据类的特征向量值及其他约束条件，构造分类函数或分类模型（分类器），目的是根据数据集的特点把未知类别的样本映射到给定类别中。数据分

9、类过程主要包括两个步骤，即学习和分类。图3-1 建立一个模型第一步，建立一个模型第三章 数据挖掘算法of3910图3-2 使用模型进行分类3.2 分类第二步，使用模型进行分类第三章 数据挖掘算法of39113.2 分类分类分析在数据挖掘中是一项比较重要的任务，目前在商业上应用最多。分类的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个类中。为建立模型而被分析的数据元组形成训练数据集，由一组数据库记录或元组构成，每个元组是一个由有关字段（又称属性或特征）值组成的特征向量，此外，每一个训练样

10、本都有一个预先定义的类别标记，由一个被称为类标签的属性确定。一个具体样本的形式可表示为 ,其中 表示字段值，C 表示类别1,nXXCnX分类又称为有监督的学习第三章 数据挖掘算法of39123.2 分类1条件概率数学基础知识事件A 在另外一个事件B 已经发生条件下的发生概率，称为在B 条件下A 的概率。表示为|P A B |P ABP A BP B2联合概率联合概率表示两个事件共同发生的概率。 A 与B 的联合概率表示为 、 或者P AB,P A BP AB3贝叶斯定理贝叶斯定理用来描述两个条件概率之间的关系，例如， 与 。根据乘法法则 可以推导出贝叶斯公式：|P A B|P B A |P A

11、BP A P B AP B P A B |P A P B AP A BP B第三章 数据挖掘算法of39133.2.1 贝叶斯决策与分类器3.2 分类4全概率公式全概率公式为概率论中的重要公式，它将对复杂事件A 的概率求解问题转化为在不同情况下发生的简单事件的概率的求和问题。设 构成一个完备事件组，即它们两两互不相容，其和为全集，且 ，则事件A的概率为：1,nBB01,iP Bin 111|nnniiiP AP A BP BP A BP BP A BP B，贝叶斯分类的工作过程如下：（1）每个数据样本均是由一个n 维特征向量 表示，分别描述其n 个属性的具体取值。12,nx xxX12,nA

12、AA第三章 数据挖掘算法of39143.2.1 贝叶斯决策与分类器3.2 分类4全概率公式（2）假设共有m 个不同类别， 。给定一个未知类别的数据样本X（没有类别号），分类器预测属于X 后验概率最大的那个类别。也就是说，朴素贝叶斯分类器将未知类别的样本X 归属到类别 ，当且仅当 。也就是 最大。其中类别 就称为最大后验概率的假设。根据贝叶斯公式可得：（3）由于 对于所有的类别均是相同的，因此，只需要 取最大即可。由于类别的先验概率是未知的，则通常假定类别出现概率相同，即 。这样对于式（3-4）取最大转换成只需要求 最大。而类别的先验概率一般可以通过 公式进行估算，其中， 为训练样本集合中类别

13、的个数，s 为整个训练样本集合的大小。12,mC CCiC|,1,ijP CXP CXjm ji |iP CXiCP X|iiP X CP C12mP CP CP C（3-4） |iP X CiisPCsisiC第三章 数据挖掘算法of39153.2.1 贝叶斯决策与分类器3.2 分类4全概率公式（4）根据所给定包含多个属性的数据集，直接计算 的运算量非常大。为实现对的有效估算，朴素贝叶斯分类器通常都假设各类别是相互独立的，即各属性间不存在依赖关系，其取值是相互独立的。可以根据训练数据样本估算 的值。如果 是分类属性，则 ；其中 是在属性 上具有值 的类 的训练样本数，而 是 中的训练样本数。

14、如果 是连续值属性，则通常假定该属性服从高斯分布。因而 （3-6）给定类 的训练样本属性 的值， 是属性 的高斯密度函数， ， 分别为均值和方差。（5）为预测一个未知样本X 的类别，可对每个类别 估算相应的 。样本X 归属类别 当且仅当 ，即X 属于 为最大的类 。|iP X C|iP X C1|nikikP X Cp xC12|,|,|iinip xCp xCp xCkA|ikkiispxCsikskAkxiCisiCkA2221|,e2ciciiiixkikcccp xCg xiCkA,iikccg xkAiciciC|iiP X CP CiC |1,iijjP X CP CP X CP

15、Cjm ji, |iiP X CP CiC第三章 数据挖掘算法of39163.2.1 贝叶斯决策与分类器3.2 分类第三章 数据挖掘算法支持向量机（Support Vector Machine）是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（对特定训练样本的学习精度，Accuracy）和学习能力（无错误地识别任意样本的能力）之间寻求最佳折中，以期获得最好的推广能力（或称泛化能力）。图3-3 超平面SVM最基本的任务就是找到一个能够让两类数据都离超平面很远的超平面，在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最

16、大化，平行超平面间的距离或差距越大，分类器的总误差越小。通常希望分类的过程是一个机器学习的过程。设样本属于两个类，用该样本训练SVM得到的最大间隔超平面。在超平面上的样本点也称为支持向量。of39173.2.2 SVM算法3.2 分类第三章 数据挖掘算法线性可分情形SVM非线性可分情形SVM支持向量机（SVM）的核函数of39183.2.2 SVM算法3.2 分类第三章 数据挖掘算法互联网的出现和普及，带来的网上信息量的大幅增长，出现信息超载问题。为了解决信息过载的问题，提出了很多解决方案，其中最具有代表性的解决方案是分类目录和搜索引擎。但是随着互联网规模的不断扩大，分类目录和搜索引擎，不能解

17、决用户的需求。推荐系统就是解决这一矛盾的重要工具。推荐系统具有用户需求驱动、主动服务和信息个性化程度高等优点，可有效解决信息过载问题。推荐系统是一种智能个性化信息服务系统，可借助用户建模技术对用户的长期信息需求进行描述，并根据用户模型通过一定的智能推荐策略实现有针对性的个性化信息定制，能够依据用户的历史兴趣偏好，主动为用户提供符合其需求和兴趣的信息资源。图3-6 推荐系统的工作原理of39193.2.3 案例：在线广告推荐中的分类3.2 分类第三章 数据挖掘算法推荐系统利用推荐算法将用户和物品联系起来，能够在信息过载的环境中帮助用户发现令他们感兴趣的信息，也能将信息推送给对他们感兴趣的用户。根

18、据已有用户注册信息和购买信息，使用朴素贝叶斯分类预测一个新注册用户购买计算机的可能性，从而向该用户推荐计算机类广告。训练样本如表3-1所示。序号ID年龄Age（岁）收入等级Income_level是否学生student信用等级Credit rate类别：是否购买计算机Class:buy computer130以下高否良否230以下高否优否331到40高否良是440以上中否良是540以上低是良是640以上低是优否731到40低是优是830以下中否良否930以下低是良是1040以上中是良是1130以下中是优是1231到40中否优是1331到40高是良是1440以上中否优否表3-1 训练课本of39

19、203.2.3 案例：在线广告推荐中的分类3.1数据挖掘概述第三章数据挖掘算法3.2分类3.3聚类3.4关联规则3.5预测规模习题3.6数据挖掘算法综合应用3.3聚类of39213.3 聚类聚类（clustering）就是将具体或抽象对象的集合分组成由相似对象组成的为多个类或簇的过程。由聚类生成的簇是一组数据对象的集合，簇必须同时满足以下两个条件：每个簇至少包含一个数据对象；每个数据对象必须属于且唯一地属于一个簇。聚类分析是指用数学的方法来研究与处理给定对象的分类，主要是从数据集中寻找数据间的相似性，并以此对数据进行分类，使得同一个簇中的数据对象尽可能相似，不同簇中的数据对象尽可能相异，从而发

20、现数据中隐含的、有用的信息。数据准备特征选择、提出特征提取聚类（或分组）聚类过程聚类算法的要求可扩展性处理不同类型属性的能力发现任意形状的聚类需要（由用户）决定的输入参数最少处理噪声数据的能力对输入记录顺序不敏感高维问题基于约束的聚类可解释性和可用性第三章 数据挖掘算法of39223.3.1 非监督机器学习方法与聚类3.3 聚类1层次聚类算法层次聚类算法的指导思想是对给定待聚类数据集合进行层次化分解。此算法又称为数据类算法，此算法根据一定的链接规则将数据以层次架构分裂或聚合，最终形成聚类结果。从算法的选择上看，层次聚类分为自顶而下的分裂聚类和自下而上的聚合聚类。分裂聚类初始将所有待聚类项看成同

21、一类，然后找出其中与该类中其他项最不相似的类分裂出去形成两类。如此反复执行，直到所有项自成一类。聚合聚类初始将所有待聚类项都视为独立的一类，通过连接规则，包括单连接、全连接、类间平均连接，以及采用欧氏距离作为相似度计算的算法，将相似度最高的两个类合并成一个类。如此反复执行，直到所有项并入同一个类。典型代表算法，BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies，利用层次方法的平衡迭代规约和聚类）第三章 数据挖掘算法of39233.3.2 常用聚类算法3.3 聚类2划分聚类算法划分法属于硬聚类，指导思想是将给定的数

22、据集初始分裂为K个簇，每个簇至少包含一条数据记录，然后通过反复迭代至每个簇不再改变即得出聚类结果。 K-Means算法也称作K-平均值算法或者K均值算法，是一种得到广泛使用的聚类分析算法。1）欧氏距离2）曼哈顿距离3）闵可夫斯基距离4）切比雪夫距离1221,pijikjkkd x xxx1,pijikjkkd x xxx11,prrijikjkkd x xxx1,2,maxijikjkkpd x xxx常用距离算法第三章 数据挖掘算法of39243.3.2 常用聚类算法3.3 聚类2划分聚类算法K-Means算法是解决聚类问题的一种经典算法，简单快速，对于处理大数据集，该算法是相对可伸缩的和高

23、效的图3-8 K-Means算法流程第三章 数据挖掘算法of39253.3.2 常用聚类算法3.3 聚类3基于密度的聚类算法基于密度聚类的经典算法DBSCAN（Density-Based Spatial Clustering of Application with Noise，具有噪声的基于密度的空间聚类应用）是一种基于高密度连接区域的密度聚类算法。DBSCAN的基本算法流程如下：从任意对象P 开始根据阈值和参数通过广度优先搜索提取从P 密度可达的所有对象，得到一个聚类。若P 是核心对象，则可以一次标记相应对象为当前类并以此为基础进行扩展。得到一个完整的聚类后，再选择一个新的对象重复上述过程。

24、若P 是边界对象，则将其标记为噪声并舍弃缺陷如聚类的结果与参数关系较大阈值过大容易将同一聚类分割阈值过小容易将不同聚类合并固定的阈值参数对于稀疏程度不同的数据不具适应性密度小的区域同一聚类易被分割密度大的区域不同聚类易被合并第三章 数据挖掘算法of39263.3.2 常用聚类算法3.3 聚类4基于网格的聚类算法基于网格的聚类算法是采用一个多分辨率的网格数据结构，即将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。STING（STatistical INformation Grid，统计信息网格）算法将空间区域划分为矩形单元针对不同级别的分辨率，通常存在多个级别的

25、矩形单元，这些单元形成了一个层次结构高层的每个单元被划分为多个低一层的单元WaveCluster（Clustering using wavelet transformation，采用小波变换聚类）是一种多分辨率的聚类算法先通过在数据空间上加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域第三章 数据挖掘算法of39273.3.2 常用聚类算法3.3 聚类5基于模型的聚类算法基于模型的聚类算法是为每一个聚类假定了一个模型，寻找数据对给定模型的最佳拟合。统计学方法(EM和COBWEB算法)神经网络方法(SOM算法)概念聚类是机器学习中的一种聚类方法，给

26、出一组未标记的数据对象，它产生一个分类模式。概念聚类除了确定相似对象的分组外，还为每组对象发现了特征描述，即每组对象代表了一个概念或类。概念聚类过程主要有两个步骤：首先，完成聚类；其次，进行特征描述。神经网络方法将每个簇描述成一个模型。模型作为聚类的一个“原型”，不一定对应一个特定的数据实例或对象。神经网络聚类的两种方法：竞争学习方法与自组织特征图映射方法。神经网络聚类方法存在较长处理时间和复杂数据中复杂关系问题，还不适合处理大数据库。第三章 数据挖掘算法of39283.3.2 常用聚类算法3.3 聚类图像分割是图像处理到图像分析的关键步骤，也是一种基本的计算机视觉技术，一般来说，图像分割是把

27、图像分成每个区域并提取感兴趣目标的技术和过程。颜色、灰度、纹理是比较常见和主要的特性，目标可以对应多个区域，也可以对应单个区域，主要与实际应用和目标有关。K-Means聚类算法简捷，具有很强的搜索能力，适合处理数据量大的应用场景，在数据挖掘和图像领域中得到了广泛的应用。图3-9 K-Means聚类算法进行图像分割示意图第三章 数据挖掘算法of39293.3.3 案例：海量视频检索中的聚类3.1数据挖掘概述第三章数据挖掘算法3.2分类3.3聚类3.1数据挖掘概述3.5预测规模习题3.6数据挖掘算法综合应用3.4关联规则of65303.4 关联规则关联规则是数据挖掘中最活跃的研究方法之一，是指搜索

28、业务系统中的所有细节或事务，找出所有能把一组事件或数据项与另一组事件或数据项联系起来的规则，以获得存在于数据库中的不为人知的或不能确定的信息，它侧重于确定数据中不同领域之间的联系，也是在无指导学习系统中挖掘本地模式的最普通形式。More应用市场：市场货篮分析、交叉销售（Crossing Sale）、部分分类（Partial Classification）、金融服务（Financial Service），以及通信、互联网、电子商务 第三章 数据挖掘算法of65313.4 关联规则第三章 数据挖掘算法一般来说，关联规则挖掘是指从一个大型的数据集（Dataset）发现有趣的关联（Associatio

29、n）或相关关系（Correlation），即从数据集中识别出频繁出现的属性值集（Sets of Attribute Values），也称为频繁项集（Frequent Itemsets，频繁集），然后利用这些频繁项集创建描述关联关系的规则的过程。3.4.1 关联规则的概念关联规则挖掘问题：发现所有的频繁项集是形成关联规则的基础。通过用户给定的最小支持度，寻找所有支持度大于或等于Minsupport的频繁项集。通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于Minconfidence的关联规则。发现频繁项集生成关联规则如何迅速高效地发现所有频繁项集，是关联规则挖掘的核心问题，也是衡

30、量关联规则挖掘算法效率的重要标准。of65323.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产生及其经典算法格结构（Lattice Structure）常常被用来枚举所有可能的项集。图3-10 项集的格of65333.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产生及其经典算法格结构（Lattice Structure）常常被用来枚举所有可能的项集。查找频繁项目集经典的查找策略基于精简集的查找策略基于最大频繁项集的查找策略按照挖掘的策略不同经典的挖掘完全频繁项集方法基于广度优先搜索策略的关联规则算法基于深度优先搜索策略的算法Apriori算法、DHP算法FP-Growth

31、算法、ECLAT算法COFI算法与经典查找不同方法基于精简集的方法基于最大频繁项目集的方法A-close算法MAFIA算法、GenMax算法DepthProject算法of65343.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产生及其经典算法1Apriori算法Apriori算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁1项集开始，采用频繁k项集搜索频繁k+1项集，直到不能找到包含更多项的频繁项集为止。Apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：生成频繁1项集L1连接步剪枝步生成频繁k项集Lk重复步骤（2）（4），直到不能产生新的频繁

32、项集的集合为止，算法中止。性能瓶颈Apriori算法是一个多趟搜索算法可能产生庞大的候选项集of65353.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产生及其经典算法2FP-Growth算法频繁模式树增长算法（Frequent Pattern Tree Growth）采用分而治之的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。FP-Growth算法由以下步骤组成：扫描事务数据库D，生成频繁1项集L1将频繁1项集L1按照支持度递减顺序排

33、序，得到排序后的项集L1构造FP树通过后缀模式与条件FP树产生的频繁模式连接实现模式增长1234图3-11 FP树的构造of65363.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产生及其经典算法3辛普森悖论虽然关联规则挖掘可以发现项目之间的有趣关系，在某些情况下，隐藏的变量可能会导致观察到的一对变量之间的联系消失或逆转方向，这种现象就是所谓的辛普森悖论（Simpsons Paradox）。为了避免辛普森悖论的出现，就需要斟酌各个分组的权重，并以一定的系数去消除以分组数据基数差异所造成的影响。同时必须了解清楚情况，是否存在潜在因素，综合考虑。of65373.4 关联规则第三章 数据挖

34、掘算法3.4.3 分类技术分类技术或分类法（Classification）是一种根据输入样本集建立类别模型，并按照类别模型对未知样本类标号进行标记的方法。根据所采用的分类模型不同基于决策树模型的数据分类基于统计模型的数据分类基于神经网络模型的数据分类基于案例推理的数据分类基于实例的数据分类1决策树决策树就是通过一系列规则对数据进行分类的过程。决策树分类算法通常分为两个步骤：构造决策树和修剪决策树。of65383.4 关联规则第三章 数据挖掘算法3.4.3 分类技术构造决策树修剪决策树根据实际需求及所处理数据的特性，选择类别标识属性和决策树的决策属性集在决策属性集中选择最有分类标识能力的属性作为

35、决策树的当前决策节点根据当前决策节点属性取值的不同，将训练样本数据集划分为若干子集 子集中的所有元组都属于同一类。 该子集是已遍历了所有决策属性后得到的。 子集中的所有剩余决策属性取值完全相同，已不能根据这些决策属性进一步划分子集。针对上一步中得到的每一个子集，重复进行以上两个步骤，直到最后的子集符合约束的3个条件之一根据符合条件不同生成叶子节点对决策树进行修剪，除去不必要的分枝，同时也能使决策树得到简化。常用的决策树修剪策略基于代价复杂度的修剪悲观修剪最小描述长度修剪按照修剪的先后顺序先剪枝（Pre-pruning）后剪枝（Post-pruning）of65393.4 关联规则第三章 数据挖

36、掘算法3.4.3 分类技术2k-最近邻最临近分类基于类比学习，是一种基于实例的学习，它使用具体的训练实例进行预测，而不必维护源自数据的抽象（或模型）。它采用n 维数值属性描述训练样本，每个样本代表n 维空间的一个点，即所有的训练样本都存放在n 维空间中。若给定一个未知样本，k-最近邻分类法搜索模式空间，计算该测试样本与训练集中其他样本的邻近度，找出最接近未知样本的k 个训练样本，这k 个训练样本就是未知样本的k 个“近邻”。其中的“邻近度”一般采用欧几里得距离定义：两个点 和 的Euclid距离是 。12(,)nXx xx12(,)nYy yy21(, )()niiid X Yxy最近邻分类是

37、基于要求的或懒散的学习法，即它存放所有的训练样本，并且直到新的（未标记的）样本需要分类时才建立分类。其优点是可以生成任意形状的决策边界，能提供更加灵活的模型表示。of65403.4 关联规则第三章 数据挖掘算法3.4.4 案例：保险客户风险分析1挖掘目标由过去大量的经验数据发现机动车辆事故率与驾驶者及所驾驶的车辆有着密切的关系，影响驾驶人员安全驾驶的主要因素有年龄、性别、驾龄、职业、婚姻状况、车辆车型、车辆用途、车龄等。因此，客户风险分析的挖掘目标就是上述各主要因素与客户风险之间的关系，等等。2数据预处理数据准备与预处理是数据挖掘中的首要步骤，高质量的数据是获得高质量决策的先决条件。在实施数据

38、挖掘之前，及时有效的数据预处理可以解决噪声问题和处理缺失的信息，将有助于提高数据挖掘的精度和性能。去除数据集之中的噪声数据和无关数据，处理遗漏数据和清洗“脏”数据等。数据清洗处理通常包括处理噪声数据、填补遗漏数据值/除去异常值、纠正数据不一致的问题，等等。在处理完噪声数据后，就可以对数据进行转化，主要的方法有： 聚集 忽略无关属性 连续型属性离散化等。数据清洗数据转化of65413.4 关联规则第三章 数据挖掘算法3.4.4 案例：保险客户风险分析3关联规则挖掘影响驾驶人员安全驾驶的主要因素年龄性别驾龄职业婚姻状况车辆车型车辆用途车龄其他根据前述关联规则的生成方法，得到挖掘出来的客户风险关联规

39、则序号关联规则支持度置信度1驾龄（X，A）被保车辆的价值（X，A）年赔付金额（X，B）0.18250.29652投保人年龄（X，A）驾龄（X，A）年赔付次数（X，B）0.16790.25713驾龄（X，B）车辆用途（X，A）年赔付金额（X，B）0.16630.33374驾龄（X，B）车辆用途（X，B）年赔付次数（X，A）0.17890.48515驾龄（X，B）被保车辆的价值（X，C）年赔付金额（X，C）0.18090.30036驾龄（X，C）车辆用途（X，B）年赔付次数（X，A）0.19940.58647驾龄（X，C）被保车辆的价值（X，C）车辆用途（X，C）年赔付次数（X，A）0.10310

40、.66398驾龄（X，A）被保车辆的价值（X，A）车辆用途（X，B）年赔付金额（X，B）0.10250.36549投保人年龄（X，B）驾龄（X，A）被保车辆的价值（X，D）年赔付金额（X，D）0.09340.454610驾龄（X，B）被保车辆的价值（X，A）车辆用途（X，A）年赔付金额（X，B）0.09680.448711投保人年龄（X，C）被保车辆的价值（X，C）车辆用途（X，C）年赔付金额（X，B）0.09090.353112投保人年龄（X，C）驾龄（X，B）被保车辆的价值（X，C）年赔付次数（X，A）0.08270.6094表3-7 客户风险关联规则详细分析所得数据，可以为公司业务提供数

41、据支撑，针对不同客户提供偏好服务，既能确保公司收益，又能给予用户更多的实惠。of65423.4关联规则3.1数据挖掘概述第三章数据挖掘算法3.2分类3.3聚类3.4关联规则习题3.6数据挖掘算法综合应用3.5预测规模of65433.5 预测模型3.5.1 预测与预测模型第三章 数据挖掘算法预测分析是一种统计或数据挖掘解决方案，包含可在结构化与非结构化数据中使用以确定未来结果的算法和技术，可为预测、优化、预报和模拟等许多其他相关用途而使用。时间序列预测是一种历史资料延伸预测，以时间序列所能反映的社会经济现象的发展过程和规律性，进行引申外推预测发展趋势的方法。从时间序列数据中提取并组建特征，仍用原

42、有的数据挖掘框架与算法进行数据挖掘将时间序列数据作为一种特殊的挖掘对象，找寻对应的数据挖掘算法进行专门研究依据研究的方式分类相似性问题挖掘时态模式挖掘依据研究的内容分类依据研究的对象分类事件序列的数据挖掘事务序列的数据挖掘数值序列的数据挖掘时间序列预测及数据挖掘分类of65443.5 预测模型3.5.1 预测与预测模型第三章 数据挖掘算法预测方案分类时间序列预测定性预测方法依据预测方法的性质因果关系预测时间序列的统计特征1）均值函数t( )ttE Xxf x dx2）自协方差函数,(,)()()t ststtssCov x xE xExxEx3）自相关函数,t st st ts sof6545

43、3.5 预测模型3.5.1 预测与预测模型第三章 数据挖掘算法1）自回归模型2）移动平均模型3）自回归移动平均模型1122tttptpixxxx 1122ttttqt qx 11221122tttptpittqt qxxxx of6546时间序列模型预测方案分类3.5 预测模型3.5.2 时间序列预测第三章 数据挖掘算法时间序列：对按时间顺序排列而成的观测值集合，进行数据的预测或预估。典型的算法：序贯模式挖掘SPMGC算法序贯模式挖掘算法SPMGC（Sequential Pattern Mining Based on General Constrains）SPMGC算法可以有效地发现有价值的数

44、据序列模式，提供给大数据专家们进行各类时间序列的相似性与预测研究。项集间的时间限制Cgap序列持续时间限制Cduration数据约束Cdata项的约束Citem序列长度的约束CLength其他约束时间序列领域约束规则of65473.5 预测模型3.5.2 时间序列预测第三章 数据挖掘算法SPMGC算法的基本处理流程扫描时间序列数据库，获取满足约束条件且长度为1的序列模式L1，以序列模式L1作为初始种子集根据长度为i-1的种子集Li-1，通过连接与剪切运算生成长度为i 并且满足约束条件的候选序列模式Ci，基于此扫描序列数据库，并计算每个候选序列模式Ci 的支持数，从而产生长度为I 的序列模式Li

45、，将Li作为新种子集在此重复上一步，直至没有新的候选序列模式或新的序列模式产生SPBGC算法首先对约束条件按照优先级进行排序，然后依据约束条件产生候选序列。SPBGC算法说明了怎样使用约束条件来挖掘序贯模式，然而，由于应用领域的不同，具体的约束条件也不尽相同，同时产生频繁序列的过程也可采用其他序贯模式算法。of65483.5 预测模型3.5.3 案例：地震预警第三章 数据挖掘算法1地震波形数据存储和计算平台南京云创大数据有限公司为山东省地震局研发了一套可以处理海量数据的高性能地震波形数据存储和计算平台，将从现有的光盘中导入地震波形数据并加以管理，以提供集中式的地震波形数据分析与地震预测功能，为

46、开展各种地震波形数据应用提供海量数据存储管理和计算服务能力。图3-12山东省地震波测数据云平台的显示界面of65493.5 预测模型3.5.3 案例：地震预警第三章 数据挖掘算法2地震波形数据存储和计算平台的主要性能指标数据存储和处理指标系统响应时间指标地震波形数据存储性能指标每年的原始地震波形数据及相关辅助信息约为15TB，为保证数据存储的可靠性，要求采用3倍副本方式保存数据，云平台每年需要提供约45TB的总存储量，同时系统必须能实时接收和处理高达10MB/s的入库数据千兆网络环境下，局域网客户端从分布式文件存储系统中读取4096B存储内容的响应时间不高于50毫秒采用HDFS格式进行数据读取

47、，读取性能为4080MB/s节点，数据规模10PB，数据负载均衡时间可依据流量配置而确定，集群重新启动时间按10PB规模计算达到分钟级别of65503.5 预测模型3.5.3 案例：地震预警第三章 数据挖掘算法3地震波形数据存储和计算平台的功能设计数据解析数据入库数据存储管理云计算平台的数据应用接口数据异地修复of65513.5 预测模型3.5.3 案例：地震预警第三章 数据挖掘算法4平台的组成、总体构架与功能模块图3-13 地震波形数据云平台总体构架与功能模块of65523.5 预测模型3.5.3 案例：地震预警第三章 数据挖掘算法5地震中的时间序列预测地震预测的主要手段也就是对地震序列进行

48、特征研究。通过对地震序列的特征研究，可以帮助判断某大地震发生后地质活动的规律，掌握一定区域内地震前后震级次序间的某种内在关联性，有利于判断次地震发生后，震区地质活动的客观趋势1）地震数据收集和预处理采用SPBGC算法，预处理的流程步骤具体如下：设定地震序列的空间跨度，并划分震级标准M依据地震目录数据库，将震级大于或等于震级标准M的地震信息存入大地震文件获取大地震文件中的每一条记录E，并取得震级M与震中所在位置G扫描地震目录数据，对每一地震记录E，均判断当前地震位置与震中G的距离是否满足设定的空间跨度。如果满足空间跨度，则将该记录标注为与震中等同的序列号，同时将震中为圆心的区域范围内地震的次数加

49、l；否则继续处理下一条地震记录大地震文件处理完毕后，该阶段地震数据收集和预处理阶段结束of65533.4关联规则3.1数据挖掘概述第三章数据挖掘算法3.2分类3.3聚类3.5预测规模习题3.4关联规则3.6数据挖掘算法综合应用of65543.6数据挖掘算法综合应用3.6.1 案例分析：精确营销中的关联规则应用数据挖掘在各领域的应用非常广泛，只要该产业拥有具备分析价值与需求的数据仓储或数据库，都可以利用挖掘工具进行有目的的挖掘分析。一般较常见的应用案例多发生在零售业、制造业、财务金融保险、通信业及医疗服务等。？如何通过交叉销售，得到更大的收入？如何在销售数据中发掘顾客的消费习性，并由交易记录找出

50、顾客偏好的产品组合？如何找出流失顾客的特征与推出新产品的时机点？通过关联规则挖掘来发现和捕捉数据间隐藏的重要关联，从而为产品营销提供技术支撑。第三章 数据挖掘算法of65553.6数据挖掘算法综合应用3.6.2 挖掘目标的提出第三章 数据挖掘算法电子商务网站中的商品推荐为例客户忠诚度影响因素其他因素：如社会文化、国家政策等客户自身原因企业原因数据挖掘技术可以建立客户忠诚度分析模型，了解哪些因素对客户的忠诚度有较大的影响，从而采取相应措施。因此，基于数据挖掘技术的客户忠诚度分析具有重要的应用价值。of65563.6数据挖掘算法综合应用3.6.3 分析方法与过程第三章 数据挖掘算法图3-14 电子