文档介绍:关联规则挖掘AssociationRuleMining背景简介(Motivation)超市购物:商场经理可能想了解顾客的购物****惯。例如:“顾客多半会在一次购物时买哪些商品?”。分析的结果可用于市场规划、广告策划和分类设计。文本分类:个性化新闻推荐系统希望对新闻进行分类,推进用户感兴趣类别的新闻内容给用户。系统可以通过挖掘哪些关键词与某个类别经常联系在一起,找出文档的分类标准。信息推荐:电子商务网站推荐用户所需的信息。如:下载某种类型音乐的用户通常具有什么样的特点解决这些问题的一种有效途径就是“AssociationRuleMining”(关联规则挖掘)AssociationRuleMiningGivenasetoftransactions,urrencesofotheritemsinthetransactionMarket-BaskettransactionsExampleofAssociationRules{Diaper}{Beer},{Milk,Bread}{Eggs,Coke},{Beer,Bread}{Milk},Implicationmeansco-occurrence,notcausality!Definition:FrequentItemsetItemsetAcollectionofoneormoreitemsExample:{Milk,Bread,Diaper}k-itemsetAnitemsetthatcontainskitemsSupportcount().({Milk,Bread,Diaper})=({Milk,Bread,Diaper})=2/5FrequentItemsetAnitemsetwhosesupportisgreaterthanorequaltoaminsupthresholdDefinition:AssociationRuleExample:AssociationRuleAnimplicationexpressionoftheformXY,whereXandYareitemsetsExample:{Milk,Diaper}{Beer}RuleEvaluationMetricsSupport(s)FractionoftransactionsthatcontainbothXandYConfidence(c)MeasureshowoftenitemsinYappearintransactionsthatcontainXAssociationRuleMiningTaskGivenasetoftransactionsT,thegoalofassociationruleminingistofindallruleshavingsupport≥minsupthresholdconfidence≥minconfthresholdBrute-forceapproach:putationallyprohibitive!MiningAssociationRulesExampleofRules:{Milk,Diaper}{Beer}(s=,c=){Milk,Beer}{Diaper}(s=,c=){Diaper,Beer}{Milk}(s=,c=){Beer}{Milk,Diaper}(s=,c=){Diaper}{Milk,Beer}(s=,c=){Milk}{Diaper,Beer}(s=,c=)Observations:Alltheaboverulesarebinarypartitionsofthesameitemset: {Milk,Diaper,Beer}RulesoriginatingfromthesameitemsethaveidenticalsupportbutcanhavedifferentconfidenceThus,wemaydecouplethesupportandconfidencerequirementsMiningAssociationRulesTwo-stepapproach:FrequentItemsetGenerationGenerateallitemsetswhosesupportminsupRuleGenerationGeneratehighconfidencerulesfromeachfrequentitemset,putationallyexpensiveFrequentItemsetGener