CPS216: Advanced Database Systems Data Mining Slides created by Jeffrey Ullman, Stanford 1 What is Data Mining? Discovery of useful, possibly unexpected, patterns in data. Subsidiary issues: Data cleansing: detection of bogus data. E.g., age = 150. Visualization: something better than

megabyte files of output. Warehousing of data (for retrieval). 2 Typical Kinds of Patterns 1. Decision trees: succinct ways to classify by testing properties. 2. Clusters: another succinct classification by similarity of properties. 3. Bayes, hidden-Markov, and other statistical models, frequent-itemsets: expose important associations within data. 3

Example: Clusters x x x x x x x x xx x x x x x x x x xx x x x x x x

x xx x x x x x x x x x x x x 4 Example: Frequent Itemsets A common marketing problem: examine what people buy together to discover patterns.

1. What pairs of items are unusually often found together at Kroger checkout? Answer: diapers and beer. 2. What books are likely to be bought by the same Amazon customer? 5 Meaningfulness of Answers A big risk when data mining is that you will discover patterns that are meaningless. Statisticians call it Bonferronis

principle: (roughly) if you look in more places for interesting patterns than your amount of data will support, you are bound to find false patterns. 6 Rhine Paradox --- (1) David Rhine was a parapsychologist in the 1950s who hypothesized that some people had Extra-Sensory Perception. He devised an experiment where subjects were asked to guess 10 hidden cards --- red or blue. He discovered that almost 1 in 1000 had ESP --- they were able to get all 10

right! 7 Rhine Paradox --- (2) He told these people they had ESP and called them in for another test of the same type. Alas, he discovered that almost all of them had lost their ESP. What did he conclude? Answer on next slide. 8 Rhine Paradox --- (3)

He concluded that you shouldnt tell people they have ESP; it causes them to lose it. 9 Association Rules Market Baskets Frequent Itemsets A-priori Algorithm 10 The 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. 11 Association Rule Mining on i t er c a

m s to n s a d r i u t c id sales

records: tran1 tran2 tran3 tran4 tran5 tran6 cust33 cust45 cust12 cust40 cust12 cust12

p2, p5, p1, p5, p2, p9 ts c du ht o pr oug b p5, p8

p8, p11 p9 p8, p11 p9 market-basket data Trend: Products p5, p8 often bought together 12 Support 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. 13 Example Items={milk, coke, pepsi, beer, juice}. Support = 3 baskets. B1 B3 B5

B7 = = = = {m, c, b} {m, b} {m, p, b} {c, b, j} B2 B4 B6

B8 = = = = {m, p, j} {c, j} {m, c, b, j} {b, c} Frequent itemsets: {m}, {c}, {b}, {j}, {m, b}, {c, b}, {j, c}.

14 Applications --- (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 diapers and raise the price of beer. High support needed, or no $$s . 15 Applications --- (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. 16 Applications --- (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. 17 Important Point Market Baskets is an abstraction that models any many-many relationship between two concepts: items and baskets. Items need not be contained in baskets.

The only difference is that we count co-occurrences of items related to a basket, not vice-versa. 18 Scale of Problem WalMart sells 100,000 items and can store billions of baskets. The Web has over 100,000,000 words and billions of pages. 19 Association 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. 20 Example + B1 = {m, c, b} _ B3 = {m, b} _

B5 = {m, p, b} B7 = {c, b, j} B2 = {m, p, j} B4 = {c, j} + B6 = {m, c, b, j} B8 = {b, c} An association rule: {m, b} c. Confidence = 2/4 = 50%. 21 Interest The interest of an association rule

is the absolute value of the amount by which the confidence differs from what you would expect, were items selected independently of one another. 22 Example B1 B3 B5 B7 =

= = = {m, c, b} {m, b} {m, p, b} {c, b, j} B2 B4 B6 B8 =

= = = {m, p, j} {c, j} {m, c, b, j} {b, c} For association rule {m, b} c, item c appears in 5/8 of the baskets. Interest = | 2/4 - 5/8 | = 1/8 --- not very interesting. 23

Relationships Among Measures Rules with high support and confidence may be useful even if they are not interesting. We dont care if buying bread causes people to buy milk, or whether simply a lot of people buy both bread and milk. But high interest suggests a cause that might be worth investigating. 24 Finding Association Rules A typical question: find all association rules with support s and confidence

c. Note: support of an association rule is the support of the set of items it mentions. Hard part: finding the high-support (frequent ) itemsets. Checking the confidence of association rules involving those sets is relatively easy. 25 Computation 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. 26 Computation Model --- (2) The true cost of mining disk-resident data is usually the number of disk I/Os. In practice, association-rule algorithms read the data in passes --all baskets read in turn. Thus, we measure the cost by the number of passes an algorithm takes. 27

Main-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. 28 Finding Frequent Pairs The hardest problem often turns out to be finding the frequent pairs.

Well concentrate on how to do that, then discuss extensions to finding frequent triples, etc. 29 Nave 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. 30 Details of Main-Memory Counting There are two basic approaches: 1. Count all item pairs, using a triangular matrix. 2. Keep a table of triples [i, j, c] = the count of the pair of items {i,j } is c. (1) requires only (say) 4 bytes/pair; (2) requires 12 bytes, but only for those pairs with >0 counts. 31

4 per pair Method (1) 12 per occurring pair Method (2) 32 Details of Approach (1) Number items 1,2, Keep pairs in the order {1,2},

{1,3},, {1,n }, {2,3}, {2,4},, {2,n }, {3,4},, {3,n },{n -1,n }. Find pair {i, j } at the position (i 1)(n i /2) + j i. Total number of pairs n (n 1)/2; total bytes about 2n 2. 33 Details of Approach (2) You need a hash table, with i and j as the key, to locate (i, j, c) triples efficiently. Typically, the cost of the hash structure can be neglected. Total bytes used is about 12p, where p is

the number of pairs that actually occur. Beats triangular matrix if at most 1/3 of possible pairs actually occur. 34 A-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. Contrapositive for pairs: if item i does not appear in s baskets, then no pair including i can appear in s baskets. 35

A-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 be frequent. Requires memory proportional to square of frequent items only. 36 Picture of A-Priori

Item counts Frequent items Counts of candidate pairs Pass 1 Pass 2 37 Detail for A-Priori You can use the triangular matrix method with n = number of

frequent items. Saves space compared with storing triples. Trick: number frequent items 1,2, and keep a table relating new numbers to original item numbers. 38 Frequent Triples, Etc. For each k, we construct two sets of k tuples: Ck = candidate k tuples = those that might be frequent sets (support > s ) based on information from the

pass for k 1. Lk = the set of truly frequent k tuples. 39 C1 Filter First pass L1

Construct C2 Filter L2 Construct C3 Second pass

40 A-Priori for All Frequent Itemsets One pass for each k. Needs room in main memory to count each candidate k tuple. For typical market-basket data and reasonable support (e.g., 1%), k = 2 requires the most memory. 41 Frequent Itemsets --- (2) C1 = all items

L1 = those counted on first pass to be frequent. C2 = pairs, both chosen from L1. In general, Ck = k tuples each k 1 of which is in Lk-1. Lk = those candidates with support s. 42