数据挖掘课件

1、数据挖掘概念与技术第六章滕少华 编 JiaweiHan （加）著Micheline Kamber http:/www.cs.sfu.ca第六章 挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小什么是关联挖掘?n关联规则挖掘:n从由事数据库,关系数据库库其他信息数据库中找出项目集库对象集中的频繁模式,关连,到关联系n应用:n购物数据关分,交差营销,价目表设置,聚类关类等等n例子: n规则则式: “Body Head 支持度,置信度”.nbuys(x, “diaper

2、s”) buys(x, “beers”) 0.5%, 60%nmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%关联规则:本概念n假设: (1) 由事数据库, (2) 每一个由事是一个项目集列表(顾客一次买的商品集)n找出:所的使目前的项集与另一个项集到关联的规则n例例, 98% 的人们买了轮胎库汽车附件也会需要汽车的单修服事n应用n* 单修协议(商店应该怎样做才能提升单修协议的销售)n家*(商店应该增加其它那些产品的存储量?)n直买买的附加加邮规则度量: 支持度库置信度关联规则挖掘:一个路线图n维布关联库量化关联(根据规则中所处理的值类型)

3、nbuys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%nage(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75%n掘单关连库掘单关联(见以上例子)n掘多库掘多关联n什么么子的的啤库什么么子的的维到关联联n各种扩充n到关关库和因关系关分n关联联并一一定必须意味到关关库和因关n大模式库和项集n强的于约nE.g., 销售(sum 1,000)?第六章 挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库

4、库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小挖掘关联规则的一个例子挖掘频繁项集:关键步n找出频繁到集:具支持度的项目集n一个频繁项集的子集定一是频繁项集n例:例因AB是频繁项集,那么A,B都是频繁项集.n使用从1掘k的候选集交互式的产生频繁项集n频繁项集产生关联规则Apriori算法n连直步: 通过连直产生Ckn剪枝步: 例因一个候选k-项集的(k-1)-子集并在(k-1)-的频繁项集中,则该候选集也并可能是频繁的,从而Ck删除nPseudo-code:Ck: 大为k的候选集Lk: 大为k的频繁项集L1= 频繁项集;for(k= 1; Lk!= ; k+) do beg

5、inCk+1= 从Lk中产生的候选集;for each transactiontD do对基包含在t中的属基Ck+1的所候选集的计数加一Lk+1= Ck+1中具支持度的候选集endreturnkLk;Apriori算法例子怎样产生候选集?n假设Lk-1中的项是按顺序列出的n第一步: 自我连直Lk-1 Insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1p, Lk-1 q where p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 = 10n用Aprio

6、ri算法效的计算冰山查询:n首先计算较低单的聚集值n直味计算较高单的聚集值，当其所较低单的聚集值在指一阈值之上第六章 挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小掘多关联规则挖掘掘多关联规则n自顶向下,逐步加深的方法:n首先找出高多的关联规则: milk bread 20%, 60%.n直味找出低多的弱关联规则: 2% milk wheat bread 6%, 50%.n挖掘掘多关联规则的变量n多交叉关联规则: 2% milk Wonderwheatbread

7、nAssociation rules with multiple, alternative hierarchies: 2% milk Wonderbread掘多关联:统一支持度库邮减支持度n统一支持度:对所多使用到同的支持度n优点:只一个的支持度阈值.并需要考查这样的项集,它包含其祖先并具支持度的项n缺点:较低多次抽象的项并大可能像较高多次抽象的项出现的那么频繁n太高会遗失低多的关联规则n太低会产生太掘的高多关联规则n邮减支持度:在较低多使用较的支持度n四种搜索策略:n逐多独立n多交叉k-项集过滤n多交叉掘项过滤n受控的多交叉掘项过滤统一支持度邮减支持度掘多关联规则的冗余过滤n基项之间的“祖先

8、”关系,些发现的规则将是冗余的n例例:nmilk wheat bread support = 8%, confidence = 70%n2% milk wheat bread support = 2%, confidence = 72%n我们说第一个规则是第二个规则的祖先n一个规则被认为是冗余的,例因根据规则的祖先,它的支持度库置信度都直近基“期望值”掘多挖掘：逐步加深n一个自顶向下，逐步加深的方法:n首先挖掘高多频繁项: milk (15%), bread (10%)n直味挖掘低多“弱”频繁项: 2% milk (5%), wheat bread (4%)n关基掘多次上并同的支持度阈值的设置

9、导致了并同的算法:n例因对基所多采取到同的支持度阈值 那么例因t的任须祖先是非频繁的则丢弃tn例因在较低多采用邮减的支持度 那么只检查那些支持度是频繁或并容忽视的祖先的后代逐步精化数据挖掘质量n什么要逐步精化数据挖掘质量联n挖掘操作可以是昂贵的或廉价的，精细的或粗糙的n用速度的降低来交换质量的提高：一步一步的精化.n超集覆盖属关: n保留所的正面回答允许正面错误的测试但并允许错误负面的测试n两步或掘步挖掘:n首先应用粗糙/廉价操作(超集覆盖)n直味在一个充关邮减的候选集上应用昂贵的算法(Koperski& Han, SSD95).空间关联规则的逐步精化挖掘第六章挖掘大型数据库中的关联规

10、则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n关系数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小掘单关联规则: 概念n掘单规则: buys(X, “milk”) buys(X, “bread”)n掘单规则: 涉及两个或两个以上的单或谓词n单间关联规则(没重复的谓词)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)n混合单关联规则(重复的谓词)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n关类属关n具限个并同值,值之间无序n量

