1、关联规则分析-大型数据库中关联规则挖掘大型数据库中关联规则挖掘 （概念描述、关联规则分析、分类、预测、聚类及孤立点分析等等）用DMQL深入学习各种数据挖掘功能之二什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。q主要的兴趣度度量指标有两个：置信度、支持度，如果一个模式既满足支持度和置信度要求，则称这个模式为强关联规则。n应用：q购物篮分析、分类设计、捆绑销售和亏本销售分析举例一：“尿布与啤酒”隐藏的典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超
2、市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。举例二：购物篮分析n如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示。 思考：这种布尔购物篮有什么缺陷？影响挖掘结果吗？n关联规则的两个兴趣度度量q支持度q置信度关联
3、规则：基本概念n给定：q项的集合（进行关联分析时问题的邻域所包含的项的集合）：I=i1,i2,.,inq任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 。例如每个事务就是购买的一个订单，每个订单记录的是购买的哪些商品的信息，项的集合就是商店里所有商品种类的集合，每个订单就是关于这个订单中购买的商品种类的集合。 这样，一个订单中购买商品种类总是被商场所有商品种类的集合所包含。q为了进行关联规则分析，我们将每个事务由事务标识符TID标识；qA,B为两个项集，事务T包含A当且仅当 ，一般分析两个项集。n则关联规则是如下蕴涵式：q其中 并且 （空集），表示规则 在事务集D中成立，并且具
4、有支持度s和置信度cIT TA , csBA IBIA , BABA规则度量：支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beern对所有满足最小支持度和置信度的关联规则q支持度支持度s s是指事务集是指事务集D D中包中包含含 的百分比的百分比q注意： 不是或，是模式间的连接，是unionq置信度置信度c c是指是指D D中包含中包含A A的事的事务同时也包含务同时也包含B B的百分比的百分比n假设最小支持度为50%，最小置信度为50%，则有如下关联规则qA C (50%, 66.6%)qC A (50%, 100%)BA)
5、( )(supportBAPBA)(/ )()|( )( APBAPABPBAconfidence大型数据库关联规则挖掘中如何降低计算复杂度，提高关联规则效率n基本概念qk k项集项集：包含k个项的集合n牛奶，面包，黄油是个3项集q项集的频率项集的频率是指包含项集的事务数占总的事务数的百分比q如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集频繁项集（即满足最小支持度要求的项集）n大型数据库中的关联规则挖掘包含两个过程：q找出所有频繁项集n涉及到大量数据读取和计算，所以大部分的计算都集中在这一步，完成后找到的项集其本身已经满足了最小支持度规则q由频繁项集产生强关联规则n即满足
6、最小支持度和最小置信度的规则关联规则挖掘一个线路图n关联规则有多种分类：关联规则有多种分类：q1、根据规则中所处理的值类型n布尔关联规则（用布尔值01表示）n量化的关联规则（对各个维进行量化衡量，不是简单的01表示）q2、根据规则中设计的数据维n单维关联规则n多维关联规则（如上例，涉及到年龄、收入和购买三个维的关联规则）) ,( ) 48.42 ,( ) 39.30 ,( computerXbuyskkXincomeXage) ,( ) ,( softwareXbuyscomputerXbuysq3、根据规则集所涉及的抽象层n单层关联规则（关联规则表达时不涉及到概念分层）n多层关联规则（关联规
7、则表达时涉及到概念分层，其内部隐含有概念分层的关系）q4、根据关联挖掘的各种扩充n挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的，意味着这个模式是最大的频繁模式）n挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c，意味着c的任何一个真超集都不可能是频繁的，我们就说c是频繁闭项集）) _ ,( ) 39.30 ,( computerlaptopXbuysXage) ,( )39.30 ,( computerXbuysXage由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘，而且我们的举例尽量不涉及概念分层。T
8、ransaction ID Items Bought2000A,B,C1000A,C4000A,D5000B,E,FFrequent Itemset SupportA75%B50%C50%A,C50%首先挖掘频繁项集，其前提条件是：最小支持度 50%，且最小置信度 50%n对规则A C，其支持度 =50%n置信度分A推导C和由C推导A，以A推导C为例：%6.66)(support/)(support)(/)()|( )( ACAAPCAPACPCAconfidence)( )(supportCAPCAApriori算法（计算大型数据库时挖掘关联规则的常用算法之一）nApriori算法利用频繁项
9、集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集（通过先验知识挖掘未知知识）。q先找到频繁1-项集集合（即单个项出现的频率）L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描，过程用到下面性质。nApriori性质：频繁项集的所有非空子集也必须是频频繁项集的所有非空子集也必须是频繁的。（繁的。（ 模式不可能比模式不可能比A A更频繁的出现，更频繁的出现，即即A A与与B B的非空交集不可能比的非空交集不可能比A A大，只能被包含）大，只能被
10、包含）qApriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集超集（注意超集与真超集概念是怎么样的？（注意超集与真超集概念是怎么样的？其定义与子集相对！）其定义与子集相对！）也不能通过相同的测试。BAApriori算法步骤nApriori算法由连接连接和剪枝剪枝两个步骤组成。n连接：连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。qLk-1中的两个元素L1和L2可以执行连接操作 的条件是nCk是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到
11、Lk 。q为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll Apriori算法示例（如何挖掘满足最小支持度的关联的频繁项集）Database TDB1st scanC1L1L2C2C22rd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA
12、, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2注意：我们假设最小支持度是50%，则最小支持计数是2个，则L1时删除D，则任何包含D的超集其出现次数都不可能再超过1次，即Apriori性质所讲的内容。剪剪枝枝结结果果连接！连接！最终，挖掘出最终，挖掘出2项集中项集中4个个和和3项集中项集中1个频繁项集！个频繁项集！C3Itemset不在不在L2中中A,B,CA,BB,C,E都在都在A,C,EA,E连接！连接！A
13、priori算法示例使用Apiori性质由L2产生C3n1 1 连接：至少有一个元素相同时，才能进行两两连接连接：至少有一个元素相同时，才能进行两两连接qC3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E， 我们认为任何频繁的三项集都包含在此C3中！n2 2使用使用AprioriApriori性质剪枝：频繁项集的所有子集必须是频繁性质剪枝：频繁项集的所有子集必须是频繁的，对候选项的，对候选项C C3 3，我们可以删除其子集为非频繁的选项：，我们可以删除其子集为非频繁的选项：qA,B,C的2项子集是A,B,A,C,B,C，其中A
14、,B不是L2的元素，所以删除这个选项；qA,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项；qB,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。n3 3这样，剪枝后得到这样，剪枝后得到C C3 3=B,C,E=B,C,EApriori算法示例由频繁项集产生关联规则n同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：n每个关联规则可由如下过程产生：q对于每个频繁项集 l，产生 l 的所有非空子集；q对于每个非空子集s，如果 则输出规则“ ”)(_
15、sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(slsApriori算法用伪码表示其形式：n基本思路步骤为：基本思路步骤为： 算法：算法：Apriori使用根据候选生成的逐层迭代找出频繁项表 输入：输入：与任务相关的事务数据库D；最小支持临界值min_sup 输出输出：D中的频繁项集Ln具体代码，略。代码了解即可，但要掌握Apriori算法的计算思想。提高Apriori算法的有效性(1)nApriori算法主要的挑战q要对数据进行多次扫描；q会产生大量的候选项
16、集；q对候选项集的支持度计算非常繁琐；n解决思路q减少对数据的扫描次数；q缩小产生的候选项集；q改进对候选项集的支持度计算方法n方法1：基于hash表的项集计数q将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集计数跟最小支持计数相比较先淘汰一部分项集。可以发现：同一个项集只能放在同一个桶中，虽然一个桶中可能包含多个项集。如果桶内模式计数总数达不到最小计数要求，则这个桶中任意模式都达不到计数要求，那么我们直接删掉该桶。q通过hash表方法可以先排除一部分不满足条件的项集。提高Apriori算法的有效性(2)n方法2：事务压缩（压缩进一步迭代的事务数）q不包
17、含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除，因为连k项集都不满足要求，那么由k项集生成的(k+1)项集肯定也不满足。如果一个子集是不频繁的，那么它的任何一个真超子集也是不频繁的。n方法3：划分（常用方法）q最大优势，显著提高效率：挖掘频繁项集只需两次数据扫描。q基本思想是将一个大的数据段划分为n个小数据段（可以非均匀划分）qD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。q第一次扫描：将数据划分为多个部分并找到局部频繁项集（模式在这个段的局部范围它出现的次数必须大于最小支持度*该段的总事务数）q第二次扫描：评估每个局部频繁项集的实
18、际支持度，以确定这个局部频繁项集是否是全局频繁项集提高Apriori算法的有效性(3)n方法4：选样（因为我们是要挖掘大部分的频繁模式，而不是必须挖掘全部有用模式，所以选样选的好的话会在保持一定精确度基础上大大提高效率，然而选样仍会丢失部分频繁模式）q基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式q通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式q在选样基础上通过两次扫描来提高Apriori算法的精确性q可以通过第一次全局扫描来验证从样本中发现的模式是否满足最小支持度的要求q可以通过第二次全
19、局扫描来找到遗漏的模式n方法5：动态项集计数q在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算，即将其提前作为合格的候选模式。不产生候选频繁项集的算法FP树nApriori算法的主要开销：q可能要产生大量的候选项集n104个频繁1-项集会导致107个频繁2-项集n长度100的频繁模式，会产生2100(10的30次数量级)个候选项集q需要将候选项集中的模式跟数据库中已有的模式进行对比，重复扫描数据库，通过模式匹配模式匹配检查一个很大的候选集合n不产生候选频繁项集的算法FP-树频集算法q一种采用divide
20、and conquer（分治策略）的方法n第一步：在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息；n第二步：将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。示例：从数据库构建一个FP树nullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3取整得：取整得：min_sup= 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i,
21、m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, of, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p步骤:1.扫描一次数据库，导出频繁项的集合（即频繁的1-项集集合，用group by count）2.将频繁项按降序排列3.再次扫描数据库，构建出FP树，方法如下所述：假设：假设：min_support= 0.5则：则：min_sup= 0.5*5=2.5FP树的构建（第二次扫描数据库）1.创建树的根节点，用null标记；2.
22、将每个事务中的项按递减支持度计数排列，并对每个事务创建一个分枝；q比如为第一个事务f, c, a, m, p构建一个分枝3.当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1，为跟随前缀后的项创建节点并连接q比如将第二个事务f, c, a, b, m加到树上时，将为f，c，a各增计数1，然后为b, m创建分枝4.创建一个项头表，以方便遍历，每个项通过一个节点链指向它在树中的出现。FP树结构的优点：n完整性q不会打破任何事务数据中的长模式q为频繁模式的挖掘保留了完整的信息n紧凑性q减少了不相关的信息非频繁的项被删除q按频率递减排列使得更频繁的项更容易在树结构中被共享q数据量比原数据库要
23、小FP树挖掘nFP树的挖掘步骤：q由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成。q构造该初始后缀模式的条件FP树，并递归的在该树上实现挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。FP树挖掘从FP树得到条件模式基n从项头表开始挖掘，由频率低的节点开始，自顶端往下查询，找出与该节点相关的条件模式基（注意顶端节点无条件模式基）n沿循每个（频繁）项的链接来遍历FP树n通过积累该项的前缀路径来形成一个条件模式基Conditional pattern basesitemcond. pattern basecf
24、:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1nullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3注意：我们得不到顶端端点f的条件模式基，因为任何模式都是由它开头的FP树挖掘由条件模式基构建条件FP树，最后，再由条件FP树得出频繁模式n对每个条件模式基q为基中的每一项累积计数q为模式基中的频繁项构建FP树m-条件模式基包含条件模式基包含:fca:2, fcab:1f:3c:3a:3m-条件条件FP-树树则得到则得到fcam是满足了最是满足了最小
25、计数为小计数为3的频繁模式的频繁模式 最后：得出关于最后：得出关于m的所的所有频繁模式，以便找出有频繁模式，以便找出最终的关联规则，并且最终的关联规则，并且知道其累积计数：知道其累积计数：m, fm, cm, am, fcm, fam, cam, fcamnullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3b:1(删除)总结：总结：FP-树挖掘可以避免产生候选频繁模式集树挖掘可以避免产生候选频繁模式集大型数据库中更加复杂的关联规则挖掘n由事务数据库挖掘多层关联规则n由关系数据库和数据仓库挖掘多维关
26、联规则n由关联挖掘到相关分析（兴趣度衡量）n基于约束的关联挖掘（加约束减少数据扫描运算）区别于之前单层单维的关联规则挖掘，其多层多维区别于之前单层单维的关联规则挖掘，其多层多维关联规则挖掘的主要内容为：关联规则挖掘的主要内容为：什么是多层关联规则n数据项中经常会形成概念分层n底层的数据项，其支持度往往也较低（一个节点支持度是其所有子节点支持度之和）n在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的，不一定等级越高越有用n通常，事务数据库中的数据也是根据维和概念分层来进行储存的n在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力，即挖掘出来的模式应该能够在各
27、个不同抽象层之间灵活转化，便于用户灵活考察AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTID ItemsT1IBM D/C, Sony b/wT2 Ms. edu. Sw., Ms. fin. Sw.T3 Logi. mouse, Ergoway wrist padT4IBM D/C, Ms. Fin. Sw.T5IBM D/CErgoway挖掘多层关联规则的方法n通常，多层关联规则的挖掘还是使用置信度支持度
28、框架，可以采用自顶向下策略，注意：这种自顶向下的挖掘方法是挖掘了同层的关联规则同层的关联规则。q由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数，顶层频繁才继续考察底层q可以使用Apriori等多种方法q请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度，可作为算法中的先验知识使用q具体做法如下，一层一层往下找，直至支持度不满足要求：n先找高层的关联规则：computer - printer 20%, 60%n再找较低层的关联规则：laptop - color printer 10%, 50%n交叉层关联规则交叉层关联规则q如跨越概念层边界的规
29、则举例：Computer = b/w printerq交叉层关联规则应该使用较低层的最小支持度，而非较高层。根据对每一个层所使用的最小支持度临界值指标将多层关联挖掘方法分为：一致支持度VS.递减支持度n一致支持度：一致支持度：对所有层都使用一致的最小支持度q优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索。简单高效！q缺点：最小支持度值设置太困难，缺点明显超过优点。n太高：将丢掉出现在较低抽象层中有意义的关联规则n太低：会在较高层产生太多的无兴趣的规则n递减支持度：递减支持度：在较低层使用递减的最小支持度q抽象层越低，对应的最小支持度越小Computer
30、support=10%Laptopsupport=6%Desktopsupport=4%第一层min_sup = 5%min_sup = 5%第二层min_sup = 3%多层关联搜索策略（用来找频繁项集的方法）n递减支持度的多层关联规则法可使用三种搜索策略：q逐层独立（逐层独立（太松散太松散）：完全的宽度搜索，每一层的数据只跟当前层的最小支持度做比较，没有频繁项集的背景知识用于剪枝，好处在于方法简单，缺点是条件太松，导致底层需要考察大量非频繁数据，浪费计算多，效率极低q层交叉单项过滤法（层交叉单项过滤法（折中折中）：）：一个第i层的项被考察的条件是，当且仅当它在第（i-1）层的父节点是频繁的
31、，即其满足最小支持度要求。其缺点在于有时父节点不满足当前层的最小支持度，但其子节点却满足他们子节点那一层的最小支持度，这时却被漏掉了考察q层交叉层交叉k k项集过滤（项集过滤（太严格太严格）：）：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的，该方法的强限制性（没几个频繁模式满足该条件），致使很多有趣模式不被考察，进而不被挖掘。n三种搜索策略比较q逐层独立策略条件松，可能导致底层考察大量非频繁项q层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女q层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项受控的层交叉单项过滤策略如何修正、改善折中的过滤
32、策略呢？n人工设置人工设置一个层传递临界值，用于向较低层传递相对频繁相对频繁的项。q即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女（虽然Computer支持度是10%，其不满足层最小支持度12%，但满足临界值8%，那么我们不考察Computer但允许考察其子女Lap和Desk）q用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生Computer support=10%Laptop support=6%Desktop support=4%第一层min_sup = 12%level_passage_support = 8%第二层min_sup
33、= 3%检查冗余的多层关联规则n挖掘多层关联规则时，由于上下层项间的“祖先”关系，祖先对子孙是超集关系，有些发现的规则将是冗余的q例如：ndesktop computer = b/w printer sup=8%, con=70% (1)nIBM desktop computer = b/w printer sup=2%, con=72% (2)n上例中，我们已知第一个规则是第二个规则的“祖先”，如果满足条件： IBM desktop computer在desktop computer中所占的比例是(1/4)刚好等于(2%除以8%)，那么我们认为规则(2)是没什么用的，即冗余的，因为由已知条件
34、“祖先”和“规则1”可以推导出其“后代”规则(2)。即：如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。多维关联规则基本概念n单维关联规则：qbuys(X, “milk”) buys(X, “bread”)，只涉及到buys这单个维n多维关联规则：涉及两个或多个维或谓词的关联规则q第一种：第一种：维间关联规则：不包含重复的谓词nage(X,”19-25”) occupation(X,“student”) = buys(X,“coke”)q第二种：第二种：混合维关联规则：包含某些谓词的多次出现nage(X,”19-2
35、5”) buys(X, “popcorn”) = buys(X, “coke”)n多维关联规则中根据属性值特点分为：分类属性和量化属性q分类属性：具有有限个不同值，值之间无序（例如occupation包含学生、教师、医生等等职业，职业间没有序的关系且个数有限）q量化属性：数值类型的值，并且值之间有一个隐含的序（例如age是19-25岁，但19-25之间有无数个值可挖掘，且有序）挖掘多维关联规则-基本技术n单维关联规则挖掘的是频繁项集，而在多维关联规则挖掘单维关联规则挖掘的是频繁项集，而在多维关联规则挖掘中，我们搜索的不是频繁项集，而是挖掘频繁谓词中，我们搜索的不是频繁项集，而是挖掘频繁谓词集。
36、集。k-谓词集是包含k个合取谓词的集合。q例如：面包、黄油、牛奶是一个buys谓词下的频繁项集，是单维挖掘，而age, occupation, buys是一个3-谓词集，是多维挖掘n挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：n1. 量化属性的静态离散化q使用预定义的概念分层对量化属性进行静态地离散化(例如在age上定义概念分层:青/中/老年，将无穷年龄数据离散化到这三个概念中)n2. 量化关联规则q根据数据的分布，将量化属性离散化到“箱”，类似前面分箱技术n3. 基于距离的关联规则q考虑数据点之间的距离，动态地离散化量化属性，使数据更加符合挖掘需要多维关联规则挖掘方法（1）
37、-使用量化属性的静态离散化n量化属性使用预定义的概念分层，在挖掘前进行离散化n数值属性的值用区间代替q如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描(例如右侧数据立方体中要把age/income/buys这三个维之间的频繁3谓词集找出来，需要扫描数据3或4次)n不同于关系数据库技术，数据立方体技术存放多维数据，其非常适合挖掘多维关联规则qn-维方体的单元用于存放对应n-谓词集的计数或支持度计数或支持度(此时我们存放的不再是第二章中的汇总数据，而是满足这个谓词集条件的出现的计数或者支持度)，0-D方体用于存放任务相关数据的事务总数！n如果包含感兴趣的维的数据
38、立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必频繁谓词集的每个子集也必须是频繁的须是频繁的，例如例如: :若3谓词集是频繁的(age,income,buys)，则(age,income)(age,buys)(income,buys)也一定是频繁的。(income)(age)( )(buys)(age, income)(age,buys) (income,buys)(age,income,buys)多维关联规则挖掘方法（2）-挖掘量化关联规则.An量化关联规则中，数值属性将根据挖掘任务的某种挖掘标准，进行动态的离散化q例如：最大化挖掘规则的置信度和紧
39、凑性n为了简化量化关联规则挖掘的讨论，我们将聚焦于类似以下形式的2-2-维量化关联规则维量化关联规则：Aquan1 Aquan2 Acatq（两个量化属性和一个分类属性间的关联）q例如： age(X,”30-39”) income(X,”42K - 48K”) buys(X,”high resolution TV”)n找出上述这类2-维量化关联规则的方法：关联规则聚类系统(ARCS)q一种源于图像处理的模式识别技术，该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上，然后通过搜索栅格点的聚类而产生关联规则多维关联规则挖掘方法（2）-挖掘量化关联规则.BnARCS过程中的步骤包括q1.
40、分箱（根据不同分箱方法创建一个2-D数组），本步骤的目的在于减少量化属性相对应的巨大的值个数，使得2-D栅格的大小可控n等宽分箱（将变量的取值范围变量的取值范围分为k个等宽的区间，每个区间作为一个分箱）n等深分箱（将变量对象按照个数按照个数等分为k个区间，每个区间作为一个分箱）n基于同质的分箱（每个箱中的元组要符合一致的分布）q2. 找出频繁谓词集n扫描分箱后形成的2-D数组，找出满足最小支持度和置信度的频繁谓词集多维关联规则挖掘方法（2）-关联规则聚类系统(ARCS).C1 q3. 关联规则聚类n将上一步得到的强关联规则映射到2-D栅格上，使用聚类算法，扫描栅格，搜索规则的矩形聚类（借用图形
41、处理中的聚类算法借用图形处理中的聚类算法，通过合并相邻的矩形来实现聚类：如果两个相邻矩形都满足，通过合并相邻的矩形来实现聚类：如果两个相邻矩形都满足最小支持度和置信度，我们就把他们合并最小支持度和置信度，我们就把他们合并）)_ ,()40.31 ,()34,(TVresolutionhighXbuysKKXincomeXage)_ ,()40.31 ,()35,(TVresolutionhighXbuysKKXincomeXage)_ ,()50.41 ,()34,(TVresolutionhighXbuysKKXincomeXage)_ ,()50.41 ,()35,(TVresolutio
42、nhighXbuysKKXincomeXage) _ ,() 50.31 ,()35.34,(TVresolutionhighXbuysKKXincomeXage多维关联规则挖掘方法（2）-关联规则聚类系统(ARCS).C2n所挖掘的关联规则左手边只能是量化属性（非量化属性，无法进行坐标定位）n规则的左手边只能有两个量化属性（受我们使用的是2-D栅格的限制），如果使用3-D、4-D栅格则其虽然量化属性达到3、4个但计算庞大，呈指数级增加，该法适应性局限n改进：一种不基于栅格的，可以发现更一般关联规则的技术，其中任意个数的量化属性和分类属性可以出现在规则的两端（现在数据挖掘技术已经可以发展到可以
43、挖掘任意个数的量化属性和分类属性，并且其可以任意组合出现在规则的左、右手两边）q这种新技术是基于等深分箱动态划分q而且其使根据部分完全性部分完全性的度量进行聚类多维关联规则挖掘方法（2）ARCS的局限性.C3多维关联规则挖掘方法（3）-挖掘基于距离的关联规则n等宽划分将很近的值分开，并创建没有数据的区间，差评！n等深划分将很远的值放在一组，差评！n基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似（等宽/等深/基于距离的划分其距离范围分别为61/46/8，方法3划分的区间少间隔短且其中元素密集，使得我们的计算更加关注在有意义的区间范围内），好评！n基于距离的关联规则挖
44、掘的两遍扫描算法：q1. 使用聚类找出区间或簇（数据分布的区间或者簇）q2. 搜索频繁的一起出现的簇组，得到基于距离的关联规则q3.两步扫描后我们把原始数据映射到很窄的簇组里,再挖掘关联规则n因前面两种方法未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义，如下例中，等深、等宽划分数据都不理想！关联规则的兴趣度度量（主客观度量相结合的方法）n客观度量q两个流行的度量指标n支持度n置信度n主观度量q最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：n它是出人意料的，新颖的n可行动的、可以转换为成果（用户可以
45、使用该规则做某些事情）n挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？甚至说挖掘的强关联规则是否都是正确的呢？对强关联规则的批评（1）n例1：(Aggarwal & Yu, PODS在98年发表的文章)q在5000个学生中n3000个打篮球，3750个喝麦片粥，2000个学生既打篮球又喝麦片粥n根据这个数据可以挖掘出关联规则：打篮球的学生往往就去喝麦片，支持度40%，置信度66.7%。即：打篮球 = 喝麦片粥 40%, 66.7%q然而，打篮球 = 喝麦片粥 40%, 66.7%是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高，说明打篮球跟喝麦
46、片之间不是正相关，而是一种负相关，不存在推导关系。q相反我们可推出，打篮球 = 不喝麦片粥 20%, 33.3%，该规则远比上面那个要精确，尽管支持度和置信度都要低的多却符合实际对强关联规则的批评（2）n例2：q上述数据可以得出buys(X, “computer games”) = buys(X, “videos”) 40%, 60%q但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的，即买游戏后不愿再买录像带，而由数据挖掘出的规则却相反即买游戏后很可能再买录像带。q由此可见强关联规则A = B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵
47、的实际强度。由关联分析到相关分析n我们需要一种度量事件间的相关性或者是依赖性的指标n当项集A的出现独立于项集B的出现时，P(AB)=P(A)P(B)，即corrA,B1，表明A与B无关， corrA,B 1表明A与B正相关， corrA,B buys(X, educational software)nY,W分别取赋给谓词变量P1, P2的属性值n一般，元规则形成一个用户希望探察的假定，而系统则寻找与该元规则匹配的规则，例如：qage(X, 30-39) income(X, 42K - 60K) buys(X, educational software)关联规则的元规则制导挖掘（2）n假定我们希
48、望挖掘的元规则形式为：qP1P2Pl = Q1Q2Qrn设元规则中谓词的个数为p=l+r，则找出符合该模板的关联规则需以下两步骤：q找出所有的频繁p-谓词集Lpq计算Lp中的l-谓词子集的支持度，然后计算由Lp导出的规则的置信度n数据立方体具有存放多聚集维值的能力，因此非常适合挖掘上述具有多个谓词的关联规则的挖掘，在n维数据立方体中(n=p)挖掘上述规则可以用以下步骤：q扫描p-D方体，将每个单元中的计数和最小支持度计数比较，得到Lp，因为p-D方体中存放的不是数据的汇总，而是p维谓词它所出现的概率的计数。q考察l-D方体，返回与元规则匹配的强关联规则用附加的规则约束制导的挖掘n在数据挖掘中，
49、与元规则一起使用的约束还有集合/子集联系，变量初始化和聚集函数等，它们将使挖掘过程更有效，例DMQL表示的数据挖掘任务如下：mine associations as （1、指定的挖掘知识类型） lives(C, _,Vancouver) sales+(C, ?I,S) = sales+(C, ?J,T)（2、用一个元规则来表示我希望挖掘出来的规则的模式）from sales （3、指定相关的数据集） where S.year=1999 and T.year=1999 and I.category=J.categorygroup by C, I.categoryhaving sum(I.pric
50、e)=500（4，指定一系列的条件约束）with support threshold=1%with confidence threshold=50% （5，兴趣度约束）挖掘过程中使用的规则约束n通常的数据挖掘中，知识类型和数据约束在挖掘前挖掘前使用，其它约束在挖掘后挖掘后用来过滤规则，但这使挖掘过程非常低效。n什么类型的规则约束可以在挖掘过程中挖掘过程中使用，以缩小规则搜索空间？n对于频繁项集挖掘，在挖掘过程中使用的约束包括以下五种类型：q反单调的q单调的q简洁的q可转变的q不可转变的反单调的和单调的约束n如果一个项集不满足该规则约束，则它的任何一个超集都不可能满足该约束；具有这种性质的规则称
