关联规则挖掘

1、数据挖掘与商务智能Data Mining & Business Intelligence第三章第三章 关联规则挖掘关联规则挖掘西安电子科技大学软件学院主讲人：黄健斌内容提纲n关联规则挖掘简介n关联规则基本模型n关联规则挖掘的经典算法Apriori FP-Growthn参考文献. 关联规则简介n关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物发生就能够预测与它相关联的其它事物的发生。n关联规则挖掘的经典范例：购物篮（Market Basket）分析。通过发现顾客放入购物篮中商品之间的同现关系来分析顾客的购买习惯，从而实现商品的

2、交叉销售和推荐。 事务与规则nGiven a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction购物篮事物集合：购物篮事物集合：关联规则示例：关联规则示例：Diaper Beer,Milk, Bread Eggs,Coke,Beer, Bread Milk,Implication means co-occurrence, not causality!蕴含意味着同现而非因果关系！事

3、务集合：所有事务集合事务集合：所有事务集合T=t1,t2, tN项集：所有项的集合项集：所有项的集合I=i1, i2, id事务事务: 若干项组成的集合若干项组成的集合tj=ij1, ij2, , ijkFrequent Itemset 频繁项集nItemset 项项A collection of one or more itemsnExample: Milk, Bread, Diaperk-itemset k-项nAn itemset that contains k itemsnSupport count ( ) 支持度计数支持度计数Frequency of occurrence of an

4、 itemsetE.g. (Milk, Bread,Diaper) = 2 nFrequent Itemset 频繁项集频繁项集An itemset whose support is greater than or equal to a minsup threshold 最小支持度计数(),iiiXt Xt tTAssociation Rule 关联规则()()XYs XYNnAssociation RuleAn implication expression of the form X Y, where X and Y are itemsetsExample: Milk, Diaper Bee

5、r nRule Evaluation MetricsSupport (s) 支持度nFraction of transactions that contain both X and YConfidence (c) 置信度nMeasures how often items in Y appear in transactions thatcontain X()()()XYc XYXDefinition: Association RuleExample:BeerDiaper,Milk4 . 052|T|)BeerDiaper,Milk(s67. 032)Diaper,Milk()BeerDiaper

