Bài giảng Nhập môn khai phá dữ liệu - Chương 4: Khai phá luật kết hợp - Hà Quang Thụy

theo thứ tự (*) và biểu diễn 
 dưới dạng [p|P] với p là mục đầu tiên, còn P là xâu 
 mục còn lại;
 Gọi insert_tree ([p|P]), T)
 3. Tìm tập phổ biến trên cây FP
 July 12, 2021 36
Xây dựng cây FP: chèn một xâu vào cây
 July 12, 2021 37
Xây dựng cây FP
 TID Items bought (ordered) frequent items min_support = 3
 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
 200 {a, b, c, f, l, m, o} {f, c, a, b, m}
 300 {b, f, h, j, o, w} {f, b}
 400 {b, c, k, s, p} {c, b, p}
 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
 July 12, 2021 38
Lợi ích của cấu trúc FP-tree
◼ Tính đầy đủ
 ◼ Duy trì tính đầy đủ thông tin để khai phá mẫu phổ biến
 ◼ Không phá vỡ mẫu dài bới bất kỳ giao dich
◼ Tính cô đọng
 ◼ Giảm các thông tin không liên quan: mục không phổ 
 biến bỏ đi
 ◼ Sắp mục theo tần số giảm: xuất hiện càng nhiều thì 
 cành hiệu quả
 ◼ Không lớn hơn so với CSDL thông thường
July 12, 2021 39
Tìm tập phổ biến từ cấu trúc FP-tree
 July 12, 2021 40
Mẫu cực đại (Max-patterns)
 1 2
 ◼ Mẫu phổ biến {a1, , a100} → (100 ) + (100 ) +  
 1 0 0 100 30 
 + (1 0 0 ) = 2 -1 = 1.27*10 frequent sub-
 patterns!
 ◼ Mẫu cực đại: Mẫu phổ biến mà không là tập con 
 thực sự của mẫu phổ biến khác
 ◼ BCDE, ACD là mẫu cực đại
 Tid Items
 ◼ BCD không là mẫu cực đại
 10 A,B,C,D,E
 20 B,C,D,E,
 Min_sup=2 30 A,C,D,F
Tập mục phổ biến cực đại
 Tập mục cực đại (Maximal Intemset) là tập mục phổ biến không là 
 tập con thực sự của một tập mục phổ biến khác
Tập mục đóng
 ◼ Tập mục đóng là tập mục mà không là tập con thực sự 
 của một tập mục có cùng độ hỗ trợ
 ◼ X đóng: Y  X s(Y) < s(X)
 Itemset Support
 {A} 4
 TID Items
 {B} 5 Itemset Support
 1 {A,B}
 {C} 3 {A,B,C} 2
 2 {B,C,D}
 {D} 4 {A,B,D} 3
 3 {A,B,C,D}
 {A,B} 4 {A,C,D} 2
 4 {A,B,D}
 {A,C} 2 {B,C,D} 3
 5 {A,B,C,D}
 {A,D} 3 {A,B,C,D} 2
 {B,C} 3
 {B,D} 4
 {C,D} 3
Phân biệt tập mục cực đại với tập mục đóng
TID Items
 1 ABC
 2 ABCD
 3 BCE
 4 ACDE
 5 DE
Tập mục cực đại với tập phổ biến đóng
Tập mục cực đại với tập mục đóng
Tập mục cực đại với tập mục đóng
 R. Bayardo. Efficiently mining long patterns from databases. SIGMOD’98
 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent
 Closed Itemsets", DMKD'00
 Mohammed Javeed Zaki, Ching-Jiu Hsiao: CHARM: An Efficient Algorithm for
 Closed Itemset Mining. SDM 2002
 July 12, 2021 47
