《大数据》第3章数据挖掘算法(下)

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