Khai thác tập phổ biến (frequent itemsets) với thuật toán Apriori

Chips and soda
Chips and soda

Bài toán khai thác tập phổ biến (frequent itemset) là bài toán rất quan trọng trong lĩnh vực data mining. Bài toán khai thác tập phổ biến là bài toán tìm tất cả tập các hạng mục (itemset) S có độ phổ biến (support) thỏa mãn độ phổ biến tối thiểu minsupp: supp(S) \geq minsupp.

Dựa trên tính chất của tập phổ biến, ta có phương pháp tìm kiếm theo chiều rộng (thuật toán Apriori (1994)) hay phương pháp phát triển mẫu (thuật toán FP-Growth (2000)). Trong bài viết này, ta sẽ nói về Apriori cùng với một số ví dụ minh họa khi chạy thuật toán này.

Các khái niệm cơ bản

Để minh họa cho các khái niệm, ta lấy ví dụ CSDL với các giao dịch sau.

TID (mã giao dịch) Itemset (tập các hạng mục)
1 A, B, E
2 B, D
3 B, C
4 A, B, D
5 A, C
6 B, C
7 A, C
8 A, B, C, E
9 A, B, C
  • Hạng mục (item): mặt hàng A = apple, B = bread, C = cereal, D = donuts, E = eggs.
  • Tập các hạng mục (itemset): danh sách các hạng mục trong giỏ hàng như \{A, B, C, D, E\}.
  • Giao dịch (transaction): tập các hạng mục được mua trong một giỏ hàng, lưu kèm với mã giao dịch (TID).
  • Mẫu phổ biến (frequent item): là mẫu xuất hiện thường xuyên trong tập dữ liệu như \{A, C\} xuất hiện khá nhiều trong các giao dịch.
  • Tập k-hạng mục (k-itemset): ví dụ danh sách sản phẩm (1-itemset) như \{A, B, C\}, danh sách cặp sản phẩm đi kèm (2-itemset) như \{\{A, B\}, \{A, C\}\}, danh sách 3 sản phẩm đi kèm (3-itemset) như \{\{A, B, C\}, \{B, C, E\}\}.
  • Độ phổ biến (support): được tính bằng supp(X) = \frac{count(X)}{|D|}. X = {B, C} là tập các hạng mục, D là cơ sở dữ liệu (CSDL) giao dịch.
  • Tập phổ biến (frequent itemset): là tập các hạng mục S (itemset) thỏa mãn độ phổ biến tối thiểu (minsupp – do người dùng xác định như 40% hoặc xuất hiện 5 lần). Nếu supp(S) \geq minsupp thì S là tập phổ biến.
  • Tập phổ biến tối đại (max pattern) thỏa
    • supp(X) \geq minsupp
    • không tồn tại |X’| > |X|, với X’ cũng phổ biến
  • Tập phổ biến đóng (closed pattern) thỏa
    • supp(S) \geq minsupp
    • không tồn tại |X’| > |X| mà supp(X’) = supp(X)
  • Luật kết hợp (association rule): kí hiệu X \rightarrow Y, nghĩa là khi X có mặt thì Y cũng có mặt (với xác suất nào đó). Ví dụ, A \rightarrow B; A,B \rightarrow C; B,D \rightarrow E.
  • Độ tin cậy (confidence): được tính bằng conf(X) = \frac{supp(X+Y)}{supp(X)}.

Ta có thể biến đổi CSDL về dạng nhị phân để dễ tính toán.

TID (mã giao dịch) A B C D E
1 1 1 0 0 1
2 0 1 0 1 0
3 0 1 1 0 0
4 1 1 0 1 0
5 1 0 1 0 0
6 0 1 1 0 0
7 1 0 1 0 0
8 1 1 1 0 1
9 1 1 1 0 0

Bài toán khai thác luật kết hợp

Cho độ phổ biến tối thiểu (minsupp) và độ tin cậy tối thiểu (minconf) do người dùng xác định.

Cho tập các hạng mục I={i_1, i_2, ..., i_m} và CSDL giao dịch D={t_1, t_2, ..., t_n}, với t_i={i_{i1}, i_{i2}, ..., i_{ik}}i_{ij} \in I.

Bài toán khai thác luật kết hợp là bài toán tìm tất cả các luật dạng X \rightarrow Y (X, Y là tập con của I và X giao Y = {}) thỏa mãn độ phổ biến và độ tin cậy tối thiểu. supp(X \rightarrow Y) \geq minsupp, conf(X \rightarrow Y) \geq minconf .

Quy trình khai thác luật kết hợp

Bước 1: Tìm tất cả các tập phổ biến (theo ngưỡng minsupp).

Bước 2: Xây dựng luật từ các tập phổ biến

  • Đối với mỗi tập phổ biến S, tạo ra tất cả các tập con khác rỗng của S.
  • Đối với mỗi tập con khác rỗng A của S (|A| < |S|). Luật A \rightarrow (S - A) là luật kết hợp cần tìm nếu: conf (A \rightarrow (S - A)) = \frac{supp(S)}{supp(A)} \geq minconf .

Từ bài toán khai thác luật kết hợp chuyển thành bài toán khai thác tập phổ biến : độ phức tạp tính toán cao.

Thuật toán tìm kiếm theo chiều rộng Apriori

Nguyên tắc loại bỏ của Apriori: Nếu không phải là tập phổ biến thì tập bao nó cũng không phổ biến.