6、,Milk,(cnAssociation RuleAn implication expression of the form X Y, where X and Y are itemsetsExample: Milk, Diaper Beer nRule Evaluation MetricsSupport (s)nFraction of transactions that contain both X and YConfidence (c)nMeasures how often items in Y appear in transactions thatcontain X规则度量：支持度与置信度

7、信度n规则 X Y 的支持度和可信度支持度支持度 s：一次交易中同时包含X 、 Y 的可能性置信度置信度 c ：包含项X 的交易中同时也包含Y的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为0.5, 最小可信度为 0.5, 则可得到关联规则A C (0.5, 0.67)C A (0.5, 1)买尿布的客户买尿布的客户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户什么是关联规则挖掘n关联规则挖掘 首先被IBM公司Almaden研究中心的R. Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提

8、出在事务、关系数据中发现频繁项集和关联规则频繁项集频繁项集: 事务数据中支持度大于最小支持度阈值minsup的所有项集关联规则关联规则：事务数据中支持度大于最小支持度阈值minsup且置信度大于最小置信度阈值minconf的所有规则什么是关联规则挖掘n关联规则挖掘的意义: 发现数据中的规律超市数据中的什么产品会一起购买？ 啤酒和尿布在得知某用户买了一台PC之后，预测他同时还会购买什么商品?关联规则挖掘nGiven a set of transactions T, the goal of association rule mining is to find all rules having su

9、pport minsup thresholdconfidence minconf thresholdnBrute-force approach 蛮力方法:List all possible association rulesCompute the support and confidence for each rulePrune rules that fail the minsup and minconf thresholds 计算开销极大，无法应用于大规模数据集!关联规则挖掘Example of Rules:Milk,Diaper Beer (s=0.4, c=0.67)Milk,Beer

10、Diaper (s=0.4, c=1.0)Diaper,Beer Milk (s=0.4, c=0.67)Beer Milk,Diaper (s=0.4, c=0.67) Diaper Milk,Beer (s=0.4, c=0.5) Milk Diaper,Beer (s=0.4, c=0.5)Observations 观察到的现象: All the above rules are binary partitions of the same itemset: Milk, Diaper, Beer Rules originating from the same itemset have ide

11、ntical support but can have different confidence Thus, we may decouple the support and confidence requirements关联规则挖掘nTwo-step approach: Frequent Itemset Generation 产生频繁项集Generate all itemsets whose support minsupRule Generation 产生规则Generate high confidence rules from each frequent itemset, where eac

12、h rule is a binary partitioning of a frequent itemsetnFrequent itemset generation is still computationally expensive 产生频繁项集的计算代价依然很高产生频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEGiven d items, there are 2d possible candidate itemsets产生频繁项集nBrute-force appr

13、oach 蛮力法: Each itemset in the lattice is a candidate frequent itemsetCount the support of each candidate by scanning the databaseMatch each transaction against every candidateComplexity O(NMw) = Expensive since M = 2d !计算复杂度nGiven d unique items:Total number of itemsets = 2dTotal number of possible

14、association rules: 1231111dddkkdjjkdkdRIf d=6, R = 602 rules频繁项集产生算法1：ApriorinApriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 nApriori算法将发现关联规则的过程分为两个步骤：检索出事务数据库中的所有频繁项集，即支持度不低于用户设定最小支持度计数阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。n挖掘并产生所有频繁项集是该算法的核心，占整个计算量的大部分。 频繁项集的性质： n性质1：频繁项集的子集必为频繁项集。 n性质2：非频繁项集的超集一定是非频繁的。 nApriori算法运

15、用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。 Found to be Infrequent频繁项集的性质：Pruned supersetsApriori算法n(1) L1=频繁1项集; n(2) for(k=2;Lk-1;k+) do begin n(3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集 n(4) for all transactions tD do begin n(5)

16、 Ct=subset(Ck,t); /t中包含的潜在频繁项集 n(6) for all candidates cCt do n(7) c.count+; n(8) end; n(9) Lk=cCk|c.countminsup n(10) end; n(11) Answer= kkL实例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB,

17、 EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2Visualization of Association Rules: Pane GraphVisualization of Association Rules: Rule Graph提高Apriori算法性能的方法nHash-based itemset counting（散列项集计数）nTransaction reduction（事务压缩）nPartitioning（划分）nSa

18、mpling（采样）n用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘是完备的避免代价较高的数据库扫描n开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则: 只使用部分数据库!频繁项集产生算法2：FP-growth构建FP-treeTIDItems1A,B2B,C,D3A,C,D,E4A,D,E5A,B,C6A,B,C,D7B,C8A,B,C9A,B,D10B,C,EnullA:1B:1nullA:1B:1B:1C:1D:1After reading TID=1:Afte

19、r reading TID=2:构建FP-TreenullA:7B:5B:3C:3D:1C:1D:1C:3D:1D:1E:1E:1TIDItems1A,B2B,C,D3A,C,D,E4A,D,E5A,B,C6A,B,C,D7B,C8A,B,C9A,B,D10B,C,EPointers are used to assist frequent itemset generationD:1E:1Transaction DatabaseItemPointerABCDEHeader tablef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head

20、f4c4a3b3m3p3最小支持度最小支持度 = 0.5TIDItems bought (ordered) frequent items100f, a, c, d, g, i, 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.再一次扫描数据库，建立FP-tree建立简化的FP-tree树：示例n基本思想 (分治)

21、用FP-tree递归增长频繁集n方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空, 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集)用FP-tree挖掘频繁集n从FP-tree的头表开始n按照每个频繁项的连接遍历 FP-treen列出能够到达此项的所有前缀路径，得到条件模式库条件模式库条件模式库itemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b

22、:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤1: 从 FP-tree 到条件模式库n对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库条件模式库:fca:2, fcab:1f:3c:3a:3m-conditional FP-treeAll frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤2

23、: 建立条件 FP-treen完备: 不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息n紧密去除不相关信息不包含非频繁项支持度降序排列: 支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)FP-tree 结构的优点33The Frequent Pattern Growth Mining MethodnIdea: Frequent pattern growth 频繁模式增长Recursively grow frequent patterns by pattern and database partitionnMethod For each fre

