Lời mở đầu

Đã bao giờ bạn thắc mắc về cách sắp xếp các món hàng trong siêu thị chưa? Hay là khi bạn mua một món hàng gì đó trên các trang web bán hàng online, nó sẽ hay đề xuất một vài món hàng nào đó ở dưới, ví dụ như khi bạn mua giày, nó sẽ hiển thị ở dưới là các loại tất… Tất cả nhờ vào Association rule. Bài viết dưới đây sẽ làm rõ những thắc mắc đó. Hãy cùng chúng mình tìm hiểu nhé.

Tổng quan nội dung bài viết

• 1. Association rule là gì ?
• 2. Một số định nghĩa cần biết
  • 2.1. Support
  • 2.2. Confidence
  • 2.3. Lift
  • 2.4. Conviction
• 3. Các thuật toán dùng cho Association rule
  • 3.1. Brute-force
    • 3.1.1. Ý tưởng thuật toán
    • 3.1.2. Mã giả
    • 3.1.3. Độ phức tạp
    • 3.1.4. Cải tiến thuật toán
    • 3.1.5. Ưu, nhược điểm của thuật toán
  • 3.2. Apriori Algorithm
    • 3.2.1. Giới thiệu
    • 3.2.2. Apriori Property
    • 3.2.3. Ý tưởng thuật toán
    • 3.2.4. Code
    • 3.2.5. Ưu, nhược điểm của thuật toán
  • 3.3. Eclat
    • 3.3.1. Thuật toán
    • 3.3.2. Ưu, nhược điểm của thuật toán
    • 3.3.3. Code
  • 3.4. FP-Growth
    • 3.4.1. Cây FP-Tree
    • 3.4.2. Thuật toán sinh cây FP-Tree
    • 3.4.3. Thuật toán đệ quy sinh các tập phổ biến
    • 3.4.4. Ưu, nhược điểm của thuật toán
    • 3.4.5. Code
• 4. Các ứng dụng trong thực tiễn
• 5. Đánh giá Association rule
• 6. Lời kết
• 7. Nguồn tham khảo

1. Association rule là gì?

Association rule (luật kết hợp) là mối quan hệ kết hợp giữa các tập thuộc tính trong cơ sở dữ liệu.

Còn Association rule learning là một kỹ thuật học không giám sát, thực hiện việc kiểm tra mức độ phụ thuộc của một mục dữ liệu trên một mục dữ liệu khác và vạch ra hướng càng có lợi càng tốt. Và nó dựa trên những luật khác nhau để khám phá mối quan hệ hoặc kết hợp có lợi giữa các biến có trong dữ liệu.

2. Một số định nghĩa cần biết

Trước khi bắt đầu, ta phải làm rõ các khái niệm sau:

\hspace{5mm}\small \bullet \hspace{2.5mm} \text{Item:}
\hspace{5mm}Ký hiệu \small I = \left\{ x_{1},x_{2},…x_{n} \right\} là tập \small n mục \small \text{(item)}.
\hspace{5mm}Ví dụ: Tập tất cả các quần áo trong cửa hàng:
\[ \text{I = {áo len, áo khoác, quần dài, váy, … }}\]

\hspace{5mm}\small \bullet \hspace{2.5mm} \text{Itemset:}
\hspace{5mm}Một tập \small X\subseteq I được gọi là một tập mục \small \text{(itemset)}.
\hspace{5mm}Nếu \small X có \small k mục \small \left( \left| X \right| = k \right) thì \small X được gọi là \small \text{k-itemset}.

\hspace{5mm}\small \bullet \hspace{2.5mm} \text{Transaction:}
\hspace{5mm}Ký hiệu \small D=\left\{ T_{1},T_{2},…T_{m} \right\} là cơ sở dữ liệu gồm \small m giao dịch \small \text{(transaction)}.
\hspace{5mm}Mỗi giao dịch \small T_{i} \in D là một tập mục, tức \small T_{i} \subseteq I.
\hspace{5mm}Ví dụ:
\hspace{5mm}Tập tất cả các mục \small \text{I = \{quần, áo, giày, dép, balo\}}
\hspace{5mm}Cơ sở dữ liệu giao dịch \small D=\left\{ T_{1},T_{2},T_{3} \right\}, trong đó:
\hspace{7.5mm}\small T_{1}=\text{\{quần, dép, balo\}}
\hspace{7.5mm}\small T_{2}=\text{\{áo, balo\}}
\hspace{7.5mm}\small T_{3}=\text{\{quần, áo, giày, dép\}}

Khá dễ hiểu phải không, bây giờ ta sẽ đến với các định nghĩa quan trọng nào.

2.1. Support

Support (Độ hỗ trợ): Tỷ lệ giữa số giao dịch chứa phần tử hoặc tập phần tử đó so với tổng số giao dịch hay cũng có thể hiểu là tần số xuất hiện của phần tử hoặc tập phần tử. Và có ký hiệu là: \small \text{ support(X)}.

Ví dụ: Một dữ liệu có thông tin 100 khách hàng. Trong đó 50 khách hàng mua \small \text{áo}, 75 khách hàng mua \small \text{quần} và 25 khách hàng mua cả \small \text{quần và áo} thì:

• \small \text{support(áo)} = 50\%
• \small \text{support(áo, quần)} = 25\%

Với luật kết hợp có dạng:
\[X\to Y\](Với \small X và \small Y là hai tập mục \small \left( X,Y\subseteq I \right) và \small X\cap Y\neq \varnothing)

Một luật \small X\to Y được gọi là phổ biến \small \text{(frequent)} nếu:
\[Support(X \to Y) \ge minsup\](Với \small minsup là giá trị \small support nhỏ nhất được chỉ định bởi người dùng)