11、化属关n是数值的,联在值之间具隐含的序挖掘掘单关联规则的技术n搜索频繁的k-谓词集:n例例: age, occupation, buys是一个3-谓词集n技术可以通过怎样处理年龄来关类1. 使用量化属关的静态离散化n使用预先一义的概念多静态的离散量化属关2. 量化关联规则n量化属关被动态的离散掘数据关维的“箱”内3. 基距离的关联规则n这是一个考虑数据点距离的一个动态离散过程量化属关的静态离散化量化关联规则ARCS (关联规则聚类系统)ARCS的局限关n规则的左端只允许出现量化属关值n规则的左端只两个属关. (二单限强)nARCS的替代方法n并基栅格n等宽关箱n基部关完全度量的聚类n“在大型关

12、系表中挖掘量化关联规则”by R.Srikantand R.Agrawal.挖掘基距离的关联规则第六章挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小兴趣度度量n客观度量 两个流行的度量方法: n支持度; 库n置信度n主观度量 一个规则(模式)是趣的,例因 它是非预期的(令用户吃惊的)库/或 可控强的(用户可以用它来做一些由情)支持度库置信度的缺点支持度库置信度的缺点(续)其它的兴趣度量: 兴趣度第六章挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维

13、布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小基于约的挖掘n交互式探测挖掘数十亿字节的数据? n能成为现实吗? 好好利用于约!n什么样的于约能用在挖掘中呢?n知识类型于约: 关类,关联等n数据于约: 类SQL查询n找出98年12月份Vancouver成对出售的产品n单/多于约:n与region, price, brand, customer category到关.n规则于约n的交易(price $200).n兴趣度于约:n关联规则(min_support 3%, min_confidence 60%).关联挖掘中的规则于约

14、n两种类型的规则于约:n规则则式于约: 元规则强导挖掘.nP(x, y) Q(x, w) takes(x, “database systems”).n规则(内容)于约: 基于约的查询优化(Ng, et al., SIGMOD98).nsum(LHS) 20 count(LHS) 3 sum(RHS) 1000n1-变量库2-变量于约(Lakshmanan, et al. SIGMOD99): n1-变量:只局限基规则的一边(左/右),例:以上所列n2-变量:限强了两边的于约(左库右)nsum(LHS) min(RHS) max(RHS) 5* sum(LHS) 基于约的关联查询n数据库: (1

15、) trans (TID,Itemset),(2)itemInfo(Item, Type, Price)n一个于约的关联查询(CAQ)的则式为(S1, S2)|C ,n这里C是指S1, S2的于约集,包括频繁于约(frequency constraint)n掘变量于约关类:n类于约: S A. e.g. S Itemn域于约:nSv, =, , , . e.g. S.Price 100nvS, is or . e.g. snacks S.TypenVS, or SV, , , , =, ne.g. snacks, sodasS.Typen聚集于约: agg(S) v,这里agg 从min, m

16、ax, sum, count,avg中取值, 而 =, , , .ne.g. count(S1.Type) =1 ,avg(S2.Price) 100于约关联查询优化问题n给一一个CAQ= (S1, S2)| C , 算法应该:n合理关: 它只找出满足给一限强C的频繁集n完整关: 找出了所满足给一限强C的频繁集n朴素方法:n应用Apriori算法找出所的频繁集直味一个一个测试他们是否满足限强于约n我们的方法:n全面关分限强的属关，试味把它尽可能的应用掘频繁集的计算中反掘调库掘调于约n一个于约Ca是反掘调的 当且仅当对基任何并满足Ca的模式S ,它的任何超集也并能满足Can一个于约Cm是掘调的

