斯坦福_数据库系统实现_Notes11.pptVIP

* * * * * * * 7 * * * * applies to persons, but also other kinds of entities two-fold: 1 - identify records that represent the same entity 2 - combine these entities * * CS 245 Notes11 * Finding High-Support Pairs Baskets(basket, item) SELECT I.item, J.item, COUNT(I.basket)FROM Baskets I, Baskets JWHERE I.basket = J.basket AND I.item J.itemGROUP BY I.item, J.itemHAVING COUNT(I.basket) = s; WHY? CS 245 Notes11 * Example CS 245 Notes11 * Example check if count ? s CS 245 Notes11 * Issues Performance for size 2 rules big even bigger! Performance for size k rules CS 245 Notes11 * Association Rules How do we perform rule mining efficiently? CS 245 Notes11 * Association Rules How do we perform rule mining efficiently? Observation: If set X has support t, then each X subset must have at least support t CS 245 Notes11 * Association Rules How do we perform rule mining efficiently? Observation: If set X has support t, then each X subset must have at least support t For 2-sets: if we need support s for {i, j} then each i, j must appear in at least s baskets CS 245 Notes11 * Algorithm for 2-Sets (1) Find OK products those appearing in s or more baskets (2) Find high-support pairs using only OK products CS 245 Notes11 * Algorithm for 2-Sets INSERT INTO okBaskets(basket, item) SELECT basket, item FROM Baskets GROUP BY item HAVING COUNT(basket) = s; CS 245 Notes11 * Algorithm for 2-Sets INSERT INTO okBaskets(basket, item) SELECT basket, item FROM Baskets GROUP BY item HAVING COUNT(basket) = s; Perform mining on okBaskets SELECT I.item, J.item, COUNT(I.basket) FROM okBaskets I, okBaskets J WHERE I.basket = J.basket AND I.item J.item GROUP BY I.item, J.item HAVING COUNT(I.basket) = s; CS 245 Notes11 * Counting Efficiently One way: threshold = 3 CS 245 Notes11 * Counting Efficiently One way: sort threshold = 3 CS 245 Notes11 * Counting Efficiently One way: sort count remove threshold =