Luật kết hợp đa mức
 ◼ Các mục có thể phân cấp
 ◼ Đặt hỗ trợ linh hoạt: Mục cấp thấp hơn là kỳ vọng có độ 
 hỗ trợ thấp hơn.
 ◼ CSDL giao dịch có thể được mã hóa theo chiều và mức
 ◼ Thăm dò KP đa mức chia sẻ
 uniform support reduced support
 Level 1
 Milk Level 1
 min_sup = 5%
 [support = 10%] min_sup = 5%
 Level 2 2% Milk Skim Milk Level 2
 min_sup = 5% [support = 6%] [support = 4%] min_sup = 3%
 July 12, 2021 48
Kết hợp đa chiều
 ◼ Luật đơn chiều (viết theo dạng quan hệ (đối tượng, giá trị)):
 buys(X, “milk”) buys(X, “bread”)
 ◼ Luật đa chiều: 2 chiều / thuộc tính
 ◼ Luật kết hợp liên chiều (không có thuộc tính lặp)
 age(X,”19-25”)  occupation(X,“student”) buys(X,“coke”)
 ◼ Luật KH chiều-kết hợp (lai/hybrid) (lặp thuộc tính)
 age(X,”19-25”)  buys(X, “popcorn”) buys(X, “coke”)
 ◼ Thuộc tính phân lớp
 ◼ Tìm số lượng các giá trị khả năng không được sắp
 ◼ Thuộc tính định lượng
 ◼ Số, thứ tự ngầm định trong miền giá trị
July 12, 2021 49
Kết hợp đa mức: Rút gọn lọc
 ◼ Trong luật phân cấp, một luật có thể dư thừa do đã có 
 quan hệ giữa “tổ tiên” của các mục.
 ◼ Ví dụ
 ◼ milk wheat bread [support = 8%, confidence = 70%]
 ◼ 2% milk wheat bread [support = 2%, confidence = 72%]
 ◼ Nói rằng: luật đầu tiên là tổ tiên luật thứ hai.
 ◼ Một luật là dư thừa nếu độ hỗ trợ của nó là khít với giá trị 
 “mong muốn”, dựa theo tổ tiên của luật.
 July 12, 2021 50
Luật kết hợp định lượng
◼ Thuộc tính số là sự rời rạc hóa động d
 ◼ Độ tin cậy hoặc độ cô đọng của luật là cực đại
◼ Luật kết hợp định lượng 2-D: Aquan1  Aquan2 Acat
◼ Phân cụm các luật kết hợp
 Liền kề nhau từ các luật
 Tổng quát dựa trên
 Lưới 2-D 
◼ Ví dụ
age(X,”30-34”)  income(X,”24K -
48K”) 
 buys(X,”high resolution TV”)
July 12, 2021 Data Mining: Concepts and Techniques 51
Khai phá luật KH dựa theo khoảng cách
 ◼ Phương pháp đóng thùng không nắm bắt được ngữ nghĩa 
 của dữ liệu khoảng
 Equi-width Equi-depth Distance-
 Price($) (width $10) (depth 2) based
 7 [0,10] [7,20] [7,7]
 20 [11,20] [22,50] [20,22]
 22 [21,30] [51,53] [50,53]
 50 [31,40]
 51 [41,50]
 53 [51,60]
 ◼ Phân vùng dựa trên khoảng cách, rời rạc có ý nghĩa hơn 
 khi xem xét :
 ◼ Mật độ/ số điểm trong một khoảng
 ◼ Tính “gần gũi” của các điểm trong một khoảng
 July 12, 2021 52
Độ đo hấp dẫn: Tương quan (nâng cao)
 ◼ play basketball eat cereal [40%, 66.7%] là lạc
 ◼ Phần trăm chung của sinh viên ăn ngũ cốc là 75% cao hơn so với 
 66.7%.
 ◼ play basketball not eat cereal [20%, 33.3%] là chính xác hơn, do 
 độ hỗ trợ và tin cậy thấp hơn
 ◼ Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao)
 Basketball Not basketball Sum (row)
 P(A B) Cereal 2000 1750 3750
 Not cereal 1000 250 1250
 corrA,B =
 P(A)P(B) Sum(col.) 3000 2000 5000
 July 12, 2021 53
