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

1、第6章: 关联规则挖掘Association rule miningAlgorithms for scalable mining of (single-dimensional Boolean) association rules in transactional databasesMining various kinds of association/correlation rules Constraint-based association miningSequential pattern miningApplications/extensions of frequent pattern m

2、iningSummary2022/10/131Data Mining: Concepts and TechniquesWhat Is Association Mining?Associationrule mining:Finding frequent patterns,associations, correlations,orcausal structuresamongsetsofitemsorobjects in transaction databases,relationaldatabases, andotherinformationrepositories.Frequentpattern

3、: pattern(setofitems,sequence, etc.) thatoccurs frequentlyinadatabaseAIS93Motivation:finding regularitiesindataWhat products wereoftenpurchased together? Beerand diapers?!What arethesubsequentpurchasesafterbuying aPC?What kinds of DNAaresensitive to thisnew drug?Canweautomaticallyclassifywebdocument

4、s?2020-03-012Data Mining:Conceptsand Techniques关联规则则挖掘的的基本概概念购物篮分分析引引发关联联规则挖挖掘的例例子问题：“什么商商品组或或集合顾顾客多半半会在一一次购物物中同时时购买？”购物篮分分析：设设全域为为商店出出售的商商品的集集合（即即项目全全集），一次购购物购买买（即事事务）的的商品为为项目全全集的子子集，若若每种商商品用一一个布尔尔变量表表示该商商品的有有无，则则每个购购物篮可可用一个个布尔向向量表示示。通过过对布尔尔向量的的分析，得到反反映商品品频繁关关联或同同时购买买的购买买模式。这些模模式可用用关联规规则描述述。例购购买计算算

5、机与购购买财务务管理软软件的关关联规则则可表示示为：computerfinancial_management_softwarsupport=2%,confidence=60%support为支持度度，confidence为置信度度。该规则表表示：在在所分析析的全部部事务中中，有2的事事务同时时购买计计算机和和财务管管理软件件；在购购买计算算机的顾顾客中60也也购买财财务管理理软件。2020-03-013Data Mining:Conceptsand TechniquesWhyIsFrequentPatternorAssoiciationMining an EssentialTask in Da

6、taMining?Foundation formany essentialdata miningtasksAssociation,correlation, causalitySequential patterns,temporalorcyclicassociation, partialperiodicity, spatialand multimediaassociationAssociativeclassification,clusteranalysis,icebergcube,fascicles(semantic datacompression)BroadapplicationsBasket

7、dataanalysis,cross-marketing,catalog design,salecampaignanalysisWeblog (clickstream) analysis,DNAsequenceanalysis, etc.2020-03-014Data Mining:Conceptsand Techniques关联规则则关联（Associations）分析的目目的是为为了挖掘掘隐藏在在数据间间的相互互关系，即对于于给定的的一组项项目和一一个记录录集，通通过对记记录集的的分析，得出项项目集中中的项目目之间的的相关性性。项目目之间的的相关性性用关联联规则来来描述，关联规规则反映映了

8、一组组数据项项之间的的密切程程度或关关系。定义81令I=i1，i2，,in是项目集集，D是全体事事务的集集合。事事务T是I上的一个个子集，集合TI，每个事务务用唯一一的标志志TID来标识。关联规规则是形形如XY的蕴含式式，其中中XI，YI且XY=，X称为规则则的条件件，Y称为规则则的结果果。2020-03-015Data Mining:Conceptsand Techniques置信度和和支持度度定义82关联规则则XY对事物集集D的支持度度（support，）定义为D中包含有有事务X和Y的百分比比。关联联规则XY对事务集集合D的置信度度（confidence）定义为D中包含有有X的事务数数与同

9、时时包含Y的百分比比。即：support(XY)(包含X和Y的事务数数 /事事务总总数)100confidence(XY)包含X和Y的事务数数 /包包含X的事务数数)100定义83置信度和和支持度度均大于于给定阈阈值（即即最小置置信度阈阈值和最最小支持持度阈值值）。即即：support(XY)min_supconfidence(XY)min_conf的关联规规则称为为强规则则；否则则称为弱弱规则。2020-03-016Data Mining:Conceptsand Techniques关联规则则挖掘数据挖掘掘主要就就是对强强规则的的挖掘。通过设设置最小小支持度度和最小小置信度度可以了了解某些些

