Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,大数据,BIG DATA,大数据BIG DATA,1,3.1,数据挖掘概述,第三章数据挖掘算法,3.2,分类,3.3,聚类,3.1,数据挖掘概述,3.5,预测规模,习题,3.6,数据挖掘算法综合应用,3.4,关联规则,of,65,2,3.1数据挖掘概述第三章数据挖掘算法3.2分类3.3,2,3.4,关联规则,关联规则是数据挖掘中最活跃的研究方法之一，是指搜索业务系统中的所有细节或事务，找出所有能把一组事件或数据项与另一组事件或数据项联系起来的规则，以获得存在于数据库中的不为人知的或不能确定的信息，它侧重于确定数据中不同领域之间的联系，也是在无指导学习系统中挖掘本地模式的最普通形式。,More,应用市场：,市场货篮分析、交叉销售（,Crossing Sale,）、部分分类（,Partial Classification,）、金融服务（,Financial Service,），以及通信、互联网、电子商务,第三章 数据挖掘算法,of,65,3,3.4 关联规则关联规则是数据挖掘中最活跃的研究方法之一，是,3,3.4,关联规则,第三章 数据挖掘算法,一般来说，关联规则挖掘是指从一个大型的数据集（,Dataset,）发现有趣的关联（,Association,）或相关关系（,Correlation,），即从数据集中识别出频繁出现的属性值集（,Sets of Attribute Values,），也称为频繁项集（,Frequent Itemsets,，频繁集），然后利用这些频繁项集创建描述关联关系的规则的过程。,3.4.1,关联规则的概念,关联规则挖掘问题,：,发现所有的频繁项集是形成关联规则的基础。通过用户给定的最小支持度，寻找所有支持度大于或等于,Minsupport,的频繁项集。,通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于,Minconfidence,的关联规则。,发现频繁项集,生成关联规则,如何迅速高效地发现所有频繁项集，是关联规则挖掘的核心问题，也是衡量关联规则挖掘算法效率的重要标准。,of,65,4,3.4 关联规则第三章 数据挖掘算法一般来说，关联规则挖掘是,4,3.4,关联规则,第三章 数据挖掘算法,3.4.2,频繁项集的产生及其经典算法,格结构（,Lattice Structure,）常常被用来枚举所有可能的项集。,图,3-10,项集的格,of,65,5,3.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产,5,3.4,关联规则,第三章 数据挖掘算法,3.4.2,频繁项集的产生及其经典算法,格结构（,Lattice Structure,）常常被用来枚举所有可能的项集。,查找频繁项目集,经典的查找策略,基于精简集的查找策略,基于最大频繁项集的查找策略,按照挖掘的策略不同,经典的挖掘完全频繁项集方法,基于广度优先搜索策略的关联规则算法,基于深度优先搜索策略,的算法,Apriori,算法,、,DHP,算法,FP-Growth,算法,、,ECLAT,算法,COFI,算法,与,经典,查找不同,方法,基于精简集的方法,基于最大频繁项目集的方法,A-close,算法,MAFIA,算法、,GenMax,算法,DepthProject,算法,of,65,6,3.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产,6,3.4,关联规则,第三章 数据挖掘算法,3.4.2,频繁项集的产生及其经典算法,1,Apriori,算法,Apriori,算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁,1,项集开始，采用频繁,k,项集搜索频繁,k,+1,项集，直到不能找到包含更多项的频繁项集为止。,Apriori,算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：,生成频繁,1,项集,L,1,连接步,剪枝步,生成频繁,k,项集,L,k,重复步骤（,2,）（,4,），直到不能产生新的频繁项集的集合为止，算法中止。,性能瓶颈,Apriori,算法是一个多趟搜索算法,可能产生庞大的候选项集,of,65,7,3.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产,7,3.4,关联规则,第三章 数据挖掘算法,3.4.2,频繁项集的产生及其经典算法,2,FP-Growth,算法,频繁模式树增长算法（,Frequent Pattern Tree Growth,）采用分而治之的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。,FP-Growth,算法由以下步骤组成：,扫描事务数据库,D,，生成频繁,1,项集,L,1,将频繁,1,项集,L,1,按照支持度递减顺序排序，得到排序后的项集,L,1,构造,FP,树,通过后缀模式与条件,FP,树产生的频繁模式连接实现模式增长,1,2,3,4,图,3-11 FP,树的构造,of,65,8,3.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产,8,3.4,关联规则,第三章 数据挖掘算法,3.4.2,频繁项集的产生及其经典算法,3,辛普森悖论,虽然关联规则挖掘可以发现项目之间的有趣关系，在某些情况下，隐藏的变量可能会导致观察到的一对变量之间的联系消失或逆转方向，这种现象就是所谓的辛普森悖论（,Simpsons Paradox,）。,为了避免辛普森悖论的出现，就需要斟酌各个分组的权重，并以一定的系数去消除以分组数据基数差异所造成的影响。同时必须了解清楚情况，是否存在潜在因素，综合考虑。,of,65,9,3.4 关联规则第三章 数据挖掘算法3.4.2 频繁项集的产,9,3.4,关联规则,第三章 数据挖掘算法,3.4.3,分类技术,分类技术或分类法（,Classification,）是一种根据输入样本集建立类别模型，并按照类别模型对未知样本类标号进行标记的方法。,根据所采用的分类模型不同,基于决策树模型的数据分类,基于统计模型的数据分类,基于神经网络模型的数据分类,基于案例推理的数据分类,基于实例的数据分类,1,决策树,决策树就是通过一系列规则对数据进行分类的过程。,决策树分类算法通常分为两个步骤：构造决策树和修剪决策树。,of,65,10,3.4 关联规则第三章 数据挖掘算法3.4.3 分类技术分类,10,3.4,关联规则,第三章 数据挖掘算法,3.4.3,分类技术,构造决策树,修剪决策树,根据实际需求及所处理数据的特性，选择类别标识属性和决策树的决策属性集,在决策属性集中选择最有分类标识能力的属性作为决策树的当前决策节点,根据当前决策节点属性取值的不同，将训练样本数据集划分为若干子集,子集中的所有元组都属于同一类。,该子集是已遍历了所有决策属性后得到的。,子集中的所有剩余决策属性取值完全相同，已不能根据这些决策属性进一步划分子集。,针对上一步中得到的每一个子集，重复进行,以上,两个步骤，直到最后的子集符合约束的,3,个条件之一,根据符合条件不同生成叶子节点,对决策树进行修剪，除去不必要的分枝，同时也能使决策树得到简化。,常用的决策树修剪策略,基于代价复杂度的修剪,悲观修剪,最小描述长度,修剪,按照修剪的先后顺序,先剪枝（,Pre-pruning,）,后剪枝（,Post-pruning,）,of,65,11,3.4 关联规则第三章 数据挖掘算法3.4.3 分类技术构造,11,3.4,关联规则,第三章 数据挖掘算法,3.4.3,分类技术,2,k-,最近邻,最临近分类基于类比学习，是一种基于实例的学习，它使用具体的训练实例进行预测，而不必维护源自数据的抽象（或模型）。它采用,n,维数值属性描述训练样本，每个样本代表,n,维空间的一个点，即所有的训练样本都存放在,n,维空间中。若给定一个未知样本，,k-,最近邻分类法搜索模式空间，计算该测试样本与训练集中其他样本的邻近度，找出最接近未知样本的,k,个训练样本，这,k,个训练样本就是未知样本的,k,个“近邻”。其中的“邻近度”一般采用欧几里得距离定义：两个点,和,的,Euclid,距离是,。,最近邻分类是基于要求的或懒散的学习法，即它存放所有的训练样本，并且直到新的（未标记的）样本需要分类时才建立分类。其优点是可以生成任意形状的决策边界，能提供更加灵活的模型表示。,of,65,12,3.4 关联规则第三章 数据挖掘算法3.4.3 分类技术2,12,3.4,关联规则,第三章 数据挖掘算法,3.4.4,案例：保险客户风险分析,1,挖掘目标,由过去大量的经验数据发现机动车辆事故率与驾驶者及所驾驶的车辆有着密切的关系，影响驾驶人员安全驾驶的主要因素有年龄、性别、驾龄、职业、婚姻状况、车辆车型、车辆用途、车龄等。因此，客户风险分析的挖掘目标就是上述各主要因素与客户风险之间的关系，等等。,2,数据预处理,数据准备与预处理是数据挖掘中的首要步骤，高质量的数据是获得高质量决策的先决条件。在实施数据挖掘之前，及时有效的数据预处理可以解决噪声问题和处理缺失的信息，将有助于提高数据挖掘的精度和性能。,去除数据集之中的噪声数据和无关数据，处理遗漏数据和清洗“脏”数据等,。,数据清洗处理通常包括处理噪声数据、填补遗漏数据值,/,除去异常值、纠正数据不一致的问题，等等。,在处理完噪声数据后，就可以对数据进行转化，主要的方法有,：,聚集,忽略无关属性,连续型属性离散化等。,数据清洗,数据转化,of,65,13,3.4 关联规则第三章 数据挖掘算法3.4.4 案例：保险客,13,3.4,关联规则,第三章 数据挖掘算法,3.4.4,案例：保险客户风险分析,3,关联规则挖掘,影响驾驶人员安全驾驶的主要因素,年龄,性别,驾龄,职业,婚姻状况,车辆车型,车辆用途,车龄,其他,根据前述关联规则的生成方法，得到挖掘出来的客户风险关联规则,序号,关联规则,支持度,置信度,1,驾龄（,X,，,A,）被保车辆的价值（,X,，,A,）,年赔付金额（,X,，,B,）,0.1825,0.2965,2,投保人年龄（,X,，,A,）驾龄（,X,，,A,）,年赔付次数（,X,，,B,）,0.1679,0.2571,3,驾龄（,X,，,B,）车辆用途（,X,，,A,）,年赔付金额（,X,，,B,）,0.1663,0.3337,4,驾龄（,X,，,B,）车辆用途（,X,，,B,）,年赔付次数（,X,，,A,）,0.1789,0.4851,5,驾龄（,X,，,B,）被保车辆的价值（,X,，,C,）,年赔付金额（,X,，,C,）,0.1809,0.3003,6,驾龄（,X,，,C,）车辆用途（,X,，,B,）,年赔付次数（,X,，,A,）,0.1994,0.5864,7,驾龄（,X,，,C,）被保车辆的价值（,X,，,C,）车辆用途（,X,，,C,）,年赔付次数（,X,，,A,）,0.1031,0.6639,8,驾龄（,X,，,A,）被保车辆的价值（,X,，,A,）车辆用途（,X,，,B,）,年赔付金额（,X,，,B,）,0.1025,0.3654,9,投保人年龄（,X,，,B,）驾龄（,X,，,A,）被保车辆的价值（,X,，,D,）,年赔付金额（,X,，,D,）,0.0934,0.4546,10,驾龄（,X,，,B,）被保车辆的价值（,X,，,A,）车辆用途（,X,，,A