CS 361A (Advanced Data Structures and Algorithms)(Advanced Data Structures and Algorithms)Lecture 20 (Dec 7, 2005)Data Mining: Association RulesRajeev Motwani(partially based on notes by Jeff Ullman)CS 361A1Association Rules Overview1.Market Baskets & Association Rules2.Frequent item-sets3.A-priori algorithm4.Hash-based improvements5.One- or two-pass approximations6.High-correlation miningCS 361A2Association RulesTwo 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 technologyCS 361A3Market-Basket ModelLarge 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 itemsetsCS 361A4ExampleItems 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, cCS 361A5Application 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 $sCS 361A6Application 2 (Information Retrieval)Scenario 1baskets = documentsitems = words in documentsfrequent word-groups = linked concepts.Scenario 2items = sentencesbaskets = documents containing sentencesfrequent sentence-groups = possible plagiarismCS 361A7Application 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 topicCS 361A8Scale of ProblemWalMart 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 basketCS 361A9Association RulesIf-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 361A10ExampleB1 = 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 361A11Finding Association RulesGoal 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 knownCS 361A12Computation ModelData 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 disasterCS 361A13Finding Frequent PairsFrequent 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,000CS 361A14Montonicity PropertyUnderlies all known algorithmsMonotonicity PropertyGiven itemsetsThen Contrapositive (for 2-sets)CS 361A15A-Priori AlgorithmA-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 bCS 361A20Multistage PCY AlgorithmProblem 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 applyCS 361A23Approximation TechniquesGoalfind all frequent k-setsreduce to 2 passesmust lose something accuracy ApproachesSampling algorithmSON (Savasere, Omiecinski, Navathe) AlgorithmToivonen AlgorithmCS 361A24Sampling AlgorithmPass 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 361A25SON AlgorithmPass 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 batchCS 361A26Toivonens AlgorithmLower 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 memoryCS 361A27Low-Support, High-CorrelationGoal 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 inapplicableCS 361A28Matrix RepresentationSparse, 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,b01010CS 361A29Column SimilarityView column as row-set (where it has 1s) Column Similarity (Jaccard measure)ExampleFinding correlated columns finding similar columnsCi Cj 0 1 1 0 1 1 sim(Ci,Cj) = 2/5 = 0.4 0 0 1 1 0 1CS 361A30Identifying 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 columnsCS 361A31Key ObservationFor columns Ci, Cj, four types of rowsCiCjA 1 1B 1 0C 0 1D 0 0Overload notation: A = # of rows of type AClaimCS 361A32Min HashingRandomly 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 rowCS 361A33Min-Hash SignaturesPick 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 361A34Example 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.00CS 361A35Implementation TrickPermuting 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 lecturesCS 361A41LSH SummaryPass 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 signaturesCS 361A42Densifying Amplification of 1sDense 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 rowsCS 361A43Example001100100101111CS 361A44Using Hamming LSHConstructing matricesn rows log2n matricestotal work = twice that of reading original matrixUsing standard LSHidentify similar columns in each matrixrestrict to columns of medium densityCS 361A45SummaryFinding 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 issuesCS 361A46ReferencesMining Associations between Sets of Items in Massive Databases, R. Agrawal, T. Imielinski, and A. Swami. SIGMOD 1993. Fast Algorithms for Mining Association Rules, R. Agrawal and R. Srikant. VLDB 1994. An Effective Hash-Based Algorithm for Mining Association Rules, J. S. Park, M.-S. Chen, and P. S. Yu. SIGMOD 1995. An Efficient Algorithm for Mining Association Rules in Large Databases , A. Savasere, E. Omiecinski, and S. Navathe. The VLDB Journal 1995. Sampling Large Databases for Association Rules, H. Toivonen. VLDB 1996. Dynamic Itemset Counting and Implication Rules for Market Basket Data, S. Brin, R. Motwani, S. Tsur, and J.D. Ullman. SIGMOD 1997. Query Flocks: A Generalization of Association-Rule Mining, D. Tsur, J.D. Ullman, S. Abiteboul, C. Clifton, R. Motwani, S. Nestorov and A. Rosenthal. SIGMOD 1998. Finding Interesting Associations without Support Pruning, E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J.D. Ullman, and C. Yang. ICDE 2000. Dynamic Miss-Counting Algorithms: Finding Implication and Similarity Rules with Confidence Pruning,S. Fujiwara, R. Motwani, and J.D. Ullman. ICDE 2000. CS 361A47)v&s!pXmUiRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$VkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*tXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5-w*t!qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdLaE2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*tmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C1z)w&s!lUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#ohPeMbJ7G4D1z-w&t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXCS 361A48