10、数据之之间的关关联程度度。关联规则则挖掘：给定一一组Item和记录集集合，挖挖掘出Item间的相关关性，使使其置信信度和支支持度分分别大于于用户给给定的最最小置信信度和、最小支支持度。2020-03-017Data Mining:Conceptsand Techniques关联规则则挖掘数据挖掘掘主要就就是对强强规则的的挖掘。通过设设置最小小支持度度和最小小置信度度可以了了解某些些数据之之间的关关联程度度。强规则XY对应的项项集（XY）必定是频频繁集。因此，可以把把关联规规则挖掘掘划分为为以下两两个子问问题：根据最小小支持度度找出事事务集D中的所有有频繁项项集。核心根据频繁繁项集和和最小置置信

11、度产产生关联联规则。较易易关联规则则挖掘：给定一一组Item和记录集集合，挖挖掘出Item间的相关关性，使使其置信信度和支支持度分分别大于于用户给给定的最最小置信信度和、最小支支持度。2020-03-018Data Mining:Conceptsand Techniques关联规则则挖掘的的分类基于变量量的类别别基于规则则中处理理的变量量的类别别,关联联规则可可以分为为布尔型型和数值值型：布尔型关关联规则则：如果果规则考考虑的关关联是项项“在”或“不不在”，则关联联规则是是布尔型型的。例例如，由由购物篮篮分析得得出的关关联规则则。量化型关关联规则则：如果果描述的的是量化化的项或或属性之之间的关

12、关联，则则该规则则是量化化型的关关联规则则。例如如，以下下是量化化型关联联规则的的一个例例子（其其中X为表示顾顾客的变变量，量量化属性性age和income已经离散散化）：age(X,“3039”)income(“42K48K”)buys(X,“high_resolution_TV”)量化型关关联规则则中也可可以包含含多种变变量。例例如：性别=“女”=职业业=“秘秘书”，是布布尔型关关联规则则；性别=“女”=avg（月收入）=2300，涉及的的收入是是数值类类型，所所以是一一个量化化型关联联规则。2020-03-019Data Mining:Conceptsand Techniques关联规则

13、则挖掘的的分类基于抽象层次次基于规则则中数据据的抽象象层次,可以分分为单层层关联规规则和多多层关联联规则：单层的关关联规则则：所有有的变量量都不涉涉及不同同抽象层层次的项项或属性性。例如：buys(X, “computer”)buys(X,“printer”)顾客X购买的商商品不涉涉及不同同抽象层层次（“computer”和“printer”在同一个个抽象层层），因因此是单单层关联联规则。多层的关关联规则则：变量量涉及不不同抽象象层次的的项或属属性。例如：age(X,“3039”)buys(X, “laptopcomputer”)age(X,“3039”)buys(X, “computer”)

14、顾客X购买的商商品涉及及不同抽抽象层次次（“computer”在比“laptopcomputer”高的抽象象层），因此是是多层关关联规则则。 2020-03-0110Data Mining:Conceptsand Techniques关联规则则挖掘的的分类基于数据据的维数数基于规则则中涉及及到的数数据的维维数,关关联规则则可以分分为单维维的和多多维的单维关联联规则：处理单单个维中中属性间间的关系系，即在在单维的的关联规规则中，只涉及及到数据据的一个个维。例如：用用户购买买的物品品：“咖咖啡=砂糖”，这条条规则只只涉及到到用户的的购买的的物品。多维关联联规则：处理多多个维中中属性之之间的关关系，

15、即即在多维维的关联联规则中中，要处处理的数数据将会会涉及多多个维。例如：性性别=“女”=职业业=“秘秘书”，这条规规则就涉涉及到两两个维中中字段的的信息，是两个个维上的的一条关关联规则则2020-03-0111Data Mining:Conceptsand Techniques关联规则则挖掘的的过程定义84在关联规规则挖掘掘算法中中，把项项目的集集合称为为项集（itemset），包含有k个项目的的项集称称为k-项集。包包含项集集的事务务数称为为项集的的出现频频率，简简称为项项集的频频率或支支持度计计数。如如果项集集的出现现频率大大于或等等于最小小支持度度s与D中事务总总数的乘乘积，则则称该项项