2.2. Confidence

Confidence (Độ tin cậy): Tỷ lệ giữa số giao dịch chứa cả \small X và \small Y trên số giao dịch chỉ chứa \small X:
\[Confidence(X \to Y)\]Tiếp tục với ví dụ trên thì:
\[Confidence(\text{áo} \to \text{quần}) = \frac{Support(\text{áo}\cup \text{quần})}{Support(\text{áo})} = \frac{25}{50} = 50\%\]Nghĩa là nếu một người mua \small \text{áo} thì xác suất họ mua \small \text{quần} là 50%.

Một luật \small X \to Y được gọi là mạnh \small \text{(strong)} nếu độ tin cậy của nó lớn hơn hoặc bằng một ngưỡng \small minconf nào đó do người dùng tự định nghĩa:
\[Confidence(X \to Y) \ge minconf\]

2.3. Lift

2.3.1. Định nghĩa

Gọi \small X là item mình đã mua.
\small Y là item mà mình có khả năng sẽ mua khi đã mua \small X.
Khi đó, ta sẽ định nghĩa \small lift(X \to Y) là một tỉ lệ cho biết khả năng mà khi mua \small X, thì ta sẽ mua \small Y. Đề cập đến sự gia tăng tỷ lệ bán \small Y khi \small X được bán:
\[lift(X \to Y)=\frac{Confidence(X \to Y)}{Support(Y)}=\frac{P(X\cap Y)}{P(X)\cdot P(Y)}\]Trong đó:

• \small P(X) là khả năng xuất hiện của tập \small X.
• \small P(Y) là khả năng xuất hiện của tập \small Y.
• \small P(X\cap Y) là khả năng mà cả tập \small X , \small Y xuất hiện đồng thời cùng nhau.

!Lưu ý: với mỗi item ta không cần quan tâm đến tần số xuất hiện mà ta chỉ cần lưu ý là nó có xuất hiện hay không thôi.

Với ví dụ trên:
\[lift(\text{áo}\to \text{quần})=\frac{Confidence(\text{áo}\to \text{quần})}{Support(\text{quần})}=\frac{50}{75}=0.667\]

2.3.2. Tiêu chuẩn

Vấn đề đặt ra ở đây là ta sẽ xem xét giá trị \small lift(X \to Y) như thế nào?

• \small lift(X \to Y) = 1 \Rightarrow xác suất xuất hiện của \small X và \small Y là độc lập, không liên quan đến nhau. Dĩ nhiên, khi sự xuất hiện của nó là độc lập với nhau, thì ta sẽ không thể rút ra được bất kỳ quy tắc nào liên quan đến hai tập hợp đó.
• \small lift(X \to Y) > 1 \Rightarrow \small X và \small Y thường được mua cùng nhau. Và điều đó sẽ giúp mô hình dự đoán hoặc phân loại dữ liệu tốt hơn.
• \small lift(X \to Y) < 1 \Rightarrow \small X và \small Y ít có khả năng được mua cùng nhau.

Vậy thì với giá trị \small lift(X \to Y) nào thì mô hình của chúng ta sẽ đạt dự đoán hoặc là phân loại tốt?
Theo như những gì mình đã phân tích ở trên, thì ta có thể dễ dàng nhận thấy rằng khi giá trị \small lift(X \to Y) > 1 mô hình sẽ hoạt động tốt hơn.
Ví dụ: Qua nhận xét ở trên, ta nhận thấy rằng, với giá trị \small lift(\text{áo}\to \text{quần}) đã tính thì \small \text{áo} và \small \text{quần} rất ít khi được mua cùng nhau.

2.4. Conviction

Conviction là tỉ số của tần số mong đợi mà \small X xảy ra mà không có \small Y hay nói cách khác đó là tần số mà quy tắc đưa ra dự đoán không chính xác.
\[\small Conv(X \to Y)=\frac{1-Support(Y)}{1-Confidence(X \to Y)}\]Ví dụ:
\[Conv(\text{áo} \to \text{quần})=\frac{1-Support(\text{quần})}{1-Confidence(\text{áo} \to \text{quần})}=\frac{1-0.75}{1-0.5}=0.5\]Giá trị trên cho ta thấy rằng, khả năng mà người dùng mua \small \text{quần} và \small \text{áo} cùng nhau là chính xác đến 50%.
Thông qua định nghĩa, ta có thể dễ dàng nhận ra được rằng, khi giá trị \small conv(X \to Y) lớn hơn 1 thì điều đó có nghĩa là \small X và \small Y không được mua cùng nhau quá thường xuyên. Hay nói cách khác, giá trị \small conv(X \to Y) càng lớn thì xác suất \small X và \small Y được mua cùng nhau càng nhỏ.

3. Các thuật toán dùng cho Association rule

Qua một vài khái niệm ở trên, có lẽ nhiều bạn sẽ thắc mắc về cách tìm những quy tắc kết hợp đó đúng không nào? Hãy cùng chúng mình tìm hiểu về các thuật toán dùng trong Association Rules nhé!

3.1. Brute-force

Mình nghĩ rằng nếu các bạn đọc bài viết này, ắt hẳn các bạn đã có một nền kiến thức khá vững chắc về Nhập môn lập trình rồi. Do đó, có lẽ thuật toán “Brute-force” không quá xa lạ đối với các bạn.

3.1.1. Ý tưởng thuật toán

Brute-force trong lập trình thi đấu hay trong Association Rule nó đều mang đến tư tưởng là quét hết mọi trường hợp để tìm ra trường hợp tối ưu, kết quả bài toán.

Vì các bạn đã có một nền kiến thức căn bản về “Brute-force” rồi nên là mình sẽ nói sơ lược về thuật toán như sau:

• Đầu tiên, mình sẽ tạo hết tất cả các \small transaction có thể có giữa các \small item.
• Sau đó, với mỗi \small transaction, ta sẽ tính toán các thông số \small support, confidence, lift của nó.
• Sau đó, dựa trên các thông số đó, ta sẽ chọn ra \small transaction phù hợp với tiêu chí mà mình cần tìm.

3.1.2. Mã giả

Vì đây là thuật toán khả đơn giản và ít được sử dụng trong AR nên mình sẽ chỉ đưa ra mã giả cho các bạn hiểu hơn về thuật toán và ý tưởng.

3.1.3. Độ phức tạp

Giả sử có \small M =2^d(với \small d là số items ban đầu) ứng cử viên và \small N giao dịch, \small w là số mặt hàng trong giao dịch tối đa thì độ phức tạp là \small O(MNw).

3.1.4. Cải tiến thuật toán

Ta có thể thấy rằng, với ý tưởng sơ khai của nó, độ phức tạp là quá lớn. Nhưng ta hãy dừng lại khoảng chừng 5s để nhìn lại thuật toán này? Liệu ta có thể đặt vài “nhánh cận” để tối ưu hơn thuật toán không? Ta có cần phải bắt buộc phải chọn những cái giá trị mà ta biết rằng nó sẽ không cần thiết cho yêu cầu của chúng ta không?

Với những suy nghĩ đó, người ta đã nghĩ ra cách tối ưu như sau:

• Đầu tiên, chúng ta sẽ chọn một ngưỡng tối thiểu của giá trị \small support và \small confidence (\small minsup và \small minconf).
• Việc đặt ra các ngưỡng này để ta chọn ra các quy tắc (được tạo ra từ việc kết hợp các món hàng lại với nhau) mà nó có giá trị \small support và \small confidence không nhỏ hơn \small minsup và \small minconf. Điều này tác dụng rất lớn đến việc giảm thời gian thực thi.
• Sắp xếp các quy tắc theo thứ tự giảm dần của giá trị \small lift. (Vì giá trị \small lift càng lớn thì mô hình càng hoạt động tốt hơn).

3.1.5. Ưu nhược điểm của thuật toán

• Ưu điểm: Dễ hiểu, dễ code, tư duy đơn giản.
• Nhược điểm: Tốn khá nhiều thời gian thực hiện. Mặc dù sau khi cải tiến thuật toán, các quy tắc còn lại đã giảm đi rất nhiều. Tuy nhiên, thời gian thực hiện vẫn rất lớn.

Chính vì điều đó, đã thôi thúc cho con người suy nghĩ và cải tiến những thuật toán tốt hơn. Để tìm hiểu rõ hơn, hãy cùng chúng mình khám phá tiếp ở các phần sau nhé.

3.2. Apriori Algorithm

3.2.1. Giới thiệu

Apriori Algorithm là thuật toán được phát minh bởi R.Agrawal và R.Srikant vào năm 1994. Đây là thuật toán được dùng để tìm ra các mối quan hệ có cấu trúc giữa các item khác nhau có liên quan. Ứng dụng nổi bật của nó là đề xuất các sản phẩm dựa trên các sản phẩm đã có trong giỏ hàng của người dùng. Và đây cũng là một trong những thuật toán phổ biến nhất khi nhắc đến AR.

Cụ thể trong bài viết này, mình sẽ trình bày về các tìm ra quy tắc kết hợp giữa các mặt hàng, nghĩa là các mặt hàng thường được mua cùng nhau.

3.2.2. Apriori Property

Nếu \small X là một tập xuất hiện thường xuyên, thì cũng có nghĩa là tất cả các tập con của \small X đều là tập xuất hiện thường xuyên. Điều này có thể dễ dàng thấy được, bởi vì mỗi lần \small X xuất hiện thì các tập con của nó đều xuất hiện hay nói cách khác:
\[Support(X) \le Support(Y), \text{với } Y \subseteq X.\]Ví dụ như: \small X=\left\{ mut,banh\ tet,banh\ chung \right\} xuất hiện thì các phần tử của \small X là \small \{mut\},\ \{banh\ tet\},\ \{banh\ chung\} đều đồng thời xuất hiện. Do đó, quy tắc ở trên là hoàn toàn đúng.

Như một quy tắc đảo của quy tắc ở trên, ta có quy tắc sau: nếu \small Y là một tập xuất hiện không thường xuyên, thì điều đó cũng có nghĩa là các tập lớn hơn \small Y mà xuất phát từ \small Y thì đều xuất hiện không thường xuyên. Do đó, một hệ quả được rút ra là, nếu \small Y là tập xuất hiện không thường xuyên thì ta không cần tiếp tục tìm thêm nữa.

Để hiểu rõ hơn, ta nhìn qua ví dụ sau: \small Y=\left\{ tet,thi\ hk \right\} nó không xuất hiện thường xuyên, có nghĩa là khi \small \{tet\} xuất hiện thì \small \{thi\ hk\} không xuất hiện và ngược lại. Do đó ta có thể dễ dàng thấy rằng, nếu \small X=\left\{ tet,thi\ hk,banh\ chung \right\} thì nó cũng không phải là một tập hợp xuất hiện thường xuyên.

3.2.3. Ý tưởng thuật toán

• Bước 1: Tính giá trị \small support cho tất cả các \small transaction ( \small k=1 , với \small k là số item trong \small transaction đó). Đây gọi là bước tạo các tập ứng cử viên.
• Bước 2: Loại bỏ các quy tắc có giá trị \small support và \small confidence nhỏ hơn ngưỡng đã cho.
• Bước 3: Nối các tập phổ biến để tạo thành các tập hợp có kích thước \small k+1 và lặp lại các bước trên cho đến khi không thể tạo thêm tập phổ biến nào nữa.