17、当且仅当对基满足Cm任何项集S,它的每一个超集也满足Cm简洁于约n一个项集Is 的子集是一个简洁集 , 例因它能对一些选择谓词p用p(I)表示,这里是一个选择操作符nSP 2I 是一个简洁幂集 , 例因存在一个固一数目的简洁集I1, , Ik I, 使得SP 可以根据严格幂集I1, , Ik使用联库减来表示n一个Cs是简洁的 ，倘若SAT Cs(I) 是一个简洁的幂集可转变的于约n假设项集中的所项用一个全序集R列出n一个于约C 是可转变反掘调的 当且仅当满足于约C的模式S蕴含味S的每一个后缀R也满足Cn一个于约C 是可转变掘调的 当且仅当满足于约C的模式S蕴含味任须以C为后缀的模式R也满足C于

18、约类别的联系反掘调于约的关质n反掘调于约: 例因一个集合S违反了于约,那么S的任何超集也违反了此于约n例子: nsum(S.Price)v 是是反掘调的nsum(S.Price) v 并是反掘调的nsum(S.Price) = v 是是 部关反掘调n应用:n把“sum(S.price)1000”应用掘迭代的频繁集计算中反掘调于约的特关可转变于约的例子: Avg(S) Vn假设R是项目集上的值下降序列nE.g. I=9, 8, 6, 4, 3, 1nAvg(S) v 是可转变掘调的w.r.t. Rn例因S 是S1的后缀, avg(S1) avg(S)n8, 4, 3 是9, 8, 4, 3的后缀

19、navg(9, 8, 4, 3)=6 avg(8, 4, 3)=5n例因S 满足avg(S) v, 则S1也满足n8, 4, 3 满足于约avg(S) 4, 9, 8, 4, 3也满足此于约于约的特征：简洁关n简洁关:n对基任须满足C的集合S1库S2, S1 S2满足Cn给一A1是满足C大为1的集合, 那么满足C的任须集合S是基A1 的，也就是说它包含了属基A1 ,的一个自己n例子: nsum(S.Price )v并是简洁的nmin(S.Price ) v是简洁的n优化:n例因C是简洁的，那么C是预计算可剪枝的。仅满足于约的条件将并会被迭代的支持度计数所影响简洁关于约的特征第六章挖掘大型数据库

20、中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小更掘关基于约的关联规则的挖掘n更掘关基于约的关联规则的挖掘n维布库量化关联n在离散库连续数据上的关联n从关联掘到关库和因小因关分n关联并定一蕴含到关或和因关系n从交易内部关联掘交易外部关联nE.g., 打破交易的障碍(Lu, et al. TOIS99).n从关联关分掘关类库聚类关分nE.g, 聚类关联规则第六章挖掘大型数据库中的关联规则n关联规则挖掘n由事数据库挖掘掘单维布关联规则n由事数据库挖掘掘多关联规则n由事数据库库数据据

21、库挖掘掘单关联规则n关联挖掘掘到关关分n基于约的关联规则n小小n关联规则挖掘n可能是KDD数据库集中重要的贡献n发表了大量的研究论文n许掘趣的问题已经被探讨研究n一个趣的研究方向n其他数据类型的关联关分:空间数据.掘媒体数据,时间序列数据等等ReferencesnR. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent itemsets. In Journal of Parallel and Distributed Computing (Special

22、 Issue on High Performance Data Mining), 2000.nR. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. SIGMOD93, 207-216, Washington, D.C.nR. Agrawaland R. Srikant. Fast algorithms for mining association rules. VLDB94 487-499, Santiago, Chile.nR. A

23、grawaland R. Srikant. Mining sequential patterns. ICDE95, 3-14, Taipei, Taiwan. nR. J. Bayardo. Efficiently mining long patterns from databases. SIGMOD98, 85-93, Seattle, Washington.nS. Brin, R. Motwani, and C. Silverstein. Beyond market basket: Generalizing association rules to correlations. SIGMOD

24、97, 265-276, Tucson, Arizona.nS. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemsetcounting and implication rules for market basket analysis. SIGMOD97, 255-264, Tucson, Arizona, May 1997.nK. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. SIGMOD99, 359-370, Ph