16、集满足足最小支支持度s。如果项集集满足最最小支持持度，则则称该项项集为频频繁项集集（frequentitemset ）。关联规则则的挖掘掘主要被被分解为为下面两两步：第1步：找出所所有的频频繁项集集，即找找出支持持度大于于或等于于给定的的最小支支持度阈阈值的所所有项集集。可以以从1到到k递归查找找k-频繁项集集。第2步：由频繁繁项集产产生强关关联规则则，即找找出满足足最小支支持度和和最小置置信度的的关联规规则。对对给定的的L，如果其非非空子集集AL，sup(L)为L的支持度度，sup(A)为A的支持度度，则产产生形式式为AL-A的规则。 2020-03-0112Data Mining:Conc

17、eptsand TechniquesBasicConcepts:FrequentPatternsand Association RulesItemset X=x1, , xkFind alltherulesXYwith minconfidence andsupportsupport,s,probabilitythat atransactioncontainsXYconfidence,c,conditionalprobabilitythat atransactionhaving XalsocontainsY.Letmin_support =50%,min_conf=50%:AC(50%,66.7

18、%)CA(50%,100%)Customerbuys diaperCustomerbuys bothCustomerbuys beerTransaction-idItems bought10A, B, C20A, C30A, D40B, E, F2020-03-0113Data Mining:Conceptsand TechniquesMiningAssociationRulesanExampleForruleAC:support =support(AC)= 50%confidence =support(AC)/support(A)= 66.6%Min. support50%Min. conf

19、idence50%Transaction-idItems bought10A, B, C20A, C30A, D40B, E, FFrequent patternSupportA75%B50%C50%A, C50%2020-03-0114Data Mining:Conceptsand TechniquesChapter 6: MiningAssociationRulesinLargeDatabasesAssociationrule miningAlgorithms forscalableminingof(single-dimensionalBoolean)associationrulesint

20、ransactional databasesMiningvariouskindsofassociation/correlationrulesConstraint-based association miningSequential patternminingApplications/extensionsoffrequentpattern miningSummary2020-03-0115Data Mining:Conceptsand TechniquesApriori:A CandidateGeneration-and-test ApproachAnysubset of afrequentit

21、emsetmust be frequentifbeer,diaper,nutsisfrequent,soisbeer,diaperEverytransactionhavingbeer, diaper,nutsalsocontainsbeer,diaperApriori pruningprinciple:Ifthereisanyitemset which is infrequent, itssupersetshouldnot be generated/tested!Method:generatelength(k+1)candidate itemsets fromlength kfrequenti

22、temsets,andtest thecandidates againstDBTheperformancestudiesshow itsefficiency andscalabilityAgrawal &Srikant1994,Mannila,etal.19942020-03-0116Data Mining:Conceptsand TechniquesTheAprioriAlgorithmAnExampleDatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItems

23、etsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E22020-03-0117Data Mining:Conceptsand TechniquesTheAprioriAlgorithmPseudo-code:Ck: Candidateitemset of sizekLk: frequent itemsetofsizekL

24、1= frequentitems;for(k= 1;Lk!=;k+)dobeginCk+1= candidatesgenerated fromLk;foreachtransactiontindatabasedoincrementthe count of allcandidates inCk+1that arecontainedintLk+1= candidatesinCk+1with min_supportendreturnkLk;2020-03-0118Data Mining:Conceptsand TechniquesImportantDetailsofAprioriHowtogenera

25、tecandidates?Step 1: self-joiningLkStep 2: pruningHowtocountsupportsofcandidates?Example of Candidate-generationL3=abc, abd,acd,ace, bcdSelf-joining:L3*L3abcdfromabcandabdacdefromacdandacePruning:acdeisremoved becauseadeisnotinL3C4=abcd2020-03-0119Data Mining:Conceptsand TechniquesHowtoGenerateCandi

26、dates?Suppose theitemsinLk-1arelisted in an orderStep 1: self-joiningLk-1insertintoCkselectp.item1, p.item2, , p.itemk-1, q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1=min_conf则输出关关联规则则“s(I-s)”，其中min_conf为最小置置信度阈阈值。2020-03-0123Data Mining:Conceptsand Techniques由频繁项项集