Phương pháp:

  1. Tìm tất cả các tập phổ biến 1- hạng mục (C_1).
  2. Tạo các tập ứng viên kích thước k-hạng mục (k – candidate itemset) từ các tập phổ biến có kích thước (k-1)-hạng mục. Ví dụ, tạo ứng viên C_2 từ tập phổ biến C_1.
  3. Kiểm tra độ phổ biến của các ứng viên trên CSDL và loại các ứng viên không phổ biến ta được L_i (i = {1, 2, ..., k}).
  4. Dừng khi không tạo được tập phổ biến hay tập ứng viên L_k = \{\} hay C_k = \{\}.

Ví dụ thuật toán Apriori với minsupp = 50%

Apriori example
Apriori example

Mã giả

# buoc 2: loai bo de giam so luong C_{k+1}
# Input:
# c: tap ung vien kich thuoc k+1
# L_k: tap pho bien (frequent itemset) kich thuoc k
# Output:
# True/False
def has_infrequent_subset(c, L_k):
    for subset in c:
        if subset not in L_k:
            return True
        return False
# buoc 3: tao tap ung vien k+1-hang muc
# gom 2 buoc join + prune
# Input:
# L_k: tap pho bien (frequent itemset) kich thuoc k
# Output:
# C_{k+1}: tap ung vien kich thuoc k+1
def apriori_gen(L_k):
    # tap ung vien kich thuoc k+1
    C_k_1 = []
    for i1 in L_k:
        for i2 in L_k:
            # generate candidate by check length
            range_k = range(len(i1)) # range_k = {0, 1, ..., k-1}
            for k in range_k:
                if i1[k] == i2[k]: # make sure generate only 1 additional item
                    continue
                if i1[k] = minsupp:
            L_k = C_k_1
            L.append(L_k)

    return L

Đánh giá thuật toán

Apriori là thuật toán đơn giản, dễ hiểu và dễ cài đặt. Tuy nhiên, Apriori có các nhược điểm như:

  • Phải duyệt CSDL nhiều lần. Với I = {i_1, i_2, ..., i_{100}}, số lần duyệt CSDL sẽ là 100.
  • Số lượng tập ứng viên rất lớn: 2^{100} - 1 = 1.27 * 10^{30}.
  • Thực hiện việc tính độ phổ biến nhiều, đơn điệu.

Cải tiến Apriori : ý tưởng chung

  • Giảm số lần duyệt CSDL
  • Giảm số lượng tập ứng viên
  • Qui trình tính độ phổ biến thuận tiện hơn

Tham khảo thêm: http://www.kdnuggets.com/2016/04/association-rules-apriori-algorithm-tutorial.html

12 thoughts on “Khai thác tập phổ biến (frequent itemsets) với thuật toán Apriori

  1. Cho mình hỏi tại sao một database ban đầu chỉ sinh 26 luật kết hợp, nhưng khi xóa đi một số item ở một số transaction thì database đó sinh tới 1028 luật (trong khi mình nghĩ nó phải ít luật hơn). Mình dùng thuật toán Apriori để sinh luât, Bạn có thể giúp mình lí giải điều này được không? Cảm ơn bạn!

    Số lượt thích

    1. luật này sinh ra dựa vào sự xuất hiện nhiều lần của các tập item trong transaction (duplicated item set). Ví dụ bạn thấy xuất hiện item set (ABC) 100 lần trong transaction thì luật sinh ra sẽ là 1 đối với tập (ABC). Khi xoá đi AB hoặc BC hoặc AC, bạn đã tạo ra các transaction không trùng nhau, lúc này số luật sinh ra sẽ nhiều hơn ban đầu.

      Số lượt thích

  2. Hi anh!
    em đang làm 1 đề tài về Xây dựng hệ hỗ trợ chẩn đoán y khoa dựa trên các xét nghiệm và tiền sử bệnh của bệnh nhân. Đề tài áp dụng các kỹ thuật trong dataming để xây dựng hệ hỗ trợ chuẩn đoán bệnh dựa trên các thông tin khai bệnh, các xét nghiệm và tiền sử bệnh nhằm giúp hạn chế sai sót. Với vấn đề này thì em có thể dùng luật kết hợp, thuật toán apriori để làm ko ạ và data sẽ phải làm như thế nào. Hiện tại em rất rối mong được anh giúp. em cảm ơn rất nhiều.

    Số lượt thích

  3. Chào anh, em đọc đi đọc lại hoài vẫn không hiểu nổi cái luật này, mai em lại có bài test. Chắc là em không có khiếu học rồi. Dù sao em cũng rất cảm ơn tất cả thông tin anh chia sẽ. Chúc anh có một ngày vui vẻ.

    Số lượt thích

  4. Chào Anh, Em đang tìm hiểu cách lựa chọn các thuộc tính có giá trong dataset sau đó dùng mạng NN để phân loại. Em áp dụng Apriori và tìm được các luật. Anh cho em hỏi cách nào để chúng ta biết được những thuộc tính nào quan trọng từ các luật đã tìm được?

    Số lượt thích

    1. Apriori ko nói lên được độ quan trọng của luật. Trừ phi, em dùng các chỉ số như số lần xuất hiện, độ tin cậy để đo lường thì có thể định lượng được. Hoặc dùng entropy giữa thuộc tính so với tập nhãn để tính được feature important từ tập này.

      Số lượt thích

    1. mã giả cũng chỉ là lập trình logic để máy hiểu, người đọc ko phải máy nên đọc sẽ khó hiểu (cần thời gian nghiền ngẫm, ko vội được).
      em nên hiểu ý tưởng để làm việc, ở đây đại ý là muốn tìm tập các item thường đi liền với nhau (xét có thứ tự hoặc ko thứ tự) với độ đo confident/support, etc.
      đầu ra cuối cùng sẽ là thống kê các kết hợp của item trong transaction giúp cho việc truy vấn theo tập hợp được thuận tiện hơn.

      Số lượt thích

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s