CHƯƠNG 1 : CO SO LY THUYET |. Phân tích thị trường Mục tiêu của MBA là tìm mối liên hệ (mối quan hệ) giữa các nhóm mục xuất hiện trong cơ sở dữ liệu giao dịch 4 bắt nguồn từ việc phân tích đữ liệu tại điểm bán hàng, như trong các siêu thị 4 nhưng, đã tìm thấy các ứng đụng trong nhiều lĩnh vực khác Khám phá quy tắc kết hợp 4 Loại kỹ thuật PTTT phô biến nhất 4 Tìm tât cả các quy tắc liên kêt sự hiện diện của một tập hợp các phân tử với sự hiện diện của một tập hợp các phần tử khác. 4 Ví dụ: 98% người mua lốp xe và phụ kiện ô tô cũng nhận được dịch vụ ô tô 4 Chúng ta quan tâm đến các quy tắc Không tầm thường (có thê bất ngờ) Có thê hành động Dễ giải thích 1. Luật kết hợp Dạng chung: 4 Body ==> Head 4 Độ hỗ trợ (support) và độ tín cậy (confidence) Thường được báo cáo cùng với các quy tắc Các số liệu cho biết sức mạnh của các liên kết mặt hàng 2.
Examples: {diaper, milk} ==> {beer} [support: 0.5%, confidence: 78%] buys(x, "bread") /\ buys(x, “eggs") ==> buys(x, "milk") [sup: 0.6%, conf: 65%] major(x, "CS") /\ takes(x, "DB") ==> grade(x, "A") [1%, 75%] age(X,30-45) A income(X, 50K-75K) ==> owns(X, SUV) ape= “30-45”, meome=“50K-75K” ==> car=“SUV” 3. Association Rules — Khai niém co ban Let D be database of transactions - e. 1: Transactions « Đặt I là tập hợp các mục xuất hiện trong cơ sở đữ liệu, ví dụ:, I={A,B,C.F} - Mỗi giao tac t la tap con cua | * Một rule là một hàm ÿ nghĩa giữa itemsets X và Y, có dạng X 9 Y, với Xcl, Ycl, va X¬Y=Ø —- @.: {B,C} ô {A} là một rule 4. Association Rules — Basic Concepts s ltemset — Tap một hay nhiều sản phẩm ° E.: {MIIk, Bread, Diaper} — k-itemset * Một Itemset mà k items * Support count (G}) — Tần suất xuất hiện của một tập Itemset (số lượng giao dịch mà nó xuất hiện) — E.
o({Milk, Bread, Diaper}) = 2 Support — Phan cua cac giao dich trong đó một tập mục xuất hién —E. s({Milk, Bread, Diaper}) = 2/5 Frequent ltemset — | itemset ma support >= nguéng minsup Association Rules — Basic Concepts Association Rule X © Y, khi X va Y la nhitng itemsets riéng biét {Milk, Diaper} > {Beer} Đánh giá luật Support (s) Tỷ lệ giao tác chứa X và Y i., support of the itemset X U Y Confidence (c) Tần suất các items trong Y xuất hiện trong giao tác có X (Y và X xuất hiện cùng nhau so với một mình X xuất hiện) Association Rules — Basic Concepts Một cách giải thích khác về độ hỗ trợ và độ tin cậy cho X © Y — Support la xác suất | giao tac chira {X U Y} or Pr(X AY) support(X > Y) = support(X U Y) = o(X u Y) / |DI — Confidence la xac suất có điêu kiện một giao tác có Y với điêu kiện có X or Pr(Y | X) confidence(X 9 Y) = o(X u Y) / o(X) = support(X U Y) / support(X) Support & Confidence - Example Support(X > Y) = support(X Uv Y) = ø(X vu Y)/|D| Confidence(X > Y) = o(X U Y)/ o(X) = support(X U Y) / support(X) Hình 1. 2: Steps in Association Rule Discovery 1. Tim cac tap frequent itemsets (item sets are the sets of items that have minimum support) 2.
Su dung cac tap frequent itemsets dé tạo các association rules Thuật toán vét cạn: +» Liệt kê và tính độ support cho toàn bộ 1temsets + Tao tat ca cac luat tir cc frequent itemsets + Loại bỏ các luật dưới ngưỡng minconf threshold Có bao nhiêu itemsets? Hình 1. Solution: The Apriroi Principle * Support 1s “downward elosed” # Nếu | itemset là frequent (đáp ứng độ support), thì tất cả tap con ciing la frequent o Néu {AB} la | frequent itemset, ca {A} va {B} la frequent itemsets # Điều này là do tính chất anti-monotone cua d6 support VXY:(ŒXcY)=s(X)>s(Y) Cho nên: Nếu I itemset không thỏa ngưỡng minimum support, các tập itemset chứa nó cũng không thỏa ® Dựa vào điều này ta có thể cắt tỉa không gian tìm kiếm) Hình 1. 4: The Apriori Principle Rút gọn dựa vào độ tin cậy Hình 1. Giải thuật Apriori Ck : Candidate itemset of size k Lk : Frequent itemset of size k Hinh 1.6: Join Step: Ck is generated by joining Lk-1with itself Prune Step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k- itemset Example of Generating Candidates L3 ={abc, abd, acd, ace, bcd} Self-joining: L3*L3 abcd from abc and abd acde from acd and ace Pruning: acde is removed because ade is not in L3 C4 = {abcd} Apriori Algorithm - An Example Assume minimum support = 2 Tap “frequent” item sets sau củng thuộc về L2 và L3.
Tuy nhién, {2,3}, {2,5}, va {3,5} ton tai trong tap item set lớn hơn là {2, 3, 5}. Cho nên, kết quả tập item sets sau cùng của thuật toán Apriori la {1,3} va {2,3,5}. Đây là tập itemset duy nhat ma tir do chúng ta sẽ tạo ra các luật kết hợp. 7 : Tao Association Rules ttr tap Frequent Itemsets Chỉ các luật kết hợp mạnh được tạo ra Frequent itemsets thoa nguGng minimum support threshold Cac rules manh thoa cac nguéng minimum confidence threshold confidence(A© B) = Pr(B | A) = For each frequent itemset, f, generate all non-empty subsets off For every non-empty subset s off do if support(f)/support(s) > min_confidence then output rule s ==> (f-s) end Generating Association Rules (Example Continued) Item sets: {1,3} va {2,3,5} Nhu da hoc confidence cua rule LHS 0 RHS 1a Support cua itemset (i.
LHS U RHS) chia cho support cua LHS. 8: Frequent Patterns Without Candidate Generation Bottlenecks of the Apriori approach Breadth-first (i., level-wise) search Candidate generation and test (Often generates a huge number of candidates) The FPGrowth Approach (J. Yin, 2000) Depth-first search; avoids explicit candidate generation Basic Idea: Grow long patterns from short ones using locally frequent items only “abc” is a frequent pattern; get all transactions having “abc” *đ” 1s a local frequent item in DB|abc > abcd is a frequent pattern Approach: Use a compressed representation of the database using an FP-tree Once an FP-tree has been constructed, it uses a recursive divide-and-conquer approach to mine the frequent itemsets Extensions: Multiple-Level Association Rules Items often form a hierarchy Items at the lower level are expected to have lower support Rules regarding itemsets at appropriate levels could be quite useful Transaction database can be encoded based on dimensions and levels Hình 1. 9: Mining Multi-Level Associations A top_down, progressive deepening approach First find high-level strong rules: > milk — bread [20%, 60%] Then find their lower-level “weaker” rules: 2% milk > wheat bread [6%, 50%] When one threshold set for all levels; if support too high then it is possible to miss meaningful associations at low level; if support too low then possible generation of uninteresting rules different minimum support thresholds across multi-levels lead to different algorithms (e., decrease min-support at lower levels) Variations at mining multiple-level association rules 4Level-crossed association rules: milk + wonder wheat bread Association rules with multiple, alternative hierarchies: 2% milk > wonder bread Extensions: Quantitative Association Rules Handling quantitative rules may requires discretization of numerical attributes Associations in Text / Web Mining Document Associations Find (content-based) associations among documents in a collection Documents correspond to items and words correspond to transactions Frequent itemsets are groups of docs in which many words occur in common Term Associations Find associations among words based on their occurrences in documents Similar to above, but invert the table (terms as items, and docs as transactions) Associations in Web Usage Mining Association Rules in Web Transactions Discover affinities among sets of Web page references across user sessions 10 Examples 60% of clients who accessed /products/, also accessed / products / software / webminer.htm 30% of clients who accessed /special-offer.html, placed an online order in /products/software/ Actual Example from IBM official Olympics Site: {Badminton, Diving} ==> {Table Tennis} [conf = 69.35%] Applications Use rules to serve dynamic, customized contents to users Prefetch files that are most likely to be accessed Determine the best way to structure the Web site (site optimization) Targeted electronic advertising and increasing cross sales 7.
Associations in Recommender Systems Il. Mining Frequent Patterns II: Mining Sequential & Navigational Patterns 1. Sequential pattern mining Khai phá luật kết hợp không xem xét thứ tự của các giao dich. Trong nhiều ứng dụng, thứ tự lại rất quan trọng.
VD: 11 Trong phân tích thị trường, thật thú vị khi biết liệu mọi I8ƯỜời có mua một số mặt hàng theo trình tự, VD, mua giường trước rồi một thời gian sau mua ga trải giường. Trong khai thác sử dụng Web, rất hữu ích khi tìm các pattern về các đường hướng truy cập của người dùng trong một trang Web từ các chuỗi truy cập trang của người dùng 2. Sequential Patterns Extending Frequent ltemsets Cac Sequential patterns b6 sung thém sé chiéu (dimension) vao frequent itemsets va association rules — thoi gian. Trước, sau, cùng lúc xuất hiện.
Dạng thức: “x% thời gian, khi A xuất hiện trong l transaction, B xuất hiện trong z transactions.” Lưu ý rằng các mục khác có thê xuất hiện giữa A và B, vi vậy các mẫu tuần tự không nhất thiết ngụ ý sự xuất hiện liên tiếp của các mục (về mặt thời gian) Examples Thuê “Star Wars”, sau đó “Emprre Strikes Back”, sau đó “Return of the Jedi” Tập hợp các sự kiện được sắp xếp trong một khoảng thời gian Hầu hết các thuật toán khám phá mẫu tuần tự đều dựa trên phần mở rộng của thuật toán Apriori đề khám phá các tập mục Navigational Patterns Một dạng thức đặc biệt của sequential patterns phi nhận patterns đường hướng truy cập của người dùng web 1 session duoc xem nhu | don vi thoi gian Objective Cho | tap S là tap input data sequences, bai toan mining sequential patterns 1a tim tat cả sequences thỏa độ support tối thiêu Sequence như vậy được gọi là một frequent sequence, hay một sequential pattern Độ support của | sequence ty 1é data sequences trong S c6 chira sequence nay 12 Sequence Databases Một sequence database một danh sách elements hay events Mỗi element co thé là một tập items hay một item lẻ (tập 1 item) Transaction databases và sequence databases Subsequence va super sequence M6Ot sequence la mét danh sach cac events, ky hiéu la<el e2. el > Cho 2 sequences o=<al a2. an > va B=< bl b2. bm > a dugc goi la mét subsequence cua B, ky hiéu la a& B, néu ton tai các số nguyên I< jI <j2 <.<jn <m sao cho al € bj1, a2 € bỊ2,., an C bịn Examples: < (ab), d> là một subsequence cua < (abc), (de)> (3, (4, 5), 8) la m6t subsequence của) (6, (3, 7), 9, (4, 5, 8), 3, 8)) C <a.html> Sequential Pattern Mining la gi? Cho một tập các sequences va support threshold, tim tap frequent subsequences 13 3.
Another Example Transactions duoc xếp theo Customer ID Example (continued) 14 GSP mining algorithm Tương tự Apriori algorithm 4. Sequential Pattern Mining Algorithms Apriori-based method: GSP (Generalized Sequential Patterns: Srikant & Agrawal, 1996) Pattern-growth methods: FreeSpan & PrefixSpan (Han et al., 2000; Pei, et al.