数据挖掘第六章分析课件.ppt

1、1 1Data Mining: Concepts and Techniques (3rd ed.) Chapter 6 挖掘频繁模式挖掘频繁模式, ,关联和相关性：基本概念和方法关联和相关性：基本概念和方法什么是频繁模式分析？什么是频繁模式分析？n频繁模式(frequent pattern)是频繁地出现在数据集中模式(如项集,子序列或子结构)。n频繁项集是频繁出现在交易数据集中的商品（如牛奶和面包，啤酒和尿布）的集合。n频繁的序列模式是（PC-数码相机-内存卡）这种频繁出现在购物的历史数据库中的序列。n频繁的结构模式是频繁出现的子结构。2什么是频繁模式分析？什么是频繁模式分析？n动机：寻找数据

2、的内在规律n经常购买的是什么产品都在一起 牛奶和面包，啤酒和尿布？n什么是购买一台PC后，后续的购买?n应用n挖掘数据之间的关联、相关性、和其他有趣的联系，及购物篮分析, 交差营销, 价目表设置,销售活动分析, 网络点击量分析。36.1 基本概念基本概念n频繁模式(关联规则)挖掘：n找出给定数据集中反复出现的联系n从事务数据库、关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、项与项之间的关联或相关性。n应用：n购物篮分析：分类设计、捆绑销售和亏本销售分析6.1.1 购物篮分析：一个诱发例子购物篮分析：一个诱发例子 采用关联模型比较典型的案例是“尿布与啤酒”的故事。 在

3、美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析购物篮分析n利用频繁模式可以制定营销计划来提高销售量，具体如下： 1、对商店的顾客事务零售数据进行分析 2、根据得到的有趣的关联设计营销策略： a、经常同时购买的商品摆放在一起，一遍刺激这些商品 同时销售 b、将同时购买的商品放在商店的两端，可以诱发顾客购 买沿途看到的商品（可以通过降价吸引顾客）购物篮分析购物篮分析n

4、如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（如形式0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示n关联规则的两个兴趣度度量computer=financial_management_softwaresupport=2%.confidence=60%n支持度：有用性；指两者被同时购买的概率n置信度：确定性；指购买A的顾客也购买B产品的概率6.1.2 频繁项集频繁项集,闭项集和关联规则闭项集和关联规则n给定：给定：n项的集合：项的集合：I=

5、i1,i2,.,inn每个事务每个事务T 则是项的集合，使得则是项的集合，使得 ；每个事务由事务标；每个事务由事务标识符识符TID 标识；标识；n任务相关数据任务相关数据D 是数据库事务的集合。是数据库事务的集合。nA,B为两个项集，事务为两个项集，事务T包含包含A，当且仅当当且仅当 ；n则关联规则是如下蕴涵式：则关联规则是如下蕴涵式：n其中其中 并且并且 ，规则，规则 在事务在事务集集D 中成立，并且具有支持度中成立，并且具有支持度s 和置信度和置信度cIT TA , csBA IBIA , BABA 规则度量：支持度和置信度规则度量：支持度和置信度n对于A-B支持度支持度：P(A B)，既

6、有A又有B的概率置信度置信度：P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)n例如购物篮分析：牛奶面包例子：支持度：3%，置信度：40%支持度3%：意味着3%顾客同时购买牛奶和面包置信度40%：意味着购买牛奶的顾客40%也购买面包规则度量：支持度和置信度规则度量：支持度和置信度n对所有满足最小支持度和置信度的关联规则n支持度s是指事务集D中包含 的百分比n置信度c是指D中包含A的事务同时也包含B的百分比n假设最小支持度为50%，最小置信度为50%，则有如下关联规则nA C (50%, 66.6%)nC A (50%, 100%)Customerbuys diaperCust

