已阅读5页,还剩43页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
CS 361A,1,CS 361A (Advanced Data Structures and Algorithms),Lecture 20 (Dec 7, 2005)Data Mining: Association RulesRajeev Motwani(partially based on notes by Jeff Ullman),CS 361A,2,Association Rules Overview,Market Baskets & Association RulesFrequent item-setsA-priori algorithmHash-based improvementsOne- or two-pass approximationsHigh-correlation mining,CS 361A,3,Association Rules,Two TraditionsDM is science of approximating joint distributionsRepresentation of process generating dataPredict PE for interesting events EDM is technology for fast countingCan compute certain summaries quicklyLets try to use themAssociation RulesCaptures interesting pieces of joint distributionExploits fast counting technology,CS 361A,4,Market-Basket Model,Large SetsItems A = A1, A2, , Ame.g., products sold in supermarketBaskets B = B1, B2, , Bnsmall subsets of items in A e.g., items bought by customer in one transactionSupport sup(X) = number of baskets with itemset XFrequent Itemset ProblemGiven support threshold sFrequent Itemsets Find all frequent itemsets,CS 361A,5,Example,Items A = milk, coke, pepsi, beer, juice.BasketsB1 = m, c, bB2 = m, p, jB3 = m, bB4 = c, jB5 = m, p, bB6 = m, c, b, jB7 = c, b, jB8 = b, cSupport threshold s=3Frequent itemsets m, c, b, j, m, b, c, b, j, c,CS 361A,6,Application 1 (Retail Stores),Real market baskets chain stores keep TBs of customer purchase infoValue?how typical customers navigate storespositioning tempting itemssuggests “tie-in tricks” e.g., hamburger sale while raising ketchup price High support needed, or no $s,CS 361A,7,Application 2 (Information Retrieval),Scenario 1baskets = documentsitems = words in documentsfrequent word-groups = linked concepts.Scenario 2items = sentencesbaskets = documents containing sentencesfrequent sentence-groups = possible plagiarism,CS 361A,8,Application 3 (Web Search),Scenario 1baskets = web pagesitems = outgoing linkspages with similar references about same topicScenario 2baskets = web pages items = incoming linkspages with similar in-links mirrors, or same topic,CS 361A,9,Scale of Problem,WalMart sells m=100,000 itemstracks n=1,000,000,000 basketsWebseveral billion pagesone new “word” per pageAssumptionsm small enough for small amount of memory per itemm too large for memory per pair or k-set of itemsn too large for memory per basketVery sparse data rare for item to be in basket,CS 361A,10,Association Rules,If-then rules about basket contentsA1, A2, Ak Ajif basket has X=A1,Ak, then likely to have AjConfidence probability of Aj given A1,AkSupport (of rule),CS 361A,11,Example,B1 = m, c, bB2 = m, p, jB3 = m, bB4 = c, jB5 = m, p, bB6 = m, c, b, jB7 = c, b, jB8 = b, cAssociation Rulem, b cSupport = 2Confidence = 2/4 = 50%,CS 361A,12,Finding Association Rules,Goal find all association rules such thatsupportconfidence Reduction to Frequent Itemsets ProblemsFind all frequent itemsets XGiven X=A1, ,Ak, generate all rules X-Aj AjConfidence = sup(X)/sup(X-Aj)Support = sup(X)Observe X-Aj also frequent support known,CS 361A,13,Computation Model,Data StorageFlat Files, rather than database systemStored on disk, basket-by-basketCost Measure number of passesCount disk I/O onlyGiven data size, avoid random seeks and do linear-scansMain-Memory BottleneckAlgorithms maintain count-tables in memoryLimitation on number of countersDisk-swapping count-tables is disaster,CS 361A,14,Finding Frequent Pairs,Frequent 2-Setshard case alreadyfocus for now, later extend to k-setsNave AlgorithmCounters all m(m1)/2 item pairsSingle pass scanning all basketsBasket of size b increments b(b1)/2 counters Failure?if memory m(m1)/2 even for m=100,000,CS 361A,15,Montonicity Property,Underlies all known algorithmsMonotonicity PropertyGiven itemsetsThen Contrapositive (for 2-sets),CS 361A,16,A-Priori Algorithm,A-Priori 2-pass approach in limited memoryPass 1m counters (candidate items in A)Linear scan of baskets bIncrement counters for each item in bMark as frequent, f items of count at least sPass 2f(f-1)/2 counters (candidate pairs of frequent items)Linear scan of baskets b Increment counters for each pair of frequent items in bFailure if memory s bit = 1)Pass 2Counter only for F qualified pairs (Xi,Xj):both are frequentpair hashes to frequent bucket (bit=1)Linear scan of baskets b Increment counters for candidate qualified pairs of items in b,CS 361A,21,Multistage PCY Algorithm,Problem False positives from hashing New IdeaMultiple rounds of hashingAfter Pass 1, get list of qualified pairsIn Pass 2, hash only qualified pairsFewer pairs hash to buckets less false positives (buckets with count s, yet no pair of count s)In Pass 3, less likely to qualify infrequent pairsRepetition reduce memory, but more passesFailure memory 2Monotonicity itemset X is frequent only if X Xj is frequent for all XjIdeaStage k finds all frequent k-setsStage 1 gets all frequent itemsStage k maintain counters for all candidate k-setsCandidates k-sets whose (k1)-subsets are all frequentTotal cost: number of passes = max size of frequent itemsetObserve Enhancements such as PCY all apply,CS 361A,24,Approximation Techniques,Goalfind all frequent k-setsreduce to 2 passesmust lose something accuracy ApproachesSampling algorithmSON (Savasere, Omiecinski, Navathe) AlgorithmToivonen Algorithm,CS 361A,25,Sampling Algorithm,Pass 1 load random sample of baskets in memoryRun A-Priori (or enhancement)Scale-down support threshold (e.g., if 1% sample, use s/100 as support threshold)Compute all frequent k-sets in memory from sampleNeed to leave enough space for countersPass 2Keep counters only for frequent k-sets of random sampleGet exact counts for candidates to validateError?No false positives (Pass 2)False negatives (X frequent, but not in sample),CS 361A,26,SON Algorithm,Pass 1 Batch ProcessingScan data on diskRepeatedly fill memory with new batch of dataRun sampling algorithm on each batchGenerate candidate frequent itemsetsCandidate Itemsets if frequent in some batchPass 2 Validate candidate itemsetsMonotonicity PropertyItemset X is frequent overall frequent in at least one batch,CS 361A,27,Toivonens Algorithm,Lower Threshold in Sampling Algorithm Example if sampling 1%, use 0.008s as support thresholdGoal overkill to avoid any false negativesNegative BorderItemset X infrequent in sample, but all subsets are frequentExample: AB, BC, AC frequent, but ABC infrequentPass 2Count candidates and negative border Negative border itemsets all infrequent candidates are exactly the frequent itemsetsOtherwise? start over!Achievement? reduced failure probability, while keeping candidate-count low enough for memory,CS 361A,28,Low-Support, High-Correlation,Goal Find highly correlated pairs, even if rareMarketing requires hi-support, for dollar valueBut mining generating process often based on hi-correlation, rather than hi-supportExample: Few customers buy Ketel Vodka, but of those who do, 90% buy Beluga CaviarApplications plagiarism, collaborative filtering, clusteringObserveEnumerate rules of high confidenceIgnore support completelyA-Priori technique inapplicable,CS 361A,29,Matrix Representation,Sparse, Boolean Matrix MColumn c = Item Xc; Row r = Basket BrM(r,c) = 1 iff item c in basket r Example mcpbjB1=m,c,b11010B2=m,p,b10110B3=m,b10010B4=c,j01001B5=m,p,j10101B6=m,c,b,j 11011B7=c,b,j01011B8=c,b01010,CS 361A,30,Column Similarity,View column as row-set (where it has 1s) Column Similarity (Jaccard measure)ExampleFinding correlated columns finding similar columns,Ci Cj 0 1 1 0 1 1 sim(Ci,Cj) = 2/5 = 0.4 0 0 1 1 0 1,CS 361A,31,Identifying Similar Columns?,Question finding candidate pairs in small memorySignature IdeaHash columns Ci to small signature sig(Ci)Set of sig(Ci) fits in memorysim(Ci,Cj) approximated by sim(sig(Ci),sig(Cj)Nave ApproachSample P rows uniformly at randomDefine sig(Ci) as P bits of Ci in sampleProblemsparsity would miss interesting part of columnssample would get only 0s in columns,CS 361A,32,Key Observation,For columns Ci, Cj, four types of rowsCiCjA 1 1B 1 0C 0 1D 0 0Overload notation: A = # of rows of type AClaim,CS 361A,33,Min Hashing,Randomly permute rowsHash h(Ci) = index of first row with 1 in column Ci Suprising PropertyWhy?Both are A/(A+B+C)Look down columns Ci, Cj until first non-Type-D rowh(Ci) = h(Cj) type A row,CS 361A,34,Min-Hash Signatures,Pick P random row permutations MinHash Signature sig(C) = list of P indexes of first rows with 1 in column CSimilarity of signatures Fact: sim(sig(Ci),sig(Cj) = fraction of permutations where MinHash values agree Observe Esim(sig(Ci),sig(Cj) = sim(Ci,Cj),CS 361A,35,Example,C1 C2 C3R1 1 0 1R2 0 1 1R3 1 0 0R4 1 0 1R5 0 1 0,Signatures S1 S2 S3Perm 1 = (12345) 1 2 1Perm 2 = (54321) 4 5 4Perm 3 = (34512) 3 5 4,Similarities 1-2 1-3 2-3Col-Col 0.00 0.50 0.25Sig-Sig 0.00 0.67 0.00,CS 361A,36,Implementation Trick,Permuting rows even once is prohibitiveRow HashingPick P hash functions hk: 1,n1,O(n2) FingerprintOrdering under hk gives random row permutationOne-pass ImplementationFor each Ci and hk, keep “slot” for min-hash valueInitialize all slot(Ci,hk) to infinityScan rows in arbitrary order looking for 1sSuppose row Rj has 1 in column Ci For each hk, if hk(j) 0 bands 0.01*20 = 0.2Low probability that nonidentical columns in band collide False positives much lower for similarities 40% Overall Band-Hash collisions measure similarityFormal Analysis later in near-neighbor lectures,CS 361A,42,LSH Summary,Pass 1 compute singature matrixBand-Hash to generate candidate pairsPass 2 check similarity of candidate pairsLSH Tuning find almost all pairs with similar signatures, but eliminate most pairs with dissimilar signatures,CS 361A,43,Densifying Amplification of 1s,Dense matrices simpler sample of P rows serves as good signature Hamming LSHconstruct series of matricesrepeatedly halve rows ORing adjacent row-pairsthereby, increase densityEach Matrixselect candidate pairs between 3060% 1s similar in selected rows,CS 361A,44,Example,00110010,0101,11,1,CS 361A,45,Using Hamming LSH,Constructing matricesn rows log2n matricestotal work = twice that of reading original matrixUsing standard LSHidentify similar columns in each matrixrestrict to columns of medium density,CS 361A,46,Summary,Finding frequent pairs A-priori PCY (hashing) multistageFinding all frequent itemsets Sampling SON ToivonenFinding similar pairs MinHash+LSH, Hamming LSHFurther WorkScope for improved algorithmsExploit frequency counting ideas from earlier lecturesMore complex rules (e.g. non-monotonic, negations)Extend similar pairs to k-setsStatistical validity issu
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 文明学生演讲稿
- 教师学习心得体会3篇
- 青春期高血压个案护理
- 《这片土地是神圣的》评课稿
- 公司办公用品管理
- 护理人员外出进修协议
- 上海房地产买卖合同补充条款中英文条款
- 《基于构件化的嵌入式系统设计》 课件 项目7 利用SPI实现多机串行通信
- 13.2.3 直线与平面的位置关系(十三大题型)-2024学年高一数学同步学与练(苏教版2019必修第二册)(解析版)
- 河南省青桐鸣2023-2024学年高二下学期三月大联考生物试题
- 德国DIN标准件ISO及国标对照表-标准间对照表
- 社会主义发展史学习通课后章节答案期末考试题库2023年
- 抗震支架安装工程施工组织方案
- 上海集成电路技术与产业促进中心事业单位招考聘用笔试题库含答案详解
- Module3 Unit2 The cows are drinking water.(说课稿)-2022-2023学年英语六年级下册
- 道路工程重点难点及其解决措施、应急预案、应急处理措施(监理投标)
- 装配式建筑施工-1施工前准备(装配式建筑深化设计与施工)
- 幸福在哪里知到章节答案智慧树2023年云南大学
- 起重事故分类及吊装作业常识
- 肺结节诊治指南
- 新人教版五年级数学下册期末测试卷共5套(标准试卷,直接打印)
评论
0/150
提交评论