27、而产产生关联联规则例假假设数据据包含频频繁项集集I=I1，I2，I5：第1步：对于频频繁项集集I=I1，I2，I5，产生I的所有非非空子集集:I1,I2,I1,I5,I2,I5,I1,I2,I5第2步：对于I的每一个个非空子子集s，输出关联联规则“s(I-s)”I1I2I5confidence=2/4=50%I1I5I2confidence=2/2=100%I2I5I1confidence=2/2=100%I1I2I5confidence=2/6=33%I2I1I5confidence=2/7=29%I5I1I2confidence=2/7=100%如果最小小置信度度设定为为70，则只只有以下

28、下三个关关联规则则输出：I1I5I2confidence=2/2=100%I2I5I1confidence=2/2=100%I5I1I2confidence=2/7=100%2020-03-0124Data Mining:Conceptsand Techniques例子例以以下表所所示的事事务集为为例，其其中Ci是候选集集，Li是大数据据项集。假设最最小支持持度为40%，最小置置信度为为70%。则数数据项在在候选集集中至少少要出现现4次以以上才能能满足大大数据项项的条件件，规则则的可信信度至少少要大于于70%才能形形成关联联规则。Apriori关联规则则挖掘过过程如图图所示。2020-03-0

29、125Data Mining:Conceptsand TechniquesChallenges of Frequent PatternMiningChallengesMultiplescansoftransactiondatabaseHuge numberofcandidatesTedious workload of supportcountingfor candidatesImprovingApriori:generalideasReducepasses of transaction database scansShrinknumber of candidatesFacilitate sup

30、portcountingofcandidates2020-03-0126Data Mining:Conceptsand TechniquesDIC: ReduceNumberofScansABCDABCABDACDBCDABACBCADBDCDABCDItemset latticeOnce bothAandDaredeterminedfrequent,the counting of AD beginsOnce alllength-2subsets of BCDaredeterminedfrequent,the counting of BCDbeginsTransactions1-itemset

31、s2-itemsetsApriori1-itemsets2-items3-itemsDICS.Brin R. Motwani, J. Ullman,and S. Tsur.Dynamic itemsetcountingand implication rules formarketbasket data. InSIGMOD972020-03-0127Data Mining:Conceptsand TechniquesPartition: ScanDatabaseOnlyTwiceAnyitemsetthat is potentially frequent in DB mustbefrequent

32、inatleastone of thepartitions of DBScan 1: partitiondatabaseandfindlocalfrequentpatternsScan 2: consolidate globalfrequentpatternsA.Savasere,E.Omiecinski,and S. Navathe.Anefficientalgorithm forminingassociationinlargedatabases. InVLDB952020-03-0128Data Mining:Conceptsand TechniquesSamplingforFrequen

33、tPatternsSelectasampleoforiginaldatabase, minefrequentpatternswithin sampleusingAprioriScan database oncetoverify frequent itemsets found in sample,onlybordersofclosure of frequent patterns arecheckedExample:checkabcdinstead ofab,ac, , etc.Scan database again to findmissed frequent patternsH.Toivone

34、n.Samplinglargedatabasesfor association rules. InVLDB962020-03-0129Data Mining:Conceptsand TechniquesDHP: ReducetheNumber of CandidatesAk-itemsetwhosecorresponding hashingbucket count is below thethresholdcannot be frequentCandidates:a,b,c,d,eHash entries: ab,ad, aebd, be,deFrequent1-itemset: a, b,

35、d, eabisnotacandidate2-itemset if thesumofcountofab,ad,ae is below supportthresholdJ.Park,M.Chen,andP.Yu.Aneffectivehash-basedalgorithmfor miningassociationrules. InSIGMOD952020-03-0130Data Mining:Conceptsand TechniquesEclat/MaxEclatandVIPER: ExploringVerticalData FormatUsetid-list, thelist of trans

36、action-idscontaining an itemsetCompressionoftid-listsItemset A: t1,t2,t3, sup(A)=3Itemset B: t2,t3,t4, sup(B)=3Itemset AB:t2,t3, sup(AB)=2Majoroperation: intersectionoftid-listsM.Zaki et al.Newalgorithmsforfastdiscoveryofassociationrules. InKDD97P.Shenoyetal.Turbo-chargingverticalminingoflargedataba

37、ses. InSIGMOD002020-03-0131Data Mining:Conceptsand TechniquesBottleneck of Frequent-patternMiningMultipledatabasescansarecostlyMininglongpatternsneedsmany passesofscanningandgenerates lotsofcandidatesTofind frequent itemseti1i2i100# of scans:100# of Candidates: (1001) +(1002) + (110000) =2100-1=1.27