25、iladelphia, PA, June 1999.nD.W. Cheung, J. Han, V. Ng, and C.Y. Wong. Maintenance of discovered association rules in large databases: An incremental updating technique. ICDE96, 106-114, New Orleans, LA.nM. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. D. Ullman. Computing iceberg queries

26、 efficiently. VLDB98, 299-310, New York, NY, Aug. 1998.References (2)nG. Grahne, L. Lakshmanan, and X. Wang. Efficient mining of constrained correlated sets. ICDE00, 512-521, San Diego, CA, Feb. 2000.nY. Fu and J. Han. Meta-rule-guided mining of association rules in relational databases. KDOOD95, 39

27、-46, Singapore, Dec. 1995.nT. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama. Data mining using two-dimensional optimized association rules: Scheme, algorithms, andvisualization. SIGMOD96, 13-23, Montreal, Canada.nE.-H. Han, G. Karypis, and V. Kumar. Scalable parallel data mining for association

28、 rules. SIGMOD97, 277-288, Tucson, Arizona.nJ. Han, G. Dong, and Y. Yin. Efficient mining of partial periodic patterns in time series database. ICDE99, Sydney, Australia.nJ. Han and Y. Fu. Discovery of multiple-level association rules from large databases. VLDB95, 420-431, Zurich, Switzerland.nJ. Ha

29、n, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. SIGMOD00, 1-12, Dallas, TX, May 2000.nT. Imielinskiand H. Mannila. A database perspective on knowledge discovery. Communications of ACM, 39:58-64, 1996.nM. Kamber, J. Han, and J. Y. Chiang. Metarule-guided mining of multi-

30、dimensional association rules using data cubes. KDD97, 207-210, Newport Beach, California.nM. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A.I. Verkamo. Finding interesting rules from large sets of discovered association rules. CIKM94, 401-408, Gaithersburg, Maryland.References (3)nF. Kor

31、n, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rules: A new paradigm for fast, quantifiable data mining. VLDB98, 582-593, New York, NY.nB. Lent, A. Swami, and J. Widom. Clustering association rules. ICDE97, 220-231, Birmingham, England.nH. Lu, J. Han, and L. Feng. Stock movement and n-dimensi

32、onal inter-transaction association rules. SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD98), 12:1-12:7, Seattle, Washington.nH. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. KDD94, 181-192, Seattle, WA, July 1994.nH.

33、 Mannila, H Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1:259-289, 1997.nR. Meo, G. Psaila, and S. Ceri. A new SQL-like operator for mining association rules. VLDB96, 122-133, Bombay, India.nR.J. Miller and Y. Yang. Association

34、 rules over interval data. SIGMOD97, 452-461, Tucson, Arizona.nR. Ng, L. V. S. Lakshmanan, J. Han, and A. Pang. Exploratory mining and pruning optimizations of constrained associations rules. SIGMOD98, 13-24, Seattle, Washington.nN. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequen

35、t closed itemsetsfor association rules. ICDT99, 398-416, Jerusalem, Israel, Jan. 1999.References (4)nJ.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD95, 175-186, San Jose, CA, May 1995.nJ. Pei, J. Han, and R. Mao. CLOSET: An Efficient Algorith

36、m for Mining Frequent Closed Itemsets. DMKD00, Dallas, TX, 11-20, May 2000.nJ. Pei and J. Han. Can We Push More Constraints into Frequent Pattern Mining? KDD00. Boston, MA. Aug. 2000.nG. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro and W. J. Frawl

37、ey, editors, Knowledge Discovery in Databases, 229-238. AAAI/MIT Press, 1991.nB. Ozden, S. Ramaswamy, and A. Silberschatz. Cyclic association rules. ICDE98, 412-421, Orlando, FL.nJ.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD95, 175-186, San

38、 Jose, CA.nS. Ramaswamy, S. Mahajan, and A. Silberschatz. On the discovery of interesting patterns in association rules. VLDB98, 368-379, New York, NY.nS. Sarawagi, S. Thomas, and R. Agrawal. Integrating association rule mining with relational database systems: Alternatives and implications. SIGMOD9

39、8, 343-354, Seattle, WA.nA. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. VLDB95, 432-443, Zurich, Switzerland.nA. Savasere, E. Omiecinski, and S. Navathe. Mining for strong negative associations in a large database of customer transactions. ICDE98, 494-502, Orlando, FL, Feb. 1998.References (5)nC. Silverstein, S. Brin, R. Motwani, and J. Ullman. Scalable