Association rule là gì

LUẬT KẾT HỢP (Association Rules)

Bài toán phân tích giỏ hàng 

Phân tích việc mua hàng của khách hàng bằng cách tìm ra những “mối kết hợp” giữa những mặt hàng mà khách đã mua.
Bài toán được Agrawal thuộc nhóm nghiên cứu của IBM đưa ra vào năm 1994.

Khai phá luật kết hợp:
Tìm tần số mẫu, mối kết hợp, sự  tương quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác.
Tính hiểu được: dễ hiểu
Tính sử dụng được: Cung cấp thông tin thiết thực
Tính hiệu quả: Đã có những thuật toán khai thác hiệu quả
Các ứng dụng: Phân tích bán hàng trong siêu thị, cross-marketing, thiết kế catalog, loss-leader analysis, gom cụm, phân lớp, ...

Định dạng thể hiện đặc trưng cho các luật kết hợp:

• khăn ⇒ bia [0.5%, 60%]
• mua:khăn ⇒ mua:bia [0.5%, 60%]
• “Nếu mua khăn thì mua bia trong 60% trường hợp. Khăn và bia được mua chung trong 0.5% dòng dữ liệu."

Các biểu diễn khác:

• mua(x, “khăn") ⇒ mua(x, “bia") [0.5%, 60%]
• khoa(x, "CS") ^ học(x, "DB") ⇒ điểm(x, "A") [1%, 75%]

Tiền đề, vế trái luật
Mệnh đề kết quả, vế phải luật 
Support, độ hỗ trợ/ủng hộ (“trong bao nhiêu phần trăm dữ liệu thì những điều ở vế trái và vế phải cùng xảy ra")
Confidence, độ mạnh (“nếu vế trái xảy ra thì có bao nhiêu khả năng vế phải xảy ra")

2.1 Thuật toán Apriori

Nhận xét 1:
* Hai bước chính của bài toán khai thác dữ liệu dựa trên các luật kết hợp:
1.  Tạo ra tất cả tập đơn vị dữ liệu thường xuyên xảy ra (thoả ngưỡng là Min_Sup). 
2.  Từ tập các đơn vị dữ liệu thường xuyên xảy ra Y = {I1, I2, . . ., Ik }  với k >= 2, sinh ra các luật tạo ra từ các đơn vị dữ liệu này bằng cách tỡm các tập con của mỗi tập đơn vị dữ liệu và tính các độ tin cậy của chúng như trên.

Cách tiếp cận của thuật toán Apriori dựa trên nhận xét sau: Nếu bất kỳ tập k-đvdl nào là không phổ biến thì bất kỳ tập (k+1)-đvdl chứa chúng cũng sẽ không phổ biến, và ngược lại: Nếu bất kỳ tập k-đvdl nào là phổ biến thì mọi tập con của nó là phổ biến.

Ký hiệu:
- Ta gọi số đơn vị dữ liệu trong một tập hợp là số các phần tử của chúng và tập có k phần tử là k- đơn vị dữ liệu
- Gọi Lk:  Tập hợp các tập phổ biến gồm các k-đvdl. Mỗi phần tử gồm 2 trường: i) các đơn vị dữ liệu và ii) đếm số lần xuất hiện.
-  Ck : Tập hợp các tập ứng viên k- đơn vị dữ liệu. Mỗi phần tử gồm 2 trường: i) các đơn vị dữ liệu và ii) đếm số lần xuất hiện. 

Cho: (1) CSDL các giao tác, (2) mỗi giao tác là một danh sách mặt hàng được mua (trong một lượt mua của khách hàng)Frequent item sets

Tìm: tất cả luật có support >= minsupport

Tạo ứng viên Apriori

Nguyên tắc Apriori:
Những tập con của tập phổ biến cũng phải phổ biến
L3={abc, abd, acd, ace, bcd}
Tự kết: L3*L3
abcd  từ abc và abd
acde  từ acd và ace
Rút gọn: acde bị loại vì ade không có trong L3
C4={abcd}

Ví dụ về Apriori

Tập phổ biến tối đại ( maximal frequent sets). 

Định nghĩa: M là tập phổ biến tối đại nếu M là tập phổ biến và không tồn tại tập phổ biến S khác M mà  M ⊂ S

Thuật toán Apriori đã đủ nhanh?

Phần cốt lõi của thuật toán Apriori: FP tree

• Dùng các tập phổ biến kích thước (k – 1) để tạo các tập phổ biến kích thước k ứng viên
• Duyệt CSDL và đối sánh mẫu để đếm số lần xuất hiện của các tập ứng viên trong các giao tác

Tình trạng nghẽn cổ chai của thuật toán Apriori: việc tạo ứng viên

• Các tập ứng viên đồ sộ:
  
  • 104 tập phổ biến kích thước 1 sẽ tạo ra 107 tập ứng viên kích thước 2
  • Để phát hiện một mẫu phổ biến kích thước 100, ví dụ {a1, a2, …, a100}, cần tạo 2100 ≈ 1030 ứng viên.