38、*1030!Bottleneck:candidate-generation-and-testCanweavoidcandidate generation?2020-03-0132Data Mining:Conceptsand TechniquesMiningFrequentPatternsWithoutCandidateGenerationGrow longpatternsfromshortones using local frequent items“abc”isa frequent patternGetall transactionshaving“abc”: DB|abc“d”isaloc

39、alfrequentitem in DB|abc abcdisafrequentpattern2020-03-0133Data Mining:Conceptsand TechniquesConstructFP-treefrom aTransactionDatabasef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3min_support= 3TIDItems bought(ordered)frequentitems100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,

40、l,m,of,c,a,b,m300b,f,h,j,o,wf,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,pScan DB once, findfrequent1-itemset (singleitempattern)Sort frequent items in frequencydescending order,f-listScan DB again,constructFP-treeF-list=f-c-a-b-m-p2020-03-0134Data Mining:Conceptsand TechniquesBenefitsoftheFP-treeS

41、tructureCompletenessPreservecompleteinformationforfrequentpatternminingNeverbreaka longpatternofanytransactionCompactnessReduceirrelevantinfoinfrequentitemsare goneItemsinfrequencydescendingorder:the morefrequentlyoccurring, themore likelytobesharedNeverbelargerthantheoriginaldatabase(notcountnode-l

42、inks andthecountfield)ForConnect-4 DB,compressionratiocouldbeover 1002020-03-0135Data Mining:Conceptsand TechniquesPartitionPatternsand DatabasesFrequentpatternscanbepartitionedintosubsets accordingtof-listF-list=f-c-a-b-m-pPatternscontaining pPatternshavingmbutnopPatternshavingcbutnoanorb,m,pPatter

43、n fCompletenessand non-redundency2020-03-0136Data Mining:Conceptsand TechniquesFind Patterns HavingP FromP-conditionalDatabaseStartingatthefrequentitemheadertableinthe FP-treeTraversetheFP-treebyfollowingthe linkofeachfrequentitempAccumulate alloftransformedprefixpathsofitemptoformps conditional pat

44、ternbaseConditionalpattern basesitemcond. patternbasecf:3afc:3bfca:1,f:1, c:1mfca:2,fcab:1pfcam:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p32020-03-0137Data Mining:Conceptsand TechniquesFrom Conditional Pattern-basestoConditionalFP-treesForeachpattern-baseAccum

45、ulate thecountforeachitem in thebaseConstructthe FP-treefor thefrequentitemsofthepatternbasem-conditionalpattern base:fca:2,fcab:1f:3c:3a:3m-conditional FP-treeAllfrequentpatternsrelate tomm, fm,cm, am,fcm, fam,cam,fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p32020-03-

46、0138Data Mining:Conceptsand TechniquesRecursion: MiningEach Conditional FP-treef:3c:3a:3m-conditional FP-treeCond.pattern baseof“am”:(fc:3)f:3c:3am-conditional FP-treeCond.pattern baseof“cm”:(f:3)f:3cm-conditionalFP-treeCond.pattern baseof“cam”: (f:3)f:3cam-conditionalFP-tree2020-03-0139Data Mining:

47、Conceptsand TechniquesA SpecialCase:Single PrefixPath in FP-treeSuppose a(conditional)FP-tree Thas ashared singleprefix-pathPMiningcan be decomposedintotwopartsReductionofthe singleprefixpathinto onenodeConcatenation of theminingresultsofthetwo partsa2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2

48、C3:k3r1+a2:n2a3:n3a1:n1r1=2020-03-0140Data Mining:Conceptsand TechniquesMiningFrequentPatternsWithFP-treesIdea:Frequentpattern growthRecursivelygrow frequent patterns by patternand database partitionMethodForeachfrequentitem,constructits conditional pattern-base,and thenits conditional FP-treeRepeat

49、the processoneachnewlycreated conditional FP-treeUntiltheresulting FP-treeisempty, or it contains onlyone pathsingle pathwillgenerateallthe combinationsofitssub-paths,each of which is afrequentpattern2020-03-0141Data Mining:Conceptsand Techniques算法中文文说明2020-03-0142Data Mining:Conceptsand TechniquesS

