【精品】刘渡舟讲伤寒论录音整理 title62

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