KPDL dựa trên ràng buộc
 ◼ Tìm mọi mẫu trong CSDL tự động? — phi hiện thực!
 ◼ Mẫu có thể quá nhiều mà không mục đích!
 ◼ KPDL nên là quá trình tương tác
 ◼ Người dùng trực tiếp xác định KPDL gì khi dùng ngôn 
 ngữ hỏi KPDL (hoặc giao diện đồ họa)
 ◼ KP dựa theo ràng buộc
 ◼ Linh hoạt người dùng: cung cấp ràng buộc : cái được KP
 ◼ Tối ưu hệ thống: thăm dò các ràng buộc để hiệu quả 
 KP: KP dựa theo ràng buộc
 July 12, 2021 54
Ràng buộc trong KPDL
 ◼ Ràng buộc kiểu tri thức
 ◼ classification, association, v.v.
 ◼ Ràng buộc dữ liệu: dùng câu hỏi kiếu SQL
 ◼ Tìm các cặp sản phẩm mua cùng nhau trong Vancouver vào Dec.’00
 ◼ Ràng buộc chiều/cấp
 ◼ Liên quan tới vùng, giá, loại hàng, lớp khách hàng
 ◼ Ràng buộc luật (mẫu)
 ◼ Mua hàng nhỏ (price $200)
 ◼ Ràng buộc hấp dẫn
 ◼ Luật mạng: min_support 3%, min_confidence 60%
 July 12, 2021 55
