Thuật toán apriori

Phân tích giỏ hàng trong R

Christopher Bruffaerts

Statistician

Khai phá luật kết hợp

Khai phá luật kết hợp giúp phát hiện quan hệ giữa các mục trong CSDL giao dịch lớn.

Nhiệm vụ gồm hai phần:

Sinh tập mục thường xuyên: tìm mọi tập mục thường xuyên từ CSDL giao dịch lớn. Một tập mục là thường xuyên nếu đạt ngưỡng hỗ trợ tối thiểu.
Sinh luật: từ các tập mục thường xuyên, tạo luật kết hợp có độ tin cậy trên ngưỡng độ tin cậy tối thiểu.

Thuật toán apriori là thuật toán cổ điển, nhanh thuộc nhóm khai phá luật kết hợp.

Ý tưởng của thuật toán apriori

Thuật toán apriori:

Tiếp cận từ dưới lên
Sinh tập mục ứng viên dựa trên nguyên lý apriori

Nguyên lý apriori:

Nếu một tập mục là thường xuyên, mọi tập con của nó cũng thường xuyên.
- vd. nếu {A,B} thường xuyên, thì {A} và {B} đều thường xuyên
Với tập mục không thường xuyên, mọi siêu tập của nó đều không thường xuyên.
- vd. nếu {A} không thường xuyên, thì {A,B}, {A,C} và {A,B,C} đều không thường xuyên.

¹ Agrawal và Srikant (1994)

Ví dụ: tập 1 mục

lưới_tập_mục2

TID	Giao dịch
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ngưỡng hỗ trợ tối thiểu = 3/7 = 0,42

Ví dụ: tập 2 mục

lưới_tập_mục3

TID	Giao dịch
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ngưỡng hỗ trợ tối thiểu = 3/7 = 0,42

Ví dụ: tập 3 mục

tất_cả_tập_mục

TID	Giao dịch
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ngưỡng hỗ trợ tối thiểu = 3/7 = 0,42

Ví dụ: tập mục thường xuyên

lưới_tập_mục3

Tập mục	Đếm	Hỗ trợ
{A}	3	0,42
{B}	6	0,85
{C}	4	0,57
{D}	5	0,71
{A,B}	3	0,42
{B,C}	3	0,42
{B,D}	4	0,57
{C,D}	3	0,42

¹ Ngưỡng hỗ trợ tối thiểu = 3/7 = 0,42

Apriori: sinh luật

Sau bước sinh tập mục thường xuyên tốn chi phí, apriori sinh luật:

Bắt đầu với luật có độ tin cậy cao và vế trái một mục
- vd. {A,C} $\rightarrow$ {B}
Xây dựng luật phức tạp hơn, có nhiều mục ở vế phải
- vd. {A,C} $\rightarrow$ {B, D}

Mẹo: cắt tỉa luật kết hợp

vd.: nếu luật {B,C,D} $\rightarrow$ {A} có độ tin cậy thấp, mọi luật có A ở vế phải đều bỏ được (như {B,D} $\rightarrow$ {A, C} hoặc {D} $\rightarrow$ {A,B, C}).

Thử apriori lần đầu

Dữ liệu giao dịch

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

Gọi apriori lần đầu - tập mục thường xuyên

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Kết quả apriori - tập mục thường xuyên

Tập mục thường xuyên

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

lưới_tập_mục3

Trích xuất luật bằng apriori

Tham số: tham số khai phá quyết định đặc tính của tập mục hoặc luật thu được.

Hỗ trợ = 3/7
Độ tin cậy = 60%
Độ dài tối thiểu của luật = 2

Gọi hàm apriori để sinh luật với tham số cụ thể

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

Trích xuất luật: kết quả

Kiểm tra các luật

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Ayo berlatih!

Phân tích giỏ hàng trong R