• Duyệt CSDL nhiều lần: 
  
  • Cần duyệt (n +1 ) lần, n  là chiều dài của mẫu dài nhất

Thực tế: Đối với tiếp cận Apriori căn bản thì số lượng thuộc tính trên dòng thường khó hơn nhiều so với số lượng dòng giao tác.
Ví dụ:

• 50 thuộc tính mỗi cái có 1-3 giá trị, 100.000 dòng (không quá tệ)
• 50 thuộc tính mỗi cái có 10-100 giá trị, 100.000 dòng (hơi tệ)
• 10.000 thuộc tính mỗi cái có 5-10 giá trị, 100 dòng (quá tệ...)

Lưu ý:

• Một thuộc tính có thể có một vài giá trị khác nhau
• Các thuật toán luật kết hợp có đặc trưng là xem một cặp thuộc tính-giá trị là một thuộc tính (2 thuộc tính mỗi cái có 5 giá trị => "10 thuộc tính")  

Cải thiện hiệu quả của TT Apriori 

• Đếm tập dựa vào kỹ thuật băm: Một tập kích thước k có hashing bucket count tương ứng nhỏ hơn giới hạn thì không thể phổ biến.
• Thu nhỏ giao tác:  Một giao tác không chứa tập phổ biến kích thước k nào thì không cần xét đến ở các lần duyệt tiếp tiếp theo.
• Chia nhỏ:  Tập nào có khả năng phổ biến trong DB thì sẽ phổ biến trong ít nhất một phần chia của DB.
• Lấy mẫu:  Khai thác trên tập con của dữ liệu được cho, ngưỡng của độ ủng hộ thấp hơn + một phương thức để xác định tính đầy đủ

Thuật toán FP-Tree

Ý tưởng: Dùng đệ quy để gia tăng độ dài của mẫu phổ biến dựa trên cây FP và các mẫu được phân hoạch
Phương pháp thực hiện: 

• Với mỗi item phổ biến trong Header Table, xây dựng cơ sở điều kiện và cây điều kiện của nó
• Lặp lại tiến trình trên với mỗi cây điều kiện mới được tạo ra
• Cho tới khi cây điều kiện được tạo ra là cây rỗng hoặc chỉ bao gồm một đường đi đơn thì ngừng. Mỗi tổ hợp con các item trên đường đi đơn được tạo ra sẽ là một tập phổ biến

Các bước xây dựng cây FP-Tree

Bước 1: Duyệt CSDL, xác định tập F các item phổ biến một phần tử, sau đó loại bỏ các Item không thoả ngưỡng minsup. Sắp xếp các item trong tập F theo thứ tự giảm dần của độ phổ biến, ta được tập kết quả là L.
Bước 2: Tạo nút gốc cho cây T, và tên của nút gốc sẽ là Null. Sau đó duyệt CSDL lần thứ hai. Ứng với mỗi giao tác trong CSDL ta thực hiện 2 công việc sau:

• Chọn các item phổ biến trong các giao tác và sắp xếp chúng theo thứ tự giảm dần độ phổ biến trong tập L
• Gọi hàm Insert_tree([p|P],T) để đưa các item vào trong cây T

Những giao tác có bao gồm item E

Tạo luật kết hợp

Ghi nhớ 1:

• Tạo các tập phổ biến thì chậm (đặc biệt là các tập kích thước 2)
• Tạo các luật kết hợp từ các tập phổ biến thì nhanh

• Khi tạo các tập phổ biến, ngưỡng độ ủng hộ được sử dụng
• Khi tạo luật kết hợp, ngưỡng độ tin cậy được sử dụng

Thực tế, việc tạo các tập phổ biến và tạo các luật kết hợp thật sử chiếm thời gian bao lâu?

• Xét một ví dụ nhỏ trong thực tế…
• Các thử nghiệm được thực hiện với Citum 4/275 Alpha server có bộ nhớ chính 512 MB & Red Hat Linux release 5.0 (kernel 2.0.30)

Chọn những luật tốt nhất?

Tập kết quả thường rất lớn, cần chọn ra những luật tốt nhất dựa trên:

Các độ đo khách quan:

•  Hai các đo phổ biến: 
•  support;  và  
•  confidence

Các độ đo chủ quan (Silberschatz & Tuzhilin, KDD95)

Một luật (mẫu) là tốt nếu

•  gây bất ngờ (gây ngạc nhiên cho user); và/hoặc
•  có thể hoạt động (user có thể dùng nó để làm gì đó)

Những kết quả này sẽ được dùng trong các quá trình khám phá tri thức (KDD)

Luật Boolean và luật định lượng

Các thuộc tính định lượng: ví dụ: tuổi, thu nhập, chiều cao, cân nặng
Các thuộc tính phân loại: ví dụ: màu sắc của xe

Vấn đề: có quá nhiều giá trị khác nhau cho các thuộc tính định lượng
Giải pháp: chuyển các thuộc tính định lượng sang các thuộc tính phân loại (chuyển qua không gian rời rạc)

Các luật một chiều và nhiều chiều