KP ràng buộc tìm kiếm dựa theo ràng buộc
 ◼ KP ràng buộc tìm/lập luận theo ràng buộc
 ◼ Cả hai hướng tới rút gọn không gian tìm kiếm
 ◼ Tìm mọi mẫu bảm đảm ràng buộc tìm một vài (một_ câu trả lời 
 của tìm dựa theo ràng buộc trong AI (TTNT)
 ◼ Cố tìm theo ràng buộc tìm kiếm heuristic
 ◼ Tích hợp hai cái cho một bài toán tìm kiếm thú vị
 ◼ KP ràng buộc quá trình hỏi CSDL quan hệ
 ◼ Quá trình hỏi trong CSDL quan hệ đòi hỏi tìm tất cả
 ◼ KP mẫu ràng buộc chung một triết lý tương tựng như cố 
 gắng chọn về chiều sâu của câu hỏi
 July 12, 2021 56
KP mấu PB ràng buộc: tối ưu hóa câu hỏi
 ◼ Cho một câu hỏi KP mấu phổ biến với một 
 tập ràng buộc C, thì thuật toán nên là
 ◼ Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C
 ◼ đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C
 ◼ Giải pháp “thơ ngây” (naïve)
 ◼ Tìm tất cả tập PB sau đó kiểm tra ràng buộc
 ◼ Tiếp cận hiệu quả hơn
 ◼ Phân tích tính chất các ràng buộc một cách toàn diện
 ◼ Khai thác chúng sâu sắc có thể nhất trong tính toán mẫu PB.
 July 12, 2021 57
Tính chống đơn điêu trong KP theo ràng buộc
 TDB (min_sup=2)
 ◼ Chống đơn điệu (Anti-monotonicity) TID Transaction
 ◼ Một tập mục S vi phạm ràng buộc, 10 a, b, c, d, f
 mọi tập lớn hơn nó cũng vi phạm 20 b, c, d, f, g, h
 30 a, c, d, e, f
 ◼ sum(S.Price) v là chống đơn điệu 40 c, e, f, g
 ◼ sum(S.Price) v là không chống đơn 
 Item Profit
 điệu a 40
 ◼ Ví dụ. C: range(S.profit) 15 là chống b 0
 đơn điệu c -20
 d 10
 ◼ Tập mục ab vi phạm C e -30
 f 30
 ◼ Cũng vậy mọi tập chứa ab
 g 20
 h -10
 July 12, 2021 58
Ràng buộc nào là chống đơn điệu
 Ràng buộc Chống đơn điệu
 v S No
 S  V no
 S  V yes
 min(S) v no
 min(S) v yes
 max(S) v yes
 max(S) v no
 count(S) v yes 
 count(S) v no
 sum(S) v ( a S, a 0 ) yes
 sum(S) v ( a S, a 0 ) no
 range(S) v yes
 range(S) v no
 avg(S)  v,  { =, , } convertible
 support(S)  yes
 support(S)  no
 July 12, 2021 59
Tính đơn điệu trong KP luật dựa theo ràng buộc
 TDB (min_sup=2)
 ◼ Tính đơn điệu TID Transaction
 ◼ Khi một tập mục S thỏa mãn ràng 10 a, b, c, d, f
 buộc, thì mọi tập lớn hơn của nó 20 b, c, d, f, g, h
 30 a, c, d, e, f
 cũng thỏa mãn 40 c, e, f, g
 ◼ sum(S.Price) v là đơn điệu Item Profit
 a 40
 ◼ min(S.Price) v là đơn điệu b 0
 ◼ Ví dụ. C: range(S.profit) 15 c -20
 d 10
 ◼ Tập mục ab đảm bảo C e -30
 f 30
 ◼ Cũng vậy mọi tập chứa ab
 g 20
 h -10
 July 12, 2021 60
Ràng buộc đơn điệu
 Ràng buộc Đơn điệu
 v S yes
 S  V yes
 S  V no
 min(S) v yes
 min(S) v no
 max(S) v no
 max(S) v yes
 count(S) v no
 count(S) v yes
 sum(S) v ( a S, a 0 ) no
 sum(S) v ( a S, a 0 ) yes
 range(S) v no
 range(S) v yes
 avg(S)  v,  { =, , } convertible
 support(S)  no
 support(S)  yes
 July 12, 2021 61
Tính cô đọng
 ◼ Tính cô đọng:
 ◼ Cho A1, là tập mục bảo đảm một ràng buộc cô đọng 
 C, thì mọi S bảo đảm C là dựa trên A1 , chằng hạn, S
 chứa một tập con thuộc A1
 ◼ Tư tưởng: Bỏ qua xem xét toàn bộ CSDL giao dịch, 
 có chăng một tập mục S bảo đảm ràng buộc C có thể 
 được xác định dựa theo việc chọn các mục
 ◼ min(S.Price) v là cô đọng
 ◼ sum(S.Price) v không cô đọng
 ◼ Tối ưu hóa: Nếu C là cô đọng có thể đẩy đếm trước
 July 12, 2021 62
Ràng buộc cô đọng
 Ràng buộc Cô đọng
 v S yes
 S  V yes
 S  V yes
 min(S) v yes
 min(S) v yes
 max(S) v yes
 max(S) v yes
 count(S) v weakly
 count(S) v weakly
 sum(S) v ( a S, a 0 ) no
 sum(S) v ( a S, a 0 ) no
 range(S) v no
 range(S) v no
 avg(S)  v,  { =, , } no
 support(S)  no
 support(S)  no
 July 12, 2021 63
Thuật toán Apriori— Ví dụ
 Database D itemset sup. itemset sup.
 L1
 TID Items C1 {1} 2 {1} 2
 100 1 3 4 {2} 3
 Scan D {2} 3
 200 2 3 5 {3} 3 {3} 3
 300 1 2 3 5 {4} 1 {5} 3
 400 2 5 {5} 3
 C itemset
 2 itemset sup C2
 {1 2}
 L2 itemset sup {1 2} 1 Scan D
 {1 3} 2 {1 3} 2 {1 3}
 {2 3} 2 {1 5} 1 {1 5}
 {2 5} 3 {2 3} 2 {2 3}
 {2 5}
 {3 5} 2 {2 5} 3
 {3 5} 2 {3 5}
 C3 itemset Scan D L3 itemset sup
 {2 3 5} {2 3 5} 2
 July 12, 2021 64
Thuật toán Naïve: Apriori +ràng buộc
 Database D itemset sup. itemset sup.
 L1
 TID Items C1 {1} 2 {1} 2
 100 1 3 4 {2} 3
 Scan D {2} 3
 200 2 3 5 {3} 3 {3} 3
 300 1 2 3 5 {4} 1 {5} 3
 400 2 5 {5} 3
 C itemset
 2 itemset sup C2
 {1 2}
 L2 itemset sup {1 2} 1 Scan D
 {1 3} 2 {1 3} 2 {1 3}
 {2 3} 2 {1 5} 1 {1 5}
 {2 5} 3 {2 3} 2 {2 3}
 {2 5}
 {3 5} 2 {2 5} 3
 {3 5} 2 {3 5}
 C3 itemset Scan D L3 itemset sup Constraint: 
 {2 3 5} {2 3 5} 2 Sum{S.price < 5}
 July 12, 2021 65
Apriori ràng buộc: Đẩy RB chống Đ Đ xuống đáy
 Database D itemset sup. itemset sup.
 L1
 TID Items C1 {1} 2 {1} 2
 100 1 3 4 {2} 3
 Scan D {2} 3
 200 2 3 5 {3} 3 {3} 3
 300 1 2 3 5 {4} 1 {5} 3
 400 2 5 {5} 3
 C itemset
 2 itemset sup C2
 {1 2}
 L2 itemset sup {1 2} 1 Scan D
 {1 3} 2 {1 3} 2 {1 3}
 {2 3} 2 {1 5} 1 {1 5}
 {2 5} 3 {2 3} 2 {2 3}
 {2 5}
 {3 5} 2 {2 5} 3
 {3 5} 2 {3 5}
 C3 itemset Scan D L3 itemset sup Constraint: 
 {2 3 5} {2 3 5} 2 Sum{S.price < 5}
 July 12, 2021 66
Apriori ràng buộc: Đẩy RB chống Đ Đ xuống đáy
 Database D itemset sup. itemset sup.
 L1
 TID Items C1 {1} 2 {1} 2
 100 1 3 4 {2} 3
 Scan D {2} 3
 200 2 3 5 {3} 3 {3} 3
 300 1 2 3 5 {4} 1 {5} 3
 400 2 5 {5} 3
 C itemset
 2 itemset sup C2
 {1 2}
 L2 itemset sup {1 2} 1 Scan D
 {1 3} 2 {1 3} 2 {1 3}
 {2 3} 2 {1 5} 1 {1 5}
 {2 3}
 {2 5} 3 {2 3} 2
 {2 5}
 {3 5} 2 {2 5} 3
 {3 5} 2 {3 5}
 C3 itemset Scan D L3 itemset sup Constraint: 
 {2 3 5} {2 3 5} 2 min{S.price <= 1 }
 July 12, 2021 67
Luật kết hợp hiếm và luật kết hợp âm
 ◼ Luật kết hợp hiếm hàm ý chỉ các LKH không xảy ra
 thường xuyên trong CSDL.
 ◼ Ví dụ
 ◼ “máy pha cà phê” → “máy xay cà phê” (0.8%, 80%).
 [Koh05] Koh Y. S., Rountree N. (2005). Finding Sporadic Rules Using
 Apriori-Inverse. Proc. of PAKDD2005, pp. 97-106.
 ◼ “ăn chay” → “bệnh tim mạch”. [Szathmary10] Szathmary L.,
 Valtchev P., and Napoli A. (2010). Generating Rare Association Rules
 Using Minimal Rare Itemsets Family. International Journal of Software
 and Informatics, Vol. 4 (3), pp. 219-238.
 ◼ "thuốc hạ lipid trong máu Cerivastatin" → "tác động 
 xấu khi điều trị“. [Szathmary10] 
 ◼ Luật kết hợp âm hàm ý chỉ các LKH mà các mục là
 xung khắc nhau trong CSDL “nếu A thì không B”.
 68
Luật hiếm: Phân loại
 [Koh16] Yun Sing Koh, Sri Devi Ravana. Unsupervised Rare Pattern Mining: A 
 Survey. TKDD 10(4): 45 (2016) 69
Khai phá luật kết hợp hiếm
 ◼ Hai hướng tiếp cận chính phát hiện luật hiếm:
 ◼ Sử dụng ràng buộc
 ◼ Sử dụng ranh giới 
 ◼ Hạn chế của cách tiếp cận hiện tại:
 ◼ Sinh mọi tập không phổ biến chi phí cao.
 ◼ Thực hiện trên CSDL tác vụ.
 70
Luật kết hợp hiếm sporadic tuyệt đối
 ◼ Luật hiếm Sporadic tuyệt đối (Koh và csự - 2005):
 ◼ Luật kết hợp dạng X → Y sao cho:
 ▪ Thuật toán tìm các tập Sporadic tuyệt đối: Apriori-Inverse 
 ▪ Hạn chế:
 • Thuật toán có hiệu quả ở mức trung bình so với các thuật 
 toán khác.
 • Chỉ được tìm trên các CSDL tác vụ.
 Cần phát triển thuật toán phát hiện luật Sporadic tuyệt đối
 hiệu quả hơn, và phát hiện luật này cả trên CSDL định lượng
 71
Luật kết hợp Sporadic tuyệt đối hai ngưỡng
 ◼ Mục đích nghiên cứu:
 ◼ Phát triển thuật toán phát hiện luật Sporadic tuyệt đối hiệu 
 quả hơn.
 ◼ Đề xuất mở rộng bài toán: tìm các luật A → B sao cho:
 ❖ Đóng góp chính:
 ▪ Bài toán phát hiện LKH tuyệt đối 2 ngưỡng là tổng quát hơn.
 ▪ Thuật toán được phát triển theo cách tiếp cận thuật toán 
 CHARM: Chỉ tìm các tập Sporadic tuyệt đối đóng 2 ngưỡng.
 72
CSDL tuần tự và Phân tích mẫu tuần tự
 Phần mềm phân tích chuỗi thời gian EidoSearch: Trợ giúp đánh dấu mẫu dữ liệu
 hấp dẫn và EidoSearch đi tìm mọi mẫu tương tự từ quá khứ và hiện tại, phân tích
 kết quả tìm kiếm này, và chỉ ra xu hướng gì sẽ xảy ra.
 Gait-CAD Matlab toolbox: trực quan hóa và phân tích chuỗi thời gian, bao gồm
 phân lớp, hồi quy, và phân cụm. Giấy phép GNU-GPL.
 Miningco: chương trình mã nguồn mở tự động tìm ra mẫu và quan hệ trong
 weblogs và các bộ dữ liệu khác.
 SAS Enterprise Miner
 XAffinity (TM): xác định mối quan hệ thân hoặc mẫu trong giao dịch và dòng dữ
 liệu nháy phím
 July 12, 2021 73
CSDL TT và PT MTT (2)
 ◼ CSDL giao dịch, CSDL chuỗi thời gian CSDL tuần tự
 ◼ Mấu PB mấu TT (PB) 
 ◼ Ứng dụng của KP Mấu TT
 ◼ Tuần tự mua của khách hàng: 
 ◼ Đầu tiên mua máy tính, sau đó CD-ROM, và sau đó là máy 
 ảnh số, trong vòng 3 tháng.
 ◼ Phẫu thuật y tế, thảm họa tự nhiên (động đất), quá trình KH 
 và kỹ nghệ, chứng khoán và thị trường.
 ◼ Mẫu gọi điện thoại, dòng click tại Weblogs
 ◼ Dãy DNA và cấu trúc gene
 July 12, 2021 74
Khái niệm KP mấu TT
 ◼ Cho một tập các dãy, tìm tập đầy đủ các dãy con 
 phổ biến
 dãy TT : 
 CSDL dãy TT
 SID sequence Một phần tử chứa một tập mục.
 10 Tập mục trong một phần tử là không thứ tự
 , và viết chúng theo ABC.
 20 
 30 là dãy con của
 40 
 Cho độ hỗ trợ min_sup =2, là mẫu tuần tự 
 sequential pattern
 July 12, 2021 75