24、quent item, construct its conditional pattern-base, and then its conditional FP-treeRepeat the process on each newly created conditional FP-tree Until the resulting FP-tree is empty, or it contains only one pathsingle path will generate all the combinations of its sub-paths, each of which is a frequ

25、ent pattern34FP-Growth vs. Apriori: Scalability With the Support Threshold010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10K2022年3月15日星期二Data Mining: Concepts and Techniques35FP-Growth vs. Tree-Projection: Scalability with

26、the Support Threshold02040608010012014000.511.52Support threshold (%)Runtime (sec.)D2 FP-growthD2 TreeProjectionData set T25I20D100K产生关联规则n任务描述：给定频繁项集Y, 查找Y的所有非空真子集X Y，使得 X Y X 的置信度超过最小置信度阈值minconf例子：If A,B,C is a frequent itemset, 候选规则如下： AB C, AC B, BC AA BC,B AC,C ABn如果 |Y| = k, 那么会有 2k 2 个候选关联规则

27、 (不包括 Y and Y)产生关联规则nHow to efficiently generate rules from frequent itemsets?通常，置信度不满足反单调性（anti-monotone property ），例如：c(ABC D) 可能大于也可能小于 c(AB D)但是，针对同一个频繁项集的关联规则，如果规则的后件满足子集关系，那么这些规则的置信度间满足反单调性e.g., Y= A,B,C,D: c(ABC D) c(AB CD) c(A BCD)Rule Generation for Apriori AlgorithmLattice of rulesPruned R

28、ulesLow Confidence Rule针对Apriori 算法的规则产生方法nCandidate rule is generated by merging two rules that share the same prefixin the rule consequentnjoin(CD=AB,BD=AC)would produce the candidaterule D = ABCnPrune rule D=ABC if itssubset AD=BC does not havehigh confidenceBD=ACCD=ABD=ABC参考文献nAgrawal R, Imielin

29、ski T, and Swami A. Mining association rules between sets of items in large databases. SIGMOD, 207-216, 1993.nAgrawal R, and Srikant R. Fast algorithms for mining association rules in large databases. VLDB, 478-499, 1994. nHan J W, Pei J, Yin Y W. Mining frequent patterns without candidate generatio

30、n. SIGMOD, 1-12, 2000.nHan J W, Pei J, Yin Y W, and Mao R Y. Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery. 8, 53-87, 2004课程安排n通过垂直数据格式挖掘关联规则nECLATn挖掘最大、闭合关联规则模nMaxMinernCLOSETnCLOSETnCHARM第一部分通过垂直数据格式挖掘关联规则ECLAT基本概念n水平数据

31、格式：TID:itemsetn垂直数据格式：item:TID_setTID商品IDT100I1 I2 T200I2 I4T300I2 I3T400I1 I2 I3项TID集I1T100，T400I2T100，T200，T300，T400I3T300，T400I4T200ECLAT:使用垂直数据格式进行挖掘nECLAT：生成-检测模型n剪枝策略：子集不频繁剪枝n算法步骤：1、扫描事务数据库TDB，将水平数据格式转化成垂直数据格式垂直数据格式。2、通过对集合操作，得到满足最小支持度域值min_sup的频繁频繁1项集项集。3、通过频繁k项集产生候选k+1项集，通过集合求集合求交交来产生频繁K+1项集

32、。4、直到不再生成候选项集或不再产生频繁项集，程序结束。算法实例例：TIDList of item IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3构造垂直数据格式：构造垂直数据格式：itemsetTID_setI1T100,T400,T500,T700,T800,T900I2T100,T200,T300,T400,T600,T800,T900I3T300,T500,T600,T700,T800,T900I4T200,T400I5T100,T80

33、0ECLAT构造频繁1项集（min_sup=2）:itemsetTID_setI1T100,T400,T500,T700,T800,T900I2T100,T200,T300,T400,T600,T800,T900I3T300,T500,T600,T700,T800,T900I4T200,T400I5T100,T800ECLATitemsetTID_setI1,I2T100,T400,T800,T900I1,I3T500,T700,T800,T900I1,I4T400I1,I5T100,T800I2,I3T300,T600,T800,T900I2,I4T200,T400I2,I5T100,T80

