Unformatted text preview:

Data Mining: AssociationsPurposeThe Market-Basket ModelSupportExampleApplications 1Applications 2Applications 3Scale of ProblemAssociation RulesSlide 11Finding Association RulesComputation ModelMain-Memory BottleneckFinding Frequent PairsNaïve AlgorithmA-Priori Algorithm 1A-Priori Algorithm 2Picture of A-PrioriPCY Algorithm 1Picture of PCYPCY Algorithm 2Multistage AlgorithmMultistage PictureFinding Larger ItemsetsApproximationsAll Frequent Itemsets in <= 2 PassesSimple Algorithm 1Simple Algorithm 2SON Algorithm 1SON Algorithm 2Toivonen’s Algorithm 1Toivonen’s Algorithm 2Toivonen’s Algorithm 3Toivonen’s Algorithm 4Low-Support, High-CorrelationAssumptionsApplicationsMatrix RepresentationIn Matrix FormSimilarity of ColumnsSlide 42SignaturesAn Idea That Doesn’t WorkFour Types of RowsMin HashingSurprising PropertyMin-Hash SignaturesSlide 49Important TrickSlide 51Locality-Sensitive HashingPartition into BandsSlide 54Suppose C1, C2 are 80% SimilarSuppose C1, C2 Only 40% SimilarLSH SummaryAmplification of 1’sSlide 59Using Hamming LSHSummary1Data Mining: AssociationsFrequent itemsets, market basketsA-priori algorithmHash-based improvementsOne- or two-pass approximationsHigh-correlation mining2PurposeIf people tend to buy A and B together, then a buyer of A is a good target for an advertisement for B.The same technology has other uses, such as detecting plagiarism and organizing the Web.3The Market-Basket ModelA large set of items, e.g., things sold in a supermarket.A large set of baskets, each of which is a small set of the items, e.g., the things one customer buys on one day.4SupportSimplest question: find sets of items that appear “frequently” in the baskets.Support for itemset I = the number of baskets containing all items in I. Given a support threshold s, sets of items that appear in >= s baskets are called frequent itemsets.5ExampleItems={milk, coke, pepsi, beer, juice}.Support = 3 baskets.B1 = {m, c, b} B2 = {m, p, j}B3 = {m, b} B4 = {c, j}B5 = {m, p, b} B6 = {m, c, b, j}B7 = {c, b, j} B8 = {b, c}Frequent itemsets: {m}, {c}, {b}, {j}, {m, b}, {c, b}, {j, c}.6Applications 1Real market baskets: chain stores keep terabytes of information about what customers buy together.Tells how typical customers navigate stores, lets them position tempting items.Suggests tie-in “tricks,” e.g., run sale on hamburger and raise the price of ketchup.High support needed, or no $$’s .7Applications 2“Baskets” = documents; “items” = words in those documents.Lets us find words that appear together unusually frequently, i.e., linked concepts.“Baskets” = sentences, “items” = documents containing those sentences.Items that appear together too often could represent plagiarism.8Applications 3“Baskets” = Web pages; “items” = linked pages.Pairs of pages with many common references may be about the same topic.“Baskets” = Web pages p ; “items” = pages that link to p .Pages with many of the same links may be mirrors or about the same topic.9Scale of ProblemWalMart sells 100,000 items and can store hundreds of millions of baskets.The Web has 100,000,000 words and several billion pages.10Association RulesIf-then rules about the contents of baskets.{i1, i2,…, ik} -> jMeans: “if a basket contains all of i1,…,ik, then it is likely to contain j.Confidence of this association rule is the probability of j given i1,…,ik.11ExampleB1 = {m, c, b} B2 = {m, p, j}B3 = {m, b} B4 = {c, j}B5 = {m, p, b} B6 = {m, c, b, j}B7 = {c, b, j} B8 = {b, c}An association rule: {m, b} -> c.Confidence = 2/4 = 50%.+__ +12Finding Association RulesA typical question is “find all association rules with support >= s and confidence >= c.”The hard part is finding the high-support itemsets.Once you have those, checking the confidence of association rules involving those sets is relatively easy.13Computation ModelTypically, data is kept in a “flat file” rather than a database system.Stored on disk.Stored basket-by-basket.•Expand baskets into pairs, triples, etc. as you read baskets.True cost = # of Disk I/O’s.Count # of passes through the data.14Main-Memory BottleneckIn many algorithms to find frequent itemsets we need to worry about how main-memory is used.As we read baskets, we need to count something, e.g., occurrences of pairs.The number of different things we can count is limited by main memory.Swapping counts in/out is a disaster.15Finding Frequent PairsThe hardest problem often turns out to be finding the frequent pairs.We’ll concentrate on how to do that, then discuss extensions to finding frequent triples, etc.16Naïve AlgorithmA simple way to find frequent pairs is:Read file once, counting in main memory the occurrences of each pair.•Expand each basket of n items into its n(n-1)/2 pairs.Fails if #items-squared exceeds main memory.17A-Priori Algorithm 1A two-pass approach called a-priori limits the need for main memory.Key idea: monotonicity : if a set of items appears at least s times, so does every subset.Converse for pairs: if item i does not appear in s baskets, then no pair including i can appear in s baskets.18A-Priori Algorithm 2Pass 1: Read baskets and count in main memory the occurrences of each item.Requires only memory proportional to #items.Pass 2: Read baskets again and count in main memory only those pairs both of which were found in Pass 1 to have occurred at least s times.Requires memory proportional to square of frequent items only.19Picture of A-PrioriItem countsPass 1 Pass 2Frequent itemsCounts ofcandidate pairs20PCY Algorithm 1Hash-based improvement to A-Priori.During Pass 1 of A-priori, most memory is idle.Use that memory to keep counts of buckets into which pairs of items are hashed.Just the count, not the pairs themselves.Gives extra condition that candidate pairs must satisfy on Pass 2.21Picture of PCYHashtableItem countsBitmapPass 1 Pass 2Frequent itemsCounts ofcandidate pairs22PCY Algorithm 2PCY Pass 1:Count items.Hash each pair to a bucket and increment its count by 1.PCY Pass 2:Summarize buckets by a bitmap : 1 = frequent (count >= s ); 0 = not.Count only those pairs that (a) are both frequent and (b) hash to a frequent bucket.23Multistage AlgorithmKey idea: After Pass


View Full Document

Stanford CS 206 - LECTURE NOTES

Documents in this Course
Load more
Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?