Để hiểu rõ hơn về thuật toán, ta sẽ nhìn vào mã giả sau:

Sau khi nhìn vào mã giả và ý tưởng thuật toán, có lẽ các bạn cũng đã hình dung một phần nào đó rồi đúng không. Để cụ thể hơn, mình sẽ đi qua ví dụ sau:

Giả sử mình có bộ dữ liệu sau, bên cạnh đó, mình chọn giá trị:
\[minsup=2, minconf=60%\]

i-transaction	item
\small T_{1}	\small i_{1},i_{2},i_{5}
\small T_{2}	\small i_{2},i_{4}
\small T_{3}	\small i_{2},i_{3}
\small T_{4}	\small i_{1},i_{2},i_{4}
\small T_{5}	\small i_{1},i_{3}
\small T_{6}	\small i_{2},i_{3}
\small T_{7}	\small i_{1},i_{3}
\small T_{8}	\small i_{1},i_{2},i_{3},i_{5}
\small T_{9}	\small i_{1},i_{2},i_{3}

\small K = 1. Ban đầu, ta có bảng giá trị \small support của các item như sau:

item	sup_count
\small i_{1}	\small 6
\small i_{2}	\small 7
\small i_{3}	\small 6
\small i_{4}	\small 2
\small i_{5}	\small 2

Sau đó, ta sẽ so sánh giá trị \small support của các item, tiến hành loại bỏ các item có giá trị \small support < minsup.
Tuy nhiên, trong ví dụ này, ta thấy rằng giá trị \small support của mỗi item đều \small \ge minsup, do đó, ta không loại bỏ item nào cả.

\small K = 2.
Ta tiến hành chọn các item ở bước \small K = 1 và ghép chúng lại với nhau.
Tuy nhiên, ta cần lưu ý là các item được chọn để ghép phải là item ở trong \small transaction ban đầu, và các tập con của item đó phải \small frequent, nếu không thì kết quả ở bước sau sẽ không khả quan.

itemset	sup_count
\small i_{1},i_{2}	\small 4
\small i_{1},i_{3}	\small 4
\small i_{1},i_{4}	\small 1
\small i_{1},i_{5}	\small 2
\small i_{2},i_{3}	\small 4
\small i_{2},i_{4}	\small 2
\small i_{2},i_{5}	\small 2
\small i_{3},i_{4}	\small 0
\small i_{3},i_{5}	\small 1
\small i_{4},i_{5}	\small 0

Giống bước trước, ta lại tiếp tục loại bỏ những itemset có \small support < minsup. Sau khi thực hiện, bảng giá trị của ta còn lại như sau:

itemset	sup_count
\small i_{1},i_{2}	\small 4
\small i_{1},i_{3}	\small 4
\small i_{1},i_{5}	\small 2
\small i_{2},i_{3}	\small 4
\small i_{2},i_{4}	\small 2
\small i_{2},i_{5}	\small 2

\small K = 3. Tương tự các giá trị \small K ở trên, ta có:

itemset	sup_count
\small i_{1},i_{2},i_{3}	\small 2
\small i_{1},i_{2},i_{5}	\small 2

\small K = 4. Ta thấy rằng không tồn tại itemset nào có thể tạo ra từ bước trên. Do đó, thuật toán dừng ở đây.

3.2.4. Code

Để triển khai thuật toán, trong python có hỗ trợ chúng ta thư viện \small apyori

!pip install apyori

Import các thư viện cần thiết

# Import các thư viện cần thiết
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from apyori import apriori

Tải dữ liệu. Đây là bộ dữ liệu mô tả mối liên hệ giữa các sản phẩm khác nhau với 7500 giao dịch trong suốt một tuần tại một cửa hàng bán lẻ của Pháp. Các bạn có thể tải bộ dữ liệu tại đây.

# Tải dữ liệu từ drive xuống 
!gdown --id 1y5DYn0dGoSbC22xowBq2d4po6h1JxcTQ

Load dữ liệu.

# Đọc dữ liệu từ file csv
data = pd.read_csv('/content/store_data.csv', header = None)

Có thể tới đây, bạn sẽ thắc mắc rằng tại sao phải có dòng header = None đúng không? Vâng, nếu các bạn đã quan sát dữ liệu trong link mà mình để ở trên, thì các bạn sẽ thấy rằng, bộ dữ liệu này không có header. Do đó, mặc định, nó sẽ lấy hàng đầu tiên để làm header. Vậy nên mình thêm dòng header = None để nó thêm header vào cho mình.

Bây giờ ta cùng nhau ngắm nhìn những dữ liệu đầu tiên trước nhé.

data.head()

Sau khi quan sát bộ dữ liệu, bạn có biết mối quan hệ giữa các hàng, các cột với nhau như thế nào không? Các bạn có thể dừng ở đây và đoán thử nhé.
Với bộ dữ liệu này, mỗi hàng nó sẽ tương ứng với mỗi giao dịch và mỗi cột tương ứng với một mặt hàng được mua trong giao dịch cụ thể đó. NaN cho ta biết rằng mặt hàng được đại diện bởi cột đó không được mua trong giao dịch này.
Ví dụ như trong hàng 2 (giao dịch 2), thì các mặt hàng được mua là chutney.

Tiếp đến, chúng ta sẽ nhìn xem kích thước của dữ liệu thông qua lệnh ở dưới để dễ dàng hình dung hơn về kích thước dữ liệu.

data.shape

Như chúng ta thấy thì, dữ liệu của chúng ta có kích thước là 7501 dòng và 20 cột.