34、0I3,I5T800构造频繁2项集(min_sup=2):ECLATECLAT直到没有频繁项集或候选项集产生，算法结束课程安排第二部分挖掘最大、闭合关联规则模式 MaxMiner、CLOSET、CLOSET+、CHARMnDB = , min_sup=2;问题：频繁项集有哪些呢250-1 ！？基本概念n最大频繁项集最大频繁项集是这样的频繁项集，它的直接超集都是不频繁的。最大频繁最大频繁项集项集基本概念n闭项集项集X是闭的，如果它的直接超集都不具有和它相同的支持度计数。n频繁闭项集如果项集X是闭的，并且它的支持度计数大于或等于最小支持度阈值min_sup，则项集X是频繁闭项集。最大项集VS闭频繁

35、项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE12412312342453451212424412323243445122244423424闭频繁项集闭频繁项集且最大频繁项集TID项1abc2abcd3bce4acde5deminsup=2TDB频繁项集、最大频繁项集和频繁闭项集之间的关系MaxMiner：挖掘最大模式n完全集合枚举树A (BCD)B (CD)C (D)D ()AB (CD)AC (D) AD ()BC (D) BD ()CD ()ABC (C)ABCD

36、 ()ABD () ACD ()BCD () (ABCD)设TDB中包含有项ABCDMaxMinern剪枝原理子集不频繁剪枝：任何非频繁项集的超集都是非频繁项集；超集频繁剪枝：超集频繁剪枝：任何频繁项集的子集都是频繁项集；n搜索策略广度优先搜索完全集合枚举树广度优先搜索完全集合枚举树MaxMiner算法实例(1/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDEF0A2B2C3D3E2F1Min_sup=2Max patterns:A (BCDE)B (CDE) C (DE)E ()D (E)MaxMiner

37、算法实例(2/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDE1AB1AC2AD2AE1Min_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()Max patterns:Node AMaxMiner算法实例(3/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyBCDE2BCBDBEMin_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()

38、Max patterns:BCDENode BMaxMiner算法实例(4/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyACD2Min_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()Max patterns:BCDEACDNode ACCLOSET ：高效的挖掘频繁闭项集算法n频繁项集列表（f_list）给定事务数据库TDB和最小支持度计数阈值min_sup，将所有的频繁项按照支持度计数递减顺序构成的表。n条件数据库（conditional database）给定

39、一个事务数据库TDB，若项i是一个频繁项。 项i的条件数据库(用TDB|i表示)，是TDB中包含项i的交易构成的子集，并且所有出现的非频繁项、项i和f_list中项i后面的项都删除。构造f_listTIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,f则由f_list定义得到：f_list:设有如下事物数据库TDB(min_sup=2)：首先计算出每个项的支持度计数：a:3,b:1,c:4,d:2,e:4,f:4, 条件数据库的构造TDBcefadeacefcfadceff_list:d-cond DB(d:2)cefacfaa-cond DB(a:

40、3)cefecff-cond DB(f:4)ce:3ce-cond DB(e:4)cCLOSET算法n引理1挖掘所有频繁闭项集的问题可以被分解成n个子问题；第j个问题是找到包含项in+1-j但是不包含ik (n+1-jkn)的完全频繁闭项集。n引理2如果项集X是一个频繁闭项集，则在X条件数据库中不存在项i，使得项i出现在所有的事务中。n引理3在项集X的条件数据库中，Y是每一个事务都出现的项构成的最大的集合，如果X没有以相同的支持度计数被已发现的频繁闭项集融合，则X是一个频繁闭项集。n引理 项融合(item merging)项集X是一个频繁项集，如果每个包含项集X的事务中都包含有项集，而不是项集

41、的任何一个直接超集，则XY构成频繁闭项集并且没有必要再搜索任何包含项集而不含项集的项集。CLOSE算法实例(1/3)选择的事务数据库TIDTIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,f最小支持度计数min_sup=2CLOSE算法实例(2/3)n1、构造f_list计算TDB中每个项的支持度计数，得到：a:3 b:1 c:4 d:2 e:4 f:4 min_sup=2f_list:CLOSE算法实例(3/3)n2、构造条件数据库TDBcefadeacefcfadceff_list:a-cond DB(a:3)cefecff-cond DB(f

42、:4)ce:3ce-cond DB(e:4)cd-cond DB(d:2)cefacfaOutput: cfad:2Output: a:3Output: cf:4;cef:3Output: e:4ea-cond DB(ea:2)cOutput: ea:2 CLOSET+ ：高效的挖掘频繁闭项集方法n混合树投影技术(hybrid tree-projection method)1、自底向上物理的树投影(bottom-up physical tree-projection)-高密度的数据集2、自顶向下伪树投影(top-down pseudo tree-projection)-稀疏数据集Bottom-

43、up physical tree-projectionf4c4a3b3m 3p3rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1(a)Global FP-treec3f2a2m 2f:2c:3m:2a:2root(b)Projected FP-tree with prefix pfcam:2cb:1Top-down pseudo tree-projectionrootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1fcabmp443333(a)Pseudo tree for prefix ffcabmp443333rootf:4c:3c:1m:2b:

44、1b:1b:1p:1a:3p:2m:1(b)Pseudo tree for prefix cHHTop-down pseudo tree-projection for f:4cabmp32232rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hf:4amp332rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3(a)(b)Top-down pseudo tree-projection for f:4amp332rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3amp33

45、2rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3(c)(d)CLOSET+算法n引理1：项的跳跃(Item skipping)若局部频繁项i，在不同层次的一些头表(header tables)中有相同的支持度计数，则可以安全地将项i从较高的层次的头表(header tables)中移除。n定理1：子集检测(Subset checking)在分治框架下，使用项集融合剪枝方法，通过CLOSET+算法得到的频繁项集，如果它不能被其它的任何已找到的频繁闭项集融合，则该项集是频繁项集。CLOSET+算法n加速子集检测方法：(1)两层哈希索引结果树(2

46、)基于向上检测的伪投影CLOSET+算法nCLOSET+算法步骤：1、扫描事务数据库，构造f_list。2、使用f_list，通过扫描事务数据库建立FP-tree。3、使用分治策略分治策略和深度优先搜索深度优先搜索方法，(1)当数据集是稀疏稀疏时，使用自顶向下方法挖掘FP-tree来寻找频繁闭项集。(2)当数据集是密集密集时，使用自底向上的方法挖掘FP-tree来寻找频繁闭项集。4、当全局头表上的所有项都被挖掘了，算法结束。CHARM算法n定义 对于项集X，定义X对应的事务id集合(tidset)为t(X):t(X)=xXt(x)对于事务id集合，定义对应的项集(itemset)为i(Y):i

47、(Y)= yYi(y)CHARM:使用垂直数据格式挖掘闭项集nIT-Tree:Itemset-Tidset Search TreeTIDitems1ACTW2CDW3ACTW4ACDW5ACDTW6CDT设事务数据库TDB为：IT-Tree则对应的IT-Tree为：n等价类(Equivalence Classes)等价类P=l1,l2,ln,其中P是父节点（前驱），且每个li表示单独的项。例如：前面IT-Tree中根节点的等价类为： =A,C,D,T,Wn项集的闭包项集X的闭包是包含项集X的最小的闭集。c(X) = i t(X) = i(t(X).n结论：项集X是闭的，当且仅当X=c(X)。C

48、HARM算法n定理1设Xit(Xi)和Xjt(Xj)是类P的任意两个成员，如果满足XifXj，其中f表示一个全序关系(如，按字典顺序或者基于支持度的顺序)。存在如下四条性质：1.如果t(Xi)=t(Xj)，则c(Xi)=c(Xj)=c(XiXj)2.如果t(Xi) t(Xj)，则c(Xi) c(Xj)，但是满足c(Xi)=c(XiXj)3.如果t(Xi)?t(Xj)，则c(Xi) c(Xj),但是满足c(Xj)=c(XiXj)4.如果t(Xi) t(xj)，则c(Xi) c(Xj)c(Xi Xj)n定理产生的启发信息：1、由于c(Xi) = c(Xj) = c(Xi Xj)，所以可以用Xi Xj替换掉Xi，并且将Xj从等价类中移除。2、由于c(Xi Xj) = c(Xi) c(Xj )，所以可以用Xi Xj替换掉Xi；但是由于c(Xi) c(Xj )，所以不能将元素Xj从等价类中移除。3、与2相似。4、由于c(Xi)c(Xj)c(XiXj)，所以Xi和Xj都能各自产生不同的闭