Chào mừng đến với BIS Đăng nhập | Đăng ký | Trợ giúp
trong Tìm kiếm

Thuật toán Apriori khai phá luật kết hợp

Bài cuối 09-08-2014 08:48 PM của xuandungpy. 4 trả lời.
Trang 1 trong số 1 (5 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 01-01-2011 12:07 AM

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 9,370

    Thuật toán Apriori khai phá luật kết hợp

    Thuật toán Apriori khai phá luật kết hợp

    Nguyễn Văn Chức - chucnv@ud.edu.vn

    1. Luật kết hợp trong khai phá dữ liệu (Association Rule in Data Mining)

    Trong lĩnh vực Data Mining, mục đích của luật kết hợp (Association Rule - AR) là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu. Nội dung cơ bản của luật kết hợp được tóm tắt như dưới đây.

    Cho cơ sở dữ liệu gồm các giao dịch T là tập các giao dịch t1, t2, …, tn.

    T = {t1, t2, …, tn}. T gọi là cơ sở dữ liệu giao dịch (Transaction Database)

    Mỗi giao dịch ti bao gồm tập các đối tượng I (gọi là itemset)

    I = {i1, i2, …, im}. Một itemset gồm k items gọi là k-itemset

    Mục đích của luật kết hợp là tìm ra sự kết hợp (association) hay tương quan (correlation) giữa các items. Những luật kết hợp này có dạng X =>Y

    Trong Basket Analysis, luật kết hợp X =>Y có thể hiểu rằng những người mua các mặt hàng trong tập X cũng thường mua các mặt hàng trong tập Y. (X và Y gọi là itemset).

    Ví dụ, nếu X = {Apple, Banana} và Y = {Cherry, Durian} và ta có luật kết hợp X =>Y thì chúng ta có thể nói rằng những người mua Apple và Banana thì cũng thường mua Cherry và Durian.

    Theo quan điểm thống kê, X được xem là biến độc lập (Independent variable) còn Y được xem là biến phụ thuộc (Dependent variable)

    Độ hỗ trợ (Support) và độ tin cây (Confidence) là 2 tham số dùng để đo lường luật kết hợp.

    Độ hỗ trợ (Support) của luật kết hợp X =>Y là tần suất của giao dịch chứa tất cả các items trong cả hai tập X và Y. Ví dụ, support của luật X =>Y là 5% có nghĩa là  5% các giao dịch X và Y được mua cùng nhau.

    Công thức để tính support của luật X =>Y như sau:


    Trong đó: N là tổng số giao dịch.

    Độ tin cậy (Confidence) của luật kết hợp X =>Y là xác suất xảy ra Y khi đã biết X. Ví dụ độ tin cậy của luật kết hợp {Apple} =>Banana} là 80% có nghĩa là 80% khách hàng mua Apple cũng mua Banana.

    Công thức để tính độ tin cậy của luật kết hợp X =>là xác suất có điều kiện Y khi đã biết X như sau :


    Trong đó: n(X) là số giao dịch chứa X

    Để thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí: minimum support (min_sup) và  minimum confidence (min_conf)

    Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng)  cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Rle)

    Minimum support và Minimum confidence gọi là các giá trị ngưỡng (threshold) và phải xác định trước khi sinh các luật kết hợp.

    Một itemsets mà tần suất xuất hiện của nó >= min_sup goi là frequent itemsets

    Một số loại luật kết hợp

    Binary association rules (luật kết hợp nhị phân): Apple => Banana

    Quantitative association rules (luật kết hợp định lượng):

    weight in [70kg – 90kg] => height in [170cm – 190cm]

    Fuzzy association rules (Luật kết hợp mờ):  weight in HEAVY => height in TALL

    Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary association rules.

     

    2.Thuật toán sinh các luật kết hợp Apriori (by Agrawal and Srikant 1994)

    Tư tưởng chính của thuật toán Apriori là:

    - Tìm tất cả frequent itemsets:

    k-itemset (itemsets gồm k items) được dùng để tìm (k+1)- itemset.

     Đầu tiên tìm 1-itemset (ký hiệu L1). L1 được dùng để tìm L2 (2-itemsets). L2 được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy.

    - Từ frequent itemsets sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn 2 tham số min_sup và min_conf)

    Apriori Algorithm

    1.    Duyệt (Scan)  toàn bộ transaction database để có được support S của 1-itemset, so sánh S với min_sup, để có được 1-itemset (L1)

    2.    Sử dụng Lk-1 nối (join) Lk-1  để sinh ra candidate k-itemset. Loại bỏ các itemsets không phải là frequent itemsets thu được k-itemset

    3.    Scan transaction database để có được support của mỗi candidate k-itemset, so sánh S với min_sup để thu được frequent k –itemset (Lk)

    4.    Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không tìm thấy frequent itemsets)

    5.    Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng của I

    6.    Với mỗi tập con s không rỗng của I, sinh ra các luật  s => (I-s) nếu độ tin cậy (Confidence)  của nó > =min_conf

     Chẳn hạn với I= {A1,A2,A5},các tập con của I:

    {A1}, {A2}, {A5}, {A1,A2},{A1,A5},{A2,A5}

    sẽ có các luật sau

    {A1} => {A2,A5},{A2} =>{A1,A5},{A5} =>{A1,A2}

    {A1,A2} =>{A5},{A1,A5} =>{A2},{A2,A5} => {A1}

     

    Ví dụ: Giả sử ta có có sở dữ liệu giao dịch (Transaction Database -TDB) như sau :


    Thuật toán Apriori khai phá luật kết hợp được mô tả qua các bước sau


     Ta có frequent itemsets I ={B,C,E}, với min_conf =80% ta có 2 luật kết hợp là

    {B,C} => {E} và {C,E} => {B}

     

    Giả sử có cơ sở dữ liệu giao dịch bán hàng gồm 5 giao dịch như sau:


    Thuật toán Apriori tìm các luật kết hợp trong giao dịch bán hàng trên như sau:

     




    Kết quả ta có các luật kết hợp sau (với min_sup= 40%, min_conf=70%)

    R1: Beer => Diaper  (support =60%, confidence = 75%)

    R2: Diaper =>Beer (support =60%,confidence = 75%)

    R3: Milk =>Beer (support =40%, confidence = 100%)

    R4: Baby Powder => Diaper (support =40%,confidence = 100%)

     Từ kết quả các luật được sinh ra bởi giao dịch bán hàng trên, ta thấy rằng có luật có thể tin được (hợp lý) như Baby Powder => Diaper, có  luật cần phải phân tích thêm như Milk =>Beer và có luật có vẻ khó tin như Diaper =>Beer.Ví dụ này sinh ra các luật có thể không thực tế vì dữ liệu dùng để phân tích (transaction database) hay còn gọi là tranining data rất nhỏ.

    Thuật toán Apriori được dùng để phát hiện các luật kết hợp dạng khẳng định (Positive Rule X=>Y) nhị phân (Binary Association Rules) chứ không thể phát hiện các luật kết hợp ở dạng phủ định (Negative Association Rule) chẳn hạn như các kết hợp dạng “Khách hàng mua mặt hàng A thường KHÔNG mua mặt hàng B” hoặc “Nếu ủng hộ quan điểm A thường KHÔNG  ủng hộ quan điểm B”. Khai phá các luật kết hợp dạng phủ định (Mining Negative Association Rules) có phạm vi ứng dụng rất rộng và thú vị nhất là trong Marketing, Health Care và Social Network Analysis.

    PS. All comments please send to chucnv@ud.edu.vn. Thank you and Welcome!

    Từ khóa đại diện: , ,
    • Điểm chủ đề: 65
  • 01-21-2011 10:02 AM trả lời

    • BigRose
    • 150 thành viên năng nổ nhất
    • Tham gia 01-21-2011
    • Điểm 70

    Re: Thuật toán Apriori khai phá luật kết hợp

    Bài viết dễ hiểu và minh hoạ rất rõ ràng. Cảm ơn bạn Chucnv rất nhiều. Mình mới tìm hiểu về lĩnh vực này và chuẩn bị làm tốt nghiệp thấy hay nhưng cũng khó. Đọc các bài viết của bạn mới có cái nhìn cụ thể hơn.
    Chúc bạn mọi điều tốt đẹp,
     
    • Điểm chủ đề: 35
  • 02-18-2011 09:20 AM trả lời

    Re: Thuật toán Apriori khai phá luật kết hợp

    Chào Anh Chức,
    Hôm trước em nghe anh nói anh sẽ giới thiệu về kỹ thuật phân cụm SOM (Self Organizing Map), em đang tìm hiểu về kỹ thuật này và trông chờ bài viết của anh về SOM. Nếu anh có tài liệu nào về SOM (tiếng Anh cũng được) anh có thể cho em xin với được không?.
    Email của em sẽ gởi cho anh qua private message.
    Em cảm ơn anh trước
    Hiền Giang
     
    • Điểm chủ đề: 20
  • 04-14-2013 07:06 AM trả lời

    • wander
    • 500 thành viên năng nổ nhất
    • Tham gia 04-14-2013
    • Điểm 20

    Re: Thuật toán Apriori khai phá luật kết hợp

    Cảm ơn về bài viết rất dễ hiểu của bạn,
    mình chỉ có 1 thắc mắc nhỏ ở bước thứ 2 và bước thứ 3, nếu bước thứ 2 bạn đã lọc được frequent itemset rồi thì bản thân nó chính là Ck, sao cần bước thứ 3 làm gì nữa hả bạn.
    Thân! 
    • Điểm chủ đề: 20
  • 09-08-2014 08:48 PM trả lời

    Re: Thuật toán Apriori khai phá luật kết hợp

    Thầy hoặc anh chị nào biết thì vui lòng hướng dẫn giúp em cách tính độ chính xác và độ bao phủ cho ví dụ cơ sở giao dịch bán hàng trong bài Thầy đưa ra

    Sau khi áp dụng Apriori cho cơ sở giao dịch bán hàng thì được các luật kết hợp sau (với min_sup= 40%, min_conf=70%)

    R1: Beer => Diaper  (support =60%, confidence = 75%)

    R2: Diaper =>Beer (support =60%,confidence = 75%)

    R3: Milk =>Beer (support =40%, confidence = 100%)

    R4: Baby Powder => Diaper (support =40%,confidence = 100%)

    Xin chân thành cảm ơn.
    • Điểm chủ đề: 20
Trang 1 trong số 1 (5 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems