第4章 数据仓库关联规则

2012/11/6数据仓库与数据挖掘1第4章关联规则2012/11/6数据仓库与数据挖掘2工业控制技术研究所什么是关联挖掘?关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。举例：规则形式：“Bodyead[support,confidence]”.buys(x,“diapers”)buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)grade(x,“A”)[1%,75%]2012/11/6数据仓库与数据挖掘34.1概述一、概述关联规则(AssociationRuleMining)挖掘是数据挖掘中最活跃的研究方法之一。最早是由R.Agrawal等人提出的。其目的是为了发现超市交易数据库中不同商品之间的关联关系。一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。经典的关联规则挖掘算法：Apriori算法和FP-growth算法2012/11/6数据仓库与数据挖掘4关联规则：基本概念给定:(1)交易数据库(2)每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则E.g.,98%ofpeoplewhopurchasetiresandautoaccessoriesalsogetautomotiveservicesdone应用*护理用品(商店应该怎样提高护理用品的销售？)家用电器*(其他商品的库存有什么影响?)2012/11/6数据仓库与数据挖掘54.2引例假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea交易号TID顾客购买商品ItemsT1breadcreammilkteaT2breadcreammilkT3cakemilkT4milkteaT5breadcakemilkT6breadteaT7beermilkteaT8breadteaT9breadcreammilkteaT10breadmilktea2012/11/6数据仓库与数据挖掘64.2引例定义4.1项目与项集设I={i1,i2,…,im}是m个不同项目的集合，每个ik(k=1，2，……，m)称为一个项目(Item)。项目的集合I称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)。举例:超市项集:I={bread,beer,cake,cream,milk,tea}2012/11/6数据仓库与数据挖掘74.2引例定义4.2交易每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。对应每一个交易有一个唯一的标识——交易号，记作TID交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。交易集D中包含交易的个数记为|D|。举例:交易号为T3,是一个2-项集{milk,cake},是I子集.2012/11/6数据仓库与数据挖掘84.2引例定义4.3项集的支持度对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性。|D|T)count(Xsupport(X)2012/11/6数据仓库与数据挖掘94.2引例定义4.4项集的最小支持度与频繁集发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支持度(MinimumSupport)，记为supmin。从统计意义上讲，它表示用户关心的关联规则必须满足的最低重要性。只有满足最小支持度的项集才能产生关联规则。支持度大于或等于supmin的项集称为频繁项集，简称频繁集，反之则称为非频繁集。通常k-项集如果满足supmin，称为k-频繁集，记作Lk。2012/11/6数据仓库与数据挖掘104.2引例定义4.5关联规则关联规则(AssociationRule)可以表示为一个蕴含式：R：XY其中XI，YI，并且XY=。项集X在某一交易中出现，则导致项集Y按照某一概率也在同一交易种出现。X为规则条件，Y为规则结果。2012/11/6数据仓库与数据挖掘114.2引例定义4.6关联规则的支持度对于关联规则R：XY，其中XI,YI，并且XY=，规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。|D|Y)count(XY)support(X2012/11/6数据仓库与数据挖掘124.2引例定义4.7关联规则的可信度对于关联规则R：XY，其中XI,YI，并且XY=，规则R的可信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比support(X)Y)support(XY)(Xconfidence2012/11/6数据仓库与数据挖掘134.2引例定义4.8关联规则的最小支持度和最小可信度关联规则的最小支持度也就是衡量频繁集的最小支持度(MinimumSupport)，记为supmin，它用于衡量规则需要满足的最低重要性。规则的最小可信度(MinimumConfidence)记为confmin，它表示关联规则需要满足的最低可靠性。2012/11/6数据仓库与数据挖掘144.2引例定义4.9强关联规则如果规则XY满足：support(XY)supmin且confidence(XY)confmin，称关联规则XY为强关联规则，否则称关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。2012/11/6数据仓库与数据挖掘15工业控制技术研究所规则度量：支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,包含{X、Y}的交易中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户2012/11/6数据仓库与数据挖掘164.3经典算法一、Apriori算法二、FP-growth算法2012/11/6数据仓库与数据挖掘174.2引例假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea交易号TID顾客购买商品ItemsT1breadcreammilkteaT2breadcreammilkT3cakemilkT4milkteaT5breadcakemilkT6breadteaT7beermilkteaT8breadteaT9breadcreammilkteaT10breadmilktea2012/11/6数据仓库与数据挖掘18一、Apriori算法2012/11/6数据仓库与数据挖掘19一、Apriori算法apriori_gen(Lk-1,supmin)算法2012/11/6数据仓库与数据挖掘20一、Apriori算法has_infrequent_subset(c,Lk-1)算法2012/11/6数据仓库与数据挖掘21二、FP-growth算法定义4.10FP-tree频繁模式树FP-tree是一个树形结构。包括一个频繁项组成的头表，一个标记为“null”的根节点，它的子节点为一个项前缀子树的集合。定义4.11频繁项单个项目的支持度超过最小支持度则称其为频繁项(FrequentItem)。2012/11/6数据仓库与数据挖掘22二、FP-growth算法定义4.12频繁项头表频繁项头表(HeadTable)的每个表项由两个域组成：项目名称item-name和指针node_link。node_link指向FP-tree中具有与该表项相同item-name的第一个节点。定义4.13频繁项头表每个项前缀子树(ItemPrefixSubtree)的节点有三个域：item-name，count，node_link。item-name记录了该节点所代表的项的名字。count记录了所在路径代表的交易中包含此节点项目的交易个数。node_link指向下一个具有同样的item-name域的节点，要是没有这样一个节点，就为null。2012/11/6数据仓库与数据挖掘23二、FP-growth算法第一部分：根据一个输入交易记录集建立一棵FP-tree，其操作步骤如图4.4所示。输入：交易记录集D，最小支持度supmin。输出：FP-tree。（1）扫描数据库D一遍，得到频繁项的集合F和每个频繁项的支持度。把F按支持度递降排序，结果记为L。（2）创建FP-tree的根节点，记为T，并且标记为“null”。然后对DB中的每个交易做如下的步骤：根据L中的顺序，选出并排序Trans中的频繁项。把Trans中排好序的频繁项列表记为[p|P]，其中p是第一个元素，P是列表的剩余部分。调用insert_tree([p|P]，T)。2012/11/6数据仓库与数据挖掘24二、FP-growth算法函数insert_tree([p|P]，T)的运行如下。如果T有一个子结点N，其中N.item-name=p.item-name，则将N的count域值加1；否则，创建一个新节点N，使它的count为1，使它的父节点为T，并且使它的node_link和那些具有相同item_name的域串起来。如果P非空，则递归调用insert_tree(P，N)。2012/11/6数据仓库与数据挖掘254.4相关研究与应用一、分类：基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。基于规则中处理的变量的类型不同，关联规则可以分为布尔型和数值型。2012/11/6数据仓库与数据挖掘26二、SQLServer2005中的关联规则挖掘AdventureWorksDW数据库关联规则发现的详细步骤如下：创建AnalysisServices项目创建数据源创建数据源视图创建关联挖掘结构建立好挖掘模型后，需要设置关联规则挖掘的参数建立关联规则挖掘模型查看挖掘结果