7、omerbuys bothCustomerbuys beerBA)( )(supBAPBAport)(/ )()|( )( APBAPABPBAconfidence标识符标识符大型数据库关联规则挖掘过程大型数据库关联规则挖掘过程n基本概念nk k项集项集：包含k个项的集合n牛奶，面包，黄油是个3项集n项集的频率项集的频率 是指包含项集的事务数n如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集频繁项集n大型数据库中的关联规则挖掘包含两个过程：n找出所有频繁项集n这些项集的出现次数至少与预定的最小支持计数min_sup一样，大部分的计算都集中在这一步n由频繁项集产生强关联规则n

8、即满足最小支持度和最小置信度的规则6.2 有效的和可伸缩的频繁项集挖掘方法n最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。n对规则AC，其支持度=50%n置信度:%6 .66)(sup/ )(sup)(/ )()|( )( AportCAportAPCAPACPCAconfidenceTransactionID ItemsBought2000A,B,C1000A,C4000A,D5000B,E,FFrequentItemset SupportA75%B50%C50%A,C50%最小支持度 50%最小置信度 50%)( )(supCAPCAport6.2Apriori算法算法n频繁项集

9、两个定理： 1）频繁项子集定理：频繁项集的子集都是频繁 项集，而非频繁项的超集都是非频繁项集。 2）频繁项集的合并/连接定理：由k-1项集，向k项集进行合并。当两个k-1项集，拥有k-2个相同元素时，才能合并成k项集。n如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。n同时满足最小支持度阈值和最小置信度阈值的规则称为强规则6.2.1 Apriori算法算法nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。n先找到频繁1-项集

10、集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。nApriori性质：根据项集I不满足最小支持度阈值min_sup,则I不是频繁的，即P(I)minn_sup 频繁项集的所有非空子集也必须是频繁的。（频繁项集的所有非空子集也必须是频繁的。（ 将项将项A添加到项集添加到项集I中，模式中，模式IA不可能比不可能比I更频繁的出现）更频繁的出现）nApriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。Apriori算法步骤算法步骤nApriori算法由连接连接和剪枝剪枝两个步骤组成。n连接

11、：连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选候选k项集项集记为Ck。nLk-1中的两个元素L1和L2可以执行连接操作 的条件是nCk是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。n为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll Apriori算法步骤算法步骤n首先，找出频繁“1项集”

12、的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。n核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。Apriori算法步骤算法步骤n简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集，重复步骤（1）（5）直到不能发现更大的频集。n2、产生关联规则，过程为:

13、根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果P（L）/P（S）min_conf则输出规则“SL-S”注：L-S表示在项集L中除去S子集的项集Apriori算法例6.3Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1

14、A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E2使用Apiori性质由L2产生C3n1 连接：连接：nC3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,En2使用使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对性质剪枝：频繁项集的所有子集必须是频繁的，对候选项候选项C3，我们可以删除其子集为非频繁的选项：，我们可以删除其子集为非频繁的选项：nA,B,C的的2项子集是项子集是A,B,A,C,B,C，其中，其中A,B不是

15、不是L2的的元素，所以删除这个选项；元素，所以删除这个选项；nA,C,E的的2项子集是项子集是A,C,A,E,C,E，其中，其中A,E 不是不是L2的的元素，所以删除这个选项；元素，所以删除这个选项；nB,C,E的的2项子集是项子集是B,C,B,E,C,E，它的所有，它的所有2项子集项子集都是都是L2的元素，因此保留这个选项。的元素，因此保留这个选项。n3这样，剪枝后得到这样，剪枝后得到C3=B,C,E图图6-3 :由由L2产生和剪枝候选产生和剪枝候选3项集的集合项集的集合C3Pseudo-code:Ck:CandidateitemsetofsizekLk:frequentitemsetofs

16、izek L1=frequentitems;for (k=1;Lk!=;k+)do beginCk+1=candidatesgeneratedfromLk;for eachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_support endreturnkLk;图图6-4 Apriori算法算法6.2.2由频繁项集产生关联规则由频繁项集产生关联规则n同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支

17、持度要求，而其置信度则可由一下公式计算：n每个关联规则可由如下过程产生：n对于每个频繁项集L，产生L的所有非空子集；n对于每个非空子集s，如果 则输出规则 “ ”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls例例 :6.4 p164 6.2.3 提高提高Apriori算法的效率算法的效率(1)nApriori算法主要的挑战算法主要的挑战n要对数据进行多次扫描；n会产生大量的候选项集；n对候选项集的支持度计算非常繁琐；n解决思路解决思路n减少对数据

18、的扫描次数；n缩小产生的候选项集；n改进对候选项集的支持度计算方法n方法方法1：基于：基于hash表的项集计数表的项集计数n将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高提高Apriori算法的效率算法的效率(2)n方法方法2：事务压缩：事务压缩（压缩进一步迭代的事务数）n不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。n方法方法3：划分：划分n挖掘频繁项集只需要两次数据扫描nD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。n第一次扫描：将数据

19、划分为多个部分并找到局部频繁项集n第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集提高Apriori算法的有效性(3)n方法方法4：选样：选样（在给定数据的一个子集挖掘）n基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式n通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式n可以通过一次全局扫描来验证从样本中发现的模式n可以通过第二此全局扫描来找到遗漏的模式n方法方法5：动态项集计数：动态项集计数n在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则可以直接将它添加

20、到频繁项集，而不必在这次扫描的以后对比中继续计算6.2.4挖掘频繁模式增长的方法挖掘频繁模式增长的方法nApriori的候选-产生机制显著压缩了候选项集的大小，并导致的很好的性能，但是也有一些缺点，比如说当数据量很大的时候，候选集将会非常的大(划分方法可以避免这一点)；并且需要多次扫描数据库(划分应该是一个非常好的方法)。所以一种称作“频繁模式增长”或简称FP增长(FP Growth)的方法应运而生了。它采用分治策略，将提供频繁项的数据库压缩到一颗频繁模式树中，但仍保留项集的相关信息。然后将压缩后的数据库划分成一组条一组条件数据库件数据库 ，每个关联一个频繁项或模式段，并分别挖掘每个条件数据库

21、。6.2.4挖掘频繁模式增长（挖掘频繁模式增长（FP-增长）的方法增长）的方法特点：不产生侯选频繁项集过程：1、产生频繁1-项集L，并按照其支持度记数降序排列2、构造FP-树：扫描数据库中的每个事务，对每个事务按照L中的次序构造树的分支3、对FP-树进行挖掘：从L的底端开始，依次向上进行。 条件模式基：有路径：,则,是I5的条件模式基。 条件FP-树： 构成的分支是I5的条件FP-树6.2.5使用垂直数据格式挖掘频繁项集使用垂直数据格式挖掘频繁项集Apriori算法和FP-growth算法都是从TID项集格式（即TID:itemset）的事务集中挖掘频繁模式，其中TID是事务标识符，这种数据格

22、式称为水平数据格式。或者，数据可以采用项-TID集格式（即item：TID_set）表示，其中item是项的名称，而TID_set是包含item的事务的标识符的集合。这种格式称为垂直数据格式。6.2.5使用垂直数据格式挖掘频繁项集使用垂直数据格式挖掘频繁项集例6.6使用垂直格式挖掘频繁项集 取每对频繁项的取每对频繁项的TID集的交集的交 一个给定的一个给定的3项集是候选项集是候选3项集，项集， 仅当它的每一个仅当它的每一个2项集子集都是频繁的项集子集都是频繁的 6.3 6.3 哪些模式是有趣的：模式评估方法哪些模式是有趣的：模式评估方法 大部分关联规则挖掘算法都使用支持度-置信度框架，尽管最小

23、支持度和置信度阈值有助于排出大量的无趣规则，但仍会产生一些用户不感兴趣的规则，当使用低支持度阈值挖掘或挖掘长模式时，情况特别严重。这是关联规则挖掘成功应用的主要瓶颈之一。6.3.1 6.3.1 强规则不一定是有趣的强规则不一定是有趣的 强规则为何有可能是无趣的或是误导呢？ 因为规则是否有趣可以主观或客观地评价。最终，只有用户能够评价一个给定的规则是否是有趣的，并且这种判断是主观的，可能因用户而异，然后根据数据“背后”的统计量，客观兴趣度度量可以用来清除无趣的规则，而不向用户提供。无趣规则。例例 6.7 6.7 一个误导的一个误导的“强强”关联规则关联规则 假设我们对分析设计购买计算机游戏和录像

24、的AllElectronics的事务感兴趣。设game表示包含计算机游戏的事务，video表示包含录像的事务。在所分析的10000个事务中，数据显示： 6000个顾客事务包含计算机游戏， 7500个事务包含录像， 4000个事务同时包含计算机游戏和录像。 假设发现关联规则的数据挖掘程序在该数据上运行，使用最小支持率30%，最小置信率60%。将发现下面的关联规则：上述规则是强关联规则，因为它的支持率为4000/10000=40%30%(最小支持率），置信度为4000/6000=66%60%（最小置信率）。然而这个规则是误导，因为购买录像的概率75%66%,而计算机游戏和录像是负相关。 6.3.2

25、 6.3.2 从关联分析到相关分析从关联分析到相关分析 由于支持度和置信度度量不足以过滤掉无趣的关联规则，因此可以由于支持度和置信度度量不足以过滤掉无趣的关联规则，因此可以使用使用相关性度量相关性度量来扩充关联规则的支持度来扩充关联规则的支持度-置信度框架。产生如下相关置信度框架。产生如下相关规则规则相关规则不仅用到了支持度和置信度度量，而且还用项集相关规则不仅用到了支持度和置信度度量，而且还用项集A和和B之间之间的相关性度量。的相关性度量。 提升度（提升度（lift）是一种简单的相关性度量。）是一种简单的相关性度量。A 和和B的提升度可以通过下的提升度可以通过下式得到式得到 lift(A,B

26、)1,A和和B是正相关。是正相关。 lift(A,B)=1,A和和B是独立的。是独立的。 例例6.8 6.8 使用提升度的相关分析使用提升度的相关分析 设设 表示不包含计算机游戏的事务，表示不包含计算机游戏的事务， 表示不包含录像的事务。表示不包含录像的事务。它们之间的相依表如下它们之间的相依表如下:例例6.9 6.9 使用使用 进行相关分析进行相关分析 为了使用为了使用 分析计算相关性，需要相依每个位置上的观测值和期望分析计算相关性，需要相依每个位置上的观测值和期望值（显示在括号内），如表值（显示在括号内），如表6.7所示，所示，由该表计算由该表计算 值如下：值如下：由于由于 的值大于的值大

27、于1，且位置（，且位置（game，video）上的观测值等于）上的观测值等于4000，小，小于期望值于期望值4500，因此购买游戏与购买录像是负相关。，因此购买游戏与购买录像是负相关。6.3.3 6.3.3 模式评估度量比较模式评估度量比较 本节介绍本节介绍4种模式评估度量：全置信度、最大置信度、种模式评估度量：全置信度、最大置信度、Kulczynski和和余弦。然后比较它们的有效性，并与提升度和余弦。然后比较它们的有效性，并与提升度和 进行比较进行比较。 给定两个项集给定两个项集A和和B，A和和B的的全置信度全置信度定义为：定义为：其中，其中，maxsup(A),sup(B)是是A和和B的最

28、大支持度。因此，的最大支持度。因此，all-conf（A,B)又称为两个与又称为两个与A和和B相关的关联规则相关的关联规则 的最小置的最小置信度。信度。 给定两个项集给定两个项集A和和B，A和和B的的最大置信度最大置信度（max_confidence）定义）定义为：为：max_conf是两个规则是两个规则 的最大置信度。的最大置信度。 给定两个项集给定两个项集A和和B，A和和B的的Kulczynski度量定义为：度量定义为：该度量是波兰数学家该度量是波兰数学家S.Kulczynski于于1927年提出的。它可以看做两个置信度年提出的。它可以看做两个置信度的平均值。更确切地说，它是两个条件概率的

29、平均值。的平均值。更确切地说，它是两个条件概率的平均值。 给定两个项集给定两个项集A和和B，A和和B的余弦度量定义为的余弦度量定义为:余弦度量可以看做调和提升度度量：两个公式类似，不同之处在于余弦对余弦度量可以看做调和提升度度量：两个公式类似，不同之处在于余弦对A和和B的概率的乘积取平方根。然而，这是一个重要区别，因为通过取平方根，余的概率的乘积取平方根。然而，这是一个重要区别，因为通过取平方根，余弦值仅受弦值仅受A、B和和AUB的支持度的影响，而不受事务总个数的影响。的支持度的影响，而不受事务总个数的影响。 上面介绍的上面介绍的4种度量都具有如下性质：度量值仅受种度量都具有如下性质：度量值仅

30、受A、B和和AUB的支持度的的支持度的影响，更准确地说，仅受条件概率影响，更准确地说，仅受条件概率P(AlB）和）和P(BlA）的影响，而不受事务总）的影响，而不受事务总个数的影响。另一个共同的性质是，每个度量值都遍取个数的影响。另一个共同的性质是，每个度量值都遍取01，并且值越大，并且值越大，A和和B的联系越紧密。的联系越紧密。 例例6.10 6.10 在典型的数据集上比较在典型的数据集上比较6 6种模式评估度量种模式评估度量 牛奶和咖啡两种商品购买之间的关系可以通过把它们的牛奶和咖啡两种商品购买之间的关系可以通过把它们的购买历史记录汇总在表购买历史记录汇总在表6.86.8的的2 2* *2

31、 2相依表中来考察，其中像相依表中来考察，其中像mcmc这样的表目表示包含牛奶和咖啡的事务个数。这样的表目表示包含牛奶和咖啡的事务个数。 从该表可以看出，从该表可以看出，m m和和c c在数据集在数据集D1D1和和D2D2中是正关联的，在中是正关联的，在D3D3中是负关联的，中是负关联的，而在而在D4D4中是中性的。对于中是中性的。对于D1D1和和D2D2，m m和和c c是正关联的，因为是正关联的，因为mcmc（1000010000）显著）显著大于大于 直观地，对于购买牛奶的人直观地，对于购买牛奶的人（m=10000+1000=11000m=10000+1000=11000）而言，他们非常可

32、能也购买咖啡）而言，他们非常可能也购买咖啡（mc/m=10/11=91%mc/m=10/11=91%），反之亦然。），反之亦然。零事务是不包含任何考察项集的事务。零事务是不包含任何考察项集的事务。例例6.11 6.11 比较模式评估的零不变度量比较模式评估的零不变度量 考察表考察表6.9的数据集的数据集D5和和D6，其中两个事件，其中两个事件m和和c具有不平衡的条件概率。具有不平衡的条件概率。即即mc与与c的比大于的比大于0.9.这意味，知道这意味，知道c出现将强烈暗示出现将强烈暗示m也出现。也出现。Mc与与m的的比小于比小于0.1，表明，表明m蕴含蕴含c很可能不出现。全置信度和余弦度量把两种

33、情况很可能不出现。全置信度和余弦度量把两种情况都看做负关联的，而都看做负关联的，而Kluc度量把两者都视为中性的。最大置信度度量声称度量把两者都视为中性的。最大置信度度量声称这些情况都是强正关联的。这些情况都是强正关联的。 总之，仅使用支持度和置信度度量来挖掘关联可能产生大量规则，其中总之，仅使用支持度和置信度度量来挖掘关联可能产生大量规则，其中大部分规则用户是不感兴趣的。或者，我们可以用模式兴趣度度量来扩展大部分规则用户是不感兴趣的。或者，我们可以用模式兴趣度度量来扩展支持度支持度-置信度框架，有助于把挖掘聚焦到具有强模式联系的规则。附加的置信度框架，有助于把挖掘聚焦到具有强模式联系的规则。

34、附加的度量显著地减少了所产生规则的数量，并且导致更有意义规则的发现。除度量显著地减少了所产生规则的数量，并且导致更有意义规则的发现。除了本书介绍的相关性度量外，文献中还研究了许多其他兴趣的度量。不幸了本书介绍的相关性度量外，文献中还研究了许多其他兴趣的度量。不幸的是，大部分度量都不具有零不变性，由于大型数据集常常具有许多零事的是，大部分度量都不具有零不变性，由于大型数据集常常具有许多零事务，因此在进行相关分析选择合适的兴趣度量时，考虑零不变性是重要的。务，因此在进行相关分析选择合适的兴趣度量时，考虑零不变性是重要的。这里研究的这里研究的4个零不变的度量（即，全置信度、最大置信度、个零不变的度量

35、（即，全置信度、最大置信度、Kulczynski和余弦）中，我们推荐和余弦）中，我们推荐Kluc与不平衡比配合使用。与不平衡比配合使用。6.4 6.4 小结小结l 大量数据中的频繁模式、关联和相关关系的发现在选择性销售、决策大量数据中的频繁模式、关联和相关关系的发现在选择性销售、决策分析和商务管理方面是有用的。一个流行的应用领域是购物篮分析，通分析和商务管理方面是有用的。一个流行的应用领域是购物篮分析，通过搜索经常在一起购买的商品的集合，研究顾客的购买习惯。过搜索经常在一起购买的商品的集合，研究顾客的购买习惯。l 关联规则挖掘首先找出频繁项集（项的集合，如关联规则挖掘首先找出频繁项集（项的集合

36、，如A A和和B B，满足最小支持度，满足最小支持度阈值，或任务相关组的百分比），然后，由它们产生形如阈值，或任务相关组的百分比），然后，由它们产生形如A BA B的强的强关联规则。这些归则还满足最小置信度阈值。进一步分析关联，发现项关联规则。这些归则还满足最小置信度阈值。进一步分析关联，发现项集集A A和和B B之间具有统计相关性的相关规则。之间具有统计相关性的相关规则。l 对于频繁项集挖掘，已经开发了许多有效的、可伸缩的算法，由它们可对于频繁项集挖掘，已经开发了许多有效的、可伸缩的算法，由它们可以导出关联和相关规则，这些算法可分为三类以导出关联和相关规则，这些算法可分为三类（1 1）类）类

37、AprioriApriori算法；（算法；（2 2）基于频繁模式增长的算法，如基于频繁模式增长的算法，如FP-growthFP-growth；（；（3 3）使用垂直数据格式的算）使用垂直数据格式的算法。法。l AprioriApriori算法是为布尔关联规则挖掘频繁项集的原创性算法。它逐层进行算法是为布尔关联规则挖掘频繁项集的原创性算法。它逐层进行挖掘，利用先验性质：频繁项集的所有非空子集也是频繁的，在第挖掘，利用先验性质：频繁项集的所有非空子集也是频繁的，在第k k 次次迭代，它根据频繁（迭代，它根据频繁（k-1)k-1)项集形成项集形成k k项集候选，并扫描数据库一次，找出项集候选，并扫描

38、数据库一次，找出完整的频繁完整的频繁k k项集的集合项集的集合LkLk。使用涉及散列和事务压缩技术的变形使得过。使用涉及散列和事务压缩技术的变形使得过程更有效。其他变形包括划分数据（对每分区挖掘，然后合并结果）和程更有效。其他变形包括划分数据（对每分区挖掘，然后合并结果）和抽样数据（对数据子集挖掘）。这些变形可以将数据扫描次数减少到一抽样数据（对数据子集挖掘）。这些变形可以将数据扫描次数减少到一两次。两次。l 频繁模式增长是一种不产生候选的挖掘频繁项集方法。它构造一个高频繁模式增长是一种不产生候选的挖掘频繁项集方法。它构造一个高度压缩的数据结构，压缩原来的事务数据库。与类度压缩的数据结构，压缩

39、原来的事务数据库。与类AprioriApriori方法使用昌方法使用昌盛盛- -测试策略不同，它聚焦于频繁模式增长，避免了高代价的候选产生，测试策略不同，它聚焦于频繁模式增长，避免了高代价的候选产生，可获得更好的效率。可获得更好的效率。l 使用垂直数据格式挖掘频繁模式将给定的、用使用垂直数据格式挖掘频繁模式将给定的、用TID-TID-项集形式的水平数项集形式的水平数据格式书屋数据集变换成项据格式书屋数据集变换成项TID-TID-集合形式的垂直数据格式。它根据集合形式的垂直数据格式。它根据先验性质和附加的优化技术，通过取先验性质和附加的优化技术，通过取TID-TID-集的交，对变换后的数据集集的

40、交，对变换后的数据集进行挖掘。进行挖掘。l 并非所有的强关联规则都是有趣的。因此，应当用模式评估度量来扩并非所有的强关联规则都是有趣的。因此，应当用模式评估度量来扩展支持度展支持度- -置信度框架，促进更有趣的规则挖掘，以产生更有意义的相置信度框架，促进更有趣的规则挖掘，以产生更有意义的相关规则。一种度量是零不变的，如果它的值不受零事务的影响。在许关规则。一种度量是零不变的，如果它的值不受零事务的影响。在许多模式评估度量中，我们考察了提升度、多模式评估度量中，我们考察了提升度、 、全置信度、最大置信度、全置信度、最大置信度、KulczynskiKulczynski和余弦，并且说明只有后和余弦，并且说明只有后4 4种是零不变的。我们建议把种是零不变的。我们建议把KulczynskiKulczynski度量与不平衡比一起使用，提供项集间的模式联系。度量与不平衡比一起使用，提供项集间的模式联系。