Để dễ dàng làm việc, ta sẽ đẩy tất cả các dữ liệu vào list records như ở dưới:

records = []
for i in range(0, 7501):
    records.append([str(data.values[i,j]) for j in range(0, 20)])

• Vì Python có thư viện hỗ trợ để mình dùng \text{Apriori}, vì thế, ở đây mình sẽ trình bày đơn giản về cách xây dựng model thông qua hàm apriori.
• Cụ thể như sau:
  • Ở đây, mình sẽ đặt ngưỡng \small minsup = 0.005 để chọn những quy tắc kết hợp mà giá trị \small support của nó \small \geq 0.005.
  • Và ngưỡng \small minconf = 0.2 để chọn những quy tắc kết hợp có giá trị \small confidence \geq 0.2
  • Giá trị \small min\_length sẽ thể hiện cho ta biết về số itemset nhỏ nhất trong quy tắc mà ta sẽ chọn.
  • Từ đó, ta có thể thấy rằng các quy tắc kết hợp của chúng ta đã giảm đi rất nhiều, từ đó, giảm thời gian thực thi.
  • Lưu ý rằng: việc chọn giá trị \small minsup, \small minconf tác động rất lớn đến thời gian chọn ra quy tắc. Cụ thể là \small minsup,minconf càng nhỏ thì model sẽ chạy càng lâu. Do đó, ta cần chọn giá trị \small minsup,minconf phù hợp cho mỗi tình huống.

association_rules = apriori(records, min_support=0.005, min_confidence=0.2, min_length=2)
results = list(association_rules) 

Sau khi tạo model xong, mình cùng nhau nhìn ngắm lại số transaction phù hợp với các ngưỡng mà mình đã đặt ra nhé!

print(len(results)) 

Như các bạn thấy, số transaction đã giảm đi rất nhiều so với số transaction có thể có từ tập dữ liệu ban đầu. 

Để giúp model hoạt động tốt nhất, ta sẽ chọn sắp xếp lại các quy tắc theo giá trị \small lift tăng dần.

df = pd.DataFrame(columns=('Items','Antecedent','Consequent','Support','Confidence','Lift'))
 
Support =[]
Confidence = []
Lift = []
Items = []
Antecedent = [] 
 Consequent=[]
 
for record in results:
    for val in record.ordered_statistics:
        Support.append(record.support)
        Items.append(record.items)
        Antecedent.append(val.items_base)
        Consequent.append(val.items_add)
        Confidence.append(val.confidence)
        Lift.append(val.lift)
 
df['Items'] = list(map(set, Items))                                   
df['Antecedent'] = list(map(set, Antecedent))
df['Consequent'] = list(map(set, Consequent))
df['Support'] = Support
df['Confidence'] = Confidence
df['Lift']= Lift 

# Sắp xếp giảm dần theo giá trị "lift"
df.sort_values(by ='Lift', ascending = False, inplace = True) 

Bây giờ ta sẽ cùng chiêm ngưỡng các quy tắc sau khi sắp xếp lại nhé!

3.2.5. Ưu và nhược điểm

• Ưu điểm
  • Đơn giản, dễ hiểu, nhanh hơn Brute-force.
  • Nó không yêu cầu dữ liệu được gắn nhãn vì nó học không giám sát; do đó, bạn có thể sử dụng nó trong nhiều trường hợp khác nhau vì dữ liệu không được gắn nhãn thường dễ truy cập hơn.
• Nhược điểm
  • Tạo ra nhiều tập ứng cử viên \small \rightarrow tốn thời gian
  • Nếu dữ liệu nhỏ, nhiều khả năng sẽ tìm ra các quy tắc sai.
  • Kiểm tra tập dữ liệu nhiều lần, nghĩa là với mỗi tập ứng cử viên được xây dựng, thuật toán sẽ phải quét hết toàn bộ dữ liệu một lần nữa.

3.3. Eclat

Một thuật toán phổ biến khác có tên là Eclat được đề xuất bởi Zaki vào năm 2001. Đây là một phiên bản hiệu quả và mở rộng hơn của thuật toán Apriori. Trong khi phương pháp Apriori sử dụng duyệt chiều rộng (BFS) thì phương pháp Eclat sử dụng duyệt chiều sâu (DFS) giúp nó nhanh hơn Apriori.

3.3.1. Thuật toán

Trước tiên, ta hãy nhìn qua mã giả của nó

Ý tưởng đơn giản là sử dụng phần giao Id của các tập giao dịch (tidsets) để tính toán giá trị \small Support của một ứng cử viên và tránh sinh ra thế hệ của các tập con – các tập mà không xuất hiện ở cây tiền tố. Ở lần gọi hàm đầu tiên, tất cả các mục đều đi chung với tidsets của nó. Sau đó hàm lại được gọi đệ quy, với mỗi lần gọi như thế, mỗi cặp item-tidsets được xác thực và kết hợp với một cặp item-tidsets khác. Quá trình này dừng lại khi không có một cặp item-tidsets nào được tạo ra.

Ví dụ ta có các tập giao dịch sau:

• \small T_{1}=\{A,B,C\}
• \small T_{2}=\{A,B\}
• \small T_{3}=\{A\}

Đây là kiểu bố trí theo chiều ngang, bây giờ ta sẽ bố trí nó theo chiều dọc.

• Với \small k = 1, minsup = 2:
  • \small A=\{T_{1},T_{2},T_{3}\},support=3
  • \small B=\{T_{1},T_{2}\},support=2
  • \small C=\{T_{1}\},support=1

Do support của \small C < minsup nên ta sẽ loại \small C ra khỏi tập và tiếp tục sinh tập mục có độ dài \small k=2 :
\small A, B = \{T_{1},\ T_{2}\}

