《数据仓库与数据挖掘》第8章

2019年8月1日星期四DataMining:ConceptsandTechniques1第6章:关联规则挖掘AssociationruleminingAlgorithmsforscalableminingof(single-dimensionalBoolean)associationrulesintransactionaldatabasesMiningvariouskindsofassociation/correlationrulesConstraint-basedassociationminingSequentialpatternminingApplications/extensionsoffrequentpatternminingSummary2019年8月1日星期四DataMining:ConceptsandTechniques2WhatIsAssociationMining?Associationrulemining:Findingfrequentpatterns,associations,correlations,orcausalstructuresamongsetsofitemsorobjectsintransactiondatabases,relationaldatabases,andotherinformationrepositories.Frequentpattern:pattern(setofitems,sequence,etc.)thatoccursfrequentlyinadatabase[AIS93]Motivation:findingregularitiesindataWhatproductswereoftenpurchasedtogether?—Beeranddiapers?!WhatarethesubsequentpurchasesafterbuyingaPC?WhatkindsofDNAaresensitivetothisnewdrug?Canweautomaticallyclassifywebdocuments?2019年8月1日星期四DataMining:ConceptsandTechniques3关联规则挖掘的基本概念购物篮分析－引发关联规则挖掘的例子问题：“什么商品组或集合顾客多半会在一次购物中同时购买？”购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。〖例〗购买计算机与购买财务管理软件的关联规则可表示为：computerfinancial_management_softwar[support=2%,confidence=60%]support为支持度，confidence为置信度。该规则表示：在所分析的全部事务中，有2％的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60％也购买财务管理软件。2019年8月1日星期四DataMining:ConceptsandTechniques4WhyIsFrequentPatternorAssoiciationMininganEssentialTaskinDataMining?FoundationformanyessentialdataminingtasksAssociation,correlation,causalitySequentialpatterns,temporalorcyclicassociation,partialperiodicity,spatialandmultimediaassociationAssociativeclassification,clusteranalysis,icebergcube,fascicles(semanticdatacompression)BroadapplicationsBasketdataanalysis,cross-marketing,catalogdesign,salecampaignanalysisWeblog(clickstream)analysis,DNAsequenceanalysis,etc.2019年8月1日星期四DataMining:ConceptsandTechniques5关联规则关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性。项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。〖定义8－1〗令I={i1，i2，…,in}是项目集，D是全体事务的集合。事务T是I上的一个子集，集合TI，每个事务用唯一的标志TID来标识。关联规则是形如XY的蕴含式，其中XI，YI且XY=，X称为规则的条件，Y称为规则的结果。2019年8月1日星期四DataMining:ConceptsandTechniques6置信度和支持度〖定义8－2〗关联规则XY对事物集D的支持度（support，）定义为D中包含有事务X和Y的百分比。关联规则XY对事务集合D的置信度（confidence）定义为D中包含有X的事务数与同时包含Y的百分比。即：support(XY)＝(包含X和Y的事务数/事务总数)×100％confidence(XY)＝包含X和Y的事务数/包含X的事务数)×100％〖定义8－3〗置信度和支持度均大于给定阈值（即最小置信度阈值和最小支持度阈值）。即：support(XY)＝min_supconfidence(XY)＝min_conf的关联规则称为强规则；否则称为弱规则。2019年8月1日星期四DataMining:ConceptsandTechniques7关联规则挖掘数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和、最小支持度。2019年8月1日星期四DataMining:ConceptsandTechniques8关联规则挖掘数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。强规则XY对应的项集（X∪Y）必定是频繁集。因此，可以把关联规则挖掘划分为以下两个子问题：根据最小支持度找出事务集D中的所有频繁项集。―核心根据频繁项集和最小置信度产生关联规则。―较易关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和、最小支持度。2019年8月1日星期四DataMining:ConceptsandTechniques9关联规则挖掘的分类—基于变量的类别基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型：布尔型关联规则：如果规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。例如，以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age和income已经离散化）：age(X,“30…39”)∧income(“42K…48K”)buys(X,“high_resolution_TV”)量化型关联规则中也可以包含多种变量。例如：性别=“女”=职业=“秘书”，是布尔型关联规则；性别=“女”=avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。2019年8月1日星期四DataMining:ConceptsandTechniques10关联规则挖掘的分类—基于抽象层次基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则：单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。例如：buys(X,“computer”)buys(X,“printer”)顾客X购买的商品不涉及不同抽象层次（“computer”和“printer”在同一个抽象层），因此是单层关联规则。多层的关联规则：变量涉及不同抽象层次的项或属性。例如：age(X,“30…39”)buys(X,“laptopcomputer”)age(X,“30…39”)buys(X,“computer”)顾客X购买的商品涉及不同抽象层次（“computer”在比“laptopcomputer”高的抽象层），因此是多层关联规则。2019年8月1日星期四DataMining:ConceptsandTechniques11关联规则挖掘的分类—基于数据的维数基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。例如：用户购买的物品：“咖啡=砂糖”，这条规则只涉及到用户的购买的物品。多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。例如：性别=“女”=职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则2019年8月1日星期四DataMining:ConceptsandTechniques12关联规则挖掘的过程〖定义8－4〗在关联规则挖掘算法中，把项目的集合称为项集（itemset），包含有k个项目的项集称为k-项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或等于最小支持度s与D中事务总数的乘积，则称该项集满足最小支持度s。如果项集满足最小支持度，则称该项集为频繁项集（frequentitemset）。关联规则的挖掘主要被分解为下面两步：第1步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1到k递归查找k-频繁项集。第2步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关联规则。对给定的L，如果其非空子集AL，sup(L)为L的支持度，sup(A)为A的支持度，则产生形式为AL-A的规则。2019年8月1日星期四DataMining:ConceptsandTechniques13BasicConcepts:FrequentPatternsandAssociationRulesItemsetX={x1,…,xk}FindalltherulesXYwithminconfidenceandsupportsupport,s,probabilitythatatransactioncontainsXYconfidence,c,conditionalprobabilitythatatransactionhavingXalsocontainsY.Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,F2019年8月1日星期四DataMining:ConceptsandTechniques14MiningAssociationRules—anExampleForruleAC:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20