50、caling FP-growthbyDBProjectionFP-tree cannotfitinmemory?DBprojectionFirstpartitionadatabaseinto aset of projectedDBsThen constructandmineFP-tree foreach projectedDBParallelprojectionvs.PartitionprojectiontechniquesParallelprojection is space costly2020-03-0143Data Mining:Conceptsand TechniquesPartit

51、ion-basedProjectionParallelprojectionneedsa lotofdisk spacePartitionprojectionsavesitTran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2020-03-0144Data Mining:Conceptsand TechniquesFP-Growthvs. Apriori: Sca

52、lability Withthe SupportThresholdData setT25I20D10K2020-03-0145Data Mining:Conceptsand TechniquesFP-Growthvs. Tree-Projection:ScalabilitywiththeSupportThresholdData setT25I20D100K2020-03-0146Data Mining:Conceptsand TechniquesWhyIsFP-Growth theWinner?Divide-and-conquer:decomposeboththemining taskand

53、DB accordingtothefrequentpatternsobtainedsofarleadstofocused searchofsmaller databasesOtherfactorsnocandidategeneration,nocandidate testcompressed database:FP-tree structurenorepeatedscan of entiredatabasebasicopscountinglocalfreqitemsandbuildingsub FP-tree, no patternsearch andmatching2020-03-0147D

54、ata Mining:Conceptsand TechniquesImplicationsofthe MethodologyMiningclosed frequent itemsets andmax-patternsCLOSET(DMKD00)MiningsequentialpatternsFreeSpan(KDD00),PrefixSpan(ICDE01)Constraint-based miningoffrequentpatternsConvertibleconstraints(KDD00,ICDE01)Computingicebergdata cubes withcomplexmeasu

55、resH-treeand H-cubing algorithm(SIGMOD01)2020-03-0148Data Mining:Conceptsand TechniquesMax-patternsFrequentpattern a1, , a100(1001) +(1002) + (110000) =2100-1=1.27*1030frequentsub-patterns!Max-pattern:frequentpatternswithoutproperfrequentsuperpatternBCDE,ACDare max-patternsBCDisnot amax-patternTidIt

56、ems10A,B,C,D,E20B,C,D,E,30A,C,D,FMin_sup=22020-03-0149Data Mining:Conceptsand TechniquesMaxMiner:Mining Max-patterns1stscan:find frequent itemsA,B,C,D,E2ndscan:find supportforAB,AC, AD,AE,ABCDEBC,BD, BE,BCDECD,CE,CDE, DE,SinceBCDE is amax-pattern, no needtocheckBCD,BDE, CDEinlaterscanR.Bayardo.Effic

57、ientlymininglongpatternsfrom databases. InSIGMOD98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,FPotentialmax-patterns2020-03-0150Data Mining:Conceptsand TechniquesFrequentClosedPatternsConf(acd)=100% recordacdonlyForfrequentitemsetX,ifthereexistsnoitemy s.t.everytransactioncontainingX alsocontainsy,thenX is

58、 afrequentclosedpattern“acd”isa frequent closedpatternConcise rep.offreqpatsReduce#ofpatternsandrulesN.Pasquieretal.InICDT99TIDItems10a, c, d, e, f20a, b, e30c, e, f40a, c, d, f50c, e, fMin_sup=22020-03-0151Data Mining:Conceptsand TechniquesMiningFrequentClosed Patterns:CLOSETFlist:listofallfrequent

59、itemsinsupportascendingorderFlist:d-a-f-e-cDividesearch spacePatternshavingdPatternshavingdbutnoa,etc.Find frequent closedpattern recursivelyEverytransactionhavingdalso hascfa cfadisafrequentclosedpatternJ.Pei, J. Han& R. Mao.CLOSET:AnEfficientAlgorithm forMiningFrequentClosed Itemsets,DMKD00.TIDIte

60、ms10a, c, d, e, f20a, b, e30c, e, f40a, c, d, f50c, e, fMin_sup=22020-03-0152Data Mining:Conceptsand TechniquesMiningFrequentClosed Patterns:CHARMUseverticaldataformat: t(AB)=T1, T12, Deriveclosed patternbasedonverticalintersectionst(X)=t(Y): Xand Yalways happentogethert(X)t(Y):transactionhaving Xal