Ta dừng lại ở đây vì không thể sinh thêm tập mục chỉ với \small \{A,\ B\}.

Một ví dụ khác minh họa quá trình duyệt của eclat:

3.3.2. Ưu và nhược điểm

• Ưu điểm
  • Do Eclat sử dụng duyệt sâu nên ít tốn bộ nhớ hơn Apriori.
  • Thường nhanh hơn thuật toán Apriori.
  • Không quét lại tập dữ liệu để tính toán các giá trị support riêng biệt.
• Nhược điểm
  • Khi có nhiều giao dịch, Eclat tốn nhiều bộ nhớ và thời gian tính toán cho phần giao của các tập.

3.3.3. Code

!pip install pyECLAT 

Import các thư viện cần thiết

import pandas as pd
from pyECLAT import ECLAT 

Ta tiếp tục sử dụng data ở ví dụ trên nhé

data = pd.read_csv('/content/store_data.csv', header = None)
print(data.shape)
data.head().T 

Mục đích là để mang tính chất minh họa nên ta sẽ áp dụng thuật toán eclat với \small minsup = 0.05 và độ dài tập sinh là \small 2

my_eclat = ECLAT(data=data, verbose=True)
rule_indices, rule_supports = my_eclat.fit(min_support=0.05, max_combination=2, min_combination=2) 

Sau đó ta có được các luật sau

rule_supports 

3.4. FP-Growth

3.4.1. Cây FP-Tree

Thuật toán Apriori tồn tại 2 nhược điểm cơ bản sau:

• Tại mỗi bước, tập ứng cử viên phải được xây dựng.
• Để xây dựng tập ứng cử viên, thuật toán phải lặp lại bước quét tập dữ liệu.

Hai tính chất đó đã khiến thuật toán chậm. Để khắc phục những bước dư thừa đó, một thuật toán khai thác luật kết hợp đã được phát triển và có tên là Frequent Pattern Growth. Nó vượt qua các điểm yếu của thuật toán Apriori bằng cách sắp xếp lại các giao dịch trong cấu trúc dữ liệu Trie.

Để tìm hiểu về cách thuật toán hoạt động, ta xét trên ví dụ sau:

Tập tất cả các mục I

\small I = \{A, B, C, D, E\}

Cơ sở dữ liệu giao dịch D

\small D = \{T_{1}, T_{2}, T_{3}, T_{4}, T_{5}, T_{6}\} , cụ thể: \small T_{1} = \{A, B, D, E\} \small T_{2} = \{B, C, E\} \small T_{3} = \{A, B, D, E\} \small T_{4} = \{A, B, C, E\} \small T_{5} = \{A, B, C, D, E\} \small T_{6} = \{B, C, D\}

Nhằm thuận tiện cho việc minh họa, ta xem \small Support là độ đo tần số xuất hiện của phần tử hoặc tập phần tử và có \small minsup=3.

Bước đầu tiên của thuật toán là phải sắp xếp lại các mục giảm dần theo tần số xuất hiện:

Tập tất cả các mục I

\small I = \{B(6),E(5),A(4),C(4),D(4)\}

Cơ sở dữ liệu giao dịch D

\small D = \{T_{1}, T_{2}, T_{3}, T_{4}, T_{5}, T_{6}\} , cụ thể: \small T_{1} = \{B, E, A, D\} \small T_{2} = \{B, E, C\} \small T_{3} = \{B, E, A, D\} \small T_{4} = \{B, E, A, C\} \small T_{5} = \{B, E, A, C, D\} \small T_{6} = \{B, C, D\}

Bây giờ, ta sẽ xây dựng một cấu trúc dữ liệu FP-Tree có các tính chất sau:

• Mỗi nút trên cây được gắn nhãn là một mục.
• Các nút con của một nút đại diện cho các mục khác nhau.
• Mỗi nút cũng lưu thông tin về độ hỗ trợ của tập mục bao gồm tất cả các mục trên đường đi từ nút gốc đến nó.
• Có một bảng lưu tất cả các mục và con trỏ (node-link) để liên kết tất cả các vị trí xuất hiện của mỗi mục trong cây.

Mục đích xây dựng FP-Tree nhằm nén cơ sở dữ liệu trong cấu trúc gọn nhẹ và thuận lợi cho việc xử lý sau này.

3.4.2. Thuật toán sinh cây FP-Tree

Và đây là thuật toán sinh cây FP-Tree T từ cơ sở dữ liệu giao dịch D:

Minh họa các bước xây dựng cây FP-Tree T từ cơ sở dữ liệu D:

Giải thích:

\small \bullet \hspace{2.5mm} Thêm tập \small \{B, E, A, D\} vào cây.
Ở bước này, tất cả các mục liên kết với nhau theo thứ tự xuất hiện trong tập và khởi tạo giá trị \small support ban đầu là 1.

\small \bullet \hspace{2.5mm} Thêm tập \small \{B, E, C\} vào cây.
Do đã có đường đi \varnothing \rightarrow B \rightarrow E nên đơn giản chỉ là tăng giá trị \small support của hai nút \small B và \small C thêm \small 1. Và khi đó chưa có liên kết giữa nút \small E và \small C nên ta phải tạo thêm nút \small C mới liên kết với \small E và khởi tạo giá trị \small support là \small 1.

Và tương tự với các bước tiếp theo.

Kết quả sau khi xây dựng cây FP-Tree T:

Và đây là các đặc điểm của cây FP-Tree:

• Chỉ cần quét toàn bộ cơ sở dữ liệu D 2 lần để xây dựng cây FP-Tree T.
• Cây FP-Tree là một dạng biểu diễn cô đọng (compressed) của cơ sở dữ liệu giao dịch D.
• Cây FP-Tree càng nhỏ gọn càng tốt.
• Các mục càng phổ biến càng nằm gần gốc cây.
• Tất cả các tập phổ biến có thể được khai phá trực tiếp từ cây FP-Tree T thay vì từ cơ sở dữ liệu D.

3.4.3. Thuật toán đệ quy sinh các tập phổ biến

Sau khi có được một cấu trúc gọn nhẹ, bây giờ chúng ta sẽ áp dụng thuật toán FPGrowth trên FP-Tree để tìm các tập phổ biến:

Minh họa thuật toán FPGrowth:

• Với lời gọi đầu tiên: \small FPGrowth (T, P \leftarrow \varnothing , F \leftarrow \varnothing , minsup = 3)
  • Không xóa bỏ được mục không phổ biến nào (tất cả đều phổ biến).
  • \small T không phải dạng đường tuyến tính path.
  • Tiền tố (prefix) \small p = \varnothing .
  • \small y sẽ lần lượt nhận \small D(4), C(4), A(4), E(5), B(6).
  • Trước tiên \small y nhận \small D :
    • \small X \leftarrow P \cup \{y\} = \varnothing \cup \{D\} = \{D\}.
    • \small F \leftarrow F \cup \{X\} = \varnothing \cup \{\{D(4)\}\} = \{\{D(4)\}\} .
    • Có 3 đường đi tuyến tính (path) từ gốc của \small T đến nút \small D: \small BCD, cnt(D)=1;BEACD,cnt(D)=1 và \small BEAD,cnt(D)=2.
    • Tạo cây FP-Tree \small T_{\{D\}} từ 3 paths nói trên. (1)
    • Gọi đệ quy hàm \small FPGrowth(T_{\{D\}},\{D\},\{\{D(4)\}\},minsup=3)
  • \small y nhận \small C: …
  • \small y nhận \small A: …
  • \small y nhận \small E: …
  • \small y nhận \small B: …

Các bước xây dựng cây FP-Tree \small T_{\{D\}}

Với lời gọi: \small {FPGrowth(T_{\{D\}}, P = \{D\}, F = \{\{D(4)\}\}, minsup=3}):

• Loại bỏ nút C ra khỏi \small T_{\{D\}} vì \small cnt(C) = 1 + 1 = 2 < minsup = 3.
• Cây FP-Tree \small T_{\{D\}} bây giờ trở thành một đường tuyến tính: \small B(4) \rightarrow E(3) \rightarrow A(3):
  • Liệt kê các tập con của đường tuyến tính: \small B, E, BE, BA, EA, BEA.
  • Ghép các tiền tố \small P = \{D\} tạo thành các tập phổ biến: \small DB(4), DE(3), DA(3), DBE(3), DEA(3), DBEA(3).
  • Thêm các tập phổ biến vào trong \small F ta được: \small F = \{D(4), DB(4), DE(3), DA(3), DBE(3), DBA(3), DEA(3), DBEA(3)\}.
  • Lời gọi \small FPGrowth(T_{\{D\}}, P = \{D\}, F = \{\{D(4)\}\},minsup=3) kết thúc.

Khi \small y nhận các mục khác:

• \small y nhận \small C:
  • \scriptsize {F = \{D(4),\ DB(4),\ DE(3),\ DA(3),\ DBE(3),\ DBA(3),\ DEA(3),\ DBEA(3)\} \cup \{C(4),\ CB(4),\ CE(3),\ CBE(3)\}}.
• \small y nhận \small A:
  • \scriptsize {F = \{D(4),\ DB(4),\ DE(3),\ DA(3),\ DBE(3),\ DBA(3),\ DEA(3),\ DBEA(3)\} \cup \{C(4),\ CB(4),\ CE(3),\ CBE(3)\} \cup \{A(4),\ AE(4),\ AB(4),\ AEB(4)\}}.
• \small y nhận \small E:
  • \scriptsize {F = \{D(4),\ DB(4),\ DE(3),\ DA(3),\ DBE(3),\ DBA(3),\ DEA(3),\ DBEA(3)\} \cup \{C(4),\ CB(4),\ CE(3),\ CBE(3)\} \cup \{A(4),\ AE(4),\ AB(4),\ AEB(4)\} \cup \{E(5),\ EB(5)\}}.
• \small y nhận \small B:
  • \scriptsize {F = \{D(4),\ DB(4),\ DE(3),\ DA(3),\ DBE(3),\ DBA(3),\ DEA(3),\ DBEA(3)\} \cup \{C(4),\ CB(4),\ CE(3),\ CBE(3)\} \cup \{A(4),\ AE(4),\ AB(4),\ AEB(4)\} \cup \{E(5),\ EB(5)\} \cup \{B(6)\}}.

Vậy \small F bao gồm các tập phổ biến với các mức hỗ trợ khác nhau:

• \small support = 6: B
• \small support = 5: E, BE
• \small support = 4: D, C, A, DB, CB, AE, AB, ABE
• \small support = 3: DE, DA, CE, DBE, DBA, DAE, CBE, DBEA

3.4.4. Ưu và nhược điểm

• Ưu điểm
  • Nén được cơ sở dữ liệu trong một cấu trúc cây gọn nhẹ FP-Tree.
  • Chỉ cần quét cơ sở dữ liệu 2 lần.
  • Hiệu quả kể cả khi ngưỡng \small minsup bé.
• Nhược điểm
  • Thuật toán cài đặt phức tạp hơn so với Apriori.
  • Khi cơ sở dữ liệu lớn: FP-Tree lớn và khó lưu vừa trong bộ nhớ.
  • Sử dụng đệ quy (có thể khử đệ quy).

3.4.5. Code

Đầu tiên chúng ta phải cài đặt \small mlxtend

!pip install mlxtend 

Import các thư viện cần thiết

import pandas as pd
from mlxtend.frequent_patterns import fpgrowth
from mlxtend.frequent_patterns import association_rules
from mlxtend.preprocessing import TransactionEncoder

Mình sẽ dùng lại data của các ví dụ trên

data = pd.read_csv('/content/store_data.csv', header = None)
print(data.shape)
data.head().T 

Để sử dụng được thư viện \small mlxtend, ta cần phải chuyển về đúng input mà nó cần

# Converting into required format of TransactionEncoder()
trans = []
for i in range(0, data.shape[0]):
    trans.append([str(data.values[i,j]) for j in range(0, data.shape[1])]) 

trans = np.array(trans)
 
print(trans.shape)
trans

t = TransactionEncoder()
data = t.fit_transform(trans)
data = pd.DataFrame(data,columns=t.columns_, dtype=int)
 
print(data.shape)
data.head() 

Do data của chúng ta có giá trị nan, nên sau khi chuyển sang format mới sẽ xuất hiện cột nan, nhiệm vụ của ta là sẽ drop đi cột đó

data.drop('nan', axis=1, inplace=True)
print(data.shape)
data.head() 

Bây giờ thì mình áp dụng thuật toán thôi nào

res = fpgrowth(data, min_support=0.005, use_colnames=True)
res

res = association_rules(res,metric="lift",min_threshold=1)
res = res.sort_values(by=['lift'], ascending=False)
res.head(10) 

4. Các ứng dụng trong thực tiễn

Ngoài ứng dụng trong kinh doanh thì association rule còn nhiều ứng dụng khác như:

• Y học: Bác sĩ có thể dùng luật kết hợp để giúp chẩn đoán bệnh. Do có nhiều tác nhân cần xem xét khi thực hiện một chẩn đoán, như nhiều căn bệnh có chung triệu chứng. Bằng cách sử dụng association rules và machine learning-fueled data analysis, bác sĩ có thể biết được xác suất có điều kiện của một căn bệnh thông qua việc so sánh các mối quan hệ của triệu chứng từ dữ liệu trong quá khứ.
• Trải nghiệm người dùng (UX): Developer có thể thu thập dữ liệu về cách người dùng sử dụng trang web của họ như thế nào. Như vậy, họ có thể sử dụng luật kết hợp để tối ưu giao diện bằng cách phân tích nơi người dùng có xu hướng click vào và xác định hành động yêu thích của họ.
• Giải trí: Nếu bạn có các dịch vụ như Netflix hay Spotify thì bạn có thể sử dụng association rules để tăng cường phương pháp gợi ý nội dung. Và kết hợp các mô hình máy học phân tích hành vi của người dùng trong quá khứ để giới thiệu các nội dung thích hợp nhất cho họ.
• Và nhiều công dụng vi diệu khác.

5. Đánh giá Association rule

• Chưa trả lời được chính xác liệu quy tắc mà mình chọn có tốt hay không. Tuy nhiên, nếu chúng ta sử dụng giá thông số \small confidence, lift, support thì nó sẽ là một công cụ tốt để xác định các quy tắc.
• Tuy khó có thể xác định được quy tắc của chúng ta chọn có tốt hay không. Nhưng ta vẫn có thể dùng một số phương pháp để phần nào đánh giá nó. Gần gũi nhất, có lẽ là việc chia các tập dữ liệu thành tập train và test. Sau đó, ta có thể đánh giá tần suất liên kết mà bạn tìm thấy trong tập train cũng như xuất hiện trong tập test. Nếu có sự trùng lặp lớn, các quy tắc kết hợp có thể tốt.
• Cuối cùng, sau bài viết trên, ta có thể dễ dàng thấy được Association Rules là một trong những ví dụ mà ta có thể giải quyết vấn đề với sự tự động hóa khá tốt. Tuy nhiên, trong những dữ liệu mà ta thu thập được, sẽ có một vài dữ liệu “nhiễu” và điều đó có thể ảnh hưởng ít nhiều đến các quy tắc kết hợp mà ta có. Dữ liệu “nhiễu” ở đây là những dữ liệu ghi lại những hành vi mua hàng kỳ lạ của khách hàng. Do vậy, các quy tắc mà ta thu được sẽ hoạt động tốt hơn nếu được kiểm tra thủ công, nghĩa là lọc ra các dữ liệu “nhiễu”. Tuy nhiên, nhìn chung, đây là một công cụ khá tốt để áp dụng trong một số lĩnh vực của cuộc sống.

6. Lời kết

Như vậy ta đã biết được luật khai thác là gì và các ứng dụng thần kỳ của nó trong kinh doanh cũng như trong các lĩnh vực khác, cùng với đó là các thuật toán mà tùy trường hợp sẽ có ưu nhược điểm riêng, do đó hãy dựa vào tình huống để vận dụng tốt nhé. Chúc các bạn một ngày tốt lành.

7. Nguồn tham khảo

Association Rules in Data Mining – Educba

A Comprehensive Guide on Market Basket Analysis

Association Rule Learning – Coursera

Association Rule – GeeksforGeeks

What is association rule learning

Khám phá dữ liệu cùng association rules

Association rule learning -i2tutorials

Association Analysis – Hieu

Luật kết hợp

Practical Introduction to Market Basket Analysis – Asociation Rules

Association Rule Mining

Mining Association Rules in Large Databases

Association Analysis: Basic Concepts and Algorithms

Association Rules Mining General Concepts

UNDERSTANDING ASSOCIATION RULE

Association Rule Mining via Apriori Algorithm in Python (stackabuse.com)

Itemset